Программирование конуса второго порядка
Задача выпуклой оптимизации

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

минимизировать   ф Т х   {\displaystyle \ f^{T}x\ }
при условии
‖ А я х + б я ‖ 2 ≤ с я Т х + г я , я = 1 , … , м {\displaystyle \lВертикаль A_{i}x+b_{i}\rВертикаль _{2}\leq c_{i}^{T}x+d_{i},\quad i=1,\dots ,м}
Ф х = г   {\displaystyle Fx=g\ }

где параметры задачи , а . — переменная оптимизации. — евклидова норма и обозначает транспонирование . [1] «Конус второго порядка» в SOCP возникает из ограничений, которые эквивалентны требованию, чтобы аффинная функция лежала в конусе второго порядка в . [1] ф ∈ Р н ,   А я ∈ Р н я × н ,   б я ∈ Р н я ,   с я ∈ Р н ,   г я ∈ Р ,   Ф ∈ Р п × н {\displaystyle 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}} г ∈ Р п {\displaystyle g\in \mathbb {R} ^{p}} х ∈ Р н {\displaystyle x\in \mathbb {R} ^{n}} ‖ х ‖ 2 {\displaystyle \lВертикаль x\rВертикаль _{2}} Т {\displaystyle ^{Т}} ( А х + б , с Т х + г ) {\displaystyle (Ax+b,c^{T}x+d)} Р н я + 1 {\displaystyle \mathbb {R} ^{n_{i}+1}}

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

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

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

С н + 1 = { [ х т ] | х ∈ Р н , т ∈ Р , ‖ х ‖ 2 ≤ т } {\displaystyle {\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\}} .

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

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

‖ А я х + б я ‖ 2 ≤ с я Т х + г я ⇔ [ А я с я Т ] х + [ б я г я ] ∈ С н я + 1 {\displaystyle \lВертикаль A_{i}x+b_{i}\rВертикаль _{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}}

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

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

| | х | | ≤ т ⇔ [ т я х х Т т ] ≽ 0 , {\displaystyle ||x||\leq t\Leftrightarrow {\begin{bmatrix}tI&x\\x^{T}&t\end{bmatrix}}\succcurlyeq 0,}

т.е. ограничение конуса второго порядка эквивалентно линейному матричному неравенству (Здесь означает полуопределенную матрицу). Аналогично, мы также имеем, М ≽ 0 {\displaystyle M\succcurlyeq 0} М {\displaystyle М}

‖ А я х + б я ‖ 2 ≤ с я Т х + г я ⇔ [ ( с я Т х + г я ) я А я х + б я ( А я х + б я ) Т с я Т х + г я ] ≽ 0 {\displaystyle \lВертикаль A_{i}x+b_{i}\rВертикаль _{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} .

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

Иерархия задач выпуклой оптимизации. (LP: линейное программирование, QP: квадратичное программирование, SOCP: конусная программа второго порядка, SDP: полуопределенная программа, CP: конусная программа.)

При , SOCP сводится к линейному программированию . При , SOCP эквивалентен выпуклому квадратично ограниченному линейному программированию. А я = 0 {\displaystyle A_{i}=0} я = 1 , … , м {\displaystyle i=1,\точки ,м} с я = 0 {\displaystyle c_{i}=0} я = 1 , … , м {\displaystyle i=1,\точки ,м}

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

Примеры

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

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

х Т А х + б Т х + с ≤ 0. {\displaystyle x^{T}Ax+b^{T}x+c\leq 0.}

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

‖ А 1 / 2 х + 1 2 А − 1 / 2 б ‖ ≤ ( 1 4 б Т А − 1 б − с ) 1 2 {\displaystyle \lВертикаль A^{1/2}x+{\frac {1}{2}}A^{-1/2}b\rВертикаль \leq \left({\frac {1}{4}}b^{T}A^{-1}bc\right)^{\frac {1}{2}}}

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

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

минимизировать   с Т х   {\displaystyle \ c^{T}x\ }
при условии
П ( а я Т х ≤ б я ) ≥ п , я = 1 , … , м {\displaystyle \mathbb {P} (a_{i}^{T}x\leq b_{i})\geq p,\quad i=1,\dots ,m}

где параметры — независимые гауссовские случайные векторы со средним значением и ковариацией и . Эту задачу можно выразить как SOCP а я   {\displaystyle a_{i}\ } а ¯ я {\displaystyle {\bar {a}}_{i}} Σ я   {\displaystyle \Сигма _{i}\ } п ≥ 0,5 {\displaystyle p\geq 0.5}

минимизировать   c T x   {\displaystyle \ c^{T}x\ }
при условии
a ¯ i T x + Φ − 1 ( p ) ‖ Σ i 1 / 2 x ‖ 2 ≤ b i , i = 1 , … , m {\displaystyle {\bar {a}}_{i}^{T}x+\Phi ^{-1}(p)\lVert \Sigma _{i}^{1/2}x\rVert _{2}\leq b_{i},\quad i=1,\dots ,m}

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

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

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

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

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

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

ИмяЛицензияКраткая информация
АМПЛкоммерческийАлгебраический язык моделирования с поддержкой SOCP
Артелис Книтрокоммерческий
Кларабельс открытым исходным кодомСобственный решатель Julia и Rust SOCP. Может решать выпуклые задачи с произвольными типами точности.
CPLEXкоммерческий
CVXPYс открытым исходным кодомЯзык моделирования Python с поддержкой SOCP. Поддерживает решатели с открытым исходным кодом и коммерческие.
CVXOPTс открытым исходным кодомВыпуклый решатель с поддержкой SOCP
ЭКОСс открытым исходным кодомРешатель SOCP, оптимизированный для встраиваемых приложений
ФИКО Экспресскоммерческий
Оптимизатор Gurobiкоммерческий
МАТЛАБкоммерческийФункция coneprogрешает задачи SOCP [12] с использованием алгоритма внутренней точки [13]
МОСЭКкоммерческийпараллельный алгоритм внутренней точки
Числовая библиотека NAGкоммерческийУниверсальная числовая библиотека с решателем SOCP
СКСс открытым исходным кодомSCS (Splitting Conic Solver) — это пакет численной оптимизации для решения крупномасштабных задач с выпуклыми квадратичными конусами.

Смотрите также

  • Конусы степеней являются обобщениями квадратичных конусов до степеней, отличных от 2. [14]

Ссылки

  1. ^ abc Бойд, Стивен; Ванденберг, Ливен (2004). Выпуклая оптимизация (PDF) . Cambridge University Press. ISBN 978-0-521-83378-3. Получено 15 июля 2019 г. .
  2. ^ Potra, lorian A.; Wright, Stephen J. (1 декабря 2000 г.). «Методы внутренней точки». Журнал вычислительной и прикладной математики . 124 (1–2): 281–302. Bibcode : 2000JCoAM.124..281P. doi : 10.1016/S0377-0427(00)00433-7.
  3. ^ ab Fawzi, Hamza (2019). «О представлении положительного полуопределенного конуса с использованием конуса второго порядка». Математическое программирование . 175 (1–2): 109–118. arXiv : 1610.04901 . doi :10.1007/s10107-018-1233-0. ISSN  0025-5610. S2CID  119324071.
  4. ^ abc Лобо, Мигель Соуза; Ванденберге, Ливен; Бойд, Стивен; Лебре, Эрве (1998). «Применение программирования конусов второго порядка». Линейная алгебра и ее приложения . 284 (1–3): 193–228. doi : 10.1016/S0024-3795(98)10032-0 .
  5. ^ «Решение SOCP» (PDF) .
  6. ^ "оптимизация портфеля" (PDF) .
  7. ^ Ли, Хаксун (16 января 2022 г.). Численные методы с использованием Java: для науки о данных, анализа и проектирования . APress. стр. Глава 10. ISBN 978-1484267967.
  8. ^ Шайдерер, Клаус (2020-04-08). «Представление конуса второго порядка для выпуклых подмножеств плоскости». arXiv : 2004.04196 [math.OC].
  9. ^ Шайдерер, Клаус (2018). «Спектраэдральные тени». Журнал SIAM по прикладной алгебре и геометрии . 2 (1): 26–44. doi : 10.1137/17M1118981 . ISSN  2470-6566.
  10. ^ Alzalg, Baha M. (2012-10-01). "Стохастическое программирование конусов второго порядка: прикладные модели". Прикладное математическое моделирование . 36 (10): 5122–5134. doi :10.1016/j.apm.2011.12.053. ISSN  0307-904X.
  11. ^ «MOSEK Modeling Cookbook — Коническая квадратичная оптимизация».
  12. ^ "Решатель программирования конусов второго порядка - MATLAB coneprog". MathWorks . 2021-03-01 . Получено 2021-07-15 .
  13. ^ "Алгоритм программирования конусов второго порядка - MATLAB и Simulink". MathWorks . 2021-03-01 . Получено 2021-07-15 .
  14. ^ «Книга рецептов моделирования MOSEK — Power Cones».
Retrieved from "https://en.wikipedia.org/w/index.php?title=Second-order_cone_programming&oldid=1248743433"