最適化問題
このときの関数 f {\displaystyle f} を目的関数 (英: objective function, cost function) と呼び、探すべき変数 x {\displaystyle x} が集合 A {\displaystyle A} に含まれるという条件のことを制約条件、制約関数(英: constraint,constraint function)と呼ぶ。制約条件の集合 A を実行可能領域(英: feasible region)あるいは許容領域と呼び、その元(要素)を実行可能解、可能解、許容解 (英: feasible solution, candidate solution) などと呼ぶ。目的関数を最小あるいは最大にするような実行可能解を(大域的)最小解、最大解と呼び、そのときの目的関数値を最小値、最大値と呼ぶ。また最小・最大を区別しないで最適解、最適値(英: optimal solution) とも呼ばれる。なお、ここで「領域」という用語は単に「集合」と同じ意味で使っている。また「解」は「点」と同義語である。したがって実行可能集合とか実行可能点などということもある。(この分野での伝統的・慣習的表現であり、数学的な意味の「領域=連結な開集合」,「解=問題の(最終的つまり最適)解」ということではないので注意。)
最適化問題(さいてきかもんだい、英: optimization problem)とは、特定の集合上で定義された実数値関数または整数値関数についてその値が最小(もしくは最大)となる状態を解析する問題である。こうした問題は総称して数理計画問題(すうりけいかくもんだい、英: mathematical programming problem, mathematical program)、数理計画とも呼ばれる。最適化問題は、自然科学、工学、社会科学などの多種多様な分野で発生する基本的な問題の一つであり、その歴史は18世紀の変分問題に遡る。1940年代に線型計画法が登場して以来、理論的な研究や数値解法の研究が非常に活発に行われ、その応用範囲はいろいろな分野に拡大されていった。実世界の現象の数理的な解析に関わる問題や抽象的な理論の多くをこの最適化問題という一般的なくくりに入れることができる。物理学やコンピュータビジョンにおける最適化問題は、考えている関数をモデル化された系のエネルギーを表すものと見なすことによって、エネルギー最小化問題と呼ばれることもある。
線型計画問題のうち、各変数のとる値が整数に制限されている場合。