Week 2: Convex Sets and Functions

Convex Sets#

A set $C \subseteq \mathbb{R}^d$ is convex if for any two points $x, y \in C$, the entire line segment connecting them lies inside $C$:

$\theta x + (1-\theta)y \in C \quad \text{for all } \theta \in [0, 1]$

In plain English: you can draw a straight line between any two points in the set and the line never leaves the set.

Examples of convex sets:

• A line or a plane through the origin (a subspace)
• A halfspace $H = \{x \mid a^T x \leq b\}$
• The Euclidean ball $B_r(c) = \{x \mid \|x - c\|_2 \leq r\}$
• A polyhedron $P = \{x \mid Ax \leq b\}$ (intersection of halfspaces)
• The probability simplex $\{x \mid \sum_i x_i = 1,\; x_i \geq 0\}$

Non-examples:

• A crescent moon shape (the line segment between two tips exits the shape)
• The set $\{0, 1\}$ (only two points — not a continuous segment)
• A donut (the hole breaks convexity)

An important fact: the intersection of convex sets is convex. Since hyperplanes and halfspaces are convex, any set defined by linear equalities and inequalities is convex — which is why LP, QP, and SOCP constraints all produce convex feasible regions.

Convex Functions: Definitions#

A function $f: \mathbb{R}^d \to \mathbb{R}$ is convex if its domain is convex and for all $x, y$ in the domain and $\theta \in [0, 1]$:

$f(\theta x + (1-\theta) y) \leq \theta f(x) + (1-\theta) f(y)$

This is Jensen's inequality for two points. Geometrically: the graph of $f$ between $x$ and $y$ lies below the chord connecting $(x, f(x))$ and $(y, f(y))$.

For differentiable $f$, there's an equivalent and very useful first-order condition:

$f(y) \geq f(x) + \nabla f(x)^T (y - x) \quad \text{for all } x, y$

The right-hand side is the first-order Taylor approximation at $x$. Convexity says: the function always lies above its tangent line/hyperplane. This is the property we exploit to bound GD progress in Week 3.

Strict convexity means the inequality is strict for $x \neq y$, $\theta \in (0,1)$. A strictly convex function has at most one global minimum.

Strong convexity means there exists $\mu > 0$ such that:

$f(y) \geq f(x) + \nabla f(x)^T (y - x) + \frac{\mu}{2}\|y - x\|_2^2$

This adds a quadratic term, making the function "curved enough." Strong convexity gives GD linear convergence (Week 3).

Convex Functions: Examples#

Which functions are convex? Here's a practical field guide:

A handy test for 1D functions: if $f''(x) \geq 0$ for all $x$ in the domain, then $f$ is convex.

For multivariate functions, the condition is that the Hessian $\nabla^2 f(x)$ is positive semidefinite (PSDPositive Semidefinite) for all $x$.

Building Convex Functions#

You rarely prove convexity straight from the definition. Instead, build new convex functions from ones you already know using operations that preserve convexity:

• Nonnegative weighted sums: if $f_1, \ldots, f_m$ are convex and $w_i \geq 0$, then $\sum_i w_i f_i$ is convex. (A sum of convex functions is convex.)
• Pointwise maximum: if $f_1, \ldots, f_m$ are convex, so is $f(x) = \max_i f_i(x)$. This is why hinge loss and piecewise-linear penalties are convex.
• Affine composition: if $f$ is convex, then $g(x) = f(Ax + b)$ is convex. Precomposing with an affine map preserves convexity; composing with a general nonlinear map does not.
• Partial minimisation: if $f(x, y)$ is jointly convex, then $g(x) = \min_y f(x, y)$ is convex (whenever the minimum is attained).

Norms are convex. Every norm $\|\cdot\|$ satisfies the triangle inequality ($\|x + y\| \leq \|x\| + \|y\|$) and positive homogeneity ($\|\theta x\| = |\theta|\,\|x\|$). Combining the two, for $\theta \in [0, 1]$:

$\|\theta x + (1-\theta)y\| \leq \|\theta x\| + \|(1-\theta)y\| = \theta\|x\| + (1-\theta)\|y\|$

so every norm — $\|x\|_1$, $\|x\|_2$, and beyond — is convex, not only the squared norm $\|x\|_2^2$ from the table above. Norms are the workhorses of regularisation (Week 10).

A caution: composition is direction-sensitive. Convex $\circ$ convex is not automatically convex: $g(x) = x^2$ and $f(y) = |y - 1|$ are both convex, yet $f(g(x)) = |x^2 - 1|$ is not. You need $f$ convex and nondecreasing composed with $g$ convex, or $g$ affine.

Quadratic Forms and PSD#

A quadratic form $f(x) = x^T Q x$ is convex if and only if $Q$ is symmetric and positive semidefinite (PSD): all its eigenvalues are $\geq 0$, or equivalently $v^T Q v \geq 0$ for all vectors $v$. (For a non-symmetric $Q$, only its symmetric part $\tfrac{1}{2}(Q + Q^T)$ matters, since $x^T Q x = x^T \tfrac{1}{2}(Q + Q^T) x$.)

More generally, $f(x) = \frac{1}{2} x^T Q x + c^T x + d$ has Hessian $\nabla^2 f(x) = Q$. So:

• $Q \succeq 0$ (all eigenvalues $\geq 0$) → $f$ is convex
• $Q \succ 0$ (all eigenvalues $> 0$) → $f$ is strictly convex
• $Q$ has a negative eigenvalue → $f$ is nonconvex

Worked example: Is $f(x_1, x_2) = 3x_1^2 + 2x_2^2 + 2x_1 x_2$ convex?

Write as $f(x) = x^T Q x$ where $Q = \begin{pmatrix} 3 & 1 \\ 1 & 2 \end{pmatrix}$. The eigenvalues solve $\det(Q - \lambda I) = (3-\lambda)(2-\lambda) - 1 = \lambda^2 - 5\lambda + 5 = 0$, giving $\lambda = \frac{5 \pm \sqrt{5}}{2} \approx 3.618$ and $1.382$. Both are positive, so $f$ is convex (in fact, strictly convex).

This connects directly to Linear Algebra's eigendecomposition material — $Q = V \Lambda V^T$ tells you everything about the curvature of $f$ along each principal direction.

Local = Global#

Theorem: For a convex function $f$, any local minimum is also a global minimum.

Proof sketch: Suppose $x^*$ is a local minimum but not global — there exists $y$ with $f(y) < f(x^*)$. By convexity, for small $\theta$:

$f((1-\theta)x^* + \theta y) \leq (1-\theta)f(x^*) + \theta f(y) < f(x^*)$

But points $(1-\theta)x^* + \theta y$ are arbitrarily close to $x^*$ for small $\theta$, contradicting that $x^*$ is a local minimum. $\square$

Why this matters: If you can prove your loss function is convex (e.g., linear regression with squared error, logistic regression with cross-entropy), then gradient descent — if it converges at all — is converging to a global optimum. You never have to worry about getting stuck in a bad local minimum.

For nonconvex objectives (deep nets, Week 13), this guarantee vanishes. That's why nonconvex optimization is a different, messier game.

Knowledge Check#

Browser lab: tangents and the first-order condition#

Plot three convex functions and one nonconvex function on the same axes, and verify the first-order condition: the tangent line at any point always lies below a convex function's graph.

import numpy as np
import matplotlib.pyplot as plt

def f1(x): return x**2
def f2(x): return np.exp(x)
def f3(x): return -np.log(x)   # domain: x > 0
def f4(x): return x**3 - 3*x

x0 = 2.0

fig, axes = plt.subplots(2, 2, figsize=(10, 8))
axes = axes.flat

for ax, fn, name, grad_fn, xr in [
    (axes[0], f1, "$x^2$", lambda x: 2*x, (-2.0, 4.0)),
    (axes[1], f2, "$e^x$", lambda x: np.exp(x), (-2.0, 4.0)),
    (axes[2], f3, "$-\\log x$", lambda x: -1/x, (0.05, 4.0)),
    (axes[3], f4, "$x^3-3x$", lambda x: 3*x**2 - 3, (-2.0, 4.0)),
]:
    xs = np.linspace(*xr, 300)
    ys = fn(xs)
    ax.plot(xs, ys, label=name)
    tangent = fn(x0) + grad_fn(x0) * (xs - x0)
    ax.plot(xs, tangent, "--", color="tab:orange", label=f"tangent at x={x0}")
    ax.axvline(x0, color="gray", linewidth=0.5, linestyle=":")
    ax.legend(fontsize=9)
    ax.set_title(f"{'Convex' if name != '$x^3-3x$' else 'Nonconvex'}: {name}")

plt.tight_layout()
plt.show()

print("Notice: for the three convex panels the tangent line stays below (or touches) the curve —")
print("        that is the first-order condition. For x^3-3x the tangent crosses the curve.")

Further Reading#

• Stephen Boyd & Lieven Vandenberghe, Convex Optimization (Cambridge University Press, 2004). Chapter 2 covers convex sets and Chapter 3 covers convex functions, including the operations that preserve convexity. Freely available at stanford.edu/~boyd/cvxbook.
• Yurii Nesterov, Introductory Lectures on Convex Optimization (Springer, 2004). Chapter 2 is the standard reference for smooth and strongly convex functions and the definitions used in Week 3.
• Sébastien Bubeck, Convex Optimization: Algorithms and Complexity (2015). Sections 2–3 give a concise, free treatment of convexity and the first-order condition. Available at arXiv:1405.4980.
• Jorge Nocedal & Stephen Wright, Numerical Optimization (2nd ed., Springer, 2006). Chapter 2 collects the convexity fundamentals practitioners need before touching algorithms.