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

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

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

Абстрактная форма [ править ]

Задача выпуклой оптимизации определяется двумя компонентами: ^[5]^[6]

Целевая функция , которая представляет собой вещественнозначную выпуклую функцию от n переменных, $f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R}$ ;
Допустимое множество , которое является выпуклым подмножеством $C\subseteq \mathbb {R} ^{n}$ .

Цель задачи – найти некоторые $\mathbf {x^{\ast }} \in C$ достижение

\inf\{f(\mathbf {x} ):\mathbf {x} \in C\}

.

В целом есть три варианта существования решения: ^[7]^{: глава 4}

Если такая точка x * существует, ее называют оптимальной точкой или решением ; совокупность всех оптимальных точек называется оптимальным множеством ; и проблема называется разрешимой .
Если $f$ неограничен снизу над $C$ , или нижняя грань не достигается, то задача оптимизации называется неограниченной .
В противном случае, если $C$ если множество пусто, то задача называется неразрешимой .

Стандартная форма [ править ]

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

{\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {x} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {x} )\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}

где: ^[7]^{: глава 4}

$\mathbf {x} \in \mathbb {R} ^{n}$ – вектор переменных оптимизации;
Целевая функция $f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R}$ — выпуклая функция ;
Функции ограничения неравенства $g_{i}:\mathbb {R} ^{n}\to \mathbb {R}$ , $i=1,\ldots ,m$ , — выпуклые функции;
Функции ограничения равенства $h_{i}:\mathbb {R} ^{n}\to \mathbb {R}$ , $i=1,\ldots ,p$ , являются аффинными преобразованиями , то есть вида: $h_{i}(\mathbf {x} )=\mathbf {a_{i}} \cdot \mathbf {x} -b_{i}$ , где $\mathbf {a_{i}}$ является вектором и $b_{i}$ является скаляром.

Допустимый набор $C$ задачи оптимизации состоит из всех точек $\mathbf {x} \in {\mathcal {D}}$ удовлетворяющее неравенству и ограничениям равенства. Это множество выпукло, поскольку ${\mathcal {D}}$ выпукло, множества подуровней выпуклых функций выпуклы, аффинные множества выпуклы и пересечение выпуклых множеств выпукло. ^[7]^{: глава 2}

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

Форма эпиграфа (стандартная форма с линейной целью) [ править ]

В стандартной форме можно без ограничения общности считать, что целевая функция f является линейной функцией . Это связано с тем, что любую программу с общей целью можно преобразовать в программу с линейной целью, добавив одну переменную t и одно ограничение следующим образом: ^[9]^: 1.4

{\begin{aligned}&{\underset {\mathbf {x} ,t}{\operatorname {minimize} }}&&t\\&\operatorname {subject\ to} &&f(\mathbf {x} )-t\leq 0\\&&&g_{i}(\mathbf {x} )\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}

Коническая форма [ править ]

Любую выпуклую программу можно представить в конической форме , что означает минимизацию линейной цели на пересечении аффинной плоскости и выпуклого конуса: ^[9]^: 5.1

{\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&c^{T}x\\&\operatorname {subject\ to} &&x\in (b+L)\cap K\end{aligned}}

где K — замкнутый заостренный выпуклый конус , L — линейное подпространство R ^н, а b — вектор из R ^н. Линейная программа в стандартной форме в частном случае, когда K является неотрицательным ортантом R. ^н.

Устранение ограничений линейного равенства [ править ]

Можно преобразовать выпуклую программу в стандартной форме в выпуклую программу без ограничений равенства. ^[7]^: 132Обозначим ограничения равенства h _i ( x )=0 как Ax = b , где A имеет n столбцов. Если Ax = b неразрешима, то, конечно, исходная задача неразрешима. В противном случае оно имеет некоторое решение x ₀ , и множество всех решений можно представить в виде: Fz + x ₀ , где z находится в R. ^к, k = n -rank( A ), и F является n -k матрицей размера . Подстановка x = Fz + x ₀ в исходную задачу дает:

${\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {F\mathbf {z} +\mathbf {x} _{0}} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {F\mathbf {z} +\mathbf {x} _{0}} )\leq 0,\quad i=1,\dots ,m\\\end{aligned}}$

где переменные — z . Обратите внимание, что переменных ранга ( A ) меньше. Это означает, что в принципе можно ограничить внимание задачами выпуклой оптимизации без ограничений равенства. Однако на практике часто предпочитают сохранять ограничения равенства, поскольку они могут сделать некоторые алгоритмы более эффективными, а также облегчить понимание и анализ проблемы.

Особые случаи [ править ]

Все следующие классы задач представляют собой задачи выпуклой оптимизации или могут быть сведены к задачам выпуклой оптимизации с помощью простых преобразований: ^[7]^{: глава 4}^[10]

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

Другие особые случаи включают в себя;

Наименьших квадратов
Квадратичная минимизация с выпуклыми квадратичными ограничениями
Геометрическое программирование
Максимизация энтропии с соответствующими ограничениями.

Свойства [ править ]

Ниже приведены полезные свойства задач выпуклой оптимизации: ^[11]^[7]^{: глава 4}

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

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

Алгоритмы [ править ]

ограничениями равенства и с Проблемы без ограничений

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

В классе задач без ограничений (или задач с ограничениями равенства) самыми простыми являются те, в которых цель является квадратичной . Для этих задач все условия ККТ (которые необходимы для оптимальности) линейны, поэтому их можно решать аналитически. ^[7]^{: глава 11}

Для задач без ограничений (или с ограничениями равенства) с общей выпуклой целью, которая дважды дифференцируема, метод Ньютона можно использовать . Ее можно рассматривать как сведение общей выпуклой задачи без ограничений к последовательности квадратичных задач. ^[7]^{: глава 11}Метод Ньютона можно комбинировать с поиском линии для соответствующего размера шага, и можно математически доказать, что он быстро сходится.

Другими эффективными алгоритмами неограниченной минимизации являются градиентный спуск (частный случай наискорейшего спуска ).

Общие проблемы [ править ]

Более сложные проблемы связаны с ограничениями неравенства. Распространенный способ их решения — свести их к задачам без ограничений, добавив к целевой функции барьерную функцию , обеспечивающую ограничения неравенства. Такие методы называются методами внутренней точки . ^[7]^{: глава 11}Их необходимо инициализировать путем нахождения допустимой внутренней точки с использованием так называемых методов фазы I , которые либо находят допустимую точку, либо показывают, что ее не существует. Методы фазы I обычно заключаются в сведении рассматриваемого поиска к более простой задаче выпуклой оптимизации. ^[7]^{: глава 11}

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

Пакетные методы (Вульфа, Лемарешаля, Кивила) и
Методы субградиентного проектирования (Поляк),
Методы внутренней точки , ^[1] которые используют самосогласованные барьерные функции ^[13] и саморегулярные барьерные функции. ^[14]
Методы секущей плоскости
Эллипсоидный метод
Субградиентный метод
Двойные субградиенты и метод «дрейф плюс штраф».

Субградиентные методы легко реализуются и поэтому широко используются. ^[15]Двойные субградиентные методы — это субградиентные методы, применяемые к двойственной задаче . Метод дрейфа плюс штрафа аналогичен методу двойного субградиента, но он требует усреднения по времени основных переменных. ^{[ нужна цитата ]}

Множители Лагранжа [ править ]

Рассмотрим задачу выпуклой минимизации, заданную в стандартной форме функцией стоимости $f(x)$ и ограничения неравенства $g_{i}(x)\leq 0$ для $1\leq i\leq m$ . Тогда домен ${\mathcal {X}}$ является:

{\mathcal {X}}=\left\{x\in X\vert g_{1}(x),\ldots ,g_{m}(x)\leq 0\right\}.

Функция Лагранжа для этой задачи:

L(x,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})=\lambda _{0}f(x)+\lambda _{1}g_{1}(x)+\cdots +\lambda _{m}g_{m}(x).

Для каждой точки $x$ в $X$ что сводит к минимуму $f$ над $X$ , существуют действительные числа $\lambda _{0},\lambda _{1},\ldots ,\lambda _{m},$ называемые множителями Лагранжа , которые одновременно удовлетворяют этим условиям:

$x$ сводит к минимуму $L(y,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})$ общий $y\in X,$
$\lambda _{0},\lambda _{1},\ldots ,\lambda _{m}\geq 0,$ хотя бы с одним $\lambda _{k}>0,$
$\lambda _{1}g_{1}(x)=\cdots =\lambda _{m}g_{m}(x)=0$ (дополнительная расслабленность).

Если существует «строго допустимая точка», т. е. точка $z$ удовлетворяющий

g_{1}(z),\ldots ,g_{m}(z)<0,

то приведенное выше утверждение можно усилить, потребовав, чтобы $\lambda _{0}=1$ .

И наоборот, если некоторые $x$ в $X$ удовлетворяет (1)–(3) для скаляров $\lambda _{0},\ldots ,\lambda _{m}$ с $\lambda _{0}=1$ затем $x$ обязательно сведет к минимуму $f$ над $X$ .

Программное обеспечение [ править ]

Существует большая программная экосистема для выпуклой оптимизации. В этой экосистеме есть две основные категории: решатели с одной стороны и инструменты моделирования (или интерфейсы ) с другой.

Решатели сами реализуют алгоритмы и обычно пишутся на C. Они требуют от пользователей задавать задачи оптимизации в очень специфических форматах, которые могут быть неестественными с точки зрения моделирования. Инструменты моделирования — это отдельные части программного обеспечения, которые позволяют пользователю задавать оптимизацию в синтаксисе более высокого уровня. Они управляют всеми преобразованиями в и из пользовательской модели высокого уровня и формата ввода/вывода решателя.

В таблице ниже показано сочетание инструментов моделирования (таких как CVXPY и Convex.jl) и решателей (таких как CVXOPT и MOSEK). Эта таблица ни в коем случае не является исчерпывающей.


Программа	Язык	Описание	ФОСС ?	Ссылка
CVX	МАТЛАБ	Интерфейсы с решателями SeDuMi и SDPT3; предназначен только для выражения задач выпуклой оптимизации.	Да	^[16]
CVXMOD	Питон	Интерфейсы с решателем CVXOPT .	Да	^[16]
CVXPY	Питон			^[17]
Convex.jl	Юлия	Дисциплинированное выпуклое программирование, поддерживает множество решателей.	Да	^[18]
CVXR	р		Да	^[19]
ЯЛМИП	МАТЛАБ, Октава	Интерфейсы с решателями CPLEX, GUROBI, MOSEK, SDPT3, SEDUMI, CSDP, SDPA, PENNON; также поддерживает целочисленную и нелинейную оптимизацию, а также некоторую невыпуклую оптимизацию. Может выполнять надежную оптимизацию с неопределенностью в ограничениях LP/SOCP/SDP.	Да	^[16]
лаборатория ЛМИ	МАТЛАБ	Выражает и решает задачи полуопределенного программирования (называемые «линейными матричными неравенствами»).	Нет	^[16]
Переводчик LMIlab		Преобразует лабораторные проблемы LMI в проблемы SDP.	Да	^[16]
ксЛМИ	МАТЛАБ	Похож на лабораторию LMI, но использует решатель SeDuMi.	Да	^[16]
АИММС		Может выполнять надежную оптимизацию линейного программирования (с помощью MOSEK для решения конусного программирования второго порядка) и смешанного целочисленного линейного программирования . Пакет моделирования для LP+SDP и робастных версий.	Нет	^[16]
РИМ		Система моделирования для надежной оптимизации. Поддерживает устойчивую к распределению оптимизацию и наборы неопределенностей .	Да	^[16]
ГлоптиПоли 3	МАТЛАБ, Октава	Система моделирования для полиномиальной оптимизации.	Да	^[16]
СОСТУЛС		Система моделирования для полиномиальной оптимизации . Использует SDPT3 и SeDuMi. Требуется набор инструментов для символьных вычислений.	Да	^[16]
РазреженныйPOP		Система моделирования для полиномиальной оптимизации. Использует решатели SDPA или SeDuMi.	Да	^[16]
Комплексный комплекс		Поддерживает методы primal-dual для LP + SOCP. Может решать задачи LP, QP, SOCP и смешанного целочисленного линейного программирования.	Нет	^[16]
CSDP	С	Поддерживает методы primal-dual для LP + SDP. Доступны интерфейсы для MATLAB, R и Python. Доступна параллельная версия. Решатель SDP.	Да	^[16]
CVXOPT	Питон	Поддерживает методы primal-dual для LP + SOCP + SDP. Использует масштабирование Нестерова-Тодда. Интерфейсы к МОСЭК и DSDP.	Да	^[16]
МОИСЕЙ		Поддерживает методы primal-dual для LP + SOCP.	Нет	^[16]
СеДуМи	MATLAB, Октава, MEX	Решает LP+SOCP+SDP. Поддерживает методы primal-dual для LP + SOCP + SDP.	Да	^[16]
СДПА	С++	Решает ЛП+СДП. Поддерживает методы primal-dual для LP + SDP. Доступны версии с параллельной и повышенной точностью.	Да	^[16]
СДПТ3	MATLAB, Октава, MEX	Решает LP+SOCP+SDP. Поддерживает методы primal-dual для LP + SOCP + SDP.	Да	^[16]
ConicBundle		Поддерживает коды общего назначения LP + SOCP + SDP. Использует метод пакета. Специальная поддержка ограничений SDP и SOCP.	Да	^[16]
ДСДП		Поддерживает коды общего назначения для LP + SDP. Использует метод двойной внутренней точки.	Да	^[16]
ЛОГОТИП		Поддерживает коды общего назначения для SOCP, которые рассматриваются как задача нелинейного программирования.	Нет	^[16]
ПЕННОН		Поддерживает коды общего назначения. Использует расширенный метод Лагранжа, особенно для проблем с ограничениями SDP.	Нет	^[16]
СДПЛР		Поддерживает коды общего назначения. Использует факторизацию низкого ранга с расширенным методом Лагранжа.	Да	^[16]
ГАМС		Система моделирования для задач линейного, нелинейного, смешанного целочисленного линейного/нелинейного и конического программирования второго порядка.	Нет	^[16]
Услуги по оптимизации		Стандарт XML для кодирования проблем оптимизации и их решения.		^[16]

Приложения [ править ]

Выпуклая оптимизация может использоваться для моделирования проблем в широком спектре дисциплин, таких как системы автоматического управления , оценка и обработка сигналов , связь и сети, проектирование электронных схем и т . д. ^[7]^: 17 анализ данных и моделирование, финансы , статистика ( оптимальный план эксперимента ), ^[20] и структурная оптимизация , где концепция аппроксимации доказала свою эффективность. ^[7]^[21] Выпуклая оптимизация может использоваться для моделирования проблем в следующих областях:

Оптимизация портфеля . ^[22]
Анализ рисков наихудшего случая. ^[22]
Оптимальная реклама. ^[22]
Варианты статистической регрессии (включая регуляризацию и квантильную регрессию ). ^[22]
Примерка модели ^[22] (особенно многоклассовая классификация ^[23]).
Оптимизация производства электроэнергии . ^[23]
Комбинаторная оптимизация . ^[23]
Невероятностное моделирование неопределенности . ^[24]
Локализация с использованием беспроводных сигналов ^[25]

Расширения [ править ]

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

См. также [ править ]

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

^ Перейти обратно: ^а ^б Nesterov & Nemirovskii 1994
^ Мурти, Катта; Кабади, Сантош (1987). «Некоторые NP-полные задачи квадратичного и нелинейного программирования». Математическое программирование . 39 (2): 117–129. дои : 10.1007/BF02592948 . hdl : 2027.42/6740 . S2CID 30500771 .
^ Сахни, С. «Проблемы, связанные с вычислениями», в SIAM Journal on Computing, 3, 262–279, 1974.
^ Квадратичное программирование с одним отрицательным собственным значением является NP-трудным , Панос М. Пардалос и Стивен А. Вавасис в Журнале глобальной оптимизации , том 1, номер 1, 1991, стр. 15-22.
^ Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1996). Алгоритмы выпуклого анализа и минимизации: Основы . п. 291. ИСБН 9783540568506 .
^ Бен-Тал, Аарон; Немировский, Аркадий Семенович (2001). Лекции по современной выпуклой оптимизации: анализ, алгоритмы и инженерные приложения . стр. 335–336. ISBN 9780898714913 .
^ Перейти обратно: ^а ^б ^с ^д ^Это ^ж ^г ^час ^я ^дж ^к ^л Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация (PDF) . Издательство Кембриджского университета . ISBN 978-0-521-83378-3 . Проверено 12 апреля 2021 г.
^ «Типы задач оптимизации — выпуклая оптимизация» . 9 января 2011 г.
^ Перейти обратно: ^а ^б Аркадий Немировский (2004). Полиномиальные методы внутренней точки в выпуклом программировании .
^ Агравал, Акшай; Вершуерен, Робин; Даймонд, Стивен; Бойд, Стивен (2018). «Система перезаписи для задач выпуклой оптимизации» (PDF) . Контроль и решение . 5 (1): 42–60. arXiv : 1709.04494 . дои : 10.1080/23307706.2017.1397554 . S2CID 67856259 .
^ Рокафеллар, Р. Тиррелл (1993). «Множители Лагранжа и оптимальность» (PDF) . Обзор СИАМ . 35 (2): 183–238. CiteSeerX 10.1.1.161.7209 . дои : 10.1137/1035044 .
^ О методах выпуклой минимизации см. тома Хириарта-Уррути и Лемарешаля (связка) и учебники Рущинского , Берцекаса и Бойд и Ванденберге (внутренняя точка).
^ Нестеров Юрий; Аркадий, Немировский (1995). Полиномиальные алгоритмы внутренней точки в выпуклом программировании . Общество промышленной и прикладной математики. ISBN 978-0898715156 .
^ Пэн, Цзимин; Роос, Корнелис; Терлаки, Тамаш (2002). «Саморегулярные функции и новые направления поиска линейной и полуопределенной оптимизации». Математическое программирование . 93 (1): 129–171. дои : 10.1007/s101070200296 . ISSN 0025-5610 . S2CID 28882966 .
^ «Численная оптимизация» . Серия Springer по исследованию операций и финансовой инженерии . 2006. doi : 10.1007/978-0-387-40065-5 .
^ Перейти обратно: ^а ^б ^с ^д ^Это ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^О ^п ^д ^р ^с ^т ^в ^v ^В ^Икс ^и Борчерс, Брайан. «Обзор программного обеспечения для выпуклой оптимизации» (PDF) . Архивировано из оригинала (PDF) 18 сентября 2017 г. Проверено 12 апреля 2021 г.
^ «Добро пожаловать в документацию CVXPY 1.1 — CVXPY 1.1.11» . www.cvxpy.org . Проверено 12 апреля 2021 г.
^ Уделл, Мадлен; Мохан, Каранвир; Цзэн, Дэвид; Хонг, Дженни; Даймонд, Стивен; Бойд, Стивен (17 октября 2014 г.). «Выпуклая оптимизация в Джулии». arXiv : 1410.4821 [ math.OC ].
^ «Дисциплинированная выпуклая оптимизация — CVXR» . www.cvxgrp.org . Проверено 17 июня 2021 г.
^ Критенсен/Кларбринг, гл. 4.
^ Шмит, Луизиана; Флери, К. 1980: Структурный синтез путем объединения концепций аппроксимации и двойственных методов . Дж. Амер. Инст. Аэронавт. Астронавт 18 лет, 1252–1260 гг.
^ Перейти обратно: ^а ^б ^с ^д ^Это Бойд, Стивен; Даймонд, Стивен; Чжан, Цзюньцзы; Агравал, Акшай. «Приложения выпуклой оптимизации» (PDF) . Архивировано (PDF) из оригинала 1 октября 2015 г. Проверено 12 апреля 2021 г.
^ Перейти обратно: ^а ^б ^с Малик, Жером (28 сентября 2011 г.). «Выпуклая оптимизация: приложения, формулировки, расслабления» (PDF) . Архивировано (PDF) из оригинала 12 апреля 2021 г. Проверено 12 апреля 2021 г.
^ Бен Хаим Ю. и Элишакофф И., Выпуклые модели неопределенности в прикладной механике, Elsevier Science Publishers, Амстердам, 1990.
^ Ахмад Баззи , Дирк Т.М. Слок и Лиза Мейлхак. «Онлайн-оценка угла прихода при наличии взаимной связи». Семинар IEEE по статистической обработке сигналов (SSP), 2016 г. ИИЭР, 2016.

Ссылки [ править ]

Берцекас, Дмитрий П.; Недич, Ангелия; Оздаглар, Асуман (2003). Выпуклый анализ и оптимизация . Бельмонт, Массачусетс: Athena Scientific. ISBN 978-1-886529-45-8 .
Берцекас, Дмитрий П. (2009). Теория выпуклой оптимизации . Бельмонт, Массачусетс: Athena Scientific. ISBN 978-1-886529-31-1 .
Берцекас, Дмитрий П. (2015). Алгоритмы выпуклой оптимизации . Бельмонт, Массачусетс: Athena Scientific. ISBN 978-1-886529-28-1 .
Борвейн, Джонатан; Льюис, Адриан (2000). Выпуклый анализ и нелинейная оптимизация: теория и примеры, второе издание (PDF) . Спрингер . Проверено 12 апреля 2021 г.
Кристенсен, Питер В.; Андерс Кларбринг (2008). Введение в структурную оптимизацию . Том. 153. Springer Science & Business Media. ISBN 9781402086663 .

Хириар-Уррути, Жан-Батист, и Лемарешаль, Клод . (2004). Основы выпуклого анализа . Берлин: Шпрингер.
Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). Алгоритмы выпуклого анализа и минимизации, Том I: Основы . Фундаментальные основы математических наук. Том 305. Берлин: Springer-Verlag. стр. xviii+417. ISBN 978-3-540-56850-6 . МР 1261420 .
Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). Алгоритмы выпуклого анализа и минимизации, Том II: Расширенная теория и методы расслоения . Фундаментальные основы математических наук. Том 306. Берлин: Springer-Verlag. стр. xviii+346. ISBN 978-3-540-56852-0 . МР 1295240 .
Кивиэль, Кшиштоф К. (1985). Методы спуска для недифференцируемой оптимизации . Конспект лекций по математике. Нью-Йорк: Springer-Verlag. ISBN 978-3-540-15642-0 .
Лемарешаль, Клод (2001). «Лагранжева релаксация». В Михаэле Юнгере и Денисе Наддефе (ред.). Вычислительная комбинаторная оптимизация: доклады весенней школы, проходившей в замке Дагштуль, 15–19 мая 2000 г. Конспекты лекций по информатике. Том. 2241. Берлин: Springer-Verlag. стр. 112–156. дои : 10.1007/3-540-45586-8_4 . ISBN 978-3-540-42877-0 . МР 1900016 . S2CID 9048698 .
Nesterov, Yurii; Nemirovskii, Arkadii (1994). Interior Point Polynomial Methods in Convex Programming . SIAM.
Нестеров Юрий. (2004). Вводные лекции по выпуклой оптимизации , Kluwer Academic Publishers
Рокафеллар, RT (1970). Выпуклый анализ . Принстон: Издательство Принстонского университета.

Рущинский, Анджей (2006). Нелинейная оптимизация . Издательство Принстонского университета.
Шмит, Луизиана; Флери, К. 1980: Структурный синтез путем объединения концепций аппроксимации и двойственных методов . Дж. Амер. Инст. Аэронавт. Астронавт 18 лет, 1252–1260 гг.

Внешние ссылки [ править ]

EE364a: Выпуклая оптимизация I и EE364b: Выпуклая оптимизация II , домашние страницы Стэнфордского курса
6.253: Выпуклый анализ и оптимизация , домашняя страница курса MIT OCW
Брайан Борчерс, Обзор программного обеспечения для выпуклой оптимизации
Книга «Выпуклая оптимизация» Ливена Ванденберге и Стивена П. Бойда

[Nesterov_1994-1] Перейти обратно: ^а ^б Nesterov & Nemirovskii 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-трудным , Панос М. Пардалос и Стивен А. Вавасис в Журнале глобальной оптимизации , том 1, номер 1, 1991, стр. 15-22.

[5] Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1996). Алгоритмы выпуклого анализа и минимизации: Основы . п. 291. ИСБН 9783540568506 .

[6] Бен-Тал, Аарон; Немировский, Аркадий Семенович (2001). Лекции по современной выпуклой оптимизации: анализ, алгоритмы и инженерные приложения . стр. 335–336. ISBN 9780898714913 .

[:2-7] Перейти обратно: ^а ^б ^с ^д ^Это ^ж ^г ^час ^я ^дж ^к ^л Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация (PDF) . Издательство Кембриджского университета . ISBN 978-0-521-83378-3 . Проверено 12 апреля 2021 г.

[8] «Типы задач оптимизации — выпуклая оптимизация» . 9 января 2011 г.

[:02-9] Перейти обратно: ^а ^б Аркадий Немировский (2004). Полиномиальные методы внутренней точки в выпуклом программировании .

[rewriting-10] Агравал, Акшай; Вершуерен, Робин; Даймонд, Стивен; Бойд, Стивен (2018). «Система перезаписи для задач выпуклой оптимизации» (PDF) . Контроль и решение . 5 (1): 42–60. arXiv : 1709.04494 . дои : 10.1080/23307706.2017.1397554 . S2CID 67856259 .

[rockafellar93-11] Рокафеллар, Р. Тиррелл (1993). «Множители Лагранжа и оптимальность» (PDF) . Обзор СИАМ . 35 (2): 183–238. CiteSeerX 10.1.1.161.7209 . дои : 10.1137/1035044 .

[12] О методах выпуклой минимизации см. тома Хириарта-Уррути и Лемарешаля (связка) и учебники Рущинского , Берцекаса и Бойд и Ванденберге (внутренняя точка).

[13] Нестеров Юрий; Аркадий, Немировский (1995). Полиномиальные алгоритмы внутренней точки в выпуклом программировании . Общество промышленной и прикладной математики. ISBN 978-0898715156 .

[PengRoos2002-14] Пэн, Цзимин; Роос, Корнелис; Терлаки, Тамаш (2002). «Саморегулярные функции и новые направления поиска линейной и полуопределенной оптимизации». Математическое программирование . 93 (1): 129–171. дои : 10.1007/s101070200296 . ISSN 0025-5610 . S2CID 28882966 .

[15] «Численная оптимизация» . Серия Springer по исследованию операций и финансовой инженерии . 2006. doi : 10.1007/978-0-387-40065-5 .

[:3-16] Перейти обратно: ^а ^б ^с ^д ^Это ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^О ^п ^д ^р ^с ^т ^в ^v ^В ^Икс ^и Борчерс, Брайан. «Обзор программного обеспечения для выпуклой оптимизации» (PDF) . Архивировано из оригинала (PDF) 18 сентября 2017 г. Проверено 12 апреля 2021 г.

[17] «Добро пожаловать в документацию CVXPY 1.1 — CVXPY 1.1.11» . www.cvxpy.org . Проверено 12 апреля 2021 г.

[18] Уделл, Мадлен; Мохан, Каранвир; Цзэн, Дэвид; Хонг, Дженни; Даймонд, Стивен; Бойд, Стивен (17 октября 2014 г.). «Выпуклая оптимизация в Джулии». arXiv : 1410.4821 [ math.OC ].

[19] «Дисциплинированная выпуклая оптимизация — CVXR» . www.cvxgrp.org . Проверено 17 июня 2021 г.

[20] Критенсен/Кларбринг, гл. 4.

[21] Шмит, Луизиана; Флери, К. 1980: Структурный синтез путем объединения концепций аппроксимации и двойственных методов . Дж. Амер. Инст. Аэронавт. Астронавт 18 лет, 1252–1260 гг.

[:0-22] Перейти обратно: ^а ^б ^с ^д ^Это Бойд, Стивен; Даймонд, Стивен; Чжан, Цзюньцзы; Агравал, Акшай. «Приложения выпуклой оптимизации» (PDF) . Архивировано (PDF) из оригинала 1 октября 2015 г. Проверено 12 апреля 2021 г.

[:1-23] Перейти обратно: ^а ^б ^с Малик, Жером (28 сентября 2011 г.). «Выпуклая оптимизация: приложения, формулировки, расслабления» (PDF) . Архивировано (PDF) из оригинала 12 апреля 2021 г. Проверено 12 апреля 2021 г.

[24] Бен Хаим Ю. и Элишакофф И., Выпуклые модели неопределенности в прикладной механике, Elsevier Science Publishers, Амстердам, 1990.

[25] Ахмад Баззи , Дирк Т.М. Слок и Лиза Мейлхак. «Онлайн-оценка угла прихода при наличии взаимной связи». Семинар IEEE по статистической обработке сигналов (SSP), 2016 г. ИИЭР, 2016.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

v т Это Выпуклый анализ и вариационный анализ
Basic concepts	Convex combination Convex function Convex set
Topics (list)	Choquet theory Convex geometry Convex metric space Convex optimization Duality Lagrange multiplier Legendre transformation Locally convex topological vector space Simplex
Maps	Convex conjugate Concave (Closed K- Logarithmically Proper Pseudo- Quasi-) Convex function Invex function Legendre transformation Semi-continuity Subderivative
Main results (list)	Carathéodory's theorem Ekeland's variational principle Fenchel–Moreau theorem Fenchel-Young inequality Jensen's inequality Hermite–Hadamard inequality Krein–Milman theorem Mazur's lemma Shapley–Folkman lemma Robinson–Ursescu Simons Ursescu
Sets	Convex hull (Orthogonally, Pseudo-) Convex set Effective domain Epigraph Hypograph John ellipsoid Lens Radial set/Algebraic interior Zonotope
Series	Convex series related ((cs, lcs)-closed, (cs, bcs)-complete, (lower) ideally convex, (Hx), and (Hwx))
Duality	Dual system Duality gap Strong duality Weak duality
Applications and related	Convexity in economics