厳密な大域的最適化

はじめに	一変数最適化
アルゴリズム	停留点と特異点を見付けることによる最適化
CAD (Cylindrical Algebraic Decomposition)法による最適化	整数上の最適化
線形最適化	領域上の最適化

はじめに

大域的最適化問題は， Minimize，Maximize，MinValue，MaxValue，ArgMin，ArgMaxを使って厳密解を求めることができる．

以下で，最小値が得られる

の大域的最小値と

の値を計算する：

以下で集合

に外接した，原点を中心とする円の半径を計算する：

集合

に外接した，原点を中心とする円の半径をパラメータ

と

の関数として計算する：

アルゴリズム

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

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

目的関数と制約条件すべてが線形である場合，大域的極値はシンプレックス法を使って厳密に計算することができる．このアプローチは線形分数目的関数にも使うことができる．

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

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

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

例題

三次曲線

上で原点に一番近い点を見付ける：

三次曲線

上で原点に一番近い点をパラメータ

の関数として見付ける：

以下は，三次曲線

上で原点に一番近く原点からの距離が

である点を可視化する．パラメータ

の値はスライダーを使って変更することができる．可視化ではMinimizeにより計算された最小値が使われる：

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

CAD法は，Wolfram言語ではCylindricalDecompositionとして直接利用できる．このアルゴリズムについては，「実多項式系」についてのチュートリアルで詳述してある．「実多項式系」で説明されているCAD法のオプション，特にCADConstructionオプションを設定すると，最適化関数の性能に影響を及ぼす可能性がある．次では大域的最適化問題を解くためにCAD法をカスタマイズする方法を説明する．

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

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

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

CAD法の射影段階

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

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

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

CAD法のリフティング段階

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

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

線形最適化

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

10個の変数を持つ乱数の線形最小化問題を解く：

目的関数が線形関数の分数であり，制約条件が線形（線形分数計画）である最適化問題は，線形最適化問題に簡約される．次は10個の変数を持つ乱数の線形分数最小化問題を解く：

一変数最適化

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

超越目的関数を持つ一変数最適化問題を解く：

見付かった最小値の可視化：

Wolfram言語は目的関数と制約条件が周期的であることを知っている：

解は超越関数のRootで与えられることがある：

入力に特殊関数が含まれている場合，解の完全性を証明するために数値積分が使われる可能性がある：

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

制約条件が等式，および有界のボックスを厳密に指定する不等式からなる場合は，ラグランジェ乗数が使われる．次は，制約条件の特異点において最小値に達した例である：

同じ目的関数の最大は，制約条件によって定義される集合の境界上で達成される：

次の例には停留点がない：

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

ここでは，制約条件の解集合上にある目的関数の停留点で最大値に達する：

ここでは，制約条件の解集合の境界への目的関数の制限の停留点で最大値に達している：

ここでは，制約条件の解集合の境界線の境界線上で最大値に達している：

ラグランジュ乗数法は超越関数を含むいくつかの最適化問題に使える：

ラグランジェ乗数法は，制約条件が単独の等式，または有界の解集合を持つ不等式からなる場合にも使われる：

整数上の最適化

整数線形最適化

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

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

7つの変数を持つ，ランダムに生成された整数線形最適化問題を解く：

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

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