二次計画法

以下の最適化問題を考える

$$\begin{array}{}\text{min}{\displaystyle \frac{1}{2}}{x}^{T}Qx+c^{T}x\\ \text{s.t.}Ax=b,A_{eq}x\le b_{eq}\\ x\in {\mathbb{R}}^n\end{array}$$

内点法による最適化

KKT条件

与えられた問題に対するKKT条件は以下

$$\begin{array}{l}Qx+c+A^T\lambda +A_{eq}{\lambda }_{eq}=\mathbf{0}\\ {\lambda }_i{s}_i=\rho \\ Ax-b+s=\mathbf{0}\\ A_{eq}x-b_{eq}=\mathbf{0}\\ s>\mathbf{0}\\ \lambda >\mathbf{0}\end{array}$$

KKT条件について

探索方向の決定

KKT条件に対して各変数を微小変化させた場合を考える

$$\begin{array}{c}x\leftarrow x+\mathrm{\Delta }x\\ s\leftarrow s+\mathrm{\Delta }s\\ \lambda \leftarrow \lambda +\mathrm{\Delta }\lambda \\ {\lambda }_{eq}\leftarrow {\lambda }_{eq}+\mathrm{\Delta }{\lambda }_{eq}\end{array}$$

KKT条件に以上を代入し微小変化量に対して連立方程式の形式にまとめる

$$\begin{gathered} \left[\begin{array}{cccc}Q& \mathbf{0}& A^T& A_{eq}^T\\ A& I& \mathbf{0}& \mathbf{0}\\ 0& D_{\lambda }& D_s& \mathbf{0}\\ A_{e}q& \mathbf{0}& 0& \mathbf{0}\end{array}\right]\left[\begin{array}{c}\mathrm{\Delta }x\\ \mathrm{\Delta }s\\ \mathrm{\Delta }\lambda \\ \mathrm{\Delta }{\lambda }_{eq}\end{array}\right]=\left[\begin{array}{c}Qx+c+A^T\lambda +A_{eq}^T{\lambda }_{eq}\\ Ax-b+s\\ -\rho I+\lambda ⨀s\\ A_{eq}x-b_{eq}\end{array}\right] \\ {D}_{\lambda }=\text{diag}(\lambda ) \\ {D}_s=\text{diag}(s) \\ \lambda ⨀s=\text{(要素積・アダマール積)} \end{gathered}$$

この方程式を解いて各変数を更新していく

ActiveSet法による最適化

ADMMによる最適化

参考文献

• 二次計画法のアルゴリズム