Optimization Methods

2020/2021

Учебный год

ENG

Обучение ведется на английском языке

5

Кредиты

Кто читает:

Департамент больших данных и информационного поиска

Статус:

Курс обязательный

Когда читается:

3-й курс, 3, 4 модуль

Преподаватель

Хамисов Олег Валерьевич

Course Syllabus

Abstract

Optimization holds an important place in both practical and theoretical worlds, as understanding the timing and magnitude of actions to be carried out helps achieve a goal in the best possible way. This course emphasizes data-driven modeling, theory and numerical algorithms for optimization with real variables. The course gives a comprehensive foundation for theory, methods and algorithms of mathematical optimization. The prerequisites are linear algebra and calculus.

Learning Objectives

• Students will study main concepts of optimization theory and develop a methodology for theoretical investigation of optimization problems.
• Students will obtain an understanding of creation, effectiveness and application optimization methods and algorithms on practice.
• The course will give students the possibility of solving standard and nonstandard mathematical problems connected to finding optimal solutions.

Expected Learning Outcomes

• Students should be able to classify optimization problems according to their mathematical properties.
• Students should be able to perform a theoretical investigation of a given optimization problem in order to access its complexity.
• Students should be able to write down first and second-order optimality conditions.
• Students should be able to write down first and second-order optimality condition.
• Students should be able to provide a dual analysis of linear and convex optimization problems.
• Students should be able to acces the rate of convergence of the first and second order optimization methods.
• Students should be able to describe the numerical complexity of the optimization algorithms studied during the course.
• Students should be able to solve simple optimization problems without computer.
• Students should be able to implement different optimization codes in a computer environment.
• Students should be able to analyse the obtained solutions.
• Students should have an understanding of decomposition, parallel and distributed optimization.

Course Contents

• One-dimensional optimization: unimodal functions, convex and quasiconvex functions, zero and first-order methods, local and global minima.
• Existence of solutions: continuous and lower semicontinuous functions, coercive functions, Weierstrass theorem, unique and nonunique solutions.
• Linear optimization: primal and dual linear optimization problems, the simplex methods, interior-point methods, post-optimal analysis.
• Theory of optimality conditions: Fermat principle, the Hessian matrix, positive and negative semidefinite matrices, the Lagrange function and Lagrange multipliers, the Karush-Kuhn-Tucker conditions, regularity, complementarity constraints, stationary points.
• First-order optimization methods: the steepest descent method, conjugate directions, gradient-based methods.
• Second order optimization methods: Newton's method and modifications, trust-region methods.
• Convex optimization: optimality conditions, duality, subgradients and subdifferential, cutting planes and bundle methods, the complexity of convex optimization.
• Decomposition: Dantzig-Wolfe decomposition, Benders decomposition, distributed optimization.
• Conic programming: conic quadratic programming, semidefinite programming, iterior point polinomial time methods for conic programming.
• Nonconvex optimization: weakly and d.c. functions, convex envelopes and underestimators, branch and bound technique.

Assessment Elements

• Control assignments
• Exam

Interim Assessment

• Interim assessment (4 module)
  0.6 * Control assignments + 0.4 * Exam

Bibliography

Recommended Core Bibliography

• Arkadi Nemirovski. (2001). Lectures on modern convex optimization. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.5E080C05
• Mokhtar S. Bazaraa, Hanif D. Sherali, & C. M. Shetty. (2006). Nonlinear Programming : Theory and Algorithms: Vol. 3rd ed. Wiley-Interscience.

Recommended Additional Bibliography

• Yurii Nesterov. (2018). Lectures on Convex Optimization (Vol. 2nd ed. 2018). Springer.