Владимир Юрьевич Протасов

Выпуклая геометрия: от работ Минковского к современным задачам оптимизации

В.Ю.Протасов планирует провести 4 занятия

Основы геометрии выпуклых тел и выпуклых многогранников были заложены в работах Г. Минковского к началу XX века. Долгое время выпуклая геометрия справедливо считалась чрезвычайно красивой, хотя и совершенно бесполезной для приложений областью математики. Ее важность для прикладных задач выяснилась много позже, через 60–70 лет, когда развитие выпуклой оптимизации (называемой еще выпуклым программированием) «уперлось» в некоторые факты о выпуклых телах. Дело в том, что ряд классических неравенств и оценок, полученных в начале XX века для произвольных выпуклых тел, несильно зависят (либо не зависят вовсе) от размерности пространства. Это позволило избежать «проклятия размерности» — традиционной беды, когда сложность задачи катастрофически растет с увеличением числа переменных. Сейчас алгоритмы выпуклой оптимизации содержатся в большинстве пакетов прикладных компьютерных программ.

Мы начнем с симметризации выпуклых тел по Минковскому и докажем неравенство Брунна-Минковского (методом Б.Н.Делоне). С его помощью установим некоторые свойства центра тяжести, в частности, неравенство Грюнбаума-Хаммера об объемах. На этих результатах основан метод отрезающих плоскостей Левина-Ньюмена, один из первых алгоритмов выпуклой оптимизации. Затем определим эллипсоиды Лёвнера и Джона, которые приведут нас к методу эллипсоидов Немировского-Шора, и далее — к теореме Хачияна о полиномиальной разрешимости задач линейного программирования. Далее докажем теорему Минковского о многограннике с заданными площадями и направлениями граней. Если останется время, поговорим о наиболее современном и эффективном методе выпуклой оптимизации — методе внутренней точки.

Доказательства, как правило, будут элементарны и доступны школьникам. Единственное, что требуется — пространственное воображение.

Organization Committee e-mail:
dubna@mccme.ru