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

Программа конуса второго порядка ( SOCP ) — это задача выпуклой оптимизации вида

минимизировать

\ f^{T}x\

при условии

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

Fx=g\

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

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

Конус второго порядка

Стандартный или единичный второго порядка. конус размерности $n+1$ определяется как

${\mathcal {C}}_{n+1}=\left\{{\begin{bmatrix}x\\t\end{bmatrix}}{\Bigg |}x\in \mathbb {R} ^{n},t\in \mathbb {R} ,\|x\|_{2}\leq t\right\}$ .

Конус второго порядка также известен как квадратичный конус , конус мороженого или конус Лоренца . Стандартный конус второго порядка $\mathbb {R} ^{3}$ является $\left\{(x,y,z){\Big |}{\sqrt {x^{2}+y^{2}}}\leq z\right\}$ .

Набор точек, удовлетворяющих ограничению конуса второго порядка, является обратным образом единичного конуса второго порядка при аффинном отображении:

$\lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i}\Leftrightarrow {\begin{bmatrix}A_{i}\\c_{i}^{T}\end{bmatrix}}x+{\begin{bmatrix}b_{i}\\d_{i}\end{bmatrix}}\in {\mathcal {C}}_{n_{i}+1}$

и, следовательно, является выпуклым.

Конус второго порядка можно вложить в конус положительно-полуопределенных матриц, так как

$||x||\leq t\Leftrightarrow {\begin{bmatrix}tI&x\\x^{T}&t\end{bmatrix}}\succcurlyeq 0,$

т. е. ограничение на конус второго порядка эквивалентно линейному матричному неравенству (здесь $M\succcurlyeq 0$ означает $M$ полуопределенная матрица). Точно так же у нас также есть,

$\lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i}\Leftrightarrow {\begin{bmatrix}(c_{i}^{T}x+d_{i})I&A_{i}x+b_{i}\\(A_{i}x+b_{i})^{T}&c_{i}^{T}x+d_{i}\end{bmatrix}}\succcurlyeq 0$ .

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

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

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

Примеры

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

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

x^{T}Ax+b^{T}x+c\leq 0.

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

\lVert A^{1/2}x+{\frac {1}{2}}A^{-1/2}b\rVert \leq \left({\frac {1}{4}}b^{T}A^{-1}b-c\right)^{\frac {1}{2}}

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

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

минимизировать

\ c^{T}x\

при условии

\mathbb {P} (a_{i}^{T}x\leq b_{i})\geq p,\quad i=1,\dots ,m

где параметры $a_{i}\$ являются независимыми гауссовскими случайными векторами со средним значением ${\bar {a}}_{i}$ и ковариация $\Sigma _{i}\$ и $p\geq 0.5$ . Эту проблему можно выразить как SOCP

минимизировать

\ c^{T}x\

при условии

{\bar {a}}_{i}^{T}x+\Phi ^{-1}(p)\lVert \Sigma _{i}^{1/2}x\rVert _{2}\leq b_{i},\quad i=1,\dots ,m

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

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

Мы имеем в виду конусные программы второго порядка. как детерминированные конусные программы второго порядка, поскольку данные, определяющие их, являются детерминированными. Стохастические программы с конусом второго порядка — это класс задач оптимизации, которые предназначены для обработки неопределенности в данных, определяющих детерминированные программы с конусом второго порядка. ^{[ 10 ]}

Другие примеры

Другие примеры моделирования доступны в книге рецептов моделирования MOSEK. ^{[ 11 ]}

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

Имя	Лицензия	Информация о письме
AMPL	коммерческий	Язык алгебраического моделирования с поддержкой SOCP.
Артелис Книтро	коммерческий
Кларабель	открытый исходный код	Собственный решатель Julia и Rust SOCP. Может решать выпуклые задачи с произвольными типами точности.
Комплексный комплекс	коммерческий
CVXPY	открытый исходный код	Язык моделирования Python с поддержкой SOCP. Поддерживает открытые и коммерческие решатели.
CVXOPT	открытый исходный код	Выпуклый решатель с поддержкой SOCP
ЭХО	открытый исходный код	Решатель SOCP, оптимизированный для встроенных приложений
ФИКО Экспресс	коммерческий
Оптимизатор Гуроби	коммерческий
МАТЛАБ	коммерческий	The `coneprog` функция решает проблемы SOCP ^{[ 12 ]} используя алгоритм внутренней точки ^{[ 13 ]}
МОИСЕЙ	коммерческий	параллельный алгоритм внутренней точки
Цифровая библиотека НАГ	коммерческий	Числовая библиотека общего назначения с решателем SOCP
СКС	открытый исходный код	SCS (Splitting Conic Solver) — это пакет численной оптимизации для решения крупномасштабных задач с выпуклыми квадратичными конусами.

См. также

Степенные конусы — это обобщения квадратичных конусов до степеней, отличных от 2. ^{[ 14 ]}

Ссылки

^ Jump up to: ^а ^б ^с Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация (PDF) . Издательство Кембриджского университета. ISBN 978-0-521-83378-3 . Проверено 15 июля 2019 г.
^ Потра, Лориан А.; Райт, Стивен Дж. (1 декабря 2000 г.). «Методы внутренних точек». Журнал вычислительной и прикладной математики . 124 (1–2): 281–302. Бибкод : 2000JCoAM.124..281P . дои : 10.1016/S0377-0427(00)00433-7 .
^ Jump up to: ^а ^б Фаузи, Хамза (2019). «О представлении положительного полуопределенного конуса с помощью конуса второго порядка». Математическое программирование . 175 (1–2): 109–118. arXiv : 1610.04901 . дои : 10.1007/s10107-018-1233-0 . ISSN 0025-5610 . S2CID 119324071 .
^ Jump up to: ^а ^б ^с Лобо, Мигель Соуза; Ванденберге, Ливен; Бойд, Стивен; Лебре, Эрве (1998). «Приложения конусного программирования второго порядка» . Линейная алгебра и ее приложения . 284 (1–3): 193–228. дои : 10.1016/S0024-3795(98)10032-0 .
^ «Решение SOCP» (PDF) .
^ «Оптимизация портфеля» (PDF) .
^ Ли, Хаксун (16 января 2022 г.). Численные методы с использованием Java: для науки о данных, анализа и инженерии . Пресс. стр. Глава 10. ISBN 978-1484267967 .
^ Шайдерер, Клаус (08 апреля 2020 г.). «Представление конуса второго порядка для выпуклых подмножеств плоскости». arXiv : 2004.04196 [ math.OC ].
^ Шайдерер, Клаус (2018). «Спектраэдрические тени» . SIAM Journal по прикладной алгебре и геометрии . 2 (1): 26–44. дои : 10.1137/17M1118981 . ISSN 2470-6566 .
^ Алзалг, Баха М. (01 октября 2012 г.). «Стохастическое конусное программирование второго порядка: модели приложений» . Прикладное математическое моделирование . 36 (10): 5122–5134. дои : 10.1016/j.apm.2011.12.053 . ISSN 0307-904X .
^ «Пособия по моделированию МОСЭК - Коническая квадратичная оптимизация» .
^ «Решатель программирования конусов второго порядка — MATLAB coneprog» . Матворкс . 01.03.2021 . Проверено 15 июля 2021 г.
^ «Алгоритм программирования конуса второго порядка — MATLAB и Simulink» . Матворкс . 01.03.2021 . Проверено 15 июля 2021 г.
^ «Пособия по моделированию МОСЭК - Силовые конусы» .

[boyd-1] Jump up to: ^а ^б ^с Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация (PDF) . Издательство Кембриджского университета. ISBN 978-0-521-83378-3 . Проверено 15 июля 2019 г.

[2] Потра, Лориан А.; Райт, Стивен Дж. (1 декабря 2000 г.). «Методы внутренних точек». Журнал вычислительной и прикладной математики . 124 (1–2): 281–302. Бибкод : 2000JCoAM.124..281P . дои : 10.1016/S0377-0427(00)00433-7 .

[Fawzi-3] Jump up to: ^а ^б Фаузи, Хамза (2019). «О представлении положительного полуопределенного конуса с помощью конуса второго порядка». Математическое программирование . 175 (1–2): 109–118. arXiv : 1610.04901 . дои : 10.1007/s10107-018-1233-0 . ISSN 0025-5610 . S2CID 119324071 .

[:0-4] Jump up to: ^а ^б ^с Лобо, Мигель Соуза; Ванденберге, Ливен; Бойд, Стивен; Лебре, Эрве (1998). «Приложения конусного программирования второго порядка» . Линейная алгебра и ее приложения . 284 (1–3): 193–228. дои : 10.1016/S0024-3795(98)10032-0 .

[5] «Решение SOCP» (PDF) .

[6] «Оптимизация портфеля» (PDF) .

[7] Ли, Хаксун (16 января 2022 г.). Численные методы с использованием Java: для науки о данных, анализа и инженерии . Пресс. стр. Глава 10. ISBN 978-1484267967 .

[8] Шайдерер, Клаус (08 апреля 2020 г.). «Представление конуса второго порядка для выпуклых подмножеств плоскости». arXiv : 2004.04196 [ math.OC ].

[9] Шайдерер, Клаус (2018). «Спектраэдрические тени» . SIAM Journal по прикладной алгебре и геометрии . 2 (1): 26–44. дои : 10.1137/17M1118981 . ISSN 2470-6566 .

[10] Алзалг, Баха М. (01 октября 2012 г.). «Стохастическое конусное программирование второго порядка: модели приложений» . Прикладное математическое моделирование . 36 (10): 5122–5134. дои : 10.1016/j.apm.2011.12.053 . ISSN 0307-904X .

[11] «Пособия по моделированию МОСЭК - Коническая квадратичная оптимизация» .

[12] «Решатель программирования конусов второго порядка — MATLAB coneprog» . Матворкс . 01.03.2021 . Проверено 15 июля 2021 г.

[13] «Алгоритм программирования конуса второго порядка — MATLAB и Simulink» . Матворкс . 01.03.2021 . Проверено 15 июля 2021 г.

[14] «Пособия по моделированию МОСЭК - Силовые конусы» .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]