Опуклий аналіз — це гілка математики, присвячена вивченню властивостей опуклих функцій і опуклих множин, часто застосовується в опуклому програмуванні, підгалузі теорії оптимізації.
Опуклі множини Опукла множина — це множина для деякого векторного простору X, така що для будь-яких і
.
Опукла функція Опукла функція — це будь-яка розширена дійснозначна функція , яка задовольняє нерівності Єнсена, тобто, для будь-яких і будь-якого
.
Еквівалентно, опуклою функцією є будь-яка (розширена) дійснозначна функція, така що її надграфік
є опуклою множиною.
Опукле спряження Опукле спряження розширеної (не обов'язково опуклої) функції — це функція , де X* — спряжений простір простору X, така що
Подвійне спряження Подвійне спряження функції — це спряження спряження, що зазвичай записують як . Подвійне спряження корисне, коли потрібно показати, що виконується сильна або слабка двоїстість (за допомогою ).
Для будь-кого нерівність випливає з нерівності Фенхеля. Для f = f** тоді й лише тоді, коли f опукла і напівнеперервна знизу за теоремою Фенхеля — Моро.
Опукла мінімізація (Пряма) задача опуклого програмування, це задача вигляду
така що є опуклою функцією, а є опуклою множиною.
Двоїста задача Принцип двоїстості в оптимізації стверджує, що задачу оптимізації можна розглядати з двох точок зору як пряму задачу або двоїсту задачу.
Загалом, якщо дано Двоїста пара — це трійка , де — векторний простір над полем , — множина всіх лінійних відображень , а третій елемент — білінійна форма . відокремлюваних локально опуклих просторів та функцію , можна визначити пряму задачу як знаходження такого , що Іншими словами, — це інфімум (точна нижня границя) функції .
Якщо є обмеження, їх можна вбудувати у функцію , якщо покласти , де — . Нехай тепер (для іншої двоїстої пари ) — , така що .
Двоїста задача для цієї функції збурення відносно вибраної задачі визначається як
де F* — опукле спряження за обома змінними функції F.
Розрив двоїстості — це різниця правої та лівої частин нерівності
де — опукле спряження від обох змінних, а означає супремум (точна верхня границя) .
Цей принцип збігається зі слабкою двоїстістю. Якщо обидві сторони рівні, кажуть, задача задовольняє умовам сильної двоїстості.
Існує багато умов для сильної двоїстості, такі як:
F = F**, де F — для прямої та двоїстої задач, а F** — подвійне спряження функції F; пряма задача є задачею лінійного програмування; Умова Слейтера для задач опуклого програмування.
Двоїстість Лагранжа Для опуклої задачі мінімізації з обмеженнями-нерівностями
за умов для i = 1, …, m .
двоїстою задачею Лагранжа буде
за умов для i = 1, …, m ,
де цільова функція є двоїстою функцією Лагранжа, визначеною так:
Примітки
Література Осипенко К. Ю. Оптимизация. Ч. 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 г.). : МГУ.