《制約なし最適化》のソースを表示

'''【せいやくなしさいてきか (unconstrained optimization)】'''

　関数 <math>f:\mathbf{R}^n\to \mathbf{R}</math> が与えられたときに，<math>f(x)\,</math> を変数 <math>x \in \mathbf{R}^n</math> について最小化(もしくは最大化)する問題を[[制約なし最適化]] (unconstrained optimization) 問題という．ここで，<math>f(x)\,</math> を目的関数という．ある <math>x^*\in \mathbf{R}^n</math> に対して


:<math>f(x^*) \le f(x) \quad \forall \, x \in \mathbf{R}^n</math>   


が成り立つとき，<math>x^*\,</math> を最適解，あるいは大域的最適解という．また，ある <math>x^*\,</math> とその適当な近傍 <math>N(x^*)\,</math> に対して


:<math>f(x^*) \le f(x) \quad \forall x \in N(x^*)</math> 


が成り立つとき，<math>x^*\,</math> を局所的最適解という．<math>f(x)\,</math> が <math>x^*\,</math> で微分可能であるとき，<math>x^*\,</math> が局所的最適解ならば


:<math>\nabla f(x^*) = 0</math>   


が成り立ち，さらに2回微分可能ならば <math>\nabla^2f(x^*)</math> は半正定値行列になる．逆に，<math>\nabla f(x^*)=0</math> が成り立ち，かつ，<math>\nabla^2 f(x^*)</math> が正定値行列ならば，<math>x^*\,</math> は局所的最適解になる．こうした最適性条件に基づいて，多くの数値解法は停留点，すなわち <math>\nabla f(x)=0</math> を満たす点 <math>x^*\,</math> を見つけることを目指している．

　制約なし最適化問題を解くための数値解法は，目的関数値の情報だけを用いる直接探索法と微分の情報を用いる[[勾配法]] (gradient method) とに大別される[1, 3, 4, 5]．勾配法は反復法に分類されるもので，適当な初期点 <math>x_0\,</math> から出発して，<math>k\,</math> 回目の反復で近似解 <math>x_k\,</math> と探索方向 <math>d_k\,</math> が与えられたときに


:<math>x_{k+1} := x_k + d_k\,</math>   


によって点列 <math>\{x_k\}\,</math> を生成していくものである．このとき探索方向の決め方によっていろいろな数値解法が考えられる．探索方向を決めるために，目的関数を何らかの意味で近似したモデル関数を局所的に最小化することが考えられている．モデル関数として，1次モデルと2次モデル


:<math>\begin{array}{lll}  
f(x_k+d) &\approx& f(x_k)+\nabla f(x_k)^{\top}d,   \\
\\
f(x_k+d) &\approx& f(x_k)+\nabla f(x_k)^{\top}d
     +\frac{1}{2}d^{\top}\nabla^2f(x_k)d   
\end{array}</math>


がよく用いられる．1次モデル最小化に基づいた解法として[[最急降下法]] (steepest descent method) がある．この方法は探索方向を <math>d_k :=-\nabla f(x_k)</math> に選ぶものである．他方，2次モデル最小化に基づいた解法には，[[ニュートン法]] (Newton's method)，[[準ニュートン法]] (quasi-Newton method)，[[共役勾配法]] (conjugate gradient method)などがある．ニュートン法は連立1次方程式


:<math>\nabla^2f(x_k)d_k=-\nabla f(x_k)</math>   


を解いて探索方向<math>d_k\,</math>を決定する．また，準ニュートン法はヘッセ行列を行列 <math>B_k\in \mathbf{R}^{n\times n}</math> で近似して，連立1次方程式


:<math>B_kd_k=-\nabla f(x_k)</math> 


を解いて探索方向<math>d_k\,</math>を決定する．その際，勾配ベクトル <math>\nabla f(x)\,</math> の情報を含んだ更新公式を利用して <math>B_k\,</math> を逐次生成していくのが特徴である．いろいろな更新公式が提案されているが，特にBroyden-Fletcher-Goldfarb-Shanno (BFGS) 公式が有効であることが認められている．共役勾配法はこれらとは異なった立場の解法で，探索方向は


:<math>d_k := -\nabla f(x_k) + \beta_kd_{k-1} \qquad
(\beta_k\in \mathbf{R}</math>は適当なパラメータ<math>)\,</math>


で定義される．<math>\beta_k\,</math> の選び方として Fletcher-Reeves公式やPolak-Ribi&eacute;re-Polyak公式がある．ここで，ニュートン法が2階偏導関数を用いているのに対して，準ニュートン法や共役勾配法は1階偏導関数しか利用しないことに注意されたい．

　数値解法の有効性を特徴づける指標として局所的な収束の速さの尺度である[[収束率]] (rate of convergence) と初期点の選び方によらず停留点への収束を保証する[[大域的収束性]] (global convergence) がある．収束率の観点からみれば，最急降下法は高々1次収束しかしない方法，ニュートン法は2次収束する方法，BFGS公式を用いた準ニュートン法は超1次収束する方法であるといえる．実用的には，超1次収束や2次収束する方法であることが望ましい．他方，大域的収束性はそのままでは達成出来ないので，何らかの補助手段を必要とする．代表的な手段として[[直線探索(数理計画における)]] (line search) と[[信頼領域法]] (trust region method) がある．直線探索は，探索方向 <math>d_k\,</math> が与えられたときに，その方向でステップ幅 <math>\alpha_k\,</math> を調節して関数の減少 <math>f(x_k+\alpha_kd_k)<f(x_k)\,</math> を実現し，<math>x_{k+1} :=x_k+\alpha_kd_k\,</math> とおく．直線探索の枠組みで，最急降下法，準ニュートン法，共役勾配法の大域的収束性が示されている．それに対して信頼領域法は，2次モデルによる近似が妥当であると思われる領域で2次モデルを最小化するステップ <math>s_k\,</math> を選んで <math>x_{k+1} :=x_k+s_k\,</math> とする解法である．2次モデルでヘッセ行列を用いた場合(ニュートン法に対応する)やその近似行列を用いた場合(準ニュートン法に対応する)の信頼領域法の大域的収束性が示されている．

　実際の応用では，目的関数値を単調に減少させることを緩和した非単調アルゴリズムや，ニュートン法において連立1次方程式を厳密には解かない非厳密ニュートン法などが効率的であることが知られている．また，大規模問題を解くためには，共役勾配法，ヘッセ行列のスパース構造を用いた信頼領域法，ベクトルの形でヘッセ行列の情報を更新する記憶制限付き準ニュートン法などが利用されている．なお，実際の数値計算では，導関数を解析的に与える代わりに，有限差分近似や自動微分を利用することも試みられている．

　以上では微分可能な関数の最小化問題の数値解法を取り上げたが，実際には，目的関数が必ずしも滑らかであるとは限らない．こうした関数を最小化(もしくは最大化)する問題を[[微分不可能最適化]] (nondifferentiable optimization) 問題といい，滑らかな関数を最小化する問題よりも解くのが難しくなる．目的関数 <math>f(x)\,</math> に凸性などの仮定をすれば，最適性条件は次式で与えられる．


:<math>0 \in \partial f(x) \qquad (\partial f(x)</math> は劣勾配の集合を表す<math>)\,</math>


この条件を満たす点を見つけるためには，前述した数値解法がそのままでは使えないので，何らかの工夫をしなければならない．目的関数の劣勾配を利用したりヘッセ行列の代用品を利用することが考えられており，たとえば，バンドル法や[[一般化ニュートン法]] (generalized Newton method) などがある[2, 3]．



----
'''参考文献'''

[1] J.E.Dennis, Jr. and R.B.Schnabel, ''Numerical Methods for Unconstrained Optimization and Nonlinear Equations'', SIAM, 1996.

[2] J.-B. Hiriart-Urruty and C.Lemar&eacute;chal, ''Convex Analysis and Minimization Algorithms (I and II)'', Springer, 1993.

[3] 伊理正夫，今野浩，刀根薫監訳，『最適化ハンドブック』，朝倉書店, 1995.

[4] 今野浩，山下浩,『非線形計画法』, 日科技連, 1978.

[5] 矢部博，八巻直一,『非線形計画法』, 朝倉書店, 1999.