1
$\begingroup$

My objective function is $\frac{1}{2}w^{T}Vw - P^{T}w$ with $V$ a covariance matrix (hence semidefinite positive), $P$ a column vector and $w$ a vector of semi-continuous variables.

Given that the objective function is a quadratic form, the problem is convex. However, whenever I try to solve my problem I have the following error :

Error: Model has non-convex objective

DOcplexException: Model<MIQP> did not solve successfully

The problem is clearly convex though, and I have checked that all the eigenvalues of $V$ are positive or null. When I replace $V$ by a trivial semidefinite positive matrix such as the identity matrix, the algorithm works and returns the solution, so the error must come from the matrix $V$.

Is there any way to know why there's a problem with $V$ ? It is a bounded matrix with no NaN values.

$\endgroup$
  • 1
    $\begingroup$ Suppose you add a small (but not too small) multiple of the identity matrix to V. Does CPLEX then solve the model? If so, it might be a numerical precision error (factoring of the matrix leaving CPLEX seeing what looks like a negative eigenvalue to it). $\endgroup$ – prubin Sep 9 at 20:02
3
$\begingroup$

The comment by @prubin is spot on.

The V matrix is probably being numerically evaluated as not positive semidefinite by CPLEX. That can easily happen when one ore more eigenvalues are what you call null, i.e., theoretically equal to zero, i.e., zero in exact arithmetic.

But CPLEX is using double precision floating point arithmetic, not exact arithmetic, so eigenvalues can numerically evaluate to negative. Or equivalently, a Cholesky decomposition can fail due to a negative diagonal element occurring in the decomposition which could not occur if the matrix were numerically positive semidefinite.

Convex QP solvers, such as CPLEX with optimalitytarget =1, and Mosek, among others, can be quite fussy, and will produce an error message if the smallest eigenvalue numerically evaluates to even the slightest magnitude negative number. If this is indeed the cause, again per @prubin 's suggestion, adding a small multiple, such as 1e-8, of the Identity matrix to V is a reasonable way of dealing with this. I will defer to you as ro whether your model formulation, containing a rank-deficient covariance matrix, is a good formulation for whatever your intended purpose (unbeknownst to me) of your model is.

| improve this answer | |
$\endgroup$
2
$\begingroup$

Cplex can minimize convex quadratic objectives, or maximize concave ones. For example, minimizing $x^2+y^2$ is OK, but minimizing $x^2 -y^2$ is not.

See this page for more details:

As mentioned in the page, you can set the parameter optimalitytarget to 2 to proceed and accept the risk of finding a local optimum. If so, Cplex will not stop and look for an optimum (possibly local).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your hint Philippe. However in the IBM's page they suggest to use the parameter optimality target if the quadratic term in the objective function is not PSD. Mine is a PSD matrix since it is a covariance matrix so in my opinion setting the optimality target parameter may not be the right solution here. $\endgroup$ – FredNgu Sep 9 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.