Optimization Difficulty: Intermediate

Convex Sets and Functions

Convex optimization problems have the property that any local minimum is a global minimum. This makes them tractable and foundational for machine learning, control, and finance.

Key Points

  • A set is convex if the line segment between any two points lies in the set.
  • A function is convex if its epigraph is a convex set, equivalently $f(\lambda x + (1-\lambda)y) \le \lambda f(x) + (1-\lambda)f(y)$.
  • Convex problems can be solved efficiently with interior-point methods and first-order methods.

Formulas

Convex function
$$f(\lambda x + (1-\lambda) y) \le \lambda f(x) + (1-\lambda) f(y), \quad \lambda \in [0,1]$$
Convex set
$$x, y \in C \implies \lambda x + (1-\lambda) y \in C$$
Jensen's inequality
$$f(\mathbb{E}[X]) \le \mathbb{E}[f(X)] \text{ for convex } f$$

Code Example

import numpy as np

def f(x):
    return x**2  # convex

def check_convex(f, x, y, lam):
    return f(lam*x + (1-lam)*y) <= lam*f(x) + (1-lam)*f(y)

print(check_convex(f, -1.0, 2.0, 0.5))  # True

Tags

  • convexity
  • global-optimum

References

  • Convex Optimization
    Stephen Boyd and Lieven Vandenberghe · Cambridge University Press · source
  • Convex Analysis
    Ralph T. Rockafellar · Princeton University Press · source

Knowledge Graph