Коническая оптимизация

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

Коническая оптимизация — это подраздел выпуклой оптимизации , изучающий задачи, состоящие в минимизации выпуклой функции на пересечении аффинного подпространства и выпуклого конуса .

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

Дано действительное векторное пространство X , выпуклая , действительнозначная функция

${\displaystyle f:C\to \mathbb {R} }$

Определенная на выпуклом конусе и аффинном подпространстве, заданном набором аффинных ограничений , задача конической оптимизации состоит в нахождении точки , для которой число является наименьшим.${\displaystyle C\подмножество X}$${\displaystyle {\mathcal {H}}}$${\displaystyle h_{i}(x)=0\ }$${\displaystyle x}$${\displaystyle C\cap {\mathcal {H}}}$${\displaystyle f(x)}$

Примерами являются положительный ортант , положительные полуопределенные матрицы и конус второго порядка . Часто является линейной функцией, в этом случае задача конической оптимизации сводится к линейной программе , полуопределенной программе и программе конуса второго порядка соответственно.${\displaystyle С}$ ${\displaystyle \mathbb {R} _{+}^{n}=\left\{x\in \mathbb {R} ^{n}:\,x\geq \mathbf {0} \right\}}$${\displaystyle \mathbb {S} _{+}^{n}}$ ${\displaystyle \left\{(x,t)\in \mathbb {R} ^{n}\times \mathbb {R} :\lVert x\rVert \leq t\right\}}$${\displaystyle f\ }$

Некоторые особые случаи задач конической оптимизации имеют заметные замкнутые выражения их двойственных задач.

Двойственная коническая линейная программа

минимизировать${\displaystyle c^{T}x\ }$

при условии${\displaystyle Ax=b,x\in C\ }$

является

максимизировать${\displaystyle b^{T}y\ }$

при условии${\displaystyle A^{T}y+s=c,s\in C^{*}\ }$

где обозначает двойственный конус .${\displaystyle С^{*}}$${\displaystyle C\ }$

В то время как слабая двойственность имеет место в коническом линейном программировании, сильная двойственность не обязательно имеет место. ^[1]

Двойственная к полуопределенной программе программа в форме неравенства

минимизировать${\displaystyle c^{T}x\ }$

при условии${\displaystyle x_{1}F_{1}+\cdots +x_{n}F_{n}+G\leq 0}$

дается

максимизировать${\displaystyle \mathrm {tr} \ (GZ)\ }$

при условии${\displaystyle \mathrm {tr} \ (F_{i}Z)+c_{i}=0,\quad i=1,\dots ,n}$

${\displaystyle Z\geq 0}$

• Бойд, Стивен П.; Ванденберг, Ливен (2004). Выпуклая оптимизация (PDF) . Cambridge University Press. ISBN 978-0-521-83378-3. Получено 15 октября 2011 г. .
• Программное обеспечение MOSEK, способное решать задачи конической оптимизации.