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.