Lagrangian Duality: Derivation and Strong Duality Conditions

From Primal to Dual

Let's recall the standard constrained optimization problem and its primal formulation, which we established in the previous lesson.

Primal Problem:

where the Lagrangian is $L(\mathbf{x},\mathbf{u},\mathbf{v})=f(\mathbf{x})+{\sum }_i{u}_i{g}_i(\mathbf{x})+{\sum }_j{v}_j{h}_j(\mathbf{x})$. The value $p^{\ast }$ is the optimal value of our original problem.

The central idea of duality is to consider what happens if we switch the order of the inf and sup. This gives rise to the dual problem.

Dual Problem:

To make sense of this, we first define the inner part, inf_x L(x, u, v), as a new function.

The Lagrange Dual Function

For a fixed set of multipliers $(\mathbf{u},\mathbf{v})$, the Lagrange dual function $g(\mathbf{u},\mathbf{v})$ is defined as the infimum of the Lagrangian over the primal variables $\mathbf{x}$:

Note that this infimum is taken over all $\mathbf{x}$ in the domain, without regard for the original constraints.

A fascinating and crucial property of the dual function $g(\mathbf{u},\mathbf{v})$ is that it is always concave, regardless of whether the original problem was convex. This is because it is the pointwise infimum of a family of affine functions of $(\mathbf{u},\mathbf{v})$. Since we will be maximizing this function, this means the dual problem is a convex optimization problem, which is often much easier to solve.

The following video provides an excellent intuitive walkthrough of defining the dual function.

With the dual function defined, the dual problem is simply to find the best possible value of $g(\mathbf{u},\mathbf{v})$, subject to the dual feasibility constraints.

The following reading formally defines the Lagrange dual function and the resulting dual problem.

Weak Duality: A Universal Lower Bound

The dual problem is interesting because its optimal value, $d^{\ast }$, provides a lower bound on the optimal value of the primal problem, $p^{\ast }$. This relationship, known as weak duality, always holds for any optimization problem, convex or not.

Weak Duality Theorem: $d^{\ast }\le p^{\ast }$.

This is a direct consequence of the max-min inequality, which states that for any function $F(w,z)$, we have:

In our case, $F$ is the Lagrangian $L$, $w$ is $\mathbf{x}$, and $z$ is $(\mathbf{u},\mathbf{v})$.

The proof is remarkably simple but profound. It establishes that for any choice of dual variables $(\mathbf{u},\mathbf{v})$ that are dual-feasible, the value $g(\mathbf{u},\mathbf{v})$ is a valid lower bound on the true optimal value $p^{\ast }$. The dual problem, therefore, can be interpreted as a search for the tightest possible lower bound on the primal objective.

Strong Duality and Slater's Condition

While knowing that $d^{\ast }\le p^{\ast }$ is useful, the real power of duality is unlocked when the inequality becomes an equality. This is called strong duality.

Strong Duality: $d^{\ast }=p^{\ast }$.

When strong duality holds, the duality gap—the difference $p^{\ast }-d^{\ast }$—is zero. This means we can find the optimal value of the (potentially difficult, non-convex) primal problem by solving the (always convex) dual problem.

Strong duality does not hold for all problems. However, for convex optimization problems, it holds under fairly mild conditions. The most common of these is Slater's condition.

Slater's Condition: For a convex optimization problem, if there exists a point $\mathbf{x}$ that is strictly feasible—meaning it satisfies all inequality constraints with strict inequality ($g_i(\mathbf{x})<0$)—then strong duality holds.

For many problems in machine learning and engineering, this condition is naturally satisfied. If you have a constraint on power being less than or equal to 100mW, it's almost certain that a design using 99.9mW exists. The existence of such a point with a "margin" is enough to guarantee strong duality.

The following video discusses the distinction between weak and strong duality and provides a practical perspective on why Slater's condition is often a reasonable assumption.

Geometric Interpretation of Duality

A powerful way to visualize duality is to consider the set of achievable values for the constraints and the objective. Let's imagine a simple problem with one inequality constraint $g_1(\mathbf{x})\le 0$. We can define a set $\mathcal{A}$ in a 2D plane, where each point $(u,t)$ in the set corresponds to the values $(g_1(\mathbf{x}),f(\mathbf{x}))$ for some $\mathbf{x}$.

• The primal optimal value $p^{\ast }$ is the minimum objective value $t$ we can achieve while being feasible ($u\le 0$). Geometrically, this is the lowest point of the set $\mathcal{A}$ that touches the $t$-axis or is to its left. In the diagram, this is marked as $(0,p^{\ast })$.

• The dual function $g(\lambda )$ for a given $\lambda \ge 0$ can be shown to be the vertical intercept of a supporting hyperplane with slope $-\lambda$ to the set $\mathcal{A}$. The line $\lambda u+t=g(\lambda )$ is one such supporting line.

• The dual optimal value $d^{\ast }$ is the maximum of these intercepts over all valid slopes ($\lambda \ge 0$). It is the highest point on the $t$-axis that can be touched by a non-vertical supporting hyperplane from below.

The duality gap is the vertical distance between $p^{\ast }$ and $d^{\ast }$. From the picture, it's clear that $d^{\ast }\le p^{\ast }$. If the set $\mathcal{A}$ is convex and doesn't have any strange vertical boundaries at $u=0$, the supporting hyperplane will be able to "slide up" until it touches the point $(0,p^{\ast })$, making the duality gap zero. This is the geometric essence of strong duality.

Conclusion

In this lesson, we have moved from the primal formulation of a constrained optimization problem to its dual. This "dual perspective" is a cornerstone of modern optimization and machine learning.

The key takeaways are:

• The Lagrange dual problem is formed by swapping the min and max in the primal formulation. It involves maximizing the Lagrange dual function $g(\mathbf{u},\mathbf{v})={\inf }_{\mathbf{x}}L(\mathbf{x},\mathbf{u},\mathbf{v})$.
• The dual problem is always a convex optimization problem, which is a significant advantage.
• Weak duality ($d^{\ast }\le p^{\ast }$) always holds, meaning the dual problem provides a lower bound on the true optimal value.
• Strong duality ($d^{\ast }=p^{\ast }$) holds for convex problems that satisfy certain "constraint qualifications," the most common being Slater's condition. When strong duality holds, we can solve the primal by solving the dual.
• The duality gap ($p^{\ast }-d^{\ast }$) can be visualized as the space between the feasible optimum and the best supporting hyperplane from below.

This concludes our module on the mathematical foundations of optimization. We have built a powerful toolkit, starting from simple gradient descent and culminating in the elegant theory of Lagrangian duality. You now have the necessary mathematical machinery to understand how many of the classic machine learning algorithms are trained.

In our next lesson, we will pivot from optimization to the foundations of probability in machine learning. We will begin by deriving the principle of Maximum Likelihood Estimation (MLE), a fundamental framework for fitting probabilistic models to data. This will shift our focus from how we find the minimum of a function to what function we should be minimizing in the first place.