Convex Optimization

📚 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

1. Define the components of a mathematical optimization problem, including the objective function, constraints, and variables.
2. Distinguish between least-squares, linear programming, and convex optimization problems based on their mathematical properties.
3. Compare local and global optimization strategies and evaluate the computational complexity associated with each.
4. Define and distinguish between affine sets, convex sets, and cones using formal combination notation.
5. Identify and represent standard convex sets including Euclidean balls, ellipsoids, polyhedra, and the positive semidefinite cone.
6. Apply operations that preserve convexity, such as intersection, affine transformations, and perspective functions, to verify set properties.
7. Identify and apply operations that preserve convexity, including the pointwise supremum of affine functions and vector composition rules.
8. Derive the Lagrange conjugate of various functions and apply Young's inequality.
9. Characterize quasiconvexity using sublevel sets and first/second-order differentiable conditions.
10. Formulate and Transform: Convert raw optimization problems into standard convex forms using slack variables and constraint elimination.

🔹 Lesson 1: Introduction to Mathematical Optimization

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.

🔹 Lesson 2: Theory of Convex Sets

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.

🔹 Lesson 3: Convex Functions and 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.

🔹 Lesson 4: Convex Optimization Problem Formulation

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.

🔹 Lesson 5: Lagrangian Duality and KKT Conditions

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.

🔹 Lesson 6: Approximation, Fitting, and Regularization

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.

🔹 Lesson 7: Statistical Estimation and Inference

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.

🔹 Lesson 8: Geometric Problems and Classification

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.

🔹 Lesson 9: Unconstrained Minimization Algorithms

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.

🔹 Lesson 10: Equality Constrained Minimization

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.

🔹 Lesson 11: Interior-Point Methods

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.