18. Convex Analysis

Chapter PDF · Complete book

We write $f(x)$ for the objective and $x$ for the variable to be optimized. The main references are [13, 4].

18.1 Basics of Convex Analysis¶

We consider minimization problems of the form

over the finite-dimensional Hilbert space $\mathcal{H}\mathrel{:=}\mathbb{R}^N$, with the canonical inner product $\langle \cdot,\,\cdot\rangle$.

Many of these results extend to infinite-dimensional Hilbert spaces, with additional hypotheses where compactness is used.

The objective $f : \mathcal{H}\longrightarrow \bar{\mathbb{R}}\mathrel{:=}\mathbb{R}\cup \{+\infty\}$ is convex. Allowing $f$ to take the value $+\infty$ encodes constraints directly in the objective; its effective domain is

For a set $\mathcal{C}\subset \mathcal{H}$, define the indicator function

18.1.1 Convex Sets and Functions¶

A set $\Omega\subset \mathcal{H}$ is convex if

A function is convex if

Equivalently, its epigraph $\left\{ (x,r) \in \mathcal{H}\times \mathbb{R} \;;\; r \geqslant f(x) \right\}$ is convex. The inequality is interpreted in the extended real line $\bar{\mathbb{R}}$, with the convention $0\cdot(+\infty)=0$ at the endpoints $t=0,1$.

The function $f$ is strictly convex if the inequality in (18.2) is strict whenever $x,y\in\mathop{\mathrm{dom}}(f)$ are distinct and $0<t<1$.

A set $\Omega$ is convex if and only if $\iota_{\Omega}$ is a convex function.

Throughout the chapter, convex functions $f$ are assumed proper, meaning $\mathop{\mathrm{dom}}(f) \neq \emptyset$, and lower semicontinuous (lsc), meaning that for every $x \in \mathcal{H}$,

For a convex function, lower semicontinuity is equivalent to the epigraph $\mathop{\mathrm{epi}}(f)$ being closed.

We denote by $\Gamma_0(\mathcal{H})$ the set of proper convex lsc functions.

18.1.2 First-Order Conditions¶

Existence of minimizers.

We first address existence. Lower semicontinuity and coercivity provide a useful sufficient condition.

This compactness argument is known as the direct method in the calculus of variations.

For $f$ in $\Gamma_0(\mathcal{H})$, the minimizer set $\mathop{\mathrm{argmin}}f$ is closed and convex, and every local minimizer is global. Strict convexity of $f$ implies that there is at most one minimizer.

Subdifferential.

The subdifferential at $x$ of $f$ is

We set $\partial f(x)=\emptyset$ outside $\mathop{\mathrm{dom}}(f)$. Here $\mathcal{H}^*=\mathbb{R}^N$ denotes the space of dual vectors. The inner product identifies the dual space with $\mathcal{H}$, but distinguishing primal and dual variables remains useful. The duality pairing itself is canonical; the identification of a linear functional with a vector depends on the inner product.

The subdifferential $\partial f(x)$ consists of the slopes $u$ of supporting affine functions $f(x) + \langle u,\,z-x\rangle$ that lie below $f$.

At an interior point of $\mathop{\mathrm{dom}}(f)$, the function $f$ is differentiable exactly when its subdifferential consists of the gradient alone:

Multiple elements of $\partial f(x)$ indicate distinct supporting slopes of $f$ at $x$.

The subdifferential can also be empty at a boundary point of the effective domain. For example, $f(x)=-\sqrt{1-x^2}$ on $[-1,1]$, extended by $+\infty$ outside this interval, has no subgradient at $x=\pm1$.

Since $\partial f(x) \subset \mathcal{H}^*$ is an intersection of half-spaces, it is a closed convex set.

Thus $\partial f : \mathcal{H}\mapsto 2^{\mathcal{H}^*}$ is a set-valued operator, also written $\partial f : \mathcal{H}\hookrightarrow \mathcal{H}^*$.

For the absolute value $f(x)=|x|$, write $\partial f(x) = \partial |\cdot|(x)$. Its subdifferential is

First-order conditions.

The subdifferential gives a necessary and sufficient optimality condition.

Subdifferential calculus.

Calculus rules simplify subdifferential computations. For a separable function $f(x_1,\ldots,x_K)=\sum_{k=1}^K f_k(x_k)$, the subdifferential is the Cartesian product

Applying this rule to the $\ell^1$ norm $|\!| x |\!|_1=\sum_{k=1}^N |x_k|$ gives

a hyperrectangle. With $I = \mathop{\mathrm{supp}}(x)$, the condition $u \in \partial |\!| \cdot |\!|_1(x)$ is equivalent to

A sum rule requires a domain qualification. If one function is finite and continuous at a point in the domain of the other, then for every $x\in\mathop{\mathrm{dom}}(f)\cap\mathop{\mathrm{dom}}(g)$,

where $\oplus$ denotes the Minkowski sum. In particular, if $f$ is differentiable at $x$, then

Positive scaling gives

General compositions need not preserve convexity, so no unrestricted chain rule is available.

Composition with a linear map does preserve convexity. For $A \in \mathbb{R}^{P \times N}$ and $f \in \Gamma_0(\mathbb{R}^P)$, assume $\mathop{\mathrm{Im}}(A)\cap\mathop{\mathrm{relint}}(\mathop{\mathrm{dom}}(f))\neq\emptyset$. Then $f \circ A \in \Gamma_0(\mathbb{R}^N)$ and

Normal cone.

For a nonempty closed convex set $\mathcal{C}$, the subdifferential of its indicator is the normal cone:

Outside the set, $x \notin \mathcal{C}$ implies $\partial \iota_\mathcal{C}(x) = \emptyset$.

For an affine space $\mathcal{C}= a+\mathcal{V}$ with direction space $\mathcal{V}\subset \mathcal{H}$, the normal cone at each of its points is $\mathcal{N}_\mathcal{C}(x)=\mathcal{V}^\bot$, the orthogonal complement of $\mathcal{V}$. More generally, at an interior point $x \in \mathop{\mathrm{int}}(\mathcal{C})$ of $\mathcal{C}$, we have $\mathcal{N}_\mathcal{C}(x)=\{0\}$. At a boundary point, the normal cone describes the supporting directions of $\mathcal{C}$ at $x$.

The normal cone expresses first-order optimality for the constrained problem

If $f$ is finite and continuous at a point of $\mathcal{C}$, the sum rule gives the optimality condition

If $f$ is differentiable, it reads $-\nabla f(x) \in \mathcal{N}_\mathcal{C}(x)$.

18.2 Legendre–Fenchel Transform¶

The Legendre–Fenchel transform provides a dual representation of a convex function. It makes many Lagrange-duality calculations systematic by expressing inner minimizations through conjugates.

18.2.1 Legendre Transform¶

For $f \in \Gamma_0(\mathcal{H})$, we define its Legendre–Fenchel transform, or convex conjugate, by

As a supremum of continuous affine functions, $f^*$ is convex and lower semicontinuous; in fact, $f^\star \in \Gamma_0(\mathcal{H}^*)$. The following biconjugacy theorem recovers the original function.

Even when $f$ is not convex, $f^*$ is convex. If $f$ admits an affine minorant, $f^{**}$ is its lower semicontinuous convex envelope: the largest lower semicontinuous convex function below $f$.

The subdifferentials of $f$ and $f^*$ satisfy the following inverse relation.

Here are useful examples and transformation rules.

18.2.2 Legendre Transform and Smoothness¶

The Legendre–Fenchel transform exchanges smoothness and strong convexity. It inverts subdifferentials; when $f$ is twice continuously differentiable with positive definite Hessian and $y=\nabla f(x)$, the inverse function theorem yields

The next statement gives a version of this correspondence that does not require second derivatives.

This suggests a useful smoothing operation. The infimal convolution is

For proper convex functions, whenever this infimum defines a proper function, it is convex and satisfies

Moreover, $(f+g)^*=f^*\otimes g^*$ under the qualification $\mathop{\mathrm{relint}}(\mathop{\mathrm{dom}}(f))\cap\mathop{\mathrm{relint}}(\mathop{\mathrm{dom}}(g))\neq\emptyset$; without a qualification, a lower semicontinuous closure can be necessary.

For $\mu>0$, the Moreau–Yosida regularization of $f\in\Gamma_0(\mathcal{H})$ is

The function inside the conjugate is $\mu$-strongly convex, so $f_\mu$ has a $1/\mu$-Lipschitz gradient.

For the absolute value, the Moreau–Yosida regularization is

Compare this with the earlier regularization $\sqrt{x^2+\mu^2}$, which lies above the absolute value.

18.3 Convex Duality¶

A dual problem depends on the chosen primal formulation. A change of variables or a different representation of the constraints can produce a different dual problem.

18.3.1 Lagrange Duality: Affine Constraints¶

Begin with affine equality constraints:

where $A\in\mathbb{R}^{P\times p}$, $y\in\mathbb{R}^P$, and $f : \mathbb{R}^p \rightarrow \mathbb{R}$ is convex and finite everywhere, hence continuous.

Assume that the affine constraint is feasible. Introducing $u\in\mathbb{R}^P$ gives the Lagrangian $\mathcal{L}(x,u)=f(x)+\langle Ax-y,\,u\rangle$. Minimization over $x$ yields

Because $f$ is finite and continuous everywhere, feasibility is a sufficient qualification for strong duality:

A primal-dual optimal pair satisfies $Ax^\star=y$ and $-A^*u^\star\in\partial f(x^\star)$.

18.3.2 Lagrange Duality: General Case¶

We consider a minimization of the form

for a continuous convex function $f : \mathcal{H}\rightarrow \mathbb{R}$, a matrix $A \in \mathbb{R}^{P \times N}$ and a function $g : \mathcal{H}\rightarrow \mathbb{R}^Q$ such that each coordinate $g_i : \mathcal{H}\rightarrow \mathbb{R}$ is continuous and convex.

In the standard formulation of a convex program, equality constraints are affine.

Problems with convex inequality constraints can be written in the form (18.5). The representation is not unique, and different formulations lead to different dual problems.

For simplicity, $f$ is assumed finite and continuous on its full domain $\mathop{\mathrm{dom}}(f)=\mathbb{R}^N$.

The theory extends to more general $\mathop{\mathrm{dom}}(f)$, with additional domain qualifications. Here all constraints are expressed through $Ax=y$ and $g(x) \leqslant 0$.

Conic duality extends this construction from nonnegativity $x \geqslant 0$ to positive semidefiniteness $X \succeq 0$ of a matrix $X$, and more generally to membership in a convex cone.

We use the following fact

to encode the constraints $r=Ax-y=0$ and $s=g(x) \leqslant 0$.

Define the Lagrangian by

The primal value in (18.5) is therefore

The dual objective is $F(u,v)\mathrel{:=}\inf_x\mathcal{L}(x,u,v)$. Exchanging the order of optimization gives the dual value

The dual objective $F$ is concave because it is an infimum of affine functions. The dual problem therefore maximizes a concave objective.

Weak duality states that every feasible dual value is a lower bound on the primal optimum.

The next theorem gives a constraint qualification that guarantees equality of the primal and dual values.

The existence of $x_0$ is Slater’s constraint qualification; the strict inequality $g(x_0)<0$ holds componentwise. Other, weaker qualifications are possible.

Condition (18.8) states primal and dual feasibility.

Condition (18.9) expresses optimality of $\mathcal{L}(x,u,v)$ with respect to $x$.

Together with feasibility, condition (18.10) expresses maximality of $\mathcal{L}(x^\star,u,v)$ over the admissible multipliers $(u,v)$.

Together these are the Karush–Kuhn–Tucker (KKT) conditions. Under the stated qualification, they are necessary and sufficient for primal-dual optimality.

Complementary slackness, $v_i^\star g_i(x^\star) = 0$, relates a multiplier to its constraint: if $g_i(x^\star)<0$, the constraint is inactive and $v_i^\star=0$; if $v_i^\star>0$, the constraint must be active, $g_i(x^\star)=0$.

For an affine inequality $g_i(x) = \langle x,\,h_i\rangle - c_i \leqslant 0$, strict feasibility $g_i(x_0)<0$ may be replaced by ordinary feasibility $\langle x_0,\,h_i\rangle \leqslant c_i$ in the qualification.

If $\mathop{\mathrm{dom}}(f)$ is a proper subset of $\mathbb{R}^N$, the objective itself encodes constraints in addition to those written with $\leqslant$. The qualification then also requires $x_0 \in \mathop{\mathrm{relint}}(\mathop{\mathrm{dom}}(f))$.

Theorem 18.11 extends the Lagrange-multiplier conditions to convex problems with inequalities. Inequality constraints introduce nonnegative multipliers $v$. Convexity ensures that the KKT conditions are sufficient, and the stated constraint qualification ensures their necessity.

As an example, consider projection onto a nonempty affine space $\{x:Ax=y\}$:

The minimizing $x$ satisfies $x-z+A^*u=0$, hence $x=z-A^*u$. Therefore

An optimal multiplier solves $AA^*u^\star=Az-y$. Since $y\in\mathop{\mathrm{Im}}(A)$, a solution is $u^\star=(AA^*)^+(Az-y)$, where ${}^+$ denotes the Moore–Penrose inverse. If $A$ has full row rank, $(AA^*)^+=(AA^*)^{-1}$. The unique projection is

A further example, the Lasso, is treated in Section 11.1.5.

18.3.3 Fenchel–Rockafellar Duality¶

Conjugates often give explicit expressions for the Lagrange dual of an objective $f$. Fenchel–Rockafellar duality is a particularly useful example.

We consider the following structured minimization problem

Introducing an auxiliary variable gives

We can then form the primal-dual problem

Under the domain qualification in Theorem 18.12, one can exchange the infimum and supremum to obtain the dual problem

This gives the Fenchel–Rockafellar dual problem. The following theorem states a sufficient domain qualification for strong duality.

Condition (18.16) is the constraint qualification ensuring that one can exchange the infimum and supremum in (18.17). It is the relative-interior qualification corresponding to the equality-constrained reformulation (18.14).

The relations (18.18) express first-order optimality in the primal variable $x$ and dual variable $u$ for the saddle function $\mathcal{L}$. They can be collected in matrix notation as