Department of Mathematics Syllabus

This syllabus is advisory only. For details on a particular instructor's syllabus (including books), consult the instructor's course page. For a list of what courses are being taught each quarter, refer to the Courses page.

MAT 258A: Numerical Optimization
Approved: 2011-01-04,

Units/Lecture:

Matthias Koeppe

Suggested Textbook: (actual textbook varies by instructor; check your instructor)
1. Nocedal/Wright, Numerical Optimization, 2nd edition, available for free on SpringerLink; 2. Boyd/Vandenberghe, Convex Optimization, available for free from Boyd's homepage

Prerequisites:

25 and 167, or consent of the instructor

Suggested Schedule:

Lectures Sections Comments/Topics
0.5 NW 1 Introduction
0.5 NW 2.1 Unconstrained optimization: Optimality conditions
0.5 NW 2.2, 3.1 Line search
1.5 NW 3.2—3.3 Convergence of line search. Linear convergence of steepest descent, local quadratic convergence of Newton.
0.5 BV 9.6 Self-concordant analysis of Newton.
2.5 NW 6.1—6.4 NW 7.2 Superlinear convergence of quasi-Newton methods. DFP, BFGS, Broyden, restricted Broyden, global convergence. Limited-memory BFGS (L-BFGS).
3 NW 12.1—12.7 Constrained optimization: First- and second order optimality conditions.
1 NW 12.9 BV 5.1—5.5 Lagrangean duality. Dual of convex quadratics.
1 BV 2.6, 4.4.2 BV 4.6, 5.9 Generalized inequalities: Conic, semidefinite, LMI. Their Lagrangean duality.
1.5 NW 16.1—16.5 Active-set methods for convex quadratic optimization.
1 NW 18.1—18.4 Sequential quadratic programming
1 NW 17.1—17.3 Penalty functions
0.5 NW 15.4, 18.3 Merit functions
1.5 NW 14.1—14.2 Primal-dual path-following interior point methods for linear optimization
1 NW 19.1—19.5 Interior point algorithms for general nonlinear optimization problems; line search vs. trust region
2 * Application: Compressive sensing. Conditions for the equivalence of l0 and l1 optimization. Numerical aspects, such as the LASSO algorithm and/or l1 minimization via interior point methods.

Additional Notes:

The indicated number of lectures refers to 80-minute lectures. The syllabus accounts for 19.5 of 20 lectures of one quarter.

Source for compressed sensing: the paper http://www.acm.caltech.edu/~emmanuel/papers/RIP.pdf and probably some more sources.

Assessment:

Recommended are take-home midterms or individual/group projects rather than in-class midterms.