Optimization Methods

2023/2024

Academic Year

ENG

Instruction in English

5

ECTS credits

Delivered at:

Big Data and Information Retrieval School

Course type:

Compulsory course

When:

3 year, 1, 2 module

Instructors

Ignatov, Andrei

Крсманович Марко

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

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.

Assessment Elements

• Control Testing 1
  All testings consist of tasks, devoted to different topics of the course.
• Final test
  All testings consist of tasks, devoted to different topics of the course.
• Control Testing 2
  All testings consist of tasks, devoted to different topics of the course.
• Control Testing 3
  All testings consist of tasks, devoted to different topics of the course.

Interim Assessment

• 2023/2024 2nd module
  Grade FG - Final Grade, for the course is determined by the formula: FG=0.7*(CT1+CT2+CT3)+0.3*FT, where CT - Control Testing 1,2, and 3, FT - Final Testing. In case a student has no objections to the total grade obtained during CT1, CT2 and CT3 + FT, he/she can get an automatic pass and get this grade. Otherwise this student will take an additional test with a maximum grade of 5 out of 10. If a student doesn't solve any tests during the semester, his/her grade at the exam is limited by 5 out of 10.

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.