Convexivity questions

[Ashley Thornton]

Hi all

I'm trying to check convexity of my problem and to do that I need to get my Q and A matrices. Is the only way to do this to write something that parses the information about each constraint in the .lp file into the matrix structure in the .mps file? Or should I not worry as I assume Gurobi would tell me if my A or Q were not positive semi definite?

I have seen some people getting errors where it will linearly shift the diagonal by a constant?

Can anyone shed some light on the area?

Cheers!

Ash 

[Tobias Achterberg]

In theory, Gurobi can only solve problems where all the Q matrices (objective
function and the ones in the constraints) are positive semi-definite, or define
(rotated) second-order cones, see
http://www.gurobi.com/documentation/6.5/refman/c_grbaddqconstr.html

But in addition, presolve might turn a model that violates these restrictions
into one that Gurobi can solve. For example, removing fixed variables and the
associated columns and rows from the Q matrices may turn a non-PSD matrix into a
PSD matrix.

Special presolve operations can be applied for binary variables in order to
actively turn a non-PSD matrix into a PSD matrix. Namely, one can exploit the
fact that for a binary variable x we have x^2 = x. Hence, you can easily add
d*(x^2 - x) to constraints or the objective, which adds d to the diagonal of the
Q matrix and introduces an additional linear term -d*x, which can easily be
dealt with. If all variables that appear in the Q matrix are binary, then it
will always be possible by choosing appropriate d values for the individual
variables to turn the Q matrix into a diagonally-dominant matrix, which is PSD.
If only some of the variables are binary, this may still suffice to get a PSD
matrix.

Another possibility to solve systems with non-PSD matrices in the presence of
binary variables is to linearize the quadratic terms. Namely, if you have the
term x*y and x is binary, then you can introduce a new variable z = x*y (which
turns the quadratic term x*y into a linear term in z) and enforce the
relationship of z with x and y by linear constraints. This is also done in
Gurobi in certain cases.


So, the conclusion is: if all your Q matrices are PSD or (rotated) cones, then
Gurobi will be able to handle the problem. If not, then Gurobi might still be
able to handle the problem, but it may also fail with the error stating that a Q
matrix is non-PSD.


Regards,

Tobias