Global optimization in MATLAB

7 views (last 30 days)
rihab
rihab on 4 Dec 2015
Commented: rihab on 8 Dec 2015
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.
  10 Comments
Walter Roberson
Walter Roberson on 7 Dec 2015
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
rihab on 8 Dec 2015
I appreciate your suggestion. Thanks!

Sign in to comment.

Answers (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!