非線形計画法(nonlinear programming)とは、目的関数や制約に 1 次式でないものが入る最適化問題を解く方法の総称である。制約のある問題を、制約のない最小化の列(罰金法、拡張 Lagrange 法)、2 次計画問題の列(逐次 2 次計画法)、実行可能集合の内部での最小化の列(障壁法・内点法)に置き換えて解く。反復は KKT 点を探すもので、問題が凸でなければ得られるのは一般に局所解である。工学の設計、機械学習、経済の数理などの連続最適化に使う。
前提知識: 最適化, 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$ と書いて、この形に直す。乗数の符号はこの形についての約束である。
$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条件 の主題で、この記事では判定に要る形を表にまとめる。
この記事の方法を使う条件は次のとおりである。
判定の条件を次の表にまとめる。$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 行列を近似する。
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\}
$$
と定める。
$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$ 全体での最小点であるとする。このとき次が成り立つ。
$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$ に比例して大きくなる。これが罰金法の実用上の弱点である。
$\rho$ を無限大に送らずに済ませるのが 拡張 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 次計画法(SQP)は、$x_k$ で目的関数を 2 次式、制約を 1 次式で近似した問題を解く方法である。等式の制約について述べる。$W_k:=\nabla_x^2L(x_k,\mu_k)$、$J_k:=Dh(x_k)$ とする。
$$ \text{(Q)}\qquad\text{最小化 } \nabla f(x_k)\cdot d+\frac12d\cdot W_kd\quad\text{条件 } h(x_k)+J_kd=0 $$
$f,h_j$ を $C^3$ 級とし、$F(x,\mu):=\bigl(\nabla_xL(x,\mu),h(x)\bigr)$ とおく。
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 つの方法の解との距離の減り方(例題の問題)
全体の流れは次のとおりである。
| 問題の状況 | 選ぶ方法 |
|---|---|
| 制約がない | 勾配降下法、準Newton法、Newton の方法 |
| 目的関数が 2 次式で制約が 1 次式 | 2 次計画法(等式の制約だけなら thm-nlp-sqp の 1 の連立 1 次方程式を 1 回解けばよい) |
| 凸で、不等式の制約が多い | 障壁法・内点法 |
| 凸でなく、導関数が 2 階まで使える中規模の問題 | 逐次 2 次計画法 |
| 変数が非常に多く、1 階の導関数しか使えない | 拡張 Lagrange 法 |
| 既存の制約なしの解法しか使えない | 罰金法で近似し、拡張 Lagrange 法で仕上げる |
罰金法。
拡張 Lagrange 法(等式の制約。VMLS18 Algorithm 19.2 は最小二乗の形の同じ手順である)。
逐次 2 次計画法(等式の制約)。
障壁法(BV04 §11.3.1、p. 569)。
問い:最小化 $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$ が最小値である。
問い:最小化 $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$ |
問い: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$ の上にある。
問い:同じ問題を $(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$ の大きいほうである。
$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$ となり、定理の式のとおりである。
問い:最小化 $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 |
最小化 $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$ によらず一致する。解は実行可能集合のわずかに外にある。
最小化 $\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$
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する