KKT and duality: different mathematical paths to the same destination

Image by Lance Grandahl from Unsplash

In mathematics and, particularly, in Operations Research, it is often said that all roads lead to Rome. The beauty of mathematical optimization lies in the fact that theoretical frameworks developed from different perspectives converge exactly toward the same fundamental results.

We will explore this convergence by comparing two core pillars of optimization:

1. Duality Theory in linear optimization.
2. Karush-Kuhn-Tucker (KKT) Conditions, fundamental in nonlinear optimization.

KKT in linear optimization

Below, we formally demonstrate how Karush-Kuhn-Tucker analysis applied to a general continuous Linear Optimization problem ($P$) is intrinsically related to its solutions and to those of its dual problem ($D$).

Consider the primal problem $P$ in canonical minimization form:

\[P = \begin{cases} \min & z = \mathbf{c}^\intercal \mathbf{x} \\ \text{s.t.:} & \mathbf{A}\mathbf{x} \geqslant \mathbf{b} \\ & \mathbf{x} \geqslant \mathbf{0} \end{cases}\]

and its corresponding dual problem $D$:

\[D = \begin{cases} \max & w = \mathbf{b}^\intercal \mathbf{u} \\ \text{s.t.:} & \mathbf{A}^\intercal \mathbf{u} \leqslant \mathbf{c} \\ & \mathbf{u} \geqslant \mathbf{0} \end{cases}\]

Given problem $P$ with $n$ variables and $m$ constraints, if it is treated analytically within the general framework of Nonlinear Optimization with inequality constraints of the type $g(\mathbf{x}) \leqslant 0$, we rewrite the constraints as:

• $f(\mathbf{x}) = \mathbf{c}^\intercal \mathbf{x}$
• $g_i(\mathbf{x}) = b_i - \mathbf{a}_i^\intercal \mathbf{x} \leqslant 0 \quad \forall i = 1,\ldots,m$
• $g_{m+j}(\mathbf{x}) = -x_j \leqslant 0 \quad \forall j = 1,\ldots,n$

where $\mathbf{a}_i^\intercal$ denotes the $i$-th row of the coefficient matrix $\mathbf{A}$.

Since there are $m+n$ inequality constraints in total, we assign a Lagrange multiplier to each one. The total vector of multipliers has dimension $m+n$.

The Lagrangian function is constructed as follows:

\[L(\mathbf{x},\mathbf{u}) = \sum_{j=1}^n c_j x_j + \sum_{i=1}^m u_i(b_i - \mathbf{a}_i^\intercal \mathbf{x}) + \sum_{j=1}^n u_{m+j}(-x_j)\]

Determining KKT points requires the simultaneous verification of four fundamental conditions:

1. Stationarity condition (gradient):

   \[\frac{\partial L}{\partial x_j} = 0 \quad \forall j = 1,\ldots,n \iff c_j - \sum_{i=1}^m u_i a_{ij} - u_{m+j} = 0 \quad \forall j = 1,\ldots,n\]

2. Primal feasibility condition:

   \[\mathbf{A}\mathbf{x} \geqslant \mathbf{b}, \qquad \mathbf{x} \geqslant \mathbf{0}\]

3. Complementary slackness condition (orthogonality):

   \[\begin{align*} u_i(b_i - \mathbf{a}_i^\intercal \mathbf{x}) &= 0 \quad \forall i=1,\ldots,m \\ u_{m+j} x_j &= 0 \quad \forall j=1,\ldots,n \end{align*}\]

4. Dual feasibility condition (nonnegativity):

   \[u_k \geqslant 0 \quad \forall k=1,\ldots,m+n\]

Theoretical interpretation

The stationarity and dual feasibility conditions allow us to reinterpret the subvector of the first $m$ multipliers:

\[\mathbf{u}_{dual}^\intercal = (u_1,\ldots,u_m)\]

as a feasible solution of the dual problem $D$. Indeed, rearranging the stationarity equations yields $\sum_{i=1}^m u_i a_{ij} \leqslant c_j$, which is equivalent to the matrix condition $\mathbf{A}^\intercal \mathbf{u}{dual} \leqslant \mathbf{c}$. In this relationship, the additional multipliers $u{m+j}$ ($j=1,\ldots,n$) act precisely as the slack variables of the dual constraints.

Furthermore, the orthogonality condition directly reflects the Complementary Slackness Theorem. Consequently, any optimal KKT point simultaneously specifies the optimal solution for both primal problem $P$ and its dual $D$.

Practical application

To see this equivalence in action with concrete numbers, we will solve a practical problem using both paths.

The primal problem

Consider the following linear optimization problem in its primal form:

\[\begin{align*} \max \quad & z = 3x_1 + 2x_2 \\ \text{s.t.:} \quad & x_1 + 2x_2 \leqslant 6 \\ & 2x_1 + x_2 \leqslant 8 \\ & x_1, x_2 \geqslant 0 \end{align*}\]

Solving geometrically or via the Simplex algorithm, we obtain the optimal primal solution:

\[\mathbf{x}^* = \left(10/3, 4/3\right)^\intercal, \quad z^* = 38/3 \approx 12.67\]

Path 1: duality theory

By the Strong Duality Theorem, we associate a dual variable $u_1$ with the first constraint and $u_2$ with the second to construct the dual minimization problem:

\[\begin{align*} \min \quad & w = 6u_1 + 8u_2 \\ \text{s.t.:} \quad & u_1 + 2u_2 \geqslant 3 \\ & 2u_1 + u_2 \geqslant 2 \\ & u_1, u_2 \geqslant 0 \end{align*}\]

Since the primal variables are strictly positive at the optimum ($x_1^* = 10/3$ and $x_2^* = 4/3$), complementary slackness conditions require both dual constraints to hold as equalities:

1. $u_1 + 2u_2 = 3$
2. $2u_1 + u_2 = 2$

Solving this system of linear equations yields:

\[\mathbf{u}^* = (1/3, 4/3)^\intercal, \quad w^* = 38/3\]

As expected, optimal values are equal: $z^* = w^* = 38/3$.

Path 2: Karush-Kuhn-Tucker (KKT) conditions

To apply KKT, we convert the problem into standard minimization form ($f(\mathbf{x}) = -z$ and $g_i(\mathbf{x}) \leqslant 0$ constraints):

\[\begin{align*} \min \quad & f(x_1, x_2) = -3x_1 - 2x_2 \\ \text{s.t.:} \quad & g_1(x_1, x_2) = x_1 + 2x_2 - 6 \leqslant 0 \\ & g_2(x_1, x_2) = 2x_1 + x_2 - 8 \leqslant 0 \\ & g_3(x_1, x_2) = -x_1 \leqslant 0 \\ & g_4(x_1, x_2) = -x_2 \leqslant 0 \end{align*}\]

We define the Lagrangian function by assigning multipliers $u_1, u_2, u_3, u_4 \geqslant 0$:

\[L(\mathbf{x}, \mathbf{u}) = -3x_1 - 2x_2 + u_1(x_1 + 2x_2 - 6) + u_2(2x_1 + x_2 - 8) - u_3 x_1 - u_4 x_2\]

The KKT conditions are formulated as follows:

1. Stationarity ($\nabla_{\mathbf{x}} L = \mathbf{0}$):

   \[\frac{\partial L}{\partial x_1} = -3 + u_1 + 2u_2 - u_3 = 0 \implies u_1 + 2u_2 - u_3 = 3\] \[\frac{\partial L}{\partial x_2} = -2 + 2u_1 + u_2 - u_4 = 0 \implies 2u_1 + u_2 - u_4 = 2\]

2. Primal feasibility:

   \[x_1 + 2x_2 \leqslant 6, \quad 2x_1 + x_2 \leqslant 8, \quad x_1 \geqslant 0, \quad x_2 \geqslant 0\]

3. Complementary slackness:

   \[\begin{align*} u_1 (x_1 + 2x_2 - 6) &= 0 \\ u_2 (2x_1 + x_2 - 8) &= 0 \\ u_3 x_1 &= 0 \\ u_4 x_2 &= 0 \end{align*}\]

4. Dual feasibility:

   \[u_1 \geqslant 0, \quad u_2 \geqslant 0, \quad u_3 \geqslant 0, \quad u_4 \geqslant 0\]

Evaluating at the known optimal primal point $\mathbf{x}^* = (10/3, 4/3)^\intercal$:

• Since $x_1^* > 0$ and $x_2^* > 0$, complementary slackness equations $u_3 x_1 = 0$ and $u_4 x_2 = 0$ force $u_3^* = 0$ and $u_4^* = 0$.
• Substituting $u_3 = 0$ and $u_4 = 0$ into stationarity conditions yields:
  • $u_1 + 2u_2 = 3$
  • $2u_1 + u_2 = 2$

The system is identical to the one obtained via duality theory, resulting in $u_1^* = 1/3$ and $u_2^* = 4/3$. Both multipliers are non-negative, verifying dual feasibility.

Conclusion

The equivalence between both approaches is complete:

1. KKT stationarity equations are equivalent to requiring dual constraints to hold as equalities when primal variables are strictly positive.
2. Multipliers $u_3$ and $u_4$ in the KKT approach play the exact role of dual slack variables.
3. KKT dual feasibility ($u_i \geqslant 0$) guarantees variable nonnegativity in the dual problem.

Ultimately, duality and KKT conditions demonstrate the unified elegance of Operations Research: regardless of the chosen theoretical framework, the underlying mathematical structure leads with absolute precision to the same optimal truth.

---

Want to keep exploring the world of Operations Research? Discover more posts on the topic here.