厳密な大域的最適化

はじめに

厳密な大域的最適化問題は,MinimizeMaximizeを使って厳密解を求めることができる.

以下で集合 に外接した,原点を中心とする円の半径を計算する.
In[1]:=
Click for copyable input
Out[1]=
集合 に外接した,原点を中心とする円の半径をパラメータ の関数として計算する.
In[2]:=
Click for copyable input
Out[2]=

アルゴリズム

問題のタイプに応じて,いくつかの異なるアルゴリズムを使うことができる.

最も一般的なメソッドはCAD (cylindrical algebraic decomposition)法に基づいている.これは目的関数と制約条件が実代数関数である場合に適用される.この方法では,常に大域的極値(達しない場合は極値)が計算できる.パラメータが存在する場合,極値はパラメータの区分代数関数として計算することができる.このメソッドの不利な点は,変数の数という点において,非常に高度で二重指数関数的な複雑性が伴うという点である.パラメータを含まない特殊な場合には,より速い方法が使える.

目的関数と制約条件すべてが有理数係数と線形である場合,大域的極値はシンプレックス法を使って厳密に計算することができる.

1変量問題では,制約条件の解集合,不連続点,集合内の目的関数の導関数の零点を見付けるのに.方程式および不等式の解法が使われる.

大域的極値を見付ける別の方法に,ラグランジェ乗数かKKT(KarushKuhnTucker)条件を使って局所的極値をすべて求め,最小(または最大)のものを選ぶというものがある.しかし,完全な自動メソッドでは,複雑さが増す.局所的極値に必要な条件を解く上に,目的関数の滑らかさと制約条件の滑らかさ・非縮退性をチェックする必要がある.また,制約条件により定義された集合の境界(集合が非有界ならば無限)における極値もチェックしなければならない.一般にこれには実数体上の方程式および不等式の系を余分に解くことが必要になる.このため,CADの計算はCADアルゴリズムによる最適化における計算より無難しくなることがある.現在,Wolfram言語では有界の四角形の中の同値制約についてのみラグランジェ乗数が使われている.このメソッドでも,制約条件の多数の停留点と多数の特異点が有限であることが要求される.CADベースのアルゴリズムよりもこのメソッドの方がよい点は,超越問題がWolfram言語で解ける方程式系に導かれる場合は,その超越問題が解けるという点である.

CAD (Cylindrical Algebraic Decomposition)法による最適化

例題

三次曲線 上で原点に一番近い点を見付ける.
In[3]:=
Click for copyable input
Out[3]=
三次曲線 上で原点に一番近い点をパラメータ の関数として見付ける.
In[4]:=
Click for copyable input
Out[4]=
以下は,三次曲線 上で原点に一番近く原点からの距離が である点を可視化する.パラメータ の値はスライダーを使って変更することができる.可視化ではMinimizeにより計算された最小値が使われる.
In[5]:=
Click for copyable input
Out[13]=

最適化にカスタマイズされたCAD法

CAD法は,Wolfram言語ではCylindricalDecompositionとして直接利用できる.このアルゴリズムについては,「実多項式系」についてのチュートリアルで詳述してある.次では大域的最適化問題を解くためにCAD法をカスタマイズする方法を説明する.

座標関数の最小化への還元

代数的制約条件の解集合上の代数関数 を最小化する必要があるとする.ここで は変数のベクトル, はパラメータのベクトルである. を新しい変数とする.制約条件上の の最小化は,により与えられる半代数集合上の座標関数 の最小化と等価である.

が1つの変数 の単調関数ならば,新しい変数は必要ない.を最小化することができるからである.

CAD法の射影段階

まず変数 から始め,次に新しい変数 ,その次にパラメータ を投影する.

代数関数が存在する場合,それは新しい変数に置き換えられ,その変数が満足する方程式および不等式が加えられる.代数関数を置換する変数が最初に投影される.この変数はアルゴリズムのリフティング段階でも特別な注意が必要である.

ここで,同値制約の使用を含む,Hong,McCallun,Brownによる射影演算子の向上を使うことができる.新しい変数を導入する必要がある場合は,少なくとも1つの同値制約,つまり があることに注意する.

CAD法のリフティング段階

最初にパラメータ がリフトされ,セルの代数関数方程式および不等式の記述が構築される.パラメータのみに依存する制約条件があり,がパラメータセル上で完全に同じように偽であると判定できるならば,それ以上このセルをリフトする必要はない.

最小化変数 をリフトするときは, の最小値から開始し,制約条件を満足する最初のセルを見付けるまで続ける(残りの変数を深さ優先でリフトする).このセルが, の射影式の根に対応するならば,その根は の最小値であり,セルの任意の点の に対応する座標は最小に達した点を与える.パラメータが存在するならば,セルを囲む多項式の根に関するセルの点のパラメータ記述を得る.パラメータがない場合は,CAD法で使われる標本点を与えることができる.制約条件を満足する最初のセルが区間(ここで の射影式の根)に対応するなら, の値の下限であり,この下限値には達しない.また,制約条件を満足する最初のセルが区間に対応するならば, は下から有界でなくなる.

厳密な不等式制約条件

パラメータが存在せず,すべての制約条件が厳密な不等式であり,極値だけしか必要でない場合は,このアルゴリズムを格段に簡単にしたものを使うことができる( は制約条件の解集合)が分かっているならば,不等式制約条件を簡単に厳密にすることができる).この場合,これより下の次元のセルは無視できるので,射影は主係数,終結式,判別式からのみなる.リフティング段階では,完全次元のセルを構築する必要しかないので,代数的数の計算は必要ない.

Experimental`Infimum[{f,cons},{x,y,}]
制約条件 cons を満足する点集合上の f の値の下限を見付ける
Experimental`Supremum[{f,cons},{x,y,}]
制約条件 cons を満足する点集合上の f の値の上限を見付ける

極値を見付ける

で囲まれた集合を含む,原点を中心とする最小のボールを見付ける.同じ入力の完全なMaximizeの呼出しでは,10分以内に終了しなかった.
In[14]:=
Click for copyable input
Out[14]=

線形最適化

目的関数とすべての制約条件が線形であるならば,大域的極値はシンプレックス法を使って厳密に計算することができる.

10個の変数を持つ乱数の線形最小化問題を解く.
In[15]:=
Click for copyable input
Out[22]=
目的関数が線形関数の分数であり,制約条件が線形(線形分数計画)である最適化問題は,線形最適化問題に簡約される.次は10個の変数を持つ乱数の線形分数最小化問題を解く.
In[23]:=
Click for copyable input
Out[31]=

一変数最適化

一変数の問題では,制約条件の解集合,集合内の目的関数の導関数の不連続点と零点を見付けるのに,方程式および不等式の解法が使われる.

超越目的関数を持つ一変数最適化問題を解く.
In[32]:=
Click for copyable input
Out[32]=
見付かった最小値の可視化.
In[33]:=
Click for copyable input
Out[33]=
Wolfram言語は目的関数と制約条件が周期的であることを知っている.
In[34]:=
Click for copyable input
Out[34]=

停留点と特異点を見付けることによる最適化

次は,制約条件の特異点において最小値に達した例である.
In[35]:=
Click for copyable input
Out[35]=
In[36]:=
Click for copyable input
Out[36]=
同じ目的関数の最大は,制約条件によって定義される集合の境界上で達成される.
In[37]:=
Click for copyable input
Out[37]=
In[38]:=
Click for copyable input
Out[38]=
次の例には停留点がない.
In[39]:=
Click for copyable input
Out[39]=

次は同じ制約条件を持つ,三次元の例題である.目的関数によって,最大値には制約条件の解集合上の目的関数の停留点,制約条件の解集合の境界の目的関数の制約の停留点,制約条件の解集合の境界の境界で達する.

ここでは,制約条件の解集合上にある目的関数の停留点で最大値に達する.
In[40]:=
Click for copyable input
Out[40]=
In[41]:=
Click for copyable input
Out[41]=
ここでは,制約条件の解集合の境界への目的関数の制限の停留点で最大値に達している.
In[42]:=
Click for copyable input
Out[42]=
In[43]:=
Click for copyable input
Out[43]=
ここでは,制約条件の解集合の境界線の境界線上で最大値に達している.
In[44]:=
Click for copyable input
Out[44]=
In[45]:=
Click for copyable input
Out[45]=
ラグランジュ乗数法は超越関数を含むいくつかの最適化問題に使える.
In[46]:=
Click for copyable input
Out[46]=
In[47]:=
Click for copyable input
Out[47]=

整数上の最適化

整数計画法

整数計画法とは目的関数が線形で,制約条件が線形有界であり,変数が整数範囲にある最適化問題である.

整数計画法問題を解くために,Wolfram言語はまず同値制約を解き,問題を不等式制約条件のみを含む問題に還元する.次に格子還元法を使い,不等式系をより簡単な形式に置き換える.最後に分枝限定法を使って簡約された最適化問題を解く.

7つの変数を持つ,ランダムに生成された整数計画問題を解く.
In[48]:=
Click for copyable input
Out[58]=

整数解発見と組み合せた実数上の最適化

制約条件の整数解集合上で関数 を最小化しなければならないとする.の実数解集合上の の最小値とする.を満足する整数点が存在するならば,の整数解集合上の の最小値である.そうでない場合は,等の整数解を見付けなければならない.このヒューリスティックは,実最適化問題およびすべての整数解発見問題を解くことができ,前もって決まっている試行回数内に整数解を見付けることができる場合にのみ有効である.Wolfram言語ではデフォルトで10個の最適値候補を試す.システムオプションを使うと,この値を変更することができる.

三次方程式 の下にある点の中から を最大化する整数座標を持つ点を見付ける.
In[59]:=
Click for copyable input
Out[59]=
In[60]:=
Click for copyable input
Out[60]=