Cerfify whether a solution is a KKT point via Yalmip

[Aras]

Hi!

My parameters are

Q = [-1 0; 0 -1];

D = [1 0; 0 1; -1 0; 0 -1];

d = [5;3;-2;-1];

x = sdpvar(2,1);

for solving

optimize([D*x <= d],x.'*Q*x);

And I am interested in whether a given point, let's say xstar = [4; 2] , is a KKT point or not. 

Is this possible with Yalmip? I could not make any use of this link: https://yalmip.github.io/command/kkt/

[Aras]

Maybe I can create a model with the constraints being KKTsystem as described in the link. Then, I can force a solution and check the feasibility? But I am not sure on how to implement this.

[Johan Löfberg]

% Should be feasible if xstar satisfies KKT condition

% Fails

K = kkt([D*x <= d],x.'*Q*x)

K = replace(K,x, [4; 2])

optimize(K)

% Works (this is the globally optimal point)

K = kkt([D*x <= d],x.'*Q*x)

K = replace(K,x, [5; 3])

optimize(K)

[Aras]

This is great! So, even though [4,2] is a feasible point, now with the KKT infeasibility we can see that it is not a KKT point? Also in a non-convex case? That's a big thing ...

[Johan Löfberg]

It is feasible and there are duals such that stationarity and primal feasibility is satisfied

>> K

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

|   ID|                    Constraint|   Coefficient range|                                             Tag|

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

|   #1|    Complementarity constraint|                    |   Compl. slackness and primal-dual inequalities|

|   #2|   Element-wise inequality 4x1|             1 to 10|                            Upper bound on duals|

|   #3|       Equality constraint 2x1|              1 to 8|                                    Stationarity|

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

optimize([D*x <= d, K(2:3)])

But including also complementarity (which will be a simple linear constraint once x is fixed) will lead to infeasibility, i.e., there is no dual such that kkt conditions are satisfied

[Aras]

but, this one gives error:

d = [28;5];

D = [4 7; 1 -5];

Q = [1 0; 0 1];

% Should be feasible if xstar satisfies KKT condition

% Fails

x = sdpvar(2,1);

K = kkt([D*x <= d, x>=0],-(x.'*Q*x));

K = replace(K,x, [6.4815; 0.2963]);

A = optimize(K);

Note, when I give [0;0] I don't have this error. The error message is:

>> check_kkt

Starting derivation of dual bounds (can be turned off using option kkt.dualbounds)

*Computing 2 primal bounds (required for dual bounds)

*Computing 4 dual bounds

*Success: All dual upper bounds are finite

Error using lmi/horzcat (line 21)

One of the constraints evaluates to a FALSE LOGICAL variable

Error in compileinterfacedata (line 309)

            Ftemp = [Ftemp, Cx>=0, Cy >=0];

Error in solvesdp (line 231)

[interfacedata,recoverdata,solver,diagnostic,F,Fremoved,ForiginalQuadratics] =

compileinterfacedata(F,[],logdetStruct,h,options,0,solving_parametric);

Error in optimize (line 31)

[varargout{1:nargout}] = solvesdp(varargin{:});

Error in check_kkt (line 9)

A = optimize(K);

[Aras]

Is it when we ruin the main constraint, but not the KKT ones? Thank you very much for your time.

[Johan Löfberg]

It's not feasible

>> D*[6.4815; 0.2963]-d

ans =

   1.0e-04 *

    1.0000

         0

[Johan Löfberg]

and I don't get any error message when replacing with 0

optimize(replace(K,x,0))

  struct with fields:

    yalmipversion: '20181012'

       yalmiptime: 0.4386

       solvertime: 0.1054

             info: 'Successfully solved (GUROBI-GUROBI)'

          problem: 0