WikiDer > Выпуклая оптимизация

Convex optimization

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

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

Определение

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

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

,

где целевая функция выпукло, как и допустимое множество .[10][11] Если такая точка существует, она называется оптимальная точка или же решение; множество всех оптимальных точек называется оптимальный набор. Если неограничен снизу над или нижняя грань не достигается, то задача оптимизации называется неограниченный. В противном случае, если - пустое множество, то проблема называется невыполнимый.[12]

Стандартная форма

Задача выпуклой оптимизации заключается в стандартная форма если это написано как

куда - переменная оптимизации, функция выпуклый, , , выпуклые, и , , находятся аффинный.[12] Это обозначение описывает проблему нахождения что сводит к минимуму среди всего удовлетворение , и , . Функция - целевая функция задачи, а функции и - функции ограничения.

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

Решением задачи выпуклой оптимизации является любая точка достижение . В общем, задача выпуклой оптимизации может иметь ноль, одно или несколько решений.

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

Характеристики

Ниже приведены полезные свойства задач выпуклой оптимизации:[14][12]

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

Анализ неопределенности

Бен-Хайн и Елисаков[15] (1990), Елисаков и другие.[16] (1994) применили выпуклый анализ к неопределенность модели.

Примеры

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

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

Множители Лагранжа

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

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

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

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

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

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

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

Алгоритмы

Задачи выпуклой оптимизации могут быть решены следующими современными методами:[18]

Субградиентные методы могут быть легко реализованы и поэтому широко используются.[21] Двойные субградиентные методы - это субградиентные методы, применяемые к двойная проблема. В дрейф плюс штраф Метод аналогичен двойному субградиентному методу, но требует усреднения по времени основных переменных.

Расширения

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

Смотрите также

Примечания

  1. ^ а б Нестеров и Немировский 1994
  2. ^ Мурти, Катта; Кабади, Сантош (1987). «Некоторые NP-полные задачи квадратичного и нелинейного программирования». Математическое программирование. 39 (2): 117–129. Дои:10.1007 / BF02592948. HDL:2027.42/6740. S2CID 30500771.
  3. ^ Сахни, С. «Проблемы, связанные с вычислениями», в SIAM Journal on Computing, 3, 262-279, 1974.
  4. ^ Квадратичное программирование с одним отрицательным собственным значением NP-сложно, Панос М. Пардалос и Стивен А. Вавасис в Журнал глобальной оптимизации, Volume 1, Number 1, 1991, pg.15-22.
  5. ^ Бойд и Ванденберге 2004, п. 17
  6. ^ Chritensen / Klarbring, гл. 4.
  7. ^ Бойд и Ванденберге 2004
  8. ^ Schmit, L.A .; Флери, C. 1980: Структурный синтез путем объединения приближенных концепций и двойственных методов. J. Amer. Inst. Аэронавт. Астронавт 18, 1252-1260 гг.
  9. ^ Бойд и Ванденберге 2004, п. 8
  10. ^ Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1996). Алгоритмы выпуклого анализа и минимизации: основы. п. 291. ISBN 9783540568506.
  11. ^ Бен-Тал, Аарон; Немировский, Аркадий Семенович (2001). Лекции по современной выпуклой оптимизации: анализ, алгоритмы и инженерные приложения. С. 335–336. ISBN 9780898714913.
  12. ^ а б c d Бойд и Ванденберге 2004, гл. 4
  13. ^ Бойд и Ванденберге 2004, гл. 2
  14. ^ Рокафеллар, Р. Тиррелл (1993). «Множители Лагранжа и оптимальность» (PDF). SIAM Обзор. 35 (2): 183–238. CiteSeerX 10.1.1.161.7209. Дои:10.1137/1035044.
  15. ^ Бен Хаим Й. и Элишакофф И., Выпуклые модели неопределенности в прикладной механике, издательство Elsevier Science Publishers, Амстердам, 1990 г.
  16. ^ И. Елисаков, И. Линь Ю.К. и Чжу Л.П., Вероятностное и выпуклое моделирование структур с акустическим возбуждением, издательство Elsevier Science Publishers, Амстердам, 1994 г.
  17. ^ Агравал, Акшай; Verschueren, Робин; Даймонд, Стивен; Бойд, Стивен (2018). «Система переписывания для задач выпуклой оптимизации» (PDF). Контроль и решение. 5 (1): 42–60. arXiv:1709.04494. Дои:10.1080/23307706.2017.1397554. S2CID 67856259.
  18. ^ О методах выпуклой минимизации см. Тома Хириарта-Уррути и Лемарешала (комплект) и учебники Рущинский, Бертсекас, и Бойд и Ванденберге (внутренняя точка).
  19. ^ Нестеров, Юрий; Аркадий, Немировский (1995). Полиномиальные алгоритмы внутренней точки в выпуклом программировании. Общество промышленной и прикладной математики. ISBN 978-0898715156.
  20. ^ Пэн, Джиминг; Роос, Корнелис; Терлаки, Тамаш (2002). «Саморегулируемые функции и новые направления поиска для линейной и полуопределенной оптимизации». Математическое программирование. 93 (1): 129–171. Дои:10.1007 / с101070200296. ISSN 0025-5610. S2CID 28882966.
  21. ^ Бертсекас

Рекомендации

  • Рущинский, Анджей (2006). Нелинейная оптимизация. Издательство Принстонского университета.
  • Schmit, L.A .; Флери, C. 1980: Структурный синтез путем объединения концепций аппроксимации и двойственных методов. J. Amer. Inst. Аэронавт. Астронавт 18, 1252–1260 гг.

внешняя ссылка