Global optimization in MATLAB

I have to find x that minimizes:

 sigma{k}(x'*A_k*x - b_k)^2

where A_k are 4 x 4 positive definite matrices (A_1, A_2,...A_k), x is 4 x 1 vector and b_k are scalars (b_1,b_2,...b_k). Is there a function to solve this OP in MATLAB such that x will always be a global minimum? I would highly appreciate suggestions.

[Torsten]

Try fminsearch with different starting values for x.

Best wishes

Torsten.

[rihab]

I have already tried that. Different starting values for x yield different solutions of x. Since this non-linear OP has multiple local minima(multiple x that solve this OP), I am not able to choose the best solution of x. Is there any way to solve this OP in MATLAB such that x will always be a global minimum(best/global solution)?

[Torsten]

The global optimization toolbox might be an option, although my guess is that it does not much more than I suggested: systematically changing the initial guess and choose the solution with minimal value of the objective.

Did you check that for the solutions you got, the first derivative of the objective is really zero (i.e. they are really local minima) ?

Best wishes

Torsten.

[rihab]

Thank you for your suggestion. I will keep that in mind.

Well the gradient of the objective function isn't really zero, its of the order 1e-3. Hessian matrix is indefinite. But the solutions seem to be good estimates (because when I plot the respective graphs of sigma{k}(x'*A_k*x) and sigma{k}(b_k), the former seems to be a good estimate of the latter). Is it possible to solve this problem analytically?

[Torsten]

Is this problem discussed in books/papers on approximation ? Does it have a special name ?

Best wishes

Torsten.

[Walter Roberson]

My analytic analysis suggests there might be a global minima. The symmetry implied by the positive definite matrix allows the formula to be simplified a fair bit. For any number of terms, k, the expression turns out to be quartic in each of the 4 x values; consequently the derivative with respect to each is cubic. The analytic roots of the cubic are huge to write out so you would go for the numeric solutions. With there being only three zeros for each of the 4 variables, in theory you can find all the combinations and test them. It might not be the most fun of code...

[rihab]

No, I have defined this OP based on my work.

[rihab]

@walter thank you for your suggestion. Yes the derivative with respect to each is cubic which is making it more difficult to solve. And even if I put the derivative with respect to each to be zero and solve for x, the only solution that I get is x=0! So now I am changing the initial guess vector in fminsearch and choosing the solution that yields the minimum of the objective function. Any comments on this?

[Walter Roberson]

I took a simple version,

A_1 = [[586931937100, 482570600053, 1151138491863/2, 1163850944977/2]; [482570600053, 303902179778, 1702736256419/2, 647477528317/2]; [1151138491863/2, 1702736256419/2, 382388810370, 1142892433017/2]; [1163850944977/2, 647477528317/2, 1142892433017/2, 664409229793]]
k1 = 1234

Under the assumption of real X, this lead to

(586931937100*X1^2 + 965141200106*X1*X2 + 1151138491863*X1*X3 + 1163850944977*X1*X4 + 303902179778*X2^2 + 1702736256419*X2*X3 + 647477528317*X2*X4 + 382388810370*X3^2 + 1142892433017*X3*X4 + 664409229793*X4^2-1234)^2

Maple had no problem finding the minima 0 using Maple's minimize() with 'location' option.

I then proceeded using incremental differentiation by X1, solve(), pick a root, substitute that back into the equation to reduce the number of variables, and so on. I just picked the first symbolic root returned each time, except that at the end of the process X4 had roots at 0 and +/- a value, and the root at 0 did not lead to a global minima. But I substituted in the next X4 in the list and promptly got a global sum of 0, after which I could back-substitute to get the values of X3, X2, X1.

Although 0 would have appeared as one of the roots of the derivatives, there is no requirement to accept it; it just points to one of the extrema. You can test the sum it generates and continue.

Finding the minima in this way does assume that you have the Symbolic toolbox; writing out all of the possibilities in expression form gets to be too large.

[rihab]

I appreciate your suggestion. Thanks!