Originally posted by: Tomtom369

Hello, 

I have a quadratic problem that I'm trying to solve with cplex. When I solve the problem I get the error "CPLEX Error  5002: Q in 'objective' is not positive semi-definite". So I tried to follow the suggestion in http://www-01.ibm.com/support/docview.wss?uid=swg21399951 but I can't get how to do that.

So I have some question:

is Q the Hessian of the entire objective function or just the quadratic part?

If I remove all the constraint from the problem and I keep the same objective function the solver starts to work. How is this possible?

In the link it is said that one approach is to perturbate the diagonal of the Q matrix, how can i do that if Q is just the hessian of the quadratic part?  ( I can't set a non-quadratic term in the quadratic part of the objective function)

Is it possible to print the Q matrix?

Thanks,

Thomas

Hi,

have you tried to read

https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.8.0/ilog.odms.cplex.help/CPLEX/Parameters/topics/OptimalityTarget.html

?

and change that setting to 3 ?

regards

Originally posted by: Tomtom369

Yes,

It doesn't work

Originally posted by: Mark L. Stone

Does your problem have quadratic constraints or linear constraints?  If quadratic,, what is the Hessian of the constraints (of the quadratxc, where constraint is quadratic <= 0"?

Hessian of the objective = Hessian of the quadratic portion of objective, because Hessian of the non-quadratic portion, i.e., linear and constant terms, is the matrix of all zeros.

Originally posted by: Tomtom369

The constraints are all linear.

The objective is in the form: linear part + [K1 a1 * b1+ K2 a2 * b2+ Kn an * bn] so the diagonal is 0. This matrix is indefinite, however, having Ki >= 0 and the domains of ai and bi are >= 0 so as the problem is convex. Is there any way to make this problem work with cplex?

Originally posted by: Mark L. Stone

OP wrote "The objective is in the form: linear part + [K1 a1 * b1+ K2 a2 * b2+ Kn an * bn] so the diagonal is 0. This matrix is indefinite, however, having Ki >= 0 and the domains of ai and bi are >= 0 so as the problem is convex. Is there any way to make this problem work with cplex? "

Huh?  The Hessian of a quadratic is a matrix of constants, i.e., independent of variable values. Therefore, a quadratic objective is either convex everywhere or nowhere.

The Hessian is indefinite, so it is not convex. Use optimalitytarget =2  to try to get locally optimal solution,or optimalitytargett  =3 to try to get globally optimal solution.

Originally posted by: BoJensen

Posting Ed Klotz's reply as he had technical issues posting in the forum :

Mark is correct; even if the variable domains specify a set of solutions for which x'Qx >= 0, CPLEX's (and most if not all) algorithms rely on the positive semi definiteness of the Q matrix everywhere to compute a Cholesky factorization of Q.   If Q is indefinite, no such factorization exists and the algorithm cannot proceed.   You need an algorithm which operates on Q that does not perform such calculations.

Meanwhile, when you said you said you set the solutiontarget parameter to 3 and it "didn't work", what do you mean?   Did CPLEX run, but it did not prove optimality?   If so, try setting the rlt cuts parameter to its more aggressive settings of 2 or 3; see if that helps.   Also, make sure you provide upper bounds on the variables that are as tight as possible.

If performance is the issue with solutiontarget set to 3, please post a log of the run to the forum; maybe someone here can point out a way to get faster performance is the performance bottleneck is clear from the log.

Otherwise, as Mark pointed out, you could try running with solutiontarget = 2 to try to get a local optimum.   If nothing else, the additional log file output might shed additional insight on the challenging aspects of the model.

Originally posted by: Christian Bliek

Hello,

The hessian consists of second order derivatives. So the hessian of the linear terms is 0; the hessian corresponds with the quadratic part.

If "it works" if you remove all constraints, the only explanation I see is that presolve is then able to simplify the objective and that this presolved objective is convex.

You say that the quadratic part is of the for sum_i Ki ai*bi with Ki, ai, bi >= 0. Let's take i = 1 and K1 = 1 so we have a1*b1. That is not a convex problem. It has all points with a1= 0 or b1 = 0 as minimum. 

You say that setting the optimality target to 3 "doesn't work", it should. What do you mean by "doesn't work"?

Christian.