中心パス

【ちゅうしんぱす (path of centers)】

なめらかな凸関数$f_i \; (i=1,2,\ldots,m)$について, 許容解集合 $P:=\{x| \ f_i(x) \leq 0 \; (i=1,2,\ldots,m)\}$ の内部$P^0$が非空であるとする. このとき$P^0$から実数への関数 $-\sum_{i=1}^m \ln (-f_i(x))$ は唯一の最小解(解析的中心)をもつ. 不等式$f_k(x) \leq 0$の右辺を パラメータ$\lambda$で変化させると(新たな許容解集合の内部が非空である限り) 各$\lambda$に対して解析的中心が存在し, $1$次元のなめらかなパスを形成する. これを中心パスと呼ぶ. 内点法のアルゴリズムを与えるために用いられる.