Optimization Methods

2024/2025

Учебный год

ENG

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

4

Кредиты

Кто читает:

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

Статус:

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

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

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

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

Игнатов Андрей Дмитриевич

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 acces the rate of convergence of the first and second order optimization methods.
• Students should be able to classify optimization problems according to their mathematical properties.
• Students should be able to describe the numerical complexity of the optimization algorithms studied during the course.
• Students should be able to implement different optimization codes in a computer environment.
• 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 solve simple optimization problems without computer.
• Students should be able to write down first and second-order optimality condition.
• Students should be able to write down first and second-order optimality conditions.

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.
• Quadratic unconstrained optimization: algebraic solution, complete optimization analysis, steepest descent and conjugate gradient methods.
• 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.
• Computational optimization methods: first-order, second-order, Quasi-Newton methods
• Linear Programming, Knapsack problem
• Combinatorial optimization, Transport problems
• Multi-criteria optimization

Assessment Elements

• Home Assignments
• Controlled Assessements
• Final Exam

Interim Assessment

• 2024/2025 2nd module
  Final grade = 0.6 * Cumulative + 0.4 * Final exam. The cumulative is rounded off mathematically, includes Home Assinments and Controlled Assessements which have equal weights.

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.

Authors

• KHAMISOV OLEG VALEREVICH
• IGNATOV ANDREY DMITRIEVICH
• USOV ALEKSANDR LEONIDOVICH