Optimization Methods

This repository contains seminars resources for the course "Optimization methods" for the 3-rd year students of Department of Control and Applied Mathematics, MIPT. Every seminar presents brief review of necessary part of theory covered in lectures and examples of standard tasks for considered topic. Also after every seminar students have home assignment which has to be submitted in LaTeX or Jupyter Notebook format before deadline.

The main tool in development of efficient optimization methods is numerical linear algebra. To refresh your knowledge, you can use the crash course (ru, en).

Fall term

1. Introduction (ru, en)

2. Convex sets (ru, en)

3. Projection onto set, separation, support hyperplane (ru, en)

4. Conjugate sets. Farkas' lemma (ru, en)

5. Introduction to matrix calculus (ru, en)

6. Convex functions (ru, en)

7. Subdifferential (ru, en)

8. Feasible direction cone, tangent cone, sharp extremum (ru, en)

9. Conjugate functions (ru, en)

10. Optimality conditions (ru, en)

11. Introduction to duality theory (ru, en)

Questions

The list of questions (ru) about topics in Fall term part of the course that students have to answer to pass the exam.

Spring term

1. Numerical optimization methods: introduction, convergence speed, classes of methods, black box model, one-dimensional optimization (ru, en)

2. Unconstrained optimization problems

   • Gradient descent (ru, en)
   • Newton method. Quasi-Newton methods (ru, en)
   • Conjugate gradients methods (ru, en)

3. Linear programming

   • Simplex method (ru, en)
   • Primal interior point method (ru, en)

4. Constrained optimization problems

   • Projected gradient method and Frank-Wolfe method (ru, en)
   • Interior point methods (ru, en)
   • Penalty methods and augmented Lagrangian methods (ru, en)

Questions

The list of questions (ru) about topics in Spring term part of the course that students have to answer to pass the exam.

Advanced and additional topics

1. Least squares problem (ru, en)
2. Nesterov's method and ODE (ru, en)
3. Sequential quadratic programming
4. Theory of optimal methods and lower complexity bounds
5. Mirror descent
6. Gradient descent and beyond
7. Optimization methods on Riemanien manifolds
8. Structured optimization with sparsity conditions
9. Proximal methods
10. Submodular optimization
11. ...

References

1. Stephen Boyd, Lieven Vandenberghe. Convex Optimization

2. Convex optimization course by S. Boyd at Stanford

3. Convex analysis and optimization course at MIT

4. Optimization methods course by L. Vandenberghe at UCLA

5. Y.E. Nesterov. Introductory lectures on convex optimization: A basic course

6. B.T. Polyak. Introduction to optimization

7. Lectures by A. Juditsky at Grenoble UJF

8. Matrix Cookbook

9. Video lectures by S. Boyd on course Convex Optimization at Stanford

10. Minicourse on convex optimization by S. Boyd'a

11. Nonlinear Optimization by A. Ruszczy

12. Convex Optimization: Algorithms and Complexity by S. Bubeck

13. Blog by S. Bubeck

14. Numerical Optimization by J. Nocedal & S. J. Wright

15. Lectures on Modern Convex Optimization by A. Nemirovski

16. Review of Stochactic Optimization Algorithms

17. Semidefinite Optimization by M. Laurent & F. Vallentin

Contributing

If you want to send pull-request, please read the following instruction