# Solving a Minimization Problem With a Limited Set of Vector Inputs

My numerical analysis skills are a bit rusty on this, I plan to use scipy/numpy or octave to approach the solution but I need a pointer on how I should transform the problem in a way that it can be approached given available tools.

Given:

• $X$ is a vector of float values

• $Y$ is a vector of float values

• $X$ and $Y$ are of different length

• I only care about certain combinations of $X[i]$ and $Y[j]$ not every combination.

Solve:

For $X$ and $Y$ such that $f(X[i], X[j]) \approx 0$ (as close to zero as possible) and the overall total $f(X,Y) \approx 0$. That is, I want the least total variance from zero but also want the least possible variance from zero on a per pair basis. That is, I could get to $f(X,Y) = 0$ even if $f(X[1], Y[2]) = 35$ and $f(X[2], Y[1]) = -35$ but want to avoid that solution if one exists with lower per pair variance.

Constraints:

• $Y$ is bounded, that is all values in $Y$ should be $1.0 \leq Y[i] \leq 10.0.$

My initial thought, is to create a system of equations based on the combinations of $X[i]$ and $Y[j]$ that I care about. But, after looking over the SciPy optimization tools available, they only seem to accept a single vector for input, which would make it difficult to impose a constraint on the $Y$ vector (I think). Given my dataset, I would also be looking at roughly $3700$ equations in the system which seems a bit much. I also don't know how to approach the problem with minimizing both the overall variance and the individual pair variance.

Thanks in advance for any guidance!

EDIT: the nature of $f$

$f$ is of the form $f(X[i],Y[j]) = X[i] * Y[j] - C[i][j]$ where $C[i][j]$ is a constant looked up based on the vector indexes used.

Basically the root problem is, I have a set of values that were calculated for a given pair of vector indexes $i,j$. We need to calculate these a different way, but minimize the difference in the result vs the old calculation. The calculations are similar but not similar enough to allow an exact transformation between the two.

• What is f? $\phantom{kcksdfj}$ – fedja Feb 13 '13 at 21:12
• @fedja see my edit – Mark Feb 13 '13 at 21:26
• @fedja I think my initial edit was squashed as a mod was fixing my latex failure, added it back now. – Mark Feb 13 '13 at 21:45
• OK. What is $f(X,Y)$ then ($f$ is a function of two scalar variables and $X,Y$ are vectors...) – fedja Feb 13 '13 at 22:49
• Are $X$ and $Y$ given and are you then looking for the indices $i$ and $j$ that realize the objective you mentioned? Or are you looking for the values of the components of $X$ and $Y$ such that, etc.? – Dominique Feb 13 '13 at 23:32

You can certainly do this with the usual optimization tools. Instead of dealing with two unknown vectors $X=(x_1,x_2,\ldots,x_m)$ and $Y=(y_1,y_2,\ldots,y_n)$, just put them all in a single vector $Z=(x_1,x_2,\ldots,x_m,y_1,y_2,\ldots,y_n)$ that is the concatenation of the two. Then when you want to define your objective and constraints involving $x_i$ and $y_j$, you just have to take a little bit of care to use the corresponding entries of $Z$ instead.
One problem I can foresee is that your optimum is likely to not be unique. For example, you could replace all the $x_i$ by $ax_i$ for any nonzero number $a$ and replace $y_j$ by $y_j/a$, and your function values $f(x_i,y_j)=x_iy_j-c_{ij}$ would not change at all.
• Thanks, this is what I've been leaning toward. I knew there were infinite possible 'best' answers and that was the reason for bounding $Y$. More specifically I would prefer, for outside reasons, for $Y$ $>=$ 1.0 always, and preferably as close to 1.0 as is possible. – Mark Feb 15 '13 at 3:44