Constraint Q not PSD for continuous variables

660 views
Skip to first unread message

Asif Arain

unread,
Oct 6, 2015, 11:48:55 AM10/6/15
to Gurobi Optimization
Hi, I am getting following error when the variable is continuous

gurobipy.GurobiError: Constraint Q not PSD (diagonal adjustment of 5.7e+02 would be required)

Here is my formulation.
min. |C| 
s.t. C'(GC+U) >= n

Where C is a column vector of continuous variables bounded between 0 and 1. G is square matrix of non-negative real numbers, U is a vector of non-negative real numbers, and n is a positive integer.
The error disappears when vector C contains BINARY variables instead of continuous.

Tobias Achterberg

unread,
Oct 7, 2015, 3:13:33 PM10/7/15
to gur...@googlegroups.com
I guess that your quadratic matrix C'G is indeed not positive semi-definite, and
thus, your quadratic constraint is not convex. So why does it work when the
variables are binary? This comes from Gurobi's presolve, which is able to
convert your matrix into a positive semi-definite one, by exploiting the fact
that for binary variables the equation x = x*x is valid. Then, we can add zeros
in the form of "x*x - x" to the constraint until the diagonal elements of the
matrix is large enough to make it PSD. Alternatively, one can linearize products
of a binary variable with some other (potentially non-binary) variable to get
rid of the quadratic constraints.

Depending on the circumstances, Gurobi does one or the other. If the variables
are continuous, however, there is no way to turn a non-PSD matrix into an
equivalent system with a PSD matrix.

Tobias
> --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "Gurobi Optimization" group.
> To unsubscribe from this group and stop receiving emails from it, send an email
> to gurobi+un...@googlegroups.com <mailto:gurobi+un...@googlegroups.com>.
> For more options, visit https://groups.google.com/d/optout.

--
-----------------------------------------------------------------
Dr. Tobias Achterberg
Senior Software Developer
Gurobi Optimization
achte...@gurobi.com

-----------------------------------------------------------------
Sitz der Gesellschaft: Bad Homburg v.d.H.
Registergericht: Bad Homburg v.d.H., HRB 12607
Geschäftsführer: Robert E. Bixby, Dirk Zechiel

Asif Arain

unread,
Oct 8, 2015, 11:41:30 AM10/8/15
to Gurobi Optimization
Thank you for the reply. I have tried G that is PSD by definition (its all eigenvalues are positive). To be precise, following in the example G matrix

G =
        1000          75          90         135         180          90
          75        1000          15          60         105         165
          90          15        1000          45          90         180
         135          60          45        1000          45         135
         180         105          90          45        1000          90
          90          90         180         135          90        1000

Further, I have simplified the constraint by removing U vector. Here is the updated formulation

min. |C| 
s.t. C'GC >= n

However, I am still getting the same error. Any idea please?

Renan Garcia

unread,
Oct 8, 2015, 12:09:27 PM10/8/15
to gur...@googlegroups.com
Gurobi accepts convex quadratic constraints of the form: x'Qx + q'x <= b, where Q is PSD.

However, if you rearrange your constraint to match this form, you'd get Q = -G, q = -U and b = -n. Thus, Q (or -G) would be negative semidefinite, and not PSD.

--

---
You received this message because you are subscribed to the Google Groups "Gurobi Optimization" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+un...@googlegroups.com.
Reply all
Reply to author
Forward
0 new messages