九州大学 海洋システム工学専攻
システム設計特論 （木村）講義資料5) 非線形最適化（勾配法）

場所：セミナー室1

【最適化とは？】「評価」を適切に定義していない例：
工場において、生産コストを最小化する運転方法→工場を閉鎖して生産をストップ
工場を閉鎖して生産をスト プ「最も良い状態になるように、手段や方法を考えて行動すること」

解候補－－－評価値例） 製品のデザイン－－－売上げ高
製品 デザイ
売上げ高
船の形状－－－推進抵抗

最適化以前に、その目的である「評価」を定義
することが重要モデル化に関連

一般的な最適化のプロセス：
新しい
解候補の生成解候補の評価以前の解候補の評価値を参考にして、より有望な解候補を生成することで解候補を改善していく2

【最適化とは？】

１）連続関数最適化問題

例： 石油を汲み上げるための油井を掘る
油を含む地層が最も地上に近い部分を掘ると利益が最大になる
予算 都合
予算の都合で、試掘の回数が制限される
試掘 回数が制限される→ 限られた試掘回数（６回）の範囲内で、最も地上に近い油層を探索する
解候補1

解候補5

解候補6

解候補2

解候補4

解候補3

x

真の最適解

利益関数 f(x)

探索で発見
した最良解

実際のxはn次元空間上を探索

3

【例：冗長自由度アームのリーチング問題】●各関節の角度をパラメ タとして、ア●各関節の角度をパラメータとして
アーム先端がターゲット座標に一致するパラメータ
ム先端がタ ゲット座標に 致するパラメ タを求める問題。ただし、各関節はリンク同士を±90度以内で繋ぐ制約があるので、なるべく関節の可動角度中央付近の角度にすることが好ましい。
コスト関数＝（アーム先端座標とターゲット座標の偏差の2乗）＋（各関節の可動中央角度からの偏差の2乗）

4

１０個のパラメータを持つ問題において、各パラメータが0～1の区間の値をとるものとして、各パラメータをも各パ
タを 0.1 刻みで全てのパラメータの組合せを
刻
全パ
タ 組合 を評価すると、評価回数は 11 の10 乗、これをおおよそ 10 の10乗で近似しても、 10,000,000,000 （百億）回必要になる。
１回の評価に１秒かかるものとすると、計算には ３１７年 を要する

パラメータの探し方（探索方法）を工夫しなければパラメ
タの探し方（探索方法）を工夫しなければ答えを見つけることができない5かなり粗い１０個のパラメータを持つ問題において、各パラメータが0～1の区間の値をとるものとして、各パラメータをも各パ
タを 0.1 刻みで全てのパラメータの組合せを
刻
全パ
タ 組合 を評価すると、評価回数は 11 の10 乗、これをおおよそ 10 の10乗で近似しても、 10,000,000,000 （百億）回必要になる。
１回の評価に１秒かかるものとすると、計算には ３１７年 を要する

パラメータの探し方（探索方法）を工夫しなければパラメ
タの探し方（探索方法）を工夫しなければ答えを見つけることができない6

【制約のない関数最適化】 1次元の最小化：ラインサーチ
Line search

黄金分割法
Golden section search

f(x)
( )

１次元空間上（直線）を探索a１） a < b < c の3点をとる

b

c

x

f(b)
( ) が最小なら、区間 [a,c] に必ず極小がある。

２） [b, c] の区間で新しい点 x をとり、f(x) を計算する。
３） f(b) < f(x) なら、 a < b < x に狭められた範囲に極小がある
f(x) < f(b) なら、 b < x < c に狭められた範囲に極小がある

7

【制約のない関数最適化】 1次元の最小化：ラインサーチ
Line search

黄金分割法
Golden section search

f(x)
( )

１次元空間上（直線）を探索a１） a < b < c の3点をとる

b

c

x

f(b)
( ) が最小なら、区間 [a,c] に必ず極小がある。

２） [b, c] の区間で新しい点 x をとり、f(x) を計算する。
３） f(b) < f(x) なら、 a < b < x に狭められた範囲に極小がある
f(x) < f(b) なら、 b < x < c に狭められた範囲に極小がある

8

【制約のない関数最適化】 1次元の最小化：ラインサーチ
Line search

黄金分割法
Golden section search

f(x)
( )

１次元空間上（直線）を探索a１） a < b < c の3点をとる

b

x

c

x

f(b)
( ) が最小なら、区間 [a,c] に必ず極小がある。

２） [b, c] の区間で新しい点 x をとり、f(x) を計算する。
３） f(b) < f(x) なら、 a < b < x に狭められた範囲に極小がある→ a,b,x をa,b,c に置換
9f(x) < f(b) なら、 b < x < c に狭められた範囲に極小がある【制約のない関数最適化】 1次元の最小化：ラインサーチ
Line search

黄金分割法
Golden section search

f(x)
( )

１次元空間上（直線）を探索a１） a < b < c の3点をとる

b

x

c

x

f(b)
( ) が最小なら、区間 [a,c] に必ず極小がある。

２） [b, c] の区間で新しい点 x をとり、f(x) を計算する。
３） f(b) < f(x) なら、 a < b < x に狭められた範囲に極小がある
f(x) < f(b) なら、 b < x < c に狭められた範囲に極小がある→ b,x,c をa,b,c に置換

【制約のない関数最適化】 1次元の最小化：ラインサーチ
Line search

黄金分割法
Golden section search

f(x)
( )

z

w

a
b や x をどのように決めるか？

１次元空間上（直線）を探索
x

b

c

x

1

次の新しい区間長は w+z または 1-w
1 w 。これらを等しくするとこれらを等しくすると z = 1 - 2w
区間[b,c]に対するxの位置関係は、区間[a,c]に対するbの位置関係に等しい
1 : w = (1 – w) : z
これらの連立方程式を解くと、w 2  3w  1  0

w

3 5
2

黄金比 11Golden section

【制約のない関数最適化】 1次元の最小化：ラインサーチ
Line search

黄金分割法
Golden section search

f(x)
( )

z

w

a
b や x をどのように決めるか？

１次元空間上（直線）を探索
x

b

c

x

1

次の新しい区間長は w+z または 1-w
1 w 。これらを等しくするとこれらを等しくすると z = 1 - 2w
区間[b,c]に対するxの位置関係は、区間[a,c]に対するbの位置関係に等しい
1 : w = (1 – w) : z
これらの連立方程式を解くと、w 2  3w  1  0

w

3 5
2

黄金比 12Golden section

1次元の最小化：ラインサーチ
Line search

３点を通る２次関数で近似
Approximated quadratic function

逆放物線補間f(x)( )Inverse parabolic interpolation（ニュートン法）
１次元空間上（直線）を探索
a

b

c

x

13

1次元の最小化：ラインサーチ
Line search

３点を通る２次関数で近似
Approximated quadratic function

逆放物線補間f(x)( )Inverse parabolic interpolation（ニュートン法）
１次元空間上（直線）を探索
a

b

c

x

14

1次元の最小化：ラインサーチ
Line search

３点を通る２次関数で近似
Approximated quadratic function

逆放物線補間f(x)( )Inverse parabolic interpolation（ニュートン法）
１次元空間上（直線）を探索
a

b

x

c

x

近似した２次関数の極小をサーチ
Search this point where gradient of theapproximatedppfunction is zero.

15

1次元の最小化：ラインサーチ
Line search

３点を通る２次関数で近似
Approximated quadratic function

逆放物線補間f(x)( )Inverse parabolic interpolation（ニュートン法）
１次元空間上（直線）を探索ab

x

1 (b  a ) 2  f (b)  f (c)   (b  c) 2  f (b)  f ( a ) x  b
2 (b  a ) f (b)  f (c)   (b  c) f (b)  f ( a ) cx

近似した２次関数の極小をサーチ
Search this point where gradient of theapproximatedppfunction is zero.

ただし ３点が１直線にあると 分母がゼロになってこの式は使えない
ただし、３点が１直線にあると、分母がゼロになってこの式は使えない
This equation is void when the tree points are on a same straight line.

161次元の最小化：ラインサーチ
Line search

３点を通る２次関数で近似
Approximated quadratic function

逆放物線補間f(x)( )Inverse parabolic interpolation（ニュートン法）
１次元空間上（直線）を探索ab

x

1 (b  a ) 2  f (b)  f (c)   (b  c) 2  f (b)  f ( a ) x  b
2 (b  a ) f (b)  f (c)   (b  c) f (b)  f ( a ) cx

近似した２次関数の極小をサーチ
Search this point where gradient of theapproximatedppfunction is zero.

ただし ３点が１直線にあると 分母がゼロになってこの式は使えない
ただし、３点が１直線にあると、分母がゼロになってこの式は使えない
This equation is void when the tree points are on a same straight line.

17ラインサーチの使用例：線図創生法

船型設計システムについて―線図創生―
SRC News No.62, Jan., pp.8--9, 2005,
造船技術センター(SRC)・肋骨線形状をサーチライン上に分割点を持つ2分割パラメトリック3次スプ
ライン曲線で表現する。
ライン曲線で表現する
・肋骨線の両端の点の角度と曲率を与える（隣り合う肋骨線同士での値がなめらかに変化するよう配慮）
・端点P1,
端点 , P2の座標（サイドタンジェ
座標（サイ タンジ
ンシャル・フラットボトム）を適宜与える
・船体断面の面積が該当位置のＣｐ
カーブの値×Cmと一致するよう、
サーチライン上でスプライン曲線の分割点を探索する←ラインサーチ
これもパラメトリック3次スプライン曲線
パラメータ
パラメ
タ ｔ （0＜ｔ＜1）で位置を指定

パラメトリック3次スプライン曲線：x  a x t 3  bx t 2  c x t  d x
y  a y t 3  by t 2  c y t  d y18

線図創生法で生成された線図の一例

サ チラインは船体の前部と後部でサーチラインは船体の前部と後部で別のものを用いるが、平行部付近（船体下部）では同じ角度と曲率にする19

【制約のない関数最適化】 n次元関数の最小化

optimization in n-dimensional function
探索点
探索点での関数の値（と勾配の大きさ）に基づいて次の探索点を順次決定する
数 値 勾
き
基づ
次 探索点を 次決定す手順により、あたかも山の頂上を目指すように、関数の極大値（あるいは極小値）をすみやかに発見する手法

１）勾配情報を用いる方法： 勾配法
・最大勾配法（最急降下法）
勾配方向 少しず 解を改善
勾配方向へ少しずつ解を改善
ステップ幅を勾配に比例させて極小点で停止●ラインサーチと方向転換を繰り返す方法
・最適勾配法：勾配方向にラインサーチを行い、その極小点で再び勾配方向へラインサーチ
だいたいうまく行くが、２次関数において極めて効率の悪い場合がある

・共役勾配法：方向転換するとき、その点の勾配方向だけでなく、今まで下ってきた方向も考える（関数（関数の2階偏導関数を考慮に入れることと等価）
階偏導関数を考慮に入れる とと等価）対象とする関数がn変数の２次形式である場合、
ラインサーチをn回繰返すことで最大値が求まることが保障される

振動が発生

２）勾配情報を用いない方法： 滑降シンプレックス法
20
たいした計算を要しないで手っ取り早く動くアルゴリズムが欲しい場合に最善の方法

勾配法と「ニューラルネット」との関連
w0 , w1 , , wn NET  x w  x w  x w    n 1 x w  0
 i i
1 1
2 2
3 3

のとき「A」と判定

i 1

Σ
画素

x1 , x2 , , xn

「A」？
Yes or No

activeti

興奮しているニロン同士
Hebbの学習則：学 則 興奮しているニューロン同士を結ぶシナプスの重みを強化

さらに洗練されたニューラルネットの学習法：誤差逆伝搬法（Back-Propagation)「勾配法」による誤差関数の最小化
21

勾配法と「確率的学習」や「遺伝的アルゴリズム」との関連
試行錯誤による学習＝強化学習「確率的学習」では１つの解候補がランダムウォークしつつコスト関数の勾配を下る
解候補の移動方向の期待値＝コスト関数の勾配「遺伝的アルゴリズム」では解候補の集団全体が平均したコスト関数の勾配を下る
解候補集団分布の移動方向の期待値
解候補集団分布
移動方向 期待値＝平均コスト関数の勾配

勾配法は様々な
数値最適化の基本

22【復習】 関数の勾配とは？
(gradient)

2変数関数

f ( x1 , x2 )探索すべきx  ( x1 , x2 )パラメータベクトル 
勾配ベクトルg  f ( x1 , x2 )  
f ( x1 , x2 ),f ( x1 , x2 ) 
(gradient vector)
x2
 x1

x2


f ( x1 , x2 )
x2

( x1 , x2 )f ( x1 , x2 )勾配ベクトルg(gradient vector))(gf ( x1 , x2 )
x1

x1

23

ラインサーチと方向転換を繰り返す方法（１）最適勾配法（Ｏｐｔｉｍａｌ ｇｒａｄｉｅｎｔ ｍｅｔｈｏｄ）
勾配方向にラインサーチを行い、極小点で再び勾配を求め、その方向へラインサーチする
Execute line search in direction of the ggradient toward its optimumpppoint,and turn to the new gradient direction, and execute line search again.
Optimum point in line search
Heading here

振動が発生

Line search
Direction = gradientLine search
Di ti = gradientDirection
di t

24

ラインサーチと方向転換を繰り返す方法（１）最適勾配法（Ｏｐｔｉｍａｌ ｇｒａｄｉｅｎｔ ｍｅｔｈｏｄ）
勾配方向にラインサーチを行い、極小点で再び勾配を求め、その方向へラインサーチする
Execute line search in direction of the ggradient to its optimumpppoint,and turn to the new gradient direction, and execute line search again.
Optimum point in line search
Heading here

振動が発生

Line search
Direction = gradientLine search
Di ti = gradientDirection
di t

【問題点】
２次関数において、細かいステップで方向転換を繰り返しながら同じような方向を何度もラインサーチを行い、谷底に着くまで多数のステップを要する
It needs many steps in quadratic functions repeating the line searchin similar direction.
新しい探索方向は、今までの全ての探索方向とも干渉しない（直交・共役である）
ことが望ましい A new direction should be conjugate against all past directions. 25

なぜ 「2次形式」が重要なのか？
(quadratic)

ある特定の点Ｐを原点とし、この点の近傍座標をxとする。
すると、どんな関数 f もテイラー級数で近似できる：(Taylor series)

1
f
2 f
f ( x)  f ( P )  
xi  
xi x j  
2 i , j xi x ji xi
1 f ( P )  f |P x  x  A  x  
22次形式(quadratic)

この行列A はf(x)のHesse行列(H(Hessiani matrix)ti )各要素はPにおける２階編導関数

2
A  ij xi x j

26

Pなぜ 「2次形式」が重要なのか？
(quadratic)

ある特定の点Ｐを原点とし、この点の近傍座標をxとする。
すると、どんな関数 f もテイラー級数で近似できる：(Taylor series)

f
1
2 f
f ( x)  f ( P )  
xi  
xi x j  
2 i , j xi x j
i xi
1 t
 f ( P )  f |P x  x  A  x  
22次形式(quadratic)

この行列A はf(x)のHesse行列(H(Hessiani matrix)ti )各要素はPにおける２階編導関数

2 f
A  ij xi x j

27

P【復習】 「2次形式」と「共役」な方向とは？
(quadratic)(conjugate)f ( x1 , x2 ,  , xn )  X AX  B X  Ct x1 
 a11
x 
a
 2 , A   21
探索すべき X  
パラメータベクトル   (parameter vector) 


x
 n
 an1
ただし

t

a12
a22

an 2

2次形式 (quadratic)

 a1n  b1 
b 
 a2 n , B   2

  

 
 ann bn Positive definite symmetrical matrix

N×N 正定値対称行列 A に対して、２つの方向を表すベクトル p と q が
p t Aq  0 を満たすとき、 p と q は A に関して互いに共役であるという(conjugate)

参考：A を単位行列
参考を単位行列とすると、上の式は直交条件となり、共役性は直交性の拡張概念
する 、式 直交条件 なり、共役性 直交性 拡張概念
また、「複素共役」とは無関係
28

【復習】 「2次形式」と「共役」な方向とは？
(quadratic)(conjugate)f ( x1 , x2 ,  , xn )  X AX  B X  Ct x1 
 a11
x 
a
 2 , A   21
探索すべき X  
パラメータベクトル   (parameter vector) 


x
 n
 an1
ただし

t

a12
a22

an 2

2次形式 (quadratic)

 a1n  b1 
b 
 a2 n , B   2

  

 
 ann bn Positive definite symmetrical matrix

N×N 正定値対称行列 A に対して、２つの方向を表すベクトル p と q が
p t Aq  0 を満たすとき、 p と q は A に関して互いに共役であるという(conjugate)

参考：A を単位行列
参考を単位行列とすると、上の式は直交条件となり、共役性は直交性の拡張概念
する 、式 直交条件 なり、共役性 直交性 拡張概念
また、「複素共役」とは無関係
29

Conjugate Gradient Method:
共役勾配法
CG法
【制約のない関数最適化】
xi i 番目の点の座標ベクトル
Coordinate of the i search pointg i 点 xi における勾配ベクトル
Gradient vector at x
pi 点 xi からラインサーチを行う方向ベクトル
x0
Direction of line search at x
th

i

i

Conjugate Gradient Method:
共役勾配法
CG法
【制約のない関数最適化】
xi i 番目の点の座標ベクトル
Coordinate of the i search pointg i 点 xi における勾配ベクトル
Gradient vector at x
pi 点 xi からラインサーチを行う方向ベクトル
x0
Direction of line search at x
th

i

i

まず最初は勾配の反対方向へラインサーチ

p0   g 0

xi の次の点 xi 1 を、ラインサーチで見つけた最小点とする
xi
xi 1  xi   i pi Optimum point in line searchg i 1pixi 1Conjugate Gradient Method:
共役勾配法
CG法
【制約のない関数最適化】
xi i 番目の点の座標ベクトル
Coordinate of the i search pointg i 点 xi における勾配ベクトル
Gradient vector at x
pi 点 xi からラインサーチを行う方向ベクトル
x0
Direction of line search at x
th

i

i

まず最初は勾配の反対方向へラインサーチ

p0   g 0

g i 1

pi

pi 1

xi 1
xi の次の点 xi 1 を、ラインサーチで見つけた最小点とする
xi
xi 1  xi   i pi Optimum point in line search
次の点 xi 1での新しい探索方向 pi 1は、前の探索方向 pi と共役であるようにする。
そのため、点 xi 1 での勾配と前の探索方向 pi とを結合する：
pi 1   g i 1   i 1 pi

重み係数

Conjugate Gradient Method:
共役勾配法
CG法
【制約のない関数最適化】
xi i 番目の点の座標ベクトル
Coordinate of the i search pointg i 点 xi における勾配ベクトル
Gradient vector at x
pi 点 xi からラインサーチを行う方向ベクトル
x0
Direction of line search at x
th

i

i

まず最初は勾配の反対方向へラインサーチ

p0   g 0

g i 1

pi

pi 1

xi 1
xi の次の点 xi 1 を、ラインサーチで見つけた最小点とする
xi
xi 1  xi   i pi Optimum point in line search
次の点 xi 1での新しい探索方向 pi 1は、前の探索方向 pi と共役であるようにする。
そのため、点 xi 1 での勾配と前の探索方向 pi とを結合する：
pi 1   g i 1   i 1 pi
ただし、重み係数  i 1は次の式のどちらかで与える：
T
i 1
T
i

2

g i 1g g i 1 i 1 

2
g gi
gi

（Fletcher-Reeves法）（Polak-Ribiere法）( g i 1  g i )T g i 1
 i 1 
g iT g i

Conjugate Gradient Method:
共役勾配法
CG法
【制約のない関数最適化】
xi i 番目の点の座標ベクトル
Coordinate of the i search pointg i 点 xi における勾配ベクトル
Gradient vector at x
pi 点 xi からラインサーチを行う方向ベクトル
x0
Direction of line search at x
th

i

i

まず最初は勾配の反対方向へラインサーチ

p0   g 0

g i 1

pi

pi 1

xi 1
xi の次の点 xi 1 を、ラインサーチで見つけた最小点とする
xi
xi 1  xi   i pi Optimum point in line search
次の点 xi 1での新しい探索方向 pi 1は、前の探索方向 pi と共役であるようにする。
そのため、点 xi 1 での勾配と前の探索方向 pi とを結合する：
pi 1   g i 1   i 1 pi
ただし、重み係数  i 1は次の式のどちらかで与える：
T
i 1
T
i

2

g i 1g g i 1 i 1 

2
g gi
gi

（Fletcher-Reeves法）（Polak-Ribiere法）( g i 1  g i )T g i 1
 i 1 
g iT g i

線形方程式の２次形式を最小化するための、最適なステップサイズによる最適勾配法の収束と共役勾配法の収束の比較
出典: フリー百科事典『ウィキペディア（Wikipedia）』

共役勾配法

最適勾配法

35

【共役勾配法が2次形式関数でｎ回のラインサーチで最適解を見つける理由】
次式を満たす n 個の n 次元ベクトル Z1 , Z 2 ,  Z n を考える：

const.
Z i AZ j   0tfor i  jfor i  j

Z1 , Z 2 ,  Z n は共役ベクトル集合36

【共役勾配法が2次形式関数でｎ回のラインサーチで最適解を見つける理由】
次式を満たす n 個の n 次元ベクトル Z1 , Z 2 ,  Z n を考える：

const.
Z i AZ j   0t

次に、ベクトル X を

for i  jfor i  jX   j 1 j Z j

Z1 , Z 2 ,  Z n は共役ベクトル集合nと表すと、2次形式の評価式は

f ( x1 , x2 ,  , xn )  X t AX  B t X  C
n
 n n
  n

t
t
2
t
    i j Z i AZ j      i B Z i   C    i Z i AZ i   i B t Z i  C
i 1 i 1 j 1
  i 137

【共役勾配法が2次形式関数でｎ回のラインサーチで最適解を見つける理由】
次式を満たす n 個の n 次元ベクトル Z1 , Z 2 ,  Z n を考える：

const.
Z i AZ j   0t

次に、ベクトル X を

for i  j

Z1 , Z 2 ,  Z n は共役ベクトル集合

for i  jX   j 1 j Z jnと表すと、2次形式の評価式は

f ( x1 , x2 ,  , xn )  X t AX  B t X  C
n
 n n
  n

t
t
2
t
    i j Z i AZ j      i B Z i   C    i Z i AZ i   i B t Z i  C
i 1 i 1 j 1
  i 1

ここで

g i ( i )   i Z i AZ i   i B t Z i2tとおくと 上の式は以下のようになるとおくと、上の式は以下のようになる：

各共役ベクトル毎にインデックス表示38

【共役勾配法が2次形式関数でｎ回のラインサーチで最適解を見つける理由】
次式を満たす n 個の n 次元ベクトル Z1 , Z 2 ,  Z n を考える：

for i  jconst.
Z i AZ j   0t

次に、ベクトル X を

Z1 , Z 2 ,  Z n は共役ベクトル集合

for i  jX   j 1 j Z jnと表すと、2次形式の評価式は

f ( x1 , x2 ,  , xn )  X t AX  B t X  C
n
 n n
  n

t
t
2
t
    i j Z i AZ j      i B Z i   C    i Z i AZ i   i B t Z i  C
i 1 i 1 j 1
  i 1

ここで

g i ( i )   i Z i AZ i   i B t Z i2tnf ( x1 , x2 ,  , xn )   g i ( i )  C
i 1

探索開始点から順次 Z1 , Z 2 ,  Z n 方向の関数の断面について 1 ,  2  n の最小化を行えばn回のラインサーチで最適解を得るとおくと 上の式は以下のようになるとおくと、上の式は以下のようになる：
これより、関数 f はそれぞれ  iに対する n 個の関数の代数和で表される
よって g1 (1 ), g 2 ( 2 ),  g n ( n )のそれぞれについて最小値を求めれば良い39

【２次形式関数と共役勾配方向の例】

f  x 2  xy  y 2y対称行列Ａを用いて２次形式表現すると、

f  x

 1 1 2  x 
y 
 y
1
2
1

 

このとき
とき

 1 1 2  1 
1 1
0
1 2 1   1

x
短軸
方向

長軸
方向

となるので、（１，１） と （１、－１） が対となる共役ベクトル40

【例：冗長自由度アームのリーチング問題】●各関節の角度をパラメ タとして、ア●各関節の角度をパラメータとして
アーム先端がターゲット座標に一致するパラメータ
ム先端がタ ゲット座標に 致するパラメ タを求める問題。ただし、各関節はリンク同士を±90度以内で繋ぐ制約があるので、なるべく関節の可動角度中央付近の角度にすることが好ましい。
コスト関数＝（アーム先端座標とターゲット座標の偏差の2乗）＋（各関節の可動中央角度からの偏差の2乗）

41

流体の数値計算における共役勾配法の利用
圧力のポアソン方程式を離散化 → 大規模な連立１次方程式

係数行列：隣接する領域
のみの関係なので、疎な実対称正定値行列

２次形式

f (x)  x T Ax  2x Tb

Ax  b を解く
未知量ベクトル（圧力）要素数は数万～数百万とおき、これを最小化する x を共役勾配法で求める「最小点」では df ( x) dx  0 より Ax  b を満たす
求めようとする解そのもの

大規模な連立方程式を数値的に解く場合、逆行列を直接計算するよりも共役勾配法のほうが、はるかに効率良く計算できる場合がある
42

流体の数値計算における共役勾配法の利用
圧力のポアソン方程式を離散化 → 大規模な連立１次方程式

係数行列：隣接する領域
のみの関係なので、疎な実対称正定値行列

２次形式

f (x)  x T Ax  2x Tb

Ax  b を解く
未知量ベクトル（圧力）要素数は数万～数百万とおき、これを最小化する x を共役勾配法で求める「最小点」では df ( x) dx  0 より Ax  b を満たす
求めようとする解そのもの

大規模な連立方程式を数値的に解く場合、逆行列を直接計算するよりも共役勾配法のほうが、はるかに効率良く計算できる場合がある
43

【制約のない関数最適化】 ニュートン法 Newton method
３点を通る２次関数で近似
Approximated quadratic functionf(x)f ( x)  ax  bx  cLine search2

逆放物線補間Inverse parabolic interpolation

１次元空間上次 空間上（直線）を探索xdf
 0 より、2ax  b  0dxx  (2a ) 1 (b)

近似した２次関数の極小をサーチ近似した２次関数の極小をサチ
Search this point where gradient of theapproximated function is zero.

44

【制約のない関数最適化】 ニュートン法 Newton method
３点を通る２次関数で近似
Approximated quadratic functionf(x)f ( x )  ax  bx  cLine search2

逆放物線補間Inverse parabolic interpolation

１次元空間上次 空間上（直線）を探索xdf
 0 より、2ax  b  0dxx  (2a ) 1 (b)

近似した２次関数の極小をサーチ近似した２次関数の極小をサチ
Search this point where gradient of theapproximated function is zero.

45

【制約のない関数最適化】 準ニュートン法
Quasi-Newton method

関数 f(x) をテイラー級数で近似(Taylor series)

f
1
2 f
f (x)  f (P )  
xi  
xi x j  
2 i , j xi x ji xi
この行列A はf(x)のHesse行列1
 f ( P )  f |P x  x  A  x  
2
2次形式

(
(Hessianmatrix))
各要素はPにおける２階編導関数

2
A  ij xi x j(quadratic)46

P【制約のない関数最適化】 準ニュートン法
Quasi-Newton method

関数 f(x) をテイラー級数で近似(Taylor series)

f
1
2 f
f (x)  f (P )  
xi  
xi x j  
2 i , j xi x ji xi
この行列A はf(x)のHesse行列1
 f ( P )  f |P x  x  A  x  
22次形式(quadratic)((Hessianmatrix))
各要素はPにおける２階編導関数

極小点では勾配ゼロだから上の式を微分すると

2
A  ij xi x j

f ( x )   f |P  A  x  0
これを解くとx  A 1 (   f | P )次はこの点を探査すべし
次
点を探査す

47

P

【制約のない関数最適化】 準ニュートン法
Quasi-Newton method

関数 f(x) をテイラー級数で近似(Taylor series)

f
1
2 f
f (x)  f (P )  
xi  
xi x j  
2 i , j xi x ji xi
この行列A はf(x)のHesse行列1
 f ( P )  f |P x  x  A  x  
22次形式(quadratic)((Hessianmatrix))
各要素はPにおける２階編導関数

極小点では勾配ゼロだから上の式を微分すると

2
A  ij xi x j

f ( x )   f |P  A  x  0

P

これを解くとx  A 1 (   f | P )次はこの点を探査すべし
次点を探査す

しかし、行列Ａは未知 なので、探索の過程から逐次的に近似する
Since matrix A is unknown, it is estimated from the process of the optimization incrementally.

（計算には勾配の情報とラインサーチを用いる）
48

準ニュートン法の処理手順
現在の探索点をx i 次の探索点を x i 1と表わす…あまりに式が複雑なので途中で投げ出しました
詳細は省略。最適化するなら共役勾配法を使え。

49

勾配法の補足：
関数の厳密な勾配の計算ができない場合は、差分近似で代用する と。
差分近似で代用すること。
まとめ
・１次元関数の最小化（ラインサーチ）○黄金比分割法 △ニュートン法
トン法

・n次元関数の最小化：

ラインサーチを利用
ラインサ
チを利用

勾配を用いる方法
×最急降下法 △最適勾配法 ○共役勾配法（ＣＧ法）
逆放物線補間を用いる方法○準ニュートン法（ただし計算過程で勾配とラインサーチを用いる） 50
Javaサンプルプログラム

http://sysplan.nams.kyushu-u.ac.jp/gen/index.html