Опукла оптимізація — це підрозділ математичної оптимізації, котрий вивчає проблему мінімізації опуклих функцій над опуклими множинами. Багато класів задач з опуклою оптимізацією допускають поліноміальні алгоритми тоді як математична оптимізація в цілому NP-важкаSahni, S. "Computationally related problems, " in SIAM Journal on Computing, 3, 262—279, 1974.Quadratic programming with one negative eigenvalue is NP-hard, Panos M. Pardalos and Stephen A. Vavasis in Journal of Global Optimization, Volume 1, Number 1, 1991, pg.15-22..
Опукла оптимізація має застосування в широкому спектрі дисциплін, таких як автоматичні системи управління, оцінка та обробка сигналів, комунікації та мережі, проєктування електронних схем, аналіз та моделювання даних, фінанси, статистика (оптимальний експериментальний дизайн),Chritensen/Klarbring, chpt. 4. та структурна оптимізація, де концепція наближення виявилась ефективною.Schmit, L.A.; Fleury, C. 1980: Structural synthesis by combining approximation concepts and dual methods. З недавніми досягненнями в галузі обчислювальних та оптимізаційних алгоритмів, опукле програмування майже настільки ж просте, як і лінійне програмування.
Визначення Проблема оптимізації опуклості — це проблема оптимізації, в якій цільова функція є опуклою функцією, а допустимою множиною є опукла множина. Функція відображення деякої підмножини в опукла, якщо її домен опуклий і для всіх і також для всіх у своєму домені виконується така умова: . Множина S опукла, якщо для всіх членів і для всіх , у нас є, що .
Конкретно, проблема опуклої оптимізації — це проблема пошуку маючи
,
де об'єктивна функція є опуклою, як і допустима множина . Якщо така точка існує, вона називається оптимальною точкою ; множина всіх оптимальних точок називається оптимальною множиною. Якщо є необмеженою внизу над або мінімум не досягнуто, тоді, як кажуть, проблема оптимізації є необмеженою. Інакше, якщо є порожньою множиною, тоді проблема, як кажуть, невирішувана.
Стандартна форма Кажуть, що проблема опуклої оптимізації є в стандартній формі, якщо вона записана як
де — змінна оптимізації, функції є опуклими, і функції є афінними. У цьому позначенні функція — це цільова функція задачі, і функції і називаються функціями обмеження. Можливим набором задачі оптимізації є множина, що складається з усіх точок задовольняючи і . Ця множина є опуклою, оскільки підмножини опуклих функцій опуклі, афінні множини опуклі, а перетин опуклих множин — опуклий.
Багато проблем оптимізації можуть бути сформульовані в цій стандартній формі. Наприклад, проблема максимізації увігнутої функції може бути переформульовано як проблема мінімізації опуклої функції ; така проблема максимізації увігнутої функції над опуклою множиною часто називається проблемою оптимізації опуклої форми.
Властивості Наступні корисні властивості задач опуклої оптимізації:
кожен локальний мінімум — це глобальний мінімум; оптимальна множина опукла; якщо цільова функція строго опукла, то задача має щонайменше одну оптимальну точку.
Ці результати використовуються теорією опуклої мінімізації разом з геометричними поняттями функціонального аналізу (в просторах Гільберта), такими як теорема проєкції Гільберта, теорема розділення гіперплан та лема Фаркаса.
Приклади Перелічені класи задач — це все задачі опуклої оптимізації, або їх можна звести до задачі опуклої оптимізації за допомогою простих перетворень:
Найменші квадрати Лінійне програмування Опукла квадратична мінімізація з лінійними обмеженнями Квадратна мінімізація з опуклими квадратичними обмеженнями Конічна оптимізація Геометричне програмування Програмування конуса другого порядку Напівскінченне програмування Максимізація ентропії з відповідними обмеженнями
Множники Лагранжа Розглянемо проблему мінімізації опуклої форми, задану в стандартній формі функцією витрат та обмеженням нерівності для . Домен є:
Функцією Лагранжа для задачі є
Для кожної точки в що мінімізує над , існують реальні числа котрі називаються множниками Лагранжа, які одночасно задовольняють ці умови:
мінімізує над усім принаймні з одним (додаткова млявість).
Якщо існує «строго допустима точка», тобто точка , котра задовольняє
тоді твердження вище може вимагати .
І навпаки, якщо якісь в задовольняють (1) — (3) для скалярів з , то мінімізує над .
Алгоритми Задачі опуклої оптимізації можуть бути розв'язані такими сучасними методами:Для методів для опуклої мінімізації див. книги від Hiriart-Urruty і Lemaréchal, а також підручники від Ruszczyński і Bertsekas і від Boyd і Vandenberghe (внутрішня точка).
Методи розшарування (Вулф, Лемарель, Ківіль) та Методи субградієнтної проєкції (Поляк), Методи внутрішніх точок, в яких використовуються самокорегуючі бар'єрні функції та саморегулярні бар'єрні функції. Ріжучі площинні методи Еліпсоїдний метод Субградієнтний метод Подвійні субградієнти та метод дрейфу плюс-штраф
Субградієнтні методи можуть бути реалізовані просто і тому широко застосовуються.Bertsekas Подвійні субградієнтні методи — це субградієнтні методи, застосовані до подвійної задачі. Метод дрейфування плюс-штрафу схожий з методом подвійного субградієнта.
Розширення Розширення опуклої оптимізації включають оптимізацію функцій двоопуклої, псевдоопуклої та квазіопуклої. Розширення теорії опуклого аналізу та ітеративних методів приблизно розв'язування задач мінімізації, що не є опуклими, відбуваються в області узагальненої опуклості, також відомої як абстрактний опуклий аналіз.
Див. також
Двоїстість (оптимізація) Умови Каруша — Куна — Такера Задача оптимізації Метод проксимального градієнта Алгоритм Франк — Вульфа
Примітки
Список літератури
Борвейн, Джонатан та Льюїс, Адріан. (2000). Аналіз опуклості та нелінійна оптимізація. Спрингер.
Хіріарт-Урруті, Жан-Батист і Лемарешал, Клод. (2004). Основи опуклого аналізу. Берлін: Спрінгер.
Нестеров, Юрій. (2004). Вступні лекції з опуклої оптимізації, наукові видавці Kluwer
Шміт, Л.А.; Флері, C. 1980: Структурний синтез шляхом поєднання концепцій наближення та подвійних методів. Дж. Амер. Інст. Аеронавт. Астронавт 18, 1252—1260
Посилання
Стівен Бойд та Лівен Ванденберге, опукла оптимізація (книга в pdf) EE364a: Опукла оптимізація I та EE364b: Опукла оптимізація II, домашні сторінки курсу «Стенфорд» 6.253: Опуклий аналіз та оптимізація, домашня сторінка курсу MIT OCW Брайан Борчерс, Огляд програмного забезпечення для опуклої оптимізації