【しっかり学ぶ数理最適化】2.3.3~2.3.5

2025年後期輪読会 しっかり学ぶ数理最適化 (2.3.3~2.3.5) 京都大学 工学部 情報学科 B3 稲葉 陽孔 1

アジェンダ ■ 双対定理 ■ 感度分析 ■ 双対単体法 2

アジェンダ ■ 双対定理 ■ 感度分析 ■ 双対単体法 3

双対定理 以下のような主問題と、それに対応する双対問題がある 主問題 主問題（＋スラック変数） 双対問題 主問題の制約より 4

双対定理 今の流れを一般化すると、以下のような式になる 一般式 この時の主問題(P)と双対問題(D)の関係性を表した双対定理がある 5

双対定理 Pの目的関数値<=Dの目的関数値（弱双対定理） 証明 6

双対定理 この時、この定理が成り立つ 証明 非有界：目的変数の取りうる範囲の上(下)限がない(問題が目的変数の最大(小)化の場合) 7

双対定理 また、この定理が成り立つ 8

双対定理 証明（強双対定理） 9

双対定理 また、相補性定理も成り立つ 10

双対定理 証明(相補性定理) 11

双対定理 これらから、主問題と双対問題の関係性において以下が成り立つ ：強双対定理 ：弱双対定理 12

アジェンダ ■ 双対定理 ■ 感度分析 ■ 双対単体法 13

感度分析 今回の問題では入力データの正確な値や条件を事前に把握できたが、常に そうとは限らない →入力データ(bやc)の変化に伴う最適基底解xの変化が重要になる →感度分析によって分析 問題設定 xi：野菜iの摂取量(0以上) Ai,j：野菜iにおけるビタミンjの含有量 bj：ビタミンjの摂取量 ci：野菜iの価格 c^Tx:野菜の合計値段(最小化を目的とする) cのΔc変動やbのΔb変動によって、最適基底解がどれだけ動くか分析 →最適基底解のロバスト性を見れる 14

感度分析 cを動かした場合 主問題（＋スラック変数） 15

感度分析 bを動かした場合 主問題（＋スラック変数） ビタミンiの必要量を1増やしたときの合計価格の変化量を限界価格 と呼ぶ 16

感度分析 双対問題の最適解は新たな変数追加時も役立つ 野菜kを新たに考慮する場合、双対問題に式1が追加で課される 野菜kを導入しても最適解yは制約を満たす＝双対問題の最適値は不変 満たさない場合＝双対問題の最適値が減少＝主問題の最適値が改善 式1 17

アジェンダ ■ 双対定理 ■ 感度分析 ■ 双対単体法 18

双対単体法 主問題（＋スラック変数） 新たな変数が追加された場合は今までの最適基底解は制約条件を満たす が、bが変更されると最適基底解そのものが実行できない可能性がある →変更前の最適解を元に変更後の最適解を求める（再最適化） 19

双対単体法 主問題の場合 主問題（＋スラック変数） = 20

双対単体法 双対問題の場合 双対問題（＋スラック変数） 双対問題 = 21

双対単体法 双対問題の場合 双対問題（＋スラック変数） 主問題（＋スラック変数） 先ほどの式から、 :問題における辞書 が成立し、主問題の辞書を転置+符号の入れ替えをすれば双対問題の辞書も得られる 22

双対単体法 双対問題（＋スラック変数） 主問題（＋スラック変数） 主問題のbの変更=双対問題のbの変更なので、 bが変更しても変更前の双対問題の基底解(y_p)は実行可能解のまま →双対問題に対して単体法を適応し、y_pを初期解として双対問題の制約条件を満たしつつ、目的関数を 最大化する操作をすればよい この考えに基づいた最適基底解の求め方を双対単体法 と呼ぶ メリット：制約式を追加しても単体法と比べて効率的に計算できる 23

双対単体法（例） 初期問題（主問題） 双対問題(+スラック変数) 主問題（＋スラック変数） 24

双対単体法（例） 初期問題（双対問題） 双対問題(+スラック変数) 主問題（＋スラック変数） 25

双対単体法（例） 制約条件の変化 主問題（変更前） 制約条件の変化に伴い、基底解の存在範囲が変化する 主問題（変更後） 特に左図の赤丸（変更前の最適基底解）は実行不能になった 26

双対単体法（例） 制約条件の変化 主問題（変更前） 双対問題（変更後） ←双対問題の目的値も変化 27

双対単体法（例） 制約条件の変化 主問題（変更前） 双対問題（変更後） ←双対問題の目的値も変化 28

双対単体法（例） 制約条件の変化 主問題（変更前） 双対問題（変更後） 29

双対単体法（例） 双対単体法と相補性条件 主問題 双対問題 →双対ギャップ 30