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

B.1.1 問題

　次の最適化問題

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

を考えます注1．ここで，変数$x = (x_1,\cdots,x_n)^t$は$n$次元ベクトルで，関数$f$は目的関数です．また，$g:R^n \to R^m$は$m$次元のベクトル値関数です．この問題のラグランジュ関数を

\[L(x,y,z) = f(x) - y^t g(x) - z^t x\]

としたとき，Karush-Kuhn-Tucker（KKT）条件（最適性の一次の必要条件）は次式で与えられます：

\begin{align*} \nabla_x L(x,y,z) = 0, & \\ g(x) = 0, & \\ XZe = 0, & \quad x \ge 0, z \ge 0.\end{align*}

ただし，$X = diag(x_1,\cdots,x_n) \in R^n$, $Z = diag(z_1,\cdots,z_n) \in R^n$, $e = (1,\cdots,1)^t \in R^n$です．ここで，相補性条件$XZe = 0$を$XZe = \mu e$（$\mu > 0$）で置き換えたものを修正KKT条件と呼びます．

　Nuorium Optimizerではバリヤペナルティ関数：

\[F(x,z) = f(x) - \mu \sum_{i=1}^n \log (x_i) + \rho \sum_{i=1}^m |g_i(x)| + \upsilon \left( x^T z - \mu \sum_{i=1}^n \log (x_i z_i) \right)\]

をメリット関数として採用します．ここで，$\mu > 0$はバリヤパラメ－タ，$\rho > 0$はペナルティパラメ－タ，$\upsilon > 0$は主双対項の考慮度合いを表すパラメータです．

　非線形最適化問題に対する内点法では，「修正KKT条件を満たす点を求めて，修正KKT条件を更新する」という作業を逐次行います．この際に，メリット関数$F(x,z)$の一次近似$F_l(x,z)$あるいは二次近似$F_q(x,z)$の変化量が重要な手がかりとなります注2．次項以降で示すように，修正KKT条件を求める方法は複数存在します（直線探索を利用する方法・信頼領域を利用する方法）．

　この作業を通して，最終的に元来のKKT条件を満たす点を求めます．

注1）ここでは，説明の便宜上このような形式を考えますが，Nuorium Optimizerでは制約関数に上下限が存在する場合，等式条件，変数に上下限が存在する場合などの一般形を扱うことができます．また，制約条件が存在しない問題も扱うことができます．

注2）詳細は論文[13][14][15]を参照

B.1 内点法
B.1.2 直線探索を利用する方法

 

 

上に戻る