第3章 非線形計画法の基礎

. . . .

第

3

章 非線形計画法の基礎

畔上 秀幸

名古屋大学 情報科学研究科 複雑系科学専攻

. . . .

§

1

はじめに

目標 有限次元ベクトル空間の非線形最適化問題の勾配を利用して最適解 を求めるアルゴリズムについて理解する． 制約なし最適化問題に対して，勾配が評価できていれば，勾配法で設 計変数の変動方向を決めることができる． ステップサイズはArmijoの規準とWolfeの規準を満たすように決定 することで，大域的収束性が保障される． Newton法は2次収束するが，一般に収束域が狭い．修正Newton 法は大域的収束性を持つ． 制約付最適化問題はLagrange乗数形式に修正Newton法を適用し た逐次2次計画法（SQP法）により，制約を満たす設計変数の変動 を決めることができる．

. . . .

§

2

非線形計画法の一般形

第1章で定義した，制約なし問題を考えよう． .

問題

2.1 (

制約なし問題

)

. . . 空ではない部分集合 S ⊂ Rn_{(n∈ N)上で連続微分可能な非線形関数} f (x) : Rn3 x 7→ f ∈ R が与えられたとき，次のような x?∈ S を求めよ． f (x?)= min x∈S ⊂Rnf (x)  目的関数あるいは制約関数の一部が非線形な最適化問題の解を求める アルゴリズムを非線形計画法(nonlinear programming)という．非線形 計画法では，初期値x0_{∈ S から始めて，k = 0, 1, 2, · · · として，探索方} 向hk_{∈ R}n_{とステップサイズ}k_{> 0}(_k_{∈ R})_{を求めて，次式によって設} 計変数を更新していくアルゴリズムが用いられる． xk+1= xk+ khk

. . . .

アルゴリズムの収束性

最適解 x?∈ S から離れていても収束することを大域的収束性と いう． 最適解 x?∈ S と xk_{(k= 0, 1, 2, · · · ) について次式を満たすとき，} xk+1− x? <rk xk− x? p pを収束次数(convergence order)という．また，{rk} kが 0 に収束 するとき，超 p 次収束という．

. . . .

§

3

制約なし問題

問題2.1に対して，勾配法を次のように定義する． .

定義

3.1 (

勾配法

)

. . . ある正定値対称行列 Hk_{∈ R}n×n_{とする．すなわち，H は次の条件を満} たす． ∃α > 0 : x · Hk_{x≥ α kxk}2 _{∀x ∈ R}n 問題2.1の xk_{∈ S における勾配 ∇ f}(_xk)_{∈ R}n_{とする．このとき，探索} 方向hk∈ Rnを次式で決定する方法を勾配法(gradient method)という． hk= −(Hk)−1∇ f(xk) or hk· Hky= −∇ f(xk)· y ∀y ∈ Rn  (3.1)

. . . . .

定理

3.1 (

勾配法

)

. . . 問題2.1における関数 f (x) の xk_{∈ S における勾配 ∇ f}(_xk)_{∈ R}n_を既知 とする．ある正定値対称行列 H∈ Rn_{×nを用いて，式(3.1)を満たす} hk∈ Rnは関数 f (x) の xk_{における降下方向である．} 証明 次の関係が成り立つ． f(xk+ hk)− f(xk)= ∇ f(xk)· hk+ o() = −hk· Hhk+ o() ≤ −α hk 2+ o()

. . . . .

定義

3.2 (

降下方向

)

. . . 問題2.1の xk_{∈ S における勾配 ∇ f}(_xk)_{∈ R}n_{とする．このとき次式の} θ ∈ [−π, π] を降下方向という． cosθ = − ∇ f ( xk)· hk hk ∇_f(_xk)  (3.2) .

定義

3.3 (

最急降下法

)

. . . 定義3.1の勾配法において，正定値対称行列 H∈ Rn×n_{= I(Iは単位行} 列)のとき，最急降下法という．すなわち，探索方向hk_{∈ R}n_を次式で 決定する． hk= −∇ f(xk) or hk· y = −∇ f(xk)· y ∀y ∈ Rn 

. . . .

Armijo

の規準

ステップサイズの上限条件として，Armijoの規準が知られている． .

定義

3.4 (Armijo

の規準

)

. . . 問題2.1の xk_{∈ S における勾配を ∇ f}(_xk)_{∈ R}n_{，探索方向を h}k_{∈ R}n とする次式を満たすα > 0 に対して 0 <  < α となるように  ∈ R を決

定する方法をArmijoの規準(Armijo criterion)という．ただし，

ξ ∈ (0, 1) とする． f(xk+ hk)− f(xk)≤ ξ∇ f(xk)·(αhk) 

f(x

k

₎

f(x

k

₊

_α

_h

k

_)−f(x

k

₎

²

α

∇

_f(x

k

_)∙(

_α

_h

k

₎

0

. . . . 特に， f (x) が2次関数のとき，ξ = 1/2 を用いたときの  の上限 α が 最小解 x?= xk_{+ αh}k_{となる．実際，α に対して次式が成り立つ．} ∇ f(xk+ αhk)= ∇ f(xk)+ ∇∇Tf(xk) (αhk)= 0 ∴ f(xk+ αhk)− f(xk)= ∇ f(xk)·(αhk)+1 2 ( αhk)_{· ∇∇}T_f(_xk) (_αhk) =1 2∇ f ( xk)·(αhk)= ξ∇ f(xk)·(αhk)

f(x

k

₎

∇

_f(x

k

_)∙(

_α

_h

k

₎

1

2

0

α

²

. . . .

Wolfe

の規準

ステップサイズの下限条件として，Wolfeの規準が知られている． .

定義

3.5 (Wolfe

の規準

)

. . . 問題2.1の xk_{∈ S における勾配を ∇ f}(_xk)_{∈ R}n_{，探索方向を h}k_{∈ R}n とする．次式を満たすα > 0 に対して α <  となるように  ∈ R を決定

する方法をWolfeの規準(Wolfe criterion)という．ただし，Armijoの規

準で用いたξ ∈ (0, 1) に対して， ξ ∈ (0, 1) 0 < ξ < µ < 1 とする． µ∇ f(xk)·(αhk)≤ ∇ f(xk+ hk)·(αhk)  (3.3)

f(x

k

₎

∇

_f(x

k

_)∙(

_α

_h

k

₎

0

∇

_f(x

k

₊

_α

_h

k

_)∙(

_α

_h

k

₎

²

α

. . . .

大域的収束定理

.

定理

3.2 (

大域的収束定理

)

. . . 問題2.1の f (x) が下界を持ち，水準集合 L={x∈ Rn_{| f (x) ≤ f (x}0₎}_の 近傍 U で連続微分可能，∇ f (x) が U でLipschitz連続のとき，探索方向 hk_{が降下方向であり，ステップサイズ がArmijoの規準とWolfeの規} 準を満たすならば，反復公式で生成される近似解の点列{xk} kに対して 次式が成り立つ．ただし，θk_{は式(3.2)で定義する．} ∞ ∑ k=1 ∇ f(xk) 2 cos2θk< ∞  (3.4) 証明 文献[1]定理4.1参照

. . . . もしも，探索方向 hk_{が最急降下方向−∇ f}(_xk)_{と直角に交わる方向に} 漸近することがないならば，次の関係が成り立つ． cosθk> 0 and ∞ ∑ k₌₁ ∇ f(xk) 2cos2θk< ∞ ⇒ lim k→∞∇ f ( xk)= 0

. . . .

Newton

法

次の関係を使ってNewton法を定義する． ∇ f(xk+ hk)= ∇ f(xk)+ ∇∇Tf(xk)hk= 0 .

定義

3.6 (Newton

法

)

. . . 問題2.1の xk_{∈ S における勾配を ∇ f}(_xk)_{∈ R}n_{，Hesse行列を} H(xk)= ∇∇Tf(xk)∈ Rn×nとする．このとき，探索方向hk∈ Rnを次式 で決定し，ステップサイズ = 1 とする方法をNewton法(Newton method)という． hk= −H−1(xk)∇ f(xk) or hk· H(xk)y= −∇ f(xk)· y ∀y ∈ Rn  (3.5)

. . . . .

定理

3.3 (Newton

法

)

. . . 問題2.1における関数 f (x) が2回連続微分可能で，Hesse行列 H(x)= ∇∇T_{f (x)∈ R}n×n_{が最適解 a∈ S で正則， a の近傍 x でLipschiz} 連続 (∃C ≥ 0 : kH(a) − H(x)k ≤ C ka − xk) のとき，a に十分近い初期値 から出発して，Newton法で生成された点列{xk} kは a に2次収束する．  証明 文献[1]定理4.2参照 .

注意

3.1 (Newton

法

)

. . . Newton法は，一般に収束域が狭く，初期値の選び方によって発散 したり，極大点に収束する可能性がある． Hesse行列∇∇T_{f (x)∈ R}n_{×nが特異行列や悪条件になることもある．} 式(3.1)と(3.5)の比較から，勾配法は，Hesse行列の代わりにあ る正定値対称行列を用いた方法になっている．このことから，勾配 法は，修正Newton法とみなすことができる．

. . . .

参考： 準

Newton

法，共役方向法

.

定義

3.7 (

準

Newton

法

)

. . . 探索ベクトルがNewton法の探索ベクトルに漸近する解法を総称して準

Newton法(quasi-Newton method)という．

BFGS (Broyden-Fletcher-Goldfalb-Shanno)公式 DFP (Davidon-Fletcher-Powell)公式 .

定義

3.8 (

共役方向法

)

. . . 正定値対称行列 A に対して，ベクトル x,yが x· Ay = 0 のとき， x,y は共役であるという．A= ∇∇T_f(_xk)_{として，探索方向 h}k_{を，例えば次}

式で計算する方法を，共役方向法(conjugate direction method)と呼ぶ．

hk= −∇ f(xk)+ αk−1hk−1 α0= 1, αk=

∇ f(xk)_·(_{∇ f}(_xk)_{− ∇ f}(_xk−1))

. . . .

§

4

制約付問題

第1章で定義した，不等式制約付問題を考えよう． .

問題

4.1 (

不等式制約問題

)

. . . 連続微分可能な非線形関数 f : Rn_{7→ R と g}(l)_{: R}n_{7→ R (l = 1, 2, · · · , m),} g=(g(l)) l∈ R m_{が与えられたとき，次のような x}?_{∈ R}n_{を求めよ．} f (x?)= min x_∈Rn{ f (x) | g(x) ≤ 0} 

. . . .

参考： 拡大関数法

.

定義

4.1 (

拡大関数法

)

. . . 制約付最適化問題を制約なしの問題に置き換えて解く方法を拡大関数法 という．次の定義は例である．

障壁関数法(barrier function method)，内点法(inner point method)

Pk(x, ρk)= f (x) − ρkmax_0, m ∑ l=1 log(−g(l)(x))_ ただし，{ρk} kは適当に選んだ単調減少数列とする．

罰金関数法(penalty function method)，外点法(outer point method)

Pk(x, ρk)= f (x) + ρk m ∑ l=1 max{0, g(l)(x)} ただし，{ρk} kは適当に選んだ∞ に発散する単調増加数列とする．

. . . .

Lagrange

問題の

Newton

法

.

定義

4.2 (Lagrange

問題の

Newton

法

)

. . . 問題4.1の xk_{∈ S におけるLagrange乗数形式 L}(_xk_{, λ})_{を次式で定義す} る．ただし， g(x)={g(l)_(x)} l∈ R m_{,λ =}{_λ(l)} l∈ R m_と表す． L(xk, λ)= f(xk)+ λ · g(xk) L(x, λ) の x に対する勾配を ∇L(x, λ) ∈ Rn，Hesse行列を HL(x, λ) = ∇∇TL(x, λ) ∈ Rn×nと表す．このとき，移動後にすべての制 約がアクティブ g(xk)+(∇gT(xk))Th= 0 であると仮定して，探索方向 hk∈ Rnを次式で決定し， = 1 とする方法をLagrange問題のNewton 法(Newton method)と呼ぶ．    HL ( xk, λ) ∇gT(xk) ( ∇gT(_xk))T ₀    ( hk λ ) = −   ∇ f ( xk) g(xk)     (4.1)

. . . . .

注意

4.1 (Lagrange

問題の

Newton

法

)

. . . 問題4.1における関数 f (x), g (x)が2回連続微分可能，最適解 (a, µ) ∈ S × Rm_{においてHesse行列 H} L(x, λ) が正則，かつ制約の 正則条件(第1章 定義3.2)が成り立ち，最適解の近傍 (x, λ) で Lipschiz連続のとき，(a, µ) に十分近い初期値から出発して， Lagrange問題のNewton法で生成された点列{(xk, λ)} kは (a, µ) に 2次収束する． 式(4.1)の解λ において，アクティブな制約の添字集合 IA(xk+1)={l∈ {1, 2, · · · , m}  λ(l)≥ 0}の制約を残して，式(4.1)を解 き直すことで，問題4.1の制約を満たす移動ベクトル hk_を求める ことができる． 注意3.1の性質がここでも成り立つ．

. . . .

逐次

2

次計画法

.

問題

4.2 (

逐次

2

次計画問題

)

. . . 問題4.1の xk_{∈ S における f}(_xk)_,∇gT(_xk)_{とする．また，ある正定値} 対称行列を Hk_{∈ R}n×n_{とする．このとき，次の問題の最適解s∈ R}n_を 求めよ． Q (s) = min h∈Rn { Q (h) = 1 2h · ( 1 H k ) (h) + ∇ f(xk)· (h) } s.t. g(xk)+(∇gT(xk))T(h) ≤ 0  .

定義

4.3 (

逐次

2

次計画法

)

. . . 問題4.1に対して，問題4.2の解s を移動ベクトルhk_{∈ R}n_をして， 反復公式で近似解の点列{xk} kを求める方法を逐次2次計画法

(sequential quadratic programming)あるいはSQP法と呼ぶ．ただし，

 は Q (h) に関して，Armijoの規準とWolfeの規準を満たすように決定

. . . . .

注意

4.2 (

逐次

2

次計画法

)

. . . 問題4.3において，すべての制約がアクティブ g(xk)+(∇gT(xk))T(h) = 0 であると仮定すれば， s = hk_は，式 (4.1)に対応する次式を満たす．    1 Hk ∇gT ( xk) ( ∇gT(_xk))T ₀    ( hk λ ) = −   ∇ f ( xk) g(xk)    (4.2) 式(4.1)との違いは，Hk_{がHesse行列ではなく正定値対称行列で} あることと， がArmijoとWolfeの規準を満たすように決定でき ることである．これらのことは大域的収束性を保証する． 問題4.1における関数 f (x), g (x)が連続微分可能，xk_{∈ S におい} て制約の正則条件(第1章 定義3.2)が満たされれば，式(4.2)は ( hk_{, λ})_{について解くことができる．}

. . . . . . もしも，目的関数 f (x)と制約関数g(l)(x) (l= 1, 2, · · · , m)に対して， 制約なし問題に対するHkを用いた勾配法により，それぞれの降下方向 h(0)k,h(l)k(l= 1, 2, · · · , m)が既知となっていれば，次式が成り立つ． hk= h(0)k+ m ∑ l=1 λ(l)_h(l)k _(4.3) h(0)k= −(Hk)−1∇ f(xk), h(l)k= −(Hk)−1∇g(l)(xk) (4.4) この関係を式(4.2)に代入すれば，第1式は満たされ，第2式は次式と なる．     ∇g(1)(_xk)_·(_h(1)k) _{· · · ∇g}(1)(_xk)_·(_h(m)k) ... ... ... ∇g(m)(_xk)_·(_h(1)k) _{· · · ∇g}(m)(_xk)_·(_h(m)k)         λ(1) ... λ(m)     = −     g(1)(xk)+ ∇g(1)(xk)·(h(0)k) ... g(m)(xk)+ ∇g(m)(xk)·(h(0)k)     (4.5) この式は，λ ∈ Rm_{を決定する連立1次方程式となる．}

. . . . 問題4.3において，制約 g(xk)₊(_∇gT(_xk))T_{(h) ≤ 0 に対するKKT} 条件（第1章定義3.4）は，式(4.2)の第2式を書き換えて，次式 となる． g(xk)+(∇g(1)T(xk))T   h(0)k+ m ∑ l=1 λ(l)_h(l)k    ≤ 0 (4.6) λ ·_g(xk)+(∇g(1)T(xk))T   h(0)k+ m ∑ l=1 λ(1)_h(l)k   _{ = 0} (4.7) λ ≥ 0 (4.8) したがって，式(4.5)でλ を解いて，式(4.6)から(4.8)を満たすア クティブな制約の添字集合 IA(xk+1)の制約を残して，式(4.5)を解 き直すことで，問題4.1の制約を満たす移動ベクトルhk_を求める ことができる．

. . . .

逐次

2

次計画法のアルゴリズム例

. . . アルゴリズム4.1 (逐次2次計画問題) . . . .

.

. 1 _k= 0_{とする．x}0∈ S_,_{を定める．} .

.

. 2 _f(_xk)_,g(_xk)_{を計算し，収束判定する．} 収束条件を満たしたとき，計算を終了する． 収束条件を満たさないとき，∇ f(xk)_,∇gT(_xk)_{を計算する．} .

.

. 3 _{ある正定値対称行列H}k_{∈ R}n×n_{を定めて，式(3.1)でh}k_{= h}(l)k_{とみなして} h(l)k_{(l= 0, 1, 2, · · · , m)を計算する．} .

.

. 4 _式(4.5)でλ_{を計算する．} 式(4.6)から(4.8)を満たすとき，次に進む． 式(4.6)から(4.8)を満たさないとき，式(4.6)から(4.8)が満たされるまで， アクティブな制約の添字集合IA(xk+1_{)の制約を残して，式(4.5)を解き直す．} .

.

. 5 _式(4.3)のhk_{を用いて，Armijoの規準と，必要に応じて，Wolfeの規準を} チェックする． 式(3.3)と(3.4)において，f(xk)_をL(_xk_{, λ})_{に置き換えた関係が成立すれば，} 次に進む．ただし，ξ, µ ∈ (0, 1) (ξ < µ)は定めておく． Armijoの規準が成立しなければ，を/2に置き換え，Wolfeの規準が成立し なければArmijoの規準を満たす範囲でを更新して，4に戻る． .

.

. 6 _k+ 1_{をkと置き換えて，2に戻る．}

. . . .

§

5

まとめ

有限次元ベクトル空間の非線形最適化問題の勾配を利用して最適解を 求めるアルゴリズムについて確認した． 制約なし最適化問題に対して，勾配が評価できていれば，勾配法で 設計変数の変動方向を決めることができる． ステップサイズはArmijoの規準とWolfeの規準を満たすように決 定することで，大域的収束性が保障される． Newton法は2次収束するが，一般に収束域が狭い．修正Newton 法は大域的収束性を持つ． 制約付最適化問題はLagrange乗数形式に修正Newton法を適用し た逐次2次計画法（SQP法）により，制約を満たす設計変数の変 動を決めることができる．

. . . .

参考文献

[1] 藤田宏,今野浩,田邉國士. 最適化法. 岩波書店. [2] 矢部博. 工学基礎:最適化とその応用. 数理工学社. [3] 田村明久,村松正和. 最適化法. 共立出版, 2002.

[4] G.L. Nemhauser, A.H.G. Rinnooy Kan, and M.J. Todd, editors.

[5] 山川 宏編集委員長.

最適設計ハンドブック:基礎・戦略・応用.

朝倉書店, 2003.

[6] L. Armijo.

Minimization of functions having lipschitz-continuous first partial derivatives.