最適化

FrontPage

概要 †

• 最適化の落とし込み
• 落とし込み方をアルゴリズミックにできないだろうか…

メモ †

• qpOases カスタマイズ性の高いQP, イテレーション数を調整できるのでリアルタイムシステムに合っている
  • Quantinが使ってた

最適化ライブラリなどのまとめ Pareto optimum　パレート最適（理想的な資源配分が達成されている状態） - Lenear Programming (LP) Quadratic Programming (QP) Sequential quadratic programming (SQP) Mixed Integer Linear Programming (MILP) Mixed Integer Quadratic Programming (MIQP) Mixed Integer Nonlinear Programming (MINLP)

対称ならば固有値正で，正定かが議論可能

http://www2.kaiyodai.ac.jp/~yoshi-s/Lectures/Optimization/2013/lecture_1.pdf 凸性とヘッシアンの正定性が一致 一次元では，凸性＝2次微分が正であった（高校数学） 多次元では，凸性＝ヘッシアンが正定値である．

http://www2.kaiyodai.ac.jp/~yoshi-s/Lectures/Optimization/optimization15.html 最適化数学の講義ノート

機械学習プロフェッショナル http://www.amazon.co.jp/%E3%82%B9%E3%83%91%E3%83%BC%E3%82%B9%E6%80%A7%E3%81%AB%E5%9F%BA%E3%81%A5%E3%81%8F%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92-%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92%E3%83%97%E3%83%AD%E3%83%95%E3%82%A7%E3%83%83%E3%82%B7%E3%83%A7%E3%83%8A%E3%83%AB%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E5%86%A8%E5%B2%A1-%E4%BA%AE%E5%A4%AA/dp/4061529102/ref=pd_sim_14_2?ie=UTF8&dpID=41iyQTOdN-L&dpSrc=sims&preST=_AC_UL160_SR113%2C160_&refRID=10XCZCK3VS3WFP98BQTP

凸解析と最適化理論 http://www.amazon.co.jp/%E5%87%B8%E8%A7%A3%E6%9E%90%E3%81%A8%E6%9C%80%E9%81%A9%E5%8C%96%E7%90%86%E8%AB%96-%E6%95%B0%E7%90%86%E6%83%85%E5%A0%B1%E7%A7%91%E5%AD%A6%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E7%94%B0%E4%B8%AD-%E8%AC%99%E8%BC%94/dp/479520098X

有名な凸最適化の本（pdf） Convex Optimization http://stanford.edu/~boyd/cvxbook/ その日本語の解説（特に1-11は秀逸，元のwikiはここ

ラグランジェと凸性について http://www.az.cs.is.nagoya-u.ac.jp/class/adaptive-systems/chap_2_book.pdf

• pythonのOpenOpt
  • QPのサンプル

• 劣モジュラ関数

情報幾何と内点法を繋ぐ

概要 †

• いろんな最適化（50種類）
• NEOSサーバにソルバーがまとまっている．

序章 †

• 実行可能＝制約条件を満たす元がある
• 最適化問題の4パターン
  • 実行可能で最適解あり（実行可能領域があって有界）
  • 実行可能だが非有界で最適解なし（min xで拘束がないと最適値が-infになるなど）
  • 実行可能・有界だが最適解なし（制約条件の不等式に等号がついていない）
  • 実行不能（制約条件がΦ）

• クラス
  • 連続最適化
    • 凸>半正定値＞凸二次＞線形
    • 非凸＞非凸二次
  • 離散最適化
    • 非線形整数＞線形整数，0-1整数，線形0-1整数

• 0-1IPはNP困難

• 緩和問題
  • 実行可能領域を少し大きく（一つだったのを凸にするなど）することもできる．

• 包絡分析法(LP)
  • max 総出力/総入力 s.t. 入力は正
  • これは、max 出力 s.t. 入力=1, 出力<入力, 入力重み出力重み>0に等価となり、LP

• 多目的最適化(MLP)(LP)
  • 以下はすべてLPになる
    1. 加重平均法：目的関数に重みづけ
    2. 制約化法：一つ以上の目的関数を制約条件に移動し、目的関数>閾値と制約する方法
    3. ミンマックス法：全ての目的関数を制約条件に移動し、全目的関数>閾値とし、閾値を最小化する方法
    4. 目標計画法：abs(目標目的関数値-目的関数値)を最小化する方法

• 確率分布推定 (LP)
  • 期待値の上限下限と確率の公理（全部合わせて1）から、離散確率分布を求められる
• 区分線形関数最適化 (LP)
  • 与えられた点群xに対してmax(a_i^t x_i + b_i)の最小化は、min t s.t. a_i^t x_i + b_i < tで与えられる。
  • エピグラフというらしい。