Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
How to solve this non-convex quadratically constrained quadratic programming

Subject: How to solve this non-convex quadratically constrained quadratic programming

From: Lucy

Date: 18 Apr, 2012 00:08:39

Message: 1 of 11

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!

Subject: How to solve this non-convex quadratically constrained quadratic programming

From: Roger Stafford

Date: 18 Apr, 2012 02:13:14

Message: 2 of 11

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

Subject: How to solve this non-convex quadratically constrained quadratic programming

From: Bruno Luong

Date: 18 Apr, 2012 05:34:24

Message: 3 of 11

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

Subject: How to solve this non-convex quadratically constrained quadratic programming

From: Lucy

Date: 18 Apr, 2012 13:59:10

Message: 4 of 11

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?

Subject: How to solve this non-convex quadratically constrained quadratic programming

From: Bruno Luong

Date: 18 Apr, 2012 14:12:07

Message: 5 of 11

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.

Subject: How to solve this non-convex quadratically constrained quadratic programming

From: David Epstein

Date: 19 Apr, 2012 07:43:15

Message: 6 of 11

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

Subject: How to solve this non-convex quadratically constrained quadratic programming

From: Bruno Luong

Date: 19 Apr, 2012 12:25:07

Message: 7 of 11

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

Subject: How to solve this non-convex quadratically constrained quadratic programming

From: Matt J

Date: 19 Apr, 2012 15:35:13

Message: 8 of 11

"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

Subject: How to solve this non-convex quadratically constrained quadratic programming

From: Matt J

Date: 20 Apr, 2012 10:27:13

Message: 9 of 11

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

Subject: How to solve this non-convex quadratically constrained quadratic programming

From: Bruno Luong

Date: 20 Apr, 2012 11:33:12

Message: 10 of 11

"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

Subject: How to solve this non-convex quadratically constrained quadratic programming

From: Matt J

Date: 22 Apr, 2012 16:35:09

Message: 11 of 11

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

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us