Billy Ian's Short Leisure-time Wander

into language, learning, intelligence and beyond

Notes on Convex Optimization (2): Convex Functions

| Comments

1. Basic Properties and Examples

1.1 Definition

$f:\mathbb{R}^n \rightarrow \mathbb R$ is convex if $\mathbf{dom}\ f$ is a convex set and

for all $x,y\in \mathbf{dom}\ f, 0\le\theta\le1$

  • $f$ is concave if $-f$ is convex
  • $f$ is strictly convex if $\mathbf{dom}\ f$ is convex and for $x,y\in\mathbf{dom}\ f,x\ne y, 0<\theta<1$

$f:\mathbb{R}^n \rightarrow \mathbb R$ is convex if and only if the function $g: \mathbb{R} \rightarrow \mathbb{R}$,

is convex (in $t$) for any $x \in \mathbf{dom}\ f, v\in\mathbb R^n$

1.2 Extended-value extensions

extended-value extension $\tilde f$ of $f$ is

1.3 First-order conditions

1st-order condition: differentiable $f$ with convex domain is convex iff

1.4 Second-order conditions

2nd-order conditions: for twice differentiable $f$ with convex domain - $f$ if convex if and only if - if $\nabla^2f(x)\succ0$ for all $x\in\mathbf{dom}\ f$, then $f$ is strictly convex

1.5 Sublevel sets and epigraph

$\alpha$-sublevel set of $f: \mathbb R^n \rightarrow \mathbb R$:

sublevel sets of convex functions are convex (converse if false)

If $f$ is concave, then its $\alpha$-superlevel set, given by ${x\in\mathbf{dom}\ f\mid f(x)\le\alpha}$, is a convex set

epigraph of $f:\mathbb R^n \rightarrow \mathbb R$:

$f$ is convex if and only if $\mathbf{epi}\ f$ is a convex set

$f$ is concave if and only if its hypograph, defined as

is a convex set

1.6 Jensen’s inequality and extensions

Jensen’s Inequality: if $f$ is convex, then for $0\le\theta\le1$,

extension: if $f$ is convex, then

for any random variable $z$

2. Operations that Preserve Convexity

2.1 Positive weighted sum & composition with affine function

nonnegative multiple: $\alpha f$ is convex if $f$ is convex, $\alpha \ge 0$

sum: $f_1+f_2$ convex if $f_1,f_2$ convex (extends to infinite sums, integrals)

composition with affine function: $f(Ax+b)$ is convex if $f$ is convex

2.2 Pointwise maximum

pointwise maximum: if $f_1,\dots,f_m$ are convex, then $f(x)=\max{f_1(x),\dots,f_m(x)}$ is convex

pointwise supermum: if $f(x,y)$ is convex in $x$ for each $y\in\mathcal{A}$, then

is convex

similarly, the pointwise infimum of a set of concave functions is a concave function

2.3 Composition

composition with scalar functions: composition of $g: \mathbb R^n \rightarrow \mathbb R$ and $h: \mathbb R\rightarrow \mathbb R$:

$f$ is convex if $g$ convex, $h$ convex, $\tilde h$ nondecreasing; $g$ concave, $h$ convex, $\tilde h$ nonincreasing

Note: monotonicity must hold for extended-value extension $\tilde h$

vector composition: composition of $g:\mathbb R^n \rightarrow \mathbb R^k$ and $h:\mathbb R^k \rightarrow \mathbb R$:

$f$ is convex if $g_i$ convex, $h$ convex, $\tilde h$ nondecreasing in each argument; $g$ concave, $h$ convex, $\tilde h$ nonincreasing in each argument

2.4 Minimization

minimization: if $f(x,y)$ is convex in $(x,y)$ and $C$ is a convex set then

is convex

2.5 Perspective of a function

perspective: the perspective of a function $f:\mathbb R^n \rightarrow \mathbb R$ is the function $g:\mathbb R^n \times \mathbb R \rightarrow \mathbb R$,

$g$ is convex if $f$ is convex

3. The Conjugate Function

3.1 Definition

the conjugate of a function $f$ is

  • $f^*$ is convex whether or not $f$ is convex

3.2 Basic properties

conjugate of the conjugate: if $f$ is convex and closed, then $f^{**}=f$

differentiable functions: The conjugate of a differentiable function $f$ is also called the Legendre transform of $f$. Let $z\in\mathbb{R}^n$ be arbitrary and define $y=\nabla f(z)$, then we have

scaling and composition with affline transformation: For $a>0$ and $b\in\mathbb{R}$, the conjugate of $g(x)=af(x)+b$ is $g^*(y)=af^*(y/a)-b$.

Suppose $A\in\mathbb{R}^{n\times n}$ is nonsingular and $b\in\mathbb{R}^n$. Then the conjugate of $g(x)=f(Ax+b)$ is

with $\mathbf{dom}\ g^*=A^T\mathbf{dom}\ f^*$

sums of independent functions: if $f(u,v)=f_1(u)+f_2(v)$, where $f_1$ and $f_2$ are convex functions with conjugates $f_1^*$ and $f_2^*$, respectively, then

4. Quasiconvex Functions

$f:\mathbb R^n\rightarrow \mathbb R$ is quasiconvex if $\mathbf{dom}\ f$ is convex and the sublevel sets

are convex for all $\alpha$

  • $f$ is quasiconcave if $-f$ is quasiconvex
  • $f$ is quasilinear if it is quasiconvex and quasiconcave
  • convex functions are quasiconvex, but the converse is not true

modified Jensen inequality: for quasiconvex $f$

first-order condition: differentiable $f$ with convex domain is quasiconvex iff

operations that preserve quasiconvexity:

  • nonnegative weighted maximum
  • composition
  • minimization

sum of quasiconvex functions are not necessarily quasiconvex

5. Log-concave and Log-convex Functions

a positive function $f$ is log-concave if $\log f$ is concave:

$f$ is log-convex if $\log f$ is convex

properties of log-concave functions:

  • twice differentiable $f$ with convex domain is log-concave iff

for all $x\in\mathbf{dom}\ f$

  • product of log-concave functions is log-concave
  • sum of log-concave functions is not always log-concave; however, log-convexity is preserved under sums
  • integration: if $f:\mathbb R^n\times\mathbb R^m \rightarrow \mathbb R$ is log-concave, then

is log-concave

consequences of integration property:

  • convolution $f*g$ of log-concave functions $f,g$ is log-concave
  • if $C\subseteq \mathbb R^n$ convex and $y$ is a random variable with log-concave pdf then

is log-concave

6. Convexity w.r.t. Generalized Inequalities

$f:\mathbb{R}^n\rightarrow\mathbb{R}^m$ is $K$-convex if $\mathbf{dom}\ f$ is convex and

for $x,y\in\mathbf{dom}\ f,0\le\theta\le1$