制約 (数学)のソースを表示

{{no footnotes|date=September 2016}}

'''制約'''（せいやく、'''制約条件'''、せいやくじょうけん、{{Lang-en-short|Constraint}}）とは、[[数学]]の[[最適化問題]]において解が満たさなければならない条件を指す。制約にはいくつか種類が存在し、主に[[等式]]、[[不等式]]、[[整数計画問題|整数制約]]が多用されている。与えられたすべての制約を満たす許容解の集合を[[実行可能集合]]という<ref>{{cite book |first=Akira |last=Takayama |title=Mathematical Economics |location=New York |publisher=Cambridge University Press |edition=2nd |year=1985 |isbn=0-521-31498-4 |page=[https://archive.org/details/mathematicalecon00taka/page/61 61] |url=https://archive.org/details/mathematicalecon00taka |url-access=registration }}</ref>。

== 例 ==
以下の最適化問題を例に挙げる:
:<math>\min f(\mathbf x) = x_1^2+x_2^4</math>

subject to

:<math>x_1 \ge 1</math>

and

:<math>x_2 = 1,</math>

ここで<math>\mathbf x</math> はベクトル (''x''<sub>1</sub>, ''x''<sub>2</sub>) を表す。

この問題では、最初の行に記されている関数が最小となる解を求める（これは[[目的関数]]、または損失関数、費用関数と呼ばれる。）。2つ目および3つ目の行は制約を表し、一つ目の制約を不等式制約と呼び、二つ目の制約は等式制約と呼ばれる。これら二つの制約は、この問題において解が絶対に制約を満たさなければならないという意味で{{仮リンク|ハード制約|en|hard constraint}}に分類される。

この問題に制約がない場合は、目的関数 <math>f(\mathbf x)</math> が最小となる解は <math>(0,0)</math> である。しかしこの解は制約を満たしていない。2つの制約を考慮した{{仮リンク|制約付き最適化|en|constraint optimization}}問題としての解は、<math>\mathbf x = (1,1)</math> のとき、2つの制約を満たしつつ目的関数 <math>f(\mathbf x)</math> を最も小さくする解である。

== 用語 ==
*最適点において不等式制約について等号が成り立つ場合、その制約は束縛制約である。これは、目的関数の値を改善される方向に移動しようとしても、束縛制約によって最適点以上に改善する点が存在しないことを意味する。
*一方、最適点において不等式制約が厳密に不等式として成り立つ場合（等号が成り立たない場合）、その制約は束縛制約でない。これは、束縛制約でない制約の方向に変動させることが可能であることを意味するが、最適性の観点からはその変更が望ましくない。凸最適化の場合では、ある制約が束縛制約でなければ、その制約が存在しなくても最適解の決定に起因しない。
*その点がすべての制約を満たすものでない場合、[[実行可能領域|実行不能]]である。

== ハード制約・ソフト制約 ==
最適化問題において制約の違反が許されない場合、これらの制約は'''ハード制約'''と呼ばれる。しかし、問題によってはすべての制約を必ずしも満たす必要はなく、可能な限り満たすことが望ましいが必須ではない制約を設けることがある。このような制約を'''{{仮リンク|ソフト制約|en|Constraint optimization#General form}}'''と呼び、それらを扱う問題は[[:en:Constraint satisfaction problem#Flexible CSPs|フレキシブル制約充足問題]]（flexible constraint satisfaction problem）と呼ばれる。ソフト制約を用いる問題として、[[:en:preference-based planning|preference-based planning]] の分野が挙げられる。{{仮リンク|最大制約充足問題|en|最大制約充足問題}}では、いくつかの制約の違反を許容し、評価尺度として満たされた制約の数を評価する。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
* {{cite book |first=Gordon S. G. |last=Beveridge |first2=Robert S. |last2=Schechter |chapter=Essential Features in Optimization |title=Optimization: Theory and Practice |location=New York |publisher=McGraw-Hill |year=1970 |pages=5–8 |isbn=0-07-005128-3 |chapter-url=https://books.google.com/books?id=TfhVXlWtOPQC&pg=PA5 }}

== 関連項目 ==
{{Div col|colwidth=25em}}
* {{仮リンク|代数制約|en|Constraint algebra}}
* [[カルーシュ・クーン・タッカー条件]]
* [[ラグランジュの未定乗数法]]
* [[等位集合]]
* [[線形計画問題]]
* [[非線形計画問題]]
* [[制限 (数学)|制限]]
* {{仮リンク|背景理論付き充足可能性問題|en|Satisfiability modulo theories}}
{{Div col end}}

== 外部リンク ==
*[http://www.neos-guide.org/non-lp-faq Nonlinear programming FAQ] {{Webarchive|url=https://web.archive.org/web/20191030134942/https://neos-guide.org/non-lp-faq |date=2019-10-30 }}
*[http://glossary.computing.society.informs.org/ Mathematical Programming Glossary] {{Webarchive|url=https://web.archive.org/web/20100328165516/http://glossary.computing.society.informs.org/ |date=2010-03-28 }}

{{DEFAULTSORT:せいやく}}
[[Category:最適化]]
[[Category:数学に関する記事]]