制約付き最適化

数学的最適化において、制約付き最適化（一部のコンテキストでは制約最適化と呼ばれる）は、いくつかの変数に制約が ある場合に、それらの変数に関して目的関数を最適化するプロセスです。目的関数は、最小化されるコスト関数またはエネルギー関数、または最大化される報酬関数または効用関数のいずれかです。制約は、満たす必要のある変数の条件を設定するハード制約、または変数の条件が満たされない場合にその程度に基づいて目的関数でペナルティが課される変数値を持つソフト制約のいずれかです。

制約付き最適化問題（COP）は、古典的な制約充足問題（CSP）モデルの重要な一般化です。^{[1] COPは、最適化される}目的関数を含むCSPです。最適化部分を処理するために多くのアルゴリズムが使用されます。

一般的な制約付き最小化問題は次のように記述される: ^[2]

${\displaystyle {\begin{array}{rcll}\min &~&f(\mathbf {x} )&\\\mathrm {subject~to} &~&g_{i}(\mathbf {x} )=c_{i}&{\text{for }}i=1,\ldots ,n\quad {\text{等式制約}}\\&~&h_{j}(\mathbf {x} )\geq d_{j}&{\text{for }}j=1,\ldots ,m\quad {\text{不等式制約}}\end{array}}}$

ここで、 およびは満たす必要のある制約（これらはハード制約と呼ばれます）であり、 は制約に従って最適化する必要のある目的関数です。 ${\displaystyle g_{i}(\mathbf {x} )=c_{i}~\mathrm {for~} i=1,\ldots ,n}$${\displaystyle h_{j}(\mathbf {x} )\geq d_{j}~\mathrm {for~} j=1,\ldots ,m}$${\displaystyle f(\mathbf {x} )}$

制約最適化問題と呼ばれるいくつかの問題では、目的関数は実際にはコスト関数の合計であり、各コスト関数はソフト制約(満たされることが望ましいが必須ではない制約) に違反する範囲 (ある場合) にペナルティを課します。

多くの制約付き最適化アルゴリズムは、ペナルティ法を使用することで、制約のないケースに適応できます。しかし、制約のない方法で実行される探索ステップは、制約のある問題では受け入れられない場合があり、収束が不十分になります。これはマラトス効果と呼ばれます。^[3]

非常に単純な問題、たとえば単一の等式制約に従う 2 つの変数の関数の場合、置換法を適用するのが最も実用的です。^[4]その考え方は、制約を目的関数に代入して、制約の効果を組み込んだ合成関数を作成するというものです。たとえば、目的が を条件に を最大化することであるとします。制約は を意味し、これを目的関数に代入して を作成できます。1 次必要条件は となり、これを について解くことができるため、 となります。 ${\displaystyle f(x,y)=x\cdot y}$${\displaystyle x+y=10}$${\displaystyle y=10-x}$${\displaystyle p(x)=x(10-x)=10x-x^{2}}$${\displaystyle {\frac {\partial p}{\partial x}}=10-2x=0}$${\displaystyle x=5}$${\displaystyle y=10-5=5}$

制約付き問題に等式制約のみがある場合は、ラグランジュ乗数法を使用して、変数の数が元の変数の数と元の等式制約の数の合計である制約なしの問題に変換できます。または、制約がすべて等式制約であり、すべて線形である場合は、一部の変数について他の変数を使用してそれらを解決し、前者を目的関数から置き換えて、より少ない数の変数で制約なしの問題を残すことができます。

不等式制約により、問題は幾何学的最適条件、フリッツ・ジョン条件、およびカルシュ・キューン・タッカー条件の観点から特徴付けることができ、これらの条件の下では単純な問題を解決できる可能性があります。

目的関数とすべてのハード制約が線形であり、一部のハード制約が不等式である場合、問題は線形計画問題です。これは、通常は問題のサイズで多項式時間で機能しますが、保証されていない単体法、または多項式時間で機能することが保証されている内点法によって解決できます。

目的関数または制約の一部が非線形であり、制約の一部が不等式である場合、問題は非線形計画問題です。

すべてのハード制約が線形で、一部が不等式であるが、目的関数が二次である場合、問題は二次計画問題です。これは非線形計画法の一種です。目的関数が凸関数であれば、楕円体法によって多項式時間で解決できます。そうでない場合は、問題はNP 困難である可能性があります。

不等式制約を許容することで、非線形計画法に対するKKT アプローチはラグランジュ乗数法を一般化します。これは微分可能性と凸性の下で適用できます。

制約最適化は、分岐限定アルゴリズムで解決できます。これは、実行中に見つかった最適なソリューションのコストを保存し、それを使用して検索の一部を回避するバックトラック アルゴリズムです。より正確には、アルゴリズムは、保存されている最適なコストよりも優れたコストのソリューションを形成するために拡張できない部分的なソリューションに遭遇するたびに、このソリューションを拡張しようとするのではなく、バックトラックします。

コストを最小限に抑える必要があると仮定すると、これらのアルゴリズムの効率は、部分的なソリューションを拡張することで得られるコストがどのように評価されるかによって決まります。実際、アルゴリズムが部分的なソリューションからバックトラックできる場合、検索の一部がスキップされます。推定コストが低いほど、アルゴリズムは優れています。推定コストが低いほど、これまでに見つかったソリューションの最適なコストよりも低くなる可能性が高いためです。

一方、この推定コストは、ソリューションを拡張することで得られる実効コストよりも低くすることはできません。そうしないと、これまでに見つかった最良のソリューションよりも優れたソリューションが存在するにもかかわらず、アルゴリズムがバックトラックする可能性があります。その結果、アルゴリズムでは、部分的なソリューションを拡張することで得られるコストの上限が必要になり、この上限は可能な限り小さくする必要があります。

このアプローチのバリエーションであるハンセン法は、区間法を使用します。^[5]この方法は本質的に長方形制約を実装します。

部分解のこの上限を評価する 1 つの方法は、各ソフト制約を個別に検討することです。各ソフト制約について、割り当てられていない変数への割り当ての最大値が想定されます。ソフト制約はより高い値を想定できないため、これらの値の合計が上限となります。ソフト制約の最大値は異なる評価から得られる可能性があるため、上限は正確です。つまり、あるソフト制約が に対して最大である一方で、別の制約が に対して最大である可能性があります。 ${\displaystyle x=a}$${\displaystyle x=b}$

この方法^[6]は、問題に対して分岐限定法を実行する。ここで、は変数の数である。このような各問題は、元の問題から一連の変数とそれらを含む制約を削除することによって得られる部分問題である。変数の問題が解かれた後、その最適コストは他の問題を解く際の上限として使用できる。 ${\displaystyle n}$${\displaystyle n}$${\displaystyle x_{1},\ldots ,x_{i}}$${\displaystyle x_{i+1},\ldots ,x_{n}}$

特に、割り当てられていない変数を持つソリューションのコスト推定は、評価された変数から得られるコストに追加されます。実質的には、これは評価された変数を無視し、割り当てられていない変数で問題を解決することに相当しますが、後者の問題はすでに解決されています。より正確には、割り当てられた変数と割り当てられていない変数の両方を含むソフト制約のコストは、上記のように（または任意の他の方法を使用して）推定されます。割り当てられていない変数のみを含むソフト制約のコストは、代わりに、この時点で既にわかっている対応する問題の最適解を使用して推定されます。 ${\displaystyle x_{i+1},\ldots ,x_{n}}$

ロシアン ドール サーチ法と動的プログラミングには類似点があります。動的プログラミングと同様に、ロシアン ドール サーチはサブ問題を解決して全体の問題を解決します。ただし、動的プログラミングではサブ問題で得られた結果を直接組み合わせて全体の問題の結果が得られますが、ロシアン ドール サーチでは、検索中にサブ問題から得られた結果が境界としてのみ使用されます。

バケット削除アルゴリズムは、制約の最適化に適応できます。特定の変数は、その変数を含むすべてのソフト制約を新しいソフト制約に置き換えることで、問題から削除できます。この新しい制約のコストは、削除された変数のすべての値に最大値があると仮定して計算されます。正式には、 が削除される変数、 がそれを含むソフト制約、 が を除くそれらの変数である場合、新しいソフト制約は次のように定義されます。 ${\displaystyle x}$${\displaystyle C_{1},\ldots ,C_{n}}$${\displaystyle y_{1},\ldots ,y_{m}}$${\displaystyle x}$

${\displaystyle C(y_{1}=a_{1},\ldots ,y_{n}=a_{n})=\max _{a}\sum _{i}C_{i}(x=a,y_{1}=a_{1},\ldots ,y_{n}=a_{n}).}$

バケット削除は、変数の (任意の) 順序付けで機能します。すべての変数は制約のバケットに関連付けられています。変数のバケットには、その変数が順序付けで最も高い制約がすべて含まれます。バケット削除は、最後の変数から最初の変数へと進みます。各変数について、バケットのすべての制約が上記のように置き換えられ、変数が削除されます。結果として得られた制約は、適切なバケットに配置されます。

• 制約付き最小二乗法
• 分散制約最適化
• 制約充足問題(CSP)
• 制約プログラミング
• 整数計画法
• メートル法投影
• ペナルティ方式
• 優越化

• Bertsekas, Dimitri P. (1982)。制約付き最適化とラグランジュ乗数法。ニューヨーク：Academic Press。ISBN 0-12-093480-9。
• デヒター、リナ (2003)。制約処理。モーガン・カウフマン。ISBN 1-55860-890-7。