ざっくりと最適化についてまとめる（少し詳しい目次程度）。
手法間のつながりとか流れを確認する用なので、内容には踏み込まない。
証明や細かい解説は書籍を参照すること*1。

間違いがあればご指摘ください。

勾配法

最急降下法
今いる地点の勾配（1階微分）が最大になる方向へ突き進む方法。
ニュートン法
最適化したい関数を2次の項までテイラー展開する（二次近似）。近似した関数の勾配（1階微分）が最大になる方向へ突き進む方法。 2次の項まで反映されるので、最急降下法より収束が早く、二次収束することが知られている。二階微分（ヘッセ行列）の逆行列を計算しなければならないのが難点。（数値計算において逆行列は桁落ちが激しいので避けたいということ）
共役勾配法
最適化したい関数を2次の項までテイラー展開する（二次近似）。近似した関数の勾配（1階微分）=０の式を作ると、二次の項でヘッセ行列xベクトルの形が出てくる。このベクトルが共役勾配である。共役勾配は最適化したい関数の1階微分から得られる勾配とは、少しずれたベクトルになる。ずれ分のベクトルを導入し、共役勾配=勾配+αずれベクトルと線形和で表現し、αを求めることでヘッセ行列の逆行列を計算することを回避した。

最小二乗法

あまりに一般的すぎるので省略

非線形最小二乗法

最小二乗法は連立一次方程式の解を求める方法だった。非線形の連立方程式に拡張したもの。

ガウス・ニュートン法
複雑な関数の2階微分を計算するのは困難なので、ヘッセ行列を近似してからニュートン法を用いる方法。解の近傍で与式=0と置ける場合、それを利用して二階偏微分の項を近似的に0とみなすことでヘッセ行列を2階微分を計算せずに近似できる。解の近傍でしか使えないのが難点。
レーベンバーグ・マーカート法
ガウス・ニュートン法は解の近傍でしか使えない。そこで、まず勾配法などで雑に探索を行い解の近傍に到達したらガウス・ニュートン法に切り替えるのがこの方法。

統計的最適化

最尤推定
- 出力誤差モデル
  誤差が正規分布に従うとすれば、最小二乗法と一致する。
- 入力誤差モデル
  入力にも誤差がのっているとするモデル。データ点から推定する直線までの距離を最小化する。
データ分類（クラスタリング）
- 教師なし学習
  ベイズ更新でクラスへの所属確率が収束するまでループ。EMアルゴリズムの特別な場合になっている。
- EMアルゴリズム
  未知変数について周辺化した対数尤度関数の極値計算から自然と導出される。
  未知変数の周辺化がEステップ、極値を求めるのがMステップに対応する。
  推定パラメータが収束するまでEステップとMステップを反復する。
  この反復過程で対数尤度が単調増加することはJensenの不等式から証明できる。

線形計画法

1次不等式による制約付きで、1次式を最大化/最小化する。

スラック変数
制約不等式を等式にするために導入する非負の変数。
シンプレックス法
線形計画問題を組織的に解く（可能領域の頂点を全探索せずに済む）。実装にはシンプレックス表（タブロー）を用いた実装が便利？常に関数が増大するように探索するので、初期の解が非負ならその後の解も非負である。
- 退化（縮退）
  n次元空間内の可能領域を表す多面体の頂点が、n+1枚以上の平面が交わっている点になっていると起こる。2次元平面で考えれば可能領域を表す直線３つ以上が１つの点を共有してる状態で、２直線の交点として考えたときに解釈が複数存在することになる。解釈を変えても関数の値が変化しない。この状態を退化（縮退）という。この時、シンプレックス法のアルゴリズム的には退化の分無駄なステップを刻むことになる。退化から脱出する方法としては、辞書式順序による方法、および記号摂動法などがあるとのこと。
- 人工変数を導入
  出発時の解が見つからない（見つかりにくい）場合に人工変数を導入する。
  最適解が求まった時に人工変数が0になっていればなかったことと同じなので問題ないという考え。
  可能領域が空集合になっていると、人工変数が0にならない（そのようなケースの判定に使える）
- 双対原理
  書くと長いので省略。「裏返しの関係」ともいわれる？難しい話ではないので調べてみると良い（ただ、ややこしくはある）。線形計画では、双対問題を解くと、元の問題の最適解が求まる。
  ただ、線形計画問題は簡単に解けるのであまりメリットを感じない（個人の感想）。

非線形計画法

制約条件も目的関数も一般の非線形関数になったもの。

凸計画
目的関数が上に凸、かつ可能領域も凸な問題。
線形計画法も凸計画問題の一つ。
２次計画
制約条件がすべて線形
目的関数が上に凸な問題
（cvxoptというPythonパッケージがあって簡単に使える。）

ラグランジュ乗数

目的関数は上に凸、制約不等式はすべて下に凸、制約等式がすべて1次式。
この時、制約不等式、制約等式にラグランジュ乗数をかけて目的関数と合わせてラグランジュ関数をつくる。
ラグランジュの未定乗数法を理解しておくとわかりやすい。
ここから、KKT（カルーシュ・キューン・タッカー）条件がでてくる。

双対原理

線形計画の時の拡張になっている。
線形計画問題では双対問題を解くことで主問題の最適解が求まった。
一方で2次計画では、双対問題を解くことで主問題の最適解が求まるわけではない。
しかしながら主問題より簡単に解け、主問題の解を限定できる点で強力。
また、主問題と双対問題を突き合わせることで最適解かどうかの判定に使える（サポートベクターマシーンなどに利用されているらしい）。

動的計画法

変数が離散値をとる関数の最適解を効率的に求める方法。
大きな問題を小さな問題に分割して再帰的に解いていく。
最適経路問題として考えた方がわかりやすいかもしれない（個人の感想）。
最適性原理が成り立つ（どの部分解もその部分問題の最適解になっている）。
半順序しか与えられていない問題にも使えるらしい（半順序ってなに？って人は集合・位相論のテキストを読むとよい）。