\underline{最適化問題第 1 章はじめに 1}

第1章はじめに

非線形最適化モデルは, 典型的に 2 つの問題に定式化される.

制約なし最適化問題 n 実変数 x_{1}, x_{2}, ⋯, x_{n} の非線形実数値関数 f(x) の最小値を与える x を求める問題. ただし x は第 i 要素を x_{i} とする n 項列ベクトルである.

制約つき最適化問題方程式 g_{1}(x) = 0, ⋯, g_{r}(x) = 0 および不等式 g_{r+1} ≥ 0, ⋯, g_{m} ≥ 0 で実現される制約条件下で, 非線形目的関数 f(x) の最小値を与える n 次元列ベクトル n を求める問題.

非線形最適化問題を有限回の四則演算で解くことは, 一般的にはできない. 最適化法のアルゴリズムは逐次近似 (反復) 解法の形を取る. すなわち, 適当な初期近似解 x_{0} から出発して, 反復公式,

x_{k+1} = x_{k} + α_{k}d_{k}  (1.1)

によって最適解 x^{∗} に収束する点列 x_{k} を生成する. ここで α_{k} は「ステップ幅」 , x_{k} は「探索方向」と呼ばれる. この両者をどう選ぶかによってアルゴリズムが決まる. とりわけ探索方向 d_{k} の選び方がその性能を左右する. 最適解において極小値を取り, 探索方向がその降下方向 (すなわち d_{k}^{T} M(x) < 0) となるような評価関数 M(x) を構成し, 反復の段階ではこの関数を減少させるようにする. すなわち,

M(x_{k+1}) < M(x_{k})  (1.2)

となるようにする. 制約なし最適化問題では評価関数として目的関数自体が, 制約つき最適化問題では評価関数として罰金関数や罰金付き Lagrange 関数がよく用いられる.

この文章では非線形の最適化問題の数学的構造に関してまとめる. 最適化問題の解法アルゴリズムについては W. C. Davidson (1959) の可変計量法以来, 数多くのアルゴリズムが提案されてきた. その中でもギブス自由エネルギーを最小化する平衡熱力学計算に良く利用される Newton 法をここでは取り上げる. 制約なし最適化問題として Newton 法と準 Newton 法を, 制約つき最適化問題のとして Newton 法を紹介する.

\underline{最適化問題第 2 章制約なし最適化問題 2}

第2章制約なし最適化問題

滑らかな実数値関数 f(x) の最小値を与える x を求める問題を考える. この問題を解くための反復解法 (1.1) 式において, 探索ベクトル d_{k} は,

d_{k} ≡ −H_{k}^{−1}∇f(x)  (2.1)

という形式を取ることが多い. ここで H はヘッセ (Hesse) 行列と呼ばれ, 例えば最急降下法では H ≡ I (単位行列) であり, Newton 法では H ≡ ∇^{2}f(x) である.

本章では制約なし最適化問題として, ギブス自由エネルギーを最小化するという平衡熱力学計算に良く用いられる Newton 法, 準 Newton 法を解説する.

2.1 Newton 法

制約なしの最適化解は, 停留点を定義する連立非線形方程式

∇f(x) = 0  (2.2)

を満たす. この関係式を用いることで Newton 法の探索方向を決める.

目的関数 f(x) を近似解 x_{k} のまわりでテーラー展開し, 2 次の微小量まで考慮した 2 次近似関数を Q とすると, 近似関数 Q は,

Q = f(x_{k}) + ∇f(x_{k})(x − x_{k}) + \frac{1}{2}∇^{2}f(x_{k})(x − x_{k})^{2}  (2.3)

と書ける. ただし, ∇ = ∂/∂x_{k} である. (2.3) 式の x 微分をとると (x_{k} 微分でないことに注意),

\frac{dQ}{dx} = \frac{d}{dx} f(x_{k}) + ∇f(x_{k}) · \frac{d}{dx} (x − x_{k}) + \frac{1}{2}∇^{2}f(x_{k}) · \frac{d}{dx} (x − x_{k})^{2}
= ∇f(x_{k}) + ∇^{2}f(x_{k}) · (x − x_{k})  (2.4)

となる. (2.4) 式を停留点の条件 (2.2) 式に代入することで,

∇f(x_{k}) + ∇^{2}f(x_{k})d_{k} = 0  (2.5)

が得られる. ただし (2.4) において x − x_{k} を探索方向 d_{k} とみなした.

Newton 法では, (2.5) 式より探索方向を決め, ステップ幅を常に α_{k} ≡ 1 にすることによって, 最適解 x^{∗} に収束させる. (2.5) の定式化からわかるように, この探索方向は目的関数を変数 x に関する 2 階の方程式に近似し, その停留点により目的関数の最小値を求める方法といえる.

図 2.1: Newton 法が生成する点列の意味

2.2 準 Newton 法

(2.5) 式の ∇^{2}f(x_{k}) の直接計算は手間がかかるため, 1959 年に W. C. Davidon は ∇^{2}f(x_{k}) を直接計算せずに済む「可変計量法」を開発した. 現在ではその変種が数多くしられており, それらは総称して「準 Newton 法」と呼ばれている. この方法群においては, {x_{k}}, {∇f(x_{k})} の情報を用いて ∇^{2}f(x_{k}) の近似行列の系列 {H_{k}} を構成して ∇^{2}f(x_{k}) に代用する.

2 つのベクトルを s_{k} ≡ x_{k+1} − x_{k}, y_{k} ≡ ∇f(x_{k+1}) − ∇f(x_{k}) と定義するとき, 近似的に ∇^{2}f(x)s_{k} ≈ y_{k} が成り立つ. そこで s_{k} と y_{k} の対が得られるたびに, セカント条件,

H_{k+1}s_{k} = y_{k}  (2.6)

を満たすように, 近似行列を H_{k+1} = H_{k} + ΔH_{k} の形式によって逐次近似していくと, 系列 {H_{k}} はある意味で ∇^{2}f(x_{k}) の近似になることが期待できる. そこで x_{0}, H_{0} を決め, (2.1) 式によって探索方向 d_{0} を決め, x_{1} を生成し, (2.6) 式に基づいて H_{1} を更新する. これを反復して点列 {x_{k}} を生成する. ステップ幅の決定は Wolfe の条件,

f(x + αd_{k}) − f(x_{k}) ≤ σ_{1}α(∇f(x_{k}))^{T} d_{k}  (2.7)
(∇f(x + αd_{k}))^{T} d_{k} ≤ σ_{2}(∇f(x_{k}))^{T} d_{k}  (2.8)

によって行う. ただし, 準 Newton 法においては, この条件が極端に緩くなるようにこの定数 σ_{1}, σ_{2} を選択すると, 総合性能が良くなることが経験的に知られている. 典型的には σ_{1} ≡ 10^{−4}, σ_{2} ≡ 0.9, さらに H_{0} として単位行列が選ばれることが多い.

今日, 経験的にも理論的にも最も優れているとされている準 Newton 法は, C. G. Broyden, R. Fletcher, D. Goldfalb, D. F. Shanno による BFGS 公式,

H_{k+1} = H_{k} − \frac{H_{k}s_{k}s_{k}^{T} H_{k}}{s_{k}^{T} H_{k}s_{k}} + \begin{matrix}y & k & y & T k \\ s & T k & y & k \end{matrix}  (2.9)

に基づくものである.

準 Newton 法は制約のない最適化問題の中で最もよく使われる方法であるが, 行列 H_{k} のために大きな記憶領域を必要とする点に適用上の限界がある. 90 年代以降の最適化法による平衡熱力学計算においては, 準 Newton 法が最も良く利用されている.

\underline{最適化問題第 3 章制約つき最適化問題 4}

第3章制約つき最適化問題

本章では,

g_{1}(x) = 0, ⋯, g_{r}(x) = 0  (3.1)
g_{r+1}(x) ≥ 0, ⋯, g_{m}(x) ≥ 0  (3.2)

という条件下で, 目的関数 f(x) を最小化する問題を考える.

3.1 Newton 法

g(x) = (g_{1}(x) = 0, ⋯, g_{r}(x))^{T} = 0 という等式制約のみの場合を考える. このとき, 制約想定下で最適解 x^{∗} に対して λ^{∗} が存在し, これらは Karush-Kuhn-Tucker 条件, すなわち変数 x, λ に連立非線形方程式,

∇_{x}L(x, λ) = ∇_{x}f(x) − (J(x))^{T} λ = 0  (3.3)
∇_{λ}L(x, λ) = g(x) = 0  (3.4)

を満たす. ただし λ は未定乗数, L(x, λ) ≡ f(x) − ∑ λ_{j}g_{j}(x) とし, Jacobi 行列は J(x) ≡ ∇g(x) とする. この Karush-Kuhn-Tucker 条件はラグランジュの未定乗数法の条件と同じものである. 制約つき最適化法は究極的にはこの方程式を解かねばならないと言える.

Newton 法を (3.3), (3.4) 式から成る連立方程式に適用すること考える. (3.3), (3.4) 式より L を目的関数とみなせばよいことがわかる. ただし制約なしの最適化問題では目的関数を x に関する 2 次方程式に近似するだけでよかったが, 制約つき最適化問題では x と λ について停留点を求めるので, 目的関数を x と λ で展開せねばならない. まず目的関数 L を x_{k} の近傍でテーラー展開し, 2 次の微小量まで考慮する. そのようにして求めた L(x, λ) の近似関数を Q とすると,

Q = f(x_{k}) + ∇f(x_{k}) · (x − x_{k}) + \frac{1}{2}∇^{2}f(x_{k}) · (x − x_{k})^{2}
−λg(x_{k}) − λ_{j}∇g(x_{k}) · (x − x_{k}) − \frac{1}{2}λ_{j}∇^{2}g(x_{k}) · (x − x_{k})^{2}  (3.5)

となる. さらに Q を λ_{k} の近傍でテーラー展開すれば,

Q = f(x_{k}) + ∇f(x_{k}) · (x − x_{k}) + \frac{1}{2}∇^{2}f(x_{k}) · (x − x_{k})^{2}
−λ_{k}g(x_{k}) − g(x_{k}) · (λ − λ_{k})
−λ_{k}∇g(x_{k}) · (x − x_{k}) − ∇g(x_{k}) · (x − x_{k}) · (λ − λ_{k})
−\frac{1}{2}λ_{k}∇^{2}g(x_{k}) · (x − x_{k})^{2} − \frac{1}{2}∇^{2}g(x_{k}) · (x − x_{k})^{2} · (λ − λ_{k})  (3.6)

となる. この近似関数 Q を x について微分すれば,

∇_{x}Q = ∇f(x_{k}) + ∇^{2}f(x_{k}) · (x − x_{k}) − λ∇g(x_{k}) − λ∇^{2}g(x_{k}) · (x − x_{k})
= {∇^{2}f(x_{k}) − λ∇^{2}g(x_{k})} (x − x_{k}) + ∇f(x_{k}) − λ∇g(x_{k})  (3.7)

となるので, 停留点の条件を用いると,

{∇^{2}f(x_{k}) − λ∇^{2}g(x_{k})} (x − x_{k}) + ∇f(x_{k}) − λ∇g(x_{k}) = 0
H(x_{k}, λ)d_{k} − J(x_{k})λ = −∇f(x_{k})  (3.8)

である. ただし,

H(x, λ) = ∇^{2}L(x, λ) = ∇^{2}f(x_{k}) − λ∇^{2}g(x_{k})  (3.9)

という置き換えをおこなった. 同様に近似関数 Q を λ 微分すると,

∇_{λ}Q = −g(x_{k}) − ∇g(x_{k}) · (x − x_{k}) − \frac{1}{2}∇^{2}g(x_{k}) · (x − x_{k})^{2}  (3.10)

となり, 停留点の条件を用いると,

−g(x_{k}) − ∇g(x_{k}) · (x − x_{k}) = 0
J(x_{k})d_{k} = −g(x_{k})  (3.11)

が得られる. ここで d_{k}^{2} の項を微小量とみなして無視した.

(3.8) と (3.11) 式より, Newton 法を (3.3), (3.4) 式から成る連立方程式に適用することで次のアルゴリズムが得られる. 探索方向 d_{k} を連立一次方程式,

[ \begin{matrix}H(x_{k}, λ_{k}) & −J^{T} (x_{k}) \\ J(x_{k}) & 0 \end{matrix} ] [ \begin{matrix}d & k \\ λ & k+1 \end{matrix} ] = − [ \begin{matrix}∇_{x}f(x_{k}) \\ g(x_{k}) \end{matrix} ]

によって定め, (1.1) 式においてステップ幅を常に α = 1 にとって点列 {x_{k}}, {λ_{k}} を生成する. λ_{k+1} は連立方程式の解として直接得られることに注意を払う必要がある^{1}.

この方法は, 一般に収束域が狭く, 初期値 x_{0} の選び方によっては発散したり, 解とは異なる Karush-Kuhn-Tucker 点に収束する可能性がある.

1H = H(x_{k}, λ_{k+1}) とならずに H = H(x_{k}, λ_{k}) となる理由は?

\overline{main.tex 2004/06/05(杉山耕一朗)}

\underline{最適化問題第 4 章参考文献 6}

第4章参考文献

藤田宏, 今野浩, 田辺國士, 著:

「最適化法」 , 岩波講座応用数学方法 7, 岩波書店, 1994.

田中正次, 二宮市三, 鳥居達生, 長谷川武光, 秦野和郎, 秦野, 吉田年雄, 刀根薫, 古林隆, 細野俊夫, 著: 「SSL II 使用手引書」 , 富士通株式会社, 1987.