【しっかり学ぶ数理最適化】3.3.4~3.4

2025年度後期輪読会 #7(2025/11/27) しっかり学ぶ数理最適化 3.3.4-3.4 京都大学工学部情報学科数理工学コース B3 亀山龍汰 0

アジェンダ ◼ 3.3.4 有効制約法 ◼ 3.3.5 ペナルティ関数法・バリア関数法 ◼ 3.3.6 拡張ラグランジュ関数法 ◼ 3.3.7 内点法 ◼ 3.3.8 逐次二次計画法 1

有効制約法で求めたいもの 今回考える対象：凸二次計画問題 KKT条件を満たすような x* を求めると、これは大域最適解になる. 2

有効制約法の反復手順１ 制約の不等式のうち、𝑎𝑖𝑇 𝑥 = 𝑏𝑖 を満たすような添字集合を 𝐼 𝑥 𝑘 と表す. 等式が成り立つ制約のみを抜き出した緩和問題の最適解ഥx 方向に移動する. 下の連立方程式(最適性の十分条件)から最適解ഥx を求める. 3

有効制約法の反復手順2 制約の境界にぶつかればぶつかったところを次の点とする 最適解に変化がない→ラグランジュ乗数が非負なら終了、それ以外は制約を減らす 4

アジェンダ ◼ 3.3.4 有効制約法 ◼ 3.3.5 ペナルティ関数法・バリア関数法 ◼ 3.3.6 拡張ラグランジュ関数法 ◼ 3.3.7 内点法 ◼ 3.3.8 逐次二次計画法 5

ペナルティ関数法（外部ペナルティ関数法） 目的関数に制約条件をペナルティとして組み込む.（制約条件を破ったらペナルティ） 不等式制約 𝑔𝑖 𝑥 ≤ 0 へのペナルティ 𝑚𝑎𝑥{𝑔𝑖 𝑥 , 0} 2 等式制約 𝑔𝑖 𝑥 = 0 へのペナルティ {𝑔𝑖 𝑥 }2 ペナルティ関数 gത (x) : xに関する上記のペナルティを足し合わせたもの. ペナルティへの重み𝜌をより大きなものにしながら、最適化問題を解く. 問題点 • 厳密解は𝜌 → ∞だが、計算するうえで値が不安定になりやすい. • f𝜌ҧ 𝑥 は実行可能領域の境界で微分不可能 6

バリア関数法（内部ペナルティ関数法） 目的関数に制約条件をペナルティとして組み込む（制約条件境界に近づいたらペナルティ） 不等式制約 𝑔𝑖 𝑥 ≤ 0 へのペナルティ −𝑔𝑖 𝑥 −1 , − log −𝑔𝑖 𝑥 バリア関数 g෤ (x) : xに関する上記のペナルティを足し合わせたもの ペナルティへの重み𝜌をより小さなものにしながら、最適化問題を解く. 問題点 • 厳密解は𝜌 → 0だが、右図のように境界付近で目的関数が急峻になる ため、上記の最適化問題を解くことが数値的に困難になりやすい. 7

アジェンダ ◼ 3.3.4 有効制約法 ◼ 3.3.5 ペナルティ関数法・バリア関数法 ◼ 3.3.6 拡張ラグランジュ関数法 ◼ 3.3.7 内点法 ◼ 3.3.8 逐次二次計画法 8

拡張ラグランジュ関数法のアイデア ペナルティ関数法の弱点 ・厳密解を得るためには 𝜌 → ∞ にする必要があるが、目的関数が急峻になり悪条件化する。 ラグランジュ関数の弱点 ・単にラグランジュ関数を最小化しようとしても、最小値が存在しない場合があり、局所最適解 が得られるとは限らない。 ・ラグランジュ関数にペナルティ関数項(下に凸)を組込むことで、最小値を局所的に作れる。 ・ラグランジュ乗数の更新も行うことで、有限の 𝜌 でも厳密解に到達できるようにする。 9

拡張ラグランジュ関数法 アルゴリズムの概要 Step 1: 初期点 𝑥 0 , 𝑢 0 およびパラメータの初期値 𝜌0 を定める. 𝑘 = 0 とする. Step 2: 𝑥 𝑘 を初期点として 𝑥 について拡張ラグランジュ関数 𝐿𝜌 𝑥, 𝑢 𝑘 し最適化問題を解き, 新たな点 𝑥 𝑘+1 を求める. Step 3: 𝜌𝑘 𝑔ҧ 𝑥 𝑘 を最小化する制約な が十分に小さければ、つまり制約が満たされていると判断すれば終了する. Step 4: 𝑢 𝑘+1 = 𝑢 𝑘 + 𝜌𝑘 𝑔 𝑥 𝑘+1 とする. 𝜌𝑘+1 ≥ 𝜌𝑘 を満たすパラメータの値 𝜌𝑘+1 を定める. 𝑘 = 𝑘 + 1 として Step 2 に戻る. 10

アジェンダ ◼ 3.3.4 有効制約法 ◼ 3.3.5 ペナルティ関数法・バリア関数法 ◼ 3.3.6 拡張ラグランジュ関数法 ◼ 3.3.7 内点法 ◼ 3.3.8 逐次二次計画法 11

内点法のアイデア ・制約をすべて消すのではなく、スラック変数に対してバリア関数を定義して等式制約にする. ・最小化問題を解く代わりに、KKT条件を満たす解をニュートン法で求める. 12

内点法 目的関数が急峻になる境界を避けて、反復的に解を求める. 大規模な問題、不等式制約が多い問題に強い. 13

アジェンダ ◼ 3.3.4 有効制約法 ◼ 3.3.5 ペナルティ関数法・バリア関数法 ◼ 3.3.6 拡張ラグランジュ関数法 ◼ 3.3.7 内点法 ◼ 3.3.8 逐次二次計画法 14

逐次二次計画法のアイデア 非線形最適化問題の目的関数を2次近似、制約関数を1次近似して凸二次計画問題に持ちこむ KKT条件に対してのニュートン法 等価であることが示せる(p144) 𝑑 = 𝛿𝑥 としたときの、右の二次計画問題 しかし、ヘッセ行列が常に半正定値であるとは限らないため、正定値対称行列𝐵𝑘 で近似する 15

逐次二次計画法のアルゴリズム Step 1: 初期点 𝑥 0 と初期の近似行列 𝐵0 を定める. 𝑘 = 0 とする. Step 2: 下の凸2次計画問題を解いて, 探索方向 𝑑 とラグランジュ乗数 𝑢 𝑘+1 を求める. Step 3: |𝑑| が十分に小さければ終了する. Step 4: 直線探索によりステップ幅 𝛼𝑘 を求める. 𝑥 𝑘+1 = 𝑥 𝑘 + 𝛼𝑘 𝑑 とする. Step 5: パウエルの修正BFGS公式を用いて近似行列 𝐵𝑘 を更新し, 新たな近似行列 𝐵𝑘+1 を生成 する. 𝑘 = 𝑘 + 1 として Step 2 に戻る. 16

3.4 まとめ 有効制約法： 凸2次計画問題に対して, 有効な制約条件の集合を等式制約とし, 他の制約条件を無 視した凸2次計画問題の最適解を求める手続きを繰り返す反復法. ペナルティ関数法： 実行可能領域の境界近くで大きな値をとるペナルティ関数を目的関数に組み 込み, 制約つき最適化問題を制約なし最適化問題に変形して解く手法. 拡張ラグランジュ関数法： ラグランジュ関数とペナルティ関数を足し合わせた拡張ラグランジュ 関数を用いて, 制約つき最適化問題を制約なし最適化問題に変形して解く手法. 内点法： 制約つき最適化問題の実行可能領域の内部を通り KKT 条件を満たす点に収束する点列 を生成する反復法. 逐次2次計画法： 凸2次計画問題を部分問題として繰り返し解くことで, 制約つき最適化問題の KKT 条件を満たす点に収束する点列を生成する反復法. 17