allownonconvex constraint violation

[Ahmed Hraoui]

Hi,

I have the following problem: When I run the following minimal working example:

clear all;
yalmip('clear');
options = sdpsettings('allownonconvex',0);

M1 = sdpvar(2);
solution = optimize(norm(M1^2, Inf) <= 1, [], options)

M2 = sdpvar(2);
solution = optimize(norm(M2^2, Inf) <= 1, [], options)

I obtain:

... some MOSEK output ...

solution =

  struct with fields:

    yalmipversion: '20200116'
       yalmiptime: 0.7742
       solvertime: 2.5738
             info: 'Successfully solved (MOSEK)'
          problem: 0


solution =

  struct with fields:

    solvertime: 0
       problem: 14
          info: 'Model creation failed (Convex quadratic encountered in constraint #1 at level 1)'
    yalmiptime: 0.1440

Why does this happen? So why doesn't the model creation also fail for the first run? This is very annoying, cause I don't want to run my actual optimization problem multiple times to verify convexity.

Thanks a lot in advance.

Ahmed

[Johan Löfberg]

First, this is a bug which somehow allows the model to sneak through, it should not be possible for YALMIP to setup a model for any case. norm is a convexity aware operator, and as it is now norm(squared) should not be possible to propagate as it doesn't satisfy the convexity propagation rules used. I think YALMIP fails sometimes whn ther eare polynomial stuff inside LP/SOCP/SDP-representable operators

I'm a bit concerned that you don't understand the complexity of the model though, or what you are modelling really.

The constraint effectively involves the expression max(sum(abs(M1^2),1)), hence your constraint is sum(abs(M1^2),1) <= 1, which once again won't work as you have the convex abs operator on the non-monotonic quadratic terms. Hence, the manual model is

s = sdpvar(2,2)

e = M1^2;

[-s(:) <= e(:) <= s(:), sum(s) <= 1]

this is a nonconvex set of quadratic inequalities, for which you will have to use a global nonlinear solver if you want to solve it to optimality.

Of course, it could be that norm(M1^2, Inf)  is a convex expression which is SOCP/SDP representable, but then you have to derive that model 

[Ahmed Hraoui]

Thanks a lot for your quick response.

I am actually aware that this is a nonconvex OP. However, I copied and pasted some code from another convex example, at least I think so, and forgot about this 'allownonconvex' option. As a result, I was very confused that MOSEK was called and was afraid that my previous example might also not be convex. Thus, I wanted to ask for what kinda problems I can rely on Yalmip to appropriately model a convex OP.

[Johan Löfberg]

The case where YALMIP gets overly optimistic and thinks it has derived a representation is combination of polynomial terms inside a convexity aware operator (min/max/norm etc). I.e., never do that without knowing perfectly well (by proof) that it is LP/SOCP representable.

It is a known bug, but fixing it would cause some other stuff to be extremely complicated