kkt

Tags:

Updated:


kkt creates a model of the KKT conditions of a parameterized LP or QP.

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, 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 manually 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 size of the bound.

value(details.duals)
ans =

    0.1250
    0.1250
    0.2500
         0
         0
         0

Leave a Comment