Pythonを用いた最適化に関して

 

Pythonにおける最適化についてメモ。

  • 集合(変数の添え字)
  • 変数
  • ハード制約(制約式として実装)
  • ソフト制約(目的関数に利得項として実装)
  • 目的関数
  • その他(スラック変数)

などを設定してソルバーで処理するのが大まかな流れ。

PuLPがよく使われると思うのだが、何でもやれると思って実行してみると、実は非線形最適化をプログラムに課していて、PuLPがエラーを吐くみたいなのがよくある。

結局、scipy.optimizeを使うことになる印象。

PuLP, scipy.optimize以外にもいくつかあったので、それらも含めてここにメモしとく。

(他の方が書かれたものだが、)実装例のリンクも貼らせていただいた。

 

PuLP

Optimization with PuLP — PuLP 1.6.0 documentation

線形最適化だけ対応。最適化するときにあらかじめ最適化の数式(集合、変数、目的関数、制約条件など)を書くと思うが、それらと親和性が高い文法になっていると個人的に思う。

(例)数独

数独を通して組合せ最適化を学ぼう - Qiita

(例)線形計画法

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

Home — 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 · PyPI

 変数が多くなってくると、大量に変数が扱えるような仕組み(ベクトルや行列)が欲しくなってくる。

そんなときは、ortoolpyがおすすめ。連続最適化、組み合わせ最適化などの離散最適化などによって、変数も連続値を使うか離散値を使うか以下のようにして決められる。

from ortoolpy import addvars (連続値)

from ortoolpy import addbinvars (離散値(二値))

 

 (例)数独

数独を通して組合せ最適化を学ぼう - Qiita

 

 

番外:ベイズ最適化

ベイズ最適化入門 - Qiita

 

番外:hyperopt

機械学習のパラメータチューニングに用いるもの。

Hyperopt by hyperopt

【翻訳】hyperopt チュートリアル - Qiita

 

番外:optuna

秋葉先生開発のツールということで話題に。機械学習のパラメータチューニングに用いるもの。

Optuna - A hyperparameter optimization framework

Optunaを使ってXGBoostのハイパーパラメータチューニングをやってみる

 

 

参考文献

Pythonによる数理最適化入門p.27,175,181,184

機械学習のエッセンスpp.235-239

最適化におけるPython - Qiita 

Pythonを用いた最適化 - Kazuhiro KOBAYASHI