【しっかり学ぶ数理最適化】3.1~3.1.2

2025年度後期輪読会 #5（2025/10/30） しっかり学ぶ数理最適化 3.1-3.1.2 非線形計画問題の定式化 京都大学工学部理工化学科 B2 岡本和優 0

アジェンダ ◼ 非線形計画問題の定式化 1

非線形問題の定式化 目的関数や制約条件に非線形関数を含む 非線形計画問題：非線形関数で表された目的関数や制約関数を含む最適化問題 以下の形で表せる 最小化 • 𝑓(𝑥) 条件 • 𝑔𝑖 𝑥 ≤ 0, 𝑖 = 1, … , 𝑙 • 𝑔𝑖 𝑥 = 0, 𝑖 = 𝑙 + 1, … , 𝑚 • 𝑥 ∈ ℝ𝑛 制約条件を表す関数𝑔1 , … 𝑔𝑚 を制約関数とよぶ 2

非線形計画問題の例 目的関数や制約条件に非線形関数が含まれる • 施設配置問題：配送センターと店舗の配置をどうするか？ • 円詰込み問題：コンテナにタイヤを効率的に詰め込むにはどうするか？ • ポートフォリオ選択問題：どう資産を分配すればリスクを下げられるか？ 3

分類問題 あらたなデータのカテゴリを分類したい 与えられたデータが線形分離可能だと仮定して… • サポートベクトルマシン 境界線からもっとも近いデータまでの距離を最大化する • ロジスティック回帰 以下の尤度関数の値が最大となるようなパラメータを選ぶ 𝑛 𝑖 𝑖 L 𝒘, 𝑏 = ෑ 𝑝𝑖 𝒘, 𝑏 𝑦 (1 − 𝑝𝑖 𝒘, 𝑏 1−𝑦 ) 𝑖=1 ただし𝑝𝑖 (𝒘, 𝑏)はデータ𝑥 (𝑖) のカテゴリが𝑦 (𝑖) = 1となる確率 4

凸計画問題 目的関数が凸関数、実行可能領域が凸集合となる問題 凸計画問題：目的関数が凸関数、実行可能領域が凸集合となる問題 一般に非線形改革問題には大域最適解のほかに局所最適解が存在するが、 凸計画問題なら局所最適解が大域最適解となる 5

凸集合と凸関数の性質 なにかと都合がいい性質がたくさん • 定理3.1：集合𝑆1 、𝑆2 が凸集合なら、𝑆1 ∩ 𝑆2 も凸集合 • 定理3.2：関数𝑓1 、𝑓2 が凸関数なら、𝑢1 𝑓1 + 𝑢2 𝑓2 も凸関数 • 定理3.3：関数𝑓1 、𝑓2 が凸関数なら、max{𝑓1 , 𝑓2 }も凸関数 • 定理3.4：関数𝑔1 , … , 𝑔𝑙 が凸関数なら、集合𝑆 = {𝒙 ∈ ℝ𝑛 |𝑔𝑖 (𝒙) ≤ 0, 𝑖 = 1, … , 𝑙}は凸集合 • 定理3.5：凸計画問題では任意の局所最適解は大域最適解 6

凸関数と勾配 凸関数であるための必要十分条件が勾配を用いた式で表せる • 定理3.6：関数𝑓が凸関数であるための必要十分条件は任意の2点𝒙, 𝒚に対して、 𝑓 𝒚 ≥ ∇𝑓 𝒙 𝑇 𝒚 − 𝒙 + 𝑓(𝒙) • 系3.1：関数𝑓が凸関数であるための必要十分条件は任意の2点𝒙, 𝒚に対して、 ∇𝑓 𝒚 − ∇𝑓 𝒙 𝑇 (𝒚 − 𝒙) ≥ 0 7

凸関数とヘッセ行列 凸関数であるための必要十分条件がヘッセ行列で表せる • 定理3.7：関数𝑓が凸関数であるための必要十分条件は、 任意の𝒙に対してヘッセ行列∇2 𝑓(𝒙)が半正定値になること • 定理3.8：関数𝑓が狭義凸関数であるための十分条件は、 任意の𝒙に対してヘッセ行列∇2 𝑓(𝒙)が正定値になること ※必要条件ではない（ex. 𝑓 𝑥 = 𝑥 4 ） 8