4.2. Lagrangian Duality

Lagrangian Duality

A large class of constrained optimization problems can be written in the primal form

p^* = \min_{x \in X} \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x) \le 0, \quad i=1,\ldots,m, \\ & h_j(x) = 0, \quad j=1,\ldots,k. \end{aligned}$$ Even when this problem is convex, the constraints may make it difficult to solve directly. **Lagrangian duality** handles constraints by embedding them into the objective using multipliers. The **Lagrangian** is defined as $$\mathcal{L}(x,\lambda,\mu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{j=1}^k \mu_j h_j(x),$$ where $\lambda_{i} \ge 0$ are multipliers for inequality constraints and $\mu_{j}$ are unrestricted multipliers for equality constraints. For fixed $(\lambda,\mu)$, minimizing $\mathcal{L}$ over $x$ produces a **lower bound** on the primal objective. This gives the **dual function** $$g(\lambda,\mu) = \inf_{x \in X} \mathcal{L}(x,\lambda,\mu),$$

and the Lagrangian dual problem,

$d^{\ast }={\sup }_{\lambda \ge 0,;\mu }g(\lambda ,\mu ).$

A fundamental property is weak duality, where $d^{\ast }\le p^{\ast }$, meaning the dual problem always provides a lower bound on the primal problem. Any feasible dual variables therefore act as a certificate of optimality.

When the primal problem is convex, stronger results are possible. Slater’s condition ensures that the feasible set has “room” inside its boundary by requiring the existence of some $x_0$ such that $f_i(x_0)<0$ for all inequality constraints, while satisfying all equality constraints.

If Slater’s condition holds, then strong duality applies (i.e., $p^{\ast }=d^{\ast }$), and optimal dual variables $(\lambda ,\mu )$ exist.

Under strong duality, optimality can be characterized entirely through the Karush–Kuhn–Tucker (KKT) conditions. A triple $(x^{\ast },{\lambda }^{\ast },{\mu }^{\ast })$ is optimal if and only if it meets the following conditions:

1. Primal feasibility: $f_i(x^{\ast })\le 0\text{ for }i=1,\dots ,k,h_j(x^{\ast })=0\text{ for }j=1,\dots ,m$.
2. Dual feasibility: ${\lambda }_1^{\ast },\dots ,{\lambda }_k^{\ast }\ge 0$.
3. Complementary slackness: ${\lambda }_i^{\ast }{f}_i(x^{\ast })=0,i=1,\dots ,k$.
4. Stationarity: $\nabla f_0(x^{\ast })+{\sum }_{i=1}^m{\lambda }_i^{\ast }\nabla f_i(x^{\ast })+{\sum }_{j=1}^k{\mu }_j^{\ast }\nabla h_j(x^{\ast })=0$.

Complementary slackness encodes the idea that a constraint is either active or its multiplier is zero, while stationarity balances the objective gradient against the gradients of active constraints.

In the unconstrained convex case, the KKT conditions reduce to $\nabla f_0(x^{\ast })=0$, which is both necessary and sufficient for global optimality. For non-convex problems, KKT conditions remain necessary but are no longer sufficient; they become first-order necessary optimality conditions.

Lagrangian duality is closely related to convex relaxation. If the feasible set $S$ is non-convex, replacing it with a convex superset $\tilde{S}$ yields a relaxed problem whose optimal value lower-bounds the original. Duality formalizes this idea: the dual problem searches over the best possible convex lower bounds.

KKT Examples

KKT Conditions I

Consider the convex problem

\min_{x \in \mathbb{R}^4} \quad & x_1^2 + x_2^2 + x_3^2 + x_4^2 \\\ \text{s.t.} \quad & x_1 + x_2 + x_3 + x_4 = 1. \end{aligned}$$ >[!example]- Write down the KKT conditions and compute the optimal solution. >We have that >$$\mathcal{L}(x, \mu) = x_{1}^2 + x_2^2 + x_3^2 + x_4^2 + \mu(x_1 + x_2 + x_3 + x_4-1)$$. >Therefore, >$$\nabla \mathcal{L} = \begin{bmatrix}2x_{1}+\mu \\ 2x_{2}+\mu \\ 2x_{3} + \mu \\ 2x_{4} + \mu\end{bmatrix}=0,$$ >such that $x_{1}^*=x_{2}^*=x_{3}^*=x_{4}^*=-\mu^* / 2$. >Substituting into the equality constraint, we obtain >$$4 \cdot (-\mu^* / 2) = 1 \iff \mu^* = -\frac{1}{2}.$$ >Therefore, $x_{1}^*=x_{2}^*=x_{3}^*=x_{4}^*=1 / 4$.

KKT Conditions II

Consider the convex problem

$$\begin{array}{rl}\underset{x\in {\mathbb{R}}^2}{\min }& x_1^2+x_2^2\\ \text{s.t.}& x_1+x_2=1,\\ & x_2\le \alpha .\end{array}$$

Write down the KKT conditions and compute the optimal solution. $\mathcal{L}(x,\lambda ,\mu )=x_1^2+x_2^2+\lambda (x_2-\alpha )+\mu (x_1+x_2-1).$ By stationarity, it follows that $\nabla \mathcal{L}=\left[\begin{array}{c}2x_1+\mu \\ 2x_2+\lambda +\mu \end{array}\right]=0,$ where $x_1=-\mu /2$ and $x_2=-\frac{\lambda +\mu }{2}$. Plugging this into the equality constraint, $-\mu /2-(\lambda +\mu )/2=1⟺\lambda +2\mu =-2.$ By complementary slackness, we have 2 cases: either $\lambda =0$ or $x_2=\alpha$. In case 1, the equation above simplifies to $\mu =-1$, and therefore $x_1=1/2$, $x_2=1/2$, such that feasibility requires $\alpha \ge 1/2=x_2$. In case 2, we have that $\alpha =-(\lambda +\mu )/2⟺\lambda +\mu =-2\alpha ,$ so together with the equality constraint $\lambda +2\mu =-2$ we get $-2\mu +\mu -2=-2\alpha ⟺\mu =2\alpha -2.$ As such, $\lambda =2-4\alpha \ge 0$ by dual feasibility, and therefore $\alpha \le 1/2$. To summarize, we get the following two cases: $({\lambda }^{\ast },{\mu }^{\ast })=\{\begin{array}{ll}(0,-1)& \alpha \ge 1/2,\\ (2-4\alpha ,2\alpha -2)& \alpha <1/2.\end{array}$ The neat thing about this is that at $\alpha =1/2$, both simplify to $(0,-1)$. Then, $(x_1^{\ast },x_2^{\ast })=\{\begin{array}{ll}(1/2,1/2)& \alpha \ge 1/2,\\ (1-2\alpha ,\alpha )& \alpha <1/2.\end{array}$

We have that

Equality-Constrained Least Squares (KKT Conditions III)

Consider the equality constrained least-squares problem

$$\begin{array}{rl}\underset{x}{\min }& \Vert Ax-b{\Vert }_2^2\\ \text{s.t.}& Gx=h,\end{array}$$

where $A\in {\mathbb{R}}^{m\times n}$ with $\text{rank}(A)=n$ and $G\in {\mathbb{R}}^{p\times n}$ with $\text{rank}(G)=p$.

Write down the KKT conditions and compute the optimal solution. $\mathcal{L}(x,\mu )=x^T{A}^{T}Ax+(G^T\mu -2A^{T}b{)}^{T}x-{\mu }^{T}h,$ where the term $b^{T}b$ is a constant irrelevant to the optimization problem, and therefore is omitted. The stationary condition is $\nabla \mathcal{L}=2A^{T}Ax+G^T\mu -2A^{T}b=2A^T(Ax-b)+G^T\mu =0,$ which yields $x^{\ast }=(A^{T}A{)}^{-1}\left(A^{T}b-\frac{1}{2}{G}^T\mu \right)$. Plugging $x^{\ast }$ into the equality constraint, $G(A^{T}A{)}^{-1}\left(A^{T}b-\frac{1}{2}{G}^T\mu \right)=h,$ such that ${\mu }^{\ast }=-2(G(A^{T}A{)}^{-1}{G}^T{)}^{-1}(h-G(A^{T}A{)}^{-1}{A}^{T}b)$. Substituting into $x^{\ast }=\dots$ yields the solution.

The Lagrangian is

KKT Conditions IV

Consider the optimization problem

$$\begin{array}{rl}\underset{x\in {\mathbb{R}}^2}{\min }& 8x_1^2+10x_2^2-12x_1{x}_2+50x_1-80x_2\\ \text{s.t.}& x_1+x_2\le 1,\\ & x_1^2+4x_2^2\le 6,\\ & x_1\ge 0,\\ & x_2\ge 0.\end{array}$$

Prove that the optimization problem is convex. $\nabla f_0(x)=\left[\begin{array}{c}16x_1-12x_2+50\\ 20x_2-12x_1-80\end{array}\right],$ ${\nabla }^2{f}_0(x)=\left[\begin{array}{cc}16& -12\\ -12& 20\end{array}\right],$ and find that the eigenvalues of the Hessian are $\frac{{\lambda }_{1,2}=36\pm \sqrt{36^2-4\cdot 176}}{2}$, which are both positive.

All constraints are trivially convex. To prove that the objective is convex, we take its gradient and Hessian:

We can also test this using the determinant and the trace, which are both positive:

• If $\det (H)>0$, then ${\lambda }_1{\lambda }_2>0$, which means that the eigenvalues are either both positive or negative.
• If $\text{tr}(H)>0$, then both eigenvalues are positive.
  This is sufficient to show that $H$ is positive semi-definite, and therefore the problem is convex.

Show that Slater's condition holds. $f_i(x)<0$. Therefore, Slater's condition holds. An example of this is setting $x_1=x_2=ϵ$, which strictly satisfies all constraints.

All inequality constraints have domains that meet

Write the KKT conditions for this problem.

We have the following functions:

f_{0}(x) &= 8x_{1}^2+10x_{2}^2-12x_{1}x_{2}+50x_{1}-80x_{2} \\ f_{1}(x) &= x_{1}+x_{2}-1 \\ f_{2}(x) &= x_{1}^2 + 4x_{2}^{2}-6 \\ f_{3}(x) &= -x_{1} \\ f_{4}(x) &= -x_{2} \end{align}$$ Taking their gradients, we have

\begin{align}
\nabla f_{0}(x) &= \begin{bmatrix}
16x_{1}-12x_{2}+50 \ 20x_{2}-12x_{1}-80
\end{bmatrix} \
\nabla f_{1}(x) &= \begin{bmatrix}
1 \ 1
\end{bmatrix} \
\nabla f_{2}(x) &= \begin{bmatrix}
2x_{1} \ 8x_{2}
\end{bmatrix} \
\nabla f_{3}(x) &= \begin{bmatrix}
-1 \ 0
\end{bmatrix} \
\nabla f_{0}(x) &= \begin{bmatrix}
0 \ -1
\end{bmatrix}
\end{align}

$$FortheKKTconditions,allaresatisfied:$$

\begin{align}
(1) \quad & f_{i}(x) \leq 0 \
(2) \quad & \lambda_{i}^{} \geq 0 \
(3) \quad & \lambda_{i}^{}f_{i}(x) = 0 \
(4) \quad & \nabla \mathcal{L}(x, \lambda) = \begin{bmatrix}
16x_{1}-12x_{2}+50+\lambda_{1}+2\lambda_{2}x_{1}-\lambda_{3} \
20x_{2}-12x_{1}-80 + \lambda_{1} + 8\lambda_{2}x_{2}-\lambda_{4}
\end{bmatrix}=0.
\end{align}

By studying the KKT conditions, show that $x^{\ast }={\left[\begin{array}{cc}0& 1\end{array}\right]}^T$ is a global minimum of the problem.  Note that $x^{\ast }$ satisfies all primal constraints in $(1)$. We must now analyze the Lagrange multiplies $L$. We see that the nonzero equations for $(3)$ complementary slackness are $-2{\lambda }_2^{\ast }=0,-{\lambda }_4^{\ast }=0,$ therefore ${\lambda }_2^{\ast }={\lambda }_4^{\ast }=0$. We then solve the stationarity condition, to see that

16 \cdot 0 - 12 \cdot 1 + 50 + \lambda_{1}^*+2\cdot 0 - \lambda_{3} &= 0 \\ 20-12\cdot 0-80+\lambda_{1}^*+8 \cdot 0 \cdot 1 - 0 &= 0, \end{align}$$ so we have $\lambda_{1}^*=60$, $\lambda_{2}^*=98$, which satisfy stationarity and are nonnegative. Therefore, the given $x^*$ is a global minimum.

Markov Transition Probabilities (KKT Conditions V)

Consider the optimization problem

\max_{x \in \mathbb{R}^n} \quad & \sum_{i=1}^n \alpha_i \log(x_i) \\ \text{s.t.} \quad & x_i \ge 0, \quad i = 1,2,\ldots,n, \\ & \sum_{i=1}^n x_i = c . \end{aligned}$$ where $\alpha_{1}, \ldots, \alpha_{n}$ and $c$ are strictly positive constants. Problems of this form arise in maximum-likelihood estimation of the transition probabilities of discrete-time Markov chains. >[!example]- Show that Slater's condition holds. >We can set each $x_{i}=c / n$. Then, both constraints are strictly satisfied since $c>0$. >[!example]- Write the KKT conditions for this problem. >We know that $\log$ is concave. As such, $-\log$ is convex. We have: >$$\begin{align} >f_{0}(x)&=-\sum_{i=1}^{n}\alpha_{i}\log(x_{i}) \\ >f_{i}(x)&=-x_{i}, \quad i=1,2,\ldots,n \\ >h(x) &= 1^Tx-c. >\end{align}$$ >The gradients become: >$$\begin{align} >\nabla f_{0}(x) &= \begin{bmatrix}-\alpha_{1} / x_{1} & \ldots & -\alpha_{n} / x_{n}\end{bmatrix}^T &\\ >\nabla f_{i}(x) &= -e_{i}, & i = 1,2,\ldots, n \\ >\nabla h_{i}(x) &= 1. >\end{align}$$ >Here, $-e_{i}$ is the negative of the standard basis vector with $1$ at position $i$ and zeros everywhere else. Now, let $x^* \in \mathbb{R}^n$ be a global minimum of the convex problem. Then, $x^*$ must satisfy: >$$\begin{align} >(1) & \quad f_{i}(x) \leq 0 \quad \text{and} \quad h(x)=0 \\ >(2) & \quad \lambda_{i}^* \geq 0 \\ >(3) & \quad \lambda_{i}^{*}f_{i}(x)=0 \\ >(4) & \quad \nabla \mathcal{L}(x, \lambda, \mu)=0 >\end{align}$$ >We check that stationarity is satisfied: >$$\nabla \mathcal{L}(x, \lambda, \mu) =-\alpha_{i} / x_{i}-\lambda_{i}+\mu \quad i=1,\ldots,n.$$ >[!example]- Show that the Lagrange multipliers for the inequality constraints are all zero while the Lagrange multiplier for the equality constraint is equal to $-\frac{{\alpha_{1}+\ldots+\alpha_{n}}}{c}$ (note that depending on your choice of $h$ you may also get $\frac{{\alpha_{i}+\ldots+\alpha_{n}}}{c}$). >Take a look at $(3)$ stationarity from the previous subpart. Either $f_{i}(x)=-x_{i}=0$ or $\lambda_{i}^*=0$. However, $x_{i}=0$ is not valid if you take a look at condition $(4)$, since each $x_{i}$ is a denominator, and therefore the stationary condition will be undefined. As such, all $\lambda_{i}^{*}=0$. Stationarity then simplifies to: >$$-\alpha_{i} / x_{i}+\mu=0 \iff x_{i}=\alpha_{i} / \mu.$$ >Plug this into $h$: >$$\sum^{n}_{i=1}\alpha_{i} / \mu - c = 0 \iff \mu = \frac{1}{c}\sum^{n}_{i=1}\alpha_{i}.$$ >[!example]- By solving the KKT conditions, find all optimal solutions $x^*$ of the optimization problem, and calculate the optimal objective.

Duality Examples

Strong or Weak Duality?

Consider the optimization problem

\min_{(x,y)\in \mathcal{D}} \quad & e^{-x} \
\text{s.t.} \quad & \frac{x^2}{y} \le 0,
\end{aligned}$$

where $\mathcal{D}=\{(x,y)\mid y>0\}$.

Show that the problem is convex. $e^x$ are convex by design. For the objective, we compute the gradient:

Exponential functions