制約付き最適化とは何？わかりやすく解説 Weblio辞書

制約付き最適化

読み方：せいやくつきさいてきか
【英】：constrained optimization

概要

制約付き最適化とは, ベクトル空間上の連続関数を適当な(連続)集合上で最適化する問題およびその解法である. 代表的な制約付き最適化問題には線形計画問題, 2次計画問題, 多面体上の凸(非線形)関数最適化問題, 凸計画問題などがあり, 問題に応じた解法が考案されている. 一般的な問題にも適用できる解法としては, 逐次2次計画法や内点法がある.

詳説

制約付き最適化とは, $n\,$ 次元ベクトル空間上の連続関数 $f(x)\,$ を適当な(連続)集合上で最適化する問題で一般に次の形で記述される.

$\begin{array}{ll} \mbox{min}_x & f(x) \\ \mbox{s. t.} & g_i(x) \le 0 \ (i=1,\ldots, m), \ \ \ h_j(x) = 0 \ (j=1,\ldots, l). \end{array}$

$(1)\,$

代表的な制約付き最適化問題には (A) 線形計画問題 (linear programming); (B) 2次計画問題 (quadratic programming); (C) 多面体上の凸(非線形)計画問題; (D) 凸計画問題 (convex programming); (E) (一般の) 非線形計画問題 (nonlinear programming)( $g, h, f\,$ が一般の非線形関数である場合);があり, 各問題の特徴を生かした解法が研究されている．以下では主として (E)の解法について述べる.

　問題 (1)に対するラグランジュ関数 (Lagrangian function)を次のように定義する.

$L(x,\lambda, \zeta) := f(x) + \sum_{i=1}^m \lambda_i g_i(x) + \sum_{j=1}^l \zeta_j h_j(x).$

解法は, 最適性の必要条件であるカルーシュ・キューン・タッカー条件 (Karush-Kuhn-Tucker condition)

$\begin{array}{l} \nabla_x L(x,\lambda,\zeta)=0, \\ \lambda_i g_i(x) = 0 \qquad (i=1, \ldots, m), \\ g_i(x) \leq 0, \ \lambda_i \geq 0 \qquad (i=1, \ldots, m), \\ h_j(x) = 0 \qquad (j=1, \ldots, l), \end{array}$

$(2)\,$

を満たす点(KKT点)を求めることを目的として設計される.探索方向を定め，その方向に適当なステップ幅だけ進むことを繰り返して漸近的にKKT点に収束する点列を生成する. 主な解法としては, (1) 射影勾配法 (gradient projection method)および有効制約法 (active set method); (2) ペナルティ関数法 (penalty function method); (3) 乗数法 (multiplier method); (4) 逐次2次計画法 (sequential quadratic programming method); (5) 内点法 (interior point method)が知られている. これらの内で実用性が高いとされるのは逐次2次計画法と内点法であるが, 制約領域が多面体である場合は有効制約法も用いられる.現状では, 逐次2次計画法により数百変数程度の中規模問題が, さらに内点法によって数千, 数万変数の大規模問題がある程度解けるようになりつつある.

　勾配射影法は, 実行可能領域 (やその境界) の接平面の集合上に目的関数の勾配を射影してその(逆)方向に進む方法で、等式制約のみの問題に対するものが基本形である [2]．有効制約法は制約領域が多面体である場合に対する勾配射影法の拡張である [2].

　ペナルティ関数法は, 問題を無制約最適化問題に変換して解く方法であり,60年代に研究された[2, 4].この方法では, 目的関数に制約を満たさないことに対するペナルティ項を付加したペナルティ関数 (penalty function) を導入する. ペナルティ項が十分大きければ, ペナルティ関数を最小化することによって問題が近似的に解けるわけである. 典型的なペナルティ関数の一つは

$F_\rho^{\rm P}(x) := f(x) + \rho_1 \max_i[0, g_i(x)]^2 + \rho_2 \|h(x)\|^2$

$(3)\,$

である. $\rho = (\rho_1,\rho_2)\,$ は正のパラメータでこれをペナルティパラメータと呼ぶ. 実際には, 大きな $\rho\,$ の値に対して $F_\rho^{\rm P}\,$ をいきなり最適化するのではなく, $\rho\,$ の値を徐々に大きくしながら $F_\rho^{\rm P}\,$ を無制約最適化するというステップを繰り返して問題を解く. $\rho\,$ が大きくなるにつれて $F_\rho^{\rm P}\,$ が悪条件になり無制約最適化が難しくなることが欠点とされる. 類似の方法で不等式制約を必ず満たすようにペナルティ項を付加したものは, 障壁関数法 (barrier function method)と呼ばれる.

　上に述べたペナルティ法の欠点を克服するために考えられたのが乗数法である [1, 3]. 乗数法は, 基本的には等式制約のみの問題を扱うための解法であり， $\rho\,$ の他にラグランジュ乗数(Lagrangian multiplier) $\zeta_i\,$ を導入して次のように定義される拡張ラグランジュ関数 (augumented Lagrangian function)

$F_{(\rho,\zeta)}^{\rm M}(x) := f(x) + \sum \zeta_j h_j(x) + \rho \|h(x)\|^2$

の無制約最適化を行って問題を解くものである. $\rho\,$ が十分大きく $\zeta\,$ が元の問題のKKT点におけるラグランジュ乗数である時には, KKT点は $F_{(\rho,\zeta)}^{\rm M}(x)\,$ の極小点になる. そこで， $\rho\,$ を十分に大きくとった上で, (i)適当な方法で $\zeta\,$ を推定し, (ii) $F_{(\rho,\zeta)}^{\rm M}(x)\,$ を無制約最適化する; という2つのステップを繰り返すことで, $\rho\,$ を更新することなく KKT点に収束する解法が得られる. 不等式制約 $g_i(x)\leq0\,$ を持つ問題に対しては, スラック変数 $s_i\,$ を導入して $g_i(x) + s_i^2 = 0\,$ として, 等式制約に直した上でこの方法を適用すればよい. 乗数法は70年代に研究された.

　次に 70年代後半から80年代に入って研究されたのが，逐次2次計画法である [2, 4, 6].逐次2次計画法では, 点 $x^k\,$ において, ラグランジュ関数 $L(x,\lambda,\zeta)\,$ を2次近似し, 制約条件を1次近似して得られる 2次計画問題

$\begin{array}{lll} \mbox{min}_x & \frac12 (x - x^k)^{\top} H^k (x-x^k) + (x-x^k)^{\top} \nabla f(x^k) & \\ \mbox{s. t.} & g_i(x^k) + (x - x^k)^{\top} \nabla g_i(x^k) \le 0 & (i=1,\ldots,m), \\ & h_j(x^k)+ (x-x^k)^{\top} \nabla h_j(x^k) = 0 & (j=1, \ldots, l), \end{array}$