非線形計画法

同義語:非線形計画問題非線形計画nonlinear programming非線形最適化nonlinear optimization

概要

非線形計画法(nonlinear programming)とは、目的関数や制約に 1 次式でないものが入る最適化問題を解く方法の総称である。制約のある問題を、制約のない最小化の列(罰金法、拡張 Lagrange 法)、2 次計画問題の列(逐次 2 次計画法)、実行可能集合の内部での最小化の列(障壁法・内点法)に置き換えて解く。反復は KKT 点を探すもので、問題が凸でなければ得られるのは一般に局所解である。工学の設計、機械学習、経済の数理などの連続最適化に使う。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 最適化, Lagrangeの未定乗数法, 凸最適化, Newton法

半径 $1$ の円板 $x^2+y^2\le1$ の中で、関数 $(1-x)^2+100(y-x^2)^2$ を最小にしたいとする。円の方程式も目的関数も 1 次式でないので、線形計画法 は使えない。Lagrange 関数から出る連立方程式は 3 変数の高次方程式で、手で解くのは難しい。解は $(x,y)\approx(0.78642,0.61770)$ で、値は約 $0.045675$ である(ex-nlp-rosenbrock)。
非線形計画法 は、このように目的関数や制約に 1 次式でないものが入る最適化問題を解く方法の総称である。解き方の基本の考えは、制約のある難しい問題を、解ける問題の列 に置き換えることにある。

考え方置き換える先名前
制約を満たさないことに罰を与える制約のない最小化の列罰金法、拡張 Lagrange 法
関数を 2 次式と 1 次式で近似する2 次計画問題の列逐次 2 次計画法
境界に近づくことに罰を与える実行可能集合の内部での最小化の列障壁法(内点法)

この記事では、問題の分類と解の判定条件を表にし、これらの方法が正しい答えに近づく理由を証明する。問題の性質(凸かどうか、微分できるか、制約が等式か不等式か)から方法を選ぶ手順と、数値まで計算した例題も示す。

定義と使える条件

非線形計画問題

$f,g_i,h_j\colon\mathbb{R}^n\to\mathbb{R}$($i=1,\dots,m$、$j=1,\dots,p$)について、問題
$$ \text{(NLP)}\qquad\text{最小化 } f(x)\quad\text{条件 } g_i(x)\le0\ (i=1,\dots,m),\quad h_j(x)=0\ (j=1,\dots,p) $$
を考える。$f,g_i,h_j$ のうち少なくとも 1 つが 1 次式(定数項があってもよい)でないとき、(NLP) を 非線形計画問題 といい、これを解く方法を 非線形計画法 という。条件をすべて満たす点を 実行可能解 といい、その全体を $X$ と書く。すべての $x\in X$ で $f(x^*)\le f(x)$ となる $x^*\in X$ を 大域解、ある $r>0$ について $\lvert x-x^*\rvert< r$ を満たす $x\in X$ でこの不等式が成り立つものを 局所解 という。$g_i(x)=0$ となる $i$ の全体を $\mathcal A(x)$ と書き、$x$ で 効いている 制約という。

最大化は $f$ の符号を変えて、$g(x)\ge0$ は $-g(x)\le0$ と書いて、この形に直す。乗数の符号はこの形についての約束である。

KKT 点

$f,g_i,h_j$ を $C^1$ 級とし、Lagrange 関数 を $L(x,\lambda,\mu):=f(x)+\sum_{i=1}^m\lambda_ig_i(x)+\sum_{j=1}^p\mu_jh_j(x)$ とする。実行可能解 $x^*$ と $\lambda\in\mathbb{R}^m$、$\mu\in\mathbb{R}^p$ の組が
$$ \nabla_xL(x^*,\lambda,\mu)=0,\qquad\lambda_i\ge0,\qquad\lambda_ig_i(x^*)=0\quad(i=1,\dots,m) $$
を満たすとき、$(x^*,\lambda,\mu)$ を KKT 点 という。ベクトルの組 $\nabla g_i(x)$($i\in\mathcal A(x)$)、$\nabla h_j(x)$($j=1,\dots,p$)が線形独立であることを、$x$ で LICQ が成り立つという。

非線形計画法の多くの手順は、KKT 点を探す手順である。KKT 点は解とは限らず、解は KKT 点とは限らない(ex-nlp-kkt、ex-nlp-counterexamples)。その関係の一般論は KKT条件 の主題で、この記事では判定に要る形を表にまとめる。
この記事の方法を使う条件は次のとおりである。

  • (i) $f,g_i,h_j$ は $C^2$ 級とする(thm-nlp-sqp では $C^3$ 級)。微分できない関数には、この記事の方法はそのままでは使えない。
  • (ii) 反復法の結果は一般に局所解か KKT 点である。問題が凸でなければ、大域解であることは保証されない。
  • (iii) 変数は連続の値をとる。整数の条件がある問題は 整数計画法 で扱う。
  • (iv) 変数と関数の大きさがそろうように、尺度を調整しておく。

公式の表

判定の条件を次の表にまとめる。$W:=\nabla_x^2L(x^*,\lambda,\mu)$ とする。

条件仮定言えること根拠
$\nabla f(x^*)=0$$x^*$ は $X$ の内部の局所解、$f$ は微分可能必要条件最適化
KKT 点である$f,g_i$ は凸、$h_j$ は 1 次式十分条件($x^*$ は大域解)凸最適化
KKT 点である$f,g_i$ は凸、$h_j$ なし、Slater 条件大域解での必要条件凸最適化
KKT 点である$x^*$ で LICQ局所解での必要条件KKT条件
$d\cdot Wd>0$(臨界錐の $d\ne0$)KKT 点で、$C^2$ 級十分条件($x^*$ は狭義の局所解)thm-nlp-sosc

1 次式の等式 $h_j=0$ は 2 つの不等式 $h_j\le0$、$-h_j\le0$ と同じなので、凸の場合の十分性は 凸最適化 の定理「Karush–Kuhn–Tucker の定理」に含まれる。
方法は次のとおりである。表の部分問題の記号は、次の節の fml-nlp-penalty・fml-nlp-auglag・fml-nlp-qp・fml-nlp-barrier で定める。

方法各段で解く問題要る情報局所的な速さ向く場面根拠
罰金法制約なしで $P_\rho$ を最小化$\nabla f,\nabla g_i,\nabla h_j$制約の違反は $1/\rho$ の大きさ既存の制約なしの解法を流用したいとき、粗い初期値を作るときthm-nlp-penalty
拡張 Lagrange 法制約なしで $A_\rho$ を最小化し、乗数を更新同上1 次収束(数値例)大規模で、2 階導関数が使いにくいときprop-nlp-exact
逐次 2 次計画法2 次計画問題($Q$)$\nabla^2L$ またはその近似2 次収束中規模で関数の評価が高価なときthm-nlp-sqp
障壁法・内点法内部で $B_t$ を最小化$\nabla^2f,\nabla^2g_i$精度は $m/t$ 以下(凸のとき)凸の問題、不等式が多いときthm-nlp-barrier

制約のない最小化の部分には、勾配降下法 や Newton 系の方法を使う。準Newton法 の BFGS 法は 2 階導関数を使わずに Hesse 行列を近似する。

主定理と証明

2 次の十分条件

1 次の条件だけでは、KKT 点が解かどうかは分からない。KKT 点で 2 階の導関数を調べる方向の集合を 臨界錐 といい、$\lambda$ を固定して
$$ \mathcal C:=\Bigl\{d\in\mathbb{R}^n\ \Big|\ \nabla h_j(x^*)\cdot d=0\ (\forall j),\ \nabla g_i(x^*)\cdot d=0\ (i\in\mathcal A(x^*),\lambda_i>0),\ \nabla g_i(x^*)\cdot d\le0\ (i\in\mathcal A(x^*),\lambda_i=0)\Bigr\} $$
と定める。

不等式を含む 2 次の十分条件

$f,g_i,h_j$ を $C^2$ 級とし、$(x^*,\lambda,\mu)$ を KKT 点とする。すべての $d\in\mathcal C\setminus\{0\}$ で $d\cdot\nabla_x^2L(x^*,\lambda,\mu)d>0$ なら、$x^*$ は狭義の局所解である。つまり、ある $r>0$ があって、$0<\lvert x-x^*\rvert< r$ を満たす $x\in X$ で $f(x)>f(x^*)$ である。

結論が成り立たないとすると、$x_k\in X$、$x_k\ne x^*$、$x_k\to x^*$、$f(x_k)\le f(x^*)$ となる列がある。$t_k:=\lvert x_k-x^*\rvert$、$d_k:=(x_k-x^*)/t_k$ とおき、部分列をとって $d_k\to d$、$\lvert d\rvert=1$ とする。
$d\in\mathcal C$ であること。 $h_j(x_k)=h_j(x^*)=0$ を $t_k$ で割って極限をとると $\nabla h_j(x^*)\cdot d=0$ である。$i\in\mathcal A(x^*)$ なら $g_i(x_k)\le0=g_i(x^*)$ から $\nabla g_i(x^*)\cdot d\le0$、同様に $f(x_k)\le f(x^*)$ から $\nabla f(x^*)\cdot d\le0$ である。$\nabla_xL=0$ に $d$ をかけ、相補性により $\mathcal A(x^*)$ の外では $\lambda_i=0$ であることを使うと
$$ 0\ge\nabla f(x^*)\cdot d=-\sum_{i\in\mathcal A(x^*)}\lambda_i\nabla g_i(x^*)\cdot d\ge0 $$
である。右の和の各項は $0$ 以上なので、$\lambda_i>0$ なら $\nabla g_i(x^*)\cdot d=0$ である。よって $d\in\mathcal C$ である。
2 階の評価。 $\varphi(x):=L(x,\lambda,\mu)$ とおく。$x_k\in X$ と $\lambda\ge0$ から $\varphi(x_k)\le f(x_k)\le f(x^*)=\varphi(x^*)$ である。$\nabla\varphi(x^*)=0$ なので Taylorの定理 により
$$ 0\ge\varphi(x_k)-\varphi(x^*)=\frac{t_k^2}2d_k\cdot\nabla^2\varphi(x^*)d_k+o(t_k^2) $$
である。$t_k^2$ で割って極限をとると $d\cdot\nabla^2\varphi(x^*)d\le0$ となり、仮定に反する。$\square$

等式の制約だけなら $\mathcal C$ は $\nabla h_j(x^*)$ のすべてに直交する方向の全体で、この定理は Lagrangeの未定乗数法 の定理「2 次の十分条件」の 1 と同じ形である。上の証明は LICQ を使っていない。

罰金法

$g_i^+(x):=\max(g_i(x),0)$、$v(x):=\sum_{j}h_j(x)^2+\sum_{i}g_i^+(x)^2$ とおく。$v(x)\ge0$ で、$v(x)=0$ は $x\in X$ と同値である。

罰金関数

$\rho>0$ に対し $P_\rho(x):=f(x)+\dfrac\rho2v(x)$ とおく。$(s^+)^2$ は $s$ について $C^1$ 級で導関数は $2s^+$ なので、$f,g_i,h_j$ が $C^1$ 級なら $P_\rho$ も $C^1$ 級で
$$ \nabla P_\rho(x)=\nabla f(x)+\rho\sum_ig_i^+(x)\nabla g_i(x)+\rho\sum_jh_j(x)\nabla h_j(x) $$
である。

次の定理は、大域的な最小点 を厳密に求められるなら、罰金法の極限が大域解であることを述べる。

罰金法の収束

$f,g_i,h_j$ を連続、$X\ne\emptyset$ とし、$0<\rho_1<\rho_2<\cdots\to\infty$ とする。各 $k$ で $x_k$ が $P_{\rho_k}$ の $\mathbb{R}^n$ 全体での最小点であるとする。このとき次が成り立つ。

  1. $v(x_k)$ は単調非増加、$f(x_k)$ は単調非減少で、すべての $x\in X$ で $f(x_k)\le P_{\rho_k}(x_k)\le f(x)$ である。
  2. 列 $(x_k)$ の集積点は、どれも (NLP) の大域解である。

$x\in X$ なら $v(x)=0$ なので、$x_k$ が最小点であることから
$$ f(x_k)\le P_{\rho_k}(x_k)\le P_{\rho_k}(x)=f(x) $$
である(以下、これを不等式 (a) とよぶ)。次に、最小性を 2 回使う。
$$ f(x_k)+\frac{\rho_k}2v(x_k)\le f(x_{k+1})+\frac{\rho_k}2v(x_{k+1}),\qquad f(x_{k+1})+\frac{\rho_{k+1}}2v(x_{k+1})\le f(x_k)+\frac{\rho_{k+1}}2v(x_k) $$
を足すと $(\rho_{k+1}-\rho_k)\bigl(v(x_k)-v(x_{k+1})\bigr)\ge0$ となるので、$v(x_{k+1})\le v(x_k)$ である。これを左の不等式に入れると $f(x_k)\le f(x_{k+1})$ である。以上で 1 が示せた。
$\bar x$ を集積点とし、$x_{k_l}\to\bar x$ とする。$x\in X$ を 1 つ固定すると、不等式 (a) より
$$ \frac{\rho_{k_l}}2v(x_{k_l})\le f(x)-f(x_{k_l}) $$
で、右辺は $f(x)-f(\bar x)$ に収束するので有界である。$\rho_{k_l}\to\infty$ なので $v(x_{k_l})\to0$ で、$v$ の連続性から $v(\bar x)=0$、つまり $\bar x\in X$ である。不等式 (a) で極限をとると、すべての $x\in X$ で $f(\bar x)\le f(x)$ である。$\square$

実際の計算で得られるのは最小点ではなく停留点である。その場合でも、極限が実行可能で LICQ が成り立てば KKT 点になる。さらに、制約の違反の大きさが乗数の値を教える。

罰金法の乗数の推定

$f,g_i,h_j$ を $C^1$ 級、$\rho_k\to\infty$ とし、$\nabla P_{\rho_k}(x_k)=0$、$x_k\to\bar x$ とする。$\bar x\in X$ で、$\bar x$ で LICQ が成り立つとする。
$$ \lambda_i^k:=\rho_kg_i^+(x_k),\qquad\mu_j^k:=\rho_kh_j(x_k) $$
とおくと、$\lambda^k\to\lambda$、$\mu^k\to\mu$ となる $\lambda,\mu$ があり、$(\bar x,\lambda,\mu)$ は KKT 点である。とくに $h_j(x_k)=\mu_j/\rho_k+o(1/\rho_k)$ で、$\mu_j\ne0$ なら制約の違反は $1/\rho_k$ の大きさで減る。

$i\notin\mathcal A(\bar x)$ なら $g_i(\bar x)<0$ なので、十分大きい $k$ で $g_i(x_k)<0$、$\lambda_i^k=0$ である。fml-nlp-penalty の式は、$\lambda^k,\mu^k$ を使うと
$$ \nabla f(x_k)+\sum_{i\in\mathcal A(\bar x)}\lambda_i^k\nabla g_i(x_k)+\sum_j\mu_j^k\nabla h_j(x_k)=0 $$
と書ける。$\nabla g_i(x)$($i\in\mathcal A(\bar x)$)と $\nabla h_j(x)$ を列に並べた行列を $J(x)$ とし、$\lambda^k,\mu^k$ の対応する成分を並べたベクトルを $w_k$ とすると、$J(x_k)w_k=-\nabla f(x_k)$ である。LICQ より $J(\bar x)$ の列は線形独立なので $J(\bar x)^{\mathsf T}J(\bar x)$ は正則で、連続性から十分大きい $k$ で $J(x_k)^{\mathsf T}J(x_k)$ も正則である。よって
$$ w_k=-\bigl(J(x_k)^{\mathsf T}J(x_k)\bigr)^{-1}J(x_k)^{\mathsf T}\nabla f(x_k)\longrightarrow w:=-\bigl(J(\bar x)^{\mathsf T}J(\bar x)\bigr)^{-1}J(\bar x)^{\mathsf T}\nabla f(\bar x) $$
である。極限をとると $\nabla f(\bar x)+J(\bar x)w=0$ で、これは $\nabla_xL(\bar x,\lambda,\mu)=0$ である。$\lambda_i^k\ge0$ より $\lambda_i\ge0$ で、$i\notin\mathcal A(\bar x)$ なら $\lambda_i=0$ なので相補性も成り立つ。$\square$

等式の制約では、$\rho$ を大きくすると、$\nabla^2P_\rho$ は $\rho\sum_j\nabla h_j\nabla h_j^{\mathsf T}$ の項のために制約の法線の方向にだけ急になる。谷の形が細くなり、ex-nlp-penalty では Hesse 行列の条件数が $\rho$ に比例して大きくなる。これが罰金法の実用上の弱点である。

拡張 Lagrange 法

$\rho$ を無限大に送らずに済ませるのが 拡張 Lagrange 法(乗数法)である。以下は等式の制約だけを扱う。

拡張 Lagrange 関数

$A_\rho(x;\mu):=f(x)+\sum_j\mu_jh_j(x)+\dfrac\rho2\sum_jh_j(x)^2$ とおく。
$$ \nabla_xA_\rho(x;\mu)=\nabla f(x)+\sum_j\bigl(\mu_j+\rho h_j(x)\bigr)\nabla h_j(x) $$
なので、$A_\rho$ の停留点 $x$ で $\mu^+:=\mu+\rho h(x)$ とおくと $\nabla_xL(x,\mu^+)=0$ である。これが乗数の更新の式である。

行列の項を足して正定値にする

$H$ を $n$ 次の実対称行列、$J$ を $p\times n$ の実行列とする。$Jd=0$、$d\ne0$ となるすべての $d$ で $d\cdot Hd>0$ なら、ある $\bar\rho$ があって、$\rho\ge\bar\rho$ のとき $H+\rho J^{\mathsf T}J$ は正定値である。

結論が成り立たないなら、各 $k$ について $\rho_k\ge k$ と $\lvert d_k\rvert=1$ があって $d_k\cdot Hd_k+\rho_k\lvert Jd_k\rvert^2\le0$ である。部分列をとって $d_k\to d$、$\lvert d\rvert=1$ とする。$\lvert Jd_k\rvert^2\le-d_k\cdot Hd_k/\rho_k\to0$ なので $Jd=0$ で、$d_k\cdot Hd_k\le0$ から $d\cdot Hd\le0$ である。これは仮定に反する。$\square$

正しい乗数での正確さ

$f,h_j$ を $C^2$ 級とし、$x^*$ は実行可能、$\nabla_xL(x^*,\mu^*)=0$ で、$J:=Dh(x^*)$ の核の $0$ でないすべての $d$ で $d\cdot\nabla_x^2L(x^*,\mu^*)d>0$ とする。このとき、ある $\bar\rho$ があって、$\rho\ge\bar\rho$ なら $x^*$ は $A_\rho(\cdot\,;\mu^*)$ の狭義の局所最小点である。

fml-nlp-auglag の勾配の式で $h(x^*)=0$ なので、$\nabla_xA_\rho(x^*;\mu^*)=\nabla_xL(x^*,\mu^*)=0$ である。もう 1 回微分して $h(x^*)=0$ を使うと、$\nabla_x^2A_\rho(x^*;\mu^*)=\nabla_x^2L(x^*,\mu^*)+\rho J^{\mathsf T}J$ である。lem-nlp-finsler により、これは $\rho\ge\bar\rho$ で正定値である。勾配が $0$ で Hesse 行列が正定値の点は狭義の極小点である(Taylorの定理)。$\square$

罰金法では、LICQ のもとで $\mu^*\ne0$ なら、$\rho$ をいくら大きくしても $x^*$ は $P_\rho$ の停留点にならない($\nabla P_\rho(x^*)=\nabla f(x^*)=-\sum_j\mu_j^*\nabla h_j(x^*)\ne0$)。prop-nlp-exact は、乗数が正しければ有限の $\rho$ で $x^*$ が厳密に得られることを述べる。そこで乗数のほうを反復で直していく。

逐次 2 次計画法

逐次 2 次計画法(SQP)は、$x_k$ で目的関数を 2 次式、制約を 1 次式で近似した問題を解く方法である。等式の制約について述べる。$W_k:=\nabla_x^2L(x_k,\mu_k)$、$J_k:=Dh(x_k)$ とする。

2 次計画の部分問題

$$ \text{(Q)}\qquad\text{最小化 } \nabla f(x_k)\cdot d+\frac12d\cdot W_kd\quad\text{条件 } h(x_k)+J_kd=0 $$

逐次 2 次計画法は Newton の反復である

$f,h_j$ を $C^3$ 級とし、$F(x,\mu):=\bigl(\nabla_xL(x,\mu),h(x)\bigr)$ とおく。

  1. (Q) の停留点の条件($d$ と乗数 $\mu^+$ についての連立 1 次方程式)は、$F$ に対する Newton法 の 1 段 $(x_k+d,\mu_k+\delta)$、$\delta:=\mu^+-\mu_k$ の方程式
    $$ \begin{pmatrix}W_k&J_k^{\mathsf T}\\J_k&0\end{pmatrix}\begin{pmatrix}d\\\delta\end{pmatrix}=-\begin{pmatrix}\nabla_xL(x_k,\mu_k)\\h(x_k)\end{pmatrix} $$
    と同じである。
  2. $(x^*,\mu^*)$ が $F=0$ を満たし、$x^*$ で LICQ が成り立ち、$J_*:=Dh(x^*)$ の核の $0$ でないすべての $d$ で $d\cdot\nabla_x^2L(x^*,\mu^*)d>0$ なら、1 の係数行列は $(x^*,\mu^*)$ で正則である。
  3. 2 の仮定のもとで、$(x_0,\mu_0)$ が $(x^*,\mu^*)$ に十分近ければ、反復は定義されて $(x^*,\mu^*)$ に 2 次収束する。

1。 (Q) の Lagrange 関数を $d$ で微分すると、停留点の条件は $\nabla f(x_k)+W_kd+J_k^{\mathsf T}\mu^+=0$、$h(x_k)+J_kd=0$ である。$\nabla_xL(x_k,\mu_k)=\nabla f(x_k)+J_k^{\mathsf T}\mu_k$ なので、$\mu^+=\mu_k+\delta$ を入れると方程式の 1 行目になる。$F$ の Jacobi 行列は、$\nabla_xL$ を $x$ で微分して $W_k$、$\mu$ で微分して $J_k^{\mathsf T}$、$h$ を $x$ で微分して $J_k$ なので、係数行列そのものである。
2。 係数行列を $(x^*,\mu^*)$ で考え、$W_*u+J_*^{\mathsf T}w=0$、$J_*u=0$ とする。1 つ目の式に $u$ をかけると $u\cdot W_*u=-(J_*u)\cdot w=0$ である。$J_*u=0$ なので、仮定から $u=0$ である。すると $J_*^{\mathsf T}w=0$ で、LICQ は $J_*^{\mathsf T}$ の列が線形独立であることなので $w=0$ である。よって係数行列は正則である。
3。 $f,h_j$ が $C^3$ 級なので $F$ は $C^2$ 級で、2 により $F$ の Jacobi 行列は零点で正則である。Newton法 の定理「多変数のNewton法の局所2次収束」から結論が従う。$\square$

不等式の制約があるときは、部分問題の条件に $g_i(x_k)+\nabla g_i(x_k)\cdot d\le0$ を加える。部分問題は不等式つきの 2 次計画問題になり、効いている制約の集合を部分問題が決める。遠くの初期値からは、刻み幅を $\alpha_k\le1$ に縮めて $x_{k+1}=x_k+\alpha_kd$ とし、罰金の形の関数(メリット関数)が減るようにする。これらの大域的な扱いの証明は、この記事では扱わない。

障壁法

制約が不等式 $g_i(x)\le0$ だけで、$g_i(x)<0$(すべての $i$)となる点があるとする。

対数障壁

$t>0$ に対し、$\{x\mid g_i(x)<0\ (\forall i)\}$ の上で $B_t(x):=tf(x)-\sum_{i=1}^m\log\bigl(-g_i(x)\bigr)$ とおく。$f$ が連続なら、$B_t$ は実行可能集合の境界の点に近づくと $+\infty$ に発散するので、最小点は内部に留まる。

障壁法の精度

$f,g_i$ を微分可能な凸関数、$p^*:=\inf_Xf$ とする。$x(t)$ が $B_t$ の最小点なら $\lambda_i(t):=-\dfrac1{t\,g_i(x(t))}>0$ で、
$$ f(x(t))-p^*\le\frac mt $$
である。また、$(x(t),\lambda(t))$ は $\nabla_xL=0$ と $\lambda_i(t)g_i(x(t))=-1/t$ を満たす。

$x:=x(t)$ とする。$\nabla B_t(x)=0$ を $t$ で割ると
$$ \nabla f(x)+\sum_i\frac{-1}{t\,g_i(x)}\nabla g_i(x)=0 $$
で、これは $\nabla_xL(x,\lambda(t))=0$ である。$\lambda(t)>0$ なので $L(\cdot,\lambda(t))$ は凸で、勾配が $0$ の点 $x$ で最小値をとる(凸最適化 の定理「最適性条件」)。よって、任意の $z\in X$ について
$$ f(z)\ge f(z)+\sum_i\lambda_i(t)g_i(z)\ge L(x,\lambda(t))=f(x)+\sum_i\lambda_i(t)g_i(x)=f(x)-\frac mt $$
である。$z$ について下限をとると $p^*\ge f(x)-m/t$ である。$\square$

$\lambda_ig_i=-1/t$ は相補性の条件 $\lambda_ig_i=0$ を $-1/t$ にゆるめた式で、$t\to\infty$ で KKT の条件に近づく。$t$ を動かしたときの $x(t)$ の軌跡を 中心パス という(BV04 §11.2.2、pp. 564–566)。主問題の変数と双対問題の変数を同時に Newton の反復で動かす方法が 主双対内点法 である。
図: 左は罰金関数の等高線で、制約の円に沿う細い谷ができる。右は 3 つの方法の解との距離の減り方(例題の問題) 図: 左は罰金関数の等高線で、制約の円に沿う細い谷ができる。右は 3 つの方法の解との距離の減り方(例題の問題)

計算の手順

全体の流れは次のとおりである。

  1. 標準形に書く:(NLP) の形に直し、変数の尺度をそろえる。導関数を用意する。
  2. 構造を調べる:$f,g_i$ が凸で $h_j$ が 1 次式かを調べる。凸なら KKT 点は大域解である(凸最適化)。
  3. 方法を選ぶ:下の表から選ぶ。
  4. 初期値を決める:凸でない問題では、複数の初期値から解く。
  5. 反復する:各方法の手順を、止める判定を満たすまで回す。反復の上限も決めておく。
  6. 止める判定:許容誤差 $\varepsilon$ を決め、$\lvert\nabla_xL\rvert\le\varepsilon$、$\lvert h\rvert\le\varepsilon$、$\lvert g^+\rvert\le\varepsilon$、$\lambda\ge0$、$\lvert\lambda_ig_i\rvert\le\varepsilon$ をすべて確かめる(KKT 残差 の判定)。$x$ の変化が小さいことだけで止めない。
  7. 結果を確かめる:得た点で LICQ と thm-nlp-sosc の条件を調べる。凸でない問題では、局所解であることまでしか言えない。
    問題の状況選ぶ方法
    制約がない勾配降下法、準Newton法、Newton の方法
    目的関数が 2 次式で制約が 1 次式2 次計画法(等式の制約だけなら thm-nlp-sqp の 1 の連立 1 次方程式を 1 回解けばよい)
    凸で、不等式の制約が多い障壁法・内点法
    凸でなく、導関数が 2 階まで使える中規模の問題逐次 2 次計画法
    変数が非常に多く、1 階の導関数しか使えない拡張 Lagrange 法
    既存の制約なしの解法しか使えない罰金法で近似し、拡張 Lagrange 法で仕上げる
    各方法の手順は次のとおりである。

罰金法。

  1. $\rho_0>0$(たとえば $1$)と倍率 $c>1$(たとえば $10$)を決める。
  2. 前の解を初期値にして $P_{\rho_k}$ を最小化し、$x_k$ を得る。
  3. 止める判定を満たせば終わる。そうでなければ $\rho_{k+1}\leftarrow c\rho_k$ として段 2 へ戻る。乗数の近似は thm-nlp-multiplier の $\lambda^k,\mu^k$ である。

拡張 Lagrange 法(等式の制約。VMLS18 Algorithm 19.2 は最小二乗の形の同じ手順である)。

  1. $\mu_0$(たとえば $0$)と $\rho_0$ を決める。
  2. 前の解を初期値にして $A_{\rho_k}(\cdot\,;\mu_k)$ を最小化し、$x_{k+1}$ を得る。
  3. $\mu_{k+1}\leftarrow\mu_k+\rho_kh(x_{k+1})$ とする。
  4. $\lvert h(x_{k+1})\rvert$ が前の段の $\frac14$ 以下に減っていなければ $\rho_{k+1}\leftarrow2\rho_k$ とし、減っていれば $\rho$ を変えない。

逐次 2 次計画法(等式の制約)。

  1. $(x_0,\mu_0)$ を決める。
  2. thm-nlp-sqp の 1 の連立 1 次方程式を解いて $d,\delta$ を得る。係数行列が特異に近ければ止めて、制約の線形独立性を調べる。
  3. $x_{k+1}\leftarrow x_k+\alpha d$、$\mu_{k+1}\leftarrow\mu_k+\alpha\delta$ とする。解の近くでは $\alpha=1$ である。遠くでは、罰金の形の関数が減るように $\alpha\in(0,1]$ を縮める。

障壁法(BV04 §11.3.1、p. 569)。

  1. 実行可能集合の内部の点 $x$、$t_0>0$、倍率 $c>1$ を決める。内部の点がなければ、先に $\max_ig_i$ を減らす問題を解いて探す。
  2. $x$ から始めて $B_{t_k}$ を Newton の反復で最小化し、$x$ を更新する。刻みは $g_i(x)<0$ を保つように縮める。
  3. $m/t_k\le\varepsilon$ なら止める(thm-nlp-barrier)。そうでなければ $t_{k+1}\leftarrow ct_k$ として段 2 へ戻る。

例題

KKT 点を全部挙げて分類する

問い:最小化 $f(x,y)=x^2-y^2$、条件 $g(x,y)=x^2+y^2-1\le0$。
使う公式:def-nlp-kkt、thm-nlp-sosc。
答え:KKT 点は $(0,0)$($\lambda=0$)と $(0,\pm1)$($\lambda=1$)である。$(0,\pm1)$ が大域解で最小値は $-1$、$(0,0)$ は局所解でない。$(\pm1,0)$ は $\lambda=-1$ となり KKT 点でない。

途中の計算を開く

$\nabla_xL=0$ は $2x(1+\lambda)=0$、$2y(\lambda-1)=0$ である。$\lambda=0$ なら $x=y=0$ である。$\lambda>0$ なら $g=0$ で、$1+\lambda\ne0$ から $x=0$、$y=\pm1$、$\lambda=1$ である。$(0,\pm1)$ では $W=\mathrm{diag}(2+2\lambda,-2+2\lambda)=\mathrm{diag}(4,0)$、$\lambda>0$ なので臨界錐は接線の方向 $d=(1,0)$ の倍数で、$d\cdot Wd=4>0$ である。$(0,0)$ の近くには $f(0,y)=-y^2<0$ の点がある。実行可能集合はコンパクトなので大域解があり、大域解は内部なら $\nabla f=0$、境界なら LICQ($\nabla g\ne0$)のもとで KKT 点だから、値を比べて $-1$ が最小値である。

罰金法で円周上の 1 次式を最小化する

問い:最小化 $x+2y$、条件 $h(x,y)=x^2+y^2-5=0$。
使う公式:fml-nlp-penalty、thm-nlp-multiplier。
答え:解は $(-1,-2)$、乗数は $\mu=\frac12$、最小値は $-5$ である。$P_\rho$ の最小点は下の表のとおりで(数値計算による値)、$\rho h\to\frac12$ となる。Hesse 行列の条件数は約 $20\rho$ である。

途中の計算を開く

$\nabla P_\rho=0$ は $1+2\rho hx=0$、$2+2\rho hy=0$ なので $y=2x$ で、$h=5x^2-5$ から $1+10\rho(x^2-1)x=0$ となる。この 3 次方程式の $-1$ の近くの根が $x$ である。Hesse 行列は $2\rho hI+4\rho\,(x,y)^{\mathsf T}(x,y)$ で、固有値は $2\rho h$ と $2\rho h+4\rho(x^2+y^2)$ である。Lagrange の条件は $1+2\mu x=0$、$2+2\mu y=0$ で、$\mu>0$ の側の解 $(-1,-2)$ が最小である($\mu<0$ の側の $(1,2)$ は最大)。

$\rho$$x$$y$$h(x,y)$$\rho h$条件数
$1$$-1.04668$$-2.09336$$0.47770$$0.47770$$23.9$
$10$$-1.00496$$-2.00993$$0.049753$$0.49753$$204$
$100$$-1.00050$$-2.00100$$0.0049975$$0.49975$$2004$
$1000$$-1.00005$$-2.00010$$0.00049998$$0.49998$$20004$
拡張 Lagrange 法で同じ問題を解く

問い:ex-nlp-penalty の問題を、$\rho=10$ に固定し、$\mu_0=0$ から解く。
使う公式:fml-nlp-auglag。
答え:下の表のとおりで、$\rho$ を増やさずに 3 回で $\mu$ が 7 桁合う。誤差 $\lvert\mu_k-\frac12\rvert$ は 1 回ごとに約 $0.004975$ 倍になる(数値計算による値)。

$k$最小点の $x$$h$更新後の $\mu$
$1$$-1.0049630$$4.9753\times10^{-2}$$0.4975308$
$2$$-1.0000246$$2.4570\times10^{-4}$$0.4999877$
$3$$-1.0000001$$1.2223\times10^{-6}$$0.4999999$

1 回目は $\rho=10$ の罰金法そのものである。この問題でも最小点は $y=2x$ の上にある。

逐次 2 次計画法で同じ問題を解く

問い:同じ問題を $(x_0,y_0,\mu_0)=(-1.5,-1.5,1)$ から、$\alpha=1$ で解く。
使う公式:thm-nlp-sqp。
答え:下の表のとおりで、誤差は 2 乗の速さで減る。$e_k$ は $\lvert(x_k,y_k)-(-1,-2)\rvert$ と $\lvert\mu_k-\frac12\rvert$ の大きいほうである。

1 回目の計算を開く

$W_0=2\mu_0I=2I$、$J_0=2(x_0,y_0)=(-3,-3)$、$\nabla_xL=(1+2\mu_0x_0,\ 2+2\mu_0y_0)=(-2,-1)$、$h=-0.5$ である。方程式は $2d_1-3\delta=2$、$2d_2-3\delta=1$、$-3d_1-3d_2=\frac12$ で、$d_1=\frac16$、$d_2=-\frac13$、$\delta=-\frac59$ である。よって $(x_1,y_1,\mu_1)=(-\frac43,-\frac{11}6,\frac49)$ である。

$k$$x_k$$y_k$$\mu_k$$e_k$
$0$$-1.5$$-1.5$$1$$0.7071$
$1$$-1.33333$$-1.83333$$0.44444$$0.3727$
$2$$-0.98086$$-2.05180$$0.49249$$0.05523$
$3$$-1.00083$$-2.00034$$0.49973$$9.02\times10^{-4}$
$4$$-0.9999998$$-2.0000003$$0.4999999$$3.70\times10^{-7}$
$5$$8.5\times10^{-14}$
障壁法の中心パスを閉じた形で求める

問い:最小化 $x^2+y^2$、条件 $2-x-y\le0$ の中心パスを求め、thm-nlp-barrier の精度を確かめる。解は $(1,1)$、$p^*=2$ である(凸最適化 の例「KKT 条件で解く」)。
使う公式:fml-nlp-barrier。
答え:$x(t)=y(t)=s(t):=\frac12\bigl(1+\sqrt{1+1/t}\bigr)$ である。$t=1,10,100,1000$ で $f-p^*=0.91421$、$0.09881$、$0.009988$、$0.0009999$ で、どれも $m/t=1/t$ 以下である。

途中の計算を開く

$B_t=t(x^2+y^2)-\log(x+y-2)$ は狭義凸で、$x,y$ について対称なので最小点は $x=y=s$ の上にある。$\partial_xB_t=0$ は $2ts=\frac1{2s-2}$、つまり $4ts(s-1)=1$ で、$s>1$ の根が上の式である。$\lambda(t)=\frac1{t(2s-2)}=2s$ で、双対関数の値は $2\lambda-\lambda^2/2$ なので、$f-$(双対関数の値)は $2s^2-4s+2s^2=4s(s-1)=1/t$ となり、定理の式のとおりである。

円板の上の Rosenbrock 関数

問い:最小化 $f(x,y)=(1-x)^2+100(y-x^2)^2$、条件 $g(x,y)=x^2+y^2-1\le0$。
使う公式:def-nlp-kkt、thm-nlp-sosc。
答え:$(x^*,y^*)\approx(0.786415,0.617698)$、$\lambda\approx0.121497$、$f\approx0.0456748$ である(数値計算による値)。LICQ が成り立ち、thm-nlp-sosc により狭義の局所解である。

確認を開く

制約のない最小点 $(1,1)$ は円板の外にあるので、$g=0$ の上で解を探す。$\nabla f+2\lambda(x,y)=0$ と $x^2+y^2=1$ の 3 本の連立方程式を、上の値の近くで解く。$\nabla g=2(x^*,y^*)\ne0$ なので LICQ が成り立つ。$\lambda>0$ なので臨界錐は接線の方向 $d=(-y^*,x^*)$ の倍数で、$W=\nabla^2f+2\lambda I$ について $d\cdot Wd\approx619.2>0$ である。凸でない問題なので、この計算だけでは大域解とは言えない。

使える条件と反例

外す条件反例成り立たなくなること
問題の凸性最小化 $x^2-y^2$、条件 $x^2+y^2\le1$KKT 点 $(0,0)$ が局所解でない
LICQ最小化 $x$、条件 $x^2\le0$解 $x=0$ は KKT 点でなく、$\lambda^k=2^{-2/3}\rho_k^{1/3}\to\infty$
$P_\rho$ の最小点の存在最小化 $-x^4$、条件 $x=0$どの $\rho$ でも $P_\rho$ は下に有界でない
最小点が大域的であること$f=0$、$h(x)=x^3-3x+3$局所最小点 $x=1$ が実行不可能($h(1)=1$)
臨界錐での正定値性最小化 $x^4$、条件 $y=0$Newton の反復が 1 次収束に落ちる($x_{k+1}=\frac23x_k$)
反復の点で $J_k$ が行フルランク条件 $x^2+y^2=1$、点 $(0,0)$(Q) の条件が $-1=0$ で実行不可能
狭義に実行可能な点の存在条件 $x^2\le0$$B_t$ の定義域が空
thm-nlp-barrier の凸性最小化 $(x^2-1)^2+0.2x$、条件 $x-2\le0$、$-x-2\le0$$B_t$ の局所最小点で $f-p^*\approx0.3999$、$m/t=0.02$($t=100$)
表の反例の確認

LICQ:$\nabla g(0)=0$ なので LICQ が成り立たない。$\nabla_xL=1+2\lambda x$ は $x=0$ で $1\ne0$ なので、解 $x=0$ は KKT 点でない。$P_\rho=x+\frac\rho2x^4$ の停留点は $x=-(2\rho)^{-1/3}$ で、$\lambda=\rho x^2=2^{-2/3}\rho^{1/3}$ である。thm-nlp-multiplier の収束が成り立たない。
$P_\rho$ の最小点:$P_\rho=-x^4+\frac\rho2x^2$ は $x\to\infty$ で $-\infty$ に近づく。問題自体の解は $x=0$ である。
実行不可能な極限:$h'(1)=0$、$h''(1)=6>0$、$h(1)=1>0$ なので、$x=1$ は $h^2$ の狭義の局所最小点で、どの $\rho$ でも $P_\rho=\frac\rho2h^2$ の局所最小点である。$h$ の実根は $x\approx-2.10380$ だけである。局所的な解法を $x=1$ の近くから始めると、$\rho$ を増やしても実行可能にならない。
1 次収束:$W=\mathrm{diag}(12x^2,0)$、$J=(0,1)$ で、thm-nlp-sqp の方程式から $y$ は $1$ 回で $0$ になり、$12x^2d_1=-4x^3$ から $d_1=-x/3$ である。核の方向 $d=(1,0)$ で $d\cdot Wd=0$ なので、定理の条件が満たされない。
線形化の矛盾:$h(0,0)=-1$、$J=(0,0)$ なので、$h+Jd=0$ は $-1=0$ となる。
凸でないときの障壁法:$f$ の局所最小点は $x\approx0.97399$(値 $0.19743$)、大域解は $x\approx-1.02412$(値 $-0.20244$)である。$t=100$ の $B_t$ の局所最小点 $x\approx0.97313$ は局所解の近くに留まる(数値計算による値)。

よくある誤り

誤り正しくはなぜ
KKT 点を見つければ解だと思う凸でなければ KKT 点は解とは限らないex-nlp-kkt
解なら必ず KKT 点だと思うLICQ などの制約想定が要るex-nlp-counterexamples
$g\ge0$ の形のまま $\lambda\ge0$ とする符号は $g\le0$ の形での約束。$g\ge0$ のまま書くなら $L=f-\lambda g$def-nlp-kkt
不等式の罰金を $\rho g^2$ とする$(g^+)^2$ にする。$g^2$ では効いていない制約まで罰するfml-nlp-penalty
$\rho$ を最初から非常に大きくする順に増やし、前の解を初期値にする。一度に大きくすると条件数が悪くなるex-nlp-penalty
$x$ の変化が小さいので止めるKKT 残差で判定する手順の段 6

演習

1 変数の罰金法

最小化 $x$、条件 $1-x\le0$ に罰金法を使う。$P_\rho$ の最小点と $\lambda=\rho g^+$ を求めよ。

解答を開く

$x<1$ で $P_\rho'=1-\rho(1-x)$ なので、最小点は $x=1-\frac1\rho$ である($x\ge1$ では $P_\rho'=1>0$)。$\lambda=\rho(1-x)=1$ で、KKT 点 $(1,1)$ の乗数に $\rho$ によらず一致する。解は実行可能集合のわずかに外にある。

2 次の問題の乗数の更新

最小化 $\frac12x^2$、条件 $x-1=0$ に拡張 Lagrange 法を使う。$\mu_{k+1}+1=(\mu_k+1)/(1+\rho)$ を示せ。

解答を開く

$\partial_xA_\rho=x+\mu+\rho(x-1)=0$ から $x=\frac{\rho-\mu}{1+\rho}$ である。$\mu^+=\mu+\rho(x-1)=\mu-\frac{\rho(1+\mu)}{1+\rho}=\frac{\mu-\rho}{1+\rho}$ なので、$\mu^++1=\frac{\mu+1}{1+\rho}$ である。よって $\mu_k\to-1$ で、$\rho$ が大きいほど速い。$\square$

等号が成り立つ障壁法

最小化 $x$、条件 $-x\le0$ の $x(t)$ を求め、thm-nlp-barrier の不等式が等号になることを確かめよ。

解答を開く

$B_t=tx-\log x$ の最小点は $x(t)=\frac1t$ である。$p^*=0$、$m=1$ なので $f(x(t))-p^*=\frac1t=\frac mt$ である。$\square$

補足

  • 不等式の拡張 Lagrange 法:$g_i\le0$ の項は、$\frac1{2\rho}\bigl(\max(0,\lambda_i+\rho g_i)^2-\lambda_i^2\bigr)$ の形で入れ、乗数を $\lambda_i\leftarrow\max(0,\lambda_i+\rho g_i)$ で更新する。ex-nlp-rosenbrock はこの形でも解ける。
  • 最小二乗の形:目的関数が 2 乗の和で制約が等式の問題は、罰金法・拡張 Lagrange 法の部分問題も 2 乗の和になる(VMLS18 §19.2–19.3、pp. 421–424)。
  • 大域解を保証する方法:凸でない問題の大域解を一般に求めるのは難しい。分枝限定法は 整数計画法 と同じ考えを連続の変数に使う。

関連項目

参考文献

[1]
Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st ed., Cambridge University Press, 2004, §11.2.2(中心パスと双対の点、精度 m/t、pp. 564–566)、§11.3.1(障壁法の手順、p. 569)
[2]
Stephen Boyd, Lieven Vandenberghe, Introduction to Applied Linear Algebra: Vectors, Matrices, and Least Squares, 1st ed., Cambridge University Press, 2018, §19.2 Penalty algorithm(pp. 421–422、Algorithm 19.1)、§19.3 Augmented Lagrangian algorithm(pp. 422–424、Algorithm 19.2)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する