Recap

Common strategies for showing convexity of sets

• Directly from definition
• Is it a “known” convex set? (E.g., polyhedron, ellipsoid.)
• Is it an intersection / Minkowski sum of convex sets?
• Is it a level set of a convex function?
• Combination of two or more of the above

Common strategies for showing convexity of functions

• Directly by one of the characterizations
• Is it a “known” convex function? (E.g., norm, linear, PSD quadratic.)
• Sum and scaling of convex functions
• Composition of convex with affine function
• Pointwise maximum of convex functions
• Combination of two or more of above

<aside> 💡 “Known” convex functions

• Univariate functions:

  • $e^x$ is convex over $\R$, and $\ln x$ is concave for $x>0$;
  • $x^a$ is convex over $\R^+$ for $a \geq 1$ or $a \leq 0$, and concave for $0 \leq a \leq 1$.

• Linear / Affine: $f(x) = a\cdot x + b$ for $a \in \R^d, b \in \R$ is always convex.

• Quadratic: $f(x) = x^T A x + b^T x + c$ for $A \in \R^{d \times d}, b \in \R^d, c \in \R$ is convex if $A$ is PSD.

• Norms: $f(x) = \|x\|$ is convex for any norm $\|\cdot\|$.

• Positive-weighted sums: if $f_1,\ldots,f_n$ are convex and $\alpha_1,\ldots,\alpha_n \geq 0$ then $\sum_{i=1}^n \alpha_i f_i$ is convex.

• Composition with affine: if $f : \R^n \to \R$ is convex and $A \in \R^{n \times d}, b \in \R^n$ then $g(x) = f(Ax+b)$ is also convex over $\R^d$. </aside>

Jensen’s inequality

<aside> 💡 Theorem: Jensen’s inequality

If $f : S\to\R$ is convex (over a convex $S$), then for all $x_1,\ldots,x_n \in S$ and $\lambda_1,\ldots,\lambda_n \geq 0$ such that $\sum_{i=1}^n \lambda_i = 1$, we have that

$$ \begin{align*} f\left(\sum_{i=1}^n \lambda_i x_i\right) \leq \sum_{i=1}^n \lambda_i f(x_i) . \end{align*} $$

</aside>