【しっかり学ぶ数理最適化】3.2.1~3.2.2

2025年度後期輪読会 しっかり学ぶ数理最適化(3.2.1~3.2.2) 社会⼈メンバー 栗林 雷旗 0

アジェンダ n 3.2 制約なし最適化問題 • 3.2.1 制約なし最適化問題の最適性条件 • 3.2.2 最急降下法 1

制約なし最適化問題: 最適性の1次の必要条件 勾配が0でも最適解とは限らない 定理3.8 最適性の1次の必要条件 目的関数 𝑓 が微分可能であるとき、 𝑥 ∗ が局所最適解 → ∇𝑓 𝑥 ∗ = 0 停留点 2

制約なし最適化問題: 最適性の2次の必要条件 定理3.9 最適性の2次の必要条件 目的関数 𝑓 が2階微分可能であるとき、 𝒙∗ が局所最適解 → 𝒅" ∇# 𝑓 𝒙∗ 𝒅 ≥ 0 例 𝑓! 𝑥!, 𝑥" = 𝑥!" + 2𝑥"" 2𝑥! ∇𝑓! 𝑥 = 4𝑥" ∇"𝑓! 𝑥 2 0 = 0 4 固有値は2, 4 局所最適解 半正定値であることは、固有値が負でないことと言い換えられるので∇"𝑓! 𝑥 は半正定値 3

制約なし最適化問題: 最適性の2次の必要条件 逆は⾔えないのか︖ 定理3.9の逆 目的関数 𝑓 が2階微分可能であるとき、 𝒅" ∇# 𝑓 𝒙∗ 𝒅 ≥ 0 → 𝒙∗ が局所最適解 これは言えない 反例 𝑓! 𝑥!, 𝑥" = 2𝑥!" + 5𝑥"# ∇𝑓! 𝑥 = 4𝑥! 15𝑥"" ∇"𝑓! 𝑥 = 4 0 0 0 ←点(0,0)において 固有値は 0, 4 なので負でない→このヘッセ行列は半正定値 しかし局所最適解ではない(関数の値が0になるような点(𝑥!, 𝑥")がたくさん連なっている 4

制約なし最適化問題: 最適性の2次の⼗分条件 定理3.9の逆は⾔えなかったが、停留点であることを条件に加えると 定理3.10 最適性の2次の十分条件 目的関数 𝑓 が2階微分可能であるとき、 点 𝒙∗ が停留点 かつ 𝒅" ∇# 𝑓 𝒙∗ 𝒅 ≥ 0 → 𝒙∗ は局所最適解 局所最適解 5

最急降下法 ⽬的関数の値が最も急激に減少する⽅向を選んで探索を⾏う処理を繰り返し、停留点を⾒つける 6