講義で使った資料 - 情報システム工学科

最適化理論
http://www.cs.miyazaki-u.ac.jp/~date/lectures/optimization/
伊達章
宮崎大学工学部情報システム工学科
2015 年 6 月 12 日
1 / 27
講義のスケジュール（案）
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
講義の概要
数学的準備：曲線と曲面
数学的準備：1 次形式と 2 次形式
数学的準備：2 次形式の標準形
関数の極値：関数の勾配と等高線，関数の極値
関数の極値：ラグランジュの未定乗数法
関数の最適化：勾配法・ニュートン法
関数の最適化：共役勾配法
最小二乗法：連立一次方程式，特異値分解と一般化逆行列
線形計画法：品野勇治先生（特別回）6/16 火 14:50∼ A-116
統計的最適化：正規分布，最尤推定
最先端の話：岡田真人先生（特別回）7/3 金 14:50∼ A-116
動的計画法（その 1）
動的計画法（その 2）
定期試験，解説
2 / 27
目標
• 最適化手法の原理と計算法を学ぶ
→ 数理最適化ソルバー（ソフトウェア）を使いこなせ
るようになる
• 最適化理論に必要な数学
• 曲線と曲面の方程式，法線ベクトル
• 2 次形式の最大・最小化
• 関数の極値
• ヘッセ行列やラグランジュの未定乗数法の意味
• 最適化（勾配法など）
• 最小二乗法：連立一次方程式，特異値分解と一般化逆行列
• 統計的最適化
• 正規分布
• 事前確率，事後確率，事後確率最大化，周辺分布
• 動的計画法
3 / 27
最小二乗法
4.1 式のあてはめ
4.1.1 直線のあてはめ
4.1.2 多項式のあてはめ
4.1.3 一般の曲線のあてはめ
4.2 連立 1 次方程式
4.2.1 多すぎる方程式
4.2.2 少なすぎる方程式
4.2.3 特異値分解と一般逆行列
4 / 27
連立方程式
• 方程式の数と未知数が同じ場合
{
x −y = −1
x +2y = 5
(
)( ) ( )
1 −1
x
−1
=
1 2
y
5
Ax = b
x = A−1 b
)( ) ( )
( )
(
1 2 1
1
−1
x
=
=
2
5
y
3 −1 1
5 / 27
最小二乗法
4.1 式のあてはめ
4.1.1 直線のあてはめ
4.1.2 多項式のあてはめ
4.1.3 一般の曲線のあてはめ
4.2 連立 1 次方程式
4.2.1 多すぎる方程式
4.2.2 少なすぎる方程式
4.2.3 特異値分解と一般逆行列
6 / 27
連立方程式
• 方程式が未知数より多い場合

 x −y = −1
x +2y = 5

x +y = 2


 
1 −1 ( )
−1
1 2  x =  5  , Ax = b
y
1 1
2
x = A−1 b
7 / 27
連立方程式
• 方程式が未知数より多い場合

 x −y = −1
x +2y = 5

x +y = 2


 
1 −1 ( )
−1
1 2  x =  5  , Ax = b
y
1 1
2
x = A−1 b
A−1 は存在しない！どうする？
8 / 27
連立方程式
• 方程式が未知数より多い場合


 
1 −1 ( )
−1
x
1 2 
= 5 
y
1 1
2
Ax ≈ b
となる x を見つける．
J(x) =
1
∥ Ax − b ∥2 → min
2
∇J = 0
9 / 27
連立方程式
J(x) =
J(x) =
=
=
=
=
∇J(x) =
1
∥ Ax − b ∥2 → min =⇒ ∇J = 0
2
1
1
∥ Ax − b ∥2 = (Ax − b, Ax − b)
2
2
1
{(Ax, Ax) − (Ax, b) − (b, Ax) + (b, b)}
2
1
1
(Ax, Ax) − (b, Ax) + (b, b)
2
2
1
1 T T
x A Ax − bT Ax + (b, b)
2
2
1
1
(x, AT Ax) − (AT b, x) + (b, b)
2
2
∂
J(x) =
∂x
10 / 27
連立方程式
J(x) =
J(x) =
=
=
=
=
∇J(x) =
1
∥ Ax − b ∥2 → min =⇒ ∇J = 0
2
1
1
∥ Ax − b ∥2 = (Ax − b, Ax − b)
2
2
1
{(Ax, Ax) − (Ax, b) − (b, Ax) + (b, b)}
2
1
1
(Ax, Ax) − (b, Ax) + (b, b)
2
2
1
1 T T
x A Ax − bT Ax + (b, b)
2
2
1
1
(x, AT Ax) − (AT b, x) + (b, b)
2
2
∂
J(x) = AT Ax − AT b
∂x
11 / 27
連立方程式
目的： Ax ≈ b となる x を見つける．
J(x) =
1
∥ Ax − b ∥2 → min
2
=⇒ ∇J = 0
∂
J(x) = AT Ax − AT b = 0
∂x
x = (AT A)−1 AT b
∇J(x) =
A− = (AT A)−1 AT を一般逆行列とよぶ
12 / 27
連立方程式
目的： Ax ≈ b となる x を見つける．


 
1 −1 ( )
−1
1 2  x =  5 
y
1 1
2
x = (AT A)−1 AT b = A− b


−1
 
(
) 1 −1
(
) −1
1 1 1 
1 1 1  
1 2 
5
= 
−1 2 1
−1 2 1
1 1
2
)( )
(
( )
)−1 ( )
(
1 10
1
6
6 −2
6
3 2
=
=
=
13
13
2 6
14 −2 3
14 27
13 / 27
最小二乗法
4.1 式のあてはめ
4.1.1 直線のあてはめ
4.1.2 多項式のあてはめ
4.1.3 一般の曲線のあてはめ
4.2 連立 1 次方程式
4.2.1 多すぎる方程式
4.2.2 少なすぎる方程式
4.2.3 特異値分解と一般逆行列
14 / 27
連立方程式
• 方程式が未知数より少ない場合
2x +y = 5
(
( )
( )
) x
2 1
= 5 , Ax = b
y
x = A−1 b
15 / 27
連立方程式
• 方程式が未知数より少ない場合
2x +y = 5
(
( )
( )
) x
2 1
= 5 , Ax = b
y
x = A−1 b
A−1 は存在しない！解 x は無数に存在！
どうする？
16 / 27
連立方程式
• 方程式が未知数より少ない場合
2x +y = 5
(
( )
( )
) x
2 1
= 5 , Ax = b
y
x = A−1 b
A−1 は存在しない！解 x は無数に存在！
どうする？ =⇒ なるべく小さい解を求める
∥ x ∥2 → min．条件付き最小化
17 / 27
連立方程式
• 方程式が未知数より少ない場合
(
( )
( )
) x
2 1
= 5
y
解は無数にある．一番小さい x∗ を見つける．
1
∥ x ∥2 −(λ, Ax − b)
2
1 2
= (x + y 2 ) − λ(2x + y − 5)
2
x∗ = argmin F (x)
F (x) =
x
∇F = 0
18 / 27
連立方程式
1
F (x) = ∥ x ∥2 −(λ, Ax − b) → min
2
=⇒ ∇F = 0
F (x) =
=
=
=
∇F (x) =
1
(x, x) − (λ, Ax − b)
2
1
(x, x) − (λ, Ax) − (λ, b)
2
1
(x, x) − λT Ax − (λ, b)
2
1
(x, x) − (AT λ, x) − (λ, b)
2
∂
F (x) =
∂x
19 / 27
連立方程式
1
F (x) = ∥ x ∥2 −(λ, Ax − b) → min
2
=⇒ ∇F = 0
F (x) =
=
=
=
∇F (x) =
1
(x, x) − (λ, Ax − b)
2
1
(x, x) − (λ, Ax) − (λ, b)
2
1
(x, x) − λT Ax − (λ, b)
2
1
(x, x) − (AT λ, x) − (λ, b)
2
∂
F (x) = x − AT λ
∂x
20 / 27
連立方程式
目的： ∥ x ∥ 最小の Ax = b を見つける．
F (x) =
1
∥ x ∥2 −(λ, Ax − b) → min → ∇F = 0
2
∂
F (x) = x − AT λ = 0
∂x
x = AT λ （λ を求める必要あり）
AAT λ = b → λ = (AAT )−1 b
x = AT (AAT )−1 b
∇F (x) =
A− = AT (AAT )−1 を一般逆行列とよぶ
21 / 27
連立方程式
目的： ∥ x ∥ 最小の Ax = b を見つける．
(
( )
( )
) x
2 1
= 5
y
x = AT (AAT )−1 b = A− b
( )(
( ))
(
) 2 −1 ( )
2
2 1
5
=
1
1
( )
( )
( )
1 2
2
2 −1
(5) =
5 (5) =
=
1
1
5 1
22 / 27
最小二乗法
4.1 式のあてはめ
4.1.1 直線のあてはめ
4.1.2 多項式のあてはめ
4.1.3 一般の曲線のあてはめ
4.2 連立 1 次方程式
4.2.1 多すぎる方程式
4.2.2 少なすぎる方程式
4.2.3 特異値分解と一般逆行列
23 / 27
特異値分解と一般逆行列：
AAT と ATA
(
)
A = 2 1 の例（m × n = 1 × 2 行列）：
AA
T
=
(
( )
) 2
2 1
=5
1
固有値 5，固有ベクトル (1)
)
(
( )
)
4 2
2 (
T
2 1 =
A A =
2 1
1
固有値 5，0
( )
( )
1 2
1
1
固有ベクトル √
,√
1
−2
5
5
√ T
√ 1 (
)
A = U ΛV = (1)( 5) √ 2 1
5
( )
( )
(√ )−1
1 2 1
1 2
−
T
√ (1) =
A = V
Λ
U =√
5 1
5 1
5
24 / 27
特異値分解と一般逆行列：AAT と AT A


1 −1
A = 1 2  の例（m × n = 3 × 2 行列）：
1 1




)
1 −1 (
2 −1 0
1 1 1
AAT = 1 2 
= −1 5 3
−1 2 1
1 1
0 3 2


(
) 1 −1
(
)
1
1
1
3
2
1 2  =
AT A =
−1 2 1
2 6
1 1
25 / 27
AAT と ATA：どちらも半正定値対称行列
• 固有値は実数で正の値，もしくは 0
• 固有ベクトルが互いに直交している
• AAT と AT A は固有値を共有
• 正の固有値の個数が，行列 A のランク
26 / 27
終
27 / 27

Download Report