多くの制約なし最適化アルゴリズムは、しばしばペナルティ法を用いて制約付きのケースに適応させることができる。 しかし、制約のない手法で行われる探索ステップは、制約のある問題では受け入れがたい場合があり、収束しないことにつながります。
等式制約の編集
代入法の編集
非常に単純な問題、例えば1つの等式制約に従う2変数の関数は、代入法を適用することが最も実用的である。 このアイデアは、制約の効果を組み込んだ複合関数を作成するために、目的関数に制約を代入することです。 例えば、目的関数がf ( x , y ) = x ⋅ y {displaystyle f(x,y)=xcdot y} を最大化するものであるとする。
subject to x + y = 10 {displaystyle x+y=10}.
のようになります。 この制約は、y = 10 – x {displaystyle y=10-x} を意味する。
, これを目的関数に代入すると p ( x ) = x ( 10 – x ) = 10 x – x 2 {displaystyle p(x)=x(10-x)=10x-x^{2}} となります。
. 一次の必要条件から、 ∂ p ∂ x = 10 – 2 x = 0 { {displaystyle {frac {partial p}{partial x}}=10-2x=0}} が得られる。
, これは x = 5 {displaystyle x=5} について解くことができる。
となり、y=10 – 5 = 5 {displaystyle y=10-5=5} となる。
のようになります。
Lagrange multiplierEdit
制約付き問題が等式制約しかない場合、Lagrange multipliersの方法を用いて、変数数が元の変数数に元の等式制約の数を加えた無制約問題に変換することが可能です。 あるいは、制約がすべて等式制約で、すべて線形であれば、一部の変数について他の変数の条件で解き、前者を目的関数から代入して、より少ない変数数で無制約の問題を残すことも可能である。
不等式制約Edit
不等式制約があると、問題は幾何学的最適化条件、フリッツ・ジョン条件、カルシュ・クーン・タッカー条件などで特徴付けられるが、これらの条件では単純な問題は解ける可能性がある。
Linear programmingEdit
目的関数とすべてのハード制約が線形で、いくつかのハード制約が不等式であれば、問題は線形計画問題である。 この問題は，通常問題サイズの多項式時間で動作するが保証されていないシンプレックス法や，多項式時間で動作することが保証されている内点法によって解くことができます．
Nonlinear programmingEdit
目的関数やいくつかの制約が非線形で，いくつかの制約が不等式ならば，この問題は非線形計画問題であると言えます．
二次プログラミングEdit
すべてのハード制約が線形で、一部が不等式であるが、目的関数が二次である場合、問題は二次プログラミング問題であると言えます。 非線形計画法の一種です。
KKT条件編集
不等式制約を認めると、非線形計画法のKKTアプローチはラグランジュ乗数を一般化したものとなる。 1412>
Branch and boundEdit
Constraint optimization はbranch and bound アルゴリズムで解くことができる。 これらは、実行中に見つかった最適解のコストを保存し、それを使って探索の一部を回避するバックトラック・アルゴリズムである。 より正確には、アルゴリズムは、保存された最良コストよりも良いコストの解を形成するために拡張できない部分解に遭遇するたびに、この解を拡張しようとするのではなく、バックトラックする。
コストが最小化されると仮定すると、これらのアルゴリズムの効率は、部分解を拡張して得られるコストをどう評価するかに依存する。 実際、アルゴリズムが部分解からバックトラックできる場合、探索の一部がスキップされる。 一方、この推定コストは、解を拡張することによって得られる有効コストより低くすることはできず、そうでなければ、アルゴリズムは、これまでに発見された最良の解よりも優れた解が存在する間にバックトラックを行う可能性があるからである。 その結果、アルゴリズムは部分解を拡張することによって得られるコストの上限を必要とし、この上限はできるだけ小さくする必要がある。
第一選択の境界関数編集
部分解のこの上界を評価する一つの方法は、各軟質制約を別々に考えることである。 各軟性制約について、未割り当ての変数への任意の割り当てに対して可能な最大値を仮定する。 軟制約はこれ以上の値を仮定できないので、これらの値の和が上界となる。 ソフト制約はx = a {displaystyle x=a} に対して最大であるかもしれません。
一方、別の制約は x = b {displaystyle x=b} に対して最大である。
.
Russian doll searchEdit
This method runs a branch-and-bound algorithm on n {displaystyle n} .
問題で、n { {displaystyle n} の場合。
は変数の数である。 このような問題は、変数 x 1 , … , x i の列を削除して得られる部分問題である{displaystyle x_{1},\ldots ,x_{i}} 。
を含む制約と一緒に元の問題から削除します。 変数x i + 1 , … , x nに関する問題の後{displaystyle x_{i+1},\ldots ,x_{n}}。
を解くと、その最適コストは他の問題を解く際の上限として使用できる。
特に、x i + 1 , … , x n {displaystyle x_{i+1},\ldots ,x_{n}} とする解のコストの推定は、その問題を解く際の上限として使用可能だ。
を未割り当て変数として、評価変数から派生するコストに加算される。 これは事実上、評価済み変数を無視して未割り当ての変数の問題を解くことに相当するが、後者の問題は既に解かれている。 より正確には、割り当てられた変数と割り当てられていない変数の両方を含むソフト制約のコストは、上記のように（または任意の他の方法を使用して）推定され、割り当てられていない変数のみを含むソフト制約のコストは、代わりに、この時点ですでに知られている対応する問題の最適解を使用して推定されます。
ロシアン・ドール・サーチ法とダイナミック・プログラミングの間には類似点がある。 動的計画法同様、ロシアン・ドール・サーチは問題全体を解くために部分問題を解く。
Bucket eliminationEdit
バケット消去法は制約条件最適化に適用できる． 与えられた変数は、それを含むすべてのソフト制約を新しいソフト制約に置き換えることにより、問題から実際に除去することができる。 この新しい制約のコストは、除去された変数のすべての値に対して最大値を仮定して計算される。 形式的には、x {displaystyle x}
を除去される変数とすると、C 1 , … , C n {displaystyle C_{1},\ldots ,C_{n}} が生成される。
はそれを含むソフト制約、y 1 , … , y m {displaystyle y_{1},\ldots ,y_{m}} はそれを含むソフト制約、y 2 , … , y m {displaystyle y_{2}, y_{3} はそれを含むソフト制約です。
はx {displaystyle x}
を除くそれらの変数で、新しい軟拘束は次のように定義されている。 C ( y 1 = a 1 , … , y n = a n ) = max a ∑ i C i ( x = a , y 1 = a 1 , … , y n = a n ) . {displaystyle C(y_{1}=a_{1},\ldots ,y_{n}=a_{n})=theme max _{a}sum _{i}C_{i}(x=a,y_{1}=a_{1},\ldots ,y_{n}=a_{n}).} ←クリックすると拡大します。
変数の順序は（任意の）バケット削除が動作します。 各変数は制約のバケットに関連付けられ、変数のバケットには、その変数が順序で最も高い制約を持つすべての制約が含まれます。 バケット消去は、最後の変数から最初の変数へと進む。 各変数について、バケットのすべての制約を上記のように置き換えて、その変数を削除する。 そして、得られた制約は適切なバケットに入れられる
。