Thread Subject:

how to solve quadratic minimization problem with quadratic equality constraints?

Hello everyone,
Nowadays, I have faced a quadratic minimization problem with quadratic equality constraints. Is it a non-concave constrained optimization problem which CPLEX cannot handle? If so, how to solve? Is there any solver or software available?
Could you suggest something?
Many thanks.

On Tuesday, July 10, 2012 9:16:54 PM UTC-5, Hycere Hung wrote:
> Hello everyone,
> Nowadays, I have faced a quadratic minimization problem with quadratic equality constraints. Is it a non-concave constrained optimization problem which CPLEX cannot handle? If so, how to solve? Is there any solver or software available?
> Could you suggest something?
> Many thanks.


help the fmincon function

在 2012年7月11日星期三UTC+8下午1时32分35秒，（未知）写道：
> On Tuesday, July 10, 2012 9:16:54 PM UTC-5, Hycere Hung wrote:
> > Hello everyone,
> > Nowadays, I have faced a quadratic minimization problem with quadratic equality constraints. Is it a non-concave constrained optimization problem which CPLEX cannot handle? If so, how to solve? Is there any solver or software available?
> > Could you suggest something?
> > Many thanks.
>
>
> help the fmincon function

Okay, millions of thx.

Hi:

For your type of problem, both first and second derivatives are readily
available. So, ideally, you can calculate those and pass them to the
solver. Below is a pointer to an example in the documentation on how to
do this.

-Marcelo

---
Example: Constrained Minimization Using fmincon's Interior-Point
Algorithm with Analytic Hessian
http://www.mathworks.com/help/toolbox/optim/ug/brn4nh7.html#bri8026

On 7/10/2012 10:16 PM, honeyhycere@gmail.com wrote:
> Hello everyone,
> Nowadays, I have faced a quadratic minimization problem with quadratic equality constraints. Is it a non-concave constrained optimization problem which CPLEX cannot handle? If so, how to solve? Is there any solver or software available?
> Could you suggest something?
> Many thanks.
>

honeyhycere@gmail.com wrote in message <8857c2c6-a43c-4c0f-8342-8b2e8e415215@googlegroups.com>...
> Hello everyone,
> Nowadays, I have faced a quadratic minimization problem with quadratic equality constraints. Is it a non-concave constrained optimization problem which CPLEX cannot handle? If so, how to solve? Is there any solver or software available?
===========

This problem has an analytically known solution, which you could use if your problem isn't too large:

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

在 2012年7月11日星期三UTC+8下午10时26分07秒，Marcelo Marazzi写道：
> Hi:
>
> For your type of problem, both first and second derivatives are readily
> available. So, ideally, you can calculate those and pass them to the
> solver. Below is a pointer to an example in the documentation on how to
> do this.
>
> -Marcelo
>
> ---
> Example: Constrained Minimization Using fmincon's Interior-Point
> Algorithm with Analytic Hessian
> http://www.mathworks.com/help/toolbox/optim/ug/brn4nh7.html#bri8026
>
> On 7/10/2012 10:16 PM, honeyhycere@gmail.com wrote:
> > Hello everyone,
> > Nowadays, I have faced a quadratic minimization problem with quadratic equality constraints. Is it a non-concave constrained optimization problem which CPLEX cannot handle? If so, how to solve? Is there any solver or software available?
> > Could you suggest something?
> > Many thanks.
> >
Thank you, Marcelo.
I will give it a try.

在 2012年7月11日星期三UTC+8下午11时20分11秒，Matt J 写道：
> honeyhycere@gmail.com wrote in message <8857c2c6-a43c-4c0f-8342-8b2e8e415215@googlegroups.com>...
> > Hello everyone,
> > Nowadays, I have faced a quadratic minimization problem with quadratic equality constraints. Is it a non-concave constrained optimization problem which CPLEX cannot handle? If so, how to solve? Is there any solver or software available?
> ===========
>
> This problem has an analytically known solution, which you could use if your problem isn't too large:
>
> http://www.mathworks.com/matlabcentral/fileexchange/27596-least-square-with-2-norm-constraint

Hi, Matt,
In my problem, the H is semi-definite, and the quadratic equality constraint has the form of l*x + x'*Q*x = r. In this case, i don't think spherelsq can handle this.

Hycere Hung <honeyhycere@gmail.com> wrote in message <0ab635fa-2671-4b69-8d14-0f9135f164df@googlegroups.com>...

>
> Hi, Matt,
> In my problem, the H is semi-definite, and the quadratic equality constraint has the form of l*x + x'*Q*x = r. In this case, i don't think spherelsq can handle this.

Assuming Q is symmetric definite positive , the constraint

l*x + x'*Q*x = r, (2)

can be rewritten to

| C*x + d |^2 = p^2, where
 
C = sqrtm(Q)
d = 1/2 * (C\l')
p^2 - |d|^2 = r. (note: should double check my formula for error)

So after changing the variable y := C*x + d, the problem becomes minimizing quadratic with 2-norm constraint |y| = p.

Rather than changing variable, you could directly derive the QEP equation by Euler-Lagrage on (2) using the same technique as in the paper I cited.

Bruno (author of the FEX in question)

在 2012年7月12日星期四UTC+8上午9时52分36秒，Bruno Luong写道：
> Hycere Hung <honeyhycere@gmail.com> wrote in message <0ab635fa-2671-4b69-8d14-0f9135f164df@googlegroups.com>...
>
> >
> > Hi, Matt,
> > In my problem, the H is semi-definite, and the quadratic equality constraint has the form of l*x + x'*Q*x = r. In this case, i don't think spherelsq can handle this.
>
> Assuming Q is symmetric definite positive , the constraint
>
> l*x + x'*Q*x = r, (2)
>
> can be rewritten to
>
> | C*x + d |^2 = p^2, where
>
> C = sqrtm(Q)
> d = 1/2 * (C\l')
> p^2 - |d|^2 = r. (note: should double check my formula for error)
>
> So after changing the variable y := C*x + d, the problem becomes minimizing quadratic with 2-norm constraint |y| = p.
>
> Rather than changing variable, you could directly derive the QEP equation by Euler-Lagrage on (2) using the same technique as in the paper I cited.
>
> Bruno (author of the FEX in question)

Many thanks for your kindly help, Bruno
I will try it these days

在 2012年7月12日星期四UTC+8上午9时52分36秒，Bruno Luong写道：
> Hycere Hung <honeyhycere@gmail.com> wrote in message <0ab635fa-2671-4b69-8d14-0f9135f164df@googlegroups.com>...
>
> >
> > Hi, Matt,
> > In my problem, the H is semi-definite, and the quadratic equality constraint has the form of l*x + x'*Q*x = r. In this case, i don't think spherelsq can handle this.
>
> Assuming Q is symmetric definite positive , the constraint
>
> l*x + x'*Q*x = r, (2)
>
> can be rewritten to
>
> | C*x + d |^2 = p^2, where
>
> C = sqrtm(Q)
> d = 1/2 * (C\l')
> p^2 - |d|^2 = r. (note: should double check my formula for error)
>
> So after changing the variable y := C*x + d, the problem becomes minimizing quadratic with 2-norm constraint |y| = p.
>
> Rather than changing variable, you could directly derive the QEP equation by Euler-Lagrage on (2) using the same technique as in the paper I cited.
>
> Bruno (author of the FEX in question)
Many thanks for your kindly help, Bruno
I will try it these days