Path: news.mathworks.com!not-for-mail From: <HIDDEN> Newsgroups: comp.soft-sys.matlab Subject: Re: How to solve this non-convex quadratically constrained quadratic programming Date: Fri, 20 Apr 2012 10:27:13 +0000 (UTC) Organization: Xoran Technologies Lines: 51 Message-ID: <jmrdm1$oam$1@newscl01ah.mathworks.com> References: <3072521.689.1334707719706.JavaMail.geo-discussion-forums@ynmm9> <jmljp0$jbi$1@newscl01ah.mathworks.com> <16329087.1512.1334757550839.JavaMail.geo-discussion-forums@ynmm10> <jmofmi$q63$1@newscl01ah.mathworks.com> <jmpbbh$n13$1@newscl01ah.mathworks.com> Reply-To: <HIDDEN> NNTP-Posting-Host: www-00-blr.mathworks.com Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: newscl01ah.mathworks.com 1334917633 24918 172.30.248.45 (20 Apr 2012 10:27:13 GMT) X-Complaints-To: news@mathworks.com NNTP-Posting-Date: Fri, 20 Apr 2012 10:27:13 +0000 (UTC) X-Newsreader: MATLAB Central Newsreader 1440443 Xref: news.mathworks.com comp.soft-sys.matlab:765312 "Matt J" wrote in message <jmpbbh$n13$1@newscl01ah.mathworks.com>... > > I also don't understand it. I can see that the code is recasting the problem as > > min. x'*H*x-g'*x > s.t. norm(x)*2=1 > > The Lagrange Multiplier equations for this, I find to be > > (H-lambda*I)*x=g > > It is also clear to me that the required lambda will be the optimal objective function value, so minimizing or maximizing lambda corresponds to minimizing or maximizing the objective. > > However, I cannot see how the above Lagrange multiplier equations are equivalent to the quadratic eigenvalue problem > > ( (H*H - g*g') + (-2*H)*lambda + I*lambda^2 )*x=0 ================== I think I've figured out how to complete the derivation, at least of the quadratic eigenvalue problem. I'll just include it now for posterity readers. The Lagrange multiplier equations are g=(H-lambda*I)*x Right multiplying on both sides by g'*x leads to g*g'*x = (H-lambda*I)*x*(g'*x) = (H-lambda*I)*(x*g')*x = (H-lambda*I)*(g*x')*x = (H-lambda*I)*g*(x'*x) Substituting the feasibility constrant x'*x=1 and the original Lagrange Multiplier equation g=(H-lambda*I)*x on the RHS leads to (g*g')*x = ((H-lambda*I)^2)*x which after expanding ((H-lambda*I)^2) and re-arranging becomes ( (H*H - g*g') + (-2*H)*lambda + I*lambda^2 )*x=0 So, the optimal lambda must satisfy the above polynomial eigenvalue problem. But which solution is desired? Rearranging the original Lagrange multiplier equation lambda*x =H*x-g Premultiplying by x' on both sides and using x'*x=1 again leads to lambda = x'*H*x-g'*x =objective So taking the minimum/maximum solution to the polynomial eigenvalue problem is equivalent to minimizing/maximizing the objective. Finally, once the optimal lambda is known, the Lagrange multiplier equation can be solved for x. x=(H-lambda*I)\g This assumes (H-lambda*I) is non-singular. Otherwise, there is an affine space of solution candidates and the intersection of this affine space with the unit sphere x'*x=1 might give a non-unique space of final solutions??? I'll have to think about that a bit more.