• SU-SOC175 JAN052025
• SU-SOC175 JAN122025

1. start with function \(f\) gives as expression
2. build parse tree for expression (leaves and variables / constants, nodes are functions of child expressions)
3. apply general composition rule that preserve convexity

Greedy parses may fail, such as in the case of logsumexp.

a function for which, given any two points, the function between those points sits at (lines are convex!) or below the plane given those points

constituents

For \(f: \mathbb{R}^{n} \to \mathbb{R}\)

requirements

\begin{equation} f\qty(\theta x + \qty(1-\theta) y) \leq \theta f\qty(x) + \qty(1-\theta) f\qty(y) \end{equation}

strictly convex is the strict inequality

additional information

check if something is a convex function

• check definition
• restrict it to a line: convexity preserve line restriction
• 1st order condition
• 2nd order condition
• show that \(f\) is constructed by operations that preserve fuction convexity

some convex functions

• affine: \(ax + b\)
• exponential: \(e^{ax}\)
• powers: \(x^{\alpha}\) for \(\alpha \geq 1\) or \(\alpha \leq 0\)
• \(|x|^{p}\) for \(p > 1\)
• relu
• any norm
• sum of squares: \(\qty {x}^{2}_{2} = x_1^{2} + … + x_{n}^{2}\)
• max function: \(\max \qty(x) = \max \qty {x_1 \dots x_{n}}\)
• softmax: \(\log \qty(\exp x_1 + \dots + \exp x_{n})\)
• general affine function: \(f\qty(X) = tr\qty(A^{T} X) + b\) (“an inner product”)
• spectral norm: \(f\qty(X) = \norm{X}_{2} = \sigma_{\max}\qty(X)\) (the maximum singular value of \(X\)
• logsumexp: \(f\qty(x) = \log \sum_{k=1}^{n} \exp x_{k}\)
• quadratic over linear: \(f\qty(x,y) = \frac{x^{2}}{y}, y >0\)

some concave fuctions

• affine
• powers
• logs: \(\log x\)
• entropy: \(- x \log x\)
• negative part (opposite relu)
• log determinant: \(f\qty(X) = \log \text{det} X\)
• geometric mean: \(f\qty(x) = \qty(\prod_{k=1}^{n} x_{k})^{\frac{1}{n}}\) an \(\mathbb{R}_{++}^{n}\)

sublevel set

\begin{equation} C_{\alpha} = \qty {x \in \text{dom f} \mid f\qty(x) \leq \alpha } \end{equation}

EE364A.stanford.edu

Lecture

• SU-EE364a JAN062026
• SU-EE364A JAN082026
• SU-EE364A JAN132026

line

All points of the form \(x = \theta x_{1} + \qty(1-\theta) x_{2}\), with \(\theta \in \mathbb{R}\) is a “line through \(x_1\), \(x_2\)”.

affine set

For set \(G\), for all two points \(x_1, x_2 \in G\), all points lying on the line \(x_1, x_2 \in G\). For instance, the solution set of a set of linear equations \(\qty {x \mid A x = b}\).

convex set

convex set,

line segment

all points form \(x = \theta x_{1} + \qty(1-\theta)x_{2}\), with \(0 \leq \theta \leq 1\).