第1章最適化問題とは

この章の目標

• 生産計画・輸送・ポートフォリオ・最小二乗・ロジスティック回帰・最短路を、決定変数・目的関数・制約の形に定式化できる
• 最適値と最適解を区別し、最適値が有限でも最適解が存在しない例を挙げられる
• ワイエルシュトラスの定理と強圧性から最小点の存在を証明し、連続性・閉集合・強圧性の仮定が外れると何が起こるかを説明できる
• 局所最適と大域最適を区別し、制約なし問題の 1 次・2 次の必要条件と 2 次の十分条件を証明して使える（半正定値と正定値の違いを含めて）
• 凸性が「局所最適なら大域最適」を保証することを知り、問題が凸かどうかを見分けられる

前提：01-calculus 第7章（勾配・ヘッセ行列・テイラーの定理・コンパクト集合）、02-linear-algebra 第8章（正定値性）。例 1.5・例 1.22 では 02-linear-algebra 第7章 の最小二乗法を使う。コンパクト性の一般論は 03-topology 第5章 にある。

利益を最大にするには、2 種類の製品をそれぞれ何個作ればよいか。輸送費を最小にするには、どの倉庫からどの店舗へどれだけ運べばよいか。「この顧客は買うか」を予測するモデルの係数は、どう決めればよいか。見かけは違うが、これらはすべて「制約 $x \in X$ のもとで、目的関数 $f(x)$ を最小（または最大）にする $x$ を求めよ」という形に書ける。このような問題を最適化問題 (optimization problem) という。

数学が答えるべき問いは、(1) 最良の選択は存在するか、(2) 候補が最良であることをどう確かめるか、(3) どう計算するか、の三つである。本章では定式化と (1)・(2) の基本を扱う。(3) は第3章・第5章〜第7章、(2) を強める双対性は第3章・第4章で扱う。一般には、近くのどの点よりもよい点（局所最適解）が全体で最良（大域最適解）とは限らない。この溝を埋める性質が凸性で、第2章以降の中心になる。

ベクトルは縦ベクトルとし、転置を $A^{\top}$ で表す（02-linear-algebra の ${}^tA$ と同じ）。$\langle x, y \rangle = x^{\top}y$ は標準内積、$\lVert x \rVert$ はユークリッドノルムで、$x \geq 0$ は各成分が $0$ 以上であることを表す。

1.1 最適化問題の形

定義 1.1（最適化問題）集合 $X \subset \mathbb{R}^n$ と関数 $f\colon X \to \mathbb{R}$ について、$f$ を $X$ 上で最小にする問題を

$$\text{minimize} \quad f(x) \qquad \text{subject to} \quad x \in X$$

と書く。$x$ を決定変数 (decision variable)、$f$ を目的関数 (objective function)、$X$ を実行可能領域 (feasible region)、$X$ の元を実行可能解 (feasible solution) という。$p^{\ast} = \inf_{x \in X} f(x) \in [-\infty, +\infty]$ を最適値 (optimal value) といい（$X = \emptyset$ なら $p^{\ast} = +\infty$ とする）、$f(x^{\ast}) = p^{\ast}$ となる $x^{\ast} \in X$ を最適解 (optimal solution) または大域最小点という。最適解の全体を $\operatorname{argmin}_{x \in X} f(x)$ と書く。$X = \emptyset$ のとき実行不能 (infeasible)、$p^{\ast} = -\infty$ のとき非有界 (unbounded) であるという。

subject to（s.t.）は「という条件のもとで」の意味である。$X$ は多くの場合、不等式制約 $g_i(x) \leq 0$ と等式制約 $h_j(x) = 0$ で与えられる。$X = \mathbb{R}^n$（または開集合）のとき制約なし問題 (unconstrained problem) という。最大化は $-f$ の最小化として扱う。最適値は常に定まるが、最適解は存在するとは限らない（$X = \mathbb{R}$, $f(x) = e^{x}$ なら $p^{\ast} = 0$ だが、$e^{x} = 0$ となる $x$ はない）。

1.2 定式化の例

定式化とは、現実の問題から「何を決めるか（決定変数）」「何をよくしたいか（目的関数）」「何を守るべきか（制約）」を取り出して式にすることである。

例 1.2（生産計画）製品 A, B の 1 個あたりの利益は 4 万円、3 万円である。A を 1 個作るには機械 2 時間・作業員 1 時間、B には機械 1 時間・作業員 3 時間が必要で、1 日に使えるのは機械 10 時間、作業員 15 時間までとする。1 日の生産量を $x_1, x_2$（分割できる量とみなす）とすると

である。目的関数も制約も一次式なので線形計画問題 (linear programming problem, LP) という。実行可能領域は頂点 $(0, 0)$, $(5, 0)$, $(3, 4)$, $(0, 5)$ の四角形で、頂点での値は $0, 20, 24, 15$ である。$(3, 4)$ が最適であることは、次のように確かめられる：任意の実行可能解について

で、$(3, 4)$ で等号が成り立つ。係数 $9/5$, $2/5$ は「機械・作業員の時間を 1 時間増やすと、（変化が小さい範囲で）最大利益がいくら増えるか」を表す。このような最適性の証明書を体系的に作るのが第3章の双対問題であり、係数はシャドウプライスと呼ばれる。

例 1.3（輸送問題）倉庫 $i = 1, \dots, m$ の在庫を $s_i$、店舗 $j = 1, \dots, n$ の需要を $d_j$、倉庫 $i$ から店舗 $j$ への 1 単位あたりの輸送費を $c_{ij}$ とする。輸送量 $x_{ij}$ を決定変数として

これも線形計画問題である。制約を足し合わせると $\sum_j d_j = \sum_{i, j} x_{ij} \leq \sum_i s_i$ なので、全需要が全在庫を超えると実行不能になる。

例 1.4（ポートフォリオ選択）$n$ 個の資産の収益率を確率変数 $R_1, \dots, R_n$、期待値を $\mu_i = E[R_i]$、共分散行列を $\Sigma = (\operatorname{Cov}(R_i, R_j))_{i, j}$ とする。資金の配分の割合を $w \in \mathbb{R}^n$ とすると、ポートフォリオの収益率 $w^{\top}R$ の期待値は $\mu^{\top}w$、分散は $\sum_{i, j} w_iw_j\operatorname{Cov}(R_i, R_j) = w^{\top}\Sigma w$ である。目標の期待収益率 $r$ を確保しつつ分散を最小にする問題

を平均分散モデル (mean-variance model) という（マーコウィッツ, 1952 年）。目的関数が二次式で制約が一次式の問題を二次計画問題 (quadratic programming problem) という。$w \geq 0$ は空売りの禁止で、外すと答えが変わる（問題 1.6）。分散は負にならないので $\Sigma$ は半正定値であり、第2章で見るように、このことがこの問題を「解きやすく」している。

例 1.5（最小二乗法）データ $(a_i, b_i)$（$a_i \in \mathbb{R}^n$, $b_i \in \mathbb{R}$, $i = 1, \dots, m$）に線形モデル $b \approx a^{\top}x$ をあてはめる。$a_i^{\top}$ を第 $i$ 行とする行列を $A$ とすると、問題は制約なし問題

である。02-linear-algebra 第7章 の定理 7.19 では、解が正規方程式 $A^{\top}Ax = A^{\top}b$ の解であることを射影の幾何で示した。例 1.22 で最適性条件の立場から見直す。

例 1.6（ロジスティック回帰）特徴量 $a_i \in \mathbb{R}^n$ とラベル $y_i \in \lbrace 0, 1 \rbrace$（購入したかどうか、など）の組が $m$ 個ある。シグモイド関数 $\sigma(t) = 1/(1 + e^{-t})$ により「$y = 1$ となる確率は $\sigma(a^{\top}x)$」というモデルを立て、パラメータ $x$ を最尤法で決める。負の対数尤度 $-\sum_i \bigl(y_i\log\sigma(a_i^{\top}x) + (1 - y_i)\log(1 - \sigma(a_i^{\top}x))\bigr)$ は、$\log\sigma(t) = t - \log(1 + e^{t})$, $\log(1 - \sigma(t)) = -\log(1 + e^{t})$ を使って整理すると

となり、これを $x \in \mathbb{R}^n$ で最小化する。解の公式はなく、第5章・第6章の反復法で解く。

例 1.7（最短路問題）道路網を有向グラフ $G = (V, E)$ で表し、道路 $e$ の所要時間を $c_e \geq 0$ とする。地点 $s$ から $t$（$\neq s$）への経路で所要時間の和が最小のものを求める問題を最短路問題 (shortest path problem) という。道路 $e$ を使うとき $x_e = 1$、使わないとき $x_e = 0$ とし、$v$ から出る道路・$v$ に入る道路の集合を $\delta^{+}(v)$, $\delta^{-}(v)$ とすると

と書ける（実行可能解は経路に閉路が付いたものでもありうるが、$c_e \geq 0$ なので閉路を除いても費用は増えない）。変数が $0$ か $1$ に限られる問題を 0-1 整数計画問題という。実行可能解は有限個なので最小値は存在する（空でなければ）が、経路の数は指数関数的に増えうるので全部は調べられない。第7章でダイクストラ法を扱う。

1.3 最小値の存在

最適解が存在しない問題に反復法を適用すると、答えらしきものが出力されても意味をもたない。

例 1.8（最適解が存在しない例）

1. $X = \mathbb{R}$, $f(x) = e^{x}$。$x \to -\infty$ で値が下限 $0$ に近づくが、達成されない。
2. $X = (0, 1]$, $f(x) = x$。値を下限 $0$ に近づける点列は $X$ の外の点 $0$ に収束する（$X$ が閉でない）。
3. $X = [0, 1]$ で、$f(0) = 1$、$0 < x \leq 1$ では $f(x) = x$。下限 $0$ は達成されない（$f$ が $0$ で連続でない）。
4. $X = \mathbb{R}^2$, $f(x, y) = (xy - 1)^2 + x^2$。$f = 0$ なら $x = 0$ かつ $xy = 1$ で矛盾するので $f > 0$ だが、$f(t, 1/t) = t^2 \to 0$（$t \to 0$）なので下限 $0$ は達成されない。

定理 1.9（ワイエルシュトラスの定理, Weierstrass theorem）$K \subset \mathbb{R}^n$ を空でないコンパクト集合（有界閉集合）、$f\colon K \to \mathbb{R}$ を連続関数とする。このとき $f$ は $K$ 上で最小値と最大値をとる。

証明. 最小値について示す（最大値は $-f$ に適用する）。$m = \inf_K f \in [-\infty, \infty)$ とし、$f(x_k) \to m$ となる $x_k \in K$ をとる（$m = -\infty$ なら $f(x_k) < -k$ とする）。$K$ はコンパクトなので（01-calculus 第7章 定義 7.4・定理 7.5）、部分列 $x_{k_j}$ が $K$ の点 $x^{\ast}$ に収束する。$f$ の連続性より $f(x^{\ast}) = \lim_j f(x_{k_j}) = m$。特に $m$ は有限で、$x^{\ast}$ で最小値をとる。$\square$

これは 01-calculus 第7章 定理 7.7、03-topology 第5章 系 5.9 と同じ主張である。有界でない実行可能領域（例 1.5・1.6）のために、次の条件を導入する。

定義 1.10（強圧性, coercivity）$X \subset \mathbb{R}^n$ とする。関数 $f\colon X \to \mathbb{R}$ が

$$\forall M \in \mathbb{R},\ \exists R > 0,\ \forall x \in X,\ \lVert x \rVert > R \Rightarrow f(x) > M$$

を満たす（「$x \in X$, $\lVert x \rVert \to \infty$ のとき $f(x) \to +\infty$」）とき、$f$ は $X$ 上で強圧的 (coercive) であるという。$X$ が有界ならこの条件は自動的に成り立つ。

定理 1.11（強圧的な関数の最小値の存在）$X \subset \mathbb{R}^n$ を空でない閉集合、$f\colon X \to \mathbb{R}$ を連続かつ強圧的な関数とする。このとき $f$ は $X$ 上で最小値をとる。

証明. $x_0 \in X$ をとり、下位集合 (sublevel set) $S = \lbrace x \in X \mid f(x) \leq f(x_0) \rbrace$ を考える。$x_0 \in S$ である。強圧性の定義で $M = f(x_0)$ とした $R$ をとると、$\lVert x \rVert > R$ の $x \in X$ は $f(x) > f(x_0)$ を満たすので、$S$ は半径 $R$ の閉球に含まれ、有界である。$S$ は閉集合でもある：$x_k \in S$, $x_k \to x$ なら、$X$ が閉なので $x \in X$（01-calculus 第7章 命題 7.3）、連続性から $f(x) = \lim_k f(x_k) \leq f(x_0)$。よって $S$ はコンパクトで、定理 1.9 より $f$ は $S$ 上のある点 $x^{\ast}$ で最小値をとる。$x \in X \setminus S$ なら $f(x) > f(x_0) \geq f(x^{\ast})$ なので、$x^{\ast}$ は $X$ 全体での最小点である。$\square$

例 1.8 では、1 と 4 は強圧性、2 は $X$ の閉性、3 は $f$ の連続性が欠けている。どの仮定も外せない。

例 1.12（最小二乗法の解の存在）例 1.5 で $\operatorname{rank} A = n$ なら、$x \neq 0$ で $x^{\top}A^{\top}Ax = \lVert Ax \rVert^2 > 0$ なので $A^{\top}A$ は正定値で、最小固有値を $\lambda > 0$ とすると $\lVert Ax \rVert \geq \sqrt{\lambda}\lVert x \rVert$（02-linear-algebra 第8章 命題 8.29）。よって $\lVert Ax - b \rVert \geq \sqrt{\lambda}\lVert x \rVert - \lVert b \rVert$ で、$f$ は強圧的であり最小点をもつ。$\operatorname{rank} A < n$ なら $Az = 0$ となる $z \neq 0$ の方向に $f$ は一定で強圧的でないが、それでも最小点は存在する（02-linear-algebra 第7章 定理 7.19）。強圧性は必要条件ではない。

例 1.13（ロジスティック回帰と完全分離）例 1.6 の $\ell$ の各項 $\log(1 + e^{t}) - yt$ は、$y = 1$ なら $\log(1 + e^{-t})$、$y = 0$ なら $\log(1 + e^{t})$ に等しく、正である。いま、$y_i = 1$ なら $a_i^{\top}v > 0$、$y_i = 0$ なら $a_i^{\top}v < 0$ となる $v$ がある（データが完全に分離できる）とする。$s \to \infty$ のとき $\ell(sv)$ の各項は $\log(1 + e^{-s\lvert a_i^{\top}v \rvert}) \to 0$ となるので、最適値 $0$ は達成されず、最尤推定値は存在しない（統計学の側からの扱いは 22-statistics 第6章 定理 6.11）。一方、$\lambda > 0$ について

は $\ell_{\lambda}(x) \geq \frac{\lambda}{2}\lVert x \rVert^2$ より強圧的なので、データによらず最小点をもつ（リッジ正則化、$L^2$ 正則化）。次のコードは、完全に分離できる 1 次元のデータに勾配法（第5章）を適用したものである。

import numpy as np

a = np.array([-2.0, -1.0, 1.0, 2.0])     # 特徴量
y = np.array([0.0, 0.0, 1.0, 1.0])       # ラベル（x > 0 で完全に分離できる）
obj = lambda x, lam: np.sum(np.log1p(np.exp(a * x)) - y * a * x) + lam / 2 * x**2
grad = lambda x, lam: np.sum((1 / (1 + np.exp(-a * x)) - y) * a) + lam * x

for lam in [0.0, 0.1]:
    x = 0.0
    for k in range(1, 100001):
        x -= 0.1 * grad(x, lam)          # 勾配法（学習率 0.1）
        if k in (100, 10000, 100000):
            print(f"lam={lam}: k={k:6d}  x={x:7.4f}  obj={obj(x, lam):.6f}")

lam=0.0: k=   100  x= 3.1751  obj=0.085373
lam=0.0: k= 10000  x= 7.6053  obj=0.000996
lam=0.0: k=100000  x= 9.9041  obj=0.000100
lam=0.1: k=   100  x= 2.2520  obj=0.475615
lam=0.1: k= 10000  x= 2.2772  obj=0.475503
lam=0.1: k=100000  x= 2.2772  obj=0.475503

正則化なしでは目的関数は $0$ に近づくが、$x$ は $\log k$ 程度の速さで増え続けて収束しない。$\lambda = 0.1$ では $x \approx 2.2772$ に収束する。

1.4 局所最適と大域最適

定義 1.14（局所最小点と大域最小点）$X \subset \mathbb{R}^n$、$f\colon X \to \mathbb{R}$、$x^{\ast} \in X$ とする。ある $\varepsilon > 0$ があって、$\lVert x - x^{\ast} \rVert < \varepsilon$ を満たすすべての $x \in X$ で $f(x^{\ast}) \leq f(x)$ となるとき、$x^{\ast}$ を局所最小点（局所最適解, local minimizer）という。さらに $x \neq x^{\ast}$ なら $f(x^{\ast}) < f(x)$ となるとき狭義の局所最小点という。すべての $x \in X$ で $f(x^{\ast}) \leq f(x)$ となるとき大域最小点（大域最適解, global minimizer）という。

例 1.15 $f(x) = 3x^4 - 4x^3 - 12x^2$ は $f'(x) = 12x(x + 1)(x - 2)$ より停留点 $-1, 0, 2$ をもち、そこでの $f''(x) = 36x^2 - 24x - 24$ の値は $36, -24, 72$ である。よって $x = -1, 2$ は狭義の局所最小点（$f(-1) = -5$, $f(2) = -32$）、$x = 0$ は局所最大点である。$f$ は強圧的なので最小点が存在し、それは停留点のどれか（定理 1.17）だから、大域最小点は $x = 2$ である。$x = -1$ は局所最小点だが大域最小点ではない。

勾配法（第5章）$x_{k+1} = x_k - 0.01f'(x_k)$ をこの $f$ に 200 回適用すると、$x_0 = -2, -0.5$ からは局所最小点 $-1$ に、$x_0 = 0.5, 3$ からは $2$ に収束する（計算機で確かめられる）。勾配法は近くの情報しか使わないので、局所最小点に入ると抜け出せない。

1.5 制約なし問題の最適性条件

この節では $U \subset \mathbb{R}^n$ を開集合、$f\colon U \to \mathbb{R}$ とする（実行可能領域の内点にある局所最小点にも同じ議論が使える）。ヘッセ行列を $\nabla^2 f(x) = (\partial_i\partial_j f(x))_{i, j}$ と書く（01-calculus 第7章の $H_f(x)$）。

補題 1.16（降下方向）$f$ が $x \in U$ で微分可能で、$d \in \mathbb{R}^n$ が $\langle \nabla f(x), d \rangle < 0$ を満たすならば、ある $\bar{t} > 0$ があって、$0 < t < \bar{t}$ のとき $f(x + td) < f(x)$ となる。このような $d$ を降下方向 (descent direction) という。

証明. 微分可能性より $f(x + td) = f(x) + t\langle \nabla f(x), d \rangle + o(t)$（$t \to 0$）。$c = -\langle \nabla f(x), d \rangle > 0$ とおくと、十分小さい $t > 0$ で $o(t)$ の項の絶対値は $ct/2$ 以下なので、$f(x + td) - f(x) \leq -ct/2 < 0$。$\square$

定理 1.17（1 次の必要条件）$x^{\ast} \in U$ が $f$ の局所最小点で、$f$ が $x^{\ast}$ で微分可能ならば、$\nabla f(x^{\ast}) = 0$ である。

証明. $\nabla f(x^{\ast}) \neq 0$ なら、$d = -\nabla f(x^{\ast})$ は $\langle \nabla f(x^{\ast}), d \rangle = -\lVert \nabla f(x^{\ast}) \rVert^2 < 0$ を満たすので、補題 1.16 より $x^{\ast}$ のいくらでも近くに値のより小さい点があり、局所最小性に反する。$\square$

$\nabla f(x) = 0$ となる点を停留点 (stationary point) といい、停留点のうち局所最小点でも局所最大点でもないものを鞍点 (saddle point) という。

定理 1.18（2 次の必要条件）$f$ を $U$ 上の $C^2$ 級関数とする。$x^{\ast} \in U$ が局所最小点ならば、$\nabla f(x^{\ast}) = 0$ であり、かつ $\nabla^2 f(x^{\ast})$ は半正定値である。

証明. $\nabla f(x^{\ast}) = 0$ は定理 1.17 による。$d \in \mathbb{R}^n$ を任意にとると、テイラーの定理（ペアノ剰余の形、01-calculus 第7章 7.6 節の (1) 式）より $t \to 0$ のとき

十分小さい $t \neq 0$ で左辺は $f(x^{\ast})$ 以上なので、$\frac{1}{2}d^{\top}\nabla^2 f(x^{\ast})d + o(t^2)/t^2 \geq 0$。$t \to 0$ として $d^{\top}\nabla^2 f(x^{\ast})d \geq 0$。$\square$

定理 1.19（2 次の十分条件）$f$ を $U$ 上の $C^2$ 級関数とし、$x^{\ast} \in U$ で $\nabla f(x^{\ast}) = 0$ かつ $\nabla^2 f(x^{\ast})$ が正定値であるとする。このとき $x^{\ast}$ は狭義の局所最小点である。さらに、$\nabla^2 f(x^{\ast})$ の最小固有値を $\lambda$ とすると、ある $\varepsilon > 0$ について $\lVert x - x^{\ast} \rVert < \varepsilon$ ならば $f(x) \geq f(x^{\ast}) + \frac{\lambda}{4}\lVert x - x^{\ast} \rVert^2$ である。

証明. 正定値行列の固有値は正で（02-linear-algebra 第8章 定理 8.13）、すべての $h$ で $h^{\top}\nabla^2 f(x^{\ast})h \geq \lambda\lVert h \rVert^2$（同 命題 8.29）。テイラーの定理より $f(x^{\ast} + h) = f(x^{\ast}) + \frac{1}{2}h^{\top}\nabla^2 f(x^{\ast})h + r(h)$, $r(h) = o(\lVert h \rVert^2)$ と書ける。$\lVert h \rVert < \varepsilon$ ならば $x^{\ast} + h \in U$ かつ $\lvert r(h) \rvert \leq \frac{\lambda}{4}\lVert h \rVert^2$ となる $\varepsilon > 0$ をとれば、$f(x^{\ast} + h) \geq f(x^{\ast}) + \frac{\lambda}{2}\lVert h \rVert^2 - \frac{\lambda}{4}\lVert h \rVert^2 = f(x^{\ast}) + \frac{\lambda}{4}\lVert h \rVert^2$ であり、$h \neq 0$ なら右辺は $f(x^{\ast})$ より大きい。$\square$

定理 1.19 の前半は 01-calculus 第7章 定理 7.24 (1) と同じである。必要条件は半正定値、十分条件は正定値で、その間にはすき間がある。ヘッセ行列が半正定値だが固有値に $0$ を含む停留点は、2 次までの情報では判定できない。

例 1.20（2 次の条件で判定できない例）(1) $x^4$, $x^3$, $-x^4$ はいずれも $x = 0$ で $f' = f'' = 0$ で、2 次の必要条件を満たす。しかし $x^4$ は狭義の最小、$x^3$ は極値でなく、$-x^4$ は狭義の最大である。(2) $x^2 + y^4$, $x^2 + y^3$, $x^2 - y^4$ の原点でのヘッセ行列はどれも $\operatorname{diag}(2, 0)$ だが、原点はそれぞれ狭義の最小点・鞍点・鞍点である（後の二つは $f(0, y)$ が負の値をとる）。(3) $x^4$ の原点は狭義の局所最小点だが $f'' = 0$ である。2 次の十分条件は必要条件ではない。

二次関数ではテイラー展開が 2 次で終わるので、最適性が完全に判定できる。

命題 1.21（二次関数の最小化）$Q$ を $n$ 次実対称行列、$c \in \mathbb{R}^n$、$f(x) = \frac{1}{2}x^{\top}Qx - c^{\top}x$ とする。

1. $Q$ が半正定値で $Qx^{\ast} = c$ ならば、$x^{\ast}$ は大域最小点であり、大域最小点の全体は $\lbrace x \mid Qx = c \rbrace$ である。特に $Q$ が正定値なら、大域最小点は $Q^{-1}c$ ただ一つである。
2. $Q$ が負の固有値をもつとき、または $Q$ が半正定値で $c \notin \operatorname{Im} Q$ のとき、$f$ は下に有界でない。

したがって、$f$ が最小値をもつための必要十分条件は「$Q$ が半正定値かつ $c \in \operatorname{Im} Q$」である。

証明. $Q$ の対称性を使って展開すると、任意の $x, h$ について

特に $\nabla f(x) = Qx - c$ である。(1) $Qx^{\ast} = c$ なら (1.1) より $f(x^{\ast} + h) = f(x^{\ast}) + \frac{1}{2}h^{\top}Qh \geq f(x^{\ast})$。逆に大域最小点 $x$ では定理 1.17 より $Qx - c = 0$。$Q$ が正定値なら正則である。(2) $Qv = \mu v$, $\mu < 0$, $v \neq 0$ なら $f(tv) = -tc^{\top}v + \frac{\mu t^2}{2}\lVert v \rVert^2 \to -\infty$（$t \to \infty$）。$c \notin \operatorname{Im} Q$ のとき：$Qx = 0$ なら $x^{\top}Qz = (Qx)^{\top}z = 0$ なので $\operatorname{Ker} Q \subset (\operatorname{Im} Q)^{\perp}$ で、次元を比べると等号が成り立ち、$\mathbb{R}^n = \operatorname{Im} Q \oplus \operatorname{Ker} Q$（直交直和）。$c = c_1 + c_0$（$c_1 \in \operatorname{Im} Q$, $c_0 \in \operatorname{Ker} Q$）と分けると $c_0 \neq 0$ で、$f(tc_0) = -t\lVert c_0 \rVert^2 \to -\infty$。最後の主張は (1)・(2) から従う。$\square$

例 1.22（最小二乗法、再訪）$f(x) = \lVert Ax - b \rVert^2$ は、定数項 $\lVert b \rVert^2$ を除いて $Q = 2A^{\top}A$（半正定値）、$c = 2A^{\top}b$ とした命題 1.21 の形である。$A^{\top}Ax = 0$ なら $\lVert Ax \rVert^2 = x^{\top}A^{\top}Ax = 0$ なので $\operatorname{Ker} A^{\top}A = \operatorname{Ker} A$ で、直交補空間をとると $\operatorname{Im} A^{\top}A = \operatorname{Im} A^{\top} \ni A^{\top}b$。よって最小点が存在し、その全体は正規方程式 $A^{\top}Ax = A^{\top}b$ の解全体である。02-linear-algebra 第7章 定理 7.19 を、射影を使わずに導いたことになる。

例 1.23（存在・停留点・比較）$f(x, y) = x^4 + y^4 - 4xy$ の最小値を求める。(i) $x^4 + y^4 \geq \frac{1}{2}(x^2 + y^2)^2$ と $4\lvert xy \rvert \leq 2(x^2 + y^2)$ より、$r = \lVert (x, y) \rVert$ として $f \geq \frac{r^4}{2} - 2r^2 \to \infty$。$f$ は強圧的で、最小点が存在する。(ii) 最小点は停留点である。$\nabla f = (4x^3 - 4y, 4y^3 - 4x) = 0$ より $y = x^3$, $x = y^3 = x^9$ で $x \in \lbrace 0, \pm 1 \rbrace$、停留点は $(0, 0)$, $(1, 1)$, $(-1, -1)$。(iii) $f(0, 0) = 0$, $f(\pm 1, \pm 1) = -2$（複号同順）なので、最小値は $-2$ で、最小点は 2 つある。ヘッセ行列

は $(\pm 1, \pm 1)$ で固有値 $8, 16$（正定値）、原点で $\pm 4$（不定値、鞍点）であり、定理 1.18・1.19 と整合する。「存在を示す → 停留点を列挙する → 値を比べる」手順は、停留点を列挙できない大きな問題では使えない。

1.6 凸性への導入

例 1.15 や例 1.23 では、局所的な条件だけでは大域最小点を見分けられず、すべての停留点を比べる必要があった。この困難が起こらない問題のクラスがある。

定義 1.24（凸集合・凸関数）集合 $C \subset \mathbb{R}^n$ が、任意の $x, y \in C$ と $t \in [0, 1]$ について $(1 - t)x + ty \in C$ を満たすとき、$C$ を凸集合 (convex set) という。凸集合 $C$ 上の関数 $f$ が、任意の $x, y \in C$ と $t \in [0, 1]$ について $f((1 - t)x + ty) \leq (1 - t)f(x) + tf(y)$ を満たすとき、$f$ を凸関数 (convex function) という。凸集合上で凸関数を最小化する問題を凸最適化問題 (convex optimization problem) という。

凸集合は「どの 2 点を結ぶ線分も含む」集合、凸関数は「グラフ上の 2 点を結ぶ弦がグラフより下に来ない」関数である（1 変数の場合は 01-calculus 第4章 定義 4.28）。第2章で証明するように、凸最適化問題では次が成り立つ。

• 局所最小点は大域最小点である。$f(y) < f(x^{\ast})$ となる $y$ があれば、凸性から線分上の点 $x^{\ast} + t(y - x^{\ast})$（$0 < t \leq 1$）でも値は $f(x^{\ast})$ より小さく、$t \to 0$ でそれらは $x^{\ast}$ にいくらでも近づくからである。
• 開凸集合上の微分可能な凸関数では、$\nabla f(x^{\ast}) = 0$ が大域最小の十分条件にもなる。

例 1.2〜1.6 はいずれも凸最適化問題である（例 1.4 は $\Sigma$ が半正定値であることによる）。最短路問題（例 1.7）の実行可能領域は有限集合で凸ではないが、グラフの特別な構造のおかげで効率よく解ける。例 1.15 の 4 次関数は $f''(0) < 0$ なので凸でない。

大まかにいえば、凸最適化問題では局所的な情報だけで大域的な最適性が判定でき、線形計画や凸二次計画などには多項式時間のアルゴリズムが知られている。一方、非凸な問題や整数変数を含む問題は一般に難しく、0-1 整数計画は NP 困難な問題を含む（第7章）。問題を凸に定式化できるか、できないなら凸な問題でどう近似するかが、実際に最適化を使うときの最も重要な判断の一つである。

まとめ

• 最適化問題は、決定変数・目的関数・制約（実行可能領域）で定式化する。最適値 $p^{\ast} = \inf_{x \in X} f(x)$ は常に定まるが、最適解は存在するとは限らない。
• 生産計画・輸送は線形計画、ポートフォリオ選択は二次計画、最小二乗とロジスティック回帰は制約なし問題、最短路は 0-1 整数計画として書ける。
• コンパクト集合上の連続関数は最小値をとる（ワイエルシュトラスの定理）。閉集合上の連続で強圧的な関数も最小値をとる。連続性・閉性・強圧性のどれが欠けても反例がある。
• 完全に分離できるデータではロジスティック回帰の最尤推定値は存在しないが、リッジ正則化を加えると最小点が存在する。
• 局所最小点は大域最小点とは限らず、勾配法は出発点によって異なる局所最小点に収束しうる。
• 1 次の必要条件 $\nabla f(x^{\ast}) = 0$、2 次の必要条件「$\nabla^2 f(x^{\ast})$ が半正定値」、2 次の十分条件「$\nabla f(x^{\ast}) = 0$ かつ $\nabla^2 f(x^{\ast})$ が正定値なら狭義の局所最小」。半正定値だが正定値でない場合は判定できない。
• 二次関数 $\frac{1}{2}x^{\top}Qx - c^{\top}x$ が最小値をもつのは $Q$ が半正定値かつ $c \in \operatorname{Im} Q$ のときに限り、最小点は $Qx = c$ の解である。
• 凸最適化問題では局所最小点が大域最小点になり、$\nabla f = 0$ が最適性の十分条件になる（第2章）。

演習問題