Thread Subject:

How to solve this non-convex quadratically constrained quadratic programming

How to solve this quadratically constrained quadratic programming
problem?

Hi all,

Could you please shed some lights on this? (Not a homework problem)

I am looking for solutions to solve the following problem:

max ||Xb||^2
s.t. ||b-b 0 ||^2 <a,||b||^2=1

Here the norms are 2-norms.

X is a matrix, b 0 and a are parameters. All of X , a and b 0
are given.

I would like to solve for the vector b .

This is not a convex problem.

What's the best way to solve this problem?

Thank you!

Lucy <comtech.usa@gmail.com> wrote in message <3072521.689.1334707719706.JavaMail.geo-discussion-forums@ynmm9>...
> max ||Xb||^2
> s.t. ||b-b 0 ||^2 <a,||b||^2=1
> Here the norms are 2-norms.
> X is a matrix, b 0 and a are parameters. All of X , a and b 0
> are given.
> I would like to solve for the vector b .
- - - - - - - - - -
  It looks like a candidate for matlab's 'fmincon' function in the Optimization Toolbox, using only the nonlinear constraint functions, 'c(x)' and 'ceq(x)'. Of course the difficulty you face will be specifying an appropriate initial estimate for the 'x0' input, since it is possible in some cases to end up on a merely local minimum. You will want to be minimizing -||Xb||^2 . If you haven't used 'fmincon' before, it would be wise to read through the documentation for it very thoroughly, as well as other pertinent Optimization Toolbox documentation.

Roger Stafford

Lucy <comtech.usa@gmail.com> wrote in message <3072521.689.1334707719706.JavaMail.geo-discussion-forums@ynmm9>...
> How to solve this quadratically constrained quadratic programming
> problem?
>
> Hi all,
>
> Could you please shed some lights on this? (Not a homework problem)
>
> I am looking for solutions to solve the following problem:
>
> max ||Xb||^2
> s.t. ||b-b 0 ||^2 <a,||b||^2=1
>
>

This might take a close look of, which essentially solves the above problem with single constraint:

http://www.mathworks.com/matlabcentral/fileexchange/27596-least-square-with-2-norm-constraint

You can start first to ignore the inequality constraint | b - b0 |^2 <= a, and solve the optimization with the spherical constraint, or the opposite minimizing =|Xb| such that |b-b0|^2=1. If the solution satisfies the (ignored) inequality, then the problem is solved.

Otherwise you might take a look at the paper referred by the FEX to see if the formulation can be twisted to your problem with two equalities:

max ||Xb||^2
s.t. ||b-b 0 ||^2 =a, ||b||^2=1

% Bruno

On Wednesday, April 18, 2012 12:34:24 AM UTC-5, Bruno Luong wrote:
> Lucy <comtech.usa@gmail.com> wrote in message <3072521.689.1334707719706.JavaMail.geo-discussion-forums@ynmm9>...
> > How to solve this quadratically constrained quadratic programming
> > problem?
> >
> > Hi all,
> >
> > Could you please shed some lights on this? (Not a homework problem)
> >
> > I am looking for solutions to solve the following problem:
> >
> > max ||Xb||^2
> > s.t. ||b-b 0 ||^2 <a,||b||^2=1
> >
> >
>
> This might take a close look of, which essentially solves the above problem with single constraint:
>
> http://www.mathworks.com/matlabcentral/fileexchange/27596-least-square-with-2-norm-constraint
>
> You can start first to ignore the inequality constraint | b - b0 |^2 <= a, and solve the optimization with the spherical constraint, or the opposite minimizing =|Xb| such that |b-b0|^2=1. If the solution satisfies the (ignored) inequality, then the problem is solved.
>
> Otherwise you might take a look at the paper referred by the FEX to see if the formulation can be twisted to your problem with two equalities:
>
> max ||Xb||^2
> s.t. ||b-b 0 ||^2 =a, ||b||^2=1
>
> % Bruno

Thanks Bruno!

But mine was "MAX" though...

Any more thoughts?

Lucy <comtech.usa@gmail.com> wrote in message <16329087.1512.1334757550839.JavaMail.geo-discussion-forums@ynmm10>...
> On Wednesday, April 18, 2012 12:34:24 AM UTC-5, Bruno Luong wrote:
> > Lucy <comtech.usa@gmail.com> wrote in message <3072521.689.1334707719706.JavaMail.geo-discussion-forums@ynmm9>...
> > > How to solve this quadratically constrained quadratic programming
> > > problem?
> > >
> > > Hi all,
> > >
> > > Could you please shed some lights on this? (Not a homework problem)
> > >
> > > I am looking for solutions to solve the following problem:
> > >
> > > max ||Xb||^2
> > > s.t. ||b-b 0 ||^2 <a,||b||^2=1
> > >
> > >
> >
> > This might take a close look of, which essentially solves the above problem with single constraint:
> >
> > http://www.mathworks.com/matlabcentral/fileexchange/27596-least-square-with-2-norm-constraint
> >
> > You can start first to ignore the inequality constraint | b - b0 |^2 <= a, and solve the optimization with the spherical constraint, or the opposite minimizing =|Xb| such that |b-b0|^2=1. If the solution satisfies the (ignored) inequality, then the problem is solved.
> >
> > Otherwise you might take a look at the paper referred by the FEX to see if the formulation can be twisted to your problem with two equalities:
> >
> > max ||Xb||^2
> > s.t. ||b-b 0 ||^2 =a, ||b||^2=1
> >
> > % Bruno
>
> Thanks Bruno!
>
> But mine was "MAX" though...
>
> Any more thoughts?

Hint: You need to change only one line in the code to solve max problem.

Lucy <comtech.usa@gmail.com> wrote in message <16329087.1512.1334757550839.JavaMail.geo-discussion-forums@ynmm10>...
> On Wednesday, April 18, 2012 12:34:24 AM UTC-5, Bruno Luong wrote:
> > Lucy <comtech.usa@gmail.com> wrote in message <3072521.689.1334707719706.JavaMail.geo-discussion-forums@ynmm9>...
> > > How to solve this quadratically constrained quadratic programming
> > > problem?
> > >
> > > Hi all,
> > >
> > > Could you please shed some lights on this? (Not a homework problem)
> > >
> > > I am looking for solutions to solve the following problem:
> > >
> > > max ||Xb||^2
> > > s.t. ||b-b 0 ||^2 <a,||b||^2=1
> > >
> > >
> >
> > This might take a close look of, which essentially solves the above problem with single constraint:
> >
> > http://www.mathworks.com/matlabcentral/fileexchange/27596-least-square-with-2-norm-constraint
> >
> > You can start first to ignore the inequality constraint | b - b0 |^2 <= a, and solve the optimization with the spherical constraint, or the opposite minimizing =|Xb| such that |b-b0|^2=1. If the solution satisfies the (ignored) inequality, then the problem is solved.
> >
> > Otherwise you might take a look at the paper referred by the FEX to see if the formulation can be twisted to your problem with two equalities:
> >
> > max ||Xb||^2
> > s.t. ||b-b 0 ||^2 =a, ||b||^2=1
> >
> > % Bruno
>
> Thanks Bruno!
>
> But mine was "MAX" though...
>
> Any more thoughts?

Lucy: could you explain what you mean by max, especially since you insist on it so strongly? For example, many mathematicians would say that max{x: x<0} does not exist. On the other hand sup{x:x<0}=0. Since one of your constraints is a strict inequality, your problem as stated may have no solution. So I'll interpret your < as meaning <=.

I had a quick look at Bruno's code, but I didn't understand it. I assume it's a very good implementation of Lagrange Multipliers, applied to this particular situation. So it seems like an excellent start, though it doesn't seem all that likely that changing only one or two lines would be much of a help. I'm probably thinking too much like a pure mathematician. A lot depends on where your X comes from.

The set of b such that ||Xb|| = constant seems to me to be something like the product of an ellipsoidal surface with the kernel of X. Lagrange Multipliers (Bruno's code) should give the finite set of constants where this product is tangent to the sphere S given by ||b||^2 =1. The intersection of points of tangency will be (I think: in any case, even if I'm wrong in the details, this is the right way to think about your problem) a subsphere B of S. I assume, without checking, that the dimension of B is one less than the number of equal eigenvalues corresponding to B found by Bruno's code. Depending on the nature of your X, you may be able to assume, with probability one, that all Bruno's eigenvalues are distinct. If B intersects the open disk ||b- b0||^2 < a, then this will give one of a finite number of values of ||Xb|| to be considered. If all Bruno's eigenvalues are distinct (which is
pretty likely to be the result of any computer program because of floating point problems), then you get a sphere of dimension 0, that is a pair of antipodal points on S and the check will be particularly straightforward, but it would be straightforward anyway.

You next need to consider the possibility that the solution actually lies in the intersection N of the two spheres S and ||b-b0||^2=a. N may be empty which is fine, or non-empty, in which case it is a point or a lower dimensional sphere. You can now solve this case by restricting the whole problem to the smallest affine subspace containing N. This case can be done by Bruno's code.

Finally compare the finite set of solutions in the open disk with solutions in N and select the best one.
David

David is correct in many points.

1) The intersection of the two spheres is a sphere of dimension - 1. So the problem can reduce to two independent maximization with constraint 1, constraint 2, constraint 1 & 2.

2) The method is based on Lagrange multiplier

3) To change minimization to maximization, change the line #51 of spherelsq.m (FEX mentioned above) to

lambda = max(lambda);

That is it!

Bruno

"David Epstein" <David.Epstein.spam@remove.warwick.ac.uk> wrote in message <jmofmi$q63$1@newscl01ah.mathworks.com>...
>
> I had a quick look at Bruno's code, but I didn't understand it. I assume it's a very good implementation of Lagrange Multipliers, applied to this particular situation. So it seems like an excellent start, though it doesn't seem all that likely that changing only one or two lines would be much of a help. I'm probably thinking too much like a pure mathematician. A lot depends on where your X comes from.
====================

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

"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.

"Matt J" wrote in message <jmrdm1$oam$1@newscl01ah.mathworks.com>...
> "Matt J" wrote in message <jmpbbh$n13$1@newscl01ah.mathworks.com>...

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

For posterity readers, they should ackowledge this paper:

W. Gander, G. H. Golub, and U. Von Matt, "A constrained eigenvalue problem", Linear Algebra Appl., 114-115 (1989), pp. 815-839.

Bruno

"Matt J" wrote in message <jmrdm1$oam$1@newscl01ah.mathworks.com>...
>
> 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.
==============

I just realized that this part is wrong. The objective function is really

f(x) = 0.5*x'*H*x-g'*x

So, it's not clear to me why we want to minimize over the admissible lambda. Oh well, I guess the Gander et al paper explains it.