3.9.8 数値最適化

極小値と極大値の探索

を始点としてを最小にするの値を求める．

In[1]:= FindMinimum[Gamma[x], {x, 2}]

Out[1]=

リストの最後の要素が最小に達する値を与える．

In[2]:= Gamma[x] /. Last[%]

Out[2]=

FindRootと同様にFindMinimumとFindMaximumもある点から始めて次第に最小値または最大値を求める．しかしこれらの関数は何かが見付かり次第結果を返すので，大域的な値ではなく極小値あるいは極大値を返す可能性がある．

この曲線には2つの極小値がある．

In[3]:= Plot[x^4 - 3x^2 + x, {x, -3, 2}]

Out[3]=

を始点とすると右側の極小値が求まる．

In[4]:= FindMinimum[x^4 - 3 x^2 + x, {x, 1}]

Out[4]=

こうすると左側の極小値が求まる．この場合はこれが大域的最小値でもある．

In[5]:= FindMinimum[x^4 - 3 x^2 + x, {x, -1}]

Out[5]=

大域的最小値と最大値の探究

これは即座に大域的最小を見付ける．

In[6]:= NMinimize[x^4 - 3x^2 + x, x]

Out[6]=

NMinimizeとNMaximizeは数値用のMinimize とMaximizeと考えることができる．しかし，MinimizeやMaximizeとは異なり，大域的最小や最大を必ず見付けられるとは限らない．関数がある程度滑らかで極小と極大の数が限られていればこれらの関数はかなり効果がある．

制約条件に従って大域的最大と最小を求める

x > 0という制約条件の元では，NMinimizeは右側の極小を与える．

In[7]:= NMinimize[{x^4 - 3x^2 + x, x > 0}, x]

Out[7]=

これは単位円内のx + 2yの最小を求める．

In[8]:= NMinimize[{x + 2y, x^2 + y^2 <= 1}, {x, y}]

Out[8]=

この場合，Minimizeは厳密な結果を返す．

In[9]:= Minimize[{x + 2y, x^2 + y^2 <= 1}, {x, y}]

Out[9]=

しかしこの場合には厳密な結果は返せない．

In[10]:= Minimize[{Cos[x + 2y], x^2 + y^2 <= 1}, {x, y}]

Out[10]=

これはNMinimizeを使うのと同じことで，数値近似を与える．

In[11]:= N[%]

Out[11]=

目的関数fと制約条件consの両方がすべての変数について線形の場合，最小化と最大化は「線形計画問題」に対応することになる．このような問題は明示的な方程式で記述するのではなく行列やベクトルで記述する方が便利なことがある．

行列形式の線形計画法

これは方程式の形をした線形計画法の問題である．

In[12]:= Minimize[{2x + 3y, x + 5y >= 10, x - y >= 2, x >= 1}, {x, y}]

Out[12]=

これは同じ問題を行列形式にしたものである．

In[13]:= LinearProgramming[{2, 3}, {{1, 5}, {1, -1}, {1, 0}},
{10, 2, 1}]

Out[13]=

リストbをペアの列, の形にすると方程式と不等式の制約条件を混ぜて指定することができる．が1ならi番目の制約条件は . x である．もしが0ならi番目の制約条件は . x == である．もしが-1ならそれは . x である．

最初の不等式がを使うようにする．

In[14]:= LinearProgramming[{2, 3}, {{1, 5}, {1, -1}, {1, 0}},
{{10, -1}, {2, 1}, {1, 1}}]

Out[14]=

LinearProgramming[c, m, b, l]でlをの上界と下界を表すペアのリスト, , , , ... にすることができる．

大規模な線形計画法の問題を解く場合には行列mをSparseArrayオブジェクトとして与えると便利なことが多い．