Выпуклый анализ — это ветвь математики, посвящённая изучению свойств выпуклых функций и выпуклых множеств, часто имеющая приложения в выпуклом программировании, подобласти теории оптимизации.
Выпуклые множества
Выпуклое множество является множеством для некоторого векторного пространства X, такое что для любых и .
Выпуклая функция
Выпуклая функция — любая расширенная вещественнозначная функция , которая удовлетворяет неравенству Йенсена, то есть, для любых и любой .
Эквивалентно, выпуклой функцией является любая (расширенная) вещественнозначная функция, такая что её надграфик
является выпуклым множеством.
Выпуклое сопряжение
Выпуклое сопряжение расширенной вещественнозначной (не обязательно выпуклой) функции — это функция , где X* является двойственным пространством пространства X, такая что
Двойное сопряжение Двойное сопряжение функции — это сопряжение сопряжения, что обычно записывается как . Двойное сопряжение полезно, когда нужно показать, что выполняется сильная или слабая двойственность (с помощью ).
Для любого неравенство вытекает из неравенства Фенхеля. Для f = f** тогда и только тогда, когда f выпукла и полунепрерывна снизу по теореме Фенхеля — Моро.
Выпуклая минимизация
(Прямая) задача выпуклого программирования, это задача вида
такая что является выпуклой функцией, а является выпуклым множеством.
Двойственная задача
Принцип двойственности в оптимизации утверждает, что задачи оптимизации можно рассматривать с двух точек зрения, как прямую задачу или двойственную задачу.
общем случае, если дана Двойственная пара — это тройка , где — векторное пространство над полем , — множество всех линейных отображений , а третий элемент — билинейная форма . отделимых локально выпуклых пространств и функция , мы можем определить прямую задачу как нахождение такого , что Другими словами, — это инфимум (точная нижняя граница) функции .
Если имеются ограничения, они могут быть встроены в функцию , если положить , где — . Пусть теперь (для другой двойственной пары ) будет , такой что .
Двойственная задача для этой функции возмущения по отношению к выбранной задаче определяется как
где F* является выпуклым сопряжением по обоим переменным функции F.
Разрыв двойственности — это разность правой и левой частей неравенства
где — выпуклое сопряжение от обоих переменных, а означает супремум (точную верхнюю границу).
Этот принцип тот же самый, что и слабая двойственность. Если обе стороны равны, говорят, что задача удовлетворяет условиям сильной двойственности.
Существует много условий для сильной двойственности, такие как: F = F**, где F является для прямой и двойственной задач, а F** является двойным сопряжением функции F; прямая задача является задачей линейного программирования; Условие Слейтера для задач выпуклого программирования.
Двойственность Лагранжа Для выпуклой задачи минимизации с ограничениями-неравенствами
при условиях для i = 1, …, m.
двойственной задачей Лагранжа будет
при условиях для i = 1, …, m,
где целевая функция L(x, u) является двойственной функцией Лагранжа, определённой следующим образом:
Примечания
Литература Осипенко К.Ю. Оптимизация. Ч. 1. Выпуклый анализ (консп. лекций). М.: МГУ. 57 с. Осипенко К.Ю. Выпуклый анализ (программа курса и консп. лекций). М.: МГУ. 68 с. Петров Н.Н. Выпуклый анализ (консп. лекций). Ижевск: УдмГУ, 2009. 160 с. Жадан В. Г. Методы оптимизации. Часть I. Введение в выпуклый анализ и теорию оптимизации: учеб. пос. для студ. вузов по направл. ... "Прикладные математика и физика". Москва : МФТИ, 2014. ISBN 978-5-7417-0514-8. (Ч. I). 271 с. Выпуск 300 шт. Элементы выпуклого и сильно выпуклого анализа : учебное пособие для студентов высших учебных заведений, обучающихся по направлению "Прикладные математика и физика" и смежным направлениям и специальностям / Е. С. Половинкин, М. В. Балашов. - 2-е изд., испр. и доп. - Москва : Физматлит, 2007. - 438 с.; 22 см. - (Физтеховский учебник).; ISBN 978-5-9221-0896-6 Протасов В.Ю. Выпуклый анализ (консп. лекций. Мехмат МГУ, экономич. поток, 2009 г.). М.: МГУ.
Категория:Выпуклый анализ Категория:Выпуклая геометрия Категория:Вариационный анализ