凸最適化

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.