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

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

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

при условии

$\Vert \; A\; ix\; +\; bi\; \Vert \; 2\; \le \; ci\; T\; x\; +\; di,\; я\; знак\; равно\; 1,\dots ,\; m\; \{\backslash \; displaystyle\; \backslash \; lVert\; A\_\; \{i\}\; x\; +\; b\_\; \{i\}\; \backslash \; rVert\; \_\; \{2\}\; \backslash \; leq\; c\_\; \{i\}\; ^\; \{T\}\; x\; +\; d\_\; \{i\},\; \backslash \; quad\; i\; =\; 1,\; \backslash \; dots,\; m\}$

$F\; x\; =\; g\; \{\backslash \; displaystyle\; Fx\; =\; g\; \backslash \}$

где параметры задачи: $f\; \in \; R\; n,\; A\; i\; \in \; R\; ni\; \times \; n,\; bi\; \in \; R\; ni,\; ci\; \in \; R\; N,\; di\; \in \; R,\; F\; \in \; R\; п\; \times \; N\; \{\backslash \; Displaystyle\; F\; \backslash \; in\; \backslash \; mathbb\; \{R\}\; ^\; \{n\},\; \backslash \; A\_\; \{i\}\; \backslash \; in\; \backslash \; mathbb\; \{R\}\; ^\; \{\{n\_\; \{i\; \}\}\; \backslash \; times\; n\},\; \backslash \; b\_\; \{i\}\; \backslash \; in\; \backslash \; mathbb\; \{R\}\; ^\; \{n\_\; \{i\}\},\; \backslash \; c\_\; \{i\}\; \backslash \; in\; \backslash \; mathbb\; \{R\}\; ^\; \{n\},\; \backslash \; d\_\; \{i\}\; \backslash \; в\; \backslash \; mathbb\; \{R\},\; \backslash \; F\; \backslash \; in\; \backslash \; mathbb\; \{R\}\; ^\; \{p\; \backslash \; times\; n\}\}$и $g\; \in \; R\; p\; \{\backslash \; displaystyle\; g\; \backslash \; in\; \backslash \; mathbb\; \{R\}\; ^\; \{p\}\}$. $x\; \in \; R\; n\; \{\backslash \; displaystyle\; x\; \backslash \; in\; \backslash \; mathbb\; \{R\}\; ^\; \{n\}\}$- переменная оптимизации. $\Vert \; x\; \Vert \; 2\; \{\backslash \; displaystyle\; \backslash \; lVert\; x\; \backslash \; rVert\; \_\; \{2\}\}$- евклидова норма и $T\; \{\backslash \; displaystyle\; ^\; \{T\}\}$означает транспонировать. «Конус второго порядка» в SOCP возникает из-за ограничений, которые эквивалентны требованию аффинной функции $(A\; x\; +\; b,\; c\; T\; x\; +\; d)\; \{\backslash \; displaystyle\; (Ax\; +\; b,\; c\; ^\; \{T\}\; x\; +\; d)\}$лежать в конусе второго порядка в $R\; ni\; +\; 1\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{R\}\; ^\; \{n\_\; \{i\}\; +1\}\}$.

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

• 1 Связь с другими задачами оптимизации
• 2 Примеры
  • 2.1 Квадратичное ограничение
  • 2.2 Стохастическое линейное программирование
  • 2.3 Стохастическое конусное программирование второго порядка
• 3 Решатели и языки программирования (программирования)
• 4 Ссылки

Когда $A\; я\; =\; 0\; \{\backslash \; displaystyle\; A\_\; \{i\}\; =\; 0\}$для $i\; =\; 1,\dots ,\; m\; \{\backslash \; displaystyle\; i\; =\; 1,\; \backslash \; dots,\; m\}$, SOCP сводится к линейной программе. Когда $ci\; =\; 0\; \{\backslash \; displaystyle\; c\_\; \{i\}\; =\; 0\}$для $i\; =\; 1,\dots ,\; m\; \{\backslash \; displaystyle\; i\; =\; 1,\; \backslash \; dots,\; m\}$, SOCP эквивалентен выпуклой линейной программе с квадратичными ограничениями.

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

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

Рассмотрим квадратичное ограничение вида

$x\; TATA\; x\; +\; b\; T\; x\; +\; c\; \le \; 0.\; \{\backslash \; displaystyle\; x\; ^\; \{T\}\; A\; ^\; \{T\}\; Ax\; +\; b\; ^\; \{T\}\; x\; +\; c\; \backslash \; leq\; 0.\}$

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

$\Vert \; (1\; +\; b\; T\; x\; +\; c)\; /\; 2\; A\; x\; \Vert \; 2\; \le \; (1\; -\; b\; T\; x\; -\; c)\; /\; 2.\; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; |\; \{\backslash \; begin\; \{matrix\}\; (1\; +\; b\; ^\; \{T\}\; x\; +\; c)\; /\; 2\; \backslash \backslash \; Ax\; \backslash \; end\; \{matrix\}\}\; \backslash \; right\; \backslash \; |\; \_\; \{2\}\; \backslash \; leq\; (1-b\; ^\; \{T\}\; xc)\; /\; 2.\}$

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

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

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

с учетом

$П\; (ai\; T\; x\; \le \; bi)\; \ge \; p,\; i\; =\; 1,\dots ,\; m\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{P\}\; (a\_\; \{i\}\; ^\; \{T\}\; x\; \backslash \; leq\; b\_\; \{i\})\; \backslash \; geq\; p,\; \backslash \; quad\; я\; =\; 1,\; \backslash \; точки,\; м\}$

где параметры $ai\; \{\backslash \; displaystyle\; a\_\; \{i\}\; \backslash \}$являются независимыми гауссовскими случайными векторами со средним значением $a\; ¯\; i\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{a\}\}\; \_\; \{\; i\}\}$и ковариация $\Sigma \; i\; \{\backslash \; displaystyle\; \backslash \; Sigma\; \_\; \{i\}\; \backslash \}$и $p\; \ge \; 0,5\; \{\backslash \; displaystyle\; p\; \backslash \; geq\; 0,5\}$. Эта проблема может быть выражена как SOCP

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

при условии

$a\; ¯\; i\; T\; x\; +\; \Phi \; -\; 1\; (p)\; \Vert \; \Sigma \; я\; 1/2\; x\; \Vert \; 2\; \le \; bi,\; я\; =\; 1,\dots ,\; m\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{a\}\}\; \_\; \{i\}\; ^\; \{T\}\; x\; +\; \backslash \; Phi\; ^\; \{-\; 1\}\; (p)\; \backslash \; lVert\; \backslash \; Sigma\; \_\; \{i\}\; ^\; \{1/2\}\; x\; \backslash \; rVert\; \_\; \{2\}\; \backslash \; leq\; b\_\; \{i\},\; \backslash \; quad\; i\; =\; 1,\; \backslash \; dots,\; m\}$

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

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

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