convexity check control for quadratic optimization problem

[rao.vi...@gmail.com]

Hi, 

I am solving the problem:   min x^{T}Qx  with respect to some linear constraints. I get the following error message 

even though by construction Q is a 35,000 X 35,000 PSD matrix. 

Mosek error: MSK_RES_ERR_OBJ_Q_NOT_PSD (The quadratic coefficient matrix in the objective is not positive semidefinite as expected for a minimization problem.)

It seems that the Q matrix fails to pass the convexity check performed by mosek before executing the optimizer. 

Can you help me in modifying some parameters to control the convexity check, so that the optimization can be performed. 

Thank you. 

 

[Andrea Cassioli]

Hi,

most likely Q has some very small eigenvalue. I will suggest you to:

1- check the eigenvalues (you can even use MOSEK new functions http://docs.mosek.com/7.1/capi/Calling_BLAS_LAPACK_routines_from_MOSEK.html)

2- tweak this option http://docs.mosek.com/7.1/capi/MSK_DPAR_CHECK_CONVEXITY_REL_TOL.html

However, you should also check whether you can rescale/reformulate the problem, and if try to use a conic formulation that is more robust.

[rao.vi...@gmail.com]

Hi Andrea, 

Thank you for the suggestion. I performed eigen decomposition using matlab and found that around 200 eigen values are very small and negative. 

By rounding these values to zero and a re-computing the Q matrix, it still did not pass the convexity check. 

On the other hand, I tried tweaking the MSK_DPAR_CHECK_CONVEXITY_REL_TOL parameter, but still could not pass the convexity check. 

Am I doing this rightly? Below is the how I used to tweak this parameter. 

Code: 

//define prob. 

param=[];

param.MSK_DPAR_CHECK_CONVEXITY_REL_TOL = 100;

[r,res] = mosekopt('minimize' ,prob, param);

//

[Andrea Cassioli]

Hi,

could you double check that the recomputed Q is PSD?

Anyway, your steps to tweak the convexity check tolerance look OK to me. But it may not be easy to tweak it. And anyway you should better work on the problem formulation *sometimes it is a matter of variable scaling) and possibly move to the conic formulation. 

You can find more details here 

http://docs.mosek.com/whitepapers/qmodel.pdf

On Tuesday, March 31, 2015 at 8:47:37 AM UTC+2, rao.vi...@gmail.com wrote:

[rao.vi...@gmail.com]

Hi, 

Yes, the reconstructed Q is also a PSD. The original Q is gram matrix computed as Q = BB' from another matrix. 

Here, by construction Q is PSD. Is it that the convexity checker happens to face the rounding errors while doing 

a cholesky internally?  

As of now, quadprog from MATLAB  gives a reasonable solution for smaller matrices(Q). However, it does not scale 

for large matrices. I also have an additional constraint that x_{i} is integer and it needs a bit of rounding the solution. 

So, I want to check the solution from the  quadratic or conic solver by MOSEK as it is efficient and reliable.

The reformulation to conic problem works, but it reports me a primal infeasible solution even for smaller matrices Q.

Thank for the help.

[Erling D. Andersen]

Unless the smallest eigenvalue is much greater than 0 then rounding can potentially lead to wrong conclusions.

The note Andrea refer to above state that clearly in section 2 which I suggest you read. 

In general I strongly recommend to formulate QP with a diagonal Q and as a conic problem as suggested in the note  

  http://docs.mosek.com/whitepapers/qmodel.pdf

That way all issues with convexity check is removed. So my advice is to read that note and follow the advice given.

Regarding the primal infeasible status. Then I assume MOSEK declares your problem infeasible.

MOSEK will print out a solution summary. If you shows us this solution summary or the complete log output we can easily tell whether your problem is genuine infeasible. Here is info about solution summary if you do not know what I mean

  http://docs.mosek.com/7.1/capi/The_solution_summary.html

[rao.vi...@gmail.com]

I did go through the notes mentioned by Andrea. In section 2, it is mentioned that H is not unique s.t Q = HH'. However, in section 3 an assumption was made that H is a n X p matrix with p < n. 

One issue which needs some clarification here is what happens if  p > n? In my case, Q is obtained from a matrix H where p > n.  When I use this H, PRIMAL_INFEASIBLE status is reported by MOSEK for the conic formulation.

[Erling D. Andersen]

Formulation (6) is valid for any combination of p and n. Where is it required p<n? I do not see it. The only assumption is Q=HH'.

The section just says if p<<n, then the reformulation is particular attractive.

Most likely you make an error when you set the problem up. Try to reduce the problem to the smallest problem possible being infeasible.

Then dump the problem to disk using MOSEK and inspect that file with a text editor. In MATLAB I would do

  mosekopt('write(dump.opf)',prob);

for instance. 

[rao.vi...@gmail.com]

Sorry, I made an error in setting up the problem for conic formulation. Many thanks for pointing it out.

In my case, as p>n around( ~40K ) the program runs out of space now. The dump shows the message "Mosek error: MSK_RES_ERR_SPACE (Out of space.)".

It will take me a while to modify the code keeping track of the memory usage.

Again, thanks for all valuable suggestions, certainly helpful at many points in using the software.

I will get back to you in case of any other major issues.