1 of 26

Методы оптимизации:�семинар 12

ФКН НИУ ВШЭ

2024-2025

Маминов А.Д.

2 of 26

2

Условная оптимизация: квадратичное программирование

3 of 26

Квадратичное программирование

  • Квадратичное программирование (Quadratic Programming, QP) – это специальный класс задач оптимизации с ограниченями
  • Квадратичная целевая функция, линейные функции ограничений (равенства и неравенства)
  • Цель: найти вектор, который минимизирует целевую функцию и удовлетворяет всем ограничениям.
  • Примеры задач:
    • Поиск автоматического управления (линейные системы и квадратичный функционал качества)
    • Задачи машинного обучения (SVM, Constrained least-squares и д.р.)
    • Задача оптимизации портфеля
    • Последовательное квадратичное программирование
    • Многое другое

3

4 of 26

Постановка задачи

  •  

4

5 of 26

Постановка задачи

  •  

5

6 of 26

Постановка задачи: Пример

  •  

6

7 of 26

Постановка задачи: Пример

  •  

7

8 of 26

Постановка задачи

  •  

8

9 of 26

Постановка задачи

  •  

9

10 of 26

Постановка задачи

  •  

10

11 of 26

Условие оптимальности Каруша – Куна – Таккера

  •  

11

12 of 26

Частный случай

  •  

12

13 of 26

Двойственность Лагранжа и двойственная задача

  •  

13

14 of 26

Двойственность Лагранжа и двойственная задача

  •  

14

15 of 26

Двойственность Лагранжа и двойственная задача

  •  

15

16 of 26

Линейная задача о дополнительности (LCP)

  •  

16

17 of 26

Линейная задача о дополнительности (LCP)

  •  

17

18 of 26

Линейная задача о дополнительности (LCP)

  •  

18

19 of 26

Подходы к решению

    • Методы условной оптимизации, рассмотренные на предыдущих семинарах
    • Алгоритм Лемке
    • Метод эллипсоидов
    • Методы внутренней точки (Interior point methods)
    • Методы активного набора (Active set methods)
    • Метод множителей с переменным направлением (Alternating Direction Method of Multipliers)

​

​

19

20 of 26

Подходы к решению

    • Методы условной оптимизации, рассмотренные на предыдущих семинарах
    • Алгоритм Лемке
    • Метод эллипсоидов
    • Методы внутренней точки (Interior point methods)
    • Методы активного набора (Active set methods)
    • Метод множителей с переменным направлением (Alternating Direction Method of Multipliers)

​

​

20

21 of 26

Подходы к решению

    • Выбор метода зависит от реализации и характера задачи
    • Методы активного набора (Active set methods): Gurobi, CPLEX, qpOASES
      • Хорошо подходит для небольших задач с небольшим количеством ограничений
      • Может использовать преимущества, если есть хорошая начальная точка (warm start)
    • Методы внутренней точки (Interior point methods): Gurobi, CPLEX, MOSEK, CVXOPT
      • Хорошо подходит для больших задач с большим количеством активных ограничений
      • Почти не использует преимущество хорошей начальной точки
    • Метод множителей с переменным направлением (Alternating Direction Method of Multipliers): OSQP
      • Хорошо подходит как для небольших, так и для больших задач, с небольшим числом активных ограничений
      • Может использовать преимущества, если есть хорошая начальная точка (warm start)

​

21

22 of 26

Подходы к решению

    • Выбор метода зависит от реализации и характера задачи
    • Методы активного набора (Active set methods): Gurobi, CPLEX, qpOASES
      • Хорошо подходит для небольших задач с небольшим количеством ограничений
      • Может использовать преимущества, если есть хорошая начальная точка (warm start)
    • Методы внутренней точки (Interior point methods): Gurobi, CPLEX, MOSEK, CVXOPT
      • Хорошо подходит для больших задач с большим количеством активных ограничений
      • Почти не использует преимущество хорошей начальной точки
    • Метод множителей с переменным направлением (Alternating Direction Method of Multipliers): OSQP
      • Хорошо подходит как для небольших, так и для больших задач, с небольшим числом активных ограничений
      • Может использовать преимущества, если есть хорошая начальная точка (warm start)

​

22

23 of 26

Подходы к решению

    • Выбор метода зависит от реализации и характера задачи
    • Методы активного набора (Active set methods): Gurobi, CPLEX, qpOASES
      • Хорошо подходит для небольших задач с небольшим количеством ограничений
      • Может использовать преимущества, если есть хорошая начальная точка (warm start)
    • Методы внутренней точки (Interior point methods): Gurobi, CPLEX, MOSEK, CVXOPT
      • Хорошо подходит для больших задач с большим количеством активных ограничений
      • Почти не использует преимущество хорошей начальной точки
    • Метод множителей с переменным направлением (Alternating Direction Method of Multipliers): OSQP
      • Хорошо подходит как для небольших, так и для больших задач, с небольшим числом активных ограничений
      • Может использовать преимущества, если есть хорошая начальная точка (warm start)

​

23

24 of 26

Подходы к решению

    • Выбор метода зависит от реализации и характера задачи
    • Методы активного набора (Active set methods): Gurobi, CPLEX, qpOASES
      • Хорошо подходит для небольших задач с небольшим количеством ограничений
      • Может использовать преимущества, если есть хорошая начальная точка (warm start)
    • Методы внутренней точки (Interior point methods): Gurobi, CPLEX, MOSEK, CVXOPT
      • Хорошо подходит для больших задач с большим количеством активных ограничений
      • Почти не использует преимущество хорошей начальной точки
    • Метод множителей с переменным направлением (Alternating Direction Method of Multipliers): OSQP
      • Хорошо подходит как для небольших, так и для больших задач, с небольшим числом активных ограничений
      • Может использовать преимущества, если есть хорошая начальная точка (warm start)

​

24

25 of 26

Рассмотрим пример

  •  

25

26 of 26

Поиск ближайшей точки

  •  

26