『Global Optimization Toolbox による最適化』

数式処理システム Maple で動く実践的最適化アプリケーション

大域的最適化の利点

Maple 9.5 より標準で用意されている Optimization パッケージには、局所探索用のアルゴリズムが実装されています。局所探索では、目的関数の1階・2階の微分係数により極値を探索していきます。

Global Optimization Toolbox による大域的な最適解探索では、複数の極値を持つような領域上の目的関数に対する最適解も探し出せます。Maple 9.5 で用意されている標準の Optimization パッケージと比較してみましょう。

> restart;

> interface(warnlevel=0): with( plots ):
with(Optimization):
with(GlobalOptimization):

ここでは、以下の4次多項式を考えます;

> poly := (x-1)*(x-2)*(x-3.5)*(x-4.8);

poly := (x-1)*(x-2)*(x-3.5)*(x-4.8)

> plot(poly, x=0..5);

[Plot]

この多項式の最小値を、Optimization パッケージの NLPSolve 関数で求めてみます;

> NLPSolve(poly, initialpoint=[x=5]);

[-1.71396627012779357, [x = 1.40679933068723240]]

> NLPSolve(poly, initialpoint=[x=4]);

[-3.03603863879697267, [x = 4.29790996202590758]]

> NLPSolve(poly, initialpoint=[x=3]);

[-3.03603863879697267, [x = 4.29790996157305028]]

> NLPSolve(poly, initialpoint=[x=2]);

[-1.71396627012779401, [x = 1.40679932978430511]]

> NLPSolve(poly, initialpoint=[x=1]);

[-1.71396627012779357, [x = 1.40679933068584151]]

上記を見ると、初期点の与え方によって2つの極小値を求められていることがわかります。Optimization パッケージの NLPSolve は、非線形モデルに対して与えられた初期値から極小値(または極大値)を求めるために利用されるものです。

一方で、GlobalOptimization に用意される GlobalSolve で同じモデルに対する最小値探索を行ってみます。

> GlobalSolve(poly, x=0..5);

[-3.03603863879697311, [x = 4.29790996175691830]]

大域最適化により、真の最小値を求めることができています。