Mathematical Optimization

Introduction

This study covers numerical iterative algorithms for continuous optimization rather than heuristic or metaheuristic search methods. For a problem

an algorithm generates a sequence $x_0,x_1,\ldots$ through an update rule $x_{k+1}=\mathcal{A}(x_k)$. Gradient, Newton, quasi-Newton, proximal, and constrained-optimization methods are derived from mathematical properties of $f$ and the feasible set $\mathcal{X}$.

The main focus is the theory behind these iterations: the assumptions under which $x_k$ converges, the solution or stationary point $x^\star$ it approaches, and the speed of that convergence. Rates such as the sublinear bound $f(x_k)-f^\star=\mathcal{O}(1/k)$, the linear bound $\lVert x_k-x^\star\rVert\leq C\rho^k$ for $0<\rho<1$, and the quadratic bound $\lVert x_{k+1}-x^\star\rVert\leq C\lVert x_k-x^\star\rVert^2$ are studied together with error bounds and iteration complexity.

Prerequisites

• Optimization (Undergraduate Level)
• Numerical Analysis
• Real Analysis
• Linear Algebra
• Calculus

References

• Jorge Nocedal and Stephen J. Wright, Numerical Optimization, 2nd ed., Springer, 2006.
• Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004.
• Amir Beck, First-Order Methods in Optimization, SIAM, 2017.
• Sébastien Bubeck, Convex Optimization: Algorithms and Complexity, Foundations and Trends in Machine Learning, 2015.

Curriculum