Докладчик: Роланд Хильдебранд
Аннотация: Разные задачи оптимизации имеют разную сложность. Обычно данную задачу сначала пытаются свести к задаче из некоторого стандартного класса, для которого имеется эффективный метод решения. Если это не удается, можно попытаться аппроксимировать данную задачу стандартной, т.е. применить так называемую релаксацию. В качестве стандартных задач выступают задачи конического программирования над симметрическими конусами, т.е. линейные, квадратично-конические и полу-определенные программы. Многие выпуклые и невыпуклые задачи легко сводятся к задаче конического программирования над более сложным конусом. В этом случае проблема сводится к тому, чтобы представить этот конус в виде линейной проекции некоторого линейного сечения симметрического конуса. Конус, допускающий такое представление, называется полу-определенно представимым. На первой лекции мы рассмотрим общую теорию полу-определенной представимости, в частности теорему Янакакиса, неотрицательный ранг и их обобщения. Мы также рассмотрим некоторые стандартные релаксации, т.е. аппроксимации сложных конусов полу-определенно представимыми. В некоторых случаях удается доказать точность релаксации или же ограничить допускаемую при релаксации ошибку. Классическими примерами являются релаксация проблемы MaxCut Геманса-Виллиамсона и $\frac{\pi}{2}$-теорема Нестерова.
Место проведения: 907 аудитория корпуса прикладной математики (КПМ), МФТИ
Дата: 25 марта 2020
Время: 19:20
[Страница курса] [Видео] [Материалы]

Докладчик: Роланд Хильдебранд
Аннотация: Часто возникает ситуация, в которой данные, определяющие задачу конического программирования, неточные, а могут варьировать в некотором множестве неопределенности, центрированном на номинальных значениях. Решение номинальной задачи, т.е. задачи с номинальными коэффициентами, может дать плохой результат или быть недопустимым для коэффициентов в других точках множества неопределенности. В этом случае целесообразно рассмотреть робастную версию задачи, решение которой дает наилучший гарантированный результат для любой реализации неточных коэффициентов в множестве неопределенности. Робастная задача конического программирования сама является задачей конического программирования, но над более сложным конусом. Этот конус можно охарактеризовать как конус положительных отображений, т.е. множества линейных отображений, переводящих некоторый данный конус в подмножестсво другого данного конуса. Эти два конуса, находящиеся в исходном и в целевом пространстве рассматриваемых линейных отображений, зависят от множества неопределенности и от конуса в исходной неробастной задаче. На второй лекции мы рассмотрим вопрос полу-определенной представимости или релаксации конуса положительных отображений и приведем примеры, в которых это возможно либо точно, либо с гарантией на допускаемую при релаксации ошибку.
Место проведения: 907 аудитория корпуса прикладной математики (КПМ), МФТИ
Дата: 1 апреля 2020
Время: 19:20
[Страница курса] [Видео] [Материалы]

Докладчик: Роланд Хильдебранд
Аннотация: Любую, сколь угодно сложную задачу оптимизации можно записать как формально выпуклую задачу конического программирования на бесконечно-мерном конусе неотрицательных мер с носителем в допустимом множестве исходной задачи. В случае, когда функция цены и ограничения исходной задачи полиномиальные, эту бесконечно-мерную задачу удается свести к конечно-мерной задаче конического программирования над конусом моментов неотрицательных мер. Конуса моментов обладают иерархией полу-определенных релаксаций, при этом точность релаксации увелечивается по мере того, как берутся во внимание моменты все более высокого порядка. На третьей лекции мы рассмотрим общую теорию моментных релаксаций полиномиальных задач оптимизации и двойственных им аппроксимаций неотрицательных полиномов суммами квадратов. Мы также рассмотрим частные случаи, в которых эти релаксации точны. Наряду с обычными полиномами мы коснемся и неотрицательных тригонометрических полиномов. Соответствующие конуса моментов широко используются в решении задач управления и идентификации линейных динамических систем в пространстве частот.
Место проведения: 907 аудитория корпуса прикладной математики (КПМ), МФТИ
Дата: 8 апреля 2020
Время: 19:20
[Страница курса] [Видео] [Материалы] [Слайды]

Докладчик: Роланд Хильдебранд
Аннотация: На последней лекции мы рассмотрим весьма оригинальное приложение моментных релаксаций для решения задач оптимального управления с полиномиальными данными. Вначале мы дадим краткое введение в теорию вариационного исчисления и оптимального управления. Классическая задача оптимального управления применением принципа максимума Понтрягина сводится к нахождению решения гамильтоновой динамической системы с разрывной правой частью, удовлетворяющего краевым условиям трансверсальности. Эта проблема в свою очередь сводится к бесконечно-мерной задаче конического программирования на конусе мер оккупации. Полиномиальная структура исходной задачи позволяет ограничиться конечно-мерным конусом моментов мер оккупации, который дальше релаксируется стандартными методами. Таким образом мы получаем иерархию полу-определенных релаксаций для исходной задачи оптимального управления.
Место проведения: 907 аудитория корпуса прикладной математики (КПМ), МФТИ
Дата: 15 апреля 2020
Время: 19:20
[Страница курса] [Видео] [Материалы] [Слайды]