kkt

kkt creates a model of the KKT conditions of a (possibly nonlinearly parameterized) LPs or QPs.

Syntax

[KKTsystem, details] = kkt(Constraint,Objective,z)

Comments

The command derives the KKT system for a linear or quadratic program parametrized in the variable z. The second output contains information about the analyzed problem, primal and dual variables, and possibly derived bounds on primal and dual variables.

The KKT system will contain a complementarity constraint which can be addressed by YALMIP using either integer programming or global nonlinear programming. Both methods require bounds on the dual variables. YALMIP tries to derive these bounds by default and add them to the KKT system. If this is unsuccessful (see details.dualbounds) you must manually add reasonable bounds on the variable details.duals)

Example

The following example derives the KKT conditions of a linear program in the decision variable x, with a cost depending on a parameter z. In this case, kkt successfully derives upper bounds the dual variables.

% min c(z)'*x s.t Ax<=b
A = randn(6,2);
b = rand(6,1);
c = rand(2,1);

x = sdpvar(2,1);
z = sdpvar(1);
c = c + randn(2,1)*z;

[Constraints,details] = kkt([A*x <= b, -1 <= z <= 1],c'*x,z);

KKT conditions can be used to solve indefinite quadratic programs using mixed-integer programming (see related nonconvex QP example). Consider the following nonconvex QP which by default will be solved using a local solver such as QUADPROG or FMINCON

Q = magic(5);
x = sdpvar(5,1);
optimize([-1 <= x <= 1],x'*Q*x)

Derive the KKT conditions, and express the objective in terms of a linear function of the primals and duals. The resulting problem is a mixed-integer linear program due to the complementarity constraints in K. Note that the dual bounds details.dualbounds are all finite. Hence, they will be added to the constraints in K, leading to a numerically well-defined problem when the complementarity constraint is converted to integer constraints using a big-M approach.

[K,details] = kkt([-1 <= x <= 1],x'*Q*x);
LinearObjective = (details.c'*details.primal-details.b'*details.dual)/2;
optimize(K,LinearObjective)

The next example solves a bilevel quadratic program by deriving the KKT conditions for the inner problem. Here, kkt fails to derive bounds on the duals, hence they have to be added manually. Primal bounds are derived based on the inner problem in the kkt operator, but does not constrain all variables. Hence, we conveniently extract and add these using the boundingbox operator.

sdpvar x1 x2 y1 y2 y3

OO = -8*x1-4*x2+4*y1-40*y2-4*y3;
OO = OO+OO^2;
CO = [x1>=0, x2>=0];

OI = (x1+2*x2+y1+y2+2*y3)^2;
CI = [[y1 y2 y3] >= 0,
       -y1+y2+y3 <= 10,
      2*x1-y1+2*y2-0.5*y3 <= 10,
      2*x2+2*y1-y2-0.5*y3 <= 9.7];

[K,details] = kkt(CI,OI,[x1 x2])
optimize([K,CO,boundingbox([CI,CO]),details.dual<=100],OO)

Since we added an artificial bound on the duals, we check the solution to make sure it is inactive. If it would be active, we would need to increase the magnitude of the bound.

value(details.duals)
ans =

    0.1250
    0.1250
    0.2500
         0
         0
         0

Nonlinearly parameterized problem

The problem we apply kkt to must be an LP or QP in the decision variables. However, it can be more complex w.r.t the parameters. The following examples illustrates this by solving a nonlinear bilevel program, by deriving the nonlinearly parameterized KKT conditions of the inner program. The resulting problem will inherit the nonconvex quadratic structure from the initial models, and have additional nonconvex complementarity constraints arising from the KKT conditions, but is readily solved using a global quadratic solver such as BMIBNB

sdpvar x1 x2 y1 y2
ObjectiveInner = 2*x1^2+y1^2-5*y2;
ConstraintsInner = [-x1^2+2*x1-x2^2+2*y1-y2-3<=0;-x2-3*y1+4*y2+4<=0;-y1<=0;-y2<=0];
K = kkt(g,f,[x1 x2]);

ObjectiveOuter = -x1^2-3*x2-4*y1+y2^2;
ConstraintsOuter = [x1^2+2*x2-4<=0;-x1<=0;-x2<=0];

optimize([ConstraintsOuter, K, ConstraintsInner],F,sdpsettings('bmibnb'))