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

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

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

Определение

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

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

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

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

Двойственность

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

Конический LP

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

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

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

является

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

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

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

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

Semidefinite Program

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

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

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

дается

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

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

$Z\geq 0$

Внешние ссылки

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