KKT Conditions for Inequality Constrained Optimization

Hello! Welcome to our next lesson.

In our last session, we formulated optimization problems with inequality constraints and introduced the critical concepts of active/inactive constraints and complementary slackness. We concluded by transforming the constrained problem into an equivalent unconstrained min-max problem using the Lagrangian:
${\min }_{\mathbf{x}}\left({\max }_{\mathbf{\mu }\ge 0}L(\mathbf{x},\mathbf{\mu })\right)\text{where}L(\mathbf{x},\mathbf{\mu })=f(\mathbf{x})+{\sum }_j{\mu }_j{g}_j(\mathbf{x})$
This formulation was a crucial theoretical step, creating a unified structure that doesn't depend on knowing which constraints are active beforehand.

Today, we will build directly on that foundation. Our goal is to derive the Karush-Kuhn-Tucker (KKT) conditions as necessary conditions for optimality. These conditions are the cornerstone of nonlinear optimization and are used extensively in machine learning to characterize the solutions to problems ranging from Support Vector Machines to regularized regression. By the end of this lesson, you will understand the complete set of conditions that a potential optimal solution must satisfy.

1. The Primal and Dual Problems

The min-max formulation we ended with is known as the primal problem. Let's denote its optimal value as $p^{\ast }$:
$p^{\ast }={\min }_{\mathbf{x}}\left({\max }_{\mathbf{\mu }\ge 0}L(\mathbf{x},\mathbf{\mu })\right)$

Now, consider what happens if we swap the order of minimization and maximization. This gives us the dual problem, with an optimal value we'll call $q^{\ast }$:
$q^{\ast }={\max }_{\mathbf{\mu }\ge 0}\left({\min }_{\mathbf{x}}L(\mathbf{x},\mathbf{\mu })\right)$

A fundamental result in optimization is the max-min inequality, which states that for any function of two variables, the "max-min" is always less than or equal to the "min-max." Therefore, we have:
$q^{\ast }\le p^{\ast }$
This relationship is known as weak duality. The difference, $p^{\ast }-q^{\ast }$, is called the duality gap.

2. Strong Duality: The Key to the Derivation

For many optimization problems of interest—specifically, for convex problems that satisfy certain regularity conditions (which we'll touch on later)—the duality gap is zero. This remarkable property is called strong duality:
$q^{\ast }=p^{\ast }$
Assuming strong duality holds for our problem, we can equate the optimal values of the primal and dual problems. This equality is the key that unlocks the KKT conditions.

The following video continues the derivation we started in the last lesson. It formally introduces the primal and dual problems, the duality gap, and the assumption of strong duality, which sets the stage for the final derivation.

3. Deriving the KKT Conditions

Let's assume strong duality holds and that ${\mathbf{x}}^{\ast }$ is a primal optimal solution (our solution to the original problem) and ${\mathbf{\mu }}^{\ast }$ is a dual optimal solution.

From the video and our setup, we can establish a chain of relationships:

1. $f({\mathbf{x}}^{\ast })$ is the optimal value of our original problem, which under strong duality is equal to $p^{\ast }$ and $q^{\ast }$.
   $f({\mathbf{x}}^{\ast })=p^{\ast }=q^{\ast }$
2. The dual optimal value $q^{\ast }$ is obtained by evaluating the dual function at ${\mathbf{\mu }}^{\ast }$. The dual function itself, $\varphi (\mathbf{\mu })$, is defined as the minimum of the Lagrangian over $\mathbf{x}$.
   $q^{\ast }=\varphi ({\mathbf{\mu }}^{\ast })={\min }_{\mathbf{x}}L(\mathbf{x},{\mathbf{\mu }}^{\ast })$
3. Since the unconstrained minimum of $L(\mathbf{x},{\mathbf{\mu }}^{\ast })$ must be less than or equal to the value of the function at any specific point, it must be less than or equal to its value at our solution ${\mathbf{x}}^{\ast }$.
   ${\min }_{\mathbf{x}}L(\mathbf{x},{\mathbf{\mu }}^{\ast })\le L({\mathbf{x}}^{\ast },{\mathbf{\mu }}^{\ast })$
4. By definition of the Lagrangian, $L({\mathbf{x}}^{\ast },{\mathbf{\mu }}^{\ast })=f({\mathbf{x}}^{\ast })+{\sum }_j{\mu }_j^{\ast }{g}_j({\mathbf{x}}^{\ast })$. Since ${\mathbf{x}}^{\ast }$ is a feasible solution, we know $g_j({\mathbf{x}}^{\ast })\le 0$. Since we also require ${\mu }_j^{\ast }\ge 0$, the sum ${\sum }_j{\mu }_j^{\ast }{g}_j({\mathbf{x}}^{\ast })$ must be less than or equal to zero. This gives us:
   $L({\mathbf{x}}^{\ast },{\mathbf{\mu }}^{\ast })\le f({\mathbf{x}}^{\ast })$

Now, let's put it all together:
$f({\mathbf{x}}^{\ast })={\min }_{\mathbf{x}}L(\mathbf{x},{\mathbf{\mu }}^{\ast })\le L({\mathbf{x}}^{\ast },{\mathbf{\mu }}^{\ast })\le f({\mathbf{x}}^{\ast })$

This chain of inequalities starts and ends with $f({\mathbf{x}}^{\ast })$. This forces the inequalities in the middle to become equalities, which gives us two crucial results:

Result 1: Complementary Slackness
From $L({\mathbf{x}}^{\ast },{\mathbf{\mu }}^{\ast })=f({\mathbf{x}}^{\ast })$, we get:
$f({\mathbf{x}}^{\ast })+{\sum }_j{\mu }_j^{\ast }{g}_j({\mathbf{x}}^{\ast })=f({\mathbf{x}}^{\ast })⟹{\sum }_j{\mu }_j^{\ast }{g}_j({\mathbf{x}}^{\ast })=0$
Since each term ${\mu }_j^{\ast }{g}_j({\mathbf{x}}^{\ast })$ is a product of a non-negative number (${\mu }_j^{\ast }$) and a non-positive number ($g_j({\mathbf{x}}^{\ast })$), each term is non-positive. The only way for a sum of non-positive terms to be zero is if every term is individually zero. Thus:
${\mu }_j^{\ast }{g}_j({\mathbf{x}}^{\ast })=0\text{for all }j$
This is the complementary slackness condition we anticipated in the last lesson.

Result 2: Stationarity
From ${\min }_{\mathbf{x}}L(\mathbf{x},{\mathbf{\mu }}^{\ast })=L({\mathbf{x}}^{\ast },{\mathbf{\mu }}^{\ast })$, we see that ${\mathbf{x}}^{\ast }$ is an unconstrained minimizer of the function $L(\mathbf{x},{\mathbf{\mu }}^{\ast })$. In your multivariate calculus studies, you learned that a necessary condition for a point to be an unconstrained minimizer of a differentiable function is that the gradient at that point is zero.
${\nabla }_{\mathbf{x}}L({\mathbf{x}}^{\ast },{\mathbf{\mu }}^{\ast })=0⟹\nabla f({\mathbf{x}}^{\ast })+{\sum }_j{\mu }_j^{\ast }\nabla g_j({\mathbf{x}}^{\ast })=0$
This is the stationarity condition. It generalizes the gradient alignment idea from Lagrange multipliers.

This final part of the video puts these pieces together to state the full KKT conditions.

4. The Complete KKT Conditions

Let's consolidate what we've derived into a single, formal set of conditions. For a general optimization problem with both equality constraints $h_i(\mathbf{x})=0$ and inequality constraints $g_j(\mathbf{x})\le 0$, if ${\mathbf{x}}^{\ast }$ is a local optimum and a "constraint qualification" (a regularity condition) holds, then there must exist multipliers ${\mathbf{\lambda }}^{\ast }$ and ${\mathbf{\mu }}^{\ast }$ such that the following four conditions are satisfied:

1. Stationarity:
   $\nabla f({\mathbf{x}}^{\ast })+{\sum }_i{\lambda }_i^{\ast }\nabla h_i({\mathbf{x}}^{\ast })+{\sum }_j{\mu }_j^{\ast }\nabla g_j({\mathbf{x}}^{\ast })=0$
2. Primal Feasibility:
   $h_i({\mathbf{x}}^{\ast })=0\text{for all }i$
   $g_j({\mathbf{x}}^{\ast })\le 0\text{for all }j$
3. Dual Feasibility:
   ${\mu }_j^{\ast }\ge 0\text{for all }j$
   (Note that the Lagrange multipliers ${\lambda }_i^{\ast }$ for the equality constraints are unrestricted in sign).
4. Complementary Slackness:
   ${\mu }_j^{\ast }{g}_j({\mathbf{x}}^{\ast })=0\text{for all }j$

Test your understanding!

Suppose you solve an optimization problem and find that for a particular inequality constraint $g_k(\mathbf{x})\le 0$, the optimal solution ${\mathbf{x}}^{\ast }$ yields $g_k({\mathbf{x}}^{\ast })=-0.5$. What can you immediately conclude about its corresponding KKT multiplier ${\mu }_k^{\ast }$? Why?

Show answer

You can immediately conclude that ${\mu }_k^{\ast }=0$. This is a direct consequence of the complementary slackness condition, ${\mu }_k^{\ast }{g}_k({\mathbf{x}}^{\ast })=0$. Since $g_k({\mathbf{x}}^{\ast })=-0.5\ne 0$, the multiplier ${\mu }_k^{\ast }$ must be zero to satisfy the condition. This makes intuitive sense: the constraint is inactive (not on the boundary), so it does not contribute to the gradient sum in the stationarity condition.

For a formal, consolidated statement of the theorem guaranteeing these conditions, the following resource is excellent.

Given your interest in rigorous proofs, you might also appreciate an alternative method for proving the non-negativity of the multipliers (${\mu }_j^{\ast }\ge 0$), which uses proof by contradiction.

5. A Note on Constraint Qualifications

We have mentioned that the KKT conditions are necessary for an optimum, provided the problem is "well-behaved." This regularity is formally captured by constraint qualifications. These are mathematical conditions on the constraint functions that prevent pathological cases where the geometry of the feasible set boundary is degenerate.

For instance, if the gradients of the active constraints are not linearly independent (a condition called LICQ), the KKT conditions might fail to hold at a valid minimum. For the important class of convex optimization problems, a much simpler condition known as Slater's condition is often sufficient. It essentially requires that there exists at least one point that is strictly feasible.

You do not need to master these qualifications now, but it is important to know that they are a required assumption for the KKT theorem to hold.

Conclusion

Today, we successfully navigated one of the central derivations in optimization theory. Starting from the min-max formulation of an inequality-constrained problem, we used the powerful concept of duality to derive the complete set of Karush-Kuhn-Tucker (KKT) conditions.

Key Takeaways:

• The concepts of primal and dual problems and the assumption of strong duality ($p^{\ast }=q^{\ast }$) are the foundation for the derivation.
• By equating the primal and dual optimal values, we force a chain of inequalities to hold with equality, which in turn yields two of the main KKT conditions: stationarity and complementary slackness.
• The complete KKT conditions consist of four parts: Stationarity, Primal Feasibility, Dual Feasibility, and Complementary Slackness.
• These conditions are necessary for a point to be a local optimum, provided a constraint qualification holds.

Preview of the Next Lesson:
We have now concluded our intensive study of calculus-based optimization theory. We have built a strong foundation, moving from gradients and Hessians to Lagrange multipliers and now the KKT conditions. This completes the fifth module of our course. In our next lesson, we will pivot to a new and equally fundamental area of mathematics for machine learning: Probability Theory. We will start from the ground up, defining probability spaces, sample spaces, and the axioms that govern the entire field.