ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.3 節 Lagrange緩和 pp. 115-123 ここでは，時間制約付きの最短路問題に対する Lagrange緩和の適用を例に，Lagrange緩和の一般論について解説
大名の例題 １２時間以内に氷を献上せよ！ 終点 始点 飛脚に払う費用 と移動時間
Lagrange緩和のアイディア 制約の時間を費用に換算！ （１時間＝２両） １０両＋１時間×２（両/時間） 変換された費用に対する最短路 s->1->2->3->t （最適値は31） （本当の）費用＝23両，時間＝4時間 ->12時間以内だけど高い！
Lagrange緩和のアイディア 制約の時間を費用に換算（１時間＝１両） 新しい最短路 s->1->t （最適値は27） （本当の）費用＝11両，時間＝16時間 ->12時間を超えてしまった！
１時間＝？両にすれば良い？ 1 t s 2 3 数学者なら変数を導入！ １時間＝λ（ラムダと読む）両とする． 1+15λ 10+λ 3＋3λ 殿様が12時間にもってこいと言っている のだから，12×λ（両）は負担する． 1 t 10+λ 3＋3λ s 2＋λ 6＋λ [λを色々変えたときの最適パス の費用－殿様からのカンパ]はどんな関数？ 2 3 5+10λ 5+λ s->1->t: (10+1)+(1+15)λ-12λ=11+4λ s->1->2->3->t: (10+2+5+6)+(1+1+1+1)λ-12λ= 23-8λ s->2->1->t: =[ ] s->2->3->t: =[ ]
L(λ)：一番安いパスを選択することによって得られる関数（区分的に線形な凹関数）
L(λ）が下界を与えることを示そう！ （時間）制約付き最短路問題の定式化（0-1整数計画） 最短路の条件 枝vwの移動時間Tvw 注：数値を入れた具体的な導出はテキスト参照 最短路の条件 枝vwの移動時間Tvw 制限時間 Tmax 制約付き最短路の 場合は0,1条件が必要！
線形計画に緩和（0-1条件をとる！） （時間）制約付き最短路問題の線形計画緩和 時間制約条件 をLagrange緩和 （式に定数を乗じて 目的関数に加える）
Lagrange緩和問題の導出（１） （絶対に失敗しない方法） 時間制約を満たしていれば 必ず0以下 非負のLagrange乗数λ 最短路問題の制約！ 0以下のものを目的関数に加えて，さらに制約条件を外した->最適値以下（下界）
Lagrange緩和問題の導出（２） 殿様からもらえる （時間制約を緩和した）Lagrange緩和問題 制限時間分のカンパ １時間をλ（両）と変換した費用 最短路問題の制約！
Lagrange双対問題（なるべく良い下界を出そう！） Lagrage双対問題 パスがすべてわからないとこんな図は書けない！ 実際にはすべてのパスを列挙することは難しい！（数が多いから）
どうやってL(λ）の最大値を求めるの？ 劣勾配法（現在の傾き（劣勾配）だけを頼りに山を登る！） 9+16λ L(λ） 現在地点 λ=0 最短路を解くとs->2->1->t 傾き（劣勾配）は16λ 右方向が頂上だ！ λ
どうやってL(λ）の最大値を求めるの？(2) 右にステップサイズ（歩幅） 1/8でジャンプ！ 現在地点 λ=2 (=0+1/8×16) 最短路を解くとs->2->3->t 傾きは－8λ 左方向が頂上だ！ 23－8λ λ 2
どうやってL(λ）の最大値を求めるの？(2) 今度は左にステップサイズ1/8でジャンプ！ 現在地点 λ=1 (=2+1/8×(－8)） 最短路を解くとs->1->tと s->1->2->3->tの2本がある． 傾きはそれぞれ4λと－8λだから， ここが頂上だ！ 11+4λ 最良の下界は15 (=11+4=23-8) でも，最適値は16! 23－8λ λ 1
ステップサイズ（歩幅）の選び方 小さすぎると登り切らず に止まってしまう！ 大きすぎると頂上を 飛び越して振動してしまう！ 最初は大きく，段々と小さくしていく方法が良い．