二次計画法

目的関数が二次、制約が線形な最適化問題。Quadratic Programming、QP。

$$\underset{x}{\min }\frac{1}{2}{x}^{\top }Qx+c^{\top }x\text{s.t.}Ax\le b$$

凸性は Q で決まる#

$Q$ が半正定値なら目的関数は 凸で、多項式時間で解ける。 $Q$ が不定なら非凸となり、NP 困難になる。 $Q$ の固有値の符号を見るだけで難しさが決まるのが QP の特徴。

どこに現れるか#

• サポートベクターマシン の双対問題がそのまま QP
• ポートフォリオ最適化 — 分散（＝共分散行列による二次形式）を 最小化し、期待収益に線形制約を置く
• SQP の各反復で解く部分問題
• モデル予測制御 (MPC) の各ステップ

変数が 0/1 だと#

$x\in {\{\mathrm{0,1}\}}^n$ に限った二次計画が QUBO。制約なしの形に整理でき、 量子アニーリングや QAOAが扱う対象になる。

参考文献#

• Jorge Nocedal, Stephen J. Wright. Numerical Optimization, 2nd ed. Springer, 2006. https://doi.org/10.1007/978-0-387-40065-5
• Stephen Boyd, Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. https://web.stanford.edu/~boyd/cvxbook/