Constrained Non-Linear Optimization, the conditions hiding the optimum

Image by Mariola Grobelska retrieved from Unsplash

When venturing into the world of non-linear mathematical optimization, our first instinct is often to rely on the tools learned in basic calculus. To find the minimum or maximum of a function, we take derivatives and set them to zero. However, in the real world, optimization almost always comes with constraints.

Why basic methods are not enough

In an unconstrained optimization problem, Fermat’s theorem tells us that it suffices to search for points where the gradient of the objective function vanishes ($\nabla f(x) = \mathbf{0}$).

If we add equality constraints (for example, $h(x) = 0$), the method of Lagrange Multipliers comes to the rescue. This method allows us to build an auxiliary function (the Lagrangian) and solve the system assuming that the gradient of the objective function must be parallel to that of the constraints.

But what happens when we face inequality constraints ($g(x) \leqslant 0$)?

This is where basic methods collapse. An inequality constraint introduces a major complication: the optimal solution could lie in the interior of the feasible region (making the constraint irrelevant or inactive) or right on its boundary (making the constraint active). Pure Lagrange multipliers cannot handle this conditional duality, nor can they guarantee the correct gradient direction at boundaries. For all these reasons, we need a more robust framework.

The discovery (and rediscovery) of KKT

The theoretical framework that solved this problem is known today as the Karush-Kuhn-Tucker (KKT) Conditions, but the name hides a story of mathematical justice worth telling.

As Richard W. Cottle recounts in his essay “William Karush and the KKT theorem” (included in the wonderful outreach book Optimization Stories (Grötschel, 2012)), the mathematical community recognized this breakthrough for decades under the name Kuhn-Tucker Conditions. Harold W. Kuhn and Albert W. Tucker presented these results in 1950 during the Second Berkeley Symposium on Mathematical Statistics and Probability, publishing them to great acclaim in 1951 (Kuhn & Tucker, 1951).

However, William Karush had preceded them by 11 years. In 1939 (Karush, 1939), Karush developed the exact same conditions as part of his master’s thesis at the University of Chicago. Unfortunately, as an unpublished document and with the outbreak of World War II, his work remained buried in the archives and passed unnoticed by academia. It was not until several decades later that his original contribution was discovered, amending the official name of the theorem to KKT to give him the credit he rightfully deserved.

The intermediate step: Fritz John conditions

Before arriving at the KKT conditions, in 1948 (John, 1948), mathematician Fritz John formulated a general result based on this geometry. Suppose we want to minimize $f(\mathbf{x})$ subject to inequality constraints $g_i(\mathbf{x}) \leqslant 0$.

John proved that if $x^*$ is a local optimum, then there exist multipliers $u_0, u_1, \ldots, u_m \geqslant 0$, not all zero, such that:

\[u_0 \nabla f(\mathbf{x}^*) + \sum_{i=1}^m u_i \nabla g_i(\mathbf{x}^*) = \mathbf{0}\]

in addition to the complementary slackness conditions ($u_i g_i(\mathbf{x}^*) = 0, \; \forall i \in {1,\ldots,m}$).

What is the drawback of the Fritz John conditions?

If we look at multiplier $u_0$ accompanying the gradient of the objective function, it can be $u_0 = 0$, in which case the objective function term vanishes completely. In this scenario (known as a degenerate case), the optimization conditions depend solely on the geometry of the constraints, ignoring what we are actually trying to optimize. This occurs when the feasible region contains kinks or strange singularities.

On the path to the optimum, constraint geometry matters

To understand how we find the optimal point in a constrained problem, imagine walking across a mountainous landscape trying to reach the lowest possible point (minimizing an objective function $f(\mathbf{x})$). If there were no obstacles, you would simply walk downhill along the slope until reaching the bottom of the valley, where the incline is zero ($\nabla f(\mathbf{x}) = \mathbf{0}$).

However, in our problem, there are “fences” or barriers restricting where you can walk (inequality constraints $g_i(\mathbf{x}) \leqslant 0, \; i \in \{1,\ldots,m\}$).

What happens when you reach the lowest allowed point but hit a fence? At that optimal point, your desire to keep descending (the gradient of your objective function) collides head-on with the fence (the gradient of the constraint). If you could move without crossing the barrier, you would do so to keep descending. However, since you cannot, it means that the forces are in equilibrium. Mathematically, the direction of steepest descent of your objective function is perfectly aligned (but pointing in the opposite direction) with the direction in which the fence pushes you inward.

For the boundary of the feasible region to behave properly without creating singularities, the constraints must be differentiable and satisfy properties of convexity or quasiconvexity.

The Karush-Kuhn-Tucker (KKT) conditions

Translating this geometric intuition of equilibrium into rigorous mathematical language yields the KKT Conditions for inequality problems.

For a point $\mathbf{x}^*$ to be a local optimal solution, the existence of multipliers $\mathbf{u}$ (our reaction forces from the fences) must be guaranteed, satisfying the following fundamental conditions:

Stationarity (Force equilibrium): The gradient of the objective function plus the gradients of the constraints (multiplied by their respective force $u_i$) cancel each other out. No allowed direction improves the result.
\[\nabla f(\mathbf{x}^*) + \sum_{i=1}^m u_i \nabla g_i(\mathbf{x}^*) = \mathbf{0}\]
Primal Feasibility (Respecting the rules): The point must lie within the feasible region. We cannot cross the fences.
\[g_i(\mathbf{x}^*) \leqslant 0, \quad \forall i \in \{1,\ldots,m\}\]
Dual Feasibility (Forces only push, they don’t pull): The multipliers (the fences you cannot cross) must be positive or zero. The fence pushes you inward to keep you in the allowed zone, but it never pulls you outward.
\[u_i \geqslant 0, \quad \forall i \in \{1,\ldots,m\}\]
Complementary Slackness (Only touched fences matter): If at your optimal point you are not touching a specific constraint (that is, $g_i(\mathbf{x}^*) < 0$), that fence exerts no force on you, so its multiplier must be zero ($u_i = 0$). Only “active” constraints participate in the equilibrium.
\[u_i g_i(\mathbf{x}^*) = 0, \quad \forall i \in \{1,\ldots,m\}\]
Linear Independence of Active Constraints (Regularity): The gradients of constraints satisfied with equality at the optimal point (active constraints, $g_i(\mathbf{x}^*) = 0$) must be linearly independent:
\[\{\nabla g_i(\mathbf{x}^*)\}_{i \in \mathcal{I}}\]
is linearly independent, where $\mathcal{I}(\mathbf{x}^*) = \{i \in \{1,\ldots,m\} : g_i(\mathbf{x}^*) = 0\}$.

Note for maximization problems:

If the problem is a maximization of $f(\mathbf{x})$ while keeping the stationarity equation with a positive sign ($+\sum u_i \nabla g_i$), the dual feasibility condition changes to $u_i \leqslant 0$. This is because the gradient of the objective function ($\nabla f$) points in the same direction as that of the constraint ($\nabla g_i$).

Why do these conditions work? The role of Farkas and Gordan

The validity of the KKT conditions rests upon theorems of the alternative in convex geometry, mainly Gordan’s Lemma (1873) (Gordan, 1873) and Farkas’ Lemma (1902) (Farkas, 1902).

In essence, Farkas’ Lemma establishes a geometric disjunction at $\mathbf{x}^*$:

Either there exists a direction $d$ such that we can reduce the objective function value, $\nabla f(\mathbf{x}^*)^\intercal d < 0$, while maintaining feasibility $\nabla g_i(\mathbf{x}^*)^\intercal d \leqslant 0$,
Or the vector $-\nabla f(\mathbf{x}^*)$ belongs to the convex cone generated by the gradients of active constraints $\{\nabla g_i(\mathbf{x}^*)\}_{i \in \mathcal{I}}$.

Since $\mathbf{x}^*$ is a local minimum, no feasible descent direction can exist. Therefore, Farkas’ Lemma mathematically guarantees that $-\nabla f(\mathbf{x}^*)$ must be expressed as a linear combination with non-negative coefficients ($u_i \geqslant 0$) of the gradients $\nabla g_i(\mathbf{x}^*)$. Rearranging terms yields the KKT stationarity condition directly.

KKT sufficient conditions: from local to global optimum

The necessary KKT conditions identify candidates for local optima. However, when the problem exhibits certain convexity properties, a KKT point with $u_i \geqslant 0$ is guaranteed to be the global minimum.

For these necessary conditions to become sufficient, the following is required at the feasible point $\mathbf{x}^*$:

The objective function $f(\mathbf{x})$ is pseudoconvex: This ensures there are no false local minima. Any convex, differentiable function satisfies this property.
The active constraints ($g_i(\mathbf{x}^*) = 0$) are quasiconvex: This guarantees that the feasible region does not contain cavities or irregular shapes. Any linear or convex constraint satisfies this.

When these two geometric properties are verified, there is no need to compare the candidate with any other point: every point satisfying the KKT conditions with $u_i \geqslant 0$ is an absolute global minimum.

Illustrative example

Consider the following optimization problem:

\[\begin{aligned} \text{Opt.} \quad & f(x_1, x_2) = x_1^2 + x_2^2 \\ \text{s.t.:} \quad & x_1 + x_2 \geqslant 1 \\ & x_1 + x_2^2 \leqslant 1 \end{aligned}\]

The graphical representation of this problem is given by:

To apply the KKT conditions, we express all constraints in the form $g_i(x_1, x_2) \leqslant 0$:

$g_1(x_1, x_2) = 1 - x_1 - x_2 \leqslant 0$
$g_2(x_1, x_2) = x_1 + x_2^2 - 1 \leqslant 0$

We compute the gradients of the objective function and constraints:

\[\nabla f(x_1, x_2) = \begin{pmatrix} 2x_1 \\ 2x_2 \end{pmatrix}, \quad \nabla g_1(x_1, x_2) = \begin{pmatrix} -1 \\ -1 \end{pmatrix}, \quad \nabla g_2(x_1, x_2) = \begin{pmatrix} 1 \\ 2x_2 \end{pmatrix}\]

We construct the Lagrangian function $L(\mathbf{x}, \mathbf{u})$:

\[L(\mathbf{x}, \mathbf{u}) = x_1^2 + x_2^2 + u_1(1 - x_1 - x_2) + u_2(x_1 + x_2^2 - 1)\]

We formulate the system of KKT equations and inequalities:

Stationarity ($\nabla_{\mathbf{x}} L = \mathbf{0}$):
- (G1) $2x_1 - u_1 + u_2 = 0$
- (G2) $2x_2 - u_1 + 2 u_2 x_2 = 0$
Primal Feasibility:
- (F1) $1 - x_1 - x_2 \leqslant 0$
- (F2) $x_1 + x_2^2 - 1 \leqslant 0$
Complementary Slackness:
- (O1) $u_1 (1 - x_1 - x_2) = 0$
- (O2) $u_2 (x_1 + x_2^2 - 1) = 0$
Dual Feasibility (depending on optimization type):
- For Minimization: $u_1 \geqslant 0, \; u_2 \geqslant 0$
- For Maximization: $u_1 \leqslant 0, \; u_2 \leqslant 0$
Linear Independence: Gradients of active constraints $\{\nabla g_i(\mathbf{x}^*)\}_{i \in \mathcal{I}}$ must be linearly independent.

This system of equations can be solved using a binary tree where each multiplier is assumed to be equal to or different from $0$ ($u_i = 0$ or $u_i \neq 0$), yielding the following candidate points:

Point	Tree Branch	Coordinates $(x_1, x_2)$	Multipliers $(u_1, u_2)$
$A$	$u_1 \neq 0, u_2 \neq 0$	$(0, 1)$	$(-2, -2)$
$B$	$u_1 \neq 0, u_2 = 0$	$\left(\frac{1}{2}, \frac{1}{2}\right)$	$(1, 0)$
$C$	$u_1 = 0, u_2 \neq 0$	$(1, 0)$	$(0, -2)$
$D$	$u_1 = 0, u_2 \neq 0$	$\left(\frac{1}{2}, \frac{1}{\sqrt{2}}\right)$	$(0, -1)$

Note: The branch $u_1 = 0, u_2 = 0$ leads to point $(0,0)$, which is discarded as infeasible since it violates the first constraint ($1 - 0 - 0 = 1 \nleqslant 0$).

Instead of evaluating the objective function at all candidates, we apply the KKT Sufficient Conditions Theorem by analyzing the nature of the functions and the resulting multipliers:

For the candidate minimum $B = \left(\frac{1}{2}, \frac{1}{2}\right)$:

Multipliers: $u_1 = 1 \geqslant 0$ and $u_2 = 0$. The only active constraint is $g_1(x_1, x_2) = 1 - x_1 - x_2 = 0$.
Convexity of objective function: $f(x_1, x_2) = x_1^2 + x_2^2$ is strictly convex (its Hessian matrix is positive definite), so it is pseudoconvex.
Convexity of active constraint: $g_1(x_1, x_2) = 1 - x_1 - x_2$ is linear (convex), so it is quasiconvex.

Since dual feasibility ($u_1 \geqslant 0$), pseudoconvexity of $f$, and quasiconvexity of $g_1$ are satisfied, the Sufficient Conditions Theorem rigorously guarantees that $B = \left(\frac{1}{2}, \frac{1}{2}\right)$ is a global minimum with value $z^* = f(B) = 0.5$, without needing comparison to any other point.

For points $A = (0, 1)$, $C = (1, 0)$, and $D = \left(\frac{1}{2}, \frac{1}{\sqrt{2}}\right)$, the multipliers are non-positive ($u_i \leqslant 0$), identifying them as candidates for maxima.

To apply sufficient conditions for a global maximum, we would require $-f(\mathbf{x})$ to be pseudoconvex. However, since $f$ is strictly convex, $-f$ is strictly concave (not pseudoconvex). Therefore, KKT sufficient conditions cannot be applied to guarantee global maxima in this problem. In such scenarios, the classification of maxima is determined via graphical analysis or inspection of the boundary of the feasible region.

To rigorously confirm the existence and location of global maxima, we turn to Weierstrass’s Extreme Value Theorem. Since objective function $f(x_1, x_2) = x_1^2 + x_2^2$ is continuous and the feasible region is compact (closed and bounded within $[0, 1] \times [0, 1]$), Weierstrass guarantees the existence of at least one absolute maximum and minimum within that region.

Since candidates for extrema must satisfy necessary KKT conditions, it suffices to evaluate the function at the candidate maximum points ($A$, $C$, and $D$):

$f(D) = f\left(\frac{1}{2}, \frac{1}{\sqrt{2}}\right) = \left(\frac{1}{2}\right)^2 + \left(\frac{1}{\sqrt{2}}\right)^2 = \frac{1}{4} + \frac{1}{2} = 0.75$
$f(A) = f(0, 1) = 0^2 + 1^2 = 1$
$f(C) = f(1, 0) = 1^2 + 0^2 = 1$

Therefore, by Weierstrass’s Theorem, $A = (0, 1)$ and $C = (1, 0)$ are the two global maxima of the problem with optimal value $z^* = 1$.

Conclusions:

Global Minimum: Point $B = \left(\frac{1}{2}, \frac{1}{2}\right)$ is the global minimum with optimal value $z^* = 0.5$.
Global Maxima: Points $A = (0, 1)$ and $C = (1, 0)$ are the two global maxima with optimal value $z^* = 1$.

The journey from the lemmas of Farkas and Gordan, through the structural rigor of Fritz John, to the elegance of the KKT conditions, is one of the most beautiful developments in 20th-century applied mathematics. Thanks to this path, today we can solve everything from mechanical system control with physical limits to portfolio optimization and Support Vector Machines (SVMs).

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