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$>
References: <3072521.689.1334707719706.JavaMail.geo-discussion-forums@ynmm9> <jmljp0$jbi$> <16329087.1512.1334757550839.JavaMail.geo-discussion-forums@ynmm10> <jmofmi$q63$> <jmpbbh$n13$>
Reply-To: <HIDDEN>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: 1334917633 24918 (20 Apr 2012 10:27:13 GMT)
NNTP-Posting-Date: Fri, 20 Apr 2012 10:27:13 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1440443
Xref: comp.soft-sys.matlab:765312

"Matt J" wrote in message <jmpbbh$n13$>...
> 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


Right multiplying on both sides by g'*x  leads to

  = (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.


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.