2.2 Convex Functions

Convex Function

A function $f:{\mathbb{R}}^n\to \mathbb{R}$ is convex if its domain $D$ is a convex set, and:

1. (Zeroth-Order Condition) For all points ${\vec{x}}_1,{\vec{x}}_2\in D$ and $\alpha \in [0,1]$, the graph of $f$ lies below (or on) the line segment connecting $f({\vec{x}}_1)$ and $f({\vec{x}}_2)$, such that
   $f(\alpha {\vec{x}}_1+(1-\alpha ){\vec{x}}_2)\le \alpha f({\vec{x}}_1)+(1-\alpha )f({\vec{x}}_2).$
2. (First-Order Condition) If $f$ is differentiable, it holds that for all $x,y\in D$, the tangent line (or tangent plane in higher dimensions) at any point $x$ lies below the function everywhere else:
   $f(y)\ge f(x)+\nabla f(x{)}^T(y-x).$
3. (Second-Order Condition) If $f$ is twice-differentiable, it holds that the Hessian of $f$ for all $x\in D$ is positive semi-definite (i.e., ${\nabla }^{2}f(x)⪰0$).

If $-f$ is convex, then $f$ is said to be concave. The following is a visual interpretation of the Zeroth-Order Condition for convexity:

\usepackage{pgfplots}
\begin{document}
\begin{tikzpicture}
 \begin{axis}[
   xlabel={$x$}, xlabel style={align=left},
   ylabel={$f(x)$},
   ytick=0,
   xtick=0,
   domain=0:6,               % choose a domain that avoids the asymptote at x=1 if desired
   samples=200,
   restrict y to domain=0:20,  % only show y-values that are positive (and up to 20)
   unbounded coords=jump,      % jump over undefined/infinite parts
   axis lines=center,
   clip mode=individual]
   % Plot the function's positive part using max(0, f(x)):
   \addplot[thick, clip=true] {max(0, x^2/3 + 1/(x-1))};
   
   \draw[dashed, thick] (axis cs:5.41,0) -- (axis cs:5.41,10) node[at start, below]{$x_{2}$} node[right]{$f(x_{2})$};
   \filldraw (axis cs:5.41,10) circle (2pt);
   \draw[dashed, thick] (axis cs:1.17,0) -- (axis cs:1.17,6.3) node[at start, below]{$x_{1}$} node[left]{$f(x_{1})$};
   \filldraw (axis cs:1.17,6.3) circle (2pt);
   \draw (axis cs:1.17,6.3) -- (axis cs:5.41,10) node[midway, above, sloped]{$\alpha f(x_{1})+(1-\alpha)f(x_{2})$};
   
   \draw[dotted, thick] (axis cs:3.5,0) -- (axis cs:3.5,8.335) node[at start, below]{$z=\alpha x_1+(1-\alpha)x_2$};
   \filldraw (axis cs:3.5,4.48) circle (2pt) node[below right]{$f(z)$};
   \filldraw (axis cs:3.5,8.335) circle (1pt);
 \end{axis}
\end{tikzpicture}
\end{document}

Furthermore, a function $f:{\mathbb{R}}^n\to \mathbb{R}$ is strongly convex if there exists some $m$, such that
$\tilde{f}(x)=f(x)-\frac{m}{2}\Vert x{\Vert }_2^2$
is convex. Note that strong convexity implies strict convexity,

Properties

(Envelope Representation) If $f$ is convex and l.s.c., $f(x)=\underset{a\le f}{\sup }a(x)$, where $a$ is a collection of affine functions such that $a(x)\le f(x)$ for all $x\in X$.

You can imagine all of $f$‘s tangents “enveloping” $f$: they only intersect one point of $x$, which, in terms of all tangent lines on $f$, constructs $f$. The largest value of any affine $a$ on $x$ will be the point where the affine tangent intersects $f$. We use the supremum instead of the maximum to keep the behavior well-defined for discontinuities.

Examples

Zeroth-Order Condition on Parametrized Functions

Consider a convex function $f:{\mathbb{R}}^n\to \mathbb{R}$. Given two arbitrary points $y,z\in {\mathbb{R}}^n$, we define the scalar function $g:\mathbb{R}\to \mathbb{R}$ as follows:
$g(t)=f(y+tz),\forall t\in \mathbb{R}.$
The function $g$ is the restriction of the function $f$ to a line parametrized by a scalar $t$.

By analyzing the domain of $g$ and using the zeroth-order convexity condition, show that the function $g$ is convex. To begin, we define $\text{dom}(g)=\{t\mid y+tz\in \text{dom}(f)\}$. For some $\alpha \in [0,1]$, we must show that the domain of $g$ is convex, such that for any two $t_i$, it follows that $\alpha t_1+(1-\alpha )t_2\in \text{dom}(g)$. In terms of $\text{dom}(f)$, this is equivalent to showing that $y+(\alpha t_1+(1-\alpha )t_2)z\in \text{dom}(f).$ However, since $y+(\alpha t_1+(1-\alpha )t_2)z=\alpha (y+t_{1}z)+(1-\alpha )(y+t_{2}z)\in \text{dom}(f)$, it follows that $\text{dom}(g)$ is convex.

Now, we must show that
$g(\alpha t_1+(1-\alpha )t_2)\le \alpha g(t_1)+(1-\alpha )g(t_2),$
equivalent to saying
$f(y+[\alpha t_1+(1-\alpha )t_2]z)\le \alpha f(y+t_{1}z)+(1-\alpha )f(y+t_{2}z),$
where the LHS factorizes into $f(y+[\alpha t_1+(1-\alpha )t_2]z)=f(\alpha [y+t_{1}z]+(1-\alpha )[y+t_{2}z])$. To simplify further, take $x_1=y+t_{1}z$ and $x_2=y+t_{2}z$, such that
$f(\alpha x_1+(1-\alpha )x_2)\le \alpha f(x_1)+(1-\alpha )f(x_2).$
This fact is given by definition since $f$ is convex, and therefore $g$ is convex.

Zeroth-Order Condition on Composite Functions

Consider two functions $f:{\mathbb{R}}^n\to \mathbb{R}$ and $h:\mathbb{R}\to \mathbb{R}$. Define the composite function $g:{\mathbb{R}}^n\to \mathbb{R}$ such that $g(x)=h(f(x))$. Assume that for every $x$ in the domain of $f$, the point $f(x)$ is in the domain of $h$, which implies that $g(x)$ is defined for every $x$ in the domain of $f$. Assume that all of the following conditions hold:

• $f$ and $h$ are both convex, and may be non-differentiable

• $h$ is a non-decreasing function, meaning that $h(y_1)\le h(y_2)$ for all $y_1,y_2\in \mathbb{R}$ such that $y_1\le y_2$

By using the zeroth-order convexity condition, show that $g$ is convex. Since $f$ is convex, $\mathrm{dom}(f)$ is convex, and because $g$ is defined wherever $f$ is defined (as assumed), $\mathrm{dom}(g)=\mathrm{dom}(f)$, hence convex. We must only show that for some $x_1,x_2\in \text{dom}(g)$ and $\alpha \in [0,1]$, it follows that

g(\alpha x_{1}+(1-\alpha)x_{2})&=h(f(\alpha x_{1}+(1-\alpha)x_{2})) &(1) \\ & \leq h(\alpha f(x_{1})+(1-\alpha)f(x_{2})) &(2)\\ & \leq \alpha h(f(x_{1})) + (1-\alpha)h(f(x_{2})) &(3) \\ &= \alpha g(x_{1}) + (1-\alpha)g(x_{2}), \end{align}$$ where the RHS transition from $(1)$ to $(2)$ is both due to $h$ being non-decreasing and $f$ being convex, whereas the transition from $(2)$ to $(3)$ is due to $h$ being convex.

Second-Order Condition

Consider the function $f:{\mathbb{R}}^2\to \mathbb{R}$, defined as
$f(x)=\sin (x_1+x_2)+\cos (x_1-x_2)+\lambda (x_1^2+x_2^2),$
where $\lambda$ is some constant

Show that $f$ is not convex for $\lambda =0$