Convex Sets and Functions - Lecture Notes

Convex Sets

• A set $C ∈ R^N$ is convex if, for any two points $x, y ∈ C$, the line segment joining $x$ and $y$ is contained in $C$.

  • Mathematically, this means for any $x, y ∈ C$, the set $\ [x, y] := {tx + (1 − t)y : t ∈ [0, 1]}$ is a subset of $C$.

Convex Sets in R

• In the real number line $\mathbb{R}$, convex sets are intervals. Examples include:

  • $(a, b)$

  • $[a, b)$

  • $[a, b]$

  • $[a, +∞)$

  • $(−∞, a)$

Norm Balls

• A norm ball with center $x<em>c ∈ R^n$ and radius $r ≥ 0$ is defined as the set $\ {x ∈ R^n | ∥x − x</em>c∥ ≤ r}$.

  • Euclidean norm ball: $B<em>2(x</em>c ,r) = {x | ∥x−x<em>c∥</em>2 ≤ r} = { x | \sqrt{\sum<em>{i=1}^{n} (x</em>i − x_{c,i})^2} ≤ r }$

  • $\ell<em>1$-norm ball: $B</em>1(x<em>c ,r) = {x | ∥x−x</em>c∥<em>1 ≤ r} = {x | \sum</em>{i=1}^{n} |x<em>i − x</em>{c,i}| ≤ r}$

  • $\ell<em>∞$-norm ball: $B</em>∞(x<em>c ,r) = {x | ∥x−x</em>c∥<em>∞ ≤ r} = {x | \max</em>{i=1,…,n} |x<em>i − x</em>{c,i}| ≤ r}$

Norm Balls - Ellipsoids

• An ellipsoid is a set of the form $\ {x|(x − x<em>c )^tA(x − x</em>c ) ≤ 1}$, where $A$ is a symmetric positive definite matrix.

Affine Sets

• Lines in $R^2$: $\ {x = (x<em>1, x</em>2) ∈ R^2 | a<em>1x</em>1 + a<em>2x</em>2 = b}$, where $a = (a<em>1, a</em>2)$ is the normal to the line.

• Planes in $R^3$: $\ {x = (x<em>1, x</em>2, x<em>3) ∈ R^3 | a^T x = a</em>1x<em>1 + a</em>2x<em>2 + a</em>3x<em>3 = b}$, where $a = (a</em>1, a<em>2, a</em>3)$ is the normal to the plane.

• Lines in $R^3$ (as the intersection of two planes): $\ {x = (x<em>1, x</em>2, x_3) ∈ R^3 | Ax = b}$, where

  $A = \begin{bmatrix} a<em>{11} & a</em>{12} & a<em>{13} \ a</em>{21} & a<em>{22} & a</em>{23} \end{bmatrix} \text{and} b = \begin{bmatrix} b<em>1 \ b</em>1 \end{bmatrix}$.

  • The rows $a<em>1, a</em>2 ∈ R^3$ of $A$ are the normals to the planes.

• The solution set of underdetermined linear equations: $\ {x | Ax = b}$.

• The set of solutions of linear equations is of the form $\ {x<em>p + x</em>h : x<em>h ∈ ker(A)} = x</em>p + ker(A)$, which are vector spaces shifted by adding a constant vector $x_p$.

Convex Cones

• A convex cone is a set $C$ that is closed under positive linear combinations. If $x, y ∈ C$, then $\alpha x + \beta y ∈ C$ for any $\alpha ≥ 0, \beta ≥ 0$.

• Given a set of vectors $S$, the convex cone generated by $S$ is the set $C<em>S = { \sum</em>{i=1}^{n} \alpha<em>i x</em>i : \alpha<em>1, …, \alpha</em>n ≥ 0, x<em>1, …, x</em>n ∈ C}$.

Convex Combination and Convex Hull

• A convex combination of $x<em>1, . . . , x</em>k$ is any point $x$ of the form $x = t<em>1x</em>1 + t<em>2x</em>2 + · · · + t<em>k x</em>k$ with $t<em>1 + t</em>2 + · · · + t<em>k = 1$, and $t</em>i ≥ 0$.

• The convex hull of a set $S$ is the set of all convex combinations of points in $S$.

Hyperplanes and Half-Spaces

• A hyperplane is a set of the form $\ {x | a^tx = b}$, where $a ≠ 0$.

• A half-space is a set of the form $\ {x | a^tx ≤ b}$, where $a ≠ 0$.

• In both cases, $a$ is the normal vector.

Polytope

• A polytope is a set of the form $\ {x | Ax ⪯ b}$, where $A ∈ R^{m×n}$.

• The notation $⪯$ represents component-wise inequality: $a<em>ix ≤ b</em>i$, where $a_i$ is the $i$-th row of $A$.

• A polytope is an intersection of $m$ half-spaces.

Operations That Preserve Convexity

• The intersection of any number of convex sets is convex.

• If $f : R^n → R^n$ is an affine function (i.e., it can be written as $f (x) = Ax + b$ with $A ∈ M_{n,m}(R), b ∈ R^m$), then:

  • If $C ⊆ R^n$ is convex, then $f (C) = {f (x) ∈ R^m | x ∈ C}$ is a convex set.

  • If $C ⊆ R^m$ is convex, then $f^{-1}(C) = {x ∈ R^n | f (x) ∈ C}$ is a convex set.

• To verify if a set is convex, express it in terms of simpler known convex sets using operations that preserve convexity.

Convex Functions

• A function $f : C → R$ is convex if $f (tx + (1 − t)y) ≤ tf (x) + (1 − t)f (y)$, for any two points $x, y ∈ C$, and $t ∈ [0, 1]$.

• $f$ is concave if $-f$ is convex.

• A function $f : C → R$ is strictly convex if $f (tx + (1 − t)y) < tf (x) + (1 − t)f (y)$, for any two points $x, y ∈ C$ and any $t ∈ [0, 1]$.

Examples of Convex and Concave Functions on R

• Convex functions:

  • Quadratic functions: $x^2$ on $\mathbb{R}$.

  • Exponential: $e^{ax}$ is convex on $\mathbb{R}$, for any $a ∈ R$.

  • Powers: $x^α$ for $x > 0$ and $\alpha ≥ 1$ or $\alpha ≤ 0$.

  • Powers of absolute value: $|x|^p$ on $\mathbb{R}$, for $p ≥ 1$.

  • Negative entropy: $x \log x$ for $x > 0$.

  • Affine functions: $ax + b$ on $\mathbb{R}$, for any $a, b ∈ R$.

• Concave functions:

  • Affine functions: $ax + b$ on $\mathbb{R}$, for any $a, b ∈ R$ (Convex and concave!).

  • Powers: $x^α$ for $x > 0$ and $0 ≤ \alpha ≤ 1$.

  • Logarithm: $\log x$ for $x > 0$.

Examples of Convex Functions on Rn

• Affine functions: $f (x) = ⟨x, b⟩ + c$.

• Norms: Every norm on $R^n$ is convex. In particular, any $\ell<em>p$ norm, $\ ∥x∥</em>p = (\sum<em>{i=1}^{n} |x</em>i|^p)^{1/p}$ is convex.

• Max function: $f (x) = \max{x<em>1, . . . , x</em>n}$.

• Quadratic-over-linear function: $f (x<em>1, x</em>2) = \frac{x<em>1^2}{x</em>2}$, with $x_2 > 0$.

Epigraph, Sublevel and Superlevel Sets

• $\alpha$-sublevel set of $f : R^n → R$: $C_α = {x ∈ dom(f )| f (x) ≤ α}$.

  • Sublevel sets of convex functions are convex.

  • Superlevel sets of concave functions are convex.

  • Functions with all their sub-level sets convex are not necessarily convex. These broader class of functions are called quasi-convex.

• Epigraph of $f : R^n → R$: $epi(f ) = {(x,t) ∈ R^{n+1} | x ∈ dom(f ), f (x) ≤ t}$.

  • $f$ is a convex function if and only if its epigraph is a convex set.

Sufficient and Necessary Condition for Convexity

• A function $f : R^n → R$ is convex if and only if the function $g : R → R$, $g(t) = f (x + tv)$ is convex for any $x, v ∈ R^n$.

• Using this property the problem is reduced to check the convexity of function of one variable.

First Order Condition for Convexity

• Let $f : R^n → R^m$ be a differentiable function and let $C$ be a convex subset of $R^n$. Then:

  $f \text{ is convex } ⇐⇒ f (y) ≥ f (x) + ⟨∇f (x), y − x⟩, ∀x, y ∈ C.$

  • The first order Taylor approximation of $f$ is a global underestimator.

  • Moreover, $f$ is strictly convex if and only if:

  $f (y) > f (x) + ⟨∇f (x), y − x⟩, ∀x, y ∈ C.$

Second Order Condition for Convexity

• Let $f : R^n → R$ be a twice differentiable function and let $C$ be a convex subset of $R^n$.

  $f \text{ is convex } ⇐⇒ ∇^2f (x) \text{ is positive semi-definite for all } x ∈ C \text{ (all eigenvalues of } ∇^2f (x) \text{ are non-negative)}.$

  $f \text{ is strictly convex } ⇐⇒ ∇^2f (x) \text{ is positive definite for all } x ∈ C \text{ (all eigenvalues are positive)}.$

Is a Quadratic Function a Convex Function?

• Let $f (x) = \frac{1}{2} ⟨x, Qx⟩ − ⟨x, d⟩ + c$, with $A$ a symmetric matrix.

  • Then, $∇f (x) = Qx − d$ and $∇^2f (x) = Q$.

  • $f (x)$ is convex if the matrix $A$ is positive semi-definite.

  • A special case: $f (x) = \frac{1}{2} ∥Ax − b∥_2^2 = \frac{1}{2} ⟨x, A^tAx⟩ − 2⟨x, b⟩ + ⟨b, b⟩$.

    • Then, $∇f (x) = A^t(Ax − b)$ and $∇^2f (x) = A^tA$.

    • $f (x)$ is convex for any matrix $A$ because $A^tA$ is symmetric and positive semidefinite.

Establishing the Convexity of a Function

• In practice, for a general function $f$, we either:

  1. Show that $f$ is obtained from simple convex functions and operations that preserve convexity.

  2. Verify the definition (restricted to a line).

  3. If the function is twice differentiable, show that $∇^2f (x)$ is positive semidefinite.

  4. Verify the definition.

Operations That Preserve Convexity

• Nonnegative multiple: $\alpha f$ is convex if $f$ is convex and $\alpha > 0$.

• Sum: $f<em>1 + f</em>2$ is convex if $f<em>1, f</em>2$ are convex. This is also true for infinite sums and for integrals.

• Composition with affine function: Let $f : R^n → R$ be a convex function, $A ∈ M_{n,m}(R), b ∈ R^n$. Then, $f (Ax + b)$ is a convex function.

  • Example: any norm of an affine function $f (x) = ∥Ax + b∥$ is convex.

• Pointwise maximum: If $f<em>1, . . . , f</em>m$ are convex, then $f (x) = \max{f<em>1(x), . . . , f</em>m(x)}$ is convex.

• Pointwise supremum: If $f (x, y)$ is convex in $x$ for all $y$, and $C$ is an arbitrary set, then $g(x) = \sup_{y∈C} f (x, y)$ is convex.

• Pointwise infimum: If $f (x, y)$ is convex in $(x, y)$ and $C$ is a convex set, then $g(x) = \inf_{y∈C} f (x, y)$ is convex.

• Extended-value extension: Let $f : D ⊂ R^n → R$, be a convex function defined on $D$. We denote by $\tilde{f}$ its extended-value extension such that

  $\tilde{f}(x) = \begin{cases} f (x) & \text{if } x ∈ C \ +∞ & \text{if } x ∉ C \end{cases}$

  • The $\tilde{f}$ is convex. (Concave functions are extended with $-∞$ to preserve concavity.)

• Scalar composition: Let $g : R^n → R$ and $h : R → R$ and their composition $f = h ◦ g : R^n → R$. (That is, $f (x) = h(g(x))$).

  • $f$ is convex if $\tilde{h}$ is convex and nondecreasing, and $g$ is convex.

  • $f$ is convex if $\tilde{h}$ is convex and nonincreasing, and $g$ is concave.

  • $f$ is concave if $\tilde{h}$ is concave and nondecreasing, and $g$ is concave.

  • $f$ is concave if $\tilde{h}$ is concave and nonincreasing, and $g$ is convex.

Convex Problems You Have Already Seen

• An image denoising energy: Given $f ∈ R^{HW}$ a noisy image, recover $u ∈ R^{HW}$ as the solution of

  $\min<em>{u∈R^{HW}} ∥∇</em>h u∥<em>2^2 + λ∥u − f∥</em>2^2$

  • $\nabla_h$ is a $2HW × HW$ matrix that computes the discretized gradient with finite differences.

    1. The second term is: $u^T u − 2f^T u + f^T f$. Quadratic function with Hessian $I$, which is positive definite. Thus it is strictly convex.

    2. The first term is: $u^T (∇<em>h^T ∇</em>h)u$. Quadratic function with Hessian $∇<em>h^T ∇</em>h$, which is positive semi-definite. Thus first term is convex.

    3. Sum of convex and strictly convex functions is strictly convex.

Non-Differentiable Functions

• Total variation for image denoising (Rudin-Osher-Fatemi): Given $f$ a noisy image, recover $u$ as the solution of

  $\min<em>u ∥∇</em>h u∥<em>1 + λ∥u − f∥</em>2^2$

  1. Second term is strictly positive.

  2. First term is: $f (g(x))$, where $f (y) = ∥y∥<em>1$ and $g(u) = ∇</em>hu$. $f$ is convex (norms are convex functions) and $g$ is affine. Composition of convex with affine is convex.

  3. Sum of convex and strictly convex functions is strictly convex.