Chapter 5: Duality

Duality is a central concept in optimization theory. It associates with every optimization problem (the primal) a companion dual problem whose optimal value provides a lower bound on the primal optimal value. Under convexity and suitable regularity conditions, the two optimal values coincide (strong duality), giving rise to powerful optimality conditions known as the KKT conditions.

---

5.1 Motivation: From Constrained to Unconstrained

Consider the single-inequality problem

$$p^{\ast }=\underset{x}{min}f(x)\text{s.t.}g(x)\le 0.$$

Constrained problems are difficult to optimize directly. The key idea is to absorb the constraint into the objective using an indicator function:

$$I_{g\le 0}(x)=\{\begin{array}{ll}0,& g(x)\le 0,\\ +\mathrm{\infty },& g(x)>0.\end{array}$$

Then the problem becomes unconstrained:

$$p^{\ast }=\underset{x}{min}(f(x)+I_{g\le 0}(x)).$$

5.1.1 Linearizing the Indicator

Key Claim

$$I_{g\le 0}(x)=\underset{\lambda \ge 0}{max}\lambda g(x).$$

Explanation: If $g(x)\le 0$, then $\lambda g(x)\le 0$ for all $\lambda \ge 0$, so the supremum is $0$. If $g(x)>0$, then $\lambda g(x)\to +\mathrm{\infty }$ as $\lambda \to \mathrm{\infty }$, so the supremum is $+\mathrm{\infty }$.

Thus the indicator function can be expressed as a linear supremum.

5.1.2 Min–Max Reformulation

Substituting, we obtain

$$f(x)+I_{g\le 0}(x)=f(x)+\underset{\lambda \ge 0}{max}\lambda g(x)=\underset{\lambda \ge 0}{max}(f(x)+\lambda g(x)).$$

Hence the original problem becomes an unconstrained min–max problem:

$$p^{\ast }=\underset{x}{min}\underset{\lambda \ge 0}{max}(f(x)+\lambda g(x)).$$

Game interpretation: Player A (the minimizer) chooses $x$; Player B (the maximizer) chooses $\lambda \ge 0$. The quantity being optimized is

$$L(x,\lambda )=f(x)+\lambda g(x).$$

The order of play matters—this motivates the fundamental inequality of duality.

---

5.2 The Weak Max–Min Inequality

Theorem (Weak Max–Min Inequality)

For any function $\phi (x,y)$,

$$\underset{y}{max}\underset{x}{min}\phi (x,y)\le \underset{x}{min}\underset{y}{max}\phi (x,y).$$

Proof sketch: For any fixed $y_0$ and $x_0$,

$$\underset{x}{min}\phi (x,y_0)\le \phi (x_0,y_0)\le \underset{y}{max}\phi (x_0,y).$$

Taking $\underset{y_0}{max}$ on the left and then $\underset{x_0}{min}$ on the right establishes the inequality.

Applying this inequality to the Lagrangian $L(x,\lambda )=f(x)+\lambda g(x)$ yields:

$$\underset{\lambda \ge 0}{max}\underset{x}{min}L(x,\lambda )\le \underset{x}{min}\underset{\lambda \ge 0}{max}L(x,\lambda )=p^{\ast }.$$

---

5.3 Definitions: Lagrangian, Dual Function, Dual Problem

For the single-inequality problem, we define:

Definition (Lagrangian, Single-Inequality Case)

$$L(x,\lambda )=f(x)+\lambda g(x),\lambda \ge 0.$$

$\lambda$ is called the Lagrange multiplier (or dual variable).

Definition (Dual Function)

$$q(\lambda )=\underset{x}{min}L(x,\lambda ).$$

Definition (Dual Problem)

$$d^{\ast }=\underset{\lambda \ge 0}{max}q(\lambda ).$$

Definition (Weak Duality)

$$d^{\ast }\le p^{\ast }.$$

The difference $p^{\ast }-d^{\ast }$ is called the duality gap (always $\ge 0$).

Definition (Strong Duality)

$p^{\ast }=d^{\ast }$. This holds for convex problems under appropriate regularity conditions (e.g., Slater's condition).

Example: Unit Circle Constraint

Consider

$$\underset{x_1,x_2}{min}{x}_1+x_2\text{s.t.}{x}_1^2+x_2^2\le 1.$$

• Lagrangian: $L(x,\lambda )=x_1+x_2+\lambda (x_1^2+x_2^2-1),\lambda \ge 0.$

• Dual function: For $\lambda >0$,

  $$g(\lambda )=\underset{x}{min}L(x,\lambda )=-\frac{1}{2\lambda }-\lambda ,(x_1^{\ast }=x_2^{\ast }=-\frac{1}{2\lambda }).$$

• Dual problem:

  $$\underset{\lambda \ge 0}{max}g(\lambda )=\underset{\lambda \ge 0}{max}(-\frac{1}{2\lambda }-\lambda )=-\sqrt{2},({\lambda }^{\ast }=\frac{1}{\sqrt{2}}).$$

• Verification: The primal solution is $x^{\ast }=(-\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}})$ on the unit circle, giving $p^{\ast }=-\sqrt{2}=d^{\ast }$. Strong duality holds.

---

5.4 The General Optimization Problem

Extend the idea to the standard form:

$$\begin{array}{rl}\underset{x}{min}& f(x)\\ \text{s.t.}& g_i(x)\le 0,i=1,\dots ,m,\\ & h_j(x)=0,j=1,\dots ,p.\end{array}$$

• Inequality constraints require ${\lambda }_i\ge 0$ (nonnegative multipliers).
• Equality constraints require no sign restriction on ${\nu }_j\in \mathbb{R}$.

Definition (Lagrangian, General Case)

Let $\lambda \in {\mathbb{R}}_{+}^m$ and $\nu \in {\mathbb{R}}^p$. The Lagrangian is

$$L(x,\lambda ,\nu )=f(x)+\sum _{i=1}^m{\lambda }_i{g}_i(x)+\sum _{j=1}^p{\nu }_j{h}_j(x)=f(x)+{\lambda }^{\mathrm{\top }}g(x)+{\nu }^{\mathrm{\top }}h(x).$$

Definition (Lagrange Dual Function)

$$g(\lambda ,\nu )=\underset{x\in \mathcal{D}}{inf}L(x,\lambda ,\nu )=\underset{x\in \mathcal{D}}{inf}(f(x)+\sum _{i=1}^m{\lambda }_i{g}_i(x)+\sum _{j=1}^p{\nu }_j{h}_j(x)),$$

where $\mathcal{D}$ is the domain of the primal problem.

Properties:

• $g(\lambda ,\nu )$ is a concave function of $(\lambda ,\nu )$.
• $g$ can be $-\mathrm{\infty }$ for some $(\lambda ,\nu )$, which defines its effective domain.
• Lower bound property: If $\lambda ⪰0$, then $g(\lambda ,\nu )\le p^{\ast }$.

Proof of lower bound property: If $\tilde{x}$ is feasible and $\lambda ⪰0$, then

$$f(\tilde{x})\ge L(\tilde{x},\lambda ,\nu )\ge \underset{x\in \mathcal{D}}{inf}L(x,\lambda ,\nu )=g(\lambda ,\nu ).$$

Minimizing over all feasible $\tilde{x}$ gives $p^{\ast }\ge g(\lambda ,\nu )$.

Definition (Lagrange Dual Problem)

$$\begin{array}{rl}\underset{\lambda ,\nu }{max}& g(\lambda ,\nu )\\ \text{s.t.}& \lambda ⪰0.\end{array}$$

• Always a convex optimization problem (maximization of a concave function), even when the primal is nonconvex.
• Optimal value denoted $d^{\ast }$.
• $(\lambda ,\nu )$ is dual feasible if $\lambda ⪰0$ and $(\lambda ,\nu )\in \mathrm{dom}g$.
• $d^{\ast }=-\mathrm{\infty }$ if the problem is infeasible; $d^{\ast }=+\mathrm{\infty }$ if unbounded above.

Why the Dual Problem is Always Convex

$$g(\lambda ,\nu )=\underset{x}{min}(f(x)+\sum _{i=1}^m{\lambda }_i{g}_i(x)+\sum _{j=1}^p{\nu }_j{h}_j(x))=-\underset{x}{max}(-f(x)-\sum _{i=1}^m{\lambda }_i{g}_i(x)-\sum _{j=1}^p{\nu }_j{h}_j(x)).$$

This is the (negative) pointwise supremum of affine functions in $(\lambda ,\nu )$, hence concave. The constraint $\lambda ⪰0$ is convex. Thus the dual is a concave maximization—i.e., a convex optimization problem.

---

5.5 Weak and Strong Duality

Theorem (Weak Duality)

$$d^{\ast }\le p^{\ast }.$$

This holds always—for convex and nonconvex problems alike. It can be used to find nontrivial lower bounds for difficult problems.

For example, solving the SDP dual of the two-way partitioning problem provides a lower bound on its (NP-hard) primal.

Theorem (Strong Duality)

$d^{\ast }=p^{\ast }$ does not hold in general, but (usually) holds for convex problems. Sufficient conditions that guarantee strong duality in convex problems are called constraint qualifications.

---

5.6 Slater's Constraint Qualification

Consider a convex problem:

$$\begin{array}{rl}\underset{x}{min}& f_0(x)\\ \text{s.t.}& f_i(x)\le 0,i=1,\dots ,m,\\ & Ax=b.\end{array}$$

Definition (Slater's Condition)

The problem is strictly feasible, i.e., there exists $x\in \mathrm{int}\mathcal{D}$ such that

$$f_i(x)<0,i=1,\dots ,m,Ax=b.$$

Theorem (Slater's Theorem)

If the primal is convex and Slater's condition holds, then:

1. Strong duality holds: $p^{\ast }=d^{\ast }$.
2. If $p^{\ast }>-\mathrm{\infty }$, the dual optimum is attained: there exist dual optimal ${\lambda }^{\ast },{\nu }^{\ast }$.

Refinements:

• $\mathrm{int}\mathcal{D}$ can be replaced with $\mathrm{relint}\mathcal{D}$ (relative interior).
• Linear inequalities do not need to hold with strict inequality.
• Many other constraint qualifications exist.

---

5.7 Complementary Slackness

Assume $x$ satisfies the primal constraints and $\lambda ⪰0$. Then

$$\begin{array}{rl}g(\lambda ,\nu )& =\underset{\tilde{x}\in \mathcal{D}}{inf}(f_0(\tilde{x})+\sum _{i=1}^m{\lambda }_i{f}_i(\tilde{x})+\sum _{i=1}^p{\nu }_i{h}_i(\tilde{x}))\\ & \le f_0(x)+\sum _{i=1}^m{\lambda }_i{f}_i(x)+\sum _{i=1}^p{\nu }_i{h}_i(x)\\ & \le f_0(x).\end{array}$$

Equality $f_0(x)=g(\lambda ,\nu )$ holds if and only if both inequalities hold with equality:

1. First inequality: $x$ minimizes $L(\tilde{x},\lambda ,\nu )$ over $\tilde{x}\in \mathcal{D}$.
2. Second inequality: ${\lambda }_i{f}_i(x)=0$ for $i=1,\dots ,m$.

Definition (Complementary Slackness)

$${\lambda }_i>0⟹f_i(x)=0,f_i(x)<0⟹{\lambda }_i=0.$$

Equivalently, ${\lambda }_i{f}_i(x)=0$ for all $i=1,\dots ,m$.

The name reflects that at least one of ${\lambda }_i$ and $f_i(x)$ is "slack" (zero) while the other may be tight.

---

5.8 KKT (Karush–Kuhn–Tucker) Conditions

Assume strong duality holds, $x^{\ast }$ is primal optimal, and $({\lambda }^{\ast },{\nu }^{\ast })$ is dual optimal. Then the following necessary conditions hold:

1. Primal feasibility: $f_i(x^{\ast })\le 0$ for $i=1,\dots ,m$ and $h_i(x^{\ast })=0$ for $i=1,\dots ,p$.
2. Dual feasibility: ${\lambda }^{\ast }⪰0$.
3. Complementary slackness: ${\lambda }_i^{\ast }{f}_i(x^{\ast })=0$ for $i=1,\dots ,m$.
4. Stationarity: $x^{\ast }$ is a minimizer of $L(\cdot ,{\lambda }^{\ast },{\nu }^{\ast })$.

Conversely, these four conditions imply optimality of $x^{\ast }$ and $({\lambda }^{\ast },{\nu }^{\ast })$, and strong duality.

If the problem is convex and the functions $f_i$, $h_i$ are differentiable, condition 4 can be written as:

Definition (KKT Conditions for Differentiable Problems)

A point $(x^{\ast },{\lambda }^{\ast },{\nu }^{\ast })$ satisfies the KKT conditions if:

1. Primal feasibility: $g_i(x^{\ast })\le 0,h_j(x^{\ast })=0$
2. Dual feasibility: ${\lambda }_i^{\ast }\ge 0$
3. Complementary slackness: ${\lambda }_i^{\ast }{g}_i(x^{\ast })=0$
4. Stationarity:$$\mathrm{\nabla }f(x^{\ast })+\sum _{i=1}^m{\lambda }_i^{\ast }\mathrm{\nabla }{g}_i(x^{\ast })+\sum _{j=1}^p{\nu }_j^{\ast }\mathrm{\nabla }{h}_j(x^{\ast })=0$$

Role of the KKT Conditions

Theorem (KKT Necessity and Sufficiency)

Necessity: If $x^{\ast }$ is a primal optimal solution and Slater's condition holds, then there exist $({\lambda }^{\ast },{\nu }^{\ast })$ such that $(x^{\ast },{\lambda }^{\ast },{\nu }^{\ast })$ satisfies all KKT conditions.

Sufficiency: If the problem is convex and $(x^{\ast },{\lambda }^{\ast },{\nu }^{\ast })$ satisfies the KKT conditions, then $x^{\ast }$ is a globally optimal solution.

In summary: for a convex problem satisfying Slater's condition,

$$x^{\ast }\text{ is optimal}⟺\mathrm{\exists }{\lambda }^{\ast },{\nu }^{\ast }\text{ satisfying KKT conditions 1–4 (or 1,2,3,4’)}.$$

---

5.9 Dual of Standard Problem Classes

5.9.1 Linear Program (LP) — Standard Form

Primal:

$$\begin{array}{rl}\underset{x}{min}& c^{\mathrm{\top }}x\\ \text{s.t.}& Ax=b,x⪰0.\end{array}$$

Lagrangian: $L(x,\lambda ,\nu )=c^{\mathrm{\top }}x+{\nu }^{\mathrm{\top }}(Ax-b)-{\lambda }^{\mathrm{\top }}x=-b^{\mathrm{\top }}\nu +(c+A^{\mathrm{\top }}\nu -\lambda {)}^{\mathrm{\top }}x.$

Since $L$ is affine in $x$, the dual function is finite only when $c+A^{\mathrm{\top }}\nu -\lambda =0$:

$$g(\lambda ,\nu )=\{\begin{array}{ll}-b^{\mathrm{\top }}\nu ,& A^{\mathrm{\top }}\nu -\lambda +c=0,\\ -\mathrm{\infty },& \text{otherwise.}\end{array}$$

Dual problem:

$$\begin{array}{rl}\underset{\nu }{max}& -b^{\mathrm{\top }}\nu \\ \text{s.t.}& A^{\mathrm{\top }}\nu +c⪰0.\end{array}$$

From Slater's condition: $p^{\ast }=d^{\ast }$ if there exists $\tilde{x}\succ 0$ with $A\tilde{x}=b$. In fact, $p^{\ast }=d^{\ast }$ except when both primal and dual are infeasible.

5.9.2 Linear Program (LP) — Inequality Form

Primal:

$$\begin{array}{rl}\underset{x}{min}& c^{\mathrm{\top }}x\\ \text{s.t.}& Ax⪯b.\end{array}$$

Lagrangian: $L(x,\lambda )=c^{\mathrm{\top }}x+{\lambda }^{\mathrm{\top }}(Ax-b)=(c+A^{\mathrm{\top }}\lambda {)}^{\mathrm{\top }}x-b^{\mathrm{\top }}\lambda ,\lambda ⪰0.$

Dual function: $g(\lambda )=\underset{x}{inf}((c+A^{\mathrm{\top }}\lambda {)}^{\mathrm{\top }}x-b^{\mathrm{\top }}\lambda )=\{\begin{array}{ll}-b^{\mathrm{\top }}\lambda ,& A^{\mathrm{\top }}\lambda +c=0,\\ -\mathrm{\infty },& \text{otherwise.}\end{array}$

Dual problem:

$$\begin{array}{rl}\underset{\lambda }{max}& -b^{\mathrm{\top }}\lambda \\ \text{s.t.}& A^{\mathrm{\top }}\lambda +c=0,\lambda ⪰0.\end{array}$$

From Slater's condition: $p^{\ast }=d^{\ast }$ if $A\tilde{x}\prec b$ for some $\tilde{x}$.

5.9.3 Quadratic Program (QP)

Assume $P\in {\mathbb{S}}_{++}^n$ (positive definite).

Primal:

$$\begin{array}{rl}\underset{x}{min}& x^{\mathrm{\top }}Px\\ \text{s.t.}& Ax⪯b.\end{array}$$

Lagrangian: $L(x,\lambda )=x^{\mathrm{\top }}Px+{\lambda }^{\mathrm{\top }}(Ax-b),\lambda ⪰0.$

Dual function: Minimizing over $x$ (set gradient to zero: $2Px+A^{\mathrm{\top }}\lambda =0⟹x=-\frac{1}{2}{P}^{-1}{A}^{\mathrm{\top }}\lambda$) gives

$$g(\lambda )=-\frac{1}{4}{\lambda }^{\mathrm{\top }}A{P}^{-1}{A}^{\mathrm{\top }}\lambda -b^{\mathrm{\top }}\lambda .$$

Dual problem:

$$\begin{array}{rl}\underset{\lambda }{max}& -\frac{1}{4}{\lambda }^{\mathrm{\top }}A{P}^{-1}{A}^{\mathrm{\top }}\lambda -b^{\mathrm{\top }}\lambda \\ \text{s.t.}& \lambda ⪰0.\end{array}$$

From Slater's condition: $p^{\ast }=d^{\ast }$ if $A\tilde{x}\prec b$ for some $\tilde{x}$. In fact, for QP, $p^{\ast }=d^{\ast }$ always.

5.9.4 Equality-Constrained QP

Primal:

$$\begin{array}{rl}\underset{x}{min}& \frac{1}{2}{x}^{\mathrm{\top }}Qx+c^{\mathrm{\top }}x\\ \text{s.t.}& Ax=b,\end{array}$$

where $Q⪰0$ and $A$ has full row rank ($m\le n$).

KKT system:

$$\left[\begin{array}{cc}Q& A^{\mathrm{\top }}\\ A& 0\end{array}\right]\left[\begin{array}{c}{x}^{\ast }\\ {\nu }^{\ast }\end{array}\right]=\left[\begin{array}{c}-c\\ b\end{array}\right].$$

Since the problem is convex, the KKT solution $(x^{\ast },{\nu }^{\ast })$ is globally optimal.

5.9.5 SDP Connection (Two-Way Partitioning)

Primal (nonconvex):

$$\begin{array}{rl}\underset{x}{min}& x^{\mathrm{\top }}Wx\\ \text{s.t.}& x_i^2=1,i=1,\dots ,n.\end{array}$$

The feasible set is $\{-1,1{\}}^n$ ($2^n$ discrete points). The cost can be written as $x^{\mathrm{\top }}Wx=\sum _i{W}_{ii}+2\sum _{i>j}{W}_{ij}{x}_i{x}_j$, where the cost of assigning $i$ and $j$ to different sets is $-4W_{ij}$.

Lagrangian: $L(x,\nu )=x^{\mathrm{\top }}Wx+\sum _{i=1}^n{\nu }_i(x_i^2-1)=x^{\mathrm{\top }}(W+\mathrm{diag}(\nu ))x-{\mathbf{1}}^{\mathrm{\top }}\nu .$

Dual function:

$$g(\nu )=\{\begin{array}{ll}-{\mathbf{1}}^{\mathrm{\top }}\nu ,& W+\mathrm{diag}(\nu )⪰0,\\ -\mathrm{\infty },& \text{otherwise.}\end{array}$$

Dual problem (SDP):

$$\begin{array}{rl}\underset{\nu }{max}& -{\mathbf{1}}^{\mathrm{\top }}\nu \\ \text{s.t.}& W+\mathrm{diag}(\nu )⪰0.\end{array}$$

Lower bound: $p^{\ast }\ge -{\mathbf{1}}^{\mathrm{\top }}\nu$ if $W+\mathrm{diag}(\nu )⪰0$. For example, choosing $\nu =-{\lambda }_{min}(W)\mathbf{1}$ yields $p^{\ast }\ge n{\lambda }_{min}(W)$.

---

5.10 Geometric Interpretation of Duality

The relationship between the primal and dual problems can be understood geometrically as a min–max exchange. The primal problem minimizes over $x$ the pointwise maximum (over $\lambda \ge 0$) of the Lagrangian; the dual maximizes over $\lambda \ge 0$ the pointwise minimum (over $x$) of the Lagrangian:

$$\underset{d^{\ast }}{\underbrace{\underset{\lambda \ge 0}{max}\underset{x}{min}L(x,\lambda )}}\le \underset{p^{\ast }}{\underbrace{\underset{x}{min}\underset{\lambda \ge 0}{max}L(x,\lambda )}}.$$

The duality gap $p^{\ast }-d^{\ast }\ge 0$ measures the "wedge" between these two saddle-point problems. Strong duality ($p^{\ast }=d^{\ast }$) occurs precisely when a saddle point of $L(x,\lambda )$ exists—i.e., there is a pair $(x^{\ast },{\lambda }^{\ast })$ such that

$$L(x^{\ast },\lambda )\le L(x^{\ast },{\lambda }^{\ast })\le L(x,{\lambda }^{\ast })$$

for all $x$ and $\lambda \ge 0$. This is the essence of the KKT conditions.

Epigraph Interpretation

Define the set

$$\mathcal{A}=\{(u,t)\in {\mathbb{R}}^{m+1}|\mathrm{\exists }x:f_i(x)\le u_i(i=1,\dots ,m),f_0(x)\le t\}.$$

The primal optimal value is $p^{\ast }=inf\{t\mid (0,t)\in \mathcal{A}\}$. The dual problem can be viewed as finding the best affine support (hyperplane) to $\mathcal{A}$ from below, parametrized by $\lambda ⪰0$:

$$g(\lambda )=\underset{(u,t)\in \mathcal{A}}{inf}(t+{\lambda }^{\mathrm{\top }}u).$$

When $\mathcal{A}$ is convex (as in convex problems), supporting hyperplane theorems explain why strong duality tends to hold under mild regularity conditions.

---

5.11 Sensitivity Analysis

Dual variables carry economic meaning: they measure the sensitivity of the optimal value to perturbations in the constraints.

5.11.1 Single Perturbation

Consider perturbing a single inequality constraint $g(x)\le 0$ to $g(x)\le u$:

$$p^{\ast }(u)=\underset{x}{min}\{f(x)\mid g(x)\le u\}.$$

Global Lower Bound

$$p^{\ast }(u)\ge p^{\ast }-{\lambda }^{\ast }u,$$

where ${\lambda }^{\ast }$ is the optimal dual variable for the original ($u=0$) problem, assuming strong duality holds.

• If ${\lambda }^{\ast }$ is large and $u<0$ (tightening the constraint): $p^{\ast }(u)$ increases greatly.
• If ${\lambda }^{\ast }$ is small and $u>0$ (loosening the constraint): $p^{\ast }(u)$ does not decrease much.

Local Sensitivity

$$\frac{d{p}^{\ast }(u)}{du}=-{\lambda }^{\ast }.$$

For small $|u|$, $p^{\ast }(u)\approx p^{\ast }-{\lambda }^{\ast }u$.

Economic interpretation: ${\lambda }^{\ast }$ is the shadow price of the constraint. If the market price for relaxing this resource is less than ${\lambda }^{\ast }$, it pays to buy more. If the price exceeds ${\lambda }^{\ast }$, it is advantageous to sell (violate) the constraint.

5.11.2 General Case (Multiple Perturbations)

Perturb both inequality and equality constraints:

$$\begin{array}{rl}{p}^{\ast }(u,\ell )=\underset{x}{min}& f(x)\\ \text{s.t.}& g_i(x)\le u_i,i=1,\dots ,m,\\ & h_i(x)={\ell }_i,i=1,\dots ,p.\end{array}$$

Global Lower Bound

$$p^{\ast }(u,\ell )\ge q({\lambda }^{\ast },{\nu }^{\ast })-u^{\mathrm{\top }}{\lambda }^{\ast }-{\ell }^{\mathrm{\top }}{\nu }^{\ast }=p^{\ast }(0,0)-u^{\mathrm{\top }}{\lambda }^{\ast }-{\ell }^{\mathrm{\top }}{\nu }^{\ast }.$$

Interpretation of dual variables:

Sign of ${\lambda }_i^{\ast }$, ${\nu }_i^{\ast }$	Effect of perturbation
Large ${\lambda }_i^{\ast }$	$p^{\ast }$ increases greatly if $u_i<0$ (tighten)
Small ${\lambda }_i^{\ast }$	$p^{\ast }$ decreases little if $u_i>0$ (loosen)
Large positive ${\nu }_i^{\ast }$	$p^{\ast }$ increases greatly if ${\ell }_i<0$
Large negative ${\nu }_i^{\ast }$	$p^{\ast }$ increases greatly if ${\ell }_i>0$
Small $	\nu_i^*

Local Sensitivity (General Case)

$$\frac{\partial p^{\ast }(u,\ell )}{\partial u_i}=-{\lambda }_i^{\ast },\frac{\partial p^{\ast }(u,\ell )}{\partial {\ell }_i}=-{\nu }_i^{\ast }.$$

---

5.12 Worked Examples

5.12.1 Least-Norm Solution of Linear Equations

Primal:

$$\begin{array}{rl}\underset{x}{min}& x^{\mathrm{\top }}x\\ \text{s.t.}& Ax=b.\end{array}$$

Lagrangian: $L(x,\nu )=x^{\mathrm{\top }}x+{\nu }^{\mathrm{\top }}(Ax-b).$

Set gradient to zero: ${\mathrm{\nabla }}_{x}L=2x+A^{\mathrm{\top }}\nu =0⟹x=-\frac{1}{2}{A}^{\mathrm{\top }}\nu .$

Plug into $L$:

$$g(\nu )=L(-\frac{1}{2}{A}^{\mathrm{\top }}\nu ,\nu )=-\frac{1}{4}{\nu }^{\mathrm{\top }}A{A}^{\mathrm{\top }}\nu -b^{\mathrm{\top }}\nu .$$

This is a concave function of $\nu$. By the lower bound property:

$$p^{\ast }\ge -\frac{1}{4}{\nu }^{\mathrm{\top }}A{A}^{\mathrm{\top }}\nu -b^{\mathrm{\top }}\nu \text{for all }\nu .$$

5.12.2 Water-Filling (Power Allocation)

Primal (reformulated):

$$\begin{array}{rl}\underset{x}{min}& -\sum _{i=1}^n\ln (x_i+{\alpha }_i)\\ \text{s.t.}& x⪰0,{\mathbf{1}}^{\mathrm{\top }}x=1,\end{array}$$

where ${\alpha }_i>0$.

Lagrangian: $L(x,\lambda ,\nu )=-\sum _i\ln (x_i+{\alpha }_i)-{\lambda }^{\mathrm{\top }}x+\nu ({\mathbf{1}}^{\mathrm{\top }}x-1).$

KKT conditions: $x^{\ast }$ is optimal iff there exist $\lambda \in {\mathbb{R}}^n$, $\nu \in \mathbb{R}$ such that:

1. $x^{\ast }⪰0$, ${\mathbf{1}}^{\mathrm{\top }}{x}^{\ast }=1$
2. $\lambda ⪰0$
3. ${\lambda }_i{x}_i^{\ast }=0$, $i=1,\dots ,n$
4. Stationarity: $-\frac{1}{x_i^{\ast }+{\alpha }_i}-{\lambda }_i+\nu =0$, $i=1,\dots ,n$.

Solution:

• If $\nu \le 1/{\alpha }_i$: ${\lambda }_i=0$ and $x_i^{\ast }=1/\nu -{\alpha }_i$.
• If $\nu \ge 1/{\alpha }_i$: $x_i^{\ast }=0$ and ${\lambda }_i=\nu -1/{\alpha }_i$.

These combine to

$$x_i^{\ast }=max\{0,\frac{1}{\nu }-{\alpha }_i\},{\lambda }_i=max\{0,\nu -\frac{1}{{\alpha }_i}\}.$$

Determine $\nu$ from ${\mathbf{1}}^{\mathrm{\top }}{x}^{\ast }=1$:

$$\sum _{i=1}^{n}max\{0,\frac{1}{\nu }-{\alpha }_i\}=1.$$

Interpretation: Think of $n$ patches at heights ${\alpha }_i$. Flood the area with a unit amount of water. The resulting water level is $1/{\nu }^{\ast }$; patch $i$ receives $x_i^{\ast }$ water.

5.12.3 Projection onto the 1-Norm Ball

Primal:

$$\begin{array}{rl}\underset{x}{min}& \frac{1}{2}\parallel x-a{\parallel }_2^2\\ \text{s.t.}& \parallel x{\parallel }_1\le 1.\end{array}$$

KKT conditions:

1. $\parallel x{\parallel }_1\le 1$
2. $\lambda \ge 0$
3. $\lambda (1-\parallel x{\parallel }_1)=0$
4. $x$ minimizes $L(\tilde{x},\lambda )=\frac{1}{2}\parallel \tilde{x}-a{\parallel }_2^2+\lambda (\parallel \tilde{x}{\parallel }_1-1)=\sum _{k=1}^n(\frac{1}{2}({\tilde{x}}_k-a_k{)}^2+\lambda |{\tilde{x}}_k|)-\lambda .$

The problem is separable. For $\lambda \ge 0$, the minimizer is the soft-thresholding operator:

$$x_k=\{\begin{array}{ll}{a}_k-\lambda ,& a_k\ge \lambda ,\\ 0,& -\lambda \le a_k\le \lambda ,\\ a_k+\lambda ,& a_k\le -\lambda .\end{array}$$

Hence $\parallel x{\parallel }_1=\sum _k|x_k|=\sum _{k}max\{0,|a_k|-\lambda \}.$

• If $\parallel a{\parallel }_1\le 1$, solution is $\lambda =0$, $x=a$.
• Otherwise, solve the piecewise-linear equation in $\lambda$:

$$\sum _{k=1}^{n}max\{0,|a_k|-\lambda \}=1.$$

---

5.13 Summary

Concept	Key Idea
Lagrangian	Weighted sum of objective and constraints
Dual function	Infimum of Lagrangian over primal variables; always concave
Dual problem	Maximize dual function over $\lambda ⪰0$; always convex
Weak duality	$d^{\ast }\le p^{\ast }$ (always holds)
Strong duality	$d^{\ast }=p^{\ast }$ (holds for convex problems under constraint qualifications)
Slater's condition	Existence of a strictly feasible point guarantees strong duality
Complementary slackness	${\lambda }_i^{\ast }{g}_i(x^{\ast })=0$ — at optimum, at least one of ${\lambda }_i$, $g_i(x)$ is zero
KKT conditions	Necessary and sufficient optimality conditions for convex problems under Slater
Sensitivity	$\partial p^{\ast }/\partial u_i=-{\lambda }_i^{\ast }$ — dual variables as shadow prices