Выпуклое программирование

Выпуклое программирование — это подобласть математической оптимизации, которая изучает задачу минимизации выпуклых функций на выпуклых множествах. В то время как многие классы задач выпуклого программирования допускают алгоритмы полиномиального времени[1], математическая оптимизация в общем случае NP-трудна[2][3][4].

Выпуклое программирование находит применение в целом ряде дисциплин, таких как автоматические системы управления, оценка и обработка сигналов, коммуникации и сети, схемотехника[5], анализ данных и моделирование, финансы, статистика (оптимальный план эксперимента[en])[6] и структурная оптимизация[en][7]. Развитие вычислительной техники и алгоритмов оптимизации сделало выпуклое программирование почти столь же простым как линейное программирование[8].

ОпределениеПравить

Задача выпуклого программирования — это задача оптимизации, в которой целевая функция является выпуклой функцией и область допустимых решений выпукла. Функция  , отображающая некоторое подмножество   в  , является выпуклой, если область определения выпукла и для всех  , и всех   в их области определения  . Множество выпукло, если для всех его элементов   и любого   также и   принадлежит множеству.

В частности, задачей выпуклого программирования является задача нахождения некоторого  , на котором достигается

 ,

где целевая функция   выпукла, как и множество допустимых решений  [9][10]. Если такая точка существует, её называют оптимальной точкой. Множество всех оптимальных точек называется оптимальным множеством. Если   не ограничена на   или инфимум не достигается, говорят, что оптимизации не ограничена. Если же   пусто, говорят о недопустимой задаче[11].

Стандартная формаПравить

Говорят, что задача выпуклого программирования представлена в стандартной форме, если она записана как

Минимизировать  
При условиях
 

где   является переменной оптимизации, функции   выпуклы, а функции   аффинны [11].

В этих терминах функция   является целевой функцией задачи, а функции   и   именуются функциями ограничений. Допустимое множество решений задачи оптимизации — это множество, состоящее из всех точек  , удовлетворяющих условиям   и  . Это множество выпукло, поскольку множества подуровня выпуклой функции выпуклы, аффинные множества также выпуклы, а пересечение выпуклых множеств является выпуклым множеством[12].

Многие задачи оптимизации можно привести к этой стандартной форме. Например, задача максимизации вогнутой функции   может быть переформулирована эквивалентно как задача минимизации выпуклой функции  , так что о задаче максимизации вогнутой функции на выпуклом множестве часто говорят как о задаче выпуклого программирования

СвойстваПравить

Полезные свойства задач выпуклого программирования[13][11]:

Эти результаты используются в теории выпуклой минимизации вместе с геометрическими понятиями из функционального анализа (на гильбертовых пространствах), такими как теорема проектирование Гильберта[en], теорема об опорной гиперплоскости и лемма Фаркаша.

ПримерыПравить

 
Иерархия задач выпуклого программирования.
(LP: линейное программирование,
QP: квадратичное программирование,
SOCP: коническое программирования на конусе второго порядка,
SDP: полуопределённое программирование,
CP: коническое программирование,
GFP: программирование графических форм.)

Следующие классы задач являются задачами выпуклого программирования или могут быть сведены к задачам выпуклого программирования путём простых преобразований[11][14]:

Метод множителей ЛагранжаПравить

Рассмотрим задачу выпуклой минимизации, заданную в стандартной форме с функцией цены   и ограничениям-неравенствам   для  . Тогда область определения   равна:

 

Функция Лагранжа для задачи

 

Для любой точки   из  , которая минимизирует   на  , существуют вещественные числа  , называемые множителями Лагранжа, для которых выполняются одновременно условия:

  1.   минимизирует   над всеми  
  2.   по меньшей мере с одним  
  3.   (дополняющая нежёсткость).

Если существует «сильная допустимая точка», то есть точка  , удовлетворяющая

 

то утверждение выше может быть усилено до требования  .

И обратно, если некоторое   из   удовлетворяет условиям (1)-(3) для скаляров   с  , то   определённо минимизирует   на  .

АлгоритмыПравить

Задачи выпуклого программирования решаются следующими современными методами:[15]

Субградиентные методы могут быть реализованы просто, потому они широко используются[18][19]. Двойственные субградиентные методы — это субградиентные методы, применённые к двойственной задаче. Метод сноса+штрафа[en] аналогичен двойственному субградиентному методу, но использует среднее по времени от основных переменных.

РасширенияПравить

Расширения выпуклого программирования включают оптимизацию двояковыпуклых[en], псевдовыпуклых и квазивыпуклых функций. Расширения теории выпуклого анализа и итеративные методы для приблизительного решения невыпуклых задач оптимизации встречаются в области обобщённой выпуклости, известной как абстрактный выпуклый анализ.

См. такжеПравить

ПримечанияПравить

  1. 1 2 Nesterov, Nemirovskii, 1994.
  2. Murty, Kabadi, 1987, с. 117–129.
  3. Sahni, 1974, с. 262—279.
  4. Pardalos, Vavasis, 1991, с. 15—22.
  5. Boyd, Vandenberghe, 2004, с. 17.
  6. Christensen, Klarbring, 2008, с. chpt. 4.
  7. Boyd, Vandenberghe, 2004.
  8. Boyd, Vandenberghe, 2004, с. 8.
  9. Hiriart-Urruty, Lemaréchal, 1996, с. 291.
  10. Ben-Tal, Nemirovskiĭ, 2001, с. 335–336.
  11. 1 2 3 4 Boyd, Vandenberghe, 2004, с. chpt. 4.
  12. Boyd, Vandenberghe, 2004, с. chpt. 2.
  13. Rockafellar, 1993, с. 183–238.
  14. Agrawal, Verschueren, Diamond, Boyd, 2018, с. 42–60.
  15. О методах выпуклого программирования см. книги Ирриарта-Уррути и Лемерикала (несколько книг) и книги Рушчиньского, Берцекаса, а также Бойда и Вандерберге (методы внутренней точки).
  16. Nesterov, Nemirovskii, 1995.
  17. Peng, Roos, Terlaky, 2002, с. 129–171.
  18. Bertsekas, 2009.
  19. Bertsekas, 2015.

ЛитератураПравить

СсылкиПравить