【しっかり学ぶ数理最適化】3.3.2~3.3.3

2025年後期輪読会#7(2025/11/27) しっかり学ぶ数理最適化 3.3.2～3.3.3 京都大学大学院理学研究科 M2 佐藤海里 0

アジェンダ ◼ 3.3.2 不等式制約つき最適化問題の最適性条件 ◼ 3.3.3 双対問題と双対定理 1

3.3.2不等式制約つき最適化問題 以下の最適化問題を考える。 𝑛 𝑓, 𝑔𝑖 : ℝ → ℝとする。 Minimize 𝑓 𝑥 Under 𝑔𝑖 𝑥 ≤ 0 ⅈ = 1.2, … 𝑚 ・𝑔𝑖 𝑥 ≤ 0は等号が成立する場合としない場合がある。 成立する場合、添え字iを点xにおいて有効であると呼ぶ。 ・ 𝐼 𝑥 : = {𝑖𝜖 1,2, … , 𝑚 |𝑔𝑖 𝑥 = 0} を有効な制約条件の添え字集合とする。 2

有効という言葉をなぜ使うか
𝑥 ∗ を局所最適解とする。𝑔𝑖 (𝑥 ∗ ) < 0の場合、
𝑔𝑖 の連続性から、十分小さい𝑑に対して、 𝑔𝑖 (𝑥 ∗ + 𝑑) < 0
が成り立つ。これにより、 𝑥 ∗ の近傍においては、i番目の制約
はないものとみなせるから。有効な制約条件のみ考えればOK.

補題(Farkasの補題）
𝑣1 , 𝑣2 ,… 𝑣k をℝ𝑛 の一次独立なベクトルとする。
𝐾 ≔ {𝑐1 𝑣1 + 𝑐2 𝑣2 + ⋯ + 𝑐𝑘 𝑣𝑘 |𝑐𝑖 ≥ 0}とする。
𝑏 ∉ Kを一つ取ると、以下が成立。
∃𝑑𝜖ℝ𝑛 s. t. d ⋅ 𝑣i ≤ 0, 𝑑 ⋅ 𝑏 > 0(ⅈ = 1,2, … k).
証明：https://drive.google.com/file/d/1jyRTzg34P3RlwueQtEIhay6K0cyO2JG_/view?usp=sharing
3

• https://drive.google.com/file/d/1jyRTzg34P3RlwueQtEIhay6K0cyO2JG_/view?usp=sharing

最適性の必要条件(定理3.19) 有効な添え字のみを扱うことにする。𝑔𝑖 𝑥 ∗ ≤ 0 𝑖 = 1.2, … 𝑘 が有効な条件とする。 𝑔𝑖 𝑥 の一次近似から、 𝛻𝑔𝑖 𝑥 ∗ ・𝑑 ≤ 0が、 𝑔𝑖 𝑥 ∗ + 𝑑 ≤0のために必要。 0以上の𝑢𝑖 に対して、 − 𝛻𝑓 𝑥 ∗ ∉ σ𝑘𝑖=1 𝑢𝑖 𝛻𝑔𝑖 𝑥 ∗ と仮定すると、Farkasの補題より 𝛻𝑔𝑖 𝑥 ∗ ・𝑑 ≤ 0かつ、−𝛻𝑓 𝑥 ∗ ・𝑑 > 0すなわち、 𝛻𝑓 𝑥 ∗ ・𝑑 < 0 を満たす𝑑𝜖ℝ𝑛 が存在する。これは𝑥 ∗ が局所最適解であることに矛盾。 よって、 −𝛻𝑓 𝑥 ∗ は𝛻𝑔𝑖 𝑥 ∗ の錐結合で表せる。 すなわち、𝛻𝑓 𝑥 ∗ + σ𝑘𝑖=1 𝑢𝑖 𝛻𝑔𝑖 𝑥 ∗ = 0となるような0以上の𝑢𝑖 が存在する。 4

最適性の必要条件(定理3.19) 以上の内容をまとめると次のようになる。 局所最適解𝑥 ∗ は正則であるとする。 すなわち、 𝛻𝑔𝑖 𝑥 ∗ が一次独立とする。 このとき、以下を満たすベクトル𝑢∗ ∈ ℝ𝑚 が存在する。 ∗ 𝑘 ∗ ・𝛻𝑓 𝑥 + σ𝑖=1 𝑢𝑖 𝛻𝑔𝑖 𝑥 ∗ = 0 ・ 𝑢𝑖∗ 𝑔𝑖 𝑥 ∗ = 0, 𝑖 = 1,2, … 𝑚 ・ 𝑢𝑖∗ ≥ 0, 𝑖 = 1,2, … 𝑚 この条件をKKT条件という。 𝑢𝑖∗ 𝑔𝑖 𝑥 ∗ = 0 を相補性条件という。 5

凸計画問題における最適性の十分条件(定理3.22) 不等式制約つき最適化問題の目的関数𝑓及び制約関数𝑔𝑖 を微分可能 な凸関数とする。このとき、実行可能解𝑥 ∗ 𝜖ℝ𝑛 とベクトル𝑢 ∗ 𝜖ℝm が KKT条件を満たすならば、点𝑥 ∗ は大域最適解となる。 局所最適解であるための十分条件であるだけでなく、大域的最適解 であるための十分条件になっている。 6

3.3.3双対問題と双対定理 引き続き、不等式制約つき最適化問題を考える。 この最適化問題のラグランジュ関数は以下で与えられる。 𝐿 𝑥, 𝑢 := 𝑓 𝑥 + σ𝑚 𝑖=1 𝑢𝑖 𝑔𝑖 𝑥 (𝑢𝑖 ≥ 0と定める。) 𝑢𝑖 ≥ 0 , 𝑔𝑖 𝑥 ≤ 0から、𝑓 𝑥 ≥ 𝐿 𝑥, 𝑢 が成立。 𝑛 𝑢 ∈ ℝ𝑚 を固定した上で、𝑥 ∈ ℝ を動かし、𝐿 𝑥, 𝑢 を最小化する + 最適化問題(ラグランジュ緩和問題）を以下で定義する。 Mⅈnⅈmⅈze 𝐿 𝑥, 𝑢 := 𝑓 𝑥 + σ𝑚 𝑖=1 𝑢𝑖 𝑔𝑖 𝑥 Under 𝑥 ∈ ℝ𝑛 この問題を解くことにより、𝑓 𝑥 の下界が得られる。 7

弱双対定理(定理3.23) 𝑚ⅈ𝑛 ラグランジュ緩和問題の値を𝜃 𝑢 : = 𝑛 𝐿(𝑥, 𝑢)とすると、 𝑥∈ℝ 以下のようなラグランジュ双対問題が定義できる。 Maxⅈmⅈze 𝜃 𝑢 Under 𝑢 ∈ ℝ𝑚 + これらにより、以下の弱双対定理が得られる。 不等式制約つき問題の実行可能解𝑥と双対問題の実行可能 𝑚ⅈ𝑛 解𝑢に対して、𝑓 𝑥 ≥ 𝐿 𝑥, 𝑢 ≥ 𝑛 𝐿(𝑥, 𝑢) = 𝜃 𝑢 が成立. 𝑥∈ℝ 8

双対ギャップ 今度は逆に𝑥を固定して、𝑢を動かして、𝐿 𝑥, 𝑢 を最大化 𝑚 σ Maxⅈmⅈze 𝐿 𝑥, 𝑢 : = 𝑓 𝑥 + 𝑖=1 𝑢𝑖 𝑔𝑖 𝑥 Under 𝑢 ∈ ℝ𝑚 + 𝑥が制約条件 𝑔𝑖 𝑥 ≤ 0を満たさない場合、最大値は存在しない。 制約条件を満たす場合、𝑢𝑖 = 0のときに最大化される。このとき、 𝑚ax 𝑚ax 𝑚ⅈ𝑛 ∗ 𝑓 𝑥 = 𝑢 ∈ ℝ𝑚 𝐿 𝑥, 𝑢 .よって、 𝑓 𝑥 = 𝑛 𝑢 ∈ ℝ𝑚 𝐿 𝑥, 𝑢 𝑥∈ℝ + + 弱双対定理により、以下が成立。 𝑚ax 𝑚ax 𝑚ⅈ𝑛 𝑚ⅈ𝑛 ∗ ∗ ≥ 𝜃 𝑢 = 𝑢 ∈ ℝ𝑚 𝑛 𝑢 ∈ ℝ𝑚 𝐿 𝑥, 𝑢 = 𝑓 𝑥 𝑛 𝐿(𝑥, 𝑢) 𝑥∈ℝ + + 𝑥 ∈ℝ 𝑓 𝑥 ∗ －𝜃 𝑢∗ のことを双対ギャップという。 9

鞍点定理、強双対定理 鞍点定理 𝑚ax 𝑚ⅈ𝑛 ∗ ∗ ∗ ∗ 𝐿 𝑥, 𝑢 ≥ 𝐿 𝑥 , 𝑢 ≥ 𝐿 𝑥 , 𝑢 のとき、双対 𝑚 𝑛 𝑢 ∈ ℝ 𝑥∈ℝ + ギャップは0で、 𝑥 ∗ , 𝑢∗ はそれぞれ最適解。 強双対定理 f,giが凸関数で、スレイター制約条件を満たすとき、双対ギャップは０である。 10