0. はじめに
「21世紀の線形計画」といわれる半正定値計画(SDP)を実装し理解を深めようと思います。多くの教科書では半正定値計画の理論的なところを触れているので、実装例を備忘録の連載という形で書いていきます。21世紀の皆様に少しでもお役に立てれば幸いです。
1.半正定値計画
半正定値計画は次の標準式で記述される。
\begin{eqnarray}
\min & & C \bullet X\\
s.t. & & \ \ A_{i}\bullet X = b_{i}\ \ \ (i=1,2,...,m)\\
& & \ \ X\succeq 0
\end{eqnarray}
\tag{1}
半正定値計画は様々な数値解法が提案されているが、本記事では主双対内点法に焦点を当てる。線形計画の主双対内点法とは異なり、半正定値計画の主双対内点法では相補性条件に対して設計の自由度がある。
探索方向としてHRVW/KSH/M方向や NT方向あるいは AHO方向など提案されている。これらの探索方向は、MZ方向族として統一的にまとめられている。本記事ではAHO方向のみ取り扱い実装例を紹介する。
| 数値解法 | スケーリング方向 | 詳細 |
|---|---|---|
| 主双対内点法 | XZ method | |
| 主双対内点法 | MZ方向族 | XZ+ZX method(AHO方向) |
| 主双対内点法 | MZ方向族 | HRVW/KSH/M方向 |
| 主双対内点法 | MZ方向族 | NT方向 |
参照
- 半正定値計画問題に対する主双対内点法
- F. Alizadeh, J.-P. A. Haeberly and M. L. Overton, Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results, SIAM Journal on Optimization 8 (1998) 746-768.
- On the Kronecker
2.実装
半正定値計画のAHO方向による主双対パス追跡法のコードを下記に置きます。よかったら参照ください。
半正定値計画の適用例は下記の記事を参考にしました。
参照
3.おわりに
実装したことでSDPの理解が深まりました。半正定値計画を実装する際に躓いた点としては、クロネッカー積とか対称クロネッカー積とはなんぞや？という点でした。対称クロネッカー積については下記の文献が参考になりました。
基本的には線形計画と同じ流れで理論も展開されており、大幅な変更もなく実装もできました。今後は、SDPの産業応用の例で有名なLMIについて理解を深めていこうと思います。