EE5121 Convex Optimization, July - Nov 2022

Introduction to Optimization — 27 July

Review of linear algebra & note on condition number — 28 July

Review of analysis — 29 July

Review of convexity and continuity — 02 Aug

Review of calculus — 03 Aug, 04 Aug

Introduction, Taylors theorem, 1st and 2nd order conditions on a stationary point — 05 Aug

Overview of line search methods, definition of descent directions including steepest descent, and Newton directions — 12 Aug

Matlab code to show gradients and function contours, trust region methods and line search considerations — 16 Aug

Wolfe conditions for inexact line search and backtracking line search — 17 Aug

Proof of convergence of descent methods — 18 Aug, 19 Aug

Introduction, visualizing quadratic forms, and property of conjugacy — 23 Aug

Method of conjugate directions, and properties of conjugate vectors — 24 Aug

Expanding subspace theorem for conjugate directions method — 25 Aug

Formulation of the conjugate gradient method — 26 Aug

Matlab demo of steepest descent v/s conjugate gradient link — 01 Sep

Preconditioned CG method, code for playing around with condition number  — 06 Sep, 07 Sep

Nonlinear CG - 07 Sep, 13 Sep

Introduction and proof of convergence — 14 Sep

Hessian modification and Gershgorin disk theorem for eigenvalue bounds — 15 Sep

Quasi newton methods, intuition, and the BFGS formulation — 16 Sep

Least squares problems — 21 Sep

Linear least squares — 22 Sep

Nonlinear least squares, Gauss Newton method — 23 Sep

Introduction, definitions and a look at equality constraints — 07 Oct

Single equality and inequality constraints, Lagrangian — 11 Oct

Linearized feasibility directions, example with multiple constraints — 12 Oct

Geometry vs algebra — tangent cone and linear independence constraint qualification (ref)-- 13 Oct

First order necessary conditions for a minima & the KKT conditions — 14 Oct

Projected gradient method (ref1, ref2, showing descent of iterates) — 19 Oct

Examples of projection operations (L2 ball), concept of subgradients ref — 20 Oct

Projection onto the L1 ball (ref) — 21 Oct

KKT and duality — 26 Oct

Geometric interpretation of duality (ref, author unknown) — 27 Oct

Weak duality and an example of applying KKT/duality — 28 Oct

Introduction to Optimization

Summary of background material

Unconstrained optimization

Line search methods

Conjugate gradient methods

Newton & quasi Newton methods

Least squares problems

Constrained optimization — first order

Review: linear algebra, analysis, and calculus

Unconstrained optimization - descent directions, line search methods, Wolfe conditions, steepest descent method and its analysis, conjugate gradient method and its analysis, preconditioned conjugate gradient method, extension of the conjugate gradient method to its nonlinear versions, introduction to the Newton and quasi Newton methods, discussion of linear and nonlinear least squares problems

Constrained optimization - first order necessary conditions, Karush–Kuhn–Tucker (KKT) conditions with proof, projected gradient method and some examples of projection operatations, weak and strong duality, second order necessary conditions (time permitting)

Programming implementations of the above methods

Numerical Optimization by Jorge Nocedal and Stephen J. Wright, Springer, 2006. Available online. Keyword NW

Convex Optimization by Stephen Boyd and Lieven Vandenberghe, Oxford University Press, 2009. Available online. Keyword: BL