最適化

編集

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 最適化数学の講義ノート

機械学習プロフェッショナル

凸解析と最適化理論

有名な凸最適化の本（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

情報幾何と内点法を繋ぐ (リンク切れ)

概要

  • いろんな最適化（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で与えられる。
    • エピグラフというらしい。

最終更新: 2020-01-01