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

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

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

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

Определение

Учитывая настоящий векторное пространство Икс, а выпуклый, с реальной стоимостью функция

${displaystyle f: C o mathbb {R}}$

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

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

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

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

Конический LP

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

свести к минимуму ${displaystyle c ^ {T} x}$

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

является

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

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

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

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

Полуопределенная программа

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

свести к минимуму ${displaystyle c ^ {T} x}$

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

дан кем-то

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

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

${displaystyle Zgeq 0}$

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

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

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