Convex Optimization and Applications in Machine Learning

Contents

• Introduction and overview
• 0. Review: norms, symmetric matrices and smooth functions
• 1. Convex sets
• 2. Convex functions and convex analysis
• 3. Convex optimization problems
• 4. Duality
• 5. First-order methods and acceleration
• 6. Newton’s method and interior-point methods
• 7. Self-concordance and complexity
• 8. Applications: statistics, learning, finance and signal processing
• 9. Combinatorial problems and convex relaxations
• 10. Complements for self-study
• 11. Research directions and open problems
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: a student with a good M1 in mathematics, computer science or physics who has already run gradient descent or called an optimization solver, and now wants to recognise convex problems, write their duals and know what the algorithms guarantee.

Empirical first: on a least-squares problem in dimension 500 with condition number 10^4, a thousand steps of gradient descent bring the gap f - f^* from 23.9 down to 0.012. Nesterov’s accelerated method uses the same thousand gradients, plus one line of code, and reaches 3.9 \times 10^{-6} (code in ch. 5).

An interior-point method solves a linear program with 100 constraints to eight digits in 54 Newton steps (ch. 6). Why the first method is slow, why the second is optimal, and why the third barely depends on the data are the questions of this course.

The course teaches how to recognise a convex problem, how to rewrite it in one of a few standard forms (linear, quadratic, second-order cone and semidefinite programs), how to read its dual, and how the two families of algorithms that solve it work: first-order methods, which scale to huge problems, and interior-point methods, which reach high accuracy in few iterations. It ends with applications in statistics, learning, finance and signal processing, and with convex relaxations of combinatorial problems.

It shares tools with Introduction to Statistical Learning and Foundations of Distributed and Large-Scale Computing Optimization, and prepares Kernel Methods, Inverse Problems and Imaging and Sequential Learning.

What you will be able to do

• Recognise convex sets and functions, and prove convexity with the operations that preserve it.
• Compute projections, conjugate functions, subgradients and proximal operators of the functions used in machine learning.
• Rewrite a modelling problem as a linear, quadratic, second-order cone or semidefinite program.
• Derive the Lagrange dual of a convex program, check Slater’s condition, and solve the KKT conditions of small problems by hand.
• Prove the convergence rates of gradient, subgradient, proximal and accelerated methods, and explain why Nesterov’s rate cannot be improved.
• Implement Newton’s method and a barrier interior-point method, and bound their number of iterations with self-concordance.
• Formulate the LASSO, logistic regression, portfolio selection, robust constraints, total-variation denoising and sparse recovery as convex programs, and solve them.
• Build the semidefinite relaxation of a combinatorial problem and round it, with the Goemans–Williamson guarantee for MAXCUT.
• Read dual variables as certificates of optimality and as sensitivities of the optimal value.

Official objectives and syllabus (2026–2027)

The course description on master-mva.com states one objective: to learn to recognise, manipulate and solve a relatively broad class of convex problems that arise in fields such as learning, finance or signal processing. It lists its themes under three headings (convex modelling, algorithms, applications), announces 6 lectures of 3 hours, an exam, and three reference books. The Université Paris-Saclay course detail gives the type of assessment and the volume, with no programme of its own.

Every official topic is taught on this page. The extensions beyond the syllabus are the review of ch. 0, the proximal methods of ch. 5, and two self-study chapters: complements (the complete lower-bound proof, Frank–Wolfe, primal–dual interior-point methods) in ch. 10, and research directions in ch. 11.

Where this course fits in the programme

Official prerequisites: notions of linear algebra. The page also uses multivariable calculus at M1 level; ch. 0 reviews everything that is needed.

• Refreshers — Linear Algebra, Analysis and Optimization (eigenvalues, positive semidefinite matrices, gradients: the material of ch. 0), Scientific Python (NumPy and SciPy, used in every code block) and Probability and Statistics (for the statistical models of ch. 8 and the randomized rounding of ch. 9).
• Related courses of semester 1 — Introduction to Statistical Learning studies the convex surrogate losses whose minimization is the subject here. Foundations of Distributed and Large-Scale Computing Optimization develops stochastic and distributed versions of the methods of ch. 5. Optimal Transport for Machine Learning starts from a linear program and its dual. Computational Statistics and Theoretical Foundations of Deep Learning use the convex analysis of gradient methods as their baseline.
• Courses of semester 2 that build on it — Kernel Methods (SVM duals and quadratic programs), Inverse Problems and Imaging (total variation, \ell_1 penalties, proximal algorithms), Sequential Learning (online convex optimization), Graphical Models: Discrete Inference and Learning (linear-programming relaxations of MAP inference), Algorithms for Network Optimization and Management (linear programming and network flows) and Reinforcement Learning (the linear-programming view of Markov decision processes).

Course outline

• 0. Review — dual norms, the spectral theorem and Schur complements, Taylor’s formula and the descent lemma, Fermat’s rule.
• 1. Convex sets — the catalogue of convex sets, operations that preserve convexity, projection, separation and dual cones.
• 2. Convex functions and convex analysis — first- and second-order tests, operations, conjugates, subgradients, smoothness and strong convexity.
• 3. Convex optimization problems — standard form, global optimality, modelling transformations, and the hierarchy LP, QP, SOCP, SDP.
• 4. Duality — Lagrange duality, Slater’s theorem, KKT conditions, sensitivity, conic duality.
• 5. First-order methods and acceleration — gradient descent, the lower complexity bound, Nesterov’s method, subgradient and proximal methods.
• 6. Newton’s method and interior-point methods — Newton’s method, equality constraints, the logarithmic barrier, the central path and the barrier method.
• 7. Self-concordance and complexity — the affine-invariant analysis of Newton’s method and the polynomial complexity of path-following methods.
• 8. Applications — statistics and learning, finance, signal processing: models, solvers and dual variables.
• 9. Combinatorial problems and convex relaxations — Lagrangian and semidefinite relaxations, MAXCUT and Goemans–Williamson rounding, convex envelopes.
• 10. Complements for self-study — the proof of the lower bound, the Frank–Wolfe method, primal–dual interior-point methods, mirror descent.
• 11. Research directions and open problems — computer-aided analysis of algorithms, restarts, fast interior-point methods, low-rank semidefinite programming, tightness of relaxations.

Session plan

21 h in class = 7 sessions of 3 h. The volume is the official one of the Université Paris-Saclay programme table: 21 h of lectures. master-mva.com announces 6 lectures of 3 h, that is 18 h; the plan keeps lectures of 3 h and gives the remaining 3 h to a seventh session on applications and convex relaxations. This split, and the content of each session, is a proposal.

Level 1 = foundations, 2 = core results and algorithms, 3 = advanced and research-level material. The level never goes down from one session to the next.

Self-study, outside the 21 h (about 6 h in total): ch. 10 Complements: proof of the lower bound, Frank–Wolfe, primal–dual interior-point methods, mirror descent (≈ 3 h, with Ex. 14) · ch. 11 Research directions and open problems (≈ 3 h, with Ex. 15 and 16).

How to study this module

• Read ch. 0 before the first session if eigenvalues or Taylor’s formula feel distant: every proof of ch. 2, 5 and 7 uses them.
• After each session, redo the complete proofs without looking (Theorems 1.4, 2.2, 4.4, 4.6, 5.2, 5.5 and 7.4 are the core), then do the exercises listed in the row of the session.
• Run the code of each chapter and change one parameter (condition number, step, \mu, sparsity): the printed numbers are quoted in the text, so you can check your environment.
• The code uses only NumPy, SciPy and scikit-learn on synthetic data; every block runs in a few seconds on a laptop. Modelling tools such as CVXPY are not needed: the point is to see what they do inside.
• Keep a one-page sheet with the conjugates of Example 2.7, the four standard forms of Definition 3.3 and the KKT conditions: the exam tests whether you can use them quickly.

0. Review: norms, symmetric matrices and smooth functions

Convex optimization uses three M1 tools constantly: norms and their duals, symmetric matrices and their eigenvalues, and Taylor expansions of smooth functions. This chapter states them in the form used later.

The Linear Algebra, Analysis and Optimization refresher covers the same ground at a slower pace.

Norms and dual norms

Symmetric matrices

Gradients, Hessians and smoothness

Optimality without inequality constraints

1. Convex sets

Every convex program optimizes over a convex set, and every duality argument rests on separating convex sets by hyperplanes. This chapter lists the convex sets used in the course, the operations that preserve convexity, and the two geometric tools: projection and separation.

Projection and separation

import numpy as np

def proj_simplex(v):
    """Euclidean projection of v onto {x >= 0, sum(x) = 1} (sort-based)."""
    u = np.sort(v)[::-1]
    css = np.cumsum(u) - 1.0
    k = np.arange(1, v.size + 1)
    rho = np.nonzero(u - css / k > 0)[0][-1]   # last index with a positive entry
    tau = css[rho] / (rho + 1)
    return np.maximum(v - tau, 0.0)

rng = np.random.default_rng(0)
v = rng.normal(size=6)
p = proj_simplex(v)
print("v      =", np.round(v, 3))
print("P(v)   =", np.round(p, 3), " sum =", p.sum().round(12))

# Check the obtuse-angle characterization (Theorem 1.4) on random simplex points
Z = rng.dirichlet(np.ones(6), size=10_000)
print("max_z (v - P(v))^T (z - P(v)) =", ((Z - p) @ (v - p)).max().round(12))

2. Convex functions and convex analysis

Convex functions are the objectives and constraints of convex programs. This chapter gives the tests that recognise them, the operations that build new ones, and the three objects of convex analysis that every algorithm uses: the conjugate, the subdifferential, and the smoothness and strong-convexity constants.

Conjugate functions

Subgradients

Smoothness and strong convexity

3. Convex optimization problems

A convex program minimizes a convex function over a set described by convex inequalities and affine equalities. This chapter gives the standard form, the property that makes these problems tractable (every local minimum is global), and the hierarchy of conic programs into which modelling translates applied problems.

Equivalent problems

Modelling means rewriting a problem until a standard form appears. Four transformations are used constantly.

• Epigraph form: minimize t subject to f_0(x) \le t and the constraints, which makes the objective linear.
• Slack variables: an affine inequality a^\top x \le b becomes a^\top x + s = b with s \ge 0.
• Splitting: x = x^+ - x^- with x^\pm \succeq 0 linearizes absolute values.
• New variables: \min_x \sum_i |a_i^\top x - b_i| becomes the linear program \text{minimize } \mathbf{1}^\top t \quad \text{s.t.} \quad -t \preceq Ax - b \preceq t .

The conic hierarchy

import numpy as np
from scipy.optimize import linprog

# Polyhedron {x : a_i^T x <= b_i}: a triangle cut by a fourth half-plane
A = np.array([[-1.0, 0.0], [0.0, -1.0], [1.0, 1.0], [1.0, -2.0]])
b = np.array([0.0, 0.0, 4.0, 2.0])

# Chebyshev centre: maximize r s.t. a_i^T x + r ||a_i||_2 <= b_i  (variables x1, x2, r)
norms = np.linalg.norm(A, axis=1)
res = linprog(c=[0, 0, -1], A_ub=np.c_[A, norms], b_ub=b,
              bounds=[(None, None), (None, None), (0, None)], method="highs")
xc, r = res.x[:2], res.x[2]
print("centre =", np.round(xc, 4), " radius =", round(r, 4))
print("slacks b - A xc - r||a|| =", np.round(b - A @ xc - r * norms, 4))
print("dual variables (marginals) =", np.round(-res.ineqlin.marginals, 4))

4. Duality

Every optimization problem comes with a dual: a concave maximization whose value bounds the primal optimum from below. When the bound is tight, the dual variables certify optimality, measure the sensitivity of the optimum to the constraints, and often give a simpler problem to solve.

import numpy as np

alpha = np.array([0.2, 0.5, 0.9, 1.6])          # noise levels of 4 channels
def x_of(nu):                                   # KKT solution for a given multiplier
    return np.maximum(0.0, 1.0 / nu - alpha)

lo, hi = 1e-6, 1e6                              # bisection on the "water level" 1/nu
for _ in range(200):
    nu = np.sqrt(lo * hi)
    lo, hi = (nu, hi) if x_of(nu).sum() > 1.0 else (lo, nu)
x = x_of(nu)
lam = nu - 1.0 / (alpha + x)                    # multipliers of x >= 0
print("water level 1/nu =", round(1 / nu, 4))
print("x* =", np.round(x, 4), " sum =", round(x.sum(), 6))
print("lambda* =", np.round(lam, 4) + 0.0)        # + 0.0 turns -0.0 into 0.0
print("complementary slackness max |lambda_i x_i| =", np.abs(lam * x).max().round(10))
print("optimal value =", round(-np.log(alpha + x).sum(), 4))

5. First-order methods and acceleration

When the dimension is large, a Newton step costs too much and one uses gradients only. This chapter proves how fast gradient methods converge, shows that no gradient method can beat a rate of order 1/k^2 on smooth convex functions, and gives Nesterov’s method, which attains it. Proximal versions extend everything to nonsmooth regularizers.

Nesterov’s accelerated gradient method

import numpy as np

rng = np.random.default_rng(0)
n = 500
Q, _ = np.linalg.qr(rng.normal(size=(n, n)))
eig = np.logspace(-4, 0, n)                     # mu = 1e-4, L = 1: condition number 1e4
H = (Q * eig) @ Q.T
xstar = rng.normal(size=n)
f = lambda x: 0.5 * (x - xstar) @ H @ (x - xstar)  # f* = 0
grad = lambda x: H @ (x - xstar)
L, x0 = eig.max(), np.zeros(n)

def gd(K):
    x = x0.copy()
    for _ in range(K):
        x = x - grad(x) / L
    return f(x)

def agd(K):                                     # Nesterov, momentum k/(k+3)
    x_prev = x = y = x0.copy()
    for k in range(K):
        x_prev, x = x, y - grad(y) / L
        y = x + k / (k + 3) * (x - x_prev)
    return f(x)

R2 = np.sum((x0 - xstar) ** 2)
print(f"f(x0) = {f(x0):.3f}")
for K in (10, 100, 1000):
    print(f"K={K:5d}  GD {gd(K):.2e}  AGD {agd(K):.2e}  "
          f"bound L R^2/(2K) {L * R2 / (2 * K):.2e}  bound 2LR^2/(K+1)^2 {2 * L * R2 / (K + 1)**2:.2e}")

Nonsmooth functions: the subgradient method

Proximal gradient methods

6. Newton’s method and interior-point methods

Interior-point methods solve linear, second-order cone and semidefinite programs to high accuracy in a few dozen Newton steps. This chapter builds them in three moves: Newton’s method for smooth problems, its extension to equality constraints, and the logarithmic barrier that turns inequality constraints into a smooth penalty.

The logarithmic barrier and the central path

import numpy as np
from scipy.optimize import linprog

rng = np.random.default_rng(1)
m, n = 100, 50
A = rng.normal(size=(m, n))
b = rng.uniform(1, 2, size=m)                   # x = 0 is strictly feasible
c = -A.T @ rng.uniform(0, 1, size=m)            # c = -A^T lambda, lambda >= 0: LP is bounded

def centering(x, t, tol=1e-9, max_steps=50):
    """Newton's method with backtracking on t c^T x - sum log(b - A x)."""
    F = lambda z: t * c @ z - np.log(b - A @ z).sum()
    for steps in range(max_steps):
        d = 1.0 / (b - A @ x)
        g = t * c + A.T @ d
        Hs = A.T @ (A * d[:, None] ** 2)
        dx = -np.linalg.solve(Hs, g)
        lam2 = -g @ dx                          # Newton decrement squared
        if lam2 / 2 <= tol:
            break
        s = 1.0
        while np.min(b - A @ (x + s * dx)) <= 0:
            s *= 0.5                            # stay inside the domain
        while F(x + s * dx) > F(x) - 0.25 * s * lam2 and s > 1e-8:
            s *= 0.5                            # Armijo backtracking, alpha = 0.25
        x = x + s * dx
    return x, steps

x, t, mu, eps, total = np.zeros(n), 1.0, 20.0, 1e-7, 0
while True:                                     # Algorithm 6.7
    x, k = centering(x, t)
    total += k
    print(f"t = {t:9.1e}  Newton steps = {k:2d}  duality gap m/t = {m / t:.1e}")
    if m / t <= eps:                            # stopping rule of step 3
        break
    t *= mu
ref = linprog(c, A_ub=A, b_ub=b, bounds=[(None, None)] * n, method="highs")
print(f"barrier: {c @ x:.8f}   HiGHS: {ref.fun:.8f}   total Newton steps: {total}")

7. Self-concordance and complexity

The classical analysis of Newton’s method depends on constants m and M that change with the coordinates, although the method itself does not. Nesterov and Nemirovski (1994) found the affine-invariant condition that makes the analysis exact, self-concordance, and with it a polynomial bound on the number of Newton steps of interior-point methods.

import numpy as np

rng = np.random.default_rng(2)
m, n = 200, 20
A = rng.normal(size=(m, n))
b = rng.uniform(0.01, 1.0, size=m)              # x = 0 is strictly feasible, close to some faces
f = lambda x: -np.log(b - A @ x).sum()          # self-concordant (sum of -log of affine)

x, k = np.zeros(n), 0
while True:
    d = 1.0 / (b - A @ x)
    g, H = A.T @ d, A.T @ (A * d[:, None] ** 2)
    dx = -np.linalg.solve(H, g)
    lam = np.sqrt(-g @ dx)                      # Newton decrement lambda(x)
    print(f"k = {k:2d}  f = {f(x):10.6f}  lambda = {lam:.2e}")
    if lam < 1e-10:
        break
    step = 1.0 if lam < 0.25 else 1.0 / (1.0 + lam)   # damped phase, then pure Newton
    x, k = x + step * dx, k + 1
print("bound on damped steps: (f(x0) - f*) / omega(1/4) =",
      round((f(np.zeros(n)) - f(x)) / (0.25 - np.log(1.25)), 1))

Self-concordant barriers and the complexity of path following

8. Applications: statistics, learning, finance and signal processing

The official syllabus names three fields where convex programs arise. This chapter models a representative problem from each, solves it with the algorithms of ch. 5–7, and reads its dual variables.

Statistics and machine learning

import numpy as np
from sklearn.linear_model import Lasso

rng = np.random.default_rng(3)
n, p, s = 100, 300, 10
C = 0.9 ** np.abs(np.subtract.outer(np.arange(p), np.arange(p)))   # correlated features
X = rng.normal(size=(n, p)) @ np.linalg.cholesky(C).T
beta0 = np.zeros(p); beta0[::30] = rng.choice([-2.0, 2.0], size=s)
y = X @ beta0 + 0.5 * rng.normal(size=n)

lam_max = np.abs(X.T @ y).max() / n             # beta = 0 is optimal above this value
lam = 0.05 * lam_max
F = lambda b: 0.5 / n * np.sum((y - X @ b) ** 2) + lam * np.abs(b).sum()
L = np.linalg.norm(X, 2) ** 2 / n               # Lipschitz constant of the smooth part
soft = lambda v, a: np.sign(v) * np.maximum(np.abs(v) - a, 0.0)
step = lambda b: soft(b - X.T @ (X @ b - y) / (n * L), lam / L)

def ista(K):
    b = np.zeros(p)
    for _ in range(K):
        b = step(b)
    return b

def fista(K):
    b = z = np.zeros(p); t = 1.0
    for _ in range(K):
        b_new = step(z)
        t_new = (1 + np.sqrt(1 + 4 * t * t)) / 2
        z = b_new + (t - 1) / t_new * (b_new - b)
        b, t = b_new, t_new
    return b

ref = Lasso(alpha=lam, fit_intercept=False, tol=1e-14, max_iter=1_000_000).fit(X, y).coef_
Fstar = min(F(ref), F(fista(20000)))
print(f"lambda_max = {lam_max:.3f}, lambda = {lam:.4f}, L = {L:.1f}")
for K in (10, 100, 1000):
    print(f"K={K:5d}  ISTA gap {F(ista(K)) - Fstar:.1e}   FISTA gap {F(fista(K)) - Fstar:.1e}")
b = fista(20000)
print("nonzeros:", np.sum(np.abs(b) > 1e-6), " true support recovered:",
      set(np.flatnonzero(beta0)) <= set(np.flatnonzero(np.abs(b) > 1e-6)))
print("max |FISTA - sklearn| =", f"{np.abs(b - ref).max():.1e}")

Finance

Signal processing

import numpy as np
from scipy.optimize import linprog

rng = np.random.default_rng(4)
n, m = 200, 60                                   # unknowns, measurements
A = rng.normal(size=(m, n)) / np.sqrt(m)

def basis_pursuit(y):
    """min ||x||_1 s.t. Ax = y, as an LP in (u, v) with x = u - v, u, v >= 0."""
    res = linprog(np.ones(2 * n), A_eq=np.c_[A, -A], b_eq=y,
                  bounds=[(0, None)] * (2 * n), method="highs")
    return res.x[:n] - res.x[n:]

for s in (5, 10, 15, 20, 25):
    ok = 0
    for trial in range(20):
        x0 = np.zeros(n)
        x0[rng.choice(n, s, replace=False)] = rng.normal(size=s)
        ok += np.linalg.norm(basis_pursuit(A @ x0) - x0) < 1e-6 * np.linalg.norm(x0)
    print(f"sparsity s = {s:2d}: exact recovery in {ok:2d}/20 trials")

9. Combinatorial problems and convex relaxations

Many combinatorial problems are quadratic programs over \{-1, 1\}^n. Duality gives them a convex bound for free, and rounding the solution of that bound often gives a provably good feasible point. This chapter develops the semidefinite relaxation and the Goemans–Williamson algorithm for MAXCUT.

MAXCUT and randomized rounding

import itertools
import numpy as np

rng = np.random.default_rng(5)
n = 14
W = np.triu((rng.random((n, n)) < 0.5).astype(float), 1); W = W + W.T
Lap = np.diag(W.sum(1)) - W                     # cut(x) = x^T Lap x / 4 for x in {-1, 1}^n

# Dual SDP: minimize 1^T nu  s.t.  S(nu) = diag(nu) - Lap/4 >= 0, by the barrier method.
# t 1^T nu - log det S(nu) is self-concordant: damped Newton needs no line search.
def newton_center(nu, t):
    for _ in range(50):
        Sinv = np.linalg.inv(np.diag(nu) - Lap / 4)
        g, H = t - np.diag(Sinv), Sinv ** 2      # gradient and Hessian (Hadamard square)
        d = -np.linalg.solve(H, g)
        lam = np.sqrt(-g @ d)                    # Newton decrement
        if lam < 1e-6:                           # then f - f* <= lam^2 (Theorem 7.4)
            break
        nu = nu + (1.0 if lam < 0.25 else 1.0 / (1.0 + lam)) * d
    return nu

nu, t = np.full(n, np.linalg.eigvalsh(Lap / 4)[-1] + 1.0), 1.0
while True:
    nu = newton_center(nu, t)
    if n / t < 1e-5:
        break
    t *= 10
X = np.linalg.inv(np.diag(nu) - Lap / 4) / t    # primal point on the central path
sdp = np.trace(Lap @ X) / 4
print(f"SDP bound: dual {nu.sum():.5f}, primal {sdp:.5f}, gap {nu.sum() - sdp:.1e}, "
      f"max |diag(X) - 1| = {np.abs(X.diagonal() - 1).max():.1e}")

# Exact MAXCUT by enumeration (x_0 = +1 by symmetry)
best = max(np.array((1,) + s) @ Lap @ np.array((1,) + s) / 4
           for s in itertools.product((-1, 1), repeat=n - 1))

# Goemans-Williamson random-hyperplane rounding
w, U = np.linalg.eigh(X)
V = U * np.sqrt(np.maximum(w, 0))               # rows v_i with v_i . v_j = X_ij
cuts = [x @ Lap @ x / 4 for x in np.sign(rng.normal(size=(1000, n)) @ V.T)]
theta = np.linspace(1e-4, np.pi, 200_000)
alpha = np.min(2 / np.pi * theta / (1 - np.cos(theta)))
print(f"max cut = {best:.0f}, GW mean cut = {np.mean(cuts):.2f}, best of 1000 = {max(cuts):.0f}")
print(f"alpha_GW = {alpha:.5f}, guarantee alpha * SDP = {alpha * sdp:.2f}")

10. Complements for self-study

This chapter completes three threads of the course: the proof that Nesterov’s rate cannot be improved, two first-order methods that avoid projections or adapt to the geometry of the constraints, and the primal–dual interior-point methods used by solvers.

The lower complexity bound

Frank–Wolfe: optimization without projections

Each step solves a linear problem over C instead of a projection. On the \ell_1 ball the linear problem picks one signed vertex, so the iterates stay sparse; on the nuclear-norm ball it needs only the top singular pair (Jaggi 2013). In the code, Frank–Wolfe on an \ell_1-ball constrained least-squares problem with 200 variables has 14 nonzeros after 200 steps, with a certified gap of 0.30.

import numpy as np

# Nesterov's worst function f(x) = L/4 (x^T A x / 2 - x_1), A tridiagonal (2, -1), size p
L, K = 1.0, 50
p = 2 * K + 1
A = 2 * np.eye(p) - np.eye(p, k=1) - np.eye(p, k=-1)
f = lambda x: L / 4 * (0.5 * x @ A @ x - x[0])
grad = lambda x: L / 4 * (A @ x - np.eye(p)[0])
xstar = 1 - np.arange(1, p + 1) / (p + 1)
fstar = f(xstar)

x_prev = x = y = np.zeros(p)
for k in range(K):                              # accelerated gradient, x_0 = 0
    x_prev, x = x, y - grad(y) / L
    y = x + k / (k + 3) * (x - x_prev)
lower = 3 * L * xstar @ xstar / (32 * (K + 1) ** 2)
upper = 2 * L * xstar @ xstar / (K + 1) ** 2
print(f"K = {K}: lower bound {lower:.2e} <= AGD gap {f(x) - fstar:.2e} <= upper bound {upper:.2e}")
print("nonzero coordinates of x_K:", np.count_nonzero(np.abs(x) > 0), "out of", p)

# Frank-Wolfe on min ||Bz - c||^2 / 2 over the l1 ball of radius 1
rng = np.random.default_rng(6)
B, c = rng.normal(size=(50, 200)), rng.normal(size=50)
z = np.zeros(200)
for k in range(200):
    g = B.T @ (B @ z - c)
    i = np.argmax(np.abs(g))
    s = np.zeros(200); s[i] = -np.sign(g[i])     # linear minimization oracle: a vertex
    gap = g @ (z - s)                           # Frank-Wolfe duality gap >= f(z) - f*
    z = z + 2 / (k + 2) * (s - z)
print(f"Frank-Wolfe after 200 steps: gap {gap:.2e}, nonzeros {np.count_nonzero(z)}")

Mirror descent

Primal–dual interior-point methods

The iterates need not be feasible: the residuals shrink along the way. Mehrotra’s predictor–corrector (Mehrotra 1992) chooses \sigma adaptively from an affine-scaling step and adds a second-order correction; Wright (1997) gives the theory. The homogeneous self-dual embedding (Ye, Todd and Mizuno 1994) also detects infeasible or unbounded problems. The same ideas extend to SOCP and SDP through the symmetric-cone framework (Nesterov and Todd 1997).

11. Research directions and open problems

Convex optimization is a mature field whose questions are now about exact constants, scale, structure and the boundary with nonconvex problems. This chapter, for self-study, points to active lines of work with references that open each of them.

Exact worst cases and optimal step sizes

Work by Drori and Teboulle (2014) shows that the worst case of a first-order method on smooth convex functions is itself the value of a small semidefinite program, the performance estimation problem. Taylor, Hendrickx and Glineur (2017) make this exact through interpolation conditions, so that the best possible bound of a method can be computed.

This approach found the optimized gradient method of Kim and Fessler (2016), whose bound is about half of Nesterov’s, and Drori (2017) proved that no method does better. Altschuler and Parrilo (2023) show that plain gradient descent, with a fractal schedule of long steps, already beats the 1/k rate. The optimal step-size schedules of gradient descent without momentum are not yet known.

Restart, sharpness and adaptivity

Accelerated methods are not monotone and do not adapt to strong convexity. O’Donoghue and Candès (2015) restart them when the objective increases, and Roulet and d’Aspremont (2020) show that restart schemes adapt to sharpness, a growth condition weaker than strong convexity, with near-optimal rates.

Scieur, d’Aspremont and Bach (2016) accelerate any convergent sequence by nonlinear extrapolation, and the monograph of d’Aspremont, Scieur and Taylor (2021) surveys acceleration. Removing the need to know L without line search, as in the adaptive method of Malitsky and Mishchenko (2020), remains an active topic.

Interior-point methods at scale

On the theory side, Lee and Sidford (2014) solve linear programs in about \sqrt{\mathrm{rank}} iterations, and Cohen, Lee and Song (2021) in the time of matrix multiplication. Whether linear programming admits a strongly polynomial algorithm, with a number of operations independent of the size of the numbers, is open: it is Smale’s ninth problem.

In practice, very large LPs and conic programs are now solved by first-order primal–dual methods, such as the PDHG method of Chambolle and Pock (2011) in the PDLP solver (Applegate and coauthors 2021), the operator splitting of SCS (O’Donoghue, Chu, Parikh and Boyd 2016), and ADMM (Boyd, Parikh, Chu, Peleato and Eckstein 2011). How to reach interior-point accuracy at first-order cost is open.

Low-rank semidefinite programming

An SDP in n \times n matrices costs at least n^2 memory. Burer and Monteiro (2003) factor X = VV^\top with V of few columns and optimize V directly, a nonconvex problem.

Boumal, Voroninski and Bandeira (2016) show that, for generic smooth SDPs with m constraints, second-order critical points are optimal once the number of columns exceeds about \sqrt{2m}. Yurtsever, Tropp, Fercoq, Udell and Cevher (2021) combine Frank–Wolfe with sketching to store only a low-rank approximation.

When are convex relaxations tight?

Amelunxen, Lotz, McCoy and Tropp (2014) predict the phase transitions of convex recovery problems with random data, such as the one observed in ch. 8, from a single geometric quantity, the statistical dimension of a descent cone. Chandrasekaran, Recht, Parrilo and Willsky (2012) build convex penalties for general structured signals from atomic norms.

Phase retrieval can be relaxed to an SDP (Candès, Strohmer and Voroninski 2013) or written as a MAXCUT-like problem (Waldspurger, d’Aspremont and Mallat 2015). For community detection, the semidefinite relaxation reaches the information-theoretic threshold of exact recovery (Hajek, Wu and Xu 2016). Explaining when relaxations of higher levels of the sums-of-squares hierarchy help is a central question of average-case complexity.

Convex optimization inside learning systems

Amos and Kolter (2017) and Agrawal, Amos, Barratt, Boyd, Diamond and Kolter (2019) use convex programs as layers of neural networks, differentiating the solution through the KKT conditions (Theorem 4.6). Making such layers fast and robust when the problem is degenerate is open.

Questions to explore

• Find, with the performance estimation approach, the best constant step for gradient descent on smooth convex functions over k steps, and compare it with 1/L.
• For which random graphs does the MAXCUT relaxation of ch. 9 return a rank-one solution, so that rounding is not needed?
• Can a barrier method with Newton systems solved by conjugate gradients match the accuracy of an exact interior-point method on a large LP, and at what cost?
• How sharp is the Goemans–Williamson constant on graphs from applications rather than worst-case instances?

Exercises

Levels: ★ apply the course, ★★ combine results or prove a short statement, ★★★ open-ended or research-flavoured. Exercises 6, 13, 14, 15 and 16 are computational.

1. ★ Convex or not. Which of these sets are convex? (a) The slab \{x : a \le c^\top x \le b\}. (b) The points closer to a than to b, \{x : \|x - a\|_2 \le \|x - b\|_2\}. (c) \{x \in \mathbb{R}^2 : x_1 > 0, \ x_2 > 0, \ x_1 x_2 \ge 1\}. (d) \{x \in \mathbb{R}^2 : x_1^2 - x_2^2 \le 1\}.

   Solution: (a) Convex, an intersection of two halfspaces. (b) Convex: squaring, the condition is the halfspace 2(b - a)^\top x \le \|b\|_2^2 - \|a\|_2^2 .

   3. Convex: on the open quadrant it reads \log x_1 + \log x_2 \ge 0, a superlevel set of a concave function.

   4. Not convex: (2, 2) and (2, -2) belong to it, but their midpoint (2, 0) does not.

2. ★ Conjugates. Compute the conjugates of (a) |x| on \mathbb{R}; (b) the hinge \max(0, 1 - x); (c) the logistic loss \log(1 + e^x); (d) -\log\det X on positive definite matrices.

   Solution: (a) 0 on [-1, 1] and +\infty elsewhere (Example 2.7).

   2. f^*(y) = y on [-1, 0], and +\infty elsewhere.

   Indeed, the supremum is infinite for y > 0 (let x \to +\infty) and for y < -1 (let x \to -\infty).

   On [-1, 0], the concave piecewise-linear function x \mapsto yx - \max(0, 1 - x) is maximal at the kink x = 1.

   3. f^*(y) = y \log y + (1 - y)\log(1 - y) on [0, 1], with the convention 0 \log 0 = 0. The supremum is at x = \log(y / (1 - y)).

   4. f^*(Y) = -\log\det(-Y) - n on Y \prec 0. The computation is the same as for -\log x, with \nabla \log\det X = X^{-1}.

3. ★ The dual of \ell_\infty regression. Write \min_x \|Ax - b\|_\infty as minimize \|r\|_\infty subject to r = Ax - b, and derive its dual.

   Solution: the Lagrangian is \|r\|_\infty + \nu^\top (Ax - b - r). Minimizing over r gives 0 if \|\nu\|_1 \le 1 and -\infty otherwise (the conjugate of a norm, Example 2.7).

   Minimizing over x requires A^\top \nu = 0. With \nu \to -\nu the dual is \text{maximize } b^\top \nu \quad \text{s.t.} \quad \|\nu\|_1 \le 1, \ A^\top \nu = 0 . Strong duality holds (no inequality constraints), so a dual vector certifies the optimal value.

4. ★ Proximal operators. Compute (a) the proximal operator of \gamma times the indicator of the box [l, u]; (b) of \frac{\gamma\lambda}{2}\|x\|_2^2; (c) of \gamma \|x\|_2.

   Solution: (a) The projection, componentwise \min(\max(v_i, l_i), u_i). (b) v / (1 + \gamma\lambda), from the stationarity condition \gamma\lambda x + x - v = 0.

   3. Block soft thresholding: v \max(0, 1 - \gamma / \|v\|_2). By Proposition 2.9, the optimality condition is 0 \in \gamma \partial\|x\|_2 + x - v.

   If \|v\|_2 \le \gamma, then x = 0 works, with v/\gamma as subgradient. Otherwise x is a positive multiple of v, and its norm is \|v\|_2 - \gamma.

5. ★ Counting iterations. Let f be L-smooth and \mu-strongly convex, with L = 100 and \mu = 1.

   1. How many iterations of gradient descent does Theorem 5.2 need to divide \|x - x^*\|^2 by 10^6? How many with the contraction factor 1 - 1/\sqrt{\kappa} of accelerated methods?

   2. Without strong convexity, how many iterations do Theorems 5.2 and 5.5 need to guarantee the following accuracy? f(x_k) - f^* \le 10^{-6} L \|x_0 - x^*\|^2

   Solution: (a) Here \kappa = 100. Gradient descent needs k \ge \log(10^6) / (-\log 0.99) = 1374.6, so 1375 iterations.

   With the factor 0.9, the count is 13.82 / 0.105 = 131.1, so 132 iterations.

   2. Gradient descent needs k \ge 5 \times 10^5. The accelerated method needs (k + 1)^2 \ge 2 \times 10^6, that is k \ge 1414.

6. ★ The trade-off of the barrier parameter (computational). Run the barrier method of Example 6.8 with \mu \in \{2, 10, 50, 200, 1000\} and the same stopping rule. Count the centerings and the total number of Newton steps, and explain the result with Theorem 7.7.

   Hints and expected result: wrap the main loop in a loop over \mu. The code gives:

   \mu	2	10	50	200	1000
   centerings	31	10	7	5	4
   Newton steps	146	67	55	46	40

   The centerings follow the count of Algorithm 6.7. Small \mu wastes many cheap centerings. Large \mu makes each centering longer, but by far less than the bound m(\mu - 1 - \log\mu) of Theorem 7.7 suggests, so the total stays between 40 and 67 steps from \mu = 10 to \mu = 1000: the reason solvers use aggressive updates.

7. ★★ Schur complements and hyperbolic constraints. (a) Show that \{(x, y, t) : y > 0, \ x^\top x / y \le t\} is convex by writing it as a linear matrix inequality. (b) Show that, for x \in \mathbb{R}^n and y, z \in \mathbb{R}, \|x\|_2^2 \le yz, \ y \ge 0, \ z \ge 0 \iff \left\| \begin{pmatrix} 2x \\ y - z \end{pmatrix} \right\|_2 \le y + z .

   Solution: (a) By Proposition 0.3 with the block yI \succ 0, the condition is \begin{pmatrix} t & x^\top \\ x & y I \end{pmatrix} \succeq 0 , a linear matrix inequality in (x, y, t), whose solution set is convex (Proposition 1.3).

   2. Squaring, 4\|x\|^2 + (y - z)^2 \le (y + z)^2 is \|x\|^2 \le yz. The cone constraint implies y + z \ge |y - z|, that is y, z \ge 0, and conversely y, z \ge 0 make y + z nonnegative, so squaring is legitimate.

8. ★★ The dual of the support vector machine. Derive the dual of \text{minimize } \frac12 \|w\|_2^2 + C \sum_{i=1}^n \xi_i \quad \text{s.t.} \quad y_i (w^\top x_i + b) \ge 1 - \xi_i, \ \xi \succeq 0 , and use complementary slackness to describe the points with nonzero multipliers.

   Solution: with multipliers \alpha_i for the margin constraints and \beta_i for \xi_i \ge 0, stationarity gives w = \sum_i \alpha_i y_i x_i, \sum_i \alpha_i y_i = 0 and \alpha_i + \beta_i = C. The dual is \text{maximize } \sum_i \alpha_i - \frac12 \sum_{i, j} \alpha_i \alpha_j y_i y_j x_i^\top x_j \quad \text{s.t.} \quad 0 \le \alpha_i \le C, \ \sum_i \alpha_i y_i = 0 . \alpha_i > 0 only for points on or inside the margin (the support vectors), and \alpha_i < C forces \xi_i = 0. The data enter only through inner products, which Kernel Methods replaces by a kernel.

9. ★★ The dual of the LASSO and a stopping rule. Consider the LASSO objective P(\beta) = \frac12\|y - X\beta\|_2^2 + \lambda\|\beta\|_1 . Introduce r = y - X\beta, derive the dual, and turn any \beta into a certified suboptimality bound.

   Solution: with multiplier \theta for r = y - X\beta, minimizing over r gives r = \theta, and minimizing over \beta requires \|X^\top \theta\|_\infty \le \lambda (Example 2.7). The dual is \text{maximize } \frac12\|y\|_2^2 - \frac12\|y - \theta\|_2^2 \quad \text{s.t.} \quad \|X^\top \theta\|_\infty \le \lambda , and at the optimum \theta^* is the residual y - X\beta^*.

   For any \beta, the scaled residual \theta = r \min(1, \lambda / \|X^\top r\|_\infty) is dual feasible, and P(\beta) - g(\theta) bounds P(\beta) - P^*.

   Since \theta = y is feasible when \lambda \ge \|X^\top y\|_\infty, with g(y) = P(0), this recovers \lambda_{\max} of Example 8.2. There it is divided by n, because of the factor 1/(2n).

10. ★★ Step sizes for the subgradient method. (a) Among constant steps, show that \alpha = R / (G\sqrt{k + 1}) minimizes the bound of Theorem 5.7. (b) For \alpha_i = R / (G\sqrt{i + 1}), show a bound of order RG \log k / \sqrt{k}. (c) When f^* is known, show that the Polyak step \alpha_i = (f(x_i) - f^*) / \|g_i\|^2 also gives RG / \sqrt{k + 1}.

    Solution: (a) The bound (R^2 + (k + 1) G^2 \alpha^2) / (2(k + 1)\alpha) is minimal where its derivative in \alpha vanishes, at the given step, with value RG / \sqrt{k + 1}.

    2. \sum_{i \le k} 1/\sqrt{i+1} \ge 2(\sqrt{k + 2} - 1) and \sum_{i \le k} 1/(i+1) \le 1 + \log(k + 1), so the bound is at most \frac{RG \, (2 + \log(k + 1))}{4(\sqrt{k + 2} - 1)} .
    3. With this step, the expansion of Theorem 5.7 gives \|x_{i+1} - x^*\|^2 \le \|x_i - x^*\|^2 - \frac{(f(x_i) - f^*)^2}{G^2} . Summing, \sum_i (f(x_i) - f^*)^2 \le R^2 G^2. So the smallest squared gap is at most R^2 G^2 / (k + 1), which is the claim.

11. ★★ Self-concordance. (a) Show that if f is self-concordant, so is x \mapsto f(Ax + b).

    2. Show that -\log x - \log(1 - x) is a 2-self-concordant barrier for [0, 1], and compute its Newton decrement at x = 1/4.

    3. Show that e^x is not self-concordant on \mathbb{R}, and find the largest interval on which it is.

    Solution: (a) The restriction of f(Ax + b) to a line is the restriction of f to a line, and Definition 7.1 only involves lines.

    2. Each term is a 1-self-concordant barrier (f'^2 / f'' = 1 for -\log x), and the parameters add.

    At x = 1/4, f' = -4 + 4/3 = -8/3 and f'' = 16 + 16/9 = 160/9. So \lambda^2 = f'^2 / f'' = 0.4 \le 2, and \lambda = \sqrt{0.4} \approx 0.63.

    3. f''' = f'' = e^x, and e^x \le 2 e^{3x/2} holds exactly when x \ge -2\log 2. So e^x is self-concordant on (-2\log 2, \infty) only.

12. ★★ The efficient frontier. Without the constraint w \succeq 0, minimize w^\top \Sigma w subject to \mathbf{1}^\top w = 1 and \bar r^\top w = r, with \Sigma \succ 0.

    Let a = \mathbf{1}^\top \Sigma^{-1}\mathbf{1}, b = \mathbf{1}^\top \Sigma^{-1}\bar r and c = \bar r^\top \Sigma^{-1}\bar r. Show that the minimal variance is \sigma^2(r) = \frac{a r^2 - 2 b r + c}{a c - b^2} .

    Solution: stationarity gives w = \Sigma^{-1}(\lambda \mathbf{1} + \gamma \bar r) for some multipliers. The constraints become a\lambda + b\gamma = 1 and b\lambda + c\gamma = r, so \lambda = \frac{c - br}{ac - b^2}, \qquad \gamma = \frac{ar - b}{ac - b^2} . The variance is w^\top \Sigma w = \lambda + \gamma r, which is the formula. Its minimum, at r = b/a, is 1/a: the global minimum-variance portfolio \Sigma^{-1}\mathbf{1}/a.

13. ★★ MAXCUT on the 5-cycle (computational). For the cycle with 5 vertices and unit weights, show that the maximum cut is 4 and that the SDP value is (25 + 5\sqrt{5})/8. Check it with the code of Example 9.5.

    Solution: an odd cycle cannot be fully cut, and alternating labels cut 4 edges. Place v_k at angle 4\pi k / 5 on the unit circle: consecutive vectors make an angle 4\pi/5, so the SDP value is at least 5 \cdot \frac{1 - \cos(4\pi/5)}{2} = \frac{25 + 5\sqrt{5}}{8} \approx 4.5225 . The dual point \nu = \frac14 \lambda_{\max}(L)\mathbf{1} is feasible. With \lambda_{\max}(L) = 2 - 2\cos(4\pi/5) \approx 3.618, its value is the same 4.5225, so both are optimal.

    The code returns 4.52254 and X_{12} = -0.80902. The ratio 4/4.5225 = 0.8845 is close to \alpha_{\mathrm{GW}}.

14. ★★★ Frank–Wolfe or projections for low-rank matrices (computational). Generate a 200 \times 200 matrix of rank 5 and observe 20 % of its entries. Minimize the squared error on the observed entries over the nuclear-norm ball of radius \tau, (i) by projected gradient, with a full SVD per step, and (ii) by Frank–Wolfe, with only the top singular pair per step. Compare accuracy against time and the rank of the iterates.

    Hints and expected result: projecting on the nuclear-norm ball means projecting the singular values on an \ell_1 ball (Example 1.8 with a scaled simplex). Take \tau equal to the nuclear norm of the true matrix and the step 1/L with L = 1.

    After 300 iterations, runs with these sizes give a relative Frobenius error, against the true matrix, of about 7 % for projected gradient and about 10 % for Frank–Wolfe. The Frank–Wolfe iterations are three to four times cheaper (one call to scipy.sparse.linalg.svds with one singular pair). The k-th Frank–Wolfe iterate is a sum of k rank-one terms, which matters when n is large and k \ll n. Jaggi (2013) discusses these trade-offs.

15. ★★★ Restarting acceleration. (a) Let f be L-smooth and \mu-strongly convex. Combine Theorem 5.5 with Proposition 2.10 to show that restarting Algorithm 5.4 every \lceil\sqrt{8\kappa}\rceil steps at least halves f - f^*.

    Deduce a complexity of order \sqrt{\kappa}\log(1/\varepsilon).

    2. Implement fixed restarts and the adaptive restart of O’Donoghue and Candès (2015), which restarts when f increases, on the quadratic of Example 5.6.

    Hints and expected result: (a) Strong convexity gives \|x_0 - x^*\|^2 \le 2(f(x_0) - f^*)/\mu, so after k steps f(x_k) - f^* \le 4\kappa (f(x_0) - f^*)/(k + 1)^2, at most half when (k + 1)^2 \ge 8\kappa.

    2. With \kappa = 10^4 the period is 283. After 3000 gradients the gap is about 9 \times 10^{-8} without restart, 8 \times 10^{-16} with fixed restarts, and 5 \times 10^{-19} with adaptive restart. Adaptive restart needs no knowledge of \mu; Roulet and d’Aspremont (2020) extend restart schemes to sharp functions.

16. ★★★ The phase transition of basis pursuit (computational). With the code of Theorem 8.6, estimate the probability of exact recovery on a grid of (m/n, \, s/m) for n = 100. Compare with the prediction of Amelunxen, Lotz, McCoy and Tropp (2014): recovery succeeds when m exceeds the statistical dimension of the descent cone of \|\cdot\|_1, which is n\psi(s/n) with \psi(\rho) = \min_{\tau \ge 0} \Big\{ \rho(1 + \tau^2) + 2(1 - \rho)\big[(1 + \tau^2)\bar\Phi(\tau) - \tau\phi(\tau)\big] \Big\} . Here \phi and \bar\Phi are the standard Gaussian density and upper tail.

    Hints and expected result: the empirical transition is sharp and follows the curve. For the setting of ch. 8 (n = 200, m = 60), the statistical dimension equals 60 near s = 17, consistent with the observed drop between s = 15 (15 of 20 recovered) and s = 20 (4 of 20). Larger n makes the transition sharper.

Projects and assessment

The official assessment, on master-mva.com, is an exam (“Examen”), with no format or weight displayed. The Université Paris-Saclay course detail describes the assessment as “Evaluation Continue non Intégrale” (partial continuous assessment).

The written exam below is a proposal in the spirit of the official exam, for self-assessment. The projects are not part of the official assessment: they are paper studies at the scale of other MVA courses, for students who want to practise the methods on a real question, or to prepare a research internship in optimization.

Solo projects

1. [Solo · ≈ 20 h] Adaptive restart of accelerated methods. Can restarting recover the linear rate of acceleration without knowing the strong-convexity constant? A paper study of O’Donoghue and Candès (2015).
   • Implement: gradient descent, Algorithm 5.4, fixed-period restart, and the function and gradient restart schemes of the paper, plus the constant-momentum method when \mu is known.
   • Data: quadratics with condition numbers from 10^2 to 10^6, and \ell_2-regularized logistic regression on the breast-cancer data set bundled with scikit-learn (569 samples, 30 features, standardized before use).
   • Deliverables: code, 4–6 page report, 10-minute talk. Chapters: ch. 2, 5.
   • Success criterion: adaptive restart reaches a gap of 10^{-8} within a factor 2 of the number of gradients of the best fixed period, on every test problem.
2. [Solo · ≈ 20 h] A barrier solver for linear programs. How far can fifty lines of NumPy go against a production LP solver?
   • Implement: Algorithm 6.7 with a phase I problem, equality constraints through Proposition 6.4, and a certificate of infeasibility read from the dual of phase I.
   • Data: random feasible and infeasible LPs with 50 to 500 inequalities, and transportation problems with known optimum.
   • Deliverables: code, 4–6 page report, 10-minute talk. Chapters: ch. 4, 6, 7.
   • Success criterion: relative agreement 10^{-6} with HiGHS on 100 random instances; a plot of total Newton steps against the number of constraints that grows slowly, as in Boyd and Vandenberghe (2004, §11.3); every infeasible instance detected with a valid certificate.
3. [Solo · ≈ 20 h] Sparse inverse covariance estimation. How many samples does the penalized likelihood of ch. 8 need to recover the graph of a Gaussian model? A paper study of Banerjee, El Ghaoui and d’Aspremont (2008).
   • Implement: block coordinate descent on the dual problem, with a duality-gap stopping rule, for the penalty of ch. 8 (every entry of \Theta) and for the variant that leaves the diagonal unpenalized.
   • Data: synthetic Gaussian models on chain and grid graphs with 50 variables, sample sizes from 50 to 1000.
   • Deliverables: code, 4–6 page report, 10-minute talk. Chapters: ch. 2, 4, 8.
   • Success criterion: duality gap below 10^{-6}; for the variant with an unpenalized diagonal, which is the convention of scikit-learn, estimates within 10^{-4} of sklearn.covariance.graphical_lasso run with tol=1e-10; a curve of support recovery (F1 score) against sample size.

Group projects

1. [Group of 2–3 · ≈ 30 h each] MAXCUT at scale: interior points against low-rank factorization. How large a MAXCUT relaxation can be solved and rounded on a laptop? A paper study of Goemans and Williamson (1995) and Burer and Monteiro (2003).
   • Split: member A extends the barrier method of Example 9.5; member B implements the Burer–Monteiro factorization with unit-norm rows and a projected or Riemannian gradient; member C implements rounding with local search, and the experiments.
   • Data: random graphs G(n, 1/2), planted partitions and cycles, with n from 14 (exact enumeration) to 2000.
   • Deliverables: code, 8–10 page joint report, 20-minute talk. Chapters: ch. 6, 7, 9.
   • Success criterion: on graphs with at most 20 vertices, rounded cuts above 0.878 times the SDP bound and compared with the exact optimum; on the largest graphs, both SDP solvers agree to 10^{-4} where both run, and the factorization scales beyond.
2. [Group of 2–3 · ≈ 30 h each] Phase transitions of convex recovery. Does the statistical dimension predict where \ell_1 and \ell_\infty recovery succeed? A paper study of Amelunxen, Lotz, McCoy and Tropp (2014), with Donoho (2006).
   • Split: member A writes the solvers (basis pursuit and \ell_\infty recovery as LPs, and FISTA on a penalized version for speed); member B computes the statistical dimensions (Ex. 16 for \ell_1; for \ell_\infty at a sign vector it equals n/2); member C runs the experiments.
   • Data: Gaussian measurements of sparse vectors and of sign vectors, n from 100 to 400.
   • Deliverables: code, 8–10 page joint report, 20-minute talk. Chapters: ch. 3, 5, 8.
   • Success criterion: the empirical 50 % transition lies within 0.05 of the predicted curve (in m/n) over the whole grid.

Written exam (proposal)

Three hours, one handwritten A4 sheet allowed, no calculator needed; four independent questions.

1. Question (5 points). State Slater’s condition and the KKT conditions for a convex program with differentiable functions. Prove that a KKT point is primal optimal. Give a convex problem with a nonzero duality gap and say which hypothesis fails.

   Expected: Theorem 4.4 and the four conditions of Theorem 4.6. Proof: the Lagrangian is convex in x and stationary, so x minimizes it; complementary slackness gives g(\lambda, \nu) = f_0(x); weak duality concludes. Example 4.5, where no point is strictly feasible.

2. Question (6 points). Minimize \frac12\|x\|_2^2 subject to a^\top x \ge b, with a = (1, 2) and b = 2. (a) Solve the KKT conditions. (b) Derive and solve the dual, and check that the gap is zero. (c) Predict the optimal value for b = 2.1 with Proposition 4.7, and compare with the exact value.

   Expected: (a) Stationarity gives x^* = \lambda^* a, and the constraint is active, so \lambda^* = b/\|a\|^2 = 0.4. Hence x^* = (0.4, 0.8) and p^* = 0.4.

   2. Minimizing the Lagrangian at x = \lambda a gives the dual function g(\lambda) = \lambda b - \frac12 \lambda^2\|a\|^2 = 2\lambda - 2.5\lambda^2 , maximal at \lambda = 0.4 with value 0.4: the gap is zero.

   3. Prediction 0.4 + 0.4 \times 0.1 = 0.44; exact value b^2/(2\|a\|^2) = 0.441.

3. Question (5 points). Let f be convex and L-smooth with minimizer x^*. Prove that gradient descent with step 1/L satisfies f(x_k) - f^* \le L\|x_0 - x^*\|^2/(2k).

   Expected: the descent lemma with the step 1/L; convexity at x_k; the identity that turns the sum into \frac{L}{2}(\|x_k - x^*\|^2 - \|x_{k+1} - x^*\|^2); telescoping and monotonicity (Theorem 5.2).

4. Question (4 points). Write each problem as an LP, an SOCP or an SDP: (a) \min_x \|Ax - b\|_1; (b) \min_x \|Ax - b\|_2 + \|x\|_1.

   3. \min c^\top x subject to a^\top x \le 1 for all a with \|a - \bar a\|_2 \le \rho; (d) \min_x \lambda_{\max}(A_0 + \sum_i x_i A_i).

   Expected, one point each:

   • 1. LP: minimize \mathbf{1}^\top t s.t. -t \preceq Ax - b \preceq t.
   • 2. SOCP: minimize s + \mathbf{1}^\top u s.t. \|Ax - b\|_2 \le s and -u \preceq x \preceq u.
   • 3. SOCP: minimize c^\top x s.t. \bar a^\top x + \rho\|x\|_2 \le 1 (Example 3.5).
   • 4. SDP: minimize t s.t. A_0 + \sum_i x_i A_i \preceq tI.

Total: 5 + 6 + 5 + 4 = 20 points.

Grading rubric (proposal)

References

Official references of the course (master-mva.com):

• Boyd, S., and Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
• Nesterov, Y. (2004). Introductory Lectures on Convex Optimization: A Basic Course. Applied Optimization 87, Kluwer Academic Publishers (now Springer). Expanded second edition: Lectures on Convex Optimization, Springer, 2018.
• Ben-Tal, A., and Nemirovski, A. (2001). Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. MPS-SIAM Series on Optimization, SIAM.

Textbooks and monographs:

• Beck, A. (2017). First-Order Methods in Optimization. MOS-SIAM Series on Optimization 25, SIAM.
• Ben-Tal, A., El Ghaoui, L., and Nemirovski, A. (2009). Robust Optimization. Princeton University Press.
• Bubeck, S. (2015). Convex optimization: algorithms and complexity. Foundations and Trends in Machine Learning 8(3–4), 231–357.
• d’Aspremont, A., Scieur, D., and Taylor, A. (2021). Acceleration methods. Foundations and Trends in Optimization 5(1–2), 1–245.
• Hiriart-Urruty, J.-B., and Lemaréchal, C. (2001). Fundamentals of Convex Analysis. Springer.
• Nemirovski, A. S., and Yudin, D. B. (1983). Problem Complexity and Method Efficiency in Optimization. Wiley.
• Nesterov, Y., and Nemirovskii, A. (1994). Interior-Point Polynomial Algorithms in Convex Programming. SIAM Studies in Applied Mathematics 13, SIAM.
• Parikh, N., and Boyd, S. (2014). Proximal algorithms. Foundations and Trends in Optimization 1(3), 127–239.
• Renegar, J. (2001). A Mathematical View of Interior-Point Methods in Convex Optimization. MPS-SIAM Series on Optimization, SIAM.
• Rockafellar, R. T. (1970). Convex Analysis. Princeton University Press.
• Wright, S. J. (1997). Primal-Dual Interior-Point Methods. SIAM.

Papers:

• Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S., and Kolter, J. Z. (2019). Differentiable convex optimization layers. Advances in Neural Information Processing Systems 32.
• Altschuler, J. M., and Parrilo, P. A. (2023). Acceleration by stepsize hedging II: silver stepsize schedule for smooth convex optimization. arXiv preprint.
• Amelunxen, D., Lotz, M., McCoy, M. B., and Tropp, J. A. (2014). Living on the edge: phase transitions in convex programs with random data. Information and Inference 3(3), 224–294.
• Amos, B., and Kolter, J. Z. (2017). OptNet: differentiable optimization as a layer in neural networks. Proceedings of the 34th International Conference on Machine Learning (PMLR 70).
• Applegate, D., Díaz, M., Hinder, O., Lu, H., Lubin, M., O’Donoghue, B., and Schudy, W. (2021). Practical large-scale linear programming using primal-dual hybrid gradient. Advances in Neural Information Processing Systems 34.
• Banerjee, O., El Ghaoui, L., and d’Aspremont, A. (2008). Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data. Journal of Machine Learning Research 9, 485–516.
• Beck, A., and Teboulle, M. (2003). Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters 31(3), 167–175.
• Beck, A., and Teboulle, M. (2009). A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences 2(1), 183–202.
• Boumal, N., Voroninski, V., and Bandeira, A. S. (2016). The non-convex Burer–Monteiro approach works on smooth semidefinite programs. Advances in Neural Information Processing Systems 29.
• Boyd, S., Parikh, N., Chu, E., Peleato, B., and Eckstein, J. (2011). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning 3(1), 1–122.
• Burer, S., and Monteiro, R. D. C. (2003). A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming 95(2), 329–357.
• Candès, E. J., and Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics 9(6), 717–772.
• Candès, E. J., Romberg, J., and Tao, T. (2006). Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory 52(2), 489–509.
• Candès, E. J., Strohmer, T., and Voroninski, V. (2013). PhaseLift: exact and stable signal recovery from magnitude measurements via convex programming. Communications on Pure and Applied Mathematics 66(8), 1241–1274.
• Chambolle, A., and Pock, T. (2011). A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision 40(1), 120–145.
• Chandrasekaran, V., Recht, B., Parrilo, P. A., and Willsky, A. S. (2012). The convex geometry of linear inverse problems. Foundations of Computational Mathematics 12(6), 805–849.
• Chen, S. S., Donoho, D. L., and Saunders, M. A. (1998). Atomic decomposition by basis pursuit. SIAM Journal on Scientific Computing 20(1), 33–61.
• Cohen, M. B., Lee, Y. T., and Song, Z. (2021). Solving linear programs in the current matrix multiplication time. Journal of the ACM 68(1).
• d’Aspremont, A., El Ghaoui, L., Jordan, M. I., and Lanckriet, G. R. G. (2007). A direct formulation for sparse PCA using semidefinite programming. SIAM Review 49(3), 434–448.
• Diamond, S., and Boyd, S. (2016). CVXPY: a Python-embedded modeling language for convex optimization. Journal of Machine Learning Research 17(83), 1–5.
• Donoho, D. L. (2006). Compressed sensing. IEEE Transactions on Information Theory 52(4), 1289–1306.
• Drori, Y. (2017). The exact information-based complexity of smooth convex minimization. Journal of Complexity 39, 1–16.
• Drori, Y., and Teboulle, M. (2014). Performance of first-order methods for smooth convex minimization: a novel approach. Mathematical Programming 145(1–2), 451–482.
• Frank, M., and Wolfe, P. (1956). An algorithm for quadratic programming. Naval Research Logistics Quarterly 3(1–2), 95–110.
• Friedman, J., Hastie, T., and Tibshirani, R. (2008). Sparse inverse covariance estimation with the graphical lasso. Biostatistics 9(3), 432–441.
• Goemans, M. X., and Williamson, D. P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42(6), 1115–1145.
• Grant, M., and Boyd, S. (2008). Graph implementations for nonsmooth convex programs. In Recent Advances in Learning and Control, Lecture Notes in Control and Information Sciences 371, Springer, 95–110.
• Hajek, B., Wu, Y., and Xu, J. (2016). Achieving exact cluster recovery threshold via semidefinite programming. IEEE Transactions on Information Theory 62(5), 2788–2797.
• Jaggi, M. (2013). Revisiting Frank–Wolfe: projection-free sparse convex optimization. Proceedings of the 30th International Conference on Machine Learning (PMLR 28).
• Khot, S., Kindler, G., Mossel, E., and O’Donnell, R. (2007). Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM Journal on Computing 37(1), 319–357.
• Kim, D., and Fessler, J. A. (2016). Optimized first-order methods for smooth convex minimization. Mathematical Programming 159(1–2), 81–107.
• Lasserre, J. B. (2001). Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization 11(3), 796–817.
• Lee, Y. T., and Sidford, A. (2014). Path finding methods for linear programming: solving linear programs in Õ(√rank) iterations and faster algorithms for maximum flow. IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS).
• Malitsky, Y., and Mishchenko, K. (2020). Adaptive gradient descent without descent. Proceedings of the 37th International Conference on Machine Learning (PMLR 119).
• Markowitz, H. (1952). Portfolio selection. The Journal of Finance 7(1), 77–91.
• Mehrotra, S. (1992). On the implementation of a primal-dual interior point method. SIAM Journal on Optimization 2(4), 575–601.
• Nesterov, Y. (1983). A method for solving the convex programming problem with convergence rate O(1/k²). Soviet Mathematics Doklady 27(2), 372–376.
• Nesterov, Y., and Todd, M. J. (1997). Self-scaled barriers and interior-point methods for convex programming. Mathematics of Operations Research 22(1), 1–42.
• O’Donoghue, B., and Candès, E. (2015). Adaptive restart for accelerated gradient schemes. Foundations of Computational Mathematics 15(3), 715–732.
• O’Donoghue, B., Chu, E., Parikh, N., and Boyd, S. (2016). Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Applications 169(3), 1042–1068.
• Parrilo, P. A. (2003). Semidefinite programming relaxations for semialgebraic problems. Mathematical Programming 96(2), 293–320.
• Recht, B., Fazel, M., and Parrilo, P. A. (2010). Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review 52(3), 471–501.
• Roulet, V., and d’Aspremont, A. (2020). Sharpness, restart, and acceleration. SIAM Journal on Optimization 30(1), 262–289.
• Rudin, L. I., Osher, S., and Fatemi, E. (1992). Nonlinear total variation based noise removal algorithms. Physica D 60(1–4), 259–268.
• Scieur, D., d’Aspremont, A., and Bach, F. (2016). Regularized nonlinear acceleration. Advances in Neural Information Processing Systems 29.
• Smale, S. (1998). Mathematical problems for the next century. The Mathematical Intelligencer 20(2), 7–15.
• Taylor, A. B., Hendrickx, J. M., and Glineur, F. (2017). Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Mathematical Programming 161(1–2), 307–345.
• Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society, Series B 58(1), 267–288.
• Waldspurger, I., d’Aspremont, A., and Mallat, S. (2015). Phase recovery, MaxCut and complex semidefinite programming. Mathematical Programming 149(1–2), 47–81.
• Ye, Y., Todd, M. J., and Mizuno, S. (1994). An O(√n L)-iteration homogeneous and self-dual linear programming algorithm. Mathematics of Operations Research 19(1), 53–67.
• Yurtsever, A., Tropp, J. A., Fercoq, O., Udell, M., and Cevher, V. (2021). Scalable semidefinite programming. SIAM Journal on Mathematics of Data Science 3(1), 171–200.