数理最適化

Last updated Unknown Edit Source

数理最適化、数理計画

• 目的を達成するための最善の手を見つける

• オペレーションズリサーチ: 数学/統計/アルゴリズムで計画の効率的な手を決定する科学的手法

• 最適化問題として定式化してモデルを作って、

• そのモデルベースで最適化して、

• 現実の意思決定に活用して確認

• 現実の問題をモデル化するのが難しい、キモ

• 連続最適化問題の分類

  • 非凸計画問題は分かりやすいゴールがない問題? (定義なんだろう)

• 手法の研究

  • 多項式時間で解ける方法を探す
  • 機械学習

• 簡単なものは、高校数学でもやっている

  • グラフの最大/最小値求める問題
  • グラフ書かずに解けるように、単体法、内点法

• 最短路問題: 経路を0/1の集合で表すから0-1整数計画問題 (not連続最適化)

  • ただ、条件を緩めることで線形計画問題に帰着できる

• 機械学習の回帰とかもこれにあたる

  • 最急降下法
    • 微分して0はあくまでも正解の十分条件
    • ただ現実的な解法としてはあり

• Loss Functionの最小化

• 最近のトレンド

  • 機械学習が流行ってきたので、一次最適化法が再度盛り上がってる
    • 一次最適化 = 一階微分 (一度だけ) #情報科学