Pythonを用いた最適化に関して
Pythonにおける最適化についてメモ。
- 集合(変数の添え字)
- 変数
- ハード制約(制約式として実装)
- ソフト制約(目的関数に利得項として実装)
- 目的関数
- その他(スラック変数)
などを設定してソルバーで処理するのが大まかな流れ。
PuLPがよく使われると思うのだが、何でもやれると思って実行してみると、実は非線形最適化をプログラムに課していて、PuLPがエラーを吐くみたいなのがよくある。
結局、scipy.optimizeを使うことになる印象。
PuLP, scipy.optimize以外にもいくつかあったので、それらも含めてここにメモしとく。
(他の方が書かれたものだが、)実装例のリンクも貼らせていただいた。
PuLP
Optimization with PuLP — PuLP 1.6.0 documentation
線形最適化だけ対応。最適化するときにあらかじめ最適化の数式(集合、変数、目的関数、制約条件など)を書くと思うが、それらと親和性が高い文法になっていると個人的に思う。
(例)数独
(例)線形計画法
Python SciPy : 線形計画問題を解く | org-技術
PuLP による線型計画問題の解き方ことはじめ - Qiita
scipy.optimize
Optimization and Root Finding (scipy.optimize) — SciPy v1.2.0 Reference Guide
線形最適化でも非線形最適化でも使える。(慣れれば大したことではないのかもしれないが、)文法にクセがある。
scipy.optimize.minimizeにおけるconstraintsオプションの与え方と意味について - Qiita
(例)線形計画法
Python SciPy : 線形計画問題を解く | org-技術
(例)ラグランジュの未定乗数法
ラグランジュの未定乗数法(言語処理のための機械学習入門) - Qiita
OpenOpt
線形最適化も非線形最適化もいける。
Pythonを用いた最適化 - Kazuhiro KOBAYASHI
OpenOpt, FuncDeisignerを使って2次計画法 – Ki_chi@Blog
cvxopt
凸2次最適化問題で用いるらしい。
picos
The PICOS Documentation — PICOS 1.1.3 Documentation
2次錐最適化問題で用いるらしい。
PICOSを使って錐計画問題を解く - Kazuhiro KOBAYASHI
変数の提供: ortoolpy
ortoolpyは、線形最適化ソルバーも提供する
(pulpを叩く。以下の16行目、24行目参照。
ortoolpy/etc.py at master · SaitoTsutomu/ortoolpy · GitHub
)ようだが、最適化問題の変数の提供というのが主な使い方だと思う。
変数が多くなってくると、大量に変数が扱えるような仕組み(ベクトルや行列)が欲しくなってくる。
そんなときは、ortoolpyがおすすめ。連続最適化、組み合わせ最適化などの離散最適化などによって、変数も連続値を使うか離散値を使うか以下のようにして決められる。
from ortoolpy import addvars (連続値)
from ortoolpy import addbinvars (離散値(二値))
(例)数独
番外:ベイズ最適化
番外:hyperopt
機械学習のパラメータチューニングに用いるもの。
番外:optuna
秋葉先生開発のツールということで話題に。機械学習のパラメータチューニングに用いるもの。
Optuna - A hyperparameter optimization framework
Optunaを使ってXGBoostのハイパーパラメータチューニングをやってみる
参考文献
Pythonによる数理最適化入門p.27,175,181,184
機械学習のエッセンスpp.235-239
Pythonを用いた最適化 - Kazuhiro KOBAYASHI