[Inserted Image]

『Global Optimization Toolbox による最適化』

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

非凸2次計画問題

> restart;

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

with(GlobalOptimization):

Global Optimization Toolbox を利用して、非凸2次計画問題を解いてみます。ある矩形領域上の2次関数の大域的最小値を求めます。

> with(LinearAlgebra):

次に、非正定値行列を用いて非凸な関数Qを作ります;

> Q := Matrix( <<1.9,-3.5>|<5,-1/3>> );

Q := Matrix([[1.9, 5], [-3.5, (-1)/3]])

この行列が非正定値であることを確認します。

> IsDefinite( Q );

false

関数 x^t*Q*xを作ります。

> NonconvexQuadratic := expand( Transpose(<x,y>) . Q . <x,y> );

NonconvexQuadratic := 1.9*x^2+1.5*x*y-1/3*y^2

関数とそのコンター面を描いてみます。

<点[3.947, -10.000] 及び [-3.947, 10.000]に最小値が、また [0,0] が鞍点となっている様子がわかります。

> p1:=plot3d( NonconvexQuadratic, x=-10..10, y=-10..10, axes=boxed, transparency=.7, style=patch):
p2:=plot3d( -100, x=-10..10, y=-10..10, style=patchnogrid, color=NonconvexQuadratic ):

plots[display]( p1, p2, orientation=[125,60] );

[Plot]

およそほとんどの初期値からでも、Maple の局所探索コマンドは点[3.947, -10.000]において最小値を探し出します。

> NLPSolve( NonconvexQuadratic, x=-10..10, y=-10..10, initialpoint=[x=.1, y=0]);

[-62.9385964912280614, [x = 3.94736842105263186, y = -10.]]

しかし、もしも短絡的に初期値を選んでしまうと、標準組込の局所探索関数では鞍点[0,0]で計算が終了してしまいます。これは、現在の点で勾配が0となるからです。鞍点は勾配が0となりますが、極値ではありません。

> NLPSolve( NonconvexQuadratic, x=-10..10, y=-10..10, initialpoint=[x=0, y=0]);

[0., [x = 0., y = 0.]]

一方で、GlobalSolve コマンドならば、2つの最小値のうちのいずれかひとつを必ず見つけ出します。ここで探索領域は必ず指定しなければなりません。

> GlobalSolve( NonconvexQuadratic, x=-10..10, y=-10..10);

[-62.9385964912280684, [x = 3.94736842105263274, y = -10.]]

>