Skip to content

lixiaohang/MIPT-Opt

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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).

Almost all numerical tests in this repository are performed with liboptpy library, where you can find easy to use implementations of different optimization methods. Also we use CVXPY 1.0 for comparison purpose.

Fall term

  1. Introduction (ru, en). Demo of convex optimization power (ru Open In Colab, 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) + smoothing demo Open In Colab

  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 Open In Colab, en Open In Colab)

    • Applications of convex optimization and CVXPy (ru Open In Colab, en)
    • Disciplined convex programming and autograd with PyTorch (ru Open In Colab, en)
  2. Unconstrained optimization problems

    • Gradient descent (ru, en)
    • Heavy-ball method and accelerated Nesterov method (ru Open In Colab, en)
    • Newton method (ru Open In Colab, en Open In Colab)
    • Quasi-Newton methods (ru, en)
    • Conjugate gradient method (ru Open In Colab, en Open In Colab)
    • Subgradient method and intro to proximal methods (ru, en Open In Colab)
  3. Linear programming

    • Simplex method (ru Open In Colab, en Open In Colab)
    • Primal interior point method (ru Open In Colab, en Open In Colab)
  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 Open In Colab, en Open In Colab)
  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 (ru, en)
  10. Submodular optimization
  11. ...

References

Books, lecture notes and blogs

Related courses

Contributing

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

About

A course on Optimization Methods

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Jupyter Notebook 98.6%
  • TeX 1.4%