二次錐体計画法

Convex optimization problem

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

最小化 ${\displaystyle \ f^{T}x\ }$

対象となる

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

${\displaystyle Fx=g\ }$

ここで、問題のパラメータは、、です。は最適化変数です。 はユークリッドノルムであり、転置を示します。^[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}}$ ${\displaystyle \lVert x\rVert _{2}}$ ${\displaystyle ^{T}}$

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

${\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次次元円錐は次のように定義される。 ${\displaystyle n+1}$

${\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次円錐は、 ${\displaystyle \mathbb {R} ^{3}}$

${\displaystyle \left\{(x,y,z){\Big |}{\sqrt {x^{2}+y^{2}}}\leq z\right\}}$。

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

${\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次錐は半正定値行列の錐に埋め込むことができる。

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

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

${\displaystyle x^{T}Mx\geq 0{\text{ for all }}x\in \mathbb {R} ^{n}}$

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

同様に、

${\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は凸二次制約線形計画法 に等しくなります。 ${\displaystyle A_{i}=0}$ ${\displaystyle i=1,\dots ,m}$ ${\displaystyle c_{i}=0}$ ${\displaystyle i=1,\dots ,m}$

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

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

例

二次制約

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

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

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

${\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}}}$

確率線形計画法

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

最小化 ${\displaystyle \ c^{T}x\ }$

対象となる

${\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 \Sigma _{i}\ }$ ${\displaystyle p\geq 0.5}$

最小化 ${\displaystyle \ c^{T}x\ }$

対象となる

${\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] ${\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ソルバーを備えた汎用数値ライブラリ

参照

• べき乗円錐は2次円錐を2以外のべき乗に一般化したものである。^[15]

参考文献

1. Boyd, Stephen; Vandenberghe, Lieven (2004). 凸最適化(PDF) . ケンブリッジ大学出版局. ISBN 978-0-521-83378-3. 2019年7月15日閲覧。
2. ジブリン、シャフィウ；スウィフト、ジェームズ・W. (2024). 「2次錐関数について」.最適化ジャーナル. 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. 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. 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 モデリング クックブック - パワー コーン」。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Second-order_cone_programming&oldid=1314699711"