二次錐体計画法

2階錐計画（SOCP）は、次の形式の 凸最適化問題である。

最小化 fT× {\displaystyle \f^{T}x\}
対象となる
‖あ私×+b私‖2≤c私T×+d私、私＝1、…、メートル{\displaystyle \lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i},\quad i=1,\dots ,m}
F×＝グラム {\displaystyle Fx=g\ }

ここで、問題のパラメータは、、です。は最適化変数です。 はユークリッドノルムであり、転置を示します。[ 1 ]f∈Rn、 あ私∈Rn私×n、 b私∈Rn私、 c私∈Rn、 d私∈R、 F∈Rp×n{\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}}グラム∈Rp{\displaystyle g\in \mathbb {R} ^{p}}×∈Rn{\displaystyle x\in \mathbb {R} ^{n}}‖×‖2{\displaystyle \lVert x\rVert _{2}}T{\displaystyle ^{T}}

「二次錐計画法」という名前は、次の形式をとる個々の制約の性質に由来しています。

‖あ×+b‖2≤cT×+d{\displaystyle \lVert Ax+b\rVert _{2}\leq c^{T}x+d}

これらはそれぞれ、最適化変数 上に定義された2次多項式関数に基づく不等式によって囲まれる部分空間を定義します。これは凸錐を定義することが示されており、そのため「2次錐」と呼ばれます。[ 2 ]凸錐の定義により、それらの交差も凸錐であることが示されますが、必ずしも単一の2次不等式によって定義できるとは限りません。より詳細な説明については以下を参照してください。 ×{\displaystyle x}

SOCPは内点法で解くことができ[ 3 ]、一般に半正定値計画問題（SDP）よりも効率的に解くことができます。[ 4 ] SOCPの工学的応用としては、フィルタ設計、アンテナアレイの重量設計、トラス設計、ロボットにおける把持力の最適化などがあります。[ 5 ]定量金融における応用としてはポートフォリオ最適化があります。市場インパクト制約の中には線形ではないため二次計画法では解くことができないものもありますが、SOCP問題として定式化することができます。[ 6 ] [ 7 ] [ 8 ]

二次錐体

標準または単位2次次元円錐は次のように定義される。 n+1{\displaystyle n+1}

Cn+1＝{[×t]|×∈Rn、t∈R、‖×‖2≤t}{\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\}}。

2次円錐は、2次円錐、アイスクリーム円錐、ローレンツ円錐とも呼ばれます。例えば、標準的な2次円錐は、 R3{\displaystyle \mathbb {R} ^{3}}

{（×、y、z）|×2+y2≤z}{\displaystyle \left\{(x,y,z){\Big |}{\sqrt {x^{2}+y^{2}}}\leq z\right\}}。

2次円錐制約を満たす点の集合は、アフィン写像の下での単位2次円錐の逆像である。

‖あ私×+b私‖2≤c私T×+d私⇔[あ私c私T]×+[b私d私]∈Cn私+1{\displaystyle \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}}

したがって凸状です。

2次錐は半正定値行列の錐に埋め込むことができる。

||×||≤t⇔[t私××Tt]≽0、{\displaystyle ||x||\leq t\Leftrightarrow {\begin{bmatrix}tI&x\\x^{T}&t\end{bmatrix}}\succcurlyeq 0,}

つまり、2階錐制約は線形行列不等式と等価である。ここでの命名法は混乱を招く可能性がある。ここで は半正定値行列を意味する。つまり M≽0{\displaystyle M\succcurlyeq 0}M{\displaystyle M}

×TM×≥0 すべての人のために ×∈Rn{\displaystyle x^{T}Mx\geq 0{\text{ }}x\in \mathbb {R} ^{n}} に対して

これは従来の意味での線形不等式ではありません。

同様に、

‖あ私×+b私‖2≤c私T×+d私⇔[（c私T×+d私）私あ私×+b私（あ私×+b私）Tc私T×+d私]≽0{\displaystyle \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}。

他の最適化問題との関係

凸最適化問題の階層。(LP: 線形計画法、QP: 二次計画法、SOCP: 2 次円錐計画法、SDP: 半正定値計画法、CP: 円錐計画法。)

のとき、SOCPは線形計画法に簡約されます。のとき、SOCPは凸二次制約線形計画法 に等しくなります。 あ私＝0{\displaystyle A_{i}=0}私＝1、…、メートル{\displaystyle i=1,\dots ,m}c私＝0{\displaystyle c_{i}=0}私＝1、…、メートル{\displaystyle i=1,\dots ,m}

凸二次制約二次計画法は、目的関数を制約条件として再定式化することでSOCPとして定式化することもできる。[ 5 ]半正定値計画法はSOCPを包含する。SOCP制約条件は線形行列不等式（LMI）として記述でき、半正定値計画法のインスタンスとして再定式化できるからである。[ 5 ]しかし、逆は成り立たない。2次錐表現を許容しない半正定値錐が存在する。[ 4 ]

平面上の任意の閉じた凸半代数集合は、 SOCP の実行可能領域として書き込むことができます。[ 9 ]しかし、SDP では表現できない高次元の凸半代数集合が存在することが知られています。つまり、SDP の実行可能領域として書き込むことができない凸半代数集合が存在するのです (ましてやSOCP の実行可能領域として書き込むことはできません)。 [ 10 ]

例

二次制約

次の ような凸二次制約を考える。

×Tあ×+bT×+c≤0。{\displaystyle x^{T}Ax+b^{T}x+c\leq 0.}

これはSOCP制約と同等である

‖あ1/2×+12あ−1/2b‖≤（14bTあ−1b−c）12{\displaystyle \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}}}

確率線形計画法

不等式形式の 確率線形計画法を考える

最小化 cTx {\displaystyle \ c^{T}x\ }
対象となる
P(aiTx≤bi)≥p,i=1,…,m{\displaystyle \mathbb {P} (a_{i}^{T}x\leq b_{i})\geq p,\quad i=1,\dots ,m}

ここで、パラメータは平均と共分散を持つ独立したガウス分布ベクトルである。この問題はSOCPとして表現できる。 ai {\displaystyle a_{i}\ }a¯i{\displaystyle {\bar {a}}_{i}}Σi {\displaystyle \Sigma _{i}\ }p≥0.5{\displaystyle p\geq 0.5}

最小化 cTx {\displaystyle \ c^{T}x\ }
対象となる
a¯iTx+Φ−1(p)‖Σi1/2x‖2≤bi,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 )\ }

確率的2次円錐計画法

2階錐計画は、定義するデータが決定論的であるため、決定論的2階錐計画と呼ばれます。確率的2階錐計画は、決定論的2階錐計画を定義するデータの不確実性に対処するために定義された最適化問題の一種です。[ 11 ]

その他の例

その他のモデリング例はMOSEKモデリングクックブックで参照できます。[ 12 ]

ソルバーとスクリプト（プログラミング）言語

名前 ライセンス 簡単な情報
アルグリブ無料/商用並列 SOCP ソルバーを備えたデュアル ライセンスの C++/C#/Java/Python 数値解析ライブラリ。
アンプルコマーシャルSOCPをサポートする代数モデリング言語
アルテリス・クニトロコマーシャル
CPLEXコマーシャル
FICOエクスプレスコマーシャル
Gurobi オプティマイザーコマーシャル
MATLABコマーシャルこのconeprog関数はSOCP問題[ 13 ]を内点法アルゴリズム[ 14 ]を用いて解く。
モセクコマーシャル並列内点アルゴリズム
NAG数値計算ライブラリコマーシャルSOCPソルバーを備えた汎用数値ライブラリ

参照

参考文献

  1. ^ a b Boyd, Stephen; Vandenberghe, Lieven (2004).凸最適化(PDF) . Cambridge University Press. ISBN 978-0-521-83378-3. 2019年7月15日閲覧。
  2. ^ Jibrin, Shafiu; Swift, James W. (2024). 「2次錐関数について」 . Journal of Optimization . 2024 (1) 7090058. doi : 10.1155/2024/7090058 . ISSN 2314-6486 . 
  3. ^ Potra, lorian A.; Wright, Stephen J. (2000年12月1日). 「内点法」. Journal of Computational and Applied Mathematics . 124 ( 1–2 ): 281– 302. Bibcode : 2000JCoAM.124..281P . doi : 10.1016/S0377-0427(00)00433-7 .
  4. ^ a b Fawzi, Hamza (2019). 「2次円錐を用いた半正定値円錐の表現について」.数理計画. 175 ( 1–2 ): 109–118 . arXiv : 1610.04901 . doi : 10.1007/s10107-018-1233-0 . ISSN 0025-5610 . S2CID 119324071 .  
  5. ^ a b c Lobo, Miguel Sousa; Vandenberghe, Lieven; Boyd, Stephen; Lebret, Hervé (1998). 「二次錐計画法の応用」線形代数とその応用. 284 ( 1–3 ): 193–228 . doi : 10.1016 /S0024-3795(98)10032-0 .
  6. ^ 「SOCP の解決」(PDF)。
  7. ^ 「ポートフォリオ最適化」（PDF） .
  8. ^ Li, Haksun (2022年1月16日). Javaを用いた数値解析：データサイエンス、分析、エンジニアリング向け. APress. pp. 第10章. ISBN 978-1-4842-6796-7。
  9. ^ Scheiderer, Claus (2020-04-08). 「平面の凸部分集合の2次円錐表現」. arXiv : 2004.04196 [ math.OC ].
  10. ^ Scheiderer, Claus (2018). 「Spectrahedral Shadows」 . SIAM Journal on Applied Algebra and Geometry . 2 (1): 26– 44. doi : 10.1137/17M1118981 . ISSN 2470-6566 . 
  11. ^ Alzalg, Baha M. (2012-10-01). 「確率的二次円錐計画法：応用モデル」 .応用数理モデリング. 36 (10): 5122– 5134. doi : 10.1016/j.apm.2011.12.053 . ISSN 0307-904X . 
  12. ^ 「MOSEK モデリング クックブック - 円錐二次最適化」。
  13. ^ 「2次円錐計画法ソルバー - MATLAB coneprog」 . MathWorks . 2021年3月1日. 2021年7月15日閲覧。
  14. ^ 「2次円錐計画法アルゴリズム - MATLAB & Simulink」 . MathWorks . 2021年3月1日. 2021年7月15日閲覧。
  15. ^ 「MOSEK モデリング クックブック - パワー コーン」。
「 https://en.wikipedia.org/w/index.php?title=Second-order_cone_programming&oldid=1314699711」より取得