4,5章：最適化のアルゴリズム（担当：今泉）
□導入
・前回：利用者均衡配分の概念と数学的解法を説明した。
・フロー保存則を用いて利用者均衡の定式化を行なった。
・今回：実際に利用者均衡配分を解いてみるのが4,5章。

■最急降下法（制約なし）
・ｘの値を決めた方向（降下ベクトル）にある値ずつ（ステップサイズ）変化
させ、関数値の増加減少の変化を見ることで、最適な値を探す。
・最終的にｘに関する微分値が十分小さくなる値まで続け、その値を解として
求める。
※ステップサイズと降下ベクトルを効率よくもとめたい。
・勾配ベクトル ×（-1）が降下ベクトル： -∇z(X)
・最も効率のよいα（ステップサイズ）はもちろん min[Xn + α(-∇z(Xn)]、つ
まり微分値が0のところ
・多次元の場合、他の極小値に収束する可能性があるのが降下法の問題

■（制約あり）
・不等式の等式が満たされる式を有効な制約式（勾配ベクトルにしたがって動
かした時にすぐに破られる可能性のある、境界条件にあるもの）といい、降下
方向に対しての制約となる。実際には勾配ベクトルとの内積が最小になるとこ
ろを降下ベクトルとして決める。
・有効でない制約式に関しても、破られる可能性のあるものとないものがあ
る。ステップサイズは、破られる可能性のある制約式の等号が満たされるとこ
ろであり、条件式より求められる。それが複数ある場合は、ステップサイズ候
補のうち、最小のものとなる。

→降下ベクトルとステップサイズが求まった。
・全体の関数で見たら、降下ベクトルは効率が悪い可能性がある。
・ステップサイズを独立に求める手順が煩雑。

■凸結合法
・許容集合を満たす解Ynを適当に定めて-∇z(X)をXn→Yn方向ベクトル（Yn -
Xn）に投影し、得られたベクトルにしたがって||Yn - Xn||だけ進める。
・進み方（減少値）が最大にするYnを定めればいい。
※線形近似した直線上で探す
・目的関数z(X)を直線近似したものに対して、同様にYnを定めて値が最も小さ
くなる解を探す。
・Ynに関する部分の微分値が最小になるところを求めれば、このとき降下ベク
トルは（Yn - Xn）である。
…制約がない場合、線形だと最小値が決まらないのでは？？　→　方向は決まる
がサイズは決まらない。（※次回までの宿題）

・ステップサイズを探す：線形計画法を解けばいい（解は必ず制約式上に乗
る）、つまり何らかの制約式が等号で成り立つ点になる。
・先ほどの図でいくと、必ず壁1上に解があることになる
・min z[Xn + α(Yn - Xn)], 0=< α =< 1を解けばいい。
・最急降下法との違いは、αmaxを出さずにYnを求めることで、必ずXnとYnの間
に解があることを保証できる。

まとめ
１．初期値に対して適当なYnをさだめる
２．ステップサイズを決める
３．収束判定により試行の終了/継続を判定

■使ってみる
・x はリンクのフロー（伊藤くんの問題だと何万個もある）
・f はパス（経路）のフローであり、xはfの関数なのでz(X)はfの関数とみなせる
・fの補助変数をgとすると、gに関する制約式が求められる。：今の解に対し
ての仮の値。
・先ほどの手順のように、y→降下方向→ステップサイズ→X（収束判定）の順に
値を決定していくと求まる。

□質疑
・なぜ、ｘを最適化したいのにｔをつかっているのか？
→利用者均衡を解く、という問題がmin z(X) = 総旅行時間（ｔの積分値）