第4章制約付き最適化と双対性（最適化） | Lemma

この章の目標

等式制約の問題をラグランジュの未定乗数法で扱い、階数条件の役割を説明できる

不等式制約を含む問題の KKT 条件を書き、LICQ のもとで必要条件であることを証明できる。制約想定がないと成り立たない例を挙げられる

凸問題では KKT 条件が十分条件であることを証明し、KKT 条件から最適解を求められる

ラグランジュ双対問題を作り、弱双対性と、スレーター条件のもとでの強双対性を証明できる

二次計画・ポートフォリオ・SVM・water-filling の最適解と双対問題を導き、乗数を感度として解釈できる

前提：第2章、第3章、01-calculus 第8章。例では 02-linear-algebra 第8章の正定値行列を使う。

予算の上限、設備の能力、規制、在庫が負にならないこと。実際の最適化問題には必ず制約がある。制約がなければ最適解では勾配が $0$ になる（第1章）が、制約があると、最適解で勾配は $0$ にならず、制約の「押し返す力」とつり合う。この力の大きさがラグランジュ乗数であり、それを並べた条件が KKT 条件（カルーシュ–キューン–タッカー条件, Karush–Kuhn–Tucker conditions）である。

第3章の線形計画法では、双対問題が最適性の証明書になり、双対変数がシャドウプライスを表した。本章ではこれを非線形の問題に広げる。乗数は「制約を少しゆるめたとき最適値がどれだけ改善するか」を表し、双対問題は最適値の下界を与える。凸問題では、スレーター条件のもとで下界と最適値が一致する。これはサポートベクターマシン（SVM）の理論、内点法（第6章）、整数計画の分枝限定法（第7章）の基礎でもある。

本章では次の形の問題を考える。

\text{(P)} \qquad \text{minimize} \quad f(x) \qquad \text{subject to} \quad g_i(x) \leq 0 \ (i = 1, \dots, m), \quad h_j(x) = 0 \ (j = 1, \dots, p)

制約を満たす $x$ を実行可能といい、(P) の最適値（下限）を $p^{\ast}$ と書く。記法は第3章と同じで、 $\mathbf{1}$ は成分がすべて $1$ のベクトルである。

4.1 等式制約とラグランジュの未定乗数法

等式制約だけの場合は、01-calculus 第8章定理 8.11（ラグランジュの未定乗数法）で扱った。本章の記号で書くと次のようになる： $f, h_1, \dots, h_p$ が $C^1$ 級、 $x^{\ast}$ が $h = 0$ のもとでの $f$ の極値点で、 $\nabla h_1(x^{\ast}), \dots, \nabla h_p(x^{\ast})$ が一次独立ならば、

\nabla f(x^{\ast}) + \sum_{j=1}^{p}\nu_j\nabla h_j(x^{\ast}) = 0

となる $\nu \in \mathbb{R}^p$ が存在する（01-calculus 第8章の乗数 $\lambda_j$ が $-\nu_j$ にあたる）。勾配の一次独立性の条件は外せない。01-calculus 第8章（定理 8.11 の後の注意）では、尖点のある曲線 $y^2 = x^3$ の上で $x$ を最小化すると原点で乗数が存在しない例を見た。

例 4.1（最小分散ポートフォリオ） $n$ 個の資産の収益率の共分散行列 $\Sigma$ が正定値のとき、予算制約 $\mathbf{1}^{\top}w = 1$ のもとで分散 $w^{\top}\Sigma w$ を最小にする（空売りを許す）。ラグランジュの条件は $2\Sigma w + \nu\mathbf{1} = 0$ で、 $w = -\frac{\nu}{2}\Sigma^{-1}\mathbf{1}$ を予算制約に代入すると

w^{\ast} = \frac{\Sigma^{-1}\mathbf{1}}{\mathbf{1}^{\top}\Sigma^{-1}\mathbf{1}}, \qquad w^{\ast\top}\Sigma w^{\ast} = \frac{1}{\mathbf{1}^{\top}\Sigma^{-1}\mathbf{1}}

を得る。これが最小であることは直接確かめられる： $\mathbf{1}^{\top}w = 1$ なら $d = w - w^{\ast}$ は $\mathbf{1}^{\top}d = 0$ を満たし、 $\Sigma w^{\ast}$ は $\mathbf{1}$ の定数倍なので $w^{\ast\top}\Sigma d = 0$ 、よって $w^{\top}\Sigma w = w^{\ast\top}\Sigma w^{\ast} + d^{\top}\Sigma d \geq w^{\ast\top}\Sigma w^{\ast}$ 。数値例として、期待収益率 $\mu = (4, 7, 10)$ （%）、標準偏差 $10, 15, 20$ （%）、相関係数 $\rho_{12} = 0.2$ , $\rho_{13} = 0.1$ , $\rho_{23} = 0.3$ の 3 資産、すなわち

\Sigma = \begin{pmatrix} 100 & 30 & 20 \\ 30 & 225 & 90 \\ 20 & 90 & 400 \end{pmatrix} \quad (\%^2)

では、 $w^{\ast} = (233, 70, 38)/341 \approx (0.683, 0.205, 0.111)$ 、分散 $26160/341 \approx 76.7$ （標準偏差約 $8.76$ %）、期待収益率 $1802/341 \approx 5.28$ % である（sympy で厳密に計算した）。この 3 資産は 4.7 節でも使う。

4.2 不等式制約と KKT 条件

1 変数の問題「 $x \geq 0$ のもとで $f(x)$ を最小化」を考える。最適解 $x^{\ast}$ が $x^{\ast} > 0$ なら $f'(x^{\ast}) = 0$ 、 $x^{\ast} = 0$ なら右にしか動けないので $f'(0) \geq 0$ である。どちらも「 $f'(x^{\ast}) = \lambda$ , $\lambda \geq 0$ , $\lambda x^{\ast} = 0$ となる $\lambda$ がある」とまとめられる。これを一般化する。

定義 4.2（ラグランジュ関数・KKT 条件） $\lambda \in \mathbb{R}^m$ , $\nu \in \mathbb{R}^p$ に対し
$L(x, \lambda, \nu) = f(x) + \sum_{i=1}^{m}\lambda_ig_i(x) + \sum_{j=1}^{p}\nu_jh_j(x)$
をラグランジュ関数 (Lagrangian) という。実行可能な $x^{\ast}$ で $g_i(x^{\ast}) = 0$ となる $i$ の集合 $I(x^{\ast})$ を有効制約の集合という。 $f, g_i, h_j$ が $x^{\ast}$ で微分可能なとき、次の 4 条件を KKT 条件といい、満たす $\lambda, \nu$ をラグランジュ乗数 (Lagrange multiplier) という。

（停留性） $\nabla f(x^{\ast}) + \sum_i \lambda_i\nabla g_i(x^{\ast}) + \sum_j \nu_j\nabla h_j(x^{\ast}) = 0$

（主実行可能性） $g_i(x^{\ast}) \leq 0$ , $h_j(x^{\ast}) = 0$

（双対実行可能性） $\lambda_i \geq 0$

（相補性） $\lambda_ig_i(x^{\ast}) = 0$ （ $i = 1, \dots, m$ ）

相補性により、有効でない制約（ $g_i(x^{\ast}) < 0$ ）の乗数は $0$ である。停留性は「 $-\nabla f(x^{\ast})$ が、有効な不等式制約の外向きの法線 $\nabla g_i$ の非負結合と、等式制約の法線の一次結合で書ける」ことを意味する。

定義 4.3（LICQ） $\nabla g_i(x^{\ast})$ （ $i \in I(x^{\ast})$ ）と $\nabla h_j(x^{\ast})$ （ $j = 1, \dots, p$ ）が一次独立であるとき、 $x^{\ast}$ で一次独立制約想定 (linear independence constraint qualification, LICQ) が成り立つという。

定理 4.4（KKT 条件の必要性）開集合 $U \subset \mathbb{R}^n$ 上で $f, g_i, h_j$ は $C^1$ 級とし、 $x^{\ast} \in U$ を (P) の局所最適解とする。 $x^{\ast}$ で LICQ が成り立てば、KKT 条件を満たす $\lambda, \nu$ がただ一組存在する。

証明. $I = I(x^{\ast})$ , $k = \lvert I \rvert + p$ とし、 $\nabla g_i(x^{\ast})^{\top}$ （ $i \in I$ ）と $\nabla h_j(x^{\ast})^{\top}$ を行とする $k \times n$ 行列を $G$ 、対応する関数を並べた写像を $c(z) = ((g_i(z))_{i \in I}, (h_j(z))_j) \in \mathbb{R}^k$ とする。LICQ より $\operatorname{rank} G = k$ である。

第 1 段（線形化した方向に沿う実行可能な曲線）. $d \in \mathbb{R}^n$ が

\nabla g_i(x^{\ast})^{\top}d \leq 0 \quad (i \in I), \qquad \nabla h_j(x^{\ast})^{\top}d = 0 \quad (j = 1, \dots, p) \tag{1}

を満たすとする。 $\operatorname{Ker} G$ の基底を列に並べた $n \times (n - k)$ 行列を $Z$ とし、 $(t, z) \in \mathbb{R} \times U$ に対して

F(t, z) = \begin{pmatrix} c(z) - tGd \\ Z^{\top}(z - x^{\ast} - td) \end{pmatrix} \in \mathbb{R}^{n}

とおく（ $k = 0$ や $k = n$ のときは該当する行がないと読む）。 $F(0, x^{\ast}) = 0$ で、 $F$ の $z$ についての微分は、 $G$ の下に $Z^{\top}$ を並べた $n$ 次正方行列である。これは正則である： $Gv = 0$ かつ $Z^{\top}v = 0$ なら、 $v \in \operatorname{Ker} G$ かつ $v$ は $\operatorname{Ker} G$ に直交するので $v = 0$ 。陰関数定理（01-calculus 第8章定理 8.7）より、 $C^1$ 級の曲線 $z(t)$ （ $\lvert t \rvert < \varepsilon$ ）で $z(0) = x^{\ast}$ , $F(t, z(t)) = 0$ となるものがある。 $t = 0$ で微分すると $G(z'(0) - d) = 0$ , $Z^{\top}(z'(0) - d) = 0$ なので、同じ理由で $z'(0) = d$ 。また $F = 0$ の上半分から、 $i \in I$ について $g_i(z(t)) = t\nabla g_i(x^{\ast})^{\top}d \leq 0$ （ $t \geq 0$ ）、 $h_j(z(t)) = 0$ 。 $i \notin I$ なら $g_i(x^{\ast}) < 0$ なので、連続性から小さい $t$ で $g_i(z(t)) < 0$ 。よって十分小さい $t \geq 0$ で $z(t)$ は実行可能である。

第 2 段. $x^{\ast}$ は局所最適で $z(t) \to x^{\ast}$ なので、小さい $t > 0$ で $f(z(t)) \geq f(x^{\ast})$ 。 $t$ で割って $t \to +0$ とすると、連鎖律より $\nabla f(x^{\ast})^{\top}z'(0) = \nabla f(x^{\ast})^{\top}d \geq 0$ 。すなわち (1) を満たすすべての $d$ で $\nabla f(x^{\ast})^{\top}d \geq 0$ である。

第 3 段（ファルカスの補題）. 列 $\nabla g_i(x^{\ast})$ （ $i \in I$ ）, $\nabla h_j(x^{\ast})$ , $-\nabla h_j(x^{\ast})$ を並べた行列を $M$ とする。 $Mw = -\nabla f(x^{\ast})$ , $w \geq 0$ が解をもたないとすると、第3章のファルカスの補題（定理 3.22）より、 $M^{\top}y \geq 0$ , $-\nabla f(x^{\ast})^{\top}y < 0$ となる $y$ がある。 $d = -y$ は $\nabla g_i^{\top}d \leq 0$ （ $i \in I$ ）、 $\pm\nabla h_j^{\top}d \leq 0$ すなわち $\nabla h_j^{\top}d = 0$ を満たし、 $\nabla f(x^{\ast})^{\top}d < 0$ となって第 2 段に反する。よって解 $w \geq 0$ があり、その成分を $\lambda_i$ （ $i \in I$ ）と $\nu_j^{+}, \nu_j^{-}$ に分けて $\nu_j = \nu_j^{+} - \nu_j^{-}$ 、 $i \notin I$ では $\lambda_i = 0$ とおけば、KKT 条件の 4 つがすべて成り立つ。停留性に現れる勾配は LICQ により一次独立なので、乗数は一意である。 $\square$

命題 4.5（一次の制約）すべての $g_i, h_j$ が一次関数（アフィン関数 $a^{\top}x + \beta$ ）ならば、制約想定なしに定理 4.4 の結論が成り立つ（ただし乗数の一意性を除く）。

証明. 第 1 段で $z(t) = x^{\ast} + td$ とすればよい。実際 $i \in I$ なら $g_i(x^{\ast} + td) = g_i(x^{\ast}) + t\nabla g_i^{\top}d = t\nabla g_i^{\top}d \leq 0$ 、同様に $h_j(x^{\ast} + td) = 0$ で、有効でない制約は連続性から保たれる。第 2・3 段はそのまま使える。 $\square$

線形計画問題はこの場合にあたり、KKT 条件は第3章の主実行可能性・双対実行可能性・相補性条件（定理 3.28）そのものである（4.4 節の例 4.12）。

例 4.6（制約想定がないと KKT 条件は成り立たない）

\text{minimize} \quad -x_1 \qquad \text{subject to} \quad g_1(x) = x_2 - (1 - x_1)^3 \leq 0, \quad g_2(x) = -x_2 \leq 0

を考える。実行可能なら $0 \leq x_2 \leq (1 - x_1)^3$ より $x_1 \leq 1$ なので、最適解は $x^{\ast} = (1, 0)$ である。そこでは両方の制約が有効で、 $\nabla g_1(x^{\ast}) = (3(1 - x_1)^2, 1) = (0, 1)$ , $\nabla g_2(x^{\ast}) = (0, -1)$ は一次従属であり、LICQ が成り立たない。停留性 $(-1, 0) + \lambda_1(0, 1) + \lambda_2(0, -1) = 0$ は第 1 成分が $-1 = 0$ となって解をもたないので、KKT 条件を満たす乗数は存在しない。実行可能領域が $x^{\ast}$ で尖っているため、 $d = (1, 0)$ は線形化した条件 (1) を満たすのに、その方向に進む実行可能な曲線がないのである。

LICQ より弱い制約想定（マンガサリアン–フロモヴィッツの制約想定など）のもとでも KKT 条件は必要条件になる（主張のみ。Bertsekas, Nonlinear Programming や Nocedal–Wright, Numerical Optimization を参照）。凸問題ではスレーター条件がその役割を果たす（系 4.16）。

注意

KKT 条件は、制約想定のもとでの必要条件にすぎない。(1) 凸でない問題では、KKT 条件を満たす点が鞍点や局所最大点であることがある（問題 4.4）。(2) 逆に、制約想定が成り立たない最適解では KKT 条件が成り立たないことがある（例 4.6）。KKT 点を数値的に求める手法が返した点が最適であると言えるのは、問題が凸であるとき（定理 4.7）か、別の議論で確かめたときだけである。

4.3 凸問題での十分性

定理 4.7（凸問題での KKT 条件の十分性） $U \subset \mathbb{R}^n$ を開凸集合、 $f, g_1, \dots, g_m$ を $U$ 上の微分可能な凸関数、 $h_1, \dots, h_p$ を一次関数とする。 $x^{\ast} \in U$ と $\lambda, \nu$ が KKT 条件を満たせば、 $x^{\ast}$ は (P) の（ $U$ の中での）大域最適解である。

証明. $x \in U$ を実行可能とする。 $\lambda \geq 0$ , $g_i(x) \leq 0$ , $h_j(x) = 0$ より $f(x) \geq L(x, \lambda, \nu)$ 。 $x \mapsto L(x, \lambda, \nu)$ は凸関数の非負結合と一次関数の和なので凸で微分可能、停留性より $\nabla_xL(x^{\ast}, \lambda, \nu) = 0$ 。第2章の 1 次条件（定理 2.14）より $L(x, \lambda, \nu) \geq L(x^{\ast}, \lambda, \nu) + \nabla_xL(x^{\ast}, \lambda, \nu)^{\top}(x - x^{\ast}) = L(x^{\ast}, \lambda, \nu)$ で、相補性と $h(x^{\ast}) = 0$ より $L(x^{\ast}, \lambda, \nu) = f(x^{\ast})$ 。よって $f(x) \geq f(x^{\ast})$ 。 $\square$

したがって、制約が一次式の凸問題（たとえば凸二次計画）では、命題 4.5 と定理 4.7 により「最適解であること」と「KKT 条件を満たすこと」が同値になる。KKT 条件を解くには、どの制約が有効かを仮定して等式として解き、乗数の符号と実行可能性を確かめればよい。

例 4.8（二次計画）

\text{minimize} \quad (x_1 - 2)^2 + (x_2 - 3)^2 \qquad \text{subject to} \quad x_1 + x_2 \leq 2, \quad x_2 \leq 1, \quad -x_1 \leq 0

は、点 $a = (2, 3)$ に最も近い実行可能な点を求める問題である。有効制約の組を仮定して解くと、次のようになる（乗数は有効な制約のもの。計算機でも確かめた）。

有効制約	点 $x$	乗数	判定
なし	$(2, 3)$	—	第 1・2 制約を破る
第 1	$(1/2, 3/2)$	$\lambda_1 = 3$	第 2 制約を破る
第 2	$(2, 1)$	$\lambda_2 = 4$	第 1 制約を破る
第 1, 2	$(1, 1)$	$\lambda_1 = \lambda_2 = 2$	KKT 条件を満たす
第 2, 3	$(0, 1)$	$\lambda_2 = 4$ , $\lambda_3 = -4$	$\lambda_3 < 0$

（第 3 だけ・第 1, 3 の組の点は実行不能で、3 つを同時に等号にする点はない。）たとえば第 1, 2 制約を有効とすると、 $x = (1, 1)$ で停留性 $2(x - a) + \lambda_1(1, 1) + \lambda_2(0, 1) = 0$ が $(-2, -4) + (\lambda_1, \lambda_1 + \lambda_2) = 0$ となり、 $\lambda_1 = \lambda_2 = 2 \geq 0$ 。第 3 制約は $x_1 = 1 > 0$ で有効でなく $\lambda_3 = 0$ 。凸問題なので、定理 4.7 より $x^{\ast} = (1, 1)$ が最適で、最適値は $1 + 4 = 5$ である。

ヒント

実務では 二次計画や一般の凸最適化のソルバー（有効制約法・内点法など）は、最適解と一緒にラグランジュ乗数を返し、KKT 条件の残差（停留性・実行可能性・相補性がどれだけ破れているか）と、4.4 節の双対ギャップ $f(x) - q(\lambda, \nu)$ を停止基準に使う。弱双対性により、双対ギャップは「いまの解の値が最適値からどれだけ離れうるか」の保証になる。乗数は 4.6 節の意味で「その制約の値段」なので、どの制約が効いているか（ボトルネック）を知る手がかりにもなる。

4.4 ラグランジュ双対問題と弱双対性

(P) の関数がすべて定義される集合を $D$ とし、 $D$ の点で制約を満たすものを実行可能解とする。この節の結果は $D$ が凸でなくても成り立つ。

定義 4.9（ラグランジュ双対） $\lambda \in \mathbb{R}^m$ , $\nu \in \mathbb{R}^p$ に対し
$q(\lambda, \nu) = \inf_{x \in D}L(x, \lambda, \nu) \in [-\infty, \infty)$
を双対関数 (dual function) という。 $\lambda \geq 0$ のもとで $q(\lambda, \nu)$ を最大化する問題を (P) のラグランジュ双対問題、その最適値（上限）を $d^{\ast}$ という。

命題 4.10 $q$ は凹関数である（(P) が凸でなくてもよい）。

証明. 各 $x$ について $(\lambda, \nu) \mapsto L(x, \lambda, \nu)$ は一次関数である。 $0 < \theta < 1$ とすると（ $-\infty$ を含む計算は $\theta \cdot (-\infty) = -\infty$ と約束する）、 $\inf_x$ の中で $\theta L(x, \lambda, \nu) + (1 - \theta)L(x, \lambda', \nu') \geq \theta q(\lambda, \nu) + (1 - \theta)q(\lambda', \nu')$ なので、 $q(\theta(\lambda, \nu) + (1 - \theta)(\lambda', \nu')) \geq \theta q(\lambda, \nu) + (1 - \theta)q(\lambda', \nu')$ 。 $\square$

双対問題は、元の問題が凸でなくても、凹関数の最大化という凸最適化問題である。

定理 4.11（弱双対性, weak duality） $x$ が (P) の実行可能解、 $\lambda \geq 0$ ならば $q(\lambda, \nu) \leq f(x)$ 。特に $d^{\ast} \leq p^{\ast}$ 。

証明. $q(\lambda, \nu) \leq L(x, \lambda, \nu) = f(x) + \sum_i \lambda_ig_i(x) + \sum_j \nu_jh_j(x) \leq f(x)$ （ $\lambda_i \geq 0$ , $g_i(x) \leq 0$ , $h_j(x) = 0$ ）。 $\square$

$p^{\ast} - d^{\ast} \geq 0$ を双対ギャップ (duality gap) という。

例 4.12（線形計画）標準形 minimize $c^{\top}x$ subject to $Ax = b$ , $x \geq 0$ で、 $g(x) = -x$ , $h(x) = Ax - b$ , $D = \mathbb{R}^n$ とすると、 $L = (c - \lambda + A^{\top}\nu)^{\top}x - b^{\top}\nu$ 。 $x$ についての下限は、 $c - \lambda + A^{\top}\nu = 0$ なら $-b^{\top}\nu$ 、そうでなければ $-\infty$ である。よって双対問題は「 $\lambda = c + A^{\top}\nu \geq 0$ のもとで $-b^{\top}\nu$ を最大化」で、 $y = -\nu$ とおくと第3章の双対問題「 $A^{\top}y \leq c$ のもとで $b^{\top}y$ を最大化」に一致する。

例 4.13（例 4.8 の双対） $a = (2, 3)$ 、制約を $Gx \leq \beta$ と書く（ $G$ の行は $(1, 1)$ , $(0, 1)$ , $(-1, 0)$ 、 $\beta = (2, 1, 0)$ ）。 $L = \lVert x - a \rVert^2 + \lambda^{\top}(Gx - \beta)$ は $x$ について強凸な二次関数で、 $x = a - \frac{1}{2}G^{\top}\lambda$ で最小になるので

q(\lambda) = -\frac{1}{4}\lVert G^{\top}\lambda \rVert^2 + \lambda^{\top}(Ga - \beta), \qquad Ga - \beta = (3, 2, -2)

$\lambda = (2, 2, 0)$ では $G^{\top}\lambda = (2, 4)$ で $q = -5 + 10 = 5$ となり、主問題の最適値 $5$ に等しい。双対ギャップは $0$ である。

命題 4.14（最適性の証明書） $x^{\ast}$ が (P) の実行可能解、 $\lambda^{\ast} \geq 0$ で、 $f(x^{\ast}) = q(\lambda^{\ast}, \nu^{\ast})$ ならば、次が成り立つ。

$x^{\ast}$ は (P) の最適解、 $(\lambda^{\ast}, \nu^{\ast})$ は双対問題の最適解で、 $p^{\ast} = d^{\ast}$ 。

$\lambda_i^{\ast}g_i(x^{\ast}) = 0$ （ $i = 1, \dots, m$ ）。

$x^{\ast}$ は $D$ 上で $L(\cdot, \lambda^{\ast}, \nu^{\ast})$ を最小にする。

逆に、(P) が定理 4.7 の仮定を満たし（ $D = U$ ）、 $x^{\ast}$ と $\lambda^{\ast}, \nu^{\ast}$ が KKT 条件を満たせば、 $f(x^{\ast}) = q(\lambda^{\ast}, \nu^{\ast})$ である。

証明. $q(\lambda^{\ast}, \nu^{\ast}) \leq L(x^{\ast}, \lambda^{\ast}, \nu^{\ast}) = f(x^{\ast}) + \sum_i \lambda_i^{\ast}g_i(x^{\ast}) \leq f(x^{\ast}) = q(\lambda^{\ast}, \nu^{\ast})$ なので、すべて等号である。2 番目の等号から $\sum_i \lambda_i^{\ast}g_i(x^{\ast}) = 0$ で、各項が $0$ 以下だから各項が $0$ 。1 番目の等号が 3 である。1 は弱双対性から従う。逆： $L(\cdot, \lambda^{\ast}, \nu^{\ast})$ は凸で $x^{\ast}$ で勾配が $0$ なので、1 次条件（第2章定理 2.14）より $x^{\ast}$ で最小になり、 $q(\lambda^{\ast}, \nu^{\ast}) = L(x^{\ast}, \lambda^{\ast}, \nu^{\ast}) = f(x^{\ast})$ （相補性）。 $\square$

特に、制約が一次式で $f$ が $C^1$ 級の凸関数の問題では、最適解が存在すれば KKT 条件を満たす乗数があり（命題 4.5）、それが双対問題の最適解で、双対ギャップは $0$ である。凸でない問題では双対ギャップが正になりうる（問題 4.7）。

4.5 スレーター条件と強双対性

非線形の凸問題で双対ギャップが $0$ になるための代表的な十分条件がスレーター条件である。以下、 $D \subset \mathbb{R}^n$ は凸集合、 $f, g_i\colon D \to \mathbb{R}$ は凸関数、等式制約は $h(x) = Hx - \eta$ （ $H \in \mathbb{R}^{p \times n}$ , $\operatorname{rank} H = p$ 。冗長な等式は除いておく）とする。

定理 4.15（スレーター条件のもとでの強双対性, strong duality）スレーター条件「 $D$ の内点 $\tilde{x}$ で $g_i(\tilde{x}) < 0$ （すべての $i$ ）かつ $H\tilde{x} = \eta$ となるものがある」が成り立ち、 $p^{\ast}$ が有限であるとする。このとき $\lambda^{\ast} \geq 0$ , $\nu^{\ast}$ で $q(\lambda^{\ast}, \nu^{\ast}) = p^{\ast}$ となるものが存在する。すなわち $d^{\ast} = p^{\ast}$ で、双対問題は最適解をもつ。

証明. $\mathbb{R}^m \times \mathbb{R}^p \times \mathbb{R}$ の 2 つの集合

\mathcal{A} = \lbrace (u, v, t) \mid \text{ある } x \in D \text{ で } g(x) \leq u,\ Hx - \eta = v,\ f(x) \leq t \rbrace, \qquad \mathcal{B} = \lbrace (0, 0, s) \mid s < p^{\ast} \rbrace

を考える。 $\mathcal{A}$ は凸である：点 $x, x'$ が $(u, v, t), (u', v', t')$ を与えれば、 $f, g_i$ の凸性と $h$ の一次性より $\theta x + (1 - \theta)x'$ は $\theta(u, v, t) + (1 - \theta)(u', v', t')$ を与える。 $\mathcal{B}$ も凸で、どちらも空でない。 $(0, 0, s) \in \mathcal{A}$ （ $s < p^{\ast}$ ）なら $f(x) \leq s < p^{\ast}$ となる実行可能解 $x$ があることになるので、 $\mathcal{A} \cap \mathcal{B} = \emptyset$ 。第2章の分離定理（定理 2.11 (1) で $C_1 = \mathcal{B}$ , $C_2 = \mathcal{A}$ とする）より、 $(\tilde{\lambda}, \tilde{\nu}, \kappa) \neq 0$ で、すべての $(u, v, t) \in \mathcal{A}$ と $s < p^{\ast}$ について

\kappa s \leq \tilde{\lambda}^{\top}u + \tilde{\nu}^{\top}v + \kappa t

となるものがある。 $(u, v, t) \in \mathcal{A}$ なら $u$ の成分や $t$ を大きくしても $\mathcal{A}$ に属するので、右辺が下に有界であることから $\tilde{\lambda} \geq 0$ , $\kappa \geq 0$ 。 $s \to p^{\ast}$ として $x \in D$ に対応する点を代入すると

\kappa p^{\ast} \leq \tilde{\lambda}^{\top}g(x) + \tilde{\nu}^{\top}(Hx - \eta) + \kappa f(x) \qquad (x \in D) \tag{2}

$\kappa > 0$ なら、 $\kappa$ で割ると $L(x, \tilde{\lambda}/\kappa, \tilde{\nu}/\kappa) \geq p^{\ast}$ （ $x \in D$ ）、すなわち $q(\tilde{\lambda}/\kappa, \tilde{\nu}/\kappa) \geq p^{\ast}$ で、弱双対性と合わせて等号が成り立つ。 $\kappa = 0$ とすると矛盾が生じることを示す。(2) で $x = \tilde{x}$ とすると $\tilde{\lambda}^{\top}g(\tilde{x}) \geq 0$ で、 $g_i(\tilde{x}) < 0$ , $\tilde{\lambda} \geq 0$ より $\tilde{\lambda} = 0$ 。すると $\tilde{\nu} \neq 0$ で、(2) は $\tilde{\nu}^{\top}(Hx - \eta) \geq 0$ （ $x \in D$ ）となる。 $\operatorname{rank} H = p$ より $H^{\top}\tilde{\nu} \neq 0$ で、 $\tilde{x}$ は $D$ の内点だから小さい $\varepsilon > 0$ で $x = \tilde{x} - \varepsilon H^{\top}\tilde{\nu} \in D$ 。このとき $\tilde{\nu}^{\top}(Hx - \eta) = -\varepsilon\lVert H^{\top}\tilde{\nu} \rVert^2 < 0$ となり矛盾する（等式制約がなければ $\tilde{\lambda} = 0$ , $\kappa = 0$ がすでに $(\tilde{\lambda}, \kappa) \neq 0$ に反する）。 $\square$

系 4.16（スレーター条件のもとでの KKT 条件の必要性）定理 4.15 の仮定に加えて $D$ が開集合で $f, g_i$ が微分可能とする。 $x^{\ast}$ が (P) の最適解ならば、KKT 条件を満たす $\lambda^{\ast}, \nu^{\ast}$ が存在する。

証明. 定理 4.15 の $(\lambda^{\ast}, \nu^{\ast})$ は $q(\lambda^{\ast}, \nu^{\ast}) = p^{\ast} = f(x^{\ast})$ を満たすので、命題 4.14 より相補性が成り立ち、 $x^{\ast}$ は開集合 $D$ 上で $L(\cdot, \lambda^{\ast}, \nu^{\ast})$ の最小点である。よって $\nabla_xL(x^{\ast}, \lambda^{\ast}, \nu^{\ast}) = 0$ （第1章の 1 次の必要条件、定理 1.17）。 $\square$

例 4.17（スレーター条件がないと双対ギャップが生じうる） $D = \mathbb{R}^2$ で

\text{minimize} \quad e^{x_2} \qquad \text{subject to} \quad g(x) = \lVert x \rVert - x_1 \leq 0

を考える。 $g$ は凸で、 $\lVert x \rVert \leq x_1$ は $x_2 = 0$ , $x_1 \geq 0$ と同値なので $p^{\ast} = 1$ 。一方、 $L = e^{x_2} + \lambda(\lVert x \rVert - x_1) \geq 0$ で、 $x = (t^3, -t)$ とすると $\lVert x \rVert - x_1 = \frac{t^2}{\sqrt{t^6 + t^2} + t^3} \leq \frac{1}{2t}$ より $L \leq e^{-t} + \frac{\lambda}{2t} \to 0$ （ $t \to \infty$ ）。よって $q(\lambda) = 0$ （ $\lambda \geq 0$ ）、 $d^{\ast} = 0 < 1 = p^{\ast}$ 。 $g(x) < 0$ となる点がないので、スレーター条件は成り立たない。

4.6 感度の解釈

第3章で、線形計画の双対変数は右辺を動かしたときの最適値の変化率（シャドウプライス）を表した（定理 3.30）。一般の問題でも同じことが言える。制約をゆるめた問題

p^{\ast}(u, v) = \inf\lbrace f(x) \mid x \in D,\ g_i(x) \leq u_i,\ h_j(x) = v_j \rbrace

を考える（ $p^{\ast}(0, 0) = p^{\ast}$ ）。

定理 4.18（感度） $d^{\ast} = p^{\ast}$ が有限で、 $(\lambda^{\ast}, \nu^{\ast})$ が双対問題の最適解であるとする。

すべての $(u, v)$ について $p^{\ast}(u, v) \geq p^{\ast} - \lambda^{\ast\top}u - \nu^{\ast\top}v$ 。

$p^{\ast}(u, v)$ が $(0, 0)$ で $u_i$ について偏微分可能ならば $\lambda_i^{\ast} = -\frac{\partial p^{\ast}}{\partial u_i}(0, 0)$ 。 $v_j$ について偏微分可能ならば $\nu_j^{\ast} = -\frac{\partial p^{\ast}}{\partial v_j}(0, 0)$ 。

証明. 1： $x$ がゆるめた問題の実行可能解なら $p^{\ast} = q(\lambda^{\ast}, \nu^{\ast}) \leq L(x, \lambda^{\ast}, \nu^{\ast}) \leq f(x) + \lambda^{\ast\top}u + \nu^{\ast\top}v$ （ $\lambda^{\ast} \geq 0$ , $g(x) \leq u$ , $h(x) = v$ ）。 $x$ について下限をとればよい（実行可能解がなければ $p^{\ast}(u, v) = +\infty$ で自明）。2：1 で $(u, v) = (te_i, 0)$ とすると $p^{\ast}(te_i, 0) - p^{\ast} \geq -\lambda_i^{\ast}t$ 。 $t > 0$ と $t < 0$ でそれぞれ $t$ で割って $t \to 0$ とすると $\frac{\partial p^{\ast}}{\partial u_i} \geq -\lambda_i^{\ast}$ と $\leq -\lambda_i^{\ast}$ 。 $\nu^{\ast}$ も同様。 $\square$

$\lambda_i^{\ast}$ が大きい制約は、少しゆるめると最適値が大きく改善し、少し厳しくすると大きく悪化する。 $\lambda_i^{\ast} = 0$ の制約は（微分可能なら）1 次の範囲では最適値に影響しない。例 4.8 では $\lambda^{\ast} = (2, 2, 0)$ で、実際、第 1 制約を $x_1 + x_2 \leq 2 + u$ とすると最適解は $(1 + u, 1)$ 、最適値は $(u - 1)^2 + 4$ で、 $u = 0$ での微分は $-2 = -\lambda_1^{\ast}$ である。線形計画では $p^{\ast}$ は区分的に一次で、退化すると微分可能でないことがある（第3章 3.8 節のシャドウプライスの注意）。そのときは 1 の不等式だけが成り立つ。

4.7 応用例

ポートフォリオ最適化

例 4.1 の 3 資産で、目標の期待収益率 $r$ を達成しつつ分散を最小にする（第1章例 1.4 の平均分散モデル）。まず空売りを許し、 $\mu^{\top}w = r$ , $\mathbf{1}^{\top}w = 1$ のもとで $w^{\top}\Sigma w$ を最小化する。ラグランジュの条件 $2\Sigma w = \gamma\mu + \delta\mathbf{1}$ と 2 つの制約から $\gamma, \delta$ を求めると、 $A = \mathbf{1}^{\top}\Sigma^{-1}\mathbf{1}$ , $B = \mathbf{1}^{\top}\Sigma^{-1}\mu$ , $C = \mu^{\top}\Sigma^{-1}\mu$ , $\Delta = AC - B^2$ として

\gamma = \frac{2(Ar - B)}{\Delta}, \qquad \delta = \frac{2(C - Br)}{\Delta}, \qquad \sigma^2(r) := \min w^{\top}\Sigma w = \frac{1}{2}(\gamma r + \delta) = \frac{Ar^2 - 2Br + C}{\Delta}

となる（ $\Delta > 0$ は $\Sigma^{-1}$ の定める内積でのコーシー–シュワルツの不等式による。 $\mu$ が $\mathbf{1}$ の定数倍でないことを仮定する）。最小性は例 4.1 と同じ議論か、定理 4.7 で確かめられる。この例では

\sigma^2(r) = \frac{1705r^2 - 18020r + 58660}{144}, \qquad w(r) = \left(\frac{83}{48} - \frac{19r}{96},\ \frac{r}{16} - \frac{1}{8},\ \frac{13r}{96} - \frac{29}{48}\right)

で、たとえば $r = 8$ % では $w = (7/48, 3/8, 23/48)$ 、分散 $5905/36 \approx 164.0$ （標準偏差約 $12.8$ %）である（sympy で厳密に計算した）。 $\frac{d\sigma^2}{dr} = \frac{2(Ar - B)}{\Delta} = \gamma$ であり、乗数 $\gamma$ は目標収益率を上げたときの最小分散の増加率を表す（定理 4.18 の 2 にあたる。 $r = 8$ では $\gamma = 2315/36 \approx 64.3$ ）。

$w_1(r) = \frac{83}{48} - \frac{19r}{96}$ は $r > 166/19 \approx 8.74$ で負になる。つまり高い収益率を狙うと資産 1 を空売りすることになる。空売りを禁じて $w \geq 0$ を加え、収益の制約を $r - \mu^{\top}w \leq 0$ として $r = 9$ で解く。資産 1 を使わない（ $w_1 = 0$ が有効）と仮定すると、 $w_2 + w_3 = 1$ , $7w_2 + 10w_3 = 9$ から $w = (0, 1/3, 2/3)$ 、分散 $2185/9 \approx 242.8$ である。ラグランジュ関数 $w^{\top}\Sigma w + \gamma(r - \mu^{\top}w) + \delta(\mathbf{1}^{\top}w - 1) - \lambda^{\top}w$ の停留性 $2\Sigma w - \gamma\mu + \delta\mathbf{1} - \lambda = 0$ に $2\Sigma w = (140/3, 270, 1780/3)$ を入れ、 $\lambda_2 = \lambda_3 = 0$ として解くと $\gamma = 970/9$ , $\delta = 4360/9$ , $\lambda_1 = 100$ を得る。 $\gamma \geq 0$ , $\lambda \geq 0$ で相補性も成り立つので KKT 点であり、凸問題だから最適である（定理 4.7）。 $\lambda_1 = 100 > 0$ は空売りの禁止が効いていることを、 $\gamma = 970/9 \approx 107.8$ は $r = 9$ での最小分散の増加率を表す（目標収益率を $0.1$ % 上げると、最小分散は約 $10.8$ 増える）。実際、同じ計算を $r$ のまま行うと $\lambda_1 = 380r - 3320$ で、 $166/19 \leq r \leq 10$ では最適解は $w = (0, (10 - r)/3, (r - 7)/3)$ 、最小分散は $(445r^2 - 7040r + 29500)/9$ であり、その $r = 9$ での微分は $970/9$ である（sympy と数値最適化で確かめた）。

ヒント

実務では 平均分散最適化は $\mu$ と $\Sigma$ の推定値に敏感である。 $\Sigma$ の固有値に 0 に近いものがあると $\Sigma^{-1}$ が大きく変動し、推定誤差のわずかな違いで極端な配分（大きな空売りなど）が出やすい。実際の運用では、空売り禁止や銘柄ごとの上限といった制約を加えて極端な配分を抑えることが多い。そのとき乗数 $\lambda_i$ は「その制約がどれだけ分散を押し上げているか」を示すので、制約の見直しの判断材料になる。

サポートベクターマシンの双対問題

ラベル $y_i \in \lbrace 1, -1 \rbrace$ のついたデータ $x_i \in \mathbb{R}^n$ （ $i = 1, \dots, N$ 。両方のラベルがあるとする）を超平面 $w^{\top}x + b = 0$ で分ける。ハードマージン SVM は

\text{minimize} \quad \frac{1}{2}\lVert w \rVert^2 \qquad \text{subject to} \quad y_i(w^{\top}x_i + b) \geq 1 \quad (i = 1, \dots, N)

である（各点と超平面の距離が $1/\lVert w \rVert$ 以上になるので、 $\lVert w \rVert$ の最小化は余裕（マージン）の最大化を意味する。詳しくは 24 機械学習の数理第4章で扱う）。データが超平面で狭義に分離できれば（すべての $i$ で $y_i(w^{\top}x_i + b) > 0$ となる $(w, b)$ があれば）、それを定数倍して実行可能解が得られ、さらに 2 倍すれば制約を真に満たすのでスレーター条件が成り立つ。また、正のラベルの点 $x_i$ と負のラベルの点 $x_j$ について $1 - w^{\top}x_i \leq b \leq -1 - w^{\top}x_j$ なので、 $\frac{1}{2}\lVert w \rVert^2$ が一定値以下の実行可能解は有界閉集合をなし、最適解が存在する（第1章のワイエルシュトラスの定理、定理 1.9）。

ラグランジュ関数は $L = \frac{1}{2}\lVert w \rVert^2 + \sum_i \alpha_i(1 - y_i(w^{\top}x_i + b))$ （ $\alpha \geq 0$ ）である。 $b$ についての下限は $\sum_i \alpha_iy_i = 0$ でなければ $-\infty$ 、 $w$ については $w = \sum_i \alpha_iy_ix_i$ で最小になる。代入すると双対問題は

\text{maximize} \quad \sum_{i=1}^{N}\alpha_i - \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jx_i^{\top}x_j \qquad \text{subject to} \quad \alpha \geq 0, \quad \sum_{i=1}^{N}\alpha_iy_i = 0

となる。定理 4.15 より双対ギャップは $0$ で双対問題は最適解 $\alpha^{\ast}$ をもち、命題 4.14 より主問題の最適解 $(w^{\ast}, b^{\ast})$ は $L(\cdot, \alpha^{\ast})$ を最小にするので $w^{\ast} = \sum_i \alpha_i^{\ast}y_ix_i$ 、相補性より $\alpha_i^{\ast} > 0$ なら $y_i(w^{\ast\top}x_i + b^{\ast}) = 1$ である。このような $x_i$ をサポートベクトルという。分類器はサポートベクトルだけで決まり、双対問題はデータを内積 $x_i^{\top}x_j$ だけを通して含む（カーネル法への入口）。

例 4.19 正のラベルの点 $(2, 2), (2, 3), (3, 3)$ と負のラベルの点 $(0, 0), (1, 0), (0, 1)$ では、 $(2, 2)$ に $\alpha = 4/9$ 、 $(1, 0)$ と $(0, 1)$ に $\alpha = 2/9$ 、他に $0$ を与えると、 $\sum_i \alpha_iy_i = 4/9 - 2/9 - 2/9 = 0$ で、 $w = \frac{4}{9}(2, 2) - \frac{2}{9}(1, 0) - \frac{2}{9}(0, 1) = (2/3, 2/3)$ 、 $b = 1 - w^{\top}(2, 2) = -5/3$ 。各点の $y_i(w^{\top}x_i + b)$ は順に $1, 5/3, 7/3, 5/3, 1, 1$ で、実行可能性と相補性が成り立つ。KKT 条件を満たすので最適であり（定理 4.7）、分離する直線は $x_1 + x_2 = 5/2$ 、マージンは $1/\lVert w \rVert = 3/(2\sqrt{2}) \approx 1.06$ 。双対の値 $\sum_i \alpha_i - \frac{1}{2}\lVert w \rVert^2 = 8/9 - 4/9 = 4/9$ は主問題の値 $\frac{1}{2}\lVert w \rVert^2 = 4/9$ に等しい（数値最適化でも確かめた）。

分離できないデータには、はみ出しを許す変数 $\xi_i \geq 0$ を入れたソフトマージン SVM「minimize $\frac{1}{2}\lVert w \rVert^2 + C\sum_i \xi_i$ subject to $y_i(w^{\top}x_i + b) \geq 1 - \xi_i$ , $\xi_i \geq 0$ 」（ $C > 0$ ）を使う。 $\xi_i \geq 0$ の乗数を $\beta_i$ とすると、ラグランジュ関数の $\xi_i$ の係数 $C - \alpha_i - \beta_i$ が $0$ でなければ下限は $-\infty$ なので、双対問題は目的関数がハードマージンと同じで、制約が $\sum_i \alpha_iy_i = 0$ , $0 \leq \alpha_i \leq C$ （ $\beta_i = C - \alpha_i \geq 0$ ）になる。この問題は常にスレーター条件を満たし（ $\xi_i$ を大きくとればよい）、ハードマージンと同じ議論（ $\xi_i$ も目的関数で抑えられる）で主問題の最適解も存在する。相補性 $\beta_i\xi_i = 0$ と $\alpha_i(1 - \xi_i - y_i(w^{\top}x_i + b)) = 0$ から、 $\alpha_i = 0$ の点はマージンの外側（ $y_i(w^{\top}x_i + b) \geq 1$ ）、 $0 < \alpha_i < C$ の点はちょうどマージン上、 $\alpha_i = C$ の点はマージンの内側にはみ出しうる点である。

水の注入（water-filling）

$n$ 本の通信路（周波数帯など）に合計 $P > 0$ の送信電力を配分する。通信路 $i$ の雑音の大きさを $a_i > 0$ 、配分する電力を $x_i$ とすると、ガウス雑音の通信路で送れる情報量は $\log(1 + x_i/a_i)$ に比例する。そこで

\text{maximize} \quad \sum_{i=1}^{n}\log(a_i + x_i) \qquad \text{subject to} \quad x \geq 0, \quad \mathbf{1}^{\top}x = P

を考える（ $\sum_i \log a_i$ だけ違う）。最小化 $f(x) = -\sum_i \log(a_i + x_i)$ に直すと、 $f$ は開凸集合 $D = \lbrace x \mid x_i > -a_i \rbrace$ 上の狭義凸関数で、制約は一次式である。実行可能領域はコンパクトなので最適解が存在し、命題 4.5 と定理 4.7 より、最適解は KKT 条件の解と一致する。KKT 条件は、 $\lambda \geq 0$ , $\nu$ について

-\frac{1}{a_i + x_i} - \lambda_i + \nu = 0, \qquad \lambda_ix_i = 0, \qquad x \geq 0, \qquad \mathbf{1}^{\top}x = P

である。 $\nu = \frac{1}{a_i + x_i} + \lambda_i > 0$ なので $\theta = 1/\nu$ とおく。 $x_i > 0$ なら $\lambda_i = 0$ で $x_i = \theta - a_i$ （ $\theta > a_i$ ）、 $x_i = 0$ なら $\lambda_i = \nu - 1/a_i \geq 0$ すなわち $\theta \leq a_i$ 。合わせると

x_i = \max(\theta - a_i,\ 0), \qquad \sum_{i=1}^{n}\max(\theta - a_i,\ 0) = P

左辺の和は $\theta$ の連続関数で、 $\theta \leq \min_i a_i$ で $0$ 、そこから先は狭義単調増加で $\infty$ に発散するので、条件を満たす $\theta$ はただ一つ定まる。逆にこの $x$ は $\lambda_i = \nu - 1/(a_i + x_i) \geq 0$ とともに KKT 条件を満たす。底の高さが $a_i$ の容器に体積 $P$ の水を注ぐと水位が $\theta$ になる、という図式から water-filling（注水定理）とよばれる。雑音の大きい通信路（ $a_i \geq \theta$ ）には電力を配らない。

例 4.20 $a = (0.5, 1, 1.5, 3)$ , $P = 2$ とする。3 本に配ると仮定すると $3\theta - 3 = 2$ で $\theta = 5/3$ で、 $1.5 < 5/3 < 3$ なので仮定と整合する。最適解は $x = (7/6, 2/3, 1/6, 0)$ 、 $\nu = 3/5$ 、 $\lambda_4 = 3/5 - 1/3 = 4/15$ 、最適値は $3\log(5/3) + \log 3 \approx 2.631$ である。 $\nu$ は等式制約 $\mathbf{1}^{\top}x - P = 0$ の乗数なので、定理 4.18（スレーター条件は $x_i = P/n$ で成り立つ）より、総電力を増やしたときの最適値の増加率は $\nu = 1/\theta = 0.6$ である（ $P$ の近くでは 3 本に配る形が変わらず $\theta = (P + 3)/3$ なので、最適値 $3\log\theta + \log 3$ を $P$ で直接微分しても $1/\theta$ を得る）。電力を受け取るどの通信路でも限界的な増加 $1/(a_i + x_i)$ が $1/\theta$ にそろっている。次のコードは水位を二分法で求める。

import numpy as np

def water_filling(a, P, iters=100):
    lo, hi = a.min(), a.min() + P   # 水位 theta はこの区間にある
    for _ in range(iters):
        theta = (lo + hi) / 2
        if np.maximum(theta - a, 0).sum() > P:
            hi = theta
        else:
            lo = theta
    return np.maximum(theta - a, 0), theta

a = np.array([0.5, 1.0, 1.5, 3.0])
x, theta = water_filling(a, 2.0)
print(x.round(6), round(theta, 6), np.log(a + x).sum().round(6))

[1.166667 0.666667 0.166667 0.      ] 1.666667 2.631089

（ $\theta = \min_i a_i + P$ では最小の $a_i$ の項だけで和が $P$ 以上になるので、水位はこの区間にある。総電力を少し変えて最適値の差分をとると、増加率が $0.6$ になることも確かめられる。）

まとめ

等式制約の最適解では、勾配が一次独立なら $\nabla f + \sum_j \nu_j\nabla h_j = 0$ （ラグランジュの未定乗数法）。
不等式制約を含む問題の最適解では、LICQ などの制約想定のもとで KKT 条件（停留性・主実行可能性・双対実行可能性 $\lambda \geq 0$ ・相補性 $\lambda_ig_i = 0$ ）が成り立つ。証明は陰関数定理で実行可能な曲線を作り、ファルカスの補題を使う。制約が一次式なら制約想定は要らない。
制約想定がないと、最適解でも KKT 条件が成り立たないことがある。凸でない問題では、KKT 点が最適とは限らない。
凸問題（ $f, g_i$ 凸、 $h_j$ 一次）では KKT 条件は十分条件である。
双対関数 $q(\lambda, \nu) = \inf_x L(x, \lambda, \nu)$ は常に凹で、弱双対性 $d^{\ast} \leq p^{\ast}$ が成り立つ。 $f(x^{\ast}) = q(\lambda^{\ast}, \nu^{\ast})$ は両方の最適性の証明書である。
凸問題でスレーター条件が成り立てば双対ギャップは $0$ で、双対問題は最適解をもつ（分離定理による）。スレーター条件がないとギャップが生じうる。
最適な乗数は感度を表す： $\lambda_i^{\ast} = -\partial p^{\ast}/\partial u_i$ （微分可能なとき）。
応用：二次計画は有効制約を仮定して解ける。平均分散モデルの乗数は収益率と分散の交換比率、SVM の双対はサポートベクトルとカーネル法、water-filling の乗数は水位の逆数を与える。

演習問題

問題 4.1 ★ KKT 条件を使って、 $x_1 + x_2 \leq 2$ , $x_1 \geq 0$ , $x_2 \geq 0$ のもとで $(x_1 - 1)^2 + (x_2 - 2)^2$ を最小化せよ。

解答

点 $(1, 2)$ は $x_1 + x_2 \leq 2$ を破るので、第 1 制約だけが有効と仮定する。 $x_1 + x_2 = 2$ と停留性 $2(x_1 - 1) + \lambda_1 = 0$ , $2(x_2 - 2) + \lambda_1 = 0$ から $x_1 - 1 = x_2 - 2$ 、よって $x = (1/2, 3/2)$ , $\lambda_1 = 1 \geq 0$ 。 $x_1, x_2 > 0$ なので非負制約は有効でなく、その乗数は $0$ 。KKT 条件を満たし、凸問題なので（定理 4.7）最適解は $(1/2, 3/2)$ 、最適値は $1/2$ である。

問題 4.2 ★ $x_1 + x_2 \geq 1$ のもとで $x_1^2 + x_2^2$ を最小化する問題の双対関数 $q(\lambda)$ を求め、双対問題を解いて双対ギャップが $0$ であることを確かめよ。また乗数の意味を定理 4.18 で説明せよ。

解答

$g(x) = 1 - x_1 - x_2$ として $L = x_1^2 + x_2^2 + \lambda(1 - x_1 - x_2)$ 。 $x_i = \lambda/2$ で最小になり、 $q(\lambda) = \lambda - \lambda^2/2$ 。 $\lambda \geq 0$ での最大は $\lambda^{\ast} = 1$ で $d^{\ast} = 1/2$ 。主問題の最適解は $(1/2, 1/2)$ で $p^{\ast} = 1/2$ （スレーター条件は $x = (1, 1)$ で成り立つ）。制約を $x_1 + x_2 \geq 1 - u$ とゆるめると $p^{\ast}(u) = (1 - u)^2/2$ で、 $\frac{dp^{\ast}}{du}(0) = -1 = -\lambda^{\ast}$ 。右辺を 1 から少し上げると、最適値は 1 単位あたり約 $\lambda^{\ast} = 1$ 増える。

問題 4.3 ★★ $(x_1 - 1)^2 + x_2^2 \leq 1$ , $(x_1 + 1)^2 + x_2^2 \leq 1$ のもとで $x_1 + x_2$ を最小化する。(1) 最適解を求め、そこで LICQ もスレーター条件も成り立たず、KKT 条件を満たす乗数が存在しないことを示せ。(2) 双対関数を求め、 $d^{\ast} = p^{\ast}$ だが双対問題の最大値は達成されないことを示せ。

解答

(1) 2 つの閉円板は原点だけを共有するので、実行可能解は $x^{\ast} = (0, 0)$ だけで $p^{\ast} = 0$ 。 $\nabla g_1(0) = (-2, 0)$ , $\nabla g_2(0) = (2, 0)$ は一次従属で LICQ は成り立たず、 $g_1, g_2 < 0$ となる点もない。停留性 $(1, 1) + \lambda_1(-2, 0) + \lambda_2(2, 0) = 0$ の第 2 成分は $1 = 0$ となり、乗数は存在しない。

(2) $g_1 = x_1^2 - 2x_1 + x_2^2$ , $g_2 = x_1^2 + 2x_1 + x_2^2$ なので、 $s = \lambda_1 + \lambda_2 > 0$ のとき $L = s(x_1^2 + x_2^2) + (1 + 2\lambda_2 - 2\lambda_1)x_1 + x_2$ を平方完成して

q(\lambda) = -\frac{(1 + 2\lambda_2 - 2\lambda_1)^2 + 1}{4s} < 0

（ $s = 0$ なら $q = \inf(x_1 + x_2) = -\infty$ ）。 $\lambda_1 = \lambda_2 + 1/2$ として $\lambda_2 \to \infty$ とすると $q = -1/(4s) \to 0$ なので $d^{\ast} = 0 = p^{\ast}$ だが、 $q < 0$ なので最大値は達成されない。スレーター条件がないと、ギャップが $0$ でも双対問題が最適解をもたないことがある。

問題 4.4 ★★ $x_1^2 + x_2^2 \leq 1$ のもとで $x_1^2 - x_2^2$ を最小化する。ある分析者は「原点 $(0, 0)$ は $\lambda = 0$ で KKT 条件を満たすので最適解である」と結論した。この結論は正しいか。KKT 点をすべて求めて答えよ。

解答

正しくない。停留性は $2x_1 + 2\lambda x_1 = 0$ , $-2x_2 + 2\lambda x_2 = 0$ 。 $\lambda \geq 0$ より $1 + \lambda > 0$ なので $x_1 = 0$ 。 $x_2 = 0$ なら制約は有効でなく $\lambda = 0$ ：原点（値 $0$ ）。 $x_2 \neq 0$ なら $\lambda = 1 > 0$ で、相補性から $x_1^2 + x_2^2 = 1$ 、すなわち $(0, \pm 1)$ （値 $-1$ ）。実行可能領域はコンパクトなので最小値が存在し、境界では $\nabla g = 2x \neq 0$ 、内部では有効制約がないので、どの実行可能解でも LICQ が成り立つ。よって最小点は KKT 点のどれかで（定理 4.4）、値を比べると最小値は $-1$ 、最適解は $(0, \pm 1)$ 。原点は $f(0, t) = -t^2 < 0$ となる鞍点である。問題が凸でないので、KKT 条件は十分条件ではない。

問題 4.5 ★★（確率単体への射影） $a \in \mathbb{R}^n$ に対し、 $\mathbf{1}^{\top}x = 1$ , $x \geq 0$ のもとで $\frac{1}{2}\lVert x - a \rVert^2$ を最小にする $x$ は、ある $\tau \in \mathbb{R}$ について $x_i = \max(a_i - \tau, 0)$ と書けることを KKT 条件から示せ。 $a = (0.9, 0.5, -0.2)$ のときの $x$ と $\tau$ を求めよ。

解答

狭義凸関数を空でないコンパクト凸集合上で最小化するので最適解がただ一つあり、制約は一次式なので KKT 条件と同値である（命題 4.5、定理 4.7）。停留性は $x_i - a_i - \lambda_i + \tau = 0$ （ $\tau$ は等式制約の乗数）。 $x_i > 0$ なら $\lambda_i = 0$ で $x_i = a_i - \tau$ 。 $x_i = 0$ なら $\lambda_i = \tau - a_i \geq 0$ 、すなわち $a_i \leq \tau$ 。合わせて $x_i = \max(a_i - \tau, 0)$ 。 $\tau$ は $\sum_i \max(a_i - \tau, 0) = 1$ で決まる（左辺は $\tau$ について連続で、正の範囲では狭義単調減少）。 $a = (0.9, 0.5, -0.2)$ では、最初の 2 成分が正と仮定すると $(0.9 - \tau) + (0.5 - \tau) = 1$ より $\tau = 0.2$ 。 $0.5 - 0.2 > 0$ , $-0.2 - 0.2 < 0$ と整合し、 $x = (0.7, 0.3, 0)$ 、 $\lambda_3 = 0.4$ （計算機でも確かめた）。water-filling と同じ形の解である。

問題 4.6 ★★ $A$ を $n$ 次実対称行列とし、 $\lVert x \rVert^2 = 1$ のもとで $x^{\top}Ax$ を最小化する（凸でない問題である）。ラグランジュ双対問題の最適値が $A$ の最小固有値 $\lambda_{\min}$ に等しく、双対ギャップが $0$ であることを示せ。 $A$ の行が $(2, 1)$ , $(1, 2)$ のとき最適解を求めよ。

解答

$h(x) = x^{\top}x - 1$ として $L = x^{\top}(A + \nu I)x - \nu$ 。 $A + \nu I$ が半正定値なら $x = 0$ で下限 $-\nu$ をとり、負の固有値をもてばその固有ベクトルの方向で $-\infty$ になる。 $A + \nu I$ の固有値は $A$ の固有値 $+ \nu$ なので、 $q(\nu) = -\nu$ （ $\nu \geq -\lambda_{\min}$ ）、 $-\infty$ （それ以外）。よって $d^{\ast} = \lambda_{\min}$ 。一方 $p^{\ast} = \min_{\lVert x \rVert = 1}x^{\top}Ax = \lambda_{\min}$ （02-linear-algebra 第8章命題 8.29）なので、ギャップは $0$ である。凸でない問題でもギャップが $0$ になることはある。例の $A$ の固有値は $1, 3$ で、最適解は固有値 1 の単位固有ベクトル $\pm(1, -1)/\sqrt{2}$ 、最適値は $1$ 。

問題 4.7 ★★（ラグランジュ緩和） $x \in \lbrace 0, 1 \rbrace^2$ 、 $2x_1 + 2x_2 \leq 3$ のもとで $-x_1 - x_2$ を最小化する。不等式制約だけを双対化し（ $D = \lbrace 0, 1 \rbrace^2$ ）、双対関数と $d^{\ast}$ を求めて、双対ギャップが正であることを示せ。

解答

実行可能解は $(0, 0), (1, 0), (0, 1)$ で $p^{\ast} = -1$ 。 $L = (2\lambda - 1)(x_1 + x_2) - 3\lambda$ を $D$ 上で最小にすると、 $2\lambda - 1 \geq 0$ なら $x = (0, 0)$ で $-3\lambda$ 、 $2\lambda - 1 < 0$ なら $x = (1, 1)$ で $\lambda - 2$ 。よって $q(\lambda) = \lambda - 2$ （ $0 \leq \lambda \leq 1/2$ ）、 $-3\lambda$ （ $\lambda \geq 1/2$ ）で、最大値は $d^{\ast} = q(1/2) = -3/2$ 。双対ギャップは $1/2 > 0$ である。 $D$ が凸でないので定理 4.15 は使えない。それでも $d^{\ast}$ は $p^{\ast}$ の下界として、整数計画の分枝限定法（第7章）で使われる（この例では $x \in [0, 1]^2$ にゆるめた線形計画の最適値 $-3/2$ と一致する）。

問題 4.8 ★★ ある二次計画の実装は、有効制約の組を一つずつ試し、等式として解いた点が実行可能なら、それを最適解として返す（乗数の符号は調べない）。例 4.8 で、この実装が第 2, 3 制約の組を最初に試すとどうなるか。どこが危ないかを説明せよ。

解答

例 4.8 の表のとおり、第 2, 3 制約を等式とした点は $x = (0, 1)$ で、 $x_1 + x_2 = 1 \leq 2$ なので実行可能である。この実装は値 $(0 - 2)^2 + (1 - 3)^2 = 8$ の点を返すが、最適値は $5$ （ $x = (1, 1)$ ）である。この点の乗数は $\lambda_3 = -4 < 0$ で、双対実行可能性を破っている。負の乗数は、その制約を等号に保つのをやめて内側に入ると目的関数が下がることを意味する。実際 $x = (t, 1)$ （ $0 < t \leq 1$ ）は実行可能で、 $f = (t - 2)^2 + 4$ は $t = 0$ で傾き $-4$ で減少している。つまり $x_1 \geq 0$ を有効にしておく理由がない。KKT 条件の 4 つ（とくに $\lambda \geq 0$ ）をすべて確かめてはじめて、凸問題での最適性が保証される（定理 4.7）。