Math 273a: Basic Optimization Theory

Links

  • MS 5117, Every Wed 1-1:50pm and Friday 1-2:50pm

  • Prerequisits: latex, linear algebra, multivariate calculus, basic topology and analysis, Matlab programming

  • Online forum for Q&As, homework discussions, and projects (Sign up)

Textbooks

  1. An Introduction to Optimization, 4th Edition, by Chong and Zak

  2. Convex optimization theory by Bertsekas

  3. Convex Analysis and Monotone Operator Theory in Hilbert Spaces by Bauschke and Combettes

Workload

  • 40% four homework sets, latex required (a template is provided)

  • 50% final take-home project

  • 10% classroom and piazza participation (ask and answer questions, share resources)

Homework / exam policy

No extension will be granted. Late submission will not be accepted.

Topics:

  • Optimization terms, types, and global vs local solutions

  • Unconstrained optimization: geometry, 1st and 2nd order optimality conditions, gradient method, Newton's method

  • Conic optimization: linear and second-order programming, geometry, and typical methods

  • Nonlinear optimization: geometry, KKT conditions, projective penalty barrier methods

  • Convexity: sets, functions, key inequality, duality

  • 1st-order algorithms: subgradient, gradient, proximal, Frank-Wolfe methods

  • Monotone-operator and operator splitting methods

Lectures (tentative)

  1. Introduction to optimization (slides)

  2. Basics of optimization: terminology, types of minimizers, optimality conditions (slides)

  3. Gradient descent (slides) (Supplement: 1D search methods slides)

  4. Newton-family methods (slides)

  5. The Barzilai-Borwein method (slides)

  6. Linear programming (slides), the Simplex Method (slides)

  7. Basics of nonlinear optimization: equality-constrained (slides), inequality-constrained (slides)

  8. Convex functions and key properties (slides)

  9. Subgradients of convex functions (slides)

  10. Subgradient methods (slides), cutting plane and bundle methods (slides)

  11. Gradient method (on the board)

  12. Proximal operator and algorithm (slides)

  13. Convex conjugacy and duality (slides) (slides)

  14. Monotone operator theory and splitting methods (slides)

Homework

Policy

  • This homework assignment is open to all textbooks (listed above or not), class notes, and Internet documents except for any solution manual or the solutions from the previous quarters.

  • You are encouraged to ask questions and discuss the questions and solutions on Piazza. However, copying others’ solutions or programs is considered a serious violation.

  • Please use the Latex template below.

Assignment # 1

  • Deadline: Friday, October 16, 1pm.

  • Six problems (10 points each): Chong-Zak 8.8, 8.11, 8.18, 9.4. Prove the Baillon-Haddad theorem (see slides, page 19). Problem 6 are given in the template.

  • Template: latex / pdf. Compile it to a PDF file before submission. Do not include your name or ID number in the PDF. However, name your PDF file as HW1_[your 9-digit ID].pdf. For example, if you ID is 123-456-789, then you should submit HW1_123456789.pdf.

  • Submit your homework on UCLA CCLE. Submission will be closed after the deadline.

Assignment # 2

  • Deadline: Friday, October 31, 1pm.

  • Five problems (10 points each): Chong-Zak 15.3, 15.5, 15.11. Problems 4 and 5 are given in the template.

  • Instructions for Chong-Zak 15.11: either copy your m-file source code and its output to your latex file, or use the Matlab report function or a PDF printer to generate a PDF file(s), and then include its pages in your latex file. Please submit a single PDF file.

  • Template: latex / pdf. Compile it to a PDF file before submission. Do not include your name or ID number in the PDF. However, name your PDF file as HW2_[your 9-digit ID].pdf. For example, if you ID is 123-456-789, then you should submit HW2_123456789.pdf.

  • Submit your homework on UCLA CCLE. The resubmission option is on. Submission will be closed after the deadline.

Assignment # 3

  • Deadline: Friday, October 13, 1pm.

  • Five problems (10 points each for Problems 1 through 4, 20 points for Problem 5). All problems are given in the template.

  • Template: latex / pdf. Compile it to a PDF file before submission. Do not include your name or ID number in the PDF. However, name your PDF file as HW3_[your 9-digit ID].pdf. For example, if you ID is 123-456-789, then you should submit HW3_123456789.pdf.

  • Submit your homework on UCLA CCLE. The resubmission option is on. Submission will be closed after the deadline.

Final group project

  • Group size: 1, 2, or 3 students each group. No more than 3.

  • Requirements:

    • read one or a few related papers under the same topic

    • submit both a reading report or a set of slides that describe the background, motivation, main methods, numerical results, and future direction The submitted documents will be read by the instructor. Points will be taken for missing major parts, missing major novelties or contributions, missing major references, or any significant mathematical errors.

  • Deadlines:

    • Group formation: Nov 11. Email the instructor by email and copy all group mates.

    • Topic selection: Nov 16. Email the instructor by email and copy all group mates.

    • Check point: Nov 30. CCLE submission of intermediate results and report.

    • 15-20 minute in-class presentations. Will be scheduled.

    • Final submission: Dec 14. CCLE submission of report, slides, and code.

    • Topics: sugradient method, cutting plane method, bundle method, accelerate gradient method, ADMM, primal-dual splitting, coordinate descent method, coordinate update method, stochastic gradient method, incremental gradient method, Bregman iteration and inverse scale space.


« Back