Convex Optimization and Lagrangian Duality

Table of Contents

• 1. Convex Sets and Convex Functions
  • 1.1 Convex Sets
  • 1.2 Operations Preserving Convexity of Sets
  • 1.3 Convex Functions
  • 1.4 First-Order and Second-Order Conditions
  • 1.5 Operations Preserving Convexity of Functions
• 2. Convex Optimization Problems
  • 2.1 Standard Form
  • 2.2 Special Cases
  • 2.3 Local Equals Global
• 3. The Lagrangian
  • 3.1 Definition and Lower-Bound Interpretation
  • 3.2 The Dual Function
  • 3.3 Concavity of the Dual Function
• 4. Lagrangian Duality
  • 4.1 The Dual Problem
  • 4.2 Weak Duality
  • 4.3 The Duality Gap
  • 4.4 Strong Duality and Slater’s Condition
• 5. KKT Conditions
  • 5.1 Statement of the Conditions
  • 5.2 Necessity
  • 5.3 Sufficiency
  • 5.4 Geometric Interpretation
• 6. Recovering Primal Solutions from the Dual
  • 6.1 Strong Convexity and Uniqueness
  • 6.2 Dual Decomposition Sketch
  • 6.3 Connection to Click Shaping
• References

1. Convex Sets and Convex Functions 📐

The study of convex optimization begins with the geometry of convex sets and functions. These objects possess structural properties that make optimization problems over them tractable.

1.1 Convex Sets

Definition (Convex Set). A set \(C \subseteq \mathbb{R}^n\) is convex if for every \(x, y \in C\) and every \(\theta \in [0, 1]\), the point \(\theta x + (1 - \theta) y\) belongs to \(C\).

Geometrically, a set is convex if the line segment connecting any two of its points stays entirely within the set. The following are the canonical examples.

Example (Halfspace). Fix \(a \in \mathbb{R}^n \setminus \{0\}\) and \(b \in \mathbb{R}\). The set \(H = \{x \in \mathbb{R}^n : a^\top x \le b\}\) is a halfspace. It is convex: if \(a^\top x \le b\) and \(a^\top y \le b\), then \(a^\top(\theta x + (1-\theta)y) = \theta a^\top x + (1-\theta)a^\top y \le \theta b + (1-\theta)b = b\).

Example (Norm Ball). For any norm \(\|\cdot\|\) on \(\mathbb{R}^n\), the ball \(B(x_c, r) = \{x : \|x - x_c\| \le r\}\) is convex by the triangle inequality.

Example (Polyhedron). A polyhedron is a finite intersection of halfspaces and hyperplanes: \(\mathcal{P} = \{x : Ax \preceq b,\; Cx = d\}\) where \(\preceq\) denotes componentwise inequality. Since each halfspace is convex and intersections of convex sets are convex (see below), polyhedra are convex.

Example (Epigraph). Given \(f : \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}\), its epigraph is \(\operatorname{epi}(f) = \{(x, t) \in \mathbb{R}^n \times \mathbb{R} : f(x) \le t\}\). As we will see, \(f\) is a convex function if and only if \(\operatorname{epi}(f)\) is a convex set.

Figure 2.2 (Boyd & Vandenberghe, 2004): Convex and non-convex sets. Left: the hexagon (including boundary) is convex. Middle: the kidney-shaped set is not convex — the line segment between the two marked points leaves the set. Right: the square with some boundary points missing is not convex. The convex hulls of two sets are shown below.

1.2 Operations Preserving Convexity of Sets

Several operations preserve convexity, making it easy to verify that compound sets are convex without returning to the definition each time.

Proposition (Intersection). An arbitrary intersection of convex sets is convex. If \(C_\alpha\) is convex for every \(\alpha \in \mathcal{A}\), then \(\bigcap_{\alpha \in \mathcal{A}} C_\alpha\) is convex.

Proof. Take \(x, y \in \bigcap_\alpha C_\alpha\). Then \(x, y \in C_\alpha\) for every \(\alpha\), so \(\theta x + (1-\theta)y \in C_\alpha\) for every \(\alpha\), hence \(\theta x + (1-\theta)y \in \bigcap_\alpha C_\alpha\). \(\square\)

Proposition (Affine Image). If \(C\) is convex and \(f(x) = Ax + b\) is an affine map, then \(f(C) = \{Ax + b : x \in C\}\) is convex.

Proposition (Perspective Map). The perspective function \(P : \mathbb{R}^{n+1} \to \mathbb{R}^n\) defined by \(P(x, t) = x/t\) (with \(t > 0\)) maps convex sets to convex sets.

1.3 Convex Functions

Definition (Convex Function). A function \(f : \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}\) with convex domain \(\operatorname{dom}(f) \subseteq \mathbb{R}^n\) is convex if for every \(x, y \in \operatorname{dom}(f)\) and \(\theta \in [0,1]\): \[f(\theta x + (1-\theta)y) \le \theta f(x) + (1-\theta) f(y).\]

The function is strictly convex if the inequality is strict for \(x \ne y\) and \(\theta \in (0,1)\).

Epigraph characterization. \(f\) is convex if and only if \(\operatorname{epi}(f)\) is a convex set. This is immediate from the definitions: the inequality above says exactly that the midpoint on the graph lies at or below the chord, which is the set-theoretic statement that \(\operatorname{epi}(f)\) is convex.

Figure 3.1 (Boyd & Vandenberghe, 2004): Graph of a convex function. The chord (line segment) between any two points \((x, f(x))\) and \((y, f(y))\) on the graph lies above the graph — this is the geometric content of the convexity inequality \(f(\theta x + (1-\theta)y) \le \theta f(x) + (1-\theta)f(y)\).

Figure 3.5 (Boyd & Vandenberghe, 2004): The epigraph of a function \(f\), shown shaded. The lower boundary (shown darker) is the graph of \(f\). The set \(\operatorname{epi}(f)\) is convex if and only if \(f\) is convex.

Definition (Sublevel Set). The \(\alpha\)-sublevel set of \(f\) is \(C_\alpha = \{x \in \operatorname{dom}(f) : f(x) \le \alpha\}\). Every sublevel set of a convex function is convex. (The converse is false: a function with convex sublevel sets need not be convex.) Functions with convex sublevel sets are called quasiconvex.

1.4 First-Order and Second-Order Conditions

These conditions give practical tools for checking convexity without appealing to the definition directly.

Theorem (First-Order Condition). Let \(f\) be differentiable on its (open, convex) domain. Then \(f\) is convex if and only if for all \(x, y \in \operatorname{dom}(f)\): \[f(y) \ge f(x) + \nabla f(x)^\top (y - x).\]

This says the graph of \(f\) lies above every tangent hyperplane — convex functions have globally supporting hyperplanes at every point.

Figure 3.2 (Boyd & Vandenberghe, 2004): Geometric content of the first-order condition. The tangent line (hyperplane) at any point \((x, f(x))\) is a global underestimator of \(f\): the graph of \(f\) lies everywhere above the affine function \(f(x) + \nabla f(x)^\top(y - x)\).

Proof sketch (\(\Rightarrow\)). Fix \(x, y\) and let \(\theta \in (0,1)\). By convexity, \(f(\theta y + (1-\theta)x) \le \theta f(y) + (1-\theta)f(x)\), i.e., \(f(x + \theta(y-x)) \le f(x) + \theta(f(y) - f(x))\). Rearranging and dividing by \(\theta\): \[\frac{f(x + \theta(y-x)) - f(x)}{\theta} \le f(y) - f(x).\] Taking \(\theta \to 0^+\), the left side converges to \(\nabla f(x)^\top(y-x)\). \(\square\)

Proof sketch (\(\Leftarrow\)). For \(x, y \in \operatorname{dom}(f)\) and \(z = \theta x + (1-\theta)y\), apply the tangent inequality at \(z\) to both \(x\) and \(y\), weight by \(\theta\) and \((1-\theta)\) respectively, and add.

Corollary. If \(f\) is convex and \(\nabla f(x) = 0\) at some \(x\), then \(x\) is a global minimum of \(f\).

Theorem (Second-Order Condition). Let \(f\) be twice differentiable on its open, convex domain. Then \(f\) is convex if and only if \(\nabla^2 f(x) \succeq 0\) for all \(x \in \operatorname{dom}(f)\), i.e., the Hessian is positive semidefinite everywhere. If \(\nabla^2 f(x) \succ 0\) everywhere (positive definite), then \(f\) is strictly convex.

Proof sketch. The second-order Taylor expansion \(f(y) = f(x) + \nabla f(x)^\top(y-x) + \frac{1}{2}(y-x)^\top \nabla^2 f(z)(y-x)\) for some \(z\) on the segment \([x,y]\) shows that \(\nabla^2 f \succeq 0\) is exactly the condition that the remainder term is nonnegative, which is equivalent to the first-order condition.

1.5 Operations Preserving Convexity of Functions

Non-negative weighted sum. If \(f_1, \ldots, f_k\) are convex and \(w_i \ge 0\), then \(\sum_i w_i f_i\) is convex.

Composition with affine map. If \(f\) is convex and \(g(x) = Ax + b\), then \(f \circ g\) is convex.

Pointwise maximum. If \(\{f_\alpha\}_{\alpha \in \mathcal{A}}\) are all convex, then \(f(x) = \sup_\alpha f_\alpha(x)\) is convex (with appropriate domain). This is a consequence of the epigraph being the intersection \(\bigcap_\alpha \operatorname{epi}(f_\alpha)\).

Pointwise infimum. Crucially for duality: \(g(y) = \inf_x f(x, y)\) is convex in \(y\) if \(f(x, y)\) is jointly convex in \((x, y)\). We will use this in Section 3.3 when showing the dual function is concave.

2. Convex Optimization Problems 🔑

2.1 Standard Form

Definition (Convex Optimization Problem, Standard Form). A convex optimization problem in standard form is: \[\begin{aligned} \text{minimize} \quad & f_0(x) \\ \text{subject to} \quad & f_i(x) \le 0, \quad i = 1, \ldots, m \\ & h_j(x) = 0, \quad j = 1, \ldots, p \end{aligned}\] where \(x \in \mathbb{R}^n\) is the optimization variable, \(f_0, f_1, \ldots, f_m : \mathbb{R}^n \to \mathbb{R}\) are convex functions, and \(h_1, \ldots, h_p : \mathbb{R}^n \to \mathbb{R}\) are affine functions \(h_j(x) = a_j^\top x - b_j\).

The requirement that equality constraints are affine is not merely a convention: a convex equality constraint \(h(x) = 0\) with \(h\) nonlinear forces \(x\) to a point (the constraint set \(\{h = 0\} \cap \{h \ge 0\} = \{h = 0, h \le 0\}\) collapses) and is never convex unless \(h\) is affine.

The feasible set is \(\mathcal{F} = \{x : f_i(x) \le 0,\; h_j(x) = 0\;\forall\,i,j\}\). By Exercise 1, \(\mathcal{F}\) is convex. The optimal value is \(p^* = \inf_{x \in \mathcal{F}} f_0(x)\).

2.2 Special Cases

Many problems encountered in machine learning and information retrieval are convex problems in disguise. 💡

Linear Program (LP). \(f_0(x) = c^\top x\), \(f_i(x) = a_i^\top x - b_i\), \(h_j(x) = e_j^\top x - d_j\). All functions are affine, and the feasible set is a polyhedron.

Quadratic Program (QP). \(f_0(x) = \frac{1}{2}x^\top P x + q^\top x + r\) with \(P \succeq 0\), and affine inequality and equality constraints.

Second-Order Cone Program (SOCP). The constraint \(\|Ax + b\|_2 \le c^\top x + d\) defines a second-order cone (also called an ice-cream cone or Lorentz cone). SOCPs include LPs and QPs as special cases.

Recommendation as a Constrained QP. In the motivating paper by Agarwal et al. (SIGIR 2012), the click-shaping problem has the form: maximize an expected click objective (a linear or quadratic function of an allocation vector) subject to constraints enforcing minimum engagement on certain content categories. When the click model uses a regularized log-likelihood or Gaussian prior, the objective becomes a convex quadratic, and the whole problem is a QP admitting strong duality.

2.3 Local Equals Global

The most important property of convex optimization is that every local minimum is a global minimum.

Theorem. Let \(f_0\) be convex and \(\mathcal{F}\) be the (convex) feasible set of a convex optimization problem. If \(x^*\) is a local minimum — there exists \(\delta > 0\) such that \(f_0(x^*) \le f_0(y)\) for all feasible \(y\) with \(\|y - x^*\| \le \delta\) — then \(x^*\) is a global minimum.

Proof. Suppose for contradiction that some feasible \(z\) satisfies \(f_0(z) < f_0(x^*)\). Consider the point \(y_\theta = \theta z + (1-\theta)x^*\) for \(\theta \in (0,1)\). Since \(\mathcal{F}\) is convex, \(y_\theta\) is feasible. By convexity of \(f_0\): \[f_0(y_\theta) \le \theta f_0(z) + (1-\theta)f_0(x^*) < \theta f_0(x^*) + (1-\theta)f_0(x^*) = f_0(x^*).\] For sufficiently small \(\theta\), \(\|y_\theta - x^*\| = \theta\|z - x^*\| < \delta\), contradicting local optimality of \(x^*\). \(\square\)

Corollary. If \(f_0\) is strictly convex, the global minimum is unique.

3. The Lagrangian 📐

The Lagrangian is the central object of convex duality. It relaxes the constrained problem into an unconstrained one by “pricing” constraint violations.

3.1 Definition and Lower-Bound Interpretation

Consider the standard form problem from Section 2.1. Introduce dual variables (also called Lagrange multipliers): \(\lambda = (\lambda_1, \ldots, \lambda_m) \in \mathbb{R}^m\) for the inequality constraints and \(\nu = (\nu_1, \ldots, \nu_p) \in \mathbb{R}^p\) for the equality constraints.

Definition (Lagrangian). The Lagrangian \(L : \mathbb{R}^n \times \mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R}\) is: \[L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{j=1}^p \nu_j h_j(x).\]

The variables \((\lambda, \nu)\) are called dual variables; the vector \(\lambda\) must satisfy \(\lambda \succeq 0\) (componentwise) to retain the lower-bound property. The variable \(x\) is the primal variable.

Key observation: lower bound for feasible \(x\). Fix any \(\lambda \succeq 0\) and any \(\nu\). For any feasible point \(\tilde{x}\) (i.e., \(f_i(\tilde{x}) \le 0\) and \(h_j(\tilde{x}) = 0\)): \[L(\tilde{x}, \lambda, \nu) = f_0(\tilde{x}) + \underbrace{\sum_i \lambda_i f_i(\tilde{x})}_{\le 0} + \underbrace{\sum_j \nu_j h_j(\tilde{x})}_{= 0} \le f_0(\tilde{x}).\] So \(L(\tilde{x}, \lambda, \nu) \le f_0(\tilde{x})\) for any feasible \(\tilde{x}\) and any \(\lambda \succeq 0\). This is the lower-bound property that drives the entire duality theory.

3.2 The Dual Function

Definition (Lagrange Dual Function). The Lagrange dual function \(g : \mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R} \cup \{-\infty\}\) is: \[g(\lambda, \nu) = \inf_{x \in \mathcal{D}} L(x, \lambda, \nu) = \inf_{x \in \mathcal{D}} \left\{ f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{j=1}^p \nu_j h_j(x) \right\}\] where \(\mathcal{D} = \operatorname{dom}(f_0) \cap \bigcap_i \operatorname{dom}(f_i)\) is the natural domain of the problem.

Note that the infimum is taken over all \(x \in \mathcal{D}\), not just feasible \(x\). This is the Lagrangian relaxation: we drop the constraints and instead penalize violations.

Claim. For any \(\lambda \succeq 0\) and any \(\nu\): \(g(\lambda, \nu) \le p^*\).

Proof. Let \(x^*\) be any optimal point (if none exists, \(p^* = \inf_{x\in\mathcal{F}} f_0(x)\) and the argument applies to any sequence approaching it). Then: \[g(\lambda, \nu) = \inf_{x \in \mathcal{D}} L(x, \lambda, \nu) \le L(x^*, \lambda, \nu) \le f_0(x^*) = p^*\] where the second inequality uses the lower-bound property from Section 3.1. \(\square\)

So the dual function provides a certificate that \(p^*\) is at least \(g(\lambda, \nu)\).

3.3 Concavity of the Dual Function

The dual function is always concave in \((\lambda, \nu)\), regardless of whether the original problem is convex.

Theorem. \(g(\lambda, \nu) = \inf_x L(x, \lambda, \nu)\) is a concave function of \((\lambda, \nu)\) on \(\{(\lambda,\nu) : g(\lambda,\nu) > -\infty\}\).

Proof. Fix \(x \in \mathcal{D}\). The function \((\lambda, \nu) \mapsto L(x, \lambda, \nu) = f_0(x) + \sum_i \lambda_i f_i(x) + \sum_j \nu_j h_j(x)\) is affine (hence concave) in \((\lambda, \nu)\). The dual function \(g(\lambda, \nu) = \inf_x L(x, \lambda, \nu)\) is a pointwise infimum of affine (hence concave) functions, and pointwise infima of concave functions are concave. \(\square\)

This is a fundamental structural fact: the dual function is always concave and the dual problem (Section 4.1) is always convex, even when the primal is not. This means we can apply all the machinery of convex optimization to the dual.

4. Lagrangian Duality 🔑

4.1 The Dual Problem

The dual function provides a lower bound on \(p^*\) for every \(\lambda \succeq 0\) and \(\nu\). We naturally want the best lower bound, i.e., the largest value of \(g\).

Definition (Lagrange Dual Problem). The Lagrange dual problem is: \[\begin{aligned} \text{maximize} \quad & g(\lambda, \nu) \\ \text{subject to} \quad & \lambda \succeq 0. \end{aligned}\]

The optimal value of the dual problem is \(d^* = \sup_{\lambda \succeq 0, \nu} g(\lambda, \nu)\).

Since \(g\) is concave and \(\lambda \succeq 0\) defines a convex constraint, the dual problem is a convex optimization problem — even when the primal is not. The dual variables \((\lambda, \nu)\) are called dual feasible if \(\lambda \succeq 0\) (and \(g(\lambda,\nu) > -\infty\)). A pair \((\lambda^*, \nu^*)\) is dual optimal if it achieves \(d^*\).

4.2 Weak Duality

Theorem (Weak Duality). Always \(d^* \le p^*\).

Proof. For any \(\lambda \succeq 0\), any \(\nu\), and any feasible \(\tilde{x}\): \[g(\lambda, \nu) \le L(\tilde{x}, \lambda, \nu) \le f_0(\tilde{x}).\] The first inequality holds because \(g\) is an infimum. The second holds because \(f_i(\tilde{x}) \le 0\), \(h_j(\tilde{x}) = 0\), and \(\lambda \succeq 0\), so the extra terms in \(L\) are non-positive. Taking the infimum over feasible \(\tilde{x}\) on the right gives \(g(\lambda, \nu) \le p^*\). Since this holds for all dual-feasible \((\lambda, \nu)\), taking the supremum over dual-feasible points on the left gives \(d^* \le p^*\). \(\square\)

Figure 5.3 (Boyd & Vandenberghe, 2004): Geometric interpretation of weak duality. The set \(\mathcal{G} = \{(f_1(x), f_0(x)) : x \in \mathcal{D}\}\) is shown. The dual function value \(g(\lambda)\) equals the \(t\)-intercept of the supporting hyperplane \(\lambda u + t = g(\lambda)\) with slope \(-\lambda\). The hyperplane always lies at or below \(p^*\) (the infimum of \(t\) over \(u \le 0\)), establishing \(g(\lambda) \le p^*\).

Corollary (Certificate of Suboptimality). If \(\tilde{x}\) is primal feasible and \((\tilde{\lambda}, \tilde{\nu})\) is dual feasible, then: \[f_0(\tilde{x}) - p^* \le f_0(\tilde{x}) - g(\tilde{\lambda}, \tilde{\nu}).\] The right-hand side is computable without knowing \(p^*\) and provides an upper bound on how suboptimal \(\tilde{x}\) is. In practice, optimization algorithms use this duality gap as a stopping criterion.

4.3 The Duality Gap

Definition (Duality Gap). The duality gap is \(p^* - d^* \ge 0\).

When the duality gap is zero (\(p^* = d^*\)), the dual provides exactly as tight a lower bound as possible. This is strong duality, and it is the condition that makes the dual problem useful for computing primal solutions.

The duality gap has a beautiful geometric interpretation. Consider the set: \[\mathcal{G} = \{(u, t) \in \mathbb{R}^m \times \mathbb{R} : \exists x \in \mathcal{D},\; f_i(x) \le u_i\;\forall i,\; f_0(x) \le t\}\] (ignoring equality constraints for simplicity). The optimal value \(p^*\) is the infimum of \(t\) over points in \(\mathcal{G}\) with \(u \preceq 0\). The dual function value \(g(\lambda)\) is \(-\lambda^\top u^* + (p^* \text{ contribution})\), corresponding to a supporting hyperplane to \(\mathcal{G}\) at the point \((0, p^*)\). Strong duality holds when there is a non-vertical supporting hyperplane at \((0, p^*)\), which is guaranteed by Slater’s condition.

Figure 5.4 (Boyd & Vandenberghe, 2004): The duality gap when strong duality fails. Three supporting hyperplanes (for dual values \(\lambda_1, \lambda^*, \lambda_2\)) are shown tangent to \(\mathcal{G}\). The best dual lower bound \(d^*\) is achieved at \(\lambda^*\), but \(d^* < p^*\) — the hyperplane at \(\lambda^*\) cannot be made to pass through \((0, p^*)\) without becoming vertical. This illustrates why strong duality requires Slater’s condition.

4.4 Strong Duality and Slater’s Condition

Theorem (Slater’s Condition implies Strong Duality). Suppose the primal problem is convex (\(f_0, f_1, \ldots, f_m\) are convex, \(h_j\) are affine). If there exists a point \(\tilde{x} \in \operatorname{relint}(\mathcal{D})\) such that: \[f_i(\tilde{x}) < 0 \text{ for all } i = 1, \ldots, m, \quad \text{and} \quad h_j(\tilde{x}) = 0 \text{ for all } j = 1, \ldots, p,\] then strong duality holds: \(d^* = p^*\), and the dual optimal value is attained (there exists \((\lambda^*, \nu^*)\) with \(g(\lambda^*, \nu^*) = d^*\)).

Such a point \(\tilde{x}\) is called Slater feasible or strictly feasible.

Proof sketch (via supporting hyperplane theorem). The proof proceeds by showing the set \(\mathcal{G}\) (defined in Section 4.3) is a convex set, and \((0, p^*)\) is a boundary point. The supporting hyperplane theorem guarantees a supporting hyperplane at \((0, p^*)\). Slater’s condition rules out a vertical supporting hyperplane (which would give no useful dual), so the hyperplane has the form \(\{(u, t) : \lambda^\top u + t \ge p^*\}\) for some \(\lambda \succeq 0\), \(\mu > 0\). Normalizing \(\mu = 1\) and unpacking gives \(g(\lambda, \nu) = p^*\) for some \(\nu\). \(\square\)

Figure 5.6 (Boyd & Vandenberghe, 2004): Geometric proof of strong duality under Slater’s condition. The convex set \(\mathcal{A}\) (shaded) and the vertical segment \(\mathcal{B}\) (below \((0, p^*)\)) are disjoint and can be separated by a hyperplane. Slater’s condition guarantees this separating hyperplane is non-vertical — it must pass to the left of the strictly feasible point \((\tilde{u}, \tilde{t}) = (f_1(\tilde{x}), f_0(\tilde{x}))\) with \(\tilde{u} < 0\) — yielding a dual certificate with \(g(\lambda^*, \nu^*) = p^*\).

5. KKT Conditions 🔑

The Karush-Kuhn-Tucker (KKT) conditions are the central optimality conditions for constrained optimization. For convex problems satisfying Slater’s condition, they are both necessary and sufficient.

5.1 Statement of the Conditions

Definition (KKT Conditions). Let \(x^*\) be a primal point and \((\lambda^*, \nu^*)\) a dual point. The four KKT conditions are:

1. Primal feasibility: \(f_i(x^*) \le 0\) for all \(i\); \(h_j(x^*) = 0\) for all \(j\).

2. Dual feasibility: \(\lambda_i^* \ge 0\) for all \(i\).

3. Complementary slackness: \(\lambda_i^* f_i(x^*) = 0\) for all \(i\).

4. Stationarity: \(\nabla f_0(x^*) + \sum_{i=1}^m \lambda_i^* \nabla f_i(x^*) + \sum_{j=1}^p \nu_j^* \nabla h_j(x^*) = 0\).

Complementary slackness says: either constraint \(i\) is active (\(f_i(x^*) = 0\)) or its multiplier is zero (\(\lambda_i^* = 0\)). Both can be zero; what is excluded is \(\lambda_i^* > 0\) with \(f_i(x^*) < 0\).

5.2 Necessity

Theorem (Necessity of KKT). Suppose strong duality holds (e.g., the problem is convex and Slater’s condition is satisfied), and suppose \(x^*\) is primal optimal and \((\lambda^*, \nu^*)\) is dual optimal, and \(f_0, f_1, \ldots, f_m, h_1, \ldots, h_p\) are all differentiable. Then \(x^*\) and \((\lambda^*, \nu^*)\) satisfy the four KKT conditions.

Proof. Primal and dual feasibility hold by assumption. It remains to derive stationarity and complementary slackness from \(p^* = d^*\).

Since \(x^*\) is optimal and \((\lambda^*, \nu^*)\) is dual optimal: \[f_0(x^*) = p^* = d^* = g(\lambda^*, \nu^*) = \inf_x L(x, \lambda^*, \nu^*) \le L(x^*, \lambda^*, \nu^*).\] But also by primal feasibility and \(\lambda^* \succeq 0\): \[L(x^*, \lambda^*, \nu^*) = f_0(x^*) + \underbrace{\sum_i \lambda_i^* f_i(x^*)}_{\le 0} + \underbrace{\sum_j \nu_j^* h_j(x^*)}_{= 0} \le f_0(x^*).\] Combining: \(f_0(x^*) \le L(x^*, \lambda^*, \nu^*) \le f_0(x^*)\), so \(L(x^*, \lambda^*, \nu^*) = f_0(x^*)\). This forces: \[\sum_i \lambda_i^* f_i(x^*) = 0.\] Since \(\lambda_i^* \ge 0\) and \(f_i(x^*) \le 0\) for each \(i\), each term is non-positive; the sum is zero only if each term is zero. Hence \(\lambda_i^* f_i(x^*) = 0\) for all \(i\) — complementary slackness.

Moreover, the chain of equalities shows \(x^*\) minimizes \(L(\cdot, \lambda^*, \nu^*)\) over \(\mathcal{D}\). Since \(L(\cdot, \lambda^*, \nu^*)\) is differentiable, its minimizer satisfies \(\nabla_x L(x^*, \lambda^*, \nu^*) = 0\) — stationarity. \(\square\)

5.3 Sufficiency

Theorem (Sufficiency of KKT for Convex Problems). Suppose \(f_0, f_1, \ldots, f_m\) are convex and \(h_1, \ldots, h_p\) are affine. If \(\tilde{x}\) and \((\tilde{\lambda}, \tilde{\nu})\) satisfy all four KKT conditions, then \(\tilde{x}\) is primal optimal and \((\tilde{\lambda}, \tilde{\nu})\) is dual optimal, with zero duality gap.

Proof. By stationarity, \(\tilde{x}\) minimizes \(L(\cdot, \tilde{\lambda}, \tilde{\nu})\), so \(g(\tilde{\lambda}, \tilde{\nu}) = L(\tilde{x}, \tilde{\lambda}, \tilde{\nu})\). By complementary slackness and primal feasibility: \[g(\tilde{\lambda}, \tilde{\nu}) = L(\tilde{x}, \tilde{\lambda}, \tilde{\nu}) = f_0(\tilde{x}) + \underbrace{\sum_i \tilde{\lambda}_i f_i(\tilde{x})}_{=0} + \underbrace{\sum_j \tilde{\nu}_j h_j(\tilde{x})}_{=0} = f_0(\tilde{x}).\] Thus \(f_0(\tilde{x}) = g(\tilde{\lambda}, \tilde{\nu}) \le d^* \le p^* \le f_0(\tilde{x})\), where the last inequality uses primal feasibility of \(\tilde{x}\). All inequalities are equalities, so \(\tilde{x}\) is primal optimal, \((\tilde{\lambda}, \tilde{\nu})\) is dual optimal, and \(p^* = d^*\). \(\square\)

5.4 Geometric Interpretation

The stationarity condition \(\nabla f_0(x^*) = -\sum_i \lambda_i^* \nabla f_i(x^*) - \sum_j \nu_j^* \nabla h_j(x^*)\) has a clear geometric meaning: the negative gradient of the objective (the direction of steepest descent) must lie in the cone spanned by the gradients of the active constraints.

Intuitively: at the optimum, every direction that decreases \(f_0\) also increases some active constraint \(f_i\) (i.e., moves outside the feasible set). The multipliers \(\lambda_i^*\) quantify how much the active constraints resist the descent direction.

Complementary slackness encodes which constraints are “binding”: inactive constraints (\(f_i(x^*) < 0\)) have zero multiplier, meaning they are not contributing to the balance of forces.

6. Recovering Primal Solutions from the Dual 💡

This section addresses the operational question: given a dual optimal \((\lambda^*, \nu^*)\), how do we find the corresponding primal optimal \(x^*\)? This is the key step in the click-shaping algorithm of Agarwal et al.

6.1 Strong Convexity and Uniqueness

If we know \((\lambda^*, \nu^*)\), the stationarity condition tells us \(x^*\) minimizes \(L(\cdot, \lambda^*, \nu^*)\). But what if this Lagrangian has multiple minimizers? The following result resolves this.

Theorem (Primal Recovery via Strong Convexity). Suppose strong duality holds and \((\lambda^*, \nu^*)\) is dual optimal. If \(L(\cdot, \lambda^*, \nu^*)\) is \(\mu\)-strongly convex in \(x\) for some \(\mu > 0\), then \(L(\cdot, \lambda^*, \nu^*)\) has a unique minimizer \(x^*\), and this \(x^*\) is the unique primal optimal solution.

Proof. Since \(L(\cdot, \lambda^*, \nu^*)\) is \(\mu\)-strongly convex, it has a unique minimizer \(\hat{x}\) (this follows from strong convexity: any two minimizers \(\hat{x}_1, \hat{x}_2\) satisfy \(L(\frac{\hat{x}_1 + \hat{x}_2}{2}, \lambda^*, \nu^*) < \frac{1}{2}L(\hat{x}_1, \lambda^*, \nu^*) + \frac{1}{2}L(\hat{x}_2, \lambda^*, \nu^*)\), contradicting both being minimizers). We have: \[f_0(\hat{x}) + \underbrace{\sum_i \lambda_i^* f_i(\hat{x})}_{\ge 0 \text{ (sign unclear)}} + \underbrace{\sum_j \nu_j^* h_j(\hat{x})}_{= 0\text{ (if feasible)}} = g(\lambda^*, \nu^*) = p^*.\] The necessity proof in Section 5.2 established that any primal optimal \(x^*\) must satisfy \(L(x^*, \lambda^*, \nu^*) = p^* = g(\lambda^*, \nu^*)\), i.e., \(x^*\) also minimizes \(L(\cdot, \lambda^*, \nu^*)\). By uniqueness of the minimizer, \(x^* = \hat{x}\). \(\square\)

6.2 Dual Decomposition Sketch

Dual decomposition is a method for solving the dual problem that simultaneously produces a primal solution. It is particularly useful when the primal problem decomposes across a sum structure.

Suppose the objective and constraints separate across user groups: \(f_0(x) = \sum_k f_0^{(k)}(x^{(k)})\), \(f_i(x) = \sum_k f_i^{(k)}(x^{(k)})\), where \(x = (x^{(1)}, \ldots, x^{(K)})\) are disjoint blocks. Then: \[L(x, \lambda, \nu) = \sum_k \left[ f_0^{(k)}(x^{(k)}) + \sum_i \lambda_i f_i^{(k)}(x^{(k)}) + \sum_j \nu_j h_j^{(k)}(x^{(k)}) \right] = \sum_k L^{(k)}(x^{(k)}, \lambda, \nu).\]

The infimum over \(x\) decomposes into independent sub-problems: \[g(\lambda, \nu) = \sum_k \inf_{x^{(k)}} L^{(k)}(x^{(k)}, \lambda, \nu).\]

The dual decomposition algorithm alternates between: 1. Primal step: for each \(k\) in parallel, compute \(x^{(k)}(\lambda, \nu) = \arg\min_{x^{(k)}} L^{(k)}(x^{(k)}, \lambda, \nu)\). 2. Dual step: update \(\lambda\) by gradient ascent on \(g\): \(\lambda \leftarrow [\lambda + \alpha \nabla_\lambda g(\lambda, \nu)]_+\), where \([\cdot]_+\) denotes projection onto \(\lambda \succeq 0\) and \(\alpha > 0\) is a step size.

By Exercise 14, \(\nabla_{\lambda_i} g = \sum_k f_i^{(k)}(x^{(k)}(\lambda, \nu)) = f_i(x(\lambda, \nu))\) — the total constraint violation.

def dual_decomposition(subproblem_solvers, f_constraints, lambda_init, nu_init,
                       step_size, n_iterations):
    """
    Dual decomposition for a separable convex problem.

    Args:
        subproblem_solvers: list of callables, each taking (lambda_, nu) and
                            returning x_k minimizing L^(k)(x_k, lambda_, nu)
        f_constraints: callable taking x (concatenated) and returning
                       vector of constraint function values f_i(x)
        lambda_init: initial dual vector (shape: [m])
        nu_init: initial equality dual vector (shape: [p])
        step_size: positive float, gradient ascent step size
        n_iterations: number of dual ascent iterations
    Returns:
        lambda_opt, nu_opt, x_opt
    """
    import numpy as np
    lambda_ = lambda_init.copy()
    nu_ = nu_init.copy()

    for t in range(n_iterations):
        # Primal step: solve each sub-problem independently
        x_blocks = [solver(lambda_, nu_) for solver in subproblem_solvers]
        x = np.concatenate(x_blocks)

        # Dual gradient: constraint residuals
        constraint_vals = f_constraints(x)         # shape: [m]

        # Dual step: gradient ascent on g, project to lambda >= 0
        lambda_ = np.maximum(lambda_ + step_size * constraint_vals, 0.0)
        # Note: nu_ update for equality constraints (no projection needed)
        # nu_ += step_size * h_constraints(x)

    return lambda_, nu_, x

6.3 Connection to Click Shaping

We now make the connection to Agarwal et al. (SIGIR 2012) explicit. The paper considers a personalized recommendation problem with the following structure.

Problem setup. There is a set of items (news articles, ads) to be recommended to users. Each user \(u\) can be assigned a recommendation allocation \(x_u \in \Delta\) (a probability distribution over items, or a scoring vector). The objectives are: - Maximize total expected clicks: \(\sum_u f_0^{(u)}(x_u)\) (concave, since click models are log-concave in item scores). - Subject to minimum engagement constraints on content categories: \(\sum_u g_k^{(u)}(x_u) \ge b_k\) for each category \(k\).

This is a concave maximization problem (equivalently, a convex minimization problem with \(-f_0\)) with convex constraints. The Lagrangian is: \[L(x, \lambda) = -\sum_u f_0^{(u)}(x_u) + \sum_k \lambda_k \left(b_k - \sum_u g_k^{(u)}(x_u)\right)\] where \(\lambda_k \ge 0\) is the dual variable for category \(k\)’s engagement constraint.

Decomposition. The Lagrangian decomposes over users: \[L(x, \lambda) = \sum_u \left[-f_0^{(u)}(x_u) - \sum_k \lambda_k g_k^{(u)}(x_u)\right] + \sum_k \lambda_k b_k.\]

For fixed \(\lambda\), each user’s sub-problem is independent: \[x_u^*(\lambda) = \arg\max_{x_u \in \Delta} \left[f_0^{(u)}(x_u) + \sum_k \lambda_k g_k^{(u)}(x_u)\right].\]

Interpretation of dual variables. Each \(\lambda_k\) is the price of category \(k\) engagement. A higher \(\lambda_k\) means the algorithm is willing to sacrifice more total clicks to meet category \(k\)’s engagement quota. The personalized recommendation for user \(u\) at optimality is the item allocation that maximizes the \(\lambda\)-weighted combination of click likelihood and category engagement.

Primal recovery. The paper exploits strong convexity (from regularization of the click model, e.g., a Gaussian prior on item scores) to guarantee that the Lagrangian has a unique minimizer for each \(\lambda\). The algorithm is: 1. Solve the dual problem \(\max_{\lambda \succeq 0} g(\lambda)\) using gradient ascent on \(\lambda\). 2. At each gradient step, solve each user’s sub-problem to get \(x_u(\lambda)\) — this is efficient since it decomposes by user. 3. At convergence to \(\lambda^*\), set \(x_u^* = x_u(\lambda^*)\) — this is the primal optimal allocation.

The KKT conditions say: at optimality, \(\lambda_k^* > 0\) only if category \(k\)’s constraint is active (binding), and \(\lambda_k^* = 0\) if the system naturally meets category \(k\)’s quota without any price incentive.

Key result from Agarwal et al. The strong convexity of the per-user click models (from regularization) ensures the dual function is smooth, gradient ascent converges at a linear rate, and the mapping \(\lambda \mapsto x_u(\lambda)\) is continuous — enabling efficient online serving: the optimal personalized recommendation is computed by solving the small per-user argmax at the stored \(\lambda^*\), without re-solving the full global problem.

import numpy as np
import matplotlib.pyplot as plt

rng = np.random.default_rng(42)
n, m = 10, 5
A = rng.standard_normal((m, n))
b = A @ np.ones(n)
c = rng.standard_normal(n)

def primal_solve(lam):
    return c - A.T @ lam

def primal_obj(x):
    return 0.5 * x @ x - c @ x

def dual_fn(lam):
    x = primal_solve(lam)
    return primal_obj(x) - lam @ (A @ x - b)

lam = np.zeros(m)
alpha = 0.01
gaps = []

for _ in range(200):
    x = primal_solve(lam)
    grad = A @ x - b          # constraint residuals
    lam = np.maximum(lam - alpha * grad, 0.0)  # projected ascent: max lam

    # duality gap = primal_obj(x_feas) - dual_fn(lam)
    # use x from argmin L, which may be infeasible; gap is approximate
    gaps.append(primal_obj(x) - dual_fn(lam))

plt.plot(gaps)
plt.xlabel("Iteration")
plt.ylabel("Duality gap (approx)")
plt.title("Dual gradient ascent convergence")
plt.show()

References