О курсе
Организован для стyдентов 4 и 5 кyрса потоков ФУПМ.
Цель курса — обучить студентов современным методам выпуклой оптимизации и их применению в решении задач выпуклой и невыпуклой оптимизации. Особый упор будет сделан на коническую оптимизацию, начиная с линейного программирования, и переходя к более сложным задачам конично-квадратичного и полуопределённого программирования. В тесной связке с самими методами идут вопросы моделирования, т.е. представления конкретных задач в стандартном виде конической программы. Если же это невозможно, применяются разные техники построения выпуклых аппроксимаций (релаксаций), которых можно привести к виду конической программы. Будут рассмотрены также некоторые стандартные методы невыпуклой оптимизации, опирающиеся на решение последовательности выпуклых задач, в частности, методов типа ограничений и ветвлений.
Курс начнётся с предоставления теоретической базы: векторные и аффинные пространства, топология, нормы, двойственность, выпуклые множества и конусы и операции над ними, опорные плоскости, теоремы отделимости, фасады и экстремальные точки и лучи, а также общий вид задач оптимизации, выпуклость и сложность задач оптимизации, классы задач.
Будут представлены простые методы решения выпуклых задач, которые могут быть использованы как элементарные блоки в более сложных алгоритмах: методы одномерного поиска, метод эллипсоидов, аналитические формулы для решения простых квадратичных задач.
Всесторонне будет освещаться теория, методы и приложения линейного программирования (ЛП): полиэдры и полиэдральные конуса, политопы, двойственность, теорема об альтернативе, сложность представления полиэдра, задача ЛП в стандартном виде; симплекс-метод и его варианты, методы внутренней точки, методы решения задач линейной комплементарности; прикладные задачи, сводящиеся к задаче ЛП, линейные релаксации невыпуклых задач, методы решения смешанно-целочисленных ЛП.
Коническое программирование: конусы Лоренца и конично-квадратичные задачи, матричные конусы и полу-определённое программирование, само-согласованные барьеры, методы внутренней точки для программ над симметричными и несимметричными конусами, представимость одного конуса через другой.
Робастная оптимизация: робастный аналог конической программы, его сведение к обычной конической программе, полу-определённые релаксации робастных аналогов.
Приложения конического программирования: описанный эллипсоид минимального объёма, вписанный эллипсоид максимального объёма, оптимизация топологии фермы, построение функций Ляпунова, построение регулятора для линейных динамических систем.
Полиномиальная оптимизация: положительные полиномы и их аппроксимация суммами квадратов, случаи, в которых релаксация точна, внутренние и внешние моментные релаксации. Комплексно-эрмитовый случай: тригонометрические полиномы, векторы состояния и матрицы плотности составных квантовых систем, условие положительности частичной транспонированной.
Ведущие курса
Роланд Хильдебранд