Docplex Error: Model has non-convex objective

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.

• 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). Sep 9 '20 at 20:02

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.

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.

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).