数理最適化セミナーのご案内

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_i - B$と表現しても構いません．

　この問題のラグランジュ関数を$w = (y, Y, Z)$として

\[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) Z = 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)$であるものとします．

　Nuorium 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) \\ -\nabla g(x)^T & 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 A_i, X^{-1} A_j Z \rangle$であるものとします．$A_i$, $A_j$の構造に応じて$H_{ij}$を計算する方法は異なります．

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

　問題が非凸な場合，大域的収束性を確保するための工夫が必要になります．Nuorium Optimizerでは信頼領域法に基づく方法を利用する場合，大域的収束を保証する方向と，局所的収束に有利な方向を混ぜ合わせて探索方向を決定します．

B.1.4 線形計画問題専用内点法
B.2 単体法・有効制約法

 

 

上に戻る