[Inserted Image]

『Global Optimization Toolbox による最適化』

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

高次かつフラットな関数での最適値探索

> restart;

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

ここでは4次元の関数についての最適値探索を考えます。以下の関数は極めてフラットではありますが定数面ではなく、領域の端点上で極値(最小値)を持っています。

> objWood := 100*(y-x^2)^2+(1-x)^2+90*(z-w^2)^2+(1-w)^2+10.1*((y-1)^2+(z-1)^2)+19.8*(y-1)*(z-1);

objWood := 100*(y-x^2)^2+(1-x)^2+90*(z-w^2)^2+(1-w)^2+10.1*(y-1)^2+10.1*(z-1)^2+19.8*(y-1)*(z-1)

このような関数に対しては、局所探索ではフラットな領域上で極値を探し出そうとしますが、フラットな領域ではその勾配が0に近くなるため、最小値を探し出す前に探索が終了してしまいます。

実は、この関数の最小値は x=y=z=w=1 に存在します。なぜこの関数を最小にする点を見つけ出すことが難解であるかを見るために、z=1 及び w=1 での射影を考えてみます。

> objWoodXY := eval( objWood, { z=1, w=1 } );

objWoodXY := 100*(y-x^2)^2+(1-x)^2+10.1*(y-1)^2

コンター面を見ると、原点を中心にした領域上で関数は極めてフラット(勾配が滑らか)であることがわかります。局所探索では、そのような領域上で極値探索を行い、そして終了してしまいます。

> p1:=plot3d( objWoodXY+800, x=-2..2, y=-2..2, axes=boxed, transparency=.5, style=patch):
p2:=plot3d(0, x=-2..2, y=-2..2, style=patchnogrid, color=objWoodXY):
plots[display](p1,p2, orientation=[39,72] );

[Plot]

以下は、局所探索での計算です;

> NLPSolve( objWood, initialpoint=[w=3,x=-2,y=2,z=-2] );

[.148242645585180410, [x = .942001102189748196, y = .872155198582337588, z = 1.22185295231075752, w = 1.10990339393816284]]

大域探索では、真に最適な値を見つけ出します。

> GlobalSolve( objWood, w=-10..10, x=-10..10, y=-10..10, z=-10..10 );

[0.146859883390000718e-16, [x = .99999999876849566, y = .99999999773361736, z = 1.00000000226602093, w = 1.00000000100128728]]

>