オムライスの備忘録

数学・統計学・機械学習・プログラミングに関することを記す

トップ > データサイエンス > 【数理最適化】分野一覧 #まとめ編

【数理最適化】分野一覧 #まとめ編

データサイエンス

Index

数理最適化

最適化とは、様々な制約のもとで、数ある可能な選択肢の中から何らかの観点で 最適な選択を決定 (意志決定) をすること.

最適化は、データや情報の利活用のための欠かせない技術として、 日常の生活のありとあらゆる場面に、様々なレイヤーで浸透している.

様々な課題に対して、対象となる問題を数式で記述し、数理的な計算方法で、 最善策を求めることを数理最適化 (Mathematical Optimization) と呼ぶ.

このとき、対象を数式にて記述したものを数理モデル / Model という.

数理モデルを作成することを定式化 / Formulation という.



最適化では、対象問題を最適化問題 / Problem として定式化する.

目的達成度を表す指標を目的関数 / Object と呼ぶ.

選択する量を表した変数を決定変数といい、条件を制約条件という.



数理最適化は、数理計画法 / Mathematical Programming とも呼ばれることもある.

最適化問題の分類

  • 決定変数

    • 離散
    • 連続

  • 目的関数・制約関数

  • 目的関数・制約関数

    • 凸関数
    • 非凸関数

離散 / 組合せ 最適化

決定変数が離散値をとる最適化問題.

問題

  • グラグ・ネットワーク問題 / Graph・Network
  • 経路問題 / Routing
  • 集合被覆・分割問題 / Covering・Partitioning
  • スケジューリング問題 / Scheduling
  • 切り出し・詰込み問題 / Cutting・Packing
  • 配置問題 / Location
  • 割当・マッチング問題 / Assignment・Matching

割当・マッチング問題 / Assignment・Matching

割当・マッチング問題とは、ある集合の各要素について、 それぞれ別の集合のどの要素に割り当てると、様々な制約条件を満たしつつ、 最もよい割当を行うことができるのかを決定する問題のこと.

4色問題

  • A non-constructive proof of the Four Colour Theorem

アルゴリズム

連続

決定変数が連続値をとる最適化問題.

参考

書籍

Web サイト