最適化セミナーのご案内

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条件と呼びます.

 Numerical 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$はペナルティパラメ-タ,$\nu > 0$は主双対項の度合いを表すパラメータです.

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

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

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

注2)詳細は論文[14][15][16]を参照


 

 

上に戻る