[Inserted Image]

『Global Optimization Toolbox による最適化』

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

非凸実行可能領域

> restart;

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

次に、ある平面領域上から単位円を除いたような非凸領域での最小値探索を実行してみましょう。次の目的関数 obj 及び制約条件 constraint を考えます;

> obj := x^2 + y^2 - x + y;
constraint := x^2 + y^2 >= 1;

obj := x^2+y^2-x+y

constraint := 1 <= x^2+y^2

この問題では、最小値はおよそ点[0.707, -0.707]に存在します。(以下のグラフの、赤丸で表示されているところ)

目的関数のコンター線が表示されているところに注目してください。

点[-2, 2]から探索を始めた場合、局所探索では、青丸で示されるようにおよそ点[-0.707, 0.707]付近の“最適でない”極小値を返してきます。この理由は、点[-0.707, 0.707]の点における目的関数の勾配は、実行不可能領域の境界に対して垂直であり、すなわち局所探索がそこで終了してしまうからです。

> p1 := plottools[disk]([0,0],1,color=green):
p2 := plots[contourplot](obj, x=-2..2, y=-2..2, coloring=[blue,red], contours=20):
p3 := plots[pointplot]([[.707,-.707]],color=red, symbolsize=20, symbol=circle):
p4 := plots[pointplot]([[-.707,.707],[-2,2] ],color=blue, symbolsize=20, symbol=circle):
plots[display]( p1, p2, p3, p4 );

[Plot]

> NLPSolve( obj, {constraint}, x=-2..2, y=-2..2, initialpoint=[x=-2,y=2]);

[2.41421356273966215, [x = -.707106781262466066, y = .707106781262466066]]

GlobalSolve では、最適な値を見つけ出します。

> GlobalSolve( obj, {constraint}, x=-2..2, y=-2..2);

[-.414213564542023849, [x = .707106777775725836, y = -.707106779361111992]]

>