Solver not applicable (mosek does not support semidefinite constraints)

[TobiFx17]

Dear Johan Löfberg, 

I encountert a weird problem when running my code. Im trying to solve a problem with complementary constraints by penalizing the complementary constraints in the objective function. So im solving a for loop where only the objective function is dependant on the result of the last iteration. When doing so I noticed my Problems always stopped at the 41th iteration and I the info in the result struc is "Solver not applicable (mosek does not support semidefinite constraints)". As im not changing the constraints i don't know why i get this problem every time. I attached the examples, where every instance stated fails within the 41th iteration. 

Im using MOSEK Version 11.0.22 and Yalmip Version 20230622.

If you need more Information please let me know.

[Johan Löfberg]

The problem is that your objective becomes numerically nonconvex

A model sum(x)^2 is dangerous as Q in x'*Q*x is rank-one, and with some unfortunate numerical scaling and tolerances it can become indefinite enough to fail tolerances (easily seen with example min(eig(ones(10,1)*ones(1,10)))

Recommended way is to introduce a new variable z, with constraint z == sum(x), and then use z^2 instead, which will be easier to detect convexity on as [z;x]*Q*[z;x] is block-positive-definite

(the weird error comes from YALMIP temporarily think it can adress the nonconvex QP via geometric programming in mosek, but then once down that incorrect route it realizes there are semidefinite constraints, which it doesn't want to mix with GP)

[Johan Löfberg]

On closer inspection, it is not exactly that. For some reason, the sparse low-rank analysis of the quadratic fails. Investigating this

[Johan Löfberg]

Turns out to be an edge-case where eig(Q) yields 0 but eig(full(Q)) yields significantly negative due to numerical cancellations. For now, you can remove 'full' on line 459 in lmi/categorizeproblem, and I will work on a general fix

[Johan Löfberg]

and on even closer inspection, that did not work either, all variants to test definiteness fail in a later iteration.

I guess you will have to introduce new variables to replace your x+z and/or s+v and/or 1-s+r becomes these (or some one of them) leads to a low-rank structure which fools the psd-tests

[TobiFx17]

As the quadratic function in the objective are convex and just the linear terms change with each iteration could just adding 3 constraints (for each x+z , ... respectively)  [t1, (x+y)^T; (x+y), Identity] >= 0 and making the objective t1+t2+t3 resolve the problem. Because from my understanding the problem seams to be the cause of checking the objective for convexity ? And this way yalmip ( or mosek) doesnt need to check as the objective is linear.

[Johan Löfberg]

Since rho changes, the convex quadratic low-rank term phi_plus_terms will have varying numerical properties, and eventually become numerically indefinite enough for YALMIP to classify it as indefinite thus ruling out mosek 

YALMIP has to check for convexity, it doesn't/cannot know that the problem is convex a-priori.

If you want to avoid numerical issues regarding these low-rank structures on ill-conditioned as yours , you either manually factorize as described, or you model the quadratic term manually using an socp cone

[TobiFx17]

you are right I forgot about the scalar rho and i understand that yalmip has to check each time . but i don't seem to understand why using semidefinite constraints won't suffice to resolving the problem. because then the objective would be linear terms * rho which shouldnt resolve in being identified as non convex even if rho increases.

[Johan Löfberg]

I don't understand what semidefinite constraints you are talking about. 

the problem has nothing to do with constraints, but the numerical indefiniteness of the quadratic objective. you can see this by adding min(eig(quaddecomp(phi_plus_terms)) in your loop to see the numerical failure. At some point the value will be lower than the accepted tolerance inside the compilation code (it is not working with exactly this term, I think some scaling and permutation might occur when compiling the quadratic internally, but it is a good proxy for the data that YALMIP uses)

[TobiFx17]

I mean getting rid of the quadratic terms in the objective by reformulating the quadratic terms with semidefinite Constraints (for example  [t1, (x+y)^T; (x+y), Identity] >= 0 and same for the other 2 quadratic terms ) so we minimize ti in the objective  and therefor adding 3 semidefinite Constraints and making the objective linear : rho * (t1 + t2+ t3). 

[Johan Löfberg]

Rewriting the quadratic model using semidefinite constraints would work, but it would be a very inefficient way to do it. What I am telling you is that you should rewrite them using second-order cone constraints, either using cone operator or by using the norm operator (or introduce intermediate variables to get rid of them sums you are squaring which is the culprit for the low-ranks)

[TobiFx17]

okay thank you very much for your help