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:

| Function | Convex on | Why | |---|---|---| | $f(x) = x^2$ | $\mathbb{R}$ | Parabola opens upward | | $f(x) = e^x$ | $\mathbb{R}$ | Second derivative $e^x > 0$ everywhere | | $f(x) = x \log x$ | $x > 0$ | Second derivative $1/x > 0$ | | $f(x) = \|x\|_2^2$ | $\mathbb{R}^d$ | Quadratic form with $Q = I \succ 0$ | | $f(x) = -\log x$ | $x > 0$ | Second derivative $1/x^2 > 0$ | | Logistic loss | $\mathbb{R}^d$ | Hessian is PSD (Week 5) | | $f(x) = x^3$ | NOT convex | Second derivative changes sign at 0 | | $f(x) = -x^2$ | NOT convex | Concave — parabola opens downward |

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 (PSD) for all $x$.

Quadratic Forms and PSD#

A quadratic form $f(x) = x^T Q x$ is convex if and only if the symmetric matrix $Q$ is positive semidefinite (PSD): all its eigenvalues are $\geq 0$, or equivalently $v^T Q v \geq 0$ for all vectors $v$.

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.

Browser lab#

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

xs = np.linspace(-2, 4, 300)

def f1(x): return x**2
def f2(x): return np.exp(x)
def f3(x): return -np.log(np.maximum(x, 1e-6))
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 in [
    (axes[0], f1, "$x^2$", lambda x: 2*x),
    (axes[1], f2, "$e^x$", lambda x: np.exp(x)),
    (axes[2], f3, "$-\\log x$", lambda x: -1/x),
    (axes[3], f4, "$x^3-3x$", lambda x: 3*x**2 - 3),
]:
    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("First three: tangent below curve ✓ (convex)")
print("Last one:    tangent crosses curve ✗ (nonconvex)")