最適化セミナーのご案内

B.1.5 半正定値計画問題専用内点法

 次の最適化問題

\[\begin{array}{@{}lll@{}} \mbox{最小化} & f(x) & x \in R^n, X \in S^p \\ \mbox{条件} & g(x) = 0, X_0(x) = X, & x \ge 0, X \succeq 0 \end{array}\]

を考えます.ここで,変数$x = (x_1,\cdots,x_n)^t$$n$次元ベクトルで,関数$f$は目的関数です.また,$g:R^n \to R^m$$m$次元のベクトル値関数です.変数$X$$p$次元対称正方行列で,$X \succeq 0$は行列$X$の半正定値制約を意味するものとします.$X_0:R^n \to S^p$$n$次元ベクトルを対称正方行列空間に写す写像です.問題が線形の場合,$X_0$$\displaystyle X_0(x) = \sum_{i=1}^n A_i x - B$と表現しても構いません.

 この問題のラグランジュ関数を

\[L(w) = f(x) - y^T g(x) - \langle X_0(x) - X, Y \rangle - \langle X, Z \rangle\]

としたとき,Karush-Kuhn-Tucker(KKT)条件(最適性の一次の必要条件)は次式で与えられます:

\begin{align*} & \nabla_x L(w) = \nabla f(x) - \nabla g(x)^T \Delta y - A^*(x) Y = 0 \\ & \nabla_X L(w) = Y - Z = 0 \\ & g(x) = 0 \\ & X_0(x) - X = 0 \\ & X \circ Z = 0, X \succeq 0, Z \succeq 0 \end{align*}

ここでは,$\displaystyle A_i(x) = \frac{\partial X_0(x)}{\partial x_i}$$\displaystyle {A^*}\left( x \right)Z = \left( \begin{array}{c} \langle A_1, Z \rangle \\ \ldots \\ \langle A_n, Z \rangle \end{array} \right)$$\displaystyle X \circ Z = \frac{1}{2}(XZ + ZX)$であるものとします.

 Numerical Optimizerでは,このKKT条件を満たす点を,Newton法を利用して反復解法で求めます.

 線形な半正定値計画問題の場合,大域的収束性は保証されますが,そうでない問題を扱う場合,大域的収束を保証するには,メリット関数を定義する必要があります.

 非線形半正定値計画問題を扱う場合,バリヤペナルティ関数:

\begin{align*} & F(x,X,Z) = F_{BP}(x,X) + \nu F_{PD}(x,X,Z) \\ & F_{BP}(x,X) = f(x) - \mu \log (\det X) + \rho \| g(x) \|_1 + \rho' \| X_0(x) - X \|_1 \\ & F_{PD}(X,Z) = \langle X, Z \rangle - \mu \log (\det X \det Z) \end{align*}

をメリット関数として採用します.ここで,$\mu > 0$はバリヤパラメ-タ,$\rho, \rho' > 0$はペナルティパラメ-タ,$\nu > 0$は主双対項の度合いを表すパラメータです.

 探索方向を求めるNewton方程式は以下のように記述されます.

\begin{align*} & \left( \begin{array}{cc} G + H & -\nabla g(x)^T \\ -\nabla g(x) & 0 \end{array} \right) \left( \begin{array}{c} \Delta x \\ \Delta y \end{array} \right) = - \left( \begin{array}{c} \nabla f(x) - \nabla g(x)^T y - \mu A^*(x) X^{-1} + A^*(x)(ZX_0 X^{-1} - Z) \\ g(x) \end{array} \right) \\ & \Delta X = X_0(x + \Delta x) - X \\ & \Delta Z = \mu X^{-1} - Z - \frac{1}{2}(Z\Delta X X^{-1} + X^{-1} \Delta XZ) \end{align*}

 ここでは,$H_{ij} = \langle Ai, X^{-1} A_j Z \rangle$であるものとします.$A_i$, $A_j$の構造に応じて$H_{ij}$を計算する方法は異なります.

 修正KKT条件を満たす点を逐次求め反復するという枠組み自体は,一般の非線形用内点法と同等です.Newton方程式を解く際には,探索方向を対称化するため,KSH方向へのスケーリングを行っています.

 問題が非凸な場合,大域的収束性を確保するための工夫が必要になります.Numerical Optimizerでは準ニュートン法あるいはLevenberg-Marquardt法に基づいてGの正定値性が確保され,大域的収束性が保証されます.信頼領域法に基づく方法を利用する場合,大域的収束を保証する方向と,局所的収束に有利な方向を混ぜ合わせて探索方向を決定します.


 

 

上に戻る