KKT conditions: summary

KKT conditions: summary#

Standard form formulation#

Consider the following general inequality and equality constrained optimisation problem written in a standard form:

(5)#

\begin{aligned} min. & f (x) \\ s.t. & h_{i} (x) = 0 (λ_{i}) \forall i \in {1, 2, . . ., m} \\ g_{j} (x) \leq 0 (μ_{j}) \forall j \in {1, 2, . . ., n} \end{aligned}

There are $m$ equality constraints associated with Lagrange multipliers $λ_{i}$ and $n$ inequality constraints associated with Lagrange multipliers $μ_{j}$ .

Lagrangian#

(6)#

L = f (x) + \sum_{i = 1}^{m} λ_{i} \cdot h_{i} (x) + \sum_{j = 1}^{n} μ_{j} \cdot g_{j} (x)

The Lagrangian has three components: the original objective function, the equality constraints multiplied by their Lagrange multipliers, and the inequality constraints multiplied by their Lagrange multipliers.

KKT Conditions#

(7)#

\begin{aligned} \frac{\partial L}{\partial x} = 0 & (Optimality conditions) \\ \frac{\partial L}{\partial λ_{i}} = h_{i} (x) = 0 \forall i \in {1, 2, . . ., m} & (Primal feasibility) \\ g_{j} (x) \leq 0 \forall j \in {1, 2, . . ., n} & (Primal feasibility) \\ μ_{j} \cdot g_{j} (x) = 0 \forall j \in {1, 2, . . ., n} & (Complementary slackness conditions) \\ μ_{j} \geq 0 \forall j \in {1, 2, . . ., n} & (Dual feasibility) \end{aligned}

Let’s look at each of these equations in a little more detail. We have:

Derivative of Lagrangian w.r.t. decision variables $x$ equal to zero $\to$ optimality conditions
Derivative of Lagrangian w.r.t. Lagrange multipliers $λ_{i}$ (equality constraints) $\to$ primal feasibility (solution is feasible with respect to the primal constraints)
Derivative of Lagrangian w.r.t. Lagrange multipliers $μ_{j}$ (inequality constraints) $\to$ primal feasibility
The multiplication of a Lagrange multiplier with its associated inequality constraint is zero $\to$ complementary slackness conditions (indicates that in some cases the inequality constraints might not be binding)
Lagrange multipliers $μ_{j}$ need to be positive or zero $\to$ dual feasibility

Interpretation of the complementary slackness conditions

If a constraint is binding, we can replace the inequality sign with an equality sign, so we have $g_{j} (x) = 0$ . Then, the Lagrange multiplier $μ_{j}$ may take on any non-zero value ( $μ_{j} \geq 0$ ), and the constraint $μ_{j} \cdot g_{j} (x) = 0$ will be satisfied. If the constraint is non-binding ( $g_{j} (x) < 0$ ), the Lagrange multiplier will equal zero ( $μ_{j} = 0$ ). Otherwise the constraint $μ_{j} \cdot g_{j} (x) = 0$ would be violated. Note that these constraints are non-linear.

The KKT conditions are a large set of equations. For simple cases addressed in this course, we can solve the problem by using trial-and-error. We try different combinations of constraints, come up with candidate solutions, then assess whether they are optimal or not. Depending on the problem, we reason which inequality constraints are likely to be binding. Then, we make them equality constraints, and their corresponding $μ_{j} \neq 0$ . For the non-binding inequality constraints, their corresponding $μ_{j} = 0$ . This can greatly simplify the KKT conditions. We will be left with as many equations as there are unknowns, so we can solve for $x$ , $λ_{i}$ , and $μ_{j}$ to obtain the optimal solution to the problem. We can also check if there is alternative combination of binding/non-binding constraints that would yield a better solution.

KKT conditions: summary

Contents

KKT conditions: summary#

Standard form formulation#

Lagrangian#

KKT Conditions#