Numerical Optimization

Lecture 1: Main topic of the course: constrained and unconstrained optimization problems. A general overview of iterative methods. Program hierarchies (LP, QP, SOCP, SDP). Historical examples: Gauss and Ceres, linear optimization for military rationing, interior point methods as part of the best paper at FOCS 2022.  Examples of hard problems: NP-hard problems and uncomputable functions as optimization problems.

Lecture 2: A quick overview of modeling with Linear Programming and Integer Linear Programming.

Lecture 3: Convexity of sets and functions. Definition, basic properties. Hyperplane separation lemma and hyperplane supporting lemma. The first-order and second-order convexity criterion. Proof of convexity guaranteeing that a local minimum is a global minimum.

Lecture 4: Line search as a general tool for unconstrained minimization. The Wolfe conditions (Armijo, curvature). Proof of convergence for any line search in finite number of steps assuming Lipschitz-continuity and Wolfe conditions. Gradient descent on a convex quadratic program and its linear convergence rate. Condition number. [NW, Chapter 3].

Lecture 5: Newton method. Historical context, Newton method for finding a root of a function of one variable. Definition of the Newton method for unconstrained optimization. Proof of affine invariance of the Newton method. Damped and pure Newton methods.  Definition of operator norms. Convergence estimates in the case where a function is strongly convex and the Hessian is Lipschitz-continuous. [BV, Chapter 9.5].

Lecture 6: Conjugate gradient method. Conjugate direction method as an iterative solver of a linear system of equations. Theorem and proof that conjugate direction converges in n iterations. Conjugate gradient method for linear systems. Theorem and proof of the basic properties of CGM. A practical version of CGM. Fletcher-Reeves CGM. [NW, Chapter 5].

Lecture 7: Quasi-Newton methods. Quadratic model for the function f. , the quasi-Hessian B_k and quasi-Hessian-inverse H_k. Requirements on B_k/H_k. Derivation of the BFGS method from the requirement on H_k. Advantages and disadvantages of Quasi-Newton methods [NW, Chapter 6]. Additional notes.

Lecture 8: Constrained optimization. Definition of a constrained optimization problem and the convex constrained model. Building a first-order criterion of optimality for a local minimum for constrained optimization problems. Example with a single equation, single inequality and two inequalities. Karush-Kuhn-Tucker conditions formally. [NW, Chapter 12]. Video of the lecture, handwritten notes.

Lecture 9: Constrained optimization, part 2. The importance of constraint qualification in the KKT conditions. Definition of the tangent cone and the set of the linearized feasible directions. Common constraint qualifications: LICQ, MFCQ, Slater's condition [NW, Chapter 12].

Lecture 10: Duality. Definition of the Lagrange dual function and the dual problem. Weak duality and its proof. Duality gap, strong duality. For a convex problem, if KKT conditions hold, then strong duality holds (with proof). [BV, Chapter 5].

Lecture 11: Duality, Part 2. Strong duality and sufficient conditions of strong duality. Slater's condition and its weaker form. Solving a primal by using KKT conditions: the water filling problem [BV 5.5]. Solving a constrained problem by solving the unconstrained dual: the equality constrained analytic center problem [BV 10.2]. 

Lecture 12: Interior-point methods for linear programming. Introduction to the primal-dual interior point method -- primal + dual LP formulation, KKT complementarity conditions for the dual and their relaxation. Duality measure. Newton method for solving a system F(x) = 0 for a system of functions F. The Jacobian matrix. The general interior point method framework.  [NW, Chapter 14].

Lecture 13: Interior-point methods, part 2. Central path, feasible and strictly feasible region. The N_{-infty} neighborhood of the central path. The long-step path following framework. Proof of Lemmas 14.1 and 14.2 in the Nocedal-Wright textbook. Main idea of the proof of Theorem 14.3. [NW, Chapter 14].

Lecture 14: Review of the whole course.

Session 1: Linear Algebra refresh. Exercises.

Session 2: Linear Programming. Exercises.

Session 3: Convexity. Exercises.

Session 4: Convexity continued. Exercises.

Session 5: Gradient descent. Exercises.

Session 6: Review so far. Exercises.

Session 7: Newton's method. Exercises.

Session 8: Conjugate gradient method. Exercises.

Session 9: Constrained optimization. Exercises.

Session 10: Duality. Exercises.

Session 11: All about Support Vector Machines. Exercises.

Session 12: A sample exam. Exercises.

For tasks for Lab sessions, please visit the Google Drive managed by Filip Chudy. A SKOS module for the course (for submitting the tasks) may be open in the near future.

• [NW] Jorge Nocedal, Stephen J. Wright. Numerical Optimization. Second Edition, Springer 2006. The book is available as a PDF at this link (likely unofficially).

• [BV] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press 2004. Available online at https://web.stanford.edu/~boyd/cvxbook/ .

• [MG] Jiří Matoušek, Bernd Gärtner. Understanding and Using Linear Programming. Springer 2007 (https://link.springer.com/book/10.1007/978-3-540-30717-4). The book is also available as a PDF under this link (likely unofficially). 

• [Heb] Waldemar Hebisch. Lecture notes for the course Numerical Optimization, 2021. Available on the Internet Archive at this link.