Topic
• 12 replies
• Latest Post - ‏2013-02-20T23:55:38Z by EdKlotz
7929 Posts

# Pinned topic positive semi-definite quadratic constraint problem

‏2013-01-03T16:15:22Z |
Hi,

I am trying to solve a quadratic programing problem with quadratic constraints. My problem is with the constraints. Ordinarily quadratic constraints should take the form of:

b x + x T Q x < r

However, for my problem, the constraints instead take the form of:

b x - x T Q x < r

Q is positive semi-definite. However, if I try to redefine a new matrix K = - Q to form a new equation:

b x + x T K x < r

the problem cannot be solved, because K is not positive semi-definite.

Any thoughts on how to solve this problem??
Thanks
Updated on 2013-02-20T23:55:38Z at 2013-02-20T23:55:38Z by EdKlotz
7929 Posts

#### Re: positive semi-definite quadratic constraint problem

‏2013-01-03T17:02:21Z
Aren't you not making a convex function concave by changing the sign? If so, changing the <= r to >= r should make it PSD.

Regards,
Vivek.
7929 Posts

#### Re: positive semi-definite quadratic constraint problem

‏2013-01-03T20:56:01Z
Aren't you not making a convex function concave by changing the sign? If so, changing the <= r to >= r should make it PSD.

Regards,
Vivek.
Hi Vivek,

Do you know if there is an option in CPLEX to handle quadratic constraints which are > (the basic documentation defines the constraints as < ). If so, do you know what the syntax for that option is?

Marshall
7929 Posts

#### Re: positive semi-definite quadratic constraint problem

‏2013-01-03T21:11:31Z
Hi Vivek,

Do you know if there is an option in CPLEX to handle quadratic constraints which are > (the basic documentation defines the constraints as < ). If so, do you know what the syntax for that option is?

Marshall
There's no easy fix. b x - x^T^ Q x < r with Q psd causes the feasible region not to be convex. CPLEX (as well as all LP/MIP/QP solvers and most but not all NLP solvers) requires the feasible region (after relaxing any integrality restrictions) to be convex.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
7929 Posts

#### Re: positive semi-definite quadratic constraint problem

‏2013-01-04T03:38:22Z
There's no easy fix. b x - x^T^ Q x < r with Q psd causes the feasible region not to be convex. CPLEX (as well as all LP/MIP/QP solvers and most but not all NLP solvers) requires the feasible region (after relaxing any integrality restrictions) to be convex.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
Hi Paul,

Are there any NLP solvers that you would recommend to deal with this problem?

Thanks,

Marshall
7929 Posts

#### Re: positive semi-definite quadratic constraint problem

‏2013-01-04T05:40:09Z
Hi Vivek,

Do you know if there is an option in CPLEX to handle quadratic constraints which are > (the basic documentation defines the constraints as < ). If so, do you know what the syntax for that option is?

Marshall
Hi Marshall,

The CPXaddqconstr() in C Callable API has support for adding both <= (L) and >= (G) type QCP constraints.

Pls refer: http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r4/index.jsp?topic=%2Filog.odms.cplex.help%2Frefjavacplex%2Fhtml%2Filog%2Fcplex%2FIloCplex.html

Regards,
Vivek.
7929 Posts

#### Re: positive semi-definite quadratic constraint problem

‏2013-01-04T05:46:13Z
Hi Marshall,

The CPXaddqconstr() in C Callable API has support for adding both <= (L) and >= (G) type QCP constraints.

Pls refer: http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r4/index.jsp?topic=%2Filog.odms.cplex.help%2Frefjavacplex%2Fhtml%2Filog%2Fcplex%2FIloCplex.html

Regards,
Vivek.

Regards,
Vivek.
7929 Posts

#### Re: positive semi-definite quadratic constraint problem

‏2013-01-04T13:39:22Z
Thanks Vivek! I'll check it out.

Marshall
7929 Posts

#### Re: positive semi-definite quadratic constraint problem

‏2013-01-04T21:17:18Z
Hi Paul,

Are there any NLP solvers that you would recommend to deal with this problem?

Thanks,

Marshall
I have no first-hand experience with nonconvex problems, but you might be interested in https://groups.google.com/forum/?fromgroups=#!topic/knitro/xRZA5kDNaQ8.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
• Erwin_Kalvelagen
2 Posts

#### Re: positive semi-definite quadratic constraint problem

‏2013-01-04T21:44:07Z
I have no first-hand experience with nonconvex problems, but you might be interested in https://groups.google.com/forum/?fromgroups=#!topic/knitro/xRZA5kDNaQ8.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
GloMIQO by Floudas e.a. (http://helios.princeton.edu/GloMIQO/) may be another candidate for this type of problem.

Erwin
7929 Posts

#### Re: positive semi-definite quadratic constraint problem

‏2013-01-05T13:57:25Z
GloMIQO by Floudas e.a. (http://helios.princeton.edu/GloMIQO/) may be another candidate for this type of problem.

Erwin
Thanks!
7929 Posts

#### Re: positive semi-definite quadratic constraint problem

‏2013-02-20T18:34:06Z
Hi,

I did try to simply change the sign of the inequality in CPXaddqconstr. As a number of you suggested, this did not resolve the problem (the constraint was still not positive semi-definite). I will try some of the other solvers that were suggested.

Thanks very much for all the help!

Marshall
• EdKlotz
357 Posts

#### Re: positive semi-definite quadratic constraint problem

‏2013-02-20T23:55:38Z
Hi,

I did try to simply change the sign of the inequality in CPXaddqconstr. As a number of you suggested, this did not resolve the problem (the constraint was still not positive semi-definite). I will try some of the other solvers that were suggested.

Thanks very much for all the help!

Marshall
> YPT9_Marshall_Sussman wrote:
> Hi,
>
> I did try to simply change the sign of the inequality in CPXaddqconstr. As a number of you suggested, this did not resolve the problem (the constraint was still not positive semi-definite). I will try some of the other solvers that were suggested.
>
> Thanks very much for all the help!
>
> Marshall
Regarding more general nonlinear solvers, I have found the solvers section of the GAMS web site to contain quite a bit of useful information on a variety of solvers. The descriptions there may help you assess which solver would work well on your particular type of problem. The URL is http://www.gams.com/solvers/index.htm.

Regarding CPLEX, there are a couple of things you could try.

1) Given that Q is positive semi definite, you know that Q can be represented as
L'L (i.e. Q has a Cholesky factorization. You could then add the linear constraints
y - Lx = 0 and replace x'Qx with y'y in your quadratic constraint. You now have a
separable quadratic expression that you can approximate with piecewise linear functions. CPLEX supports that. However, this reformulation increases the problem
size significantly, adding the y - Lx = 0 constraints and introducing variables for
piecewise linear term for each element of the y vector of variables. So, this may
run slower than just using a good nonlinear solver.

2) Your problem is not convex, but it involves a special type of nonconvexity that
you might be able to address via some fairly simple discrete constraints. Let's
have a look at the simplest case, namely a single variable, and Q is the identity
matrix:

bx - x^2 <= r
x^2 - bx >= -r // multiply by -1
(x - b/2)^2 >= (b^2)/4 - r // complete the square

How, we have two data dependent cases to consider:

a) if (b^2)/4 - r <= 0, the constraint

(x - b/2)^2 >= (b^2)/4 - r

always holds. Hence, your equivalent original constraint bx - x^2 <= r
also always holds. In that case, you can just remove this constraint and solve

b) if (b^2)/4 - r > 0, the constraint

(x - b/2)^2 >= (b^2)/4 - r

holds if

x - b/2 >= sqrt ((b^2)/4 - r) or
x - b/2 <= -sqrt ((b^2)/4 - r)

CPLEX supports modeling of this type of disjunctive constraint, so in this
case you can replace your quadratic constraint and solve the model as a MIQP