Convex Optimization
A comprehensive graduate-level course and textbook covering the theory, applications, and numerical algorithms of convex optimization. It emphasizes recognizing and formulating convex problems in engineering and sciences.
Lessons
Lesson
This lesson introduces the standard form of mathematical optimization, which uses variables, objective functions, and constraints to model decision-making processes. Students learn to identify these components to distinguish between linear and nonlinear problems while establishing the foundational language required for formal optimization.
This lesson explores the geometric foundations of optimization by defining lines, line segments, rays, and affine sets. It establishes the convexity litmus test, which requires that any line segment connecting two points within a set must remain entirely contained inside that set.
This lesson explores how the pointwise supremum of a family of convex functions preserves convexity, a fundamental concept for constructing complex convex functions and understanding duality. By analyzing the epigraph as an intersection of sets, students learn how this principle applies to key mathematical tools like support functions, spectral norms, and conjugate functions.
This lesson introduces the standard form for convex optimization problems, emphasizing that equality constraints must be affine to maintain convexity. Students learn to interpret these problems geometrically through epigraphs and explore practical applications, including risk management and engineering design.
This lesson introduces the Lagrangian framework as a method to transform hard constraints into weighted penalties, allowing for the quantification of constraint costs through Lagrange multipliers. Students learn how to utilize the Lagrange dual function to establish lower bounds on optimal values and explore the role of KKT conditions, such as complementary slackness, in solving complex optimization problems.
This lesson explores the fundamentals of norm approximation in convex optimization, focusing on finding the best vector to minimize the residual between a target and an achievable subspace. Students learn how to select between $\ell_1$, $\ell_2$, and $\ell_\infty$ norms based on specific error-handling needs, such as robustness to outliers or minimizing worst-case deviations.
This lesson explores how statistical Maximum Likelihood Estimation (MLE) can be framed as a convex optimization problem by utilizing the log-likelihood function. Students learn that when probability densities are log-concave and constraints are convex, statistical estimation becomes a globally solvable task where noise distributions directly dictate the geometric penalty functions used in the optimization.
Geometric Foundations of Convex Optimization explores the role of convexity in ensuring unique projections onto sets, emphasizing the use of indicator and support functions to represent geometric constraints. The lesson highlights how convexity provides the stability necessary for optimization, while cautioning that geometric properties like uniqueness are highly dependent on the choice of norm.
This lesson introduces unconstrained minimization algorithms for convex, twice-differentiable functions, focusing on iterative methods that use descent directions like gradient descent and Newton's method. Students will learn to evaluate convergence efficiency, apply self-concordance theory, and utilize second-order models to find optimal points while maintaining numerical stability.
This lesson explores optimality conditions for convex optimization problems with equality constraints, focusing on how the gradient must be orthogonal to the constraint's nullspace. Students will learn to utilize Lagrange multipliers, the KKT system, and the projected gradient method to identify optimal points and solve for descent directions.
This lesson introduces interior-point methods, which replace non-differentiable indicator functions with smooth logarithmic barriers to handle inequality constraints in convex optimization. By iteratively increasing a parameter $t$, these methods allow Newton's method to solve constrained problems while keeping iterates strictly within the feasible region.
Course Overview
📚 Content Summary
A comprehensive graduate-level course and textbook covering the theory, applications, and numerical algorithms of convex optimization. It emphasizes recognizing and formulating convex problems in engineering and sciences.
Master the mathematical foundation and practical algorithms of convex optimization for engineering and data science.
Author: Stephen Boyd, Lieven Vandenberghe
Acknowledgments: Supported in part by NSF, and through contributions from students and colleagues at Stanford and UCLA, including special mentions of Arkadi Nemirovski and Kishan Baheti.
🎯 Learning Objectives
- Define the components of a mathematical optimization problem, including the objective function, constraints, and variables.
- Distinguish between least-squares, linear programming, and convex optimization problems based on their mathematical properties.
- Compare local and global optimization strategies and evaluate the computational complexity associated with each.
- Define and distinguish between affine sets, convex sets, and cones using formal combination notation.
- Identify and represent standard convex sets including Euclidean balls, ellipsoids, polyhedra, and the positive semidefinite cone.
- Apply operations that preserve convexity, such as intersection, affine transformations, and perspective functions, to verify set properties.
- Identify and apply operations that preserve convexity, including the pointwise supremum of affine functions and vector composition rules.
- Derive the Lagrange conjugate of various functions and apply Young's inequality.
- Characterize quasiconvexity using sublevel sets and first/second-order differentiable conditions.
- Formulate and Transform: Convert raw optimization problems into standard convex forms using slack variables and constraint elimination.
Lessons
Overview: This lesson introduces the foundational concepts of mathematical optimization, moving from the general problem formulation to specific, solvable classes like least-squares and linear programming. It emphasizes the critical distinction between convex and nonconvex optimization, detailing how convex methods serve as a reliable "watershed" for efficiency and provide vital tools for addressing more difficult nonlinear problems.
Learning Outcomes:
- Define the components of a mathematical optimization problem, including the objective function, constraints, and variables.
- Distinguish between least-squares, linear programming, and convex optimization problems based on their mathematical properties.
- Compare local and global optimization strategies and evaluate the computational complexity associated with each.
Overview: This lesson explores the foundational geometry of optimization, transitioning from basic linear structures to the complex properties of convex sets and cones. It covers the mathematical definitions of affine and convex sets, examines specific geometries like polyhedra and positive semidefinite cones, and details the operations and theorems that allow researchers to characterize and manipulate convex sets in high-dimensional spaces.
Learning Outcomes:
- Define and distinguish between affine sets, convex sets, and cones using formal combination notation.
- Identify and represent standard convex sets including Euclidean balls, ellipsoids, polyhedra, and the positive semidefinite cone.
- Apply operations that preserve convexity, such as intersection, affine transformations, and perspective functions, to verify set properties.
Overview: This lesson explores advanced operations that preserve convexity, such as pointwise suprema and specific composition rules, and introduces the Lagrange conjugate function. It extends the concept of convexity to quasiconvex and log-concave functions, while also examining convexity with respect to generalized inequalities and matrix-specific properties like the Schur complement. These concepts form the mathematical foundation for identifying and formulating complex optimization problems.
Learning Outcomes:
- Identify and apply operations that preserve convexity, including the pointwise supremum of affine functions and vector composition rules.
- Derive the Lagrange conjugate of various functions and apply Young's inequality.
- Characterize quasiconvexity using sublevel sets and first/second-order differentiable conditions.
Overview: This lesson covers the formal structure and transformation of convex optimization problems, ranging from standard forms and optimality conditions to specific problem classes like Linear (LP), Quadratic (QP), and Semidefinite Programming (SDP). Students will learn how to identify global optimality, use the bisection method for quasiconvex problems, and apply scalarization to multicriterion vector optimization.
Learning Outcomes:
- Formulate and Transform: Convert raw optimization problems into standard convex forms using slack variables and constraint elimination.
- Analyze Optimality: Apply the gradient-based optimality criterion to determine if a point is globally optimal.
- Classify and Solve: Distinguish between LP, QP, SOCP, GP, and SDP, and apply specialized methods like the Bisection Method for quasiconvex functions.
Overview: This lesson explores the fundamental theory of Lagrangian duality, moving from the definition of the Lagrange dual function to the formulation of the dual problem. It covers the critical gap between primal and dual optimal values, the geometric and game-theoretic interpretations of these relationships, and the Karush-Kuhn-Tucker (KKT) conditions that characterize optimal solutions. Finally, the lesson extends these concepts to sensitivity analysis and shadow prices.
Learning Outcomes:
- Derive the Lagrange dual function and formulate the dual problem for various optimization problems.
- Evaluate the relationship between primal and dual problems using weak/strong duality and Slater's constraint qualification.
- Apply KKT optimality conditions to solve and verify optimal solutions for convex and non-convex problems.
Overview: This lesson explores the mathematical foundations and practical applications of approximating solutions to systems of linear equations and fitting functions to data. It covers norm-based approximation including penalty functions and regularization to manage outliers and sparsity, and robust optimization techniques for handling data uncertainty. Furthermore, it details function fitting under specific constraints such as convexity and monotonicity.
Learning Outcomes:
- Formulate and solve norm approximation problems and interpret the geometric and statistical differences between Least-squares, Chebyshev, and L1 approaches.
- Design and implement regularized approximation models to achieve trade-offs between residual error, solution magnitude, and sparsity.
- Construct robust approximation frameworks to account for uncertainties in the data matrix.
Overview: This lesson explores the intersection of statistical inference and convex optimization. It focuses on formulating estimation problems—including maximum likelihood, nonparametric distribution estimation, and optimal detector design—as convex programs. Students will learn to use optimization to find parameters and design informative experiments.
Learning Outcomes:
- Formulate and solve Maximum Likelihood Estimation (MLE) and Logistic Regression problems as convex optimization tasks.
- Design optimal detectors using Linear Programming (LP) and interpret Receiver Operating Characteristics (ROC).
- Apply Nonparametric estimation techniques, including Maximum Entropy and Kullback-Leibler divergence minimization.
Overview: This lesson explores the application of convex optimization to geometric problems, including the projection of points onto sets, calculating distances between sets, and characterizing set centers. It further extends these geometric principles to real-world tasks such as linear and nonlinear classification, optimal facility placement, and floor planning using geometric programming.
Learning Outcomes:
- Formulate and solve projection and distance problems between convex sets using KKT conditions and dual representations.
- Approximate complex convex sets using extremal volume ellipsoids and identify their efficiency factors.
- Compute various set centers and apply them to robust discrimination and classification.
Overview: This lesson covers the theoretical foundations and algorithmic implementations of unconstrained minimization for convex functions. It details descent methods ranging from first-order Gradient Descent to second-order Newton’s Method. A significant portion is dedicated to convergence analysis, focusing on strong convexity and the affine-invariant theory of self-concordance.
Learning Outcomes:
- Define strong convexity and utilize its implications to provide upper bounds on suboptimality and distance to the optimizer.
- Compare and contrast Gradient Descent with Steepest Descent under Euclidean, Quadratic, and L1 norms.
- Compute the Newton step and Newton decrement, explaining why Newton's method is affine-invariant.
Overview: This lesson explores methods for solving convex optimization problems with linear equality constraints. It focuses on the derivation and implementation of the Newton step, comparing feasible and infeasible start methods, and interpreting these steps within a primal-dual framework. Special emphasis is placed on efficient numerical implementation via KKT system block elimination.
Learning Outcomes:
- Compute and interpret the Newton step and decrement for equality-constrained problems.
- Demonstrate the equivalence between Newton’s method with equality constraints and the elimination of those constraints.
- Implement the Infeasible Start Newton method and explain its primal-dual residual reduction property.
Overview: This lesson covers interior-point methods, which solve convex optimization problems with inequality constraints by applying Newton's method to a sequence of equality-constrained problems. The core involving logarithmic barrier functions, tracing a central path toward the optimal solution, and utilizing primal-dual frameworks for increased efficiency and robustness.
Learning Outcomes:
- Define and construct logarithmic barrier functions and characterize the central path and its associated dual points.
- Implement the barrier method, including the trade-off between centering steps and outer iterations.
- Formulate and solve Phase I feasibility problems to find strictly feasible starting points.