最適化のこと回歴
こちらの資料をパラパラめくる。
最適化理論について、凸関数、どうして凸か、離散的な凸とは
凸関数の定義
以上
以下の実数
2階微分が非負
どうして凸かという話に移る。
凸計画問題の定義
凸集合の上で凸関数を最小化する問題
凸関数であると、局所的最小が大域的最小を意味する。
さらに双対性を利用できる（ルジャンドル変換、最大最小定理）
線形計画法なら、主問題と双対問題を考えて、前者の最小値が後者の最大値と一致する、という双対定理が成り立つ。
ルジャンドル変換
凸関数を、接線の包絡線で表すと、
ルジャンドル変換は、傾きを変数とする変換になる。
2回変換したら元に戻る辺り、情報を失ってはない。
フェンシェル双対定理ということで、凸関数と凹関数の差の最小値は、凹関数のルジャンドル変換したものから凸関数のルジャンドル変換したものを引いたものの最大値と一致する。
こういった双対性は、計算結果の精度を保証するために使われる。
離散数学の最適化問題で、最短路問題は簡単だが、TSPはNP困難なのは、
凸か否かが影響している。
集合の要素数では、だが、
集合関数について、劣モジュラ集合関数を定義する。
劣モジュラ関数について、Lovasz拡張が凸関数となる。双対定理もある。
凸構造（局所・大域最適性、双対性）を離散でも表したい。
凸関数を離散化する準備として、
通常凸をいじった、中点凸、等近凸の対応物として、
離散中点凸性（L凸関数）、M凸関数（交換定理）
離散ルジャンドル変換なるものも存在している。
全然わかんない。離散凸の部分からだ。
