Mathematics.

optimization theory

Convex Optimization

Mathematical Optimization75 minDifficulty7 out of 10

You should know: convex functions, lagrange multipliers

Overview

Convex optimization is the study of minimizing convex functions over convex sets. It occupies a special place in optimization because local optima are guaranteed to be global optima, and a rich theory — KKT conditions, duality, interior-point methods — provides both theoretical insights and practical algorithms. Convex optimization problems arise throughout signal processing, machine learning, finance, control theory, and combinatorics (via relaxations).

Intuition

In a convex optimization problem, the landscape has no 'false valleys' — any valley you find is the deepest one globally. This means gradient descent and its variants are guaranteed to converge to the optimal solution, and you can trust certificates of optimality provided by dual variables.

Formal Definition

Definition

A convex optimization problem in standard form minimizes a convex objective over a convex feasible set defined by convex inequalities and affine equalities:

min⁡xf0(x)s.t.fi(x)≤0,i=1,…,mAx=b\begin{aligned} \min_{x} \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x) \le 0, \quad i = 1,\ldots,m \\ & Ax = b \end{aligned}
Standard form convex program
(Convexity requirements: f0,f1,…,fm convex; equality constraints affine)\text{(Convexity requirements: } f_0, f_1,\ldots,f_m \text{ convex; equality constraints affine)}
Problem structure
x∗ is optimal  ⟺  ∇f0(x∗)T(y−x∗)≥0∀y∈Fx^* \text{ is optimal} \iff \nabla f_0(x^*)^T(y - x^*) \ge 0 \quad \forall y \in \mathcal{F}
Optimality condition (unconstrained feasible set direction)

Notation

NotationMeaning
p∗=inf⁡x∈Ff0(x)p^* = \inf_{x \in \mathcal{F}} f_0(x)Optimal value
x∗x^*Optimal point (minimiser)
F\mathcal{F}Feasible set
L(x,λ,ν)=f0(x)+∑iλifi(x)+νT(Ax−b)L(x,\lambda,\nu) = f_0(x) + \sum_i \lambda_i f_i(x) + \nu^T(Ax-b)Lagrangian

Properties

Global optimality

Any local minimum of a convex optimization problem is a global minimum\text{Any local minimum of a convex optimization problem is a global minimum}

Optimality via subgradient

x∗ minimises f0 over convex C  ⟺  0∈∂f0(x∗)+NC(x∗)x^* \text{ minimises } f_0 \text{ over convex } C \iff 0 \in \partial f_0(x^*) + N_C(x^*)

Strong duality (Slater condition)

If ∃ x^:fi(x^)<0 (Slater point), then strong duality holds: p∗=d∗\text{If } \exists\, \hat{x}: f_i(\hat{x}) < 0 \text{ (Slater point), then strong duality holds: } p^* = d^*

Worked Examples

  1. 1

    The objective f(x,y)=x²+y² is strictly convex (bowl) and the constraint is linear, so there's a unique minimum.

    min⁡x+y=1x2+y2\min_{x+y=1} x^2 + y^2
  2. 2

    By symmetry the minimum is at x=y=1/2 (midpoint of the constraint line).

    x∗=y∗=12x^* = y^* = \tfrac{1}{2}
  3. 3

    Verify via Lagrangian: ∇f = λ∇g gives (2x,2y)=λ(1,1), so x=y. With x+y=1: x=y=1/2.

    p∗=(12)2+(12)2=12p^* = \left(\tfrac{1}{2}\right)^2 + \left(\tfrac{1}{2}\right)^2 = \tfrac{1}{2}

✓ Answer

Optimal solution x* = y* = 1/2 with value p* = 1/2.

Practice Problems

Mediumfree response

Formulate the portfolio optimization problem (minimise variance subject to target return and budget constraints) as a convex program and identify the type.

Common Mistakes

Common Mistake

Thinking any optimisation problem with a convex objective is a convex problem

A convex optimization problem requires both a convex objective AND a convex feasible set. A convex objective over a non-convex feasible set can have many local minima.

Quiz

Slater's condition is sufficient for:

Historical Background

Linear programming (1947) was the first large-scale convex optimization problem to be solved algorithmically. Interior-point methods, developed by Karmarkar (1984) and extended by Nesterov and Nemirovskii in the 1990s, showed that convex optimization problems can be solved in polynomial time with the same efficiency as linear programs.

  1. 1947

    Dantzig introduces linear programming and the simplex method

    George Dantzig

  2. 1984

    Karmarkar introduces polynomial-time interior-point algorithm for LP

    Narendra Karmarkar

  3. 1994

    Nesterov and Nemirovskii publish Interior-Point Polynomial Algorithms in Convex Programming

    Yurii Nesterov, Arkadi Nemirovskii

Summary

  • A convex optimization problem minimises a convex function over a convex feasible set.
  • Local optima are global optima — the key property enabling reliable algorithms.
  • KKT conditions are necessary and sufficient for optimality when Slater's condition holds.
  • Interior-point methods solve convex programs in polynomial time.

References

  1. BookBoyd, S. and Vandenberghe, L. — Convex Optimization (2004). Free at https://web.stanford.edu/~boyd/cvxbook/
  2. WebsiteWikipedia — Convex optimization