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:
MAT 127A; MAT 167.
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.
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.