最適化問題

一般的な最適化問題(P)は，不等式制約，等式制約，上下限制約を有しており，以下のように定義できる．

$$\arraycolsep=1mm (P) \begin{array}[t]{ll} \mbox{minimize} & f(\mb... ...$}) = 0,\; j=q+1, \dots, m \\ & l_i \le x_i \le u_i,\; i=1,\dots,n \end{array}$$ (1)

ここで， $\mbox{\boldmath$x$}=(x_1,\cdots,x_n)$ は $n$ 次元決定変数ベクトル， $f(\mbox{\boldmath$x$})$ は目的関数， $g_j(\mbox{\boldmath$x$}) \le 0$ は$q$個の不等式制約， $h_j(\mbox{\boldmath$x$})=0$ は$m-q$個の等式制約であり， $f,\; g_j,\; h_j$は線形あるいは非線形の実数値関数である． $l_i,\; u_i$はそれぞれ，$n$個の決定変数$x_i$の下限値，上限値である．

目的関数および制約条件がともに線形の場合が線形計画問題，その他の場合が非線形計画問題である． ここでは，不等式制約および等式制約のない問題の最適化について説明する．