Optimization Techniques -W23- Lecture 9 (Conjugate Gradient, Quasi-Newton, Distributed Optimization)

The course "Optimization Techniques" (ENGG*6140, section 2) at the School of Engineering at the University of Guelph. Instructor: Benyamin Ghojogh Lecture 9 continues the second-order optimization methods by introducing the Wolfe conditions, decomposition methods, conjugate gradient, and quasi-Newton's method. Then, it introduces distributed optimization algorithms such as ADMM. We start with reviewing the Newton's method and the interior-point method which were introduced in the previous session. We talk about line-search with Wolfe conditions (Armijo and curvature conditions). Then, we introduce fast solving of linear system of equations using LU decomposition, Cholesky decomposition, Schur complement, conjugate gradient method, relation of the conjugate gradient method to Krylov subspace, and Nonlinear Conjugate Gradient (NCG). Then, we explain quasi-Newton's method for Hessian approximation by introducing Broyden-Fletcher-Goldfarb-Shanno (BFGS), Limited-memory BFGS (LBFGS), Davidon-Fletcher-Powell (DFP), Broyden method, and Symmetric Rank-one (SR1). Then, we switch to distributed optimization by explaining alternating optimization, decomposable functions, proximal alternating optimization, dual ascent, dual decomposition method, augmented Lagrangian method (method of multipliers), Alternating Direction Method of Multipliers (ADMM), and ADMM algorithm for general optimization problems and any number of variables. The slides are available at: https://bghojogh.github.io/pages/uoguelph/engg-6140-w23/ Very useful optimization courses at Stanford University by Prof. Stephen Boyd: https://www.youtube.com/playlist?list=PL3940DD956CDF0622 Some slides of this slide deck, especially the Quasi-Newton’s methods, are inspired by the teachings of Prof. Reshad Hosseini at the University of Tehran. Chapters: 0:00 - Question about assignment 2 9:36 - Review of Newton's method and interior-point method 14:31 - Wolfe conditions for line-search in Newton's method 20:33 - Newton's method as a system of linear equations 26:50 - Decomposition methods (LU decomposition) 29:58 - Decomposition methods (Cholesky decomposition) 32:22 - Decomposition methods (Schur complement) 36:38 - Conjugate gradient method 51:51 - Nonlinear conjugate gradient (NCG) method 58:04 - Quasi-Newton's methods (justification) 1:11:41 - Quasi-Newton's methods, including BFGS 1:15:46 - Limited-memory BFGS (LBFGS) 1:25:32 - Important references for second-order optimization 1:33:11 - Talking about presentation of the course projects 1:39:53 - Problem statement for distributed optimization 1:42:53 - Alternating optimization 1:52:20 - Alternating optimization for decomposable functions 1:53:27 - Proximal alternating optimization 1:54:48 - Alternating optimization for constrained problems 1:56:39 - Dual ascent method 2:05:35 - Dual decomposition method 2:10:58 - Augmented Lagrangian method (method of multipliers) 2:14:35 - Alternating Direction Method of Multipliers (ADMM) 2:18:36 - Simplifying equations in ADMM 2:24:19 - ADMM for general problems and multiple variables