Convex Optimization

📐 Convex Optimization

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. It is the “gold standard” of optimization because any local minimum is also a global minimum.

🟢 1. Convex Sets and Functions

Convex Sets

A set $C$ is convex if the line segment between any two points in $C$ lies entirely within $C$ . $\forall x, y \in C, \forall \theta \in [0, 1]: \theta x + (1-\theta)y \in C$ Examples: Hyperplanes, half-spaces, and norm balls.

Convex Functions

A function $f: \mathbb{R}^n \to \mathbb{R}$ is convex if its domain is a convex set and for all $x, y$ in its domain: $f(\theta x + (1-\theta)y) \le \theta f(x) + (1-\theta)f(y)$ Geometrically, this means the line segment connecting $(x, f(x))$ and $(y, f(y))$ lies above the graph of $f$ .

🟡 2. The Optimization Problem

A standard convex optimization problem is written as: $\text{minimize } f_0(x)$ $\text{subject to } f_i(x) \le 0, \quad i = 1, \dots, m$ $a_j^T x = b_j, \quad j = 1, \dots, p$ Where $f_0, \dots, f_m$ are convex functions.

Why Convexity Matters

Global Optimality: No local minima to get stuck in.
Efficient Algorithms: Interior-point methods can solve these problems to very high precision in polynomial time.
Duality: We can often find a “dual” problem that provides a lower bound on the optimal value.

🔴 3. Duality and KKT

The Lagrangian

The Lagrangian associates a multiplier with each constraint: $L(x, \lambda, \nu) = f_0(x) + \sum \lambda_i f_i(x) + \sum \nu_j (a_j^T x - b_j)$

Dual Problem

The Lagrange dual function $g(\lambda, \nu) = \inf_x L(x, \lambda, \nu)$ is always concave. The dual problem is to maximize $g$ subject to $\lambda \ge 0$ .

Weak Duality: $d^* \le p^*$ (The dual optimum is always less than or equal to the primal optimum).
Strong Duality: $d^* = p^*$ (Usually holds for convex problems).