第 3 章 数理計画法の基礎

畔上 秀幸

February 15, 2022
名古屋大学 情報学研究科 複雑系科学専攻

1 / 192

はじめに

本章では，解法に焦点をあてたい．最適化問題の解法は，数理計画法とよばれ，オペレーションズ・リサーチ (OR) とよばれよる学問分野で盛んに研究が行われている．ここでは，最適化問題の解法に関する考え方や理論的に得られる結果を示しながら，アルゴリズムについて考えてみたい．

2 / 192

3.1 問題設定

§3.1 問題設定

最適設計問題は，第 1 章でみてきたように，設計変数 ξ ∈ Ξ と状態変数
u ∈ U によって定義された評価関数 f0 (ξ, u), . . . , fm (ξ, u) に対する等式制
約 (状態方程式) と不等式制約つき最適化問題であるとみなされた．第 2 章では，そのような問題は x = (ξ, u) ∈ Ξ × U を設計変数とする f0 (ξ, u), . . . ,fm (ξ, u) で構成された最適化問題とみなされた．

4 / 192

本章では，第 1 章の定義に戻って，ξ を設計変数とよび，f0 (ξ, u (ξ)), . . . ,fm (ξ, u (ξ)) を f˜0 (ξ), . . . , f˜m (ξ) とみなすことにする．ξ に対する f˜0 (ξ),. . . , f˜m (ξ) の微分は，2.8 節でみてきたように，随伴変数法で求められる．さらに，f˜0 (ξ), . . . , f˜m (ξ) は非線形関数であると仮定する．実際，第 1 章の最適設計問題 (問題 1.1.4) では，f0 (u) が u に対する線形関数であっても，等式制約関数 h (a, u) = −K (a) u + p は (a, u) に対して非線形となるために，
f˜0 (a) は非線形関数となった．
そこで，本章では，設計変数 ξ ∈ Ξ を x ∈ X = Rd とかき，非線形関数 f˜0 ,. . . , f˜m を f0 , . . . , fm とかき，それらの x に対する勾配を g0 , . . . , gm とかくことにして，等式制約を含まない次の問題を考えることにしよう．

5 / 192

問題 3.1.1 (非線形最適化問題)

X = Rd とする．f0 , . . . , fm ∈ C 1 (X; R) に対して，
min {f0 (x) | f1 (x) ≤ 0, · · · , fm (x) ≤ 0}x∈Xを満たす x を求めよ．

6 / 1923.2 反復法

§3.2 反復法
定義 3.2.1 (反復法)問題 3.1.1 に対して，最小点ではない x0 ∈ X を選び，yg ∈ X を決めながら，k ∈ {0, 1, 2, · · · } に対して，

xk+1 = xk + yg = xk + ϵ̄g ȳg(3.2.1)を求めていく方法を反復法という．ここで，yg を探索ベクトル，その大きさ ∥yg ∥X をステップサイズという．それに対して，ȳg は方向のみを与える
ベクトルで，本書では，探索方向とよんで，探索ベクトルとは区別することにする．ȳg の大きさは 1 である必要はないと仮定する．ϵ̄g はその大きさを調整するための正の定数とする．また，x0 を初期点，k ∈ {0, 1, 2, · · · } に対して xk を試行点という．
8 / 192この定義から，反復法を使ったアルゴリズムを考える場合は，探索方向 ȳgを求める方法とステップサイズ ∥yg ∥X を適切に決める方法を具体的に示す必要がある．3.3 節以降で，それらの方法についてみていくことにする．なお，
このような反復法とは別に，直接法とよばれる最適化問題の数値解法が知られている．直接法は，ある決められた有限回の手順で解を求めることができる方法の総称として用いられる．直接法は，主に線形最適化問題に対して想定される方法であることから，本書では省略することにする．

9 / 192

定義 3.2.2 (大域的収束性)
初期点が最小点から十分離れていても，最小点に収束する性質があるとき，反復法は大域的収束性をもつという．
定義 3.2.3 (収束率)

x を極小点， {xk }k∈N を反復法でえられた点列とする．このとき，ある k0がとれて，任意の k ≥ k0 に対して，∥xk+1 − x∥X ≤ r ∥xk − x∥pXが成り立つような p ∈ [1, ∞) がとれるとき，p をそのアルゴリズムの収束次数という．ただし，p = 1 のとき r ∈ (0, 1) として，p > 1 のとき r は正の定数とする．また，r が 0 に収束する数列 {rk }k∈N に置き換えられるとき，
超 p 次収束という．
10 / 192

3.3 勾配法

§3.3 勾配法

図 3.1: 勾配 g の定義

図 3.2: 勾配法

12 / 192ここで，g の意味について確認しておこう．f を xk の周りで Taylor 展開すれば，

f (xk + y) = f (xk ) + g · y + o (∥y∥X )(3.3.1)となる．ここで，第 4 章で示される Fréchet 微分の定義 (定義 4.5.4) を先取りすれば，g は X の双対空間 X ′ (定義 4.4.5) の要素で，g の大きさ (ノルム)は∥g∥X ′ = maxy∈X⟨g, y⟩X ′ ×X=
max⟨g, y⟩X ′ ×Xy∈X, ∥y∥X =1∥y∥X

13 / 192

で定義される．X = Rd の場合は X ′ = Rd および双対積 ⟨g, y⟩X ′ ×X = g · yとなる．この定義によれば，∥g∥X ′ は，∥y∥X = 1 なる任意の y ∈ X に対す
る |g · y| の最大値を意味することになる．また，g の方向は f の等高線に対して垂直な方向を向いている．なぜならば，式 (3.3.1) において xk + y ∈ X
を等高線上の点として，y を十分小さなベクトルにとったとき，

g · y ≈ f (xk + y) − f (xk ) = 0が成り立つためである．図 3.1 はこの関係を示している．

14 / 192

これらの関係より，g は f がもっとも増加する方向を向いていることになる．そこで，有限次元ベクトル空間では X = X ′ が成り立つ (4.4.6 項) ことから，

ȳg = −g(3.3.2)のように ȳg ∈ X を選べば，f (xk + ȳg ) − f (xk ) = − ∥ȳg ∥2X + o ∥ȳg ∥X

となる．ここで，∥ȳg ∥X が十分小さければ，f が減少することになる．

15 / 192

問題 3.3.1 (勾配法)

X = Rd とする．A ∈ Rd×d を正定値実対称行列 (定義 2.4.5) とする．
f ∈ C 1 (X; R) に対して，極小点ではない xk ∈ X における f の勾配を
g (xk ) ∈ X ′ = Rd とする．このとき，任意の y ∈ X に対して
ȳg · (Ay) = −g (xk ) · y(3.3.3)を満たす ȳg ∈ X を求めよ．

16 / 192

式 (3.3.3) は，任意の y ∈ X との内積を用いた表現になっている．この方
程式は，

ȳg = −A−1 g(3.3.4)

によって ȳg を求めることと同値である．わざわざ内積を用いたのは，第 7 章
で関数空間での勾配法を定義するときに，それが問題 3.3.1 の自然な拡張になるようにするためである．また，式 (3.3.2) は A に単位行列 I を使った場合の勾配法であったことになる．問題 3.3.1 の解 ȳg が f を減少させることを次の定理で確認しておこう．
定理 3.3.2 (勾配法)問題 3.3.1 の解 ȳg は，f の xk における降下方向である．

17 / 192

証明 A は正定値実対称行列なので，任意の y ∈ X に対して

y · (Ay) ≥ α ∥y∥2X ,A = A⊤

を満たす正定値 α が存在する．この関係と式 (3.3.3) を用いれば，正の定数 ϵ̄に対して，

f (xk + ϵ̄ȳg ) − f (xk ) = ϵ̄g · ȳg + o (ϵ̄) = −ϵ̄ȳg · (Aȳg ) + o (ϵ̄)≤ −ϵ̄α ∥ȳg ∥2X + o (ϵ̄)
が成り立つ．ここで，ϵ̄ が十分小さければ，f は減少することになる．

□

18 / 192

定義 3.3.3 (降下角)xk ∈ X において，g ∈ X ′ を勾配，ȳg ∈ X を降下方向とする．このとき，cos θ = −⟨g, ȳg ⟩X ′ ×X
∥g∥X ′ ∥ȳg ∥X

で定義された θ ∈ [0, π] を xk における ȳg の降下角という．
勾配法 (問題 3.3.1) において，A を単位行列 I とおいたとき，ȳg の降下角
θ はゼロとなる．そこで，このときの反復法は最急降下法とよばれる．しかし，最急降下法がいつも収束が速いとは限らない．そのことは，あとで示される共役勾配法 (問題 3.4.10) との比較で明らかになる．

19 / 192

さらに，勾配法で得られる ȳg の幾何学的意味について考えてみよう．問題
3.3.1 は，1q (ȳg ) = min q (y) = y · (Ay) + g · y + f (xk )(3.3.5)y∈X2を満たす ȳg ∈ X を求めることと同値である．実際，任意の y ∈ X に対して
q ′ (ȳg ) [y] = 0 が成り立つことは，式 (3.3.3) が成り立つことと同値である．
図 3.2 にそのときの関数 q を示す．ここで，q は楕円放物面で，その最小点が xk + ȳg になっている．ȳg の大きさは A の選び方に依存する．したがって，ステップサイズ ∥yg ∥X = ∥ϵ̄g ȳg ∥X が ϵg になるようにしたければ，次の20 / 192

ような計算をおこなえばよいことになる．正の定数 ca を調整パラメータとして導入して，式 (3.3.4) を

yg = − (ca A)−1 g(3.3.6)に変更する．ここで，ca を大きくすれば yg の大きさは小さくなることに注意する．そこで，ステップサイズ ϵg と初期点 x0 における勾配法 (問題 3.3.1)の解 ȳg = ȳg (x0 ) が与えられたとき，

ca =∥ȳg ∥Xϵg(3.3.7)21 / 192

とおくことにする．最初のステップ (k = 0) において，ca をこのように定めて，k ∈ N に対してもこの ca を用いて式 (3.3.6) で探索ベクトルを求めていけば，ステップサイズ ∥ygk ∥X は，しばらくは，およそ ϵg の大きさをもつことになる．また，ca を最初のステップで求めた値に固定することによって，収束に近づいたときにステップサイズは 0 に近づくことが期待される．このように ca を導入したときには，式 (3.3.5) は1
q (yg ) = min q (y) = y · (ca Ay) + g · y + f (xk )y∈X2(3.3.8)に変更される．

22 / 192ca の決め方に関して，ステップサイズのイメージが明確で，ϵg として具体的な値が思い浮かべることができる場合には，式 (3.3.7) を用いることができる．例えば，第 9 章で扱うような領域変動を考える場合には，領域変動の大きさ (ステップサイズ) は領域変動によるひずみのノルム (ひずみを 2 乗して積分した値の平方根，あるいは最大ひずみ) などで定義される．そこで，ϵgにはひずみのノルムのイメージで，例えば 0.05 などと，値を設定することができる．しかしながら，そのようなイメージが得られない場合には，ca を適切に決めるために別の方法を考えなければならない．
その方法の一つは，期待する目的関数の減少率を与えて，ca を決める方法
である 1 ．k = 0 のときの評価関数 f (x0 ) と勾配 g (x0 ) は与えられ，勾配法

23 / 192

によって探索ベクトル ȳg も与えられたと仮定する．その上で，目的関数の減少率 α ∈ (0, 1) を与えて，

f (x0 + ϵ̄g ȳg ) − f (x0 ) ≈ αf (x0 ) ≈ ϵ̄g g (x0 ) · ȳgを予測する．このとき，≈ を = とみなせば，ca は

ca =1
g (x0 ) · ȳg=ϵ̄g
αf (x0 )(3.3.9)によって与えられる．

24 / 192

(追加) 目的関数の減少率 α1Julius Fergy T. Rabago (私信)25 / 192これまでの考察に基づいて，勾配法を使った簡単なアルゴリズムを示すことにしよう．なお，本章でアルゴリズムを記述するときには，最適設計問題を解くことを想定して，次のような表記をすることにする．
「f (xk ) を計算する」とかくところを「状態決定問題を解いて，f (xk ) を計算する」とかく．
また，「g (xk ) を計算する」とかくところを「f に対する随伴問題を解いて，
g (xk ) を計算する」とかく．その理由は，3.1 節の冒頭で説明されたように，
最適設計問題ではそのような計算になるためである．

26 / 192

図 3.3: 勾配法のアルゴリズム

27 / 192

アルゴリズム 3.3.4 (勾配法)問題 3.1.1 において f0 を f とかき，すべての不等式制約は無効とする．

1. 初期点 x0 , 正定値対称行列 A (特に指定がなければ I), ステップサイズを調整する正の定数 ca および収束判定に用いる正の定数 ϵ0 を与える．
k = 0 とおく．
2. 状態決定問題を解いて，f (xk ) を計算する．
3. f に対する随伴問題を解いて，g (xk ) を計算する．
4. 式 (3.3.6) で yg を計算する．
5. xk+1 = xk + yg とおき，状態決定問題を解いて，f (xk+1 ) を計算する．

28 / 192

6. 終了条件 |f (xk+1 ) − f (xk )| ≤ ϵ0 を判定する．
• 終了条件が満たされたとき，(7) に進む．
• そうではないとき，k + 1 を k に代入し，(3) に戻る．

7. 計算を終了する．
アルゴリズム 3.3.4 では，終了条件に |f (xk+1 ) − f (xk )| ≤ ϵ0 が使われた．
これ以外に，設計変数の変動量に注意がむけられた ∥yg ∥X ≤ ϵ0 や k が上限
値を超えない条件などが考えられる．

29 / 192

図 3.4: ステップサイズの初期値が与えられた勾配法のアルゴリズム

30 / 192

アルゴリズム 3.3.5 (初期ステップサイズ指定の勾配法)問題 3.1.1 において f0 を f とかき，すべての不等式制約は無効とする．

1. 初期点 x0 , 正定値対称行列 A, 初期のステップサイズを与える正の定数ϵg (あるいは目的関数の減少率 α) および収束判定に用いる正の定数 ϵ0を与える．ca = 1 および k = 0 とおく．
2. 状態決定問題を解いて，f (xk ) を計算する．
3. 随伴問題を解いて，g (xk ) を計算する．
4. 式 (3.3.6) で yg を計算する．

31 / 192

5. k = 0 のとき，yg = ȳg とおき，式 (3.3.7) で ca を求める．また，ȳg /ca
を yg に代入する．
6. xk+1 = xk + yg とおき，状態決定問題を解いて，f (xk+1 ) を計算する．
7. 終了条件 |f (xk+1 ) − f (xk )| ≤ ϵ0 を判定する．
• 終了条件が満たされたとき，(8) に進む．
• そうではないとき，k + 1 を k に代入し，(3) に戻る．

8. 計算を終了する．

32 / 192

3.4 ステップサイズの規準§3.4 ステップサイズの規準

次に，ステップサイズ ∥yg ∥X を適切に決める方法について考えてみよう．
問題 3.4.1 (厳密直線探索法)

X = Rd とする．f ∈ C 1 (X; R), xk ∈ X と ȳg ∈ X が与えられたとき，
min f (xk + ϵ̄g ȳg )ϵ̄g ∈(0,∞)

を満たす ϵ̄g を求めよ．

34 / 192

問題 3.4.1 を解くアルゴリズムには，非線形方程式を解くためのアルゴリズ
ムが使われる．たとえば次のような方法が考えられる．

• 二分法• セカント法
二分法は，f が減少から増加に転じるような ϵ̄g の区間をみつけて，その区間の中間点を求める操作を繰り返す．そのときの ϵ̄g の厳密解への収束次数は 1となる．セカント法を用いる場合には，f の ϵ̄g に対する勾配がゼロとなるよ
うな ϵ̄g を求める問題とみなす．その上で，あとで示される Newton-Raphson法において f の勾配を差分におきかえたときの更新式を用いて極小点が求め

35 / 192

られる (演習問題 3.1 と 3.2)．この方法の収束次数は黄金比 1 +あることが知られている．

√ 
5 /2 で問題 3.4.2 (2 次最適化問題の厳密直線探索法)

X = Rd とする．B ∈ Rd×d を正定値実対称行列，b ∈ X を既知ベクトルとして，評価関数を
1
f (x) = x · (Bx) + b · x
2(3.4.1)

とおく．このとき，xk ∈ X に対して最急降下法により ȳg ∈ X を求め，問題 3.4.1 を満たす ϵ̄g ∈ (0, ∞) を求めよ．

36 / 192f (xk + ϵ̄g ȳg ) を f¯ (ϵ̄g ) とかけば，

解答

1f¯ (ϵ̄g ) = (xk + ϵ̄g ȳg ) · {B (xk + ϵ̄g ȳg )} + b · (xk + ϵ̄g ȳg )2
1= ϵ̄2g ȳg · (B ȳg ) + ϵ̄g ȳg · g + f (xk )2とかける．ここで，g = Bxk + b が 2 番目の等号で使われた．厳密直線探索法では，

df¯= ϵ̄g ȳg · (B ȳg ) + ȳg · g = 0
dϵ̄g
より，

ϵ̄g = −

ȳg · gȳg · (B ȳg )37 / 192

が得られる．さらに，ȳg が最急降下法の解ならば，ȳg = −g より

ϵ̄g = −

ȳg · gg·g
g·g==
ȳg · (B ȳg )g · (Bg)ȳg · (B ȳg )が成り立つ．

(3.4.2)□

このように厳密直線探索法により ϵ̄g を求めながら反復法を繰り返したときの収束性について，次の結果が得られる．

38 / 192

定理 3.4.3 (厳密直線探索法を用いた最急降下法の収束性)
問題 3.4.2 の解 ȳg ∈ X と ϵ̄g を用いた反復法によって生成される点列{xk }k∈N は∥xk+1 − x∥B ≤λd − λ 1∥xk − x∥B
λ1 + λdを満たす．ただし，x は極小点，λ1 , λd は B の最小および最大の固有値，p∥x∥B = x · (Bx) とする．

39 / 192証明 問題 3.4.2 の目的関数は

f (x) =

 


1
1
x + B −1 b · B x + B −1 b − b · B −1 b
2
2とかける．ここで，x + B −1 b を x におきかえても xk+1 − x の評価は変わらない．また，上式の右辺第 2 項は x の関数ではないので，それを省略しても
xk+1 − x の評価は変わらない．そこで，

1f¯ (x) = x · (Bx)240 / 192

の最小点を求める問題を考える．gk = g (xk ) = Bxk とかくとき，最急降下法より，ȳk = −gk が得られる．さらに，厳密直線探索法の結果，式 (3.4.2)
より，

xk+1 = xk +gk · gkȳk
gk · (Bgk )によって点列が生成される．このとき，

  

1
g
·
g
g
·
g
k
k
k
k
f¯ (xk+1 ) =xk −g k · B xk −gk2
gk · (Bgk )gk · Bgk"#
2 (gk · gk ) {gk · (Bxk )} − (gk · gk )2
1
xk · (Bxk ) −=2
gk · (Bgk )41 / 192

1
=
2

(

(gk · gk )2
xk · (Bxk ) −gk · (Bgk ))1(gk · gk )2= xk · (Bxk ) 1 −2{xk · (Bxk )} {gk · (Bgk )}!
(gk · gk )2
f (xk )
= 1−
{gk · (B −1 gk )} {gk · (Bgk )}!

が成り立つ．ここで，任意の y ∈ X に対して，Kantorovich の不等式

4λ1 λd(y · y)2≤{y · (B −1 y)} {y · (By)}(λ1 + λd )242 / 192

が成り立つことを用いれば，

f¯ (xk+1 ) ≤が得られる．

4λ1 λd1−(λ1 + λd )2f¯ (xk ) =λd − λ1
λ1 + λd2f¯ (xk )□以上の結果をふまえて，厳密直線探索法の特徴について考えてみよう．厳
密直線探索法では，ステップサイズのみを設計変数においた最小化問題を正確に解くことを要請している．最小点を正確に求めるためには，二分法やセカント法などのような繰り返し計算が必要となる．もしも，勾配を求める計算が容易ではなく，設計変数に対して評価関数を求める計算が容易な問題に

43 / 192

対しては，二分法などのような勾配の計算が不要なアルゴリズムは有効であると考えられる．しかしながら，設計変数が探索方向に移動したあとでは勾配は変化し，勾配法から決定される探索方向も変化することになる．そのような状況にあっても古い探索方向を使って最小点を正確に求めることは，必ずしも得策ではないと考えられる．特に，セカント法のように ϵ̄g を更新した
あとに勾配の再計算が必要となる (演習問題 3.2) アルゴリズムを用いる場合には，古い探索方向を使い続けるよりは，勾配法によって探索方向を更新したほうがより収束性が向上すると思われる．
そこで，次に，厳密であることにはこだわらずに，評価関数の非線形性と勾配の有効な範囲に注目した方法について考えてみることにしよう．以下に44 / 192示される規準は，ステップサイズの上限と下限を与える．ステップサイズ∥ϵ̄g ȳg ∥X の上限に関しては，次のような条件が知られている [1]．
定義 3.4.4 (Armijo の規準)

g (xk ) を f (xk ) の勾配，ȳg を探索方向，ξ ∈ (0, 1) をステップサイズの上限を調整するパラメータとする．このとき，ϵ̄g > 0 に対してf (xk + ϵ̄g ȳg ) − f (xk ) ≤ ξg (xk ) · (ϵ̄g ȳg ) < 0(3.4.3)が成り立つとき，ϵ̄g は Armijo の規準を満たすという．

45 / 192

図 3.5: Armijo の規準

46 / 192

また，ξ の目安として，次の結果が参考になる．f (x) が 2 次関数ならば，
ξ = 1/2 のときの Armijo の規準の上限値を ϵ̄gA とするとき，xk + ϵ̄gA ȳg が fの最小点となる (図 3.6)．実際，式 (3.4.1) の 2 次関数に対して

f (xk + ϵ̄gA ȳg ) − f (xk ) = g (xk ) · (ϵ̄gA ȳg ) +1(ϵ̄gA ȳg ) · {B (ϵ̄gA ȳg )}2(3.4.4)が成り立つ．ここで，xk + ϵ̄gA ȳg が極小点ならば，g (xk ) の Taylor 展開についてg (xk + ϵ̄gA ȳg ) = g (xk ) + B (ϵ̄gA ȳg ) = 0X ′(3.4.5)47 / 192

が成り立つ．式 (3.4.5) を式 (3.4.4) に代入すれば，

1
f (xk + ϵ̄gA ȳg ) − f (xk ) = g (xk ) · (ϵ̄gA ȳg )2が得られる．

図 3.6: 2 次関数に対する Armijo の規準

48 / 192

一方，ステップサイズ ∥ϵ̄g ȳg ∥X の下限を与える条件として次のような条件が知られている [3]2 ．
定義 3.4.5 (Wolfe の規準)

g (xk ) を f (xk ) の勾配，ȳg を探索方向，ξ ∈ (0, 1) を Armijo の規準で使われたパラメータ，µ ∈ (0, 1) をステップサイズの下限を調整するパラメータで 0 < ξ < µ < 1 を満たすとする．このとき，ϵ̄g > 0 に対して
µg (xk ) · (ϵ̄g ȳg ) ≤ g (xk + ϵ̄g ȳg ) · (ϵ̄g ȳg ) < 0(3.4.6)が成り立つとき，ϵ̄g は Wolfe の規準を満たすという．

49 / 192

Wolfe の規準を満たす ϵ̄g の下限値を ϵ̄gW とかけば，図 3.7 のような関係が成り立つ．式 (3.4.6) の左辺における g (xk ) は，xk のときの f の勾配を表している．一方，右辺の g (xk + ϵ̄g ȳg ) は，実際に x を xk から xk + ϵ̄g ȳg に移動したときに得られる f の勾配を表している．Wolfe の規準に対して，次のことが成り立つ．
1. ある ϵ̄g > 0 に対して g (xk + ϵ̄g ȳg ) · (ϵ̄g ȳg ) ≤ g (xk ) · (ϵ̄g ȳg ) < 0 が成り立
つとき，式 (3.4.6) が成り立つような ϵ̄g > 0 は存在しない．この条件は，
x が ȳg の方向に移動したときに，f が減少するような負の勾配がさらに大きな負の勾配になることを表している．このようなときにはステップ
サイズの下限を設ける必要はないことを表している．

50 / 192

2. ある ϵ̄g > 0 に対して g (xk ) · (ϵ̄g ȳg ) < g (xk + ϵ̄g ȳg ) · (ϵ̄g ȳg ) < 0 が成り立
つとき，式 (3.4.6) が成り立つような ϵ̄g > 0 は存在する．この条件は，
上記 (1) とは反対に，x が ȳg の方向に移動したときに，勾配の大きさが減少することを表している．式 (3.4.6) において µ を 1 よりも小さくしていけば，ϵ̄g の下限値 ϵ̄gW は大きくなっていく．
そこで，Wolfe の規準は，勾配の有効性が µ の割合まで失われる程度にス
テップサイズを大きくとることを要請する条件になっている．
また，ξ < µ の根拠は次のような関係に基づいている．f の xk + ϵ̄g ȳg まわりにおける Taylor 展開を

f (xk ) = f (xk + ϵ̄g ȳg ) − g (xk + ϵ̄g ȳg ) · (ϵ̄g ȳg ) + o (ϵ̄g )51 / 192

とかく．このとき，Wolfe の規準が満たされるならば，µg (xk ) · (ϵ̄g ȳg ) − o (ϵ̄g ) ≤ g (xk + ϵ̄g ȳg ) · (ϵ̄g ȳg ) − o (ϵ̄g )= f (xk + ϵ̄g ȳg ) − f (xk )が成り立つ．一方，Armijo の規準が満たされるならば，

f (xk + ϵ̄g ȳg ) − f (xk ) ≤ ξg (xk ) · (ϵ̄g ȳg )が成り立つ．そこで，二つの規準を同時に満たすならば，(µ − ξ) g (xk ) · (ϵ̄g ȳg ) ≤ o (ϵ̄g )52 / 192

が成り立つ必要がある．ここで，g (xk ) · (ϵ̄g ȳg ) ≤ 0 であることから，右辺が正，あるいは絶対値が十分に小さい場合には，ξ < µ のときにこの不等式は成り立つことになる．

図 3.7: Wolfe の規準

53 / 192

図 3.8: Armijo の規準と Wolfe の規準を用いた勾配法のアルゴリズム

2

文献では Wolfe の規準の中に Armijo の規準が含まれているが，本書では ϵ̄g の下限を与える条件のみを Wolfe の規準とよぶことにする．
54 / 192

Armijo の規準と Wolfe の規準が満たされるようにステップサイズが制御されたアルゴリズムの一例を次に示す．図 3.8 はその概要を示す ．
アルゴリズム 3.4.6 (Armijo の規準と Wolfe の規準)問題 3.1.1 において f0 を f とかき，すべての不等式制約は無効とする．

1. 初期点 x0 , 正定値実対称行列 A, ステップサイズ ϵg , 収束判定値 ϵ0 および Armijo の規準と Wolfe の規準で使われる．パラメータ ξ と µ(0 < ξ < µ < 1) を与える．ca = 1 および k = 0 とおく．
2. 状態決定問題を解いて，f (xk ) を計算する．
3. f に対する随伴問題を解いて，g (xk ) を計算する．
4. 式 (3.3.6) で yg を計算する．

55 / 192

5. k = 0 のとき，yg = ȳg とおき，式 (3.3.7) で ca を求める．また，ȳg /ca
を yg に代入する．
6. xk+1 = xk + yg とおき，状態決定問題を解いて，f (xk+1 ) を計算する．
7. Armijo の規準 (式 (3.4.3)) を判定する．
• 満たされていれば，次に進む．
• そうではないとき，α > 1 として ca に αca を代入し，yg に αyg を代入して，(5) に戻る．

8. g (xk+1 ) を計算する．

56 / 192

9. Wolfe の規準 (式 (3.4.6)) を判定する．
• 満たされていれば，次に進む．
• そうではないとき，β ∈ (0, 1) として ca に βca を代入し，yg に βyg を代入して，(5) に戻る．

10. 終了条件 |f0 (xk+1 ) − f0 (xk )| ≤ ϵ0 を判定する．
• 終了条件が満たされたとき，(11) に進む．
• そうではないとき，k + 1 を k に代入し，(4) に戻る．

11. 計算を終了する．

57 / 192

Armijo の規準と Wolfe の規準が満たされるようにステップサイズが制御されたアルゴリズムによって得られる点列に対して，大域的収束性に関する次の結果が得られる．

58 / 192

定理 3.4.7 (大域的収束定理)

X = Rd とする．関数 f : X → R は下界をもち，x0 ∈ X の水準集合
L = {x ∈ X | f (x) ≤ f (x0 )} の近傍で微分可能で，勾配 g は L の近傍でLipschitz 連続 (定義 4.3.1) とする．xk における探索ベクトルを ygk とかいて，ygk は降下角 θk に対して cos θk > 0 を満たすとする．ステップサイズ∥ϵ̄g ȳg ∥X は Armijo の規準と Wolfe の規準を満たすとする．このとき，勾配法で生成される点列 {xk }k∈N はX∥g (xk )∥2X ′ cos2 θk < ∞(3.4.7)k∈Nを満たす．

59 / 192

証明 Armijo の規準より，{xk }k∈N は L の近傍に含まれる．Wolfe の規準より，(µ − 1) g (xk ) · yg ≤ (g (xk+1 ) − g (xk )) · ygが成り立つ．一方，g が Lipschitz 連続であることから，ある β > 0 に対して

(g (xk+1 ) − g (xk )) · yg ≤ β ∥xk+1 − xk ∥X ∥yg ∥X = ϵ̄g β ∥yg ∥2Xが成り立つ．これらの式より，ϵ̄g ≥(g (xk+1 ) − g (xk )) · yg(µ − 1) g (xk ) · yg≥
2β ∥yg ∥Xβ ∥yg ∥2X

60 / 192

が得られる．この式を Armijo の規準に代入すれば，µ−1
f (xk+1 ) ≤ f (xk ) + ξϵ̄g g (xk ) · yg = f (xk ) − ξβµ−1∥g (xk )∥2X ′ cos2 θk= f (xk ) − ξβg (xk ) · yg
∥yg ∥X2となる．したがって，

f (xk+1 ) ≤ f (xk ) − ξ

µ−1
β

X

∥g (xk )∥2X ′ cos2 θkk∈{0,··· ,m}が成り立つ．f は下に有界であることから，定理の式が成り立つ．

□

61 / 192

式 (3.4.7) は Zoutendijk 条件とよばれる．定理 3.4.7 の結果と，無限級数が2収束するための必要条件 limk→∞ ∥g (xk )∥X ′ cos2 θk = 0 を用いれば，次のような結果が得られる．
系 3.4.8 (大域的収束定理)
定理 3.4.7 の仮定に加えて，yg は −g (xk ) と直角に交わる方向に漸近することがないとき，すなわち cos θk > 0 のとき，

lim g (xk ) = 0X ′k→∞が成り立つ．

62 / 192

この結果は，問題設定が適切であれば，勾配法で探索方向を求め，Armijoの規準と Wolfe の規準が満たされるようにステップサイズをとっていけば，生成される点列 {xk }k∈N は大域的収束性をもつことを示している．
この節の最後に，勾配法が拡張された方法として共役勾配法を紹介しておこう．まず，ベクトルどうしの共役を次のように定義する．
定義 3.4.9 (共役)B ∈ Rd×d を正定値実対称行列とする．x ∈ X と y ∈ X に対して
x · (By) = 0 のとき， x と y は共役であるという．
問題 3.4.2 に対して，共役勾配法は次のように定義される．

63 / 192

問題 3.4.10 (共役勾配法)

x0 ∈ X に対して，探索方向 ȳg0 とステップサイズを調整するパラメータϵ̄g0 は，それぞれ最急降下法と厳密直線探索法により与えられているとする．
k ∈ N に対して，ȳg k−1 を与えて，ȳg k−1 と共役になるように ȳgk を求めよ．
また，厳密直線探索法によってステップサイズを調整するパラメータ ϵ̄gk を求めよ．
共役勾配法の一例を示そう．x0 = 0X とおく．最急降下法により探索方向を ȳg0 = −g0 = −g (x0 ) = −b とおく．k ∈ {0, 1, 2, · · · } に対して，ȳgk と gkが与えられたとき，式 (3.4.2) (厳密直線探索法) により，ϵ̄gk =ȳgk · gk
ȳgk · (B ȳgk )(3.4.8)64 / 192

を求める．さらに，k ∈ N に対して，

xk = xk−1 + ϵ̄g k−1 ȳg k−1 ,(3.4.9)gk = gk−1 + ϵ̄g k−1 B ȳg k−1 ,gk · gk,
βk =gk−1 · gk−1

(3.4.10)ȳgk = −gk + βk ȳg k−1(3.4.12)(3.4.11)

によって点列を構成する．このとき，ȳg k−1 と ȳgk は共役になる (演習問題
3.3)．

65 / 192

図 3.9: 共役勾配法で得られる探索ベクトル

66 / 192

式 (3.4.11) は Fletcher-Reeves 公式 とよばれる．また，それと同値な

βk =gk · (gk − gk−1 )gk−1 · gk−1

は Polak-Ribiere 公式とよばれる．これらの他にもいくつかの公式が知られている．これらの公式は，2 次最適化問題 (問題 3.4.2) に対しては同値でも，そうではない非線形最適化問題に gk = g (xk ) を用いた場合には，異なる結果となる．

67 / 192

3.5 Newton 法§3.5 Newton 法
勾配法では勾配 g を用いて探索方向が求められた．ステップサイズは厳密
直線探索法あるいは Armijo の規準や Wolfe の規準を満たすように決められた．ここでは，g と Hesse 行列 H を使って，探索方向とステップサイズを同時に求める方法について考えてみよう．その方法は Newton 法とよばれる．
Newton 法は，任意の y ∈ X に対して g · y の xk まわりの Taylor 展開g (xk + yg ) · y = g (xk ) · y + yg · (H (xk ) y) + o ∥yg ∥Xにおいて，o ∥yg ∥X を無視し，

g (xk + yg ) · y = g (xk ) · y + yg · (H (xk ) y) = 0
とおくことにより探索ベクトル yg ∈ X を求める方法である．すなわち，次のように定義される．
69 / 192

問題 3.5.1 (Newton 法)

X = Rd とする．f ∈ C 2 (X; R) に対して，極小点ではない xk ∈ X における f の勾配と Hesse 行列を g (xk ) と H (xk ) とする．このとき，任意のy ∈ X に対して
yg · (H (xk ) y) = −g (xk ) · y(3.5.1)が満たされるように yg ∈ X を求めよ．

Newton 法は，勾配法 (定義 3.3.1) において使われた正定値実対称行列 A
を Hesse 行列におきかえて，さらに，ϵ̄g = 1 とおいたときの勾配法になっている．Newton 法について次の結果が得られる．

70 / 192

定理 3.5.2 (Newton 法)

f は極小点 x の近傍で 2 階微分可能で，Hesse 行列 H は Lipschitz 連続 (定義 4.3.1) であるとする．また，H (x) は正定値であるとする．このとき，極小点に十分近い点を x0 にして，Newton 法で生成された点列 {xk }k∈N は
x に 2 次収束する．
証明 極小点を x とする．x の近傍で Hesse 行列 H は Lipschitz 連続，かつH (x) は正則であることから，ある β > 0 に対して

1
2
(3.5.2)H −1 (x) (H (xk ) − H (x)) Rd×d ≤ H −1 (x) Rd×d β ∥xk − x∥Rd <71 / 192

が満たされるように極小点に十分近い点 xk をとることができる．ただし，

H −1 (x) Rd×d =maxy∈Rd , ∥y∥Rd=1

H −1 (x) y Rdと定義する．この関係に対して Banach の摂動定理 (たとえば，[4, p. 240])より，

H −1 (xk ) Rd×d ≤∥H −1 (x)∥Rd×d< 2 H −1 (x) Rd×d
−1
1 − ∥H (x) (H (xk ) − H (x))∥Rd×d(3.5.3)が成り立つ．このとき，xk+1 = xk + yg , 式 (3.5.1) および g (x) = 0Rd より，

xk+1 − x = xk − H −1 (xk ) g (xk ) − x + H −1 (xk ) g (x)72 / 192

= −H −1 (xk ) {g (xk ) − g (x) − H (xk ) (xk − x)}(3.5.4)が成り立つ．一方，∥g (xk ) − g (x) − H (xk ) (xk − x)∥Rd
Z 1=(H (x + t (xk − x)) − H (xk )) (xk − x) dt0
RdZ 1∥H (x + t (xk − x)) − H (xk )∥Rd×d dt≤ ∥xk − x∥Rd0
Z 1
≤ ∥xk − x∥Rdβ ∥xk − x∥Rd (1 − t) dt
01= β ∥xk − x∥2Rd
2
73 / 192

が成り立つ．したがって，式 (3.5.2), 式 (3.5.3) および式 (3.5.4) より∥xk+1 − x∥Rd ≤1
1
H −1 (xk ) Rd×d β ∥xk − x∥2Rd < ∥xk − x∥Rd (3.5.5)22が成り立つ．式 (3.5.5) の左辺と最右辺の関係により，極小点 x への収束が確認される．また，式 (3.5.5) の左辺と第１右辺の関係により，2 次収束が示された．
□

74 / 192

図 3.10: Newton 法のアルゴリズム

75 / 192

アルゴリズム 3.5.3 (Newton 法)問題 3.1.1 において f0 を f とかき，すべての不等式制約は無効とする．

1. 初期値 x0 と収束判定値 ϵ0 を定める．k = 0 とおく．
2. 状態決定問題を解いて，f (xk ) を計算する．
3. f に対する随伴問題を解いて，g (xk ) を計算する．
4. 式 (3.5.1) で yg を計算する．
5. xk+1 = xk + yg とおき，状態決定問題を解いて，f (xk+1 ) を計算する．

76 / 192

6. 終了条件 |f0 (xk+1 ) − f0 (xk )| ≤ ϵ0 を判定する．
• 終了条件が満たされたとき，(7) に進む．
• そうではないとき，k + 1 を k に代入し，(3) に戻る．

7. 計算を終了する．

77 / 192

注意 3.5.4 (Newton 法)

Newton 法は次の性質をもつ．
1. Newton 法は Hesse 行列が必要となる．Hesse 行列の計算量は，この行列が密な場合には，設計変数の 2 乗に比例する．しかし，Hesse 行列が対角行列となる場合には，設計変数に比例する程度である．実際，第１章の問題 1.1.4 では Hesse 行列は対角行列であった．
2. Newton 法は 2 次収束する (定理 3.5.2)．
3. Hesse 行列が正定値ではない場合，Newton 法では収束しないことがある．
また，不定値の場合，極大点に収束することがある (図 3.11)．

78 / 192

4. Hesse 行列 H が特異行列のとき，あるいは特異行列でなくても行列の条
件数 (最大固有値の最小固有値に対する比) が大きいとき，逆行列の計算が困難になる．

(a) 収束しない場合(b) 極大値に収束する場合

図 3.11: Newton 法

79 / 192

このようにみてくると，勾配法 (問題 3.3.1) は，Newton 法 (問題 3.5.1) において Hesse 行列を正定値実対称行列におきかえた方法になっている．そこ
で，正定値実対称行列を Hesse 行列に漸近するように更新していくことで，
Newton 法に近い性能をもつ勾配法が研究されている．それらは準 Newton法とよばれる．代表的な更新公式として次のようなものが知られている．詳
細は数理計画法の教科書を参照されたい．

• Davidon-Fletcher-Powell 法• Broyden-Fletcher-Goldfarb-Shanno 法• Broyden 法

80 / 192

また，Newton 法の原理は，非線形方程式の解を求めるときにも使われる．
そのような場合には，Newton-Raphson 法ともよばれる．Newton-Raphson 法
は，あとで示されるアルゴリズム 3.7.6 の中でも使われる．そこで，その説明をここでしておこう．Newton-Raphson 法が適用される問題は次のような問題である．
問題 3.5.5 (非線形方程式)


X = Rd とする．f ∈ C 1 Rd ; Rd に対して，
f (x) = 0Rd(3.5.6)が満たされるように x ∈ Rd を求めよ．

81 / 192

問題 3.5.5 の試行点を k ∈ {0, 1, 2, · · · } に対して xk とかくことにする．xk
における f とその勾配 G = (∂fi /∂xj )(i,j)∈{1,··· ,d}2 が計算可能であるとする．
このとき，xk+1 = xk + yg が x となるような yg を求めることを考える．fの xk まわりの Taylor 展開は

f (xk + yg ) = f (xk ) + G (xk ) yg + o ∥yg ∥Rdとかける．ここで，o ∥yg ∥Rd を無視すれば，
f (xk + yg ) = f (xk ) + G (xk ) yg = 0Rd(3.5.7)となる．式 (3.5.7) より，次の問題を考える．

82 / 192

問題 3.5.6 (Newton-Raphson 法)問題 3.5.5 に対して，試行点 xk における関数値 f (xk ) とその勾配 G (xk )が与えられたとする．探索ベクトルを

yg = −G−1 (xk ) f (xk )(3.5.8)によって求めよ．

Newton-Raphson 法は，問題 3.5.6 の解 yg を用いて，xk+1 = xk + yg により問題 3.5.5 の解 x に収束する点列 {xk }k∈N を求める方法である．Newton
法 (問題 3.5.1) の g と H をそれぞれ f と G におきかえれば，
Newton-Raphson 法 (問題 3.5.6) に一致することが理解されよう．

83 / 192この節の最後に，1.1.6 節の最後に説明した Lagrange 乗数法による評価関数の 2 階微分を用いた場合の Newton 法について考えておこう．すなわち，評
価関数の 2 階微分が式 (1.1.50) のような Hesse 勾配によって得られていることを仮定する．この場合，H0 b1 が gH0 (a, b1 ) として得られることから，
gH0 (a, b1 ) を勾配とみなしたときの勾配法を考えればよい．しかし，
gH0 (a, b1 ) を求めるために，評価関数の 1 階微分に対する随伴問題 (問題1.1.6) を解く必要がある．さらに，その随伴問題を解くためには，b1 が既知である必要がある．これらのことを考慮すれば，解くべき問題は次のようになる．

84 / 192

問題 3.5.7 (Hesse 勾配を用いた Newton 法)

X = Rd とする．A ∈ Rd×d と ca を正定値実対称行列と正の定数とする．
f ∈ C 2 (X; R) に対して，極小点ではない xk ∈ X における f の勾配
g (xk )，探索ベクトル ȳg および Hesse 勾配 gH (xk , ȳg ) が与えられたとする．このとき，任意の y ∈ X に対して
yg · (ca A (xk ) y) = − (g (xk ) + gH (xk , ȳg )) · y(3.5.9)が満たされるように yg ∈ X を求めよ．

85 / 192

問題 3.5.7 の解 yg は，ca A (xk ) = I および ȳg = yg のとき，Newton 法の解と一致する．問題 3.5.7 のを用いたアルゴリズムは，例えば，次のようになる．図 3.12 はその概要を示す．

86 / 192

図 3.12: Hesse 勾配を用いた Newton 法のアルゴリズム

87 / 192

アルゴリズム 3.5.8 (Hesse 勾配を用いた Newton 法)問題 3.1.1 において f0 を f とかき，すべての不等式制約は無効とする．

1. 初期値 x0 と収束判定値 ϵ0 を定める．k = 0 とおく．
2. 状態決定問題を解いて，f (xk ) を計算する．
3. f に対する随伴問題を解いて，g (xk ) を計算する．
4. 勾配法 (式 (3.3.6)) で yg を計算する．
5. f ′ に対する随伴問題を解いて， Hesse 勾配 gH (xk , yg ) を計算する．

88 / 192

6. gH (xk , yg ) を用いた Newton 法 (式 (3.5.9)) で yg を計算する．
7. xk+1 = xk + yg とおき，状態決定問題を解いて，f (xk+1 ) を計算する．
8. 終了条件 |f0 (xk+1 ) − f0 (xk )| ≤ ϵ0 を判定する．
• 終了条件が満たされたとき，(7) に進む．
• そうではないとき，k + 1 を k に代入し，f に対する随伴問題を解いて，
g (xk ) を計算し，(5) に戻る．

9. 計算を終了する．

89 / 192

3.6 拡大関数法

§3.6 拡大関数法
3.3 節から 3.5 節までは制約なし最適化問題に対する数値解法についてみてきた．この節以降では問題 3.1.1 に戻って，極小点で不等式制約が有効となる
場合について考えよう．まず，本節では，制約関数に重みを表す定数をかけて目的関数に加えることで，制約なし問題におきかえる方法について考えてみることにする．このような方法は，拡大関数法とよばれる．拡大関数の最小値を求める方法には，3.3 節から 3.5 節までに示された制約なし最適化問題の解法が使われる．
拡大関数法の一つは，すべての不等式制約が満たされている点 (内点) を初期点として，許容集合の外に出ないように工夫された拡大関数を用いる方法である．問題 3.1.1 に対して，次のようにして得られる点列 {xk }k∈N の収束点により解を求める方法を障壁法あるいは内点法という．
91 / 192

問題 3.6.1 (障壁法, 内点法)

{ρk }k∈N を正値をとる単調減少数列とする．x0 ∈ X は f1 (x0 ) < 0, . . . ,fm (x0 ) < 0 が満たされるように与えられているとする．k ∈ N に対して，
ρk と試行点 xk−1 を与えて，




X
ˆ
min fk (xk , ρk ) = f0 (xk ) − ρklog (−fi (xk ))y∈X i∈{1,··· ,m}を満たす xk = xk−1 + y を求めよ．

92 / 192

問題 3.6.2 (罰金法, 外点法)

{ρk }k∈N を正値をとるある単調増加数列とする．x0 ∈ X は与えられているとする．k ∈ N に対して，ρk と試行点 xk−1 を与えて，




X
min fˆk (xk , ρk ) = f0 (xk ) + ρk
max {0, fi (xk )}y∈X i∈{1,··· ,m}を満たす xk = xk−1 + y を求めよ．

93 / 192

以上の定義から，拡大関数法は，原理が明快であることから，利用しやすように思われる．しかし，拡大関数法を使用するためには，問題に応じて単調減少数列あるいは単調増加数列 {ρk }k∈N を適切に選ぶ必要がある．本書では，その選択方法の詳細には触れないことにする．

94 / 192

3.7 制約つき問題に対する勾配法

§3.7 制約つき問題に対する勾配法
次に，3.7 節と 3.8 節において，KKT 条件を用いる方法について考えてみよう．ここで示されるアルゴリズムは第 7 章以降で使われる．最初に，制約つき問題に対する勾配法について考えよう．
問題 3.1.1 に対して，不等式制約が満たされる許容集合を

S = {x ∈ X | f1 (x) ≤ 0, · · · , fm (x) ≤ 0}

(3.7.1)とかくことにする．また，x ∈ S に対して，IA (x) = {i ∈ {1, · · · , m} | fi (x) ≥ 0} = i1 , · · · , i|IA (x)|(3.7.2)を有効な制約に対する添え字の集合とする．混乱がない場合には IA (xk ) を
IA とかくことにする．
96 / 192勾配法は，k ∈ {0, 1, 2, · · · } に対して，試行点 xk ∈ S のまわりで，評価関
数 f が式 (3.3.8) のような近似 2 次関数 q (y) で近似されたときの Newton 法になっていた．そこで，問題 3.1.1 に対して，目的関数を式 (3.3.8) のように仮定して，不等式制約が勾配を用いた 1 次関数で近似された次のような問題を考えることにしよう．

97 / 192

問題 3.7.1 (制約つき問題に対する勾配法)問題 3.1.1 の試行点 xk ∈ S において f0 (xk ), fi1 (xk ) = 0, . . . ,fi|I | (xk ) = 0, g0 (xk ), gi1 (xk ), . . . , gi|I | (xk ) を既知とする．また，AAA ∈ Rd×d を正定値実対称行列，ca を正の定数とする．このとき，
1q (yg ) = min q (y) = y · (ca Ay) + g0 (xk ) · y + f0 (xk )y∈X2fi (xk ) + gi (xk ) · y ≤ 0 for i ∈ IA (xk )を満たす xk+1 = xk + yg を求めよ．

98 / 192

問題 3.7.1 は，2.2 節の最適化問題の分類によれば，2 次最適化問題に分類される．さらに，A は正定値対称実行列であることから凸最適化問題となる．
したがって，この問題に対する KKT 条件を満たす yg は問題 3.7.1 の最小点となる (図 3.13)．その yg をみつける方法について考えてみよう．

99 / 192

図 3.13: 制約つき問題に対する勾配法

100 / 192

問題 3.7.1 の Lagrange 関数を，X

LQ (y, λk+1 ) = q (y) +λi k+1 (fi (xk ) + gi (xk ) · y)

(3.7.3)i∈IA (xk )とおく．問題 3.7.1 の最小点 yg における KKT 条件は

ca Ayg + g0 (xk ) +X

λi k+1 gi (xk ) = 0X ′ ,(3.7.4)i∈IA (xk )fi (xk ) + gi (xk ) · yg ≤ 0 for i ∈ IA (xk ) ,(3.7.5)λi k+1 (fi (xk ) + gi (xk ) · yg ) = 0 for i ∈ IA (xk ) ,(3.7.6)

λi k+1 ≥ 0 for i ∈ IA (xk )(3.7.7)

101 / 192

となる．すべての i ∈ IA (xk ) に対して，不等式制約が有効であると仮定すれば，式 (3.7.4) と式 (3.7.5) は
!
!
!
⊤
ca A
G
yg
g0
=−
(3.7.8)G 0 R | I A | × |I A |λk+1(fi )i∈IAとなる．ただし，G⊤ = gi1 (xk ) · · ·
gi|I (x )| (xk )Akとする．ここで，gi1 , . . . , gi|I | が 1 次独立であれば，式 (3.7.8) は (yg , λk+1 )Aについて可解となる．この連立 1 次方程式の解に対して，

II (xk ) = {i ∈ IA (xk ) | λi k+1 < 0}(3.7.9)102 / 192

を無効な制約条件の集合とおき，II (xk ) ̸= ∅ のときには IA (xk ) \ II (xk ) を
IA (xk ) とおきなおし，式 (3.7.8) を再度解くことにする．このようにしてえられた (yg , λk+1 ) ∈ X × R|IA | は式 (3.7.4) から式 (3.7.7) を満たすことになる．このように，有効な制約のみを残しながら繰り返す方法は有効制約法とよばれる (たとえば，[2, Section 10.10.6, p. 447])．
一方，式 (3.7.8) を直接解く代わりに，i ∈ IA (xk ) ごとに fi に対して勾配法が使われた結果を用いる方法も考えられる．その方法は次のようである．
g0 , gi1 , . . . , gi|I | を用いて，個別に勾配法を適用する．すなわち，Aygi = − (ca A)−1 gi(3.7.10)103 / 192

が満たされるように yg0 , ygi1 , . . . , ygi|I | を求める．ここで，Lagrange 乗数A

λk+1 ∈ R|IA | を未知数として，
X
yg = yg (λk+1 ) = yg0 +λi k+1 ygi(3.7.11)i∈IA (xk )とおく．このとき，yg は式 (3.7.8) の 1 行目を満たすことになる．一方，
式 (3.7.8) の 2 行目は
gi1 · ygi1 · · · gi1 · ygi|I |λi1 k+1
A


..

..
..
...


.

.
.


λi|I | k+1
gi I · ygi1 · · · gi I · ygi I
| A|

| A|

| A|

A

104 / 192


fi1 + gi1 · yg0
..


= −
.

fi|I | + gi|I | · yg0
AAとなる．この式を(gi · ygj )(i,j)∈I 2 (λj k+1 )j∈IA = − (fi + gi · yg0 )i∈IA(3.7.12)Aとかくことにする．ここでも，gi1 , . . . , gi|I | が 1 次独立ならば，λk+1 はA
式 (3.7.12) により一意に決定されることになる．この連立 1 次方程式の解に対して，有効制約法を適用する．すなわち，式 (3.7.9) の II (xk ) が ∅ ではな
いときには IA (xk ) \ II (xk ) を IA (xk ) とおきなおし，式 (3.7.8) を再度解く

105 / 192

ことにする．このようにしてえられた (yg , λk+1 ) ∈ X × R|IA | は，式 (3.7.4)から式 (3.7.7) を満たすことになる．
また，式 (3.7.12) において，有効な制約関数 fi1 , . . . , fi|I | の値がすべて 0Aであれば，すべての yg0 , ygi1 , . . . , ygi|I | に任意の定数をかけても λk+1 は変A化しない．このことは，ステップサイズ ∥yg ∥X が適切に設定されていなくても，λk+1 が求められることを意味する．この関係は，3.7.2 項においてステッ
プサイズの初期値が与えられた大きさになるように ca を決定するときに使われる．
以上をまとめると，制約つき問題に対する勾配法は，式 (3.7.8) により探索ベクトル yg と Lagrange 乗数 λk+1 を直接解くか，あるいは i ∈ IA (xk ) ごとに式 (3.7.10) より ygi を解いて，それらを用いて式 (3.7.12) より λk+1 を求

106 / 192

め，それらを式 (3.7.11) に代入することにより yg を求めるかのいずれかの方法により，yg を更新していく反復法であるということができる．
具体的なアルゴリズムを示す前に，いくつかの状況について考えておこう．
一つは，問題 3.1.1 の不等式制約が等式制約 fi (x) = 0 におきかえられた状況である．実は，不等式制約が有効な場合には等式制約と同じ扱いになることから，この状況はいつも起こりえることになる．このような等式制約は，二つの不等式制約 fi (x) ≤ 0 および −fi (x) ≤ 0 に置き換えられる．しかし，これら二つの不等式制約が非線形の場合，それらを厳密に満たすように x を決めることは一般には困難である．そこで，正の定数 ϵi を定めて，|fi (x)| ≤ ϵi のように緩和する必要がある．あとで示されるアルゴリズムでは不等式制約のみが仮定されているので，ϵi を用いて制約を緩和する必要はな

107 / 192

いように思われる．しかしながら，不等式制約が有効な場合は等式制約
fi (x) = 0 と同じ意味となり，正の定数 ϵi によるチェックが必要となる．
もう一つは，あとに示されるアルゴリズムでは，初期点 x0 においてすべての不等式制約が満たされている状況を仮定する．このような状況が満たされていない場合には，次のステップを前処理として行うことで，すべての不等式制約を満たす x0 ∈ S を見つけることができる．見つからない場合には問題
設定を見直す必要がある．

0. 目的関数 f0 = 0 および g0 = 0Rd とおいて，すべての不等式制約が満たされるまで，あとのアルゴリズムで示される既定のステップを繰り返す．

108 / 192

§3.7.1 簡単なアルゴリズム

図 3.14: パラメータ調整なし制約つき問題に対する勾配法のアルゴリズム

109 / 192

アルゴリズム 3.7.2 (パラメータ調整なし制約つき問題に対する勾配法)問題 3.1.1 の極小点を次のようにして求める．

1. 初期点 x0 を f1 (x0 ) ≤ 0, . . . , fm (x0 ) ≤ 0 が満たされるように定める．
式 (3.7.10) の正定値行列 A とステップサイズを調整する正の定数 ca ，f0の収束判定に用いる正の定数 ϵ0 および f1 , . . . , fm の許容範囲を与える
正の定数 ϵ1 , . . . , ϵm を定める．また，k = 0 とおく．
2. 状態決定問題を解いて，xk において f0 (xk ), f1 (xk ), . . . , fm (xk ) を計算する．また，IA (xk ) = {i ∈ {1, · · · , m} | fi (xk ) ≥ −ϵi }とおく．
110 / 192

3. f0 , fi1 , . . . , fi|I | に対する随伴問題を解いて，xk において g0 , gi1 , . . . ,A
gi|I | を計算する．
A

4. 式 (3.7.10) で yg0 , ygi1 , . . . , ygi|I | を計算する．
A

5. 式 (3.7.12) で λk+1 を求める．式 (3.7.9) の II (xk ) が ∅ ではないときには，IA (xk ) \ II (xk ) を IA (xk ) とおきなおし，式 (3.7.12) を再度解く．
6. 式 (3.7.11) で yg を求め，xk+1 = xk + yg とおき，状態決定問題を解いて，f0 (xk+1 ), f1 (xk+1 ), . . . , fm (xk+1 ) を計算する．また，IA (xk+1 ) = {i ∈ {1, · · · , m} | fi (xk+1 ) ≥ −ϵi }とおく．

111 / 192

7. 終了条件 |f0 (xk+1 ) − f0 (xk )| ≤ ϵ0 を判定する．
• 終了条件が満たされたとき，(8) に進む．
• そうではないとき，k + 1 を k に代入し，(3) に戻る．

8. 計算を終了する．

112 / 192

アルゴリズム 3.7.2 を使って，第 1 章の例題 1.1.6 (平均コンプライアンス最小化問題の数値例) に対する試行点を求めてみよう．
例題 3.7.3 (平均コンプライアンス最小化問題の数値例)⊤

例題 1.1.6 に対して，初期点を a(0) = (1/2, 1/2) とおき，アルゴリズム
3.7.2 を使って k ∈ {0, 1} のときの試行点を求めよ．ただし，必要となる行
列や数値は適当に定めよ．

113 / 192

(a) 試行点の推移

114 / 192

(b) 評価関数の履歴(c) 最小点からの距離 ∥ak − a∥R2

図 3.15: パラメータ調整なし制約つき問題に対する勾配法による平均コンプライア
ンス最小化問題の数値例

115 / 192

解答

平均コンプライアンス f˜0 (a) と体積に対する制約関数 f1 (a) は，それぞれ

41f˜0 (a) =
+ ,
a1 a2

(3.7.13)

f1 (a) = a1 + a2 − 1(3.7.14)で与えられる．また，それらの断面積微分は

g0 = −
g1 =

4
a21
1
a22

!
1
1

!
,

(3.7.15)(3.7.16)116 / 192

となる．アルゴリズム 3.7.2 に沿って，数値を求めていく．ただし，ステップ数 k のときの設計変数を a(k) とかくことにする．bg0(k) , bg1(k) および λ1(k) も同様とする．


1. 初期点 a(0) = (1/2, 1/2)⊤ では f1 a(0) = 0 は満たされる．式 (3.7.10) の正定値行列を A = I ，ステップサイズを調整する正の定数を ca = 100 (あとで示される計算より，ステップサイズ bg(0) R2 = 0.0848528 となった)，

ϵ0 = 10−3 f˜0 a(0) ，ϵ1 = 10−3 とおく．また，k = 0 とおく．


2. 式 (3.7.13) と式 (3.7.14) より，f˜0 a(0) = 10 と f1 a(0) = 0 が得られる．また，IA a(0) = {1} とおく．
3. 式 (3.7.15) と式 (3.7.16) より，g0(0) = − (16, 4)⊤ , g1(0) = (1, 1)⊤ が得られる．
4. 式 (3.7.10) より，bg0(0) = (0.16, 0.04)⊤ , bg1(0) = − (0.01, 0.01)⊤ が得られる．

117 / 192

5. 式 (3.7.12) で λ1(1) = 10 が得られる．
6. 式 (3.7.11) で bg(0) = (0.06, −0.06)⊤ を得て，

a(1) = a(0) + bg(0) = (0.56, 0.44)⊤ とおき，f˜0 a(1) = 9.41558, f1 a(1) = 0
が得られる．また，IA a(1) = {1} とおく．


7. f˜0 a(1) − f˜0 a(0) = 0.584416 ≥ ϵ0 = 0.01 より，終了条件は満たされないと判定し，1 を k に代入し，(3) に戻る．
3. 式 (3.7.15) と式 (3.7.16) より，g0(1) = − (12.7551, 5.16529)⊤ , g1(1) = (1, 1)⊤が得られる．
4. 式 (3.7.10) より，bg0(1) = (0.127551, 0.0516529)⊤ , bg1(1) = − (0.01, 0.01)⊤ が得られる．

118 / 192

5. 式 (3.7.12) で λ1(2) = 8.9602 が得られる．
6. 式 (3.7.11) で bg(1) = (0.0379491, −0.0379491)⊤ を得て，
a(2) = a(1) + bg(1) = (0.597949, 0.402051)⊤ とおき，f˜0 a(2) = 9.17678,
f1 a(2) = 0 が得られる．また，IA a(1) = {1} とおく．


7. f˜0 a(2) − f˜0 a(1) = 0.238804 ≥ ϵ0 = 0.01 より，終了条件は満たされないと判定し，2 を k に代入し，(3) に戻る．
図 3.15 にこれらとその後の結果を示す．ただし，f0 init は k = 0 のときの f0 の値を示す．
□

119 / 192

例題 3.7.4 (体積最小化問題の数値例)
目的関数と制約関数をそれぞれ

f0 (a) = a1 + a2 ,41+−9f˜1 (a) =a1 a2(3.7.17)(3.7.18)

とおく．このとき，f˜1 (a) ≤ 0 を満たす制約のもとで f0 (a) を最小化する問
題 (平均コンプライアンス制約つき体積最小化問題) に対して，初期点をa(0) = (16/31, 4/5)⊤ ≈ (0.516, 0.8)⊤ とおき，アルゴリズム 3.7.2 を使って
k ∈ {0, 1} のときの試行点を求めよ．必要となる行列や数値は適当に定めよ．

120 / 192

(a) 試行点の推移

121 / 192

(b) 評価関数の履歴(c) 最小点からの距離 ∥ak − a∥R2

図 3.16: パラメータ調整なし制約つき問題に対する勾配法による体積最小化問題の数値例

122 / 192

解答

評価関数 f0 (a) と f˜1 (a) の断面積微分はそれぞれ

g0 =
g1 = −

!
1
,
1
4
a21
1
a22

(3.7.19)!
(3.7.20)となる．アルゴリズム 3.7.2 に沿って，数値を求めていく．ここでも，ステップ数 kのときの設計変数を a(k) とかくことにする．bg0(k) , bg1(k) および λ1(k) も同様とする．

123 / 192
1. 初期点 a(0) = (16/31, 4/5)⊤ のとき f˜1 a(0) = 0 は満たされる．式 (3.7.10) の正定値行列を A = I ，ステップサイズを調整する正の定数を ca = 10 (あとで示される計算より，ステップサイズ bg(0) R2 = 0.089113 となった)，

ϵ0 = 10−3 f0 a(0) ，ϵ1 = 9 × 10−3 とおく．また，k = 0 とおく．


2. 式 (3.7.17) と式 (3.7.18) より，f0 a(0) = 1.31613 と f˜1 a(0) = 0 が得られ
る．また，IA a(0) = {1} とおく．
3. 式 (3.7.15) と式 (3.7.16) より，g0(0) = (1, 1)⊤ , g1(0) = − (15.0156, 1.5625)⊤ が得られる．
4. 式 (3.7.10) より，bg0(0) = − (0.1, 0.1)⊤ , bg1(0) = (1.50156, 0.15625)⊤ が得られる．

124 / 192

5. 式 (3.7.12) で λ1(1) = 0.0727397 が得られる．
6. 式 (3.7.11) で bg(0) = (0.00922315, −0.0886344)⊤ を得て，
a(1) = a(0) + bg(0) = (0.525352, 0.711366)⊤ とおき，f0 a(1) = 1.23672,
f˜1 a(1) = 0.019687 が得られる．また，IA a(1) = {1} とおく．


7. f0 a(1) − f0 a(0) = 0.0794113 ≥ ϵ0 = 0.00131613 より，終了条件は満たされないと判定し，1 を k に代入し，(3) に戻る．
3. 式 (3.7.15) と式 (3.7.16) より，g0(1) = (1, 1)⊤ , g1(1) = − (14.493, 1.97612)⊤ が得られる．
4. 式 (3.7.10) より，bg0(1) = − (0.1, 0.1)⊤ , bg1(1) = (1.4493, 0.197612)⊤ が得られる．

125 / 192

5. 式 (3.7.12) で λ1(2) = 0.0778958 が得られる．
6. 式 (3.7.11) で bg(1) = (0.0128945, −0.0846068)⊤ を得て，
a(2) = a(1) + bg(1) = (0.538247, 0.626759)⊤ とおき，f0 a(2) = 1.16501,
f˜1 a(2) = 0.0270467 が得られる．また，IA a(1) = {1} とおく．


7. f0 a(2) − f0 a(1) = 0.0717123 ≥ ϵ0 = 0.00131613 より，終了条件は満たされないと判定し，2 を k に代入し，(3) に戻る．
図 3.16 にこれらとそのあとの結果を示す．

□

126 / 192
例題 3.7.3 では，f1 a(1) = f1 a(2) = 0 のように，制約は常に満たされていた．しかし，例題 3.7.4 では，f˜1 a(1) = 0.019687 およびf˜1 a(2) = 0.0459682 のように，制約は満たされておらず，反復を繰り返すごとにその超過量は拡大した．このようなことを防ぐ方法については，次の項で考えることにしよう．

127 / 192

§3.7.2 複雑なアルゴリズム
次に，簡単なアルゴリズム (アルゴリズム 3.7.2) に次のような機能を追加することを考えよう．

(i) ステップサイズの初期値 ϵg (あるいは目的関数の減少率 α) を与えて，∥yg ∥X = ϵg となるように ca を決定する機能(ii) 設計変数が xk+1 に更新されたとき，i ∈ IA (xk+1 ) に対して，|fi (xk+1 )| ≤ ϵi と λi k+1 ≥ 0 が満たされるように λk+1 = (λi k+1 )i∈IA (xk+1 )を修正する機能(iii) 目的関数 f0 の収束判定値 ϵ0 に対して，制約関数 f1 , . . . , fm の許容値
ϵ1 , . . . , ϵm を適切化する機能(iv) 大域的収束性が保証されるようにステップサイズ ∥yg ∥X を調整する機能
128 / 192

上記 (i) は，アルゴリズム 3.3.5 と同様に，式 (3.3.7) で ca を求めることで解決される．あとで示されるアルゴリズム 3.7.6 では，ステップ (6) に取り入れられている．
また，上記 (ii) については次のような方法が考えられる．アルゴリズム
3.7.2 のステップ (5) で計算された λk+1 は制約つき問題に対する勾配法 (問題 3.7.1) の KKT 条件は満たしていても，有効な不等式制約関数の非線形性により，xk+1 において指定された許容範囲で満たしているとは限らない．

xk+1 で不等式制約が指定された許容範囲で満たすためには，λk+1 が修正されて，それにより式 (3.7.11) で yg が修正され，その結果，xk+1 は xk + ygに更新される必要がある．ここでは，λk+1 = λ0 k+1 とおき，l ∈ {0, 1, 2, · · · }129 / 192

に対して λl k+1 を与えて λk+1 l+1 を求める計算を繰り返すことを考える．そこでは，非線形方程式の解法である Newton-Raphson 法 (問題 3.5.6) が使われる．
その方法は次のようである．i ∈ IA (xk+1 ) に対して fi (xk + yg (λl k+1 )) をf¯i (λl k+1 ) とかくことにする．Newton-Raphson 法の説明では，k ∈ {0, 1, 2, · · · } に対して式 (3.5.7) の関数 f (xk + yg ) = 0Rd を考えた．ここでは，l ∈ {0, 1, 2, · · · } に対して f¯i (λl k+1 + δλ) i∈I = 0R|IA | を考える．まAた，yg (λl k+1 ) は式 (3.7.11) で定義された λl k+1 の 1 次関数であることを考慮して，式 (3.5.7) の G (xk ) の代わりに (gi (λl k+1 ) · ygj (λl k+1 ))(i,j)∈I 2 を考Aえる．このとき，式 (3.5.8) に代わって，

δλ = (δλj )j∈IA
130 / 192

= − (gi (λl k+1 ) · ygj (λl k+1 ))−1(i,j)∈I 2 (fi (λl k+1 ))i∈IA(3.7.21)Aが得られる．式 (3.7.21) の δλ を用いて，λk+1 は λk+1 l+1 = λl k+1 + δλ に更新されることになる．さらに，式 (3.7.11) により yg は yg (λk+1 l+1 ) に修正される．その結果，xk+1 = xk + yg は xk+1 l+1 = xk + yg (λk+1 l+1 ) に更新される．この更新は，あとで示されるアルゴリズム 3.7.6 のステップ (11) の中で使われている．
例題 3.7.4 に対して，λk+1 を修正する方法を試してみよう．

131 / 192

例題 3.7.5 (体積最小化問題の数値例)

例題 3.7.4 では，f˜1 a(1) = 0.019687 であった．式 (3.7.21) を用いて，

λ1(1) = 0.0727397 を修正し，f˜1 a(1)[l] ≤ 10−4 が成り立つような試行点
a(1)[l] を求めよ．ただし，ステップ数 k において修正回数 l のときの λ1 を
λ1(k+1)[l] とかくことにする．
解答

式 (3.7.21) を例題 3.7.4 に適用すれば，

f˜1 a(1)[l]δλ1 = −
g1(0)[l] · bg1(0)[l](3.7.22)132 / 192

となる．l = 0 のとき，a(1)[0] = a(1) , g1(0)[0] = g1(0) および bg1(0)[0] = bg1(0) より，
δλ1 = 0.000863807 が得られる．そこで，λ1 をλ1(1)[1] = λ1 + δλ1 = 0.0736035に更新する．この λ1(1)[1] を用いて，式 (3.7.11) で bg(0) を再計算すれば，

bg(0)[1] = (0.0105202, −0.0884995)⊤となる．この探索ベクトルを用いて設計変数を更新すれば，

a(1)[1] = a(1) + bg(0)[1] = (0.526649, 0.711501)⊤
となる．このとき，f˜1 a(1)[1] = 0.00066837 > 10−4 となる．許容制約条件は満たされない．
133 / 192

そこで，l = 1 とおいて，上記のステップを繰り返す．式 (3.7.22) を適用し，f˜1 a(1)[1]δλ1 = −
= 0.000029326
g1(0)[1] · bg1(0)[1]が得られる．そこで，λ1 をλ1(1)[2] = λ1(1)[1] + δλ1 = 0.0736328に更新する．この λ1(1)[2] を用いて，式 (3.7.11) で bg(0) を再計算すれば，

bg(0)[2] = (0.0105202, −0.0884995)⊤

134 / 192

となる．この探索ベクトルを用いて設計変数を更新すれば，

a(1)[2] = a(1) + bg(0)[2] = (0.526693, 0.711505)⊤
となる．このとき，f˜1 a(1)[2] = 0.0000243138 ≤ 10−4 となる．

□

さらに，上記 (iii) については，次のような方法が考えられる．原問題 (問題3.1.1) の Lagrange 関数は

L (x, λ) = f0 (x) +X

λi fi (x)(3.7.23)i∈IA (x)135 / 192

で与えられる．i ∈ IA (xk ) に対して，|fi (xk )| ≤ ϵi が満たされているとき，L (xk , λk ) ≈ f0 (xk ) が成り立つためには

ϵ0 ≫

X

λki ϵi(3.7.24)i∈IA (xk )である必要がある．そこで，この条件が満たされるようにするために，σ を 1
よりも十分小さい正の定数として，制約許容値の規準を，すべてのi ∈ IA (xk ) に対して，

ϵi ≤

σϵ0
|IA (xk )| λki(3.7.25)

136 / 192

が成り立つことであるとする．この条件が満たされない i がある場合には，ϵiに σϵ0 / (|IA (xk )| λki ) よりも小さな値を代入することで規準が満たされるよ
うにする．このような制約許容値の規準は，このあとで示されるアルゴリズ
ム 3.7.6 のステップ (12) で使われている．
一方，上記 (iv) については，Lagrange 関数に対して Armijo の規準と Wolfeの規準が満たされるようにステップサイズ ∥yg ∥X (すなわち ca ) を決定する方法が考えられる．大域的収束性を保証する根拠となった定理 3.4.7 では，制約なしの問題を対象にしていた．ここでは，上記 (ii) と (iii) により，xk とxk+1 = xk + yg において Lagrange 乗数と不等式制約に対する KKT 条件が満たされていると仮定する (あとで示されるアルゴリズム 3.7.6 では，ステップ
サイズが調整されたあとで Lagrange 乗数と不等式制約に対する KKT 条件が137 / 192

満たされるようになっている)．このとき，Lagrange 関数は f0 と一致し，制約なし問題に対する Armijo の規準と Wolfe の規準を適用することが可能となる．実際に，それらの規準を示しておこう．原問題 (問題 3.1.1) の Lagrange
関数を式 (3.7.23) とおく．f0 (xk ), fi1 (xk ), . . . , fi|I | (xk ) の勾配を g0 (xk ),A
gi1 (xk ), . . . , gi|I | (xk ) とかき，f0 (xk + yg ), fi1 (xk + yg ), . . . ,A
fi|I | (xk + yg ) の勾配を g0 (xk + yg ), gi1 (xk + yg ), . . . , gi|I | (xk + yg ) とかAA
くことにする．このとき，Armijo の規準は ξ ∈ (0, 1) に対してL (xk + yg , λk+1 ) − L (xk , λk )X≤ ξ g0 (xk ) +λki gi (xk ) · yg

(3.7.26)i∈IA (xk )138 / 192

となる．また，Wolfe の規準は µ (0 < ξ < µ < 1) に対して
Xµ g0 (xk ) +λki gi (xk ) · yg

i∈IA (xk )≤ g0 (xk + yg ) +Xλi k+1 gi (xk + yg ) · yg

(3.7.27)i∈IA (xk+1 )で与えられる．これらの規準は，このあとで示されるアルゴリズム 3.7.6 のス
テップ (8) と (10) で使われている．
以上のような方法を組み込んだアルゴリズムの一例を次に示す．図 3.17 にその流れ図を示す．

139 / 192

図 3.17: パラメータ調整あり制約つき問題に対する勾配法のアルゴリズム
140 / 192

アルゴリズム 3.7.6 (パラメータ調整あり制約つき問題に対する勾配法)問題 3.1.1 の極小点を次のようにして求める．

1. 初期点 x0 を f1 (x0 ) ≤ 0, . . . , fm (x0 ) ≤ 0 が満たされるように定める．
式 (3.7.10) の正定値行列 A と初期ステップサイズ ϵg (あるいは目的関数の減少率 α)，f0 の収束判定値 ϵ0 ，f1 , . . . , fm の許容範囲の初期値 ϵ1 ,. . . , ϵm ，Armijo と Wolfe の規準値 ξ と µ (0 < ξ < µ < 1) および制約許
容値の規準値 σ (≪ 1) を定める．また，ca = 1，k = 0 および l = 0 とおく．
2. 状態決定問題を解いて，xk において f0 (xk ), f1 (xk ), . . . , fm (xk ) を計算する．また，次のようにおく．
IA (xk ) = {i ∈ {1, · · · , m} | fi (xk ) ≥ −ϵi }141 / 192

3. f0 , fi1 , . . . , fi|I | に対する随伴問題を解いて，xk において g0 , gi1 , . . . ,A
gi|I | を計算する．
A

4. 式 (3.7.10) で yg0 , ygi1 , . . . , ygi|I | を計算する．
A

5. 式 (3.7.12) で λk+1 = λl k+1 を求める．式 (3.7.9) の II (xk ) が ∅ ではな
いときには，IA (xk ) \ II (xk ) を IA (xk ) とおきなおし，式 (3.7.12) を再度解く．
6. 式 (3.7.11) で yg を求める．yg = ȳg とおき，式 (3.3.7) で ca を求める．
また，i ∈ IA (xk ) に対して ȳgi /ca を ygi に代入する．

142 / 192

7. xk+1 l = xk + yg (λl k+1 ) とおき，状態決定問題を解いて，f0 (xk+1 l ),f1 (xk+1 l ), . . . , fm (xk+1 l ) を計算する．また，IA (xk+1 ) = {i ∈ {1, · · · , m} | fi (xk+1 l ) ≥ −ϵi }とおく．

8. λk+1 = λl k+1 とおき，Armijo の規準 (式 (3.7.26)) を判定する．
• 満たされていれば，次に進む．
• そうではないとき，α > 1 として αca を ca に代入し，yg0 /ca , ygi1 /ca ,. . . , ygi|I | /ca を yg0 , ygi1 , . . . , ygi|I | に代入し，(7) に戻る．
AA

143 / 192

9. xk+1 において g0 , gi1 , . . . , gi|I | を計算する．
A

10. λk+1 = λl k+1 とおき，Wolfe の規準 (式 (3.7.27)) を判定する．
• 満たされていれば，次に進む．
• そうではないとき，β ∈ (0, 1) として βca を ca に代入し，βyg0 , βygi1 ,. . . , βygi|I | を yg0 , ygi1 , . . . , ygi|I | に代入し，(7) に戻る．
AA

11. すべての i ∈ IA (xk+1 ) に対して，|fi (xk+1 )| ≤ ϵi を判定する．
• 満たされていれば，次に進む．
• そうではないとき，xk+1 において g0 , gi1 , . . . , gi|I | を計算し，A
式 (3.7.10) で yg0 , ygi1 , . . . , ygi|I | を計算し，式 (3.7.21) で δλ を求め，
A
λk+1 l+1 = λl k+1 + δλ とおく．l + 1 を l に代入して (7) に戻る．

144 / 192

12. すべての i ∈ IA (xk+1 ) に対して，制約許容値の規準 (式 (3.7.25)) を判定する．
• 満たされていれば，次に進む．
• そうではないとき，満たされない i に対して，β ∈ (0, 1) として
βσϵ0 / (|IA (xk+1 )| λi k+1 ) を ϵi に代入し，(7) に戻る．

13. 終了条件 |f0 (xk+1 ) − f0 (xk )| ≤ ϵ0 を判定する．
• 終了条件が満たされたとき，(14) に進む．
• そうではないとき，k + 1 を k に代入し，l = 0 とおき，(3) に戻る．

14. 計算を終了する．

145 / 192

3.8 制約つき問題に対するNewton 法§3.8 制約つき問題に対する Newton 法

評価関数の x の変動に対する Hesse 行列が得られる場合には，勾配法をNewton 法に変更することができる．その方法を制約つき問題に対するNewton 法とよぶことにする．ここでは，f0 , f1 , . . . , fm の Hesse 行列を H0 ,H1 , . . . , Hm とかくことにする．また，混乱がないときには IA (xk ) を IA とかくことにする．

147 / 192

制約つき問題に対する勾配法 (問題 3.7.1) に対して定義された式 (3.7.3) のLagrange 関数 LQ を，ここでは，

LQ (y, λk+1 )1= y · (H0 (xk ) y) + g0 (xk ) · y + f0 (xk )
2

X 
1
+
λi k+1 (fi + gi (xk ) · y) + λik y · (Hi (xk ) y)2

(3.8.1)i∈IA (xk )におきかえる．ここで，λk = (λik )i は前のステップでえられた Lagrange 乗数とする．k = 0 のときには，制約つき問題に対する勾配法で使われた方法で決定されると仮定する．この LQ は，次の問題の Lagrange 関数となっている．

148 / 192

問題 3.8.1 (制約つき問題に対する Newton 法)問題 3.1.1 の試行点 xk ∈ X において，Lagrange 乗数 λk ∈ R|IA | は
式 (3.7.5) から式 (3.7.7) (ただし，k + 1 を k とみなす) を満たすとする．また，f0 (xk ), fi1 (xk ) = 0, . . . , fi|I | (xk ) = 0 および g0 (xk ), gi1 (xk ), . . . ,A
gi|I | (xk ) と H0 (xk ), Hi1 (xk ), . . . , Hi|I | (xk ) を既知として，A

HL (xk ) = H0 (xk ) +AXλik Hi (xk )(3.8.2)i∈IA (xk )とおく．このとき，

149 / 192

問題 3.8.1 (制約つき問題に対する Newton 法)1
q (yg ) = min q (y) = y · (HL (xk ) y) + g0 (xk ) · y + f0 (xk )y∈X2fi (xk ) + gi (xk ) · y ≤ 0 for i ∈ IA (xk )を満たす xk+1 = xk + yg を求めよ．
問題 3.8.1 は，2 次最適化問題に分類される．HL (xk ) は正定値実対称行列とは限らないが，そのような性質が満たされたときは，問題 3.8.1 は凸最適化

150 / 192

問題となる．ここでも，この問題に対する KKT 条件を用いて，yg をみつける方法について考えてみよう．
問題 3.8.1 の最小点 yg における KKT 条件は，

HL (xk ) yg + g0 (xk ) +X

λi k+1 gi (xk ) = 0X ′ ,(3.8.3)i∈IA (xk )fi (xk+1 ) = fi (xk ) + gi (xk ) · yg ≤ 0 for i ∈ IA (xk )(3.8.4)

λi k+1 (fi (xk ) + gi (xk ) · yg ) = 0 for i ∈ IA (xk ) , (3.8.5)
λi k+1 ≥ 0 for i ∈ IA (xk )(3.8.6)

151 / 192

となる．これらを満たす (yg , λk+1 ) ∈ X × R|IA | は次のようにして求められる．すべての i ∈ IA (xk ) に対して，不等式制約が有効であると仮定すれば，
式 (3.8.3) と式 (3.8.4) は

HL
G

G⊤

!

0 R |I A |× |I A |

yg
λk+1

!

g0
=−
(fi )i∈IA!
(3.8.7)となる．ただし，G ⊤ = g i 1 , . . . , g i |I |A

152 / 192

とする．gi1 , . . . , gi|I | が 1 次独立で，かつ HL が正則ならば，式 (3.8.7) はA(yg , λk+1 ) について可解となる．この連立 1 次方程式の解に対して，

II (xk ) = {i ∈ IA (xk ) | λi k+1 < 0}(3.8.8)を無効な制約条件の集合とおき，II (xk ) ̸= ∅ のときには IA (xk ) \ II (xk ) を
IA (xk ) とおきなおし，式 (3.8.7) を再度解くことにする．このようにしてえられた (yg , λk+1 ) ∈ X × R|IA | は，式 (3.8.3) から式 (3.8.6) を満たすことになる．

153 / 192

また，制約つき問題に対する勾配法 (3.7 節) においても示されたように，
式 (3.8.7) の連立 1 次方程式を直接解く代わりに，次のような方法も考えられ
る．i ∈ IA (xk ) ごとに gi に対して
−1
ygi = −HLgi

(3.8.9)が満たされるように yg0 , ygi1 , . . . , ygi|I | を求める．さらに，式 (3.7.12) でA
λk+1 を求める．ただし，II (xk ) が ∅ ではないときには IA (xk ) \ II (xk ) を
IA (xk ) とおきなおし，式 (3.7.8) を再度解くことにする．それらの結果を用いれば，yg は式 (3.7.11) によって 求められることになる．
制約つき問題に対する勾配法とこの方法の違いは ca A が HL におきかえられただけである．しかし，この方法でえられた探索ベクトル yg は，評価関154 / 192

数の Hesse 行列を用いていることから，注意 3.5.4 であげた Newton 法の性質が成り立つことが期待される．ただし，次のことに注意する必要がある．
注意 3.8.2 (制約つき問題に対する Newton 法)問題 3.8.1 の評価関数 q には，制約関数の Hesse 行列が前のステップのLagrange 乗数が乗じられて加えられている．その結果，制約条件には Hesse
行列が使われていない．このことから，制約関数の非線形性がつよく，KKT
条件を満たす Lagrange 乗数がおおきく変化する問題に対しては，ステップ
サイズを小さくしなければ，収束しない場合がある．
さらに，評価関数の 2 階微分が Hesse 勾配によって得られる場合の Newton
法は次のようになる．問題 3.8.1 は次の問題に置き換えられる．

155 / 192

問題 3.8.3 (Hesse 勾配を用いた Newton 法)

X = Rd とする．A ∈ Rd×d と ca を正定値実対称行列と正の定数とする．問題 3.1.1 の試行点 xk ∈ X において，Lagrange 乗数 λk ∈ R|IA | は式 (3.7.5)から式 (3.7.7) (ただし，k + 1 を k とみなす) を満たすとする．また，
f0 (xk ), fi1 (xk ) = 0, . . . , fi|I | (xk ) = 0 および勾配 g0 (xk ), gi1 (xk ), . . . ,A
gi|I | (xk )，探索ベクトル ȳg および Hesse 勾配 gH0 (xk , ȳg ), gHi1 (xk , ȳg ),A. . . , gHi|I | (xk , ȳg ) を既知として，A

gHL (xk , ȳg ) = gH0 (xk , ȳg ) +X

λik gHi (xk , ȳg )(3.8.10)i∈IA (xk )156 / 192

問題 3.8.3 (Hesse 勾配を用いた Newton 法)
とおく．このとき，1q (yg ) = min q (y) = y · (ca Ay) + (g0 (xk ) + gHL (xk , ȳg )) · yy∈X2+ f0 (xk )

fi (xk ) + gi (xk ) · y ≤ 0 for i ∈ IA (xk )を満たす xk+1 = xk + yg を求めよ．

157 / 192

問題 3.8.3 の解を求めるために，評価関数ごとに求めた探索ベクトルを求める方法を採用する場合には， 式 (3.8.9) を

ygi = − (ca A)−1 (gi + gHi )(3.8.11)におきかえることで Newton 法と同じアルゴリズムが利用可能である．

158 / 192

§3.8.1 簡単なアルゴリズム

上でみてきたことをふまえて，制約つき問題に対する Newton 法の考え方による簡単なアルゴリズムについて考えてみよう．図 3.18 にその流れ図を示す．ここでも，i ∈ IA (xk ) ごとに gi を用いて式 (3.8.9) で ygi を求める方法
を用いることにする．

159 / 192

図 3.18: 制約つき問題に対する Newton 法のアルゴリズム

160 / 192

アルゴリズム 3.8.4 (制約つき問題に対する Newton 法)問題 3.1.1 の極小点を次のようにして求める．

1. 初期点 x0 を f1 (x0 ) ≤ 0, . . . , fm (x0 ) ≤ 0 が満たされるように定める．
f0 の収束判定に用いる収束判定に用いる正の定数 ϵ0 および f1 , . . . , fmの許容範囲を与える正の定数 ϵ1 , . . . , ϵm を定める．また，Newton 法を開始するまでの繰り返し数 kN を定める．k = 0 とおく．
2. 状態決定問題を解いて，f0 (xk ), f1 (xk ), . . . , fm (xk ) を計算する．また，IA (xk ) = {i ∈ {1, · · · , m} | fi (xk ) ≥ −ϵi }とおく．

161 / 192

3. k < kN のとき次をおこなう．
(3.1) f0 , fi1 , . . . , fi|I | に対する随伴問題を解いて，xk において g0 , gi1 , . . . ,A
gi|I | を計算する．
A(3.2) 式 (3.7.10) で yg0 , ygi1 , . . . , ygi|I | を計算する．
A(3.3) 式 (3.7.12) で λk+1 を求める．式 (3.7.9) の II (xk ) が ∅ ではないときには，IA (xk ) \ II (xk ) を IA (xk ) とおきなおし，式 (3.7.12) を再度解く．
(3.4) 式 (3.7.11) で yg を求め，xk+1 = xk + yg とおき，状態決定問題を解いて，
f0 (xk+1 ), f1 (xk+1 ), . . . , fm (xk+1 ) を計算する．また，次のようにおく．
IA (xk+1 ) = { i ∈ {1, · · · , m} | fi (xk+1 ) ≥ −ϵi }(3.5) k + 1 を k に代入する．k < kN のとき (3.1) に戻る．そうでないとき，(4)に進む．
162 / 192

4. f0 , fi1 , . . . , fi|I | に対する随伴問題を解いて，xk において，g0 , gi1 , . . . ,A
gi|I | および H0 , Hi1 , . . . , Hi|I | を計算する．
A

A

5. 式 (3.8.9) で yg0 , ygi1 , . . . , ygi|I | を計算する．
A

6. 式 (3.7.12) で λk+1 を求める．式 (3.7.9) の II (xk ) が ∅ ではないときには，IA (xk ) \ II (xk ) を IA (xk ) とおきなおし，式 (3.7.12) を再度解く．
7. 式 (3.7.11) で yg を求め，xk+1 = xk + yg とおき，状態決定問題を解いて，f0 (xk+1 ), f1 (xk+1 ), . . . , fm (xk+1 ) を計算する．また，IA (xk+1 ) = {i ∈ {1, · · · , m} | fi (xk+1 ) ≥ −ϵi }とおく．

163 / 192

8. 終了条件 |f0 (xk+1 ) − f0 (xk )| ≤ ϵ0 を判定する．
• 終了条件が満たされたとき，(9) に進む．
• そうではないとき，k + 1 を k に代入し，(4) に戻る．

9. 計算を終了する．

164 / 192

アルゴリズム 3.8.4 を使って，第 1 章の例題 1.1.6 に対する試行点を求めてみよう．
例題 3.8.5 (平均コンプライアンス最小化問題の数値例)⊤

例題 1.1.6 に対して，初期点を a(0) = (1/2, 1/2) とおき，アルゴリズム
3.8.4 を使って k ∈ {0, 1} のときの試行点を求めよ．ただし，kN は可能な限り小さくとり，それ以外の必要となる数値は適当に定めよ．

165 / 192

(a) 試行点の推移

166 / 192

(b) 評価関数の履歴(c) 最小点からの距離 ∥ak − a∥R2

図 3.19: Newton 法による平均コンプライアンス最小化問題の数値例

167 / 192

解答 平均コンプライアンス f˜0 (a) と体積に対する制約関数 f1 (a) は，それぞれ
式 (3.7.13) と式 (3.7.14) で与えられる．また，それらの断面積微分は式 (3.7.15) と式 (3.7.16) で与えられる．f˜0 (a) の Hesse 行列は，

H0 =

8/a31
0
0
2/a32

!
(3.8.12)となる．また，H1 = 0R2×2 より，式 (3.8.2) において λ1 は不要となり，kN = 0 とおくことができる．アルゴリズム 3.8.4 に沿って，数値を求めていく．ここでも，ス
テップ数 k のときの設計変数を a(k) とかくことにする．bg0(k) , bg1(k) および λ1(k)も同様とする．

168 / 192
1. 初期点 a(0) = (1/2, 1/2)⊤ では f1 a(0) = 0 は満たされる．

ϵ0 = 10−3 f˜0 a(0) , ϵ1 = 10−6 とおく．また，k = 0 とおく．


2. 式 (3.7.13) と式 (3.7.14) より，f˜0 a(0) = 10 と f1 a(0) = 0 が得られる．また，IA a(0) = {1} とおく．
3. k = kN なので，先に進む．
4. 式 (3.7.15) と式 (3.7.16) より，g0(0) = − (16, 4)⊤ , g1(0) = (1, 1)⊤ が得られる．
5. 式 (3.8.9) より，bg0(0) = (1/4, 1/4)⊤ , bg1(0) = − (1/64, 1/16)⊤ が得られる．
6. 式 (3.7.12) で λ1(1) = 6.4 が得られる．

169 / 192

7. 式 (3.7.11) で bg(0) = (0.15, −0.15)⊤ を得て，

a(1) = a(0) + bg(0) = (0.65, 0.35)⊤ とおき，f˜0 a(1) = 9.01099, f1 a(1) = 0
が得られる．また，IA a(1) = {1} とおく．


8. f˜0 a(1) − f˜0 a(0) = 0.989011 ≥ ϵ0 = 0.01 より，終了条件は満たされないと判定し，1 を k に代入し，(4) に戻る．
4. 式 (3.7.15) と式 (3.7.16) より，g0(1) = − (9.46746, 8.16327)⊤ , g1(1) = (1, 1)⊤が得られる．
5. 式 (3.8.9) より，bg0(1) = (0.325, 0.175)⊤ , bg1(1) = − (0.0343281, 0.0214375)⊤が得られる．
6. 式 (3.7.12) で λ1(2) = 8.9661 が得られる．

170 / 192

7. 式 (3.7.11) で bg(1) = (0.0172107, −0.0172107)⊤ を得て，
a(2) = a(1) + bg(1) = (0.667211, 0.332789)⊤ とおき，f˜0 a(2) = 9.00001,

f1 a(2) = 1.11022 × 10−16 が得られる．また，IA a(1) = {1} とおく．


8. f˜0 a(2) − f˜0 a(1) = 0.010977 ≥ ϵ0 = 0.01 より，終了条件は満たされないと判定し，2 を k に代入し，(4) に戻る．
図 3.19 にこれらとそのあとの結果を示す．k = 3 のとき，f˜0 a(3) − f˜0 a(2) = 0.0000119968 ≤ ϵ0 = 0.01 より，終了条件は満たされた．

□

171 / 192

さらに，評価関数の 2 階微分が Hesse 勾配によって得られる場合のアルゴ
リズムは，アルゴリズム 3.8.4 のステップ (4) と (5) を次のように修正したものとなる．

4. xk において，f0 , fi1 , . . . , fi|I | に対する随伴問題を解いて，g0 , gi1 , . . . ,A
gi|I | を計算する．また，f0′ , fi′1 , . . . , fi′ I に対する随伴問題を解いて，
A

gH0 , gHi1 , . . . , gHi|I | を計算する．

| A|

A

5. 式 (3.8.11) で yg0 , ygi1 , . . . , ygi|I | を計算する．
A

172 / 192

1.00

評価関数

0.98
0.96
0.94
0.92
0.90
0

2

4

6

8

10

繰返し数

(a) 評価関数(b) 評価関数 (探索距離)(c) 探索経路上 f0 勾配(d) 探索経路上 f0 勾配 (探索距離)173 / 192(e) 探索経路上 f0 2 階微分(f) 探索経路上 f0 2 階微分 (探索距離)

図 3.20: 平均コンプライアンス最小化に対する数値例: 評価関数と探索経路に沿った評価関数の勾配と 2 階微分 (gL : 勾配法，h0 , gL : Newton 法，gH0 , gL : Hesse 勾配を用いた Newton 法)

174 / 192

(a) 収束履歴(b) (k − 1) 回目対 k 回目の関係

図 3.21: 平均コンプライアンス最小化に対する数値例: 最小点からの距離∥ak − a∥R2 (gL : 勾配法，h0 , gL : Newton 法，gH0 , gL : Hesse 勾配を用いた
Newton 法)

175 / 192

⊤

図 3.20 と図 3.21 は，例題 1.1.7 に対して初期点を a(0) = (1/2, 1/2) とおいたときの f0 の Hesse 勾配 gH0 を用いた Newton 法によって得られた結果を勾配法 (例題 3.7.3) と Newton 法 (例題 3.8.5) の結果と合わせて示している．
勾配法では，A = I ，ca = 200 とおいた．Hesse 勾配を用いた Newton 法では，A = I とおき，k = 0 の勾配法では ca = 200 を用いて，k ≥ kN = 1 のときに ca = 100 に変更した．
図 3.20 (a) は， 初期形状のときの f0 を表す f0init と初期形状の体積を表す
c1 = 1 で規準化された評価関数 f0 /f0init と 1 + f1 の繰返し数 k に対する変化を示している．図 3.20 (b) は，それらの評価関数を，X = R2 上の探索距離
Pk−1
i=0 bg(i) X に対して示している．また，図 3.20 (c) と (d) は，探索経路に沿って観測したときの f0 の勾配 (すなわち Lagrange 関数 L = L0 + λ1 f1 の176 / 192勾配) gL · bg(k) / bg(k) X の変化をそれぞれ繰返し数と探索距離に対して示している．さらに，図 3.20 (e) と (f) は，探索経路に沿って観測したときの f0
2の 2 階微分 hL bg(k) , bg(k) / bg(k) X (Hesse 勾配を用いた Newton 法の場合

2
2
は gH0 · bg(k) + λ1 h1 bg(k) , bg(k) / bg(k) X = gH0 · bg(k) / bg(k) X ) の変化をそれぞれ繰返し数と探索距離に対して示している．
図 3.20 より，繰返し数に対するグラフでは収束速度の違いにより異なった曲線になるが，探索距離に対するグラフはほぼ同一の曲線になることが観察される．その理由は，図 3.15 (a) や図 3.19 (a) に示されたように，探索経路は同一であったためである．このようなグラフは，第 8 章と第 9 章の数値例においても示される．そのときは，探索経路は図にかけないが，このようなイメージであることを想像してほしい．

177 / 192

また，図 3.21 (a) には，３つの方法で得られた最小点からの距離
a(k) − a X を繰返し数 k に対して示している．この図から，Hesse 勾配を用いた Newton 法の結果は，収束次数が 1 次以上であることが確認される．さらに，図 3.21 (b) は，繰返し数 (k − 1) 回目に対して k 回目の距離∥ak − a∥X をプロットしている．このグラフの勾配は収束次数を表す．なぜpならば， a(k) − a X = r a(k−1) − a X の関係を仮定したとき，log10 a(k) − a X = p log10 a(k−1) − a X + log10 r(3.8.13)が成り立つためである．この関係から，グラフの勾配が次数 p に対応し，対角線からのずれが log10 r に対応する．これらのグラフより，勾配法とNewton 法の収束次数はそれぞれ 1 次と 2 次になっていることが確認される．

178 / 192

このように，平均コンプライアンス最小化問題に対しては Newton 法が有効に機能することが確かめられた．一方，例題 3.7.4 のような体積最小化問題
に対して Newton 法をそのまま適用すれば，収束しない結果におちいる．図3.22 に，アルゴリズム 3.8.4 によって得られる試行点の推移を示す．ただし，
k = 0 のときの Lagrange 乗数 λ1(0) には，例題 3.7.4 の λ1(1) が使われた．この問題では，f0 の Hesse 行列は 0R2×2 で，f1 の Hesse 行列が正定値となっている．すなわち，注意 3.8.2 で指摘された条件が成り立っている．このような場合にも Newton 法が使えるようにするためには，ステップサイズを調整する必要がある．

179 / 192

図 3.22: Newton 法による体積最小化問題の数値例

180 / 192

§3.8.2 複雑なアルゴリズム

図 3.22 のような場合が起こりうることを考えると，ステップサイズを調整する機能をはじめ，3.7.2 節で説明された機能を追加する必要がある．それらの機能とアルゴリズムの関係は 3.7.2 項に示されている．それらをもう一度説明することは省略する．
また，Hesse 行列が正定値ではないような場合には，正定値行列を加えることで正定値化する方法や，負の固有値をもつ固有モードの成分のみをとりだ
して正値化する方法などが知られている．さらに，正定値ではないときには勾配法を適用して，収束がちかづいてきてから Newton 法にきりかえる方法なども考えられる．

181 / 192

3.9 第 3 章のまとめ

第 3 章では，有限次元ベクトル空間上の非線形最適化問題に対して，極小点を求める方法についてみてきた．要点は以下のようである．

1. 非線形最適化問題の解法には基本的に反復法が使われる．反復法は，初期点を与えて，探索ベクトル (探索方向とステップサイズ) を適切に決めながら試行点を更新していく方法である (3.2 節)．
2. 制約なし最適化問題に対して，探索方向を決める代表的な方法は勾配法である．勾配法は，評価関数の設計変数に対する勾配を既知として，勾配とは逆向きに探索方向を決める方法である (3.3 節)．

183 / 192

3. 制約なし最適化問題に対して，ステップサイズの適切性を判定する規準として Armijo の規準と Wolfe の規準が知られている．それらの規準が満たされるようにステップサイズが決定された反復法は，大域的収束性をもつ (3.4 節)．
4. 制約なし最適化問題に対して，評価関数の勾配と Hesse 行列が計算可能なとき，Newton 法を用いれば探索方向とステップサイズを同時に決めることができる．Newton 法で得られる試行点は 2 次収束する．しかし，Hesse 行列の計算にコストがかかる (3.5 節)．

184 / 192

5. 不等式制約つき最適化問題の解法の一つとして，拡大関数法が知られている．拡大関数法は，制約関数に重みを表す定数をかけて目的関数に加えることで制約なし問題におきかえる方法である．しかし，それらの方法を用いるためには，単調数列を問題ごとに適切に選ぶ必要がある (3.6節) ．
6. 不等式制約つき最適化問題の解法には，KKT 条件を用いた解法が考えられる．すべての評価関数の勾配が計算可能であれば，不等式制約つき最適化問題に対する制約つき問題に対する勾配法が使われる．この方法では，評価関数ごとの勾配とそれらを用いた勾配法によって得られる探索ベクトルで構成される行列を使って Lagrange 乗数が決定される．この関係は，実用的なアルゴリズムを考える際に有効に利用される (3.7 節)．

185 / 192

7. 不等式制約つき最適化問題において，評価関数の Hesse 行列が計算可能であれば，制約つき問題に対する Newton 法が使われる．この方法では，制約つき問題に対する勾配法で使われた正定値対称行列を Hesse 行列におきかえるだけで，制約つき問題に対する勾配法と同様のアルゴリズムが使われる．この方法が有効に機能するためには，制約関数の非線形性がよわいことが条件になる (3.8 節)．

186 / 192

3.10 第 3 章の演習問題

3.1 非線形関数 f ∈ C 2 (R; R) に対して，勾配 g (x) = 0 を満たす x ∈ R を求める問題を考える．k ∈ {0, 1, 2, · · · } に対して，xk ∈ R と g (xk ) が与えられたとき，Newton-Raphson 法 (問題 3.5.6) によって xk+1 を求める式
を示せ．また，g (xk ) を差分
f (xk ) − f (xk−1 )xk − xk−1におきかえたときに，xk+1 を求める式を示せ．この式はセカント法の公式を示す．

188 / 192

3.2 問題 3.4.1 (厳密直線探索法) を解くアルゴリズムとしてセカント法を用いることを考える．l ∈ {0, 1, 2, · · · } に対して ϵ̄gl が与えられたとき，ϵ̄g l+1 を求める式を示せ．
3.3 共役勾配法 (問題 3.4.10) の一例として示された式 (3.4.8) から式 (3.4.12)で計算される探索方向 ȳg k+1 は ȳgk と共役になることを確かめよ．
3.4 演習問題 1.6 の評価関数 f (a) (4 面体の体積) が最小となる設計変数 a(2 辺の長さ) を求める問題を考える．設計変数の初期値 a0 = (a01 , a02 )⊤が与えられたとき，Newton 法で探索ベクトル b を求めよ．

189 / 192

3.11 参考文献

[1] L. Armijo.
Minimization of functions having Lipschitz-continuous ﬁrst partial
derivatives.
Paciﬁc J. Math., Vol. 16, pp. 1–3, 1966.
[2] K. G. Murty.
Linear complementarity, linear and nonlinear programming.
Heldermann Verlag, Berlin, 1988.
[3] P. Wolfe.
Convergence conditions for ascent methods.
SIAM Review, Vol. 11, pp. 226–235, 1969.

191 / 192

[4] 矢部博.
工学基礎: 最適化とその応用.
数理工学社, 東京, 2006.

192 / 192