Программирование конуса второго порядка - Second-order cone programming

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

А программа конуса второго порядка (SOCP) это выпуклая оптимизация проблема формы

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

при условии

${displaystyle lVert A_ {i} x + b_ {i} Vert _ {2} leq c_ {i} ^ {T} x + d_ {i}, quad i = 1, dots, m}$

${displaystyle Fx = g}$

где параметры задачи ${displaystyle fin mathbb {R} ^ {n}, A_ {i} в mathbb {R} ^ {{n_ {i}} imes n}, b_ {i} в mathbb {R} ^ {n_ {i}}, c_ {i} в mathbb {R} ^ {n}, d_ {i} в mathbb {R}, Fin mathbb {R} ^ {p imes n}}$, и ${displaystyle gin mathbb {R} ^ {p}}$. ${displaystyle xin mathbb {R} ^ {n}}$ - переменная оптимизации.${displaystyle lVert xVert _ {2}}$ это Евклидова норма и ${displaystyle ^ {T}}$ указывает транспонировать.^[1] «Конус второго порядка» в SOCP возникает из-за ограничений, которые эквивалентны требованию аффинной функции ${displaystyle (Ax + b, c ^ {T} x + d)}$ лежать в конусе второго порядка в ${displaystyle mathbb {R} ^ {n_ {i} +1}}$.^[1]

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

Связь с другими проблемами оптимизации

Когда ${displaystyle A_ {i} = 0}$ для ${displaystyle i = 1, dots, m}$, SOCP сводится к линейная программа. Когда ${displaystyle c_ {i} = 0}$ для ${displaystyle i = 1, dots, m}$, SOCP эквивалентен выпуклой линейной программе с квадратичными ограничениями.

Выпуклый квадратичные программы с ограничениями также могут быть сформулированы как SOCP, переформулировав целевую функцию как ограничение.^[4] Полуопределенное программирование включает SOCP, поскольку ограничения SOCP могут быть записаны как линейные матричные неравенства (LMI) и может быть переформулирован как экземпляр полуопределенной программы.^[4] Обратное, однако, неверно: существуют положительные полуопределенные конусы, которые не допускают представления конуса второго порядка.^[3] Фактически, в то время как любая замкнутая выпуклая полуалгебраическое множество в плоскости можно записать как допустимую область SOCP,^[5] известно, что существуют выпуклые полуалгебраические множества, которые не могут быть представлены с помощью SDP, то есть существуют выпуклые полуалгебраические множества, которые не могут быть записаны как допустимая область SDP.^[6]

Примеры

Квадратичное ограничение

Рассмотрим квадратичная связь формы

${displaystyle x ^ {T} A ^ {T} Ax + b ^ {T} x + cleq 0.}$

Это эквивалентно ограничению SOC.

${displaystyle left | {egin {matrix} (1 + b ^ {T} x + c) / 2 Axend {matrix}} ight | _ {2} leq (1-b ^ {T} x-c) / 2.}$

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

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

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

при условии

${displaystyle mathbb {P} (a_ {i} ^ {T} xleq b_ {i}) geq p, quad i = 1, dots, m}$

где параметры ${displaystyle a_ {i}}$ независимые гауссовские случайные векторы со средним ${displaystyle {ar {a}} _ {i}}$ и ковариация ${displaystyle Sigma _ {i}}$ и ${displaystyle pgeq 0,5}$. Эта проблема может быть выражена как SOCP

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

при условии

${displaystyle {ar {a}} _ {i} ^ {T} x + Phi ^ {- 1} (p) lVert Sigma _ {i} ^ {1/2} xVert _ {2} leq b_ {i}, quad i = 1, dots, m}$

где ${displaystyle Phi ^ {- 1} (cdot)}$ это обратное нормальная кумулятивная функция распределения.^[1]

Стохастическое программирование конуса второго порядка

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

Решатели и языки сценариев (программирования)

использованная литература