最適化問題を解く（その05/X） - 「大人の教養・知識・気付き」を伸ばすブログ

はじめに

　統計学にしても経済学にしても、応用数学の中でも非常に重要な分野である「最適化問題」を

最適化手法入門データサイエンス入門シリーズ

作者:寒野善博
講談社

Amazon

などを参考に学んでいきます。

power-of-awareness.com

はじめに
2.　線形計画と凸2次計画
- 2.4　凸2次計画問題
- 2.5　応用例
  - 2.5.1　回帰分析と正則化
  - 2.5.2　サポートベクターマシン
3.　凸計画
- 3.0　数学的準備：勾配ベクトルとヘッセ行列
参考文献

2.　線形計画と凸2次計画

2.4　凸2次計画問題

　線形計画問題を拡張し、1次式で表された制約の下で凸2次関数と呼ばれる関数を最小化するような最適化問題を考える。
　 $n$ 変数 $x_1,\cdots,x_n$ の2次関数は、 $n$ 次対称行列 $Q,\ r\in\mathbb{R}$ および $\boldsymbol{c}\in\mathbb{R}^n$ を用いて

$\begin{aligned} \boldsymbol{\frac{1}{2}}{}^{t}\!\boldsymbol{x}Q\boldsymbol{x}+{}^{t}\!\boldsymbol{c}\boldsymbol{x}+r \end{aligned}$

と一般に書ける。もし $\boldsymbol{d}\in\mathbb{R}^n$ に対して ${}^{t}\!\boldsymbol{d}Q\boldsymbol{d}\geq0$ が成り立つとき、 $Q$ は半正定値であるといい、 $Q$ が半正定値であるとき、

$\begin{aligned} \boldsymbol{\frac{1}{2}}{}^{t}\!\boldsymbol{x}Q\boldsymbol{x}+{}^{t}\!\boldsymbol{c}\boldsymbol{x}+r \end{aligned}$

を凸2次関数と呼ぶ。
　このとき、凸2次計画を以下のとおり定式化する。

定義2.8　凸2次計画　 $\boldsymbol{x}=\begin{bmatrix}x_1\\\vdots\\x_n\end{bmatrix}$ に対して、 $Q$ を $n$ 次半正定値行列として

$\begin{aligned} \displaystyle{\frac{1}{2}}{}^{t}\!\boldsymbol{x}Q\boldsymbol{x}+{}^{t}\!\boldsymbol{c}\boldsymbol{x}+\boldsymbol{r} \end{aligned}$

を凸2次関数という。
　また凸2次関数を1次式の制約下で最適化する問題、すなわち

$\begin{aligned} \mathrm{Maximize}\ \ \ &\displaystyle{\frac{1}{2}}{}^{t}\!\boldsymbol{x}Q\boldsymbol{x}+{}^{t}\!\boldsymbol{c}\boldsymbol{x},\\ \mathrm{subject\ to}\ \ \ &A\boldsymbol{x}\geq\boldsymbol{b}\\ &\boldsymbol{x}\geq\boldsymbol{0} \end{aligned}$

を凸2次計画問題と呼ぶ*1。

2.5　応用例

2.5.1　回帰分析と正則化

　変数 $s,t$ について、観測データとして $(s_1,t_1),\cdots,(s_r,t_r)$ があるとする。変数 $t$ を変数 $s$ に回帰させた回帰モデル

$\begin{aligned} t=ws+v \end{aligned}$

を考える。このときに最小二乗法で回帰係数 $w$ を推定する問題を考えれば、この最適化問題は

$\begin{aligned} \mathrm{Minimize}\ \ \ \displaystyle{\sum_{l=1}^{r}\{(ws_l+v)-t_l\}^2} \end{aligned}$

と書ける。
　 $\mathcal{L}^2$ ノルムを用いると、この問題は

$\begin{aligned} \left\|\begin{bmatrix}(ws_1+v)-t_1\\\cdots\\(ws_r+v)-t_r\end{bmatrix}\right\|_2^2= \left\|\begin{bmatrix}s_1&1\\\vdots&\vdots\\s_r&1\end{bmatrix}\begin{bmatrix}w\\v\end{bmatrix}-\begin{bmatrix}t_1\\\vdots\\t_r\end{bmatrix}\right\|_2^2 \end{aligned}$

と書ける。記述を簡単化するために $A=\begin{bmatrix}s_1&1\\\vdots&\vdots\\s_r&1\end{bmatrix},\$ $\boldsymbol{b}=\begin{bmatrix}t_1\\\vdots\\t_r\end{bmatrix},$ $\boldsymbol{x}=\begin{bmatrix}w\\v\end{bmatrix}$ とおけば、

$\begin{aligned} \mathrm{Minimize}\ \ \ \|A\boldsymbol{x}-\boldsymbol{b}\|^2_2 \end{aligned}$

と書き直すことができる。この目的関数を展開すると、

$\begin{aligned} {}^{t}\!\boldsymbol{x}({}^{t}\!AA)\boldsymbol{x}-2{}^{t}\!\boldsymbol{b}A\boldsymbol{x}+\|\boldsymbol{b}\|^2_2 \end{aligned}$

が得られるが、 ${}^{t}\!AA$ は対称かつ半正定値であるから、この問題は凸2次計画問題の特別な場合に相当する。

任意の $\boldsymbol{x}\in\mathbb{R}^2$ に対して、
$\begin{aligned} {}^{t}\!\boldsymbol{x}({}^{t}\!AA)\boldsymbol{x}={}^{t}\!(A\boldsymbol{x})(A\boldsymbol{x})=\|A\boldsymbol{x}\|^2_2\geq0 \end{aligned}$
であるから、確かに ${}^{t}\!AA$ は対称かつ半正定値である。

　次にリッジ回帰を考える。観測データ $A$ に対してその真の値が $A+\Delta$ と書けると仮定すると、三角不等式から

$\begin{aligned} \left\|(A+\Delta)\boldsymbol{x}-\boldsymbol{b}\right\|_2\leq\|A\boldsymbol{x}-\boldsymbol{b}\|_2+\|\Delta\boldsymbol{x}\|_2 \end{aligned}$

が得られる。右辺第1項は最小二乗法における目的関数であったが、右辺第2項が大きければ、清のデータと予測値の差が大きくなり得ることが分かる。そのため、 $\|\boldsymbol{x}\|^2$ が大きいと右辺第2項が大きくなり得るためにデータが含む誤差の影響を受けやすいと言える。そこで右辺の両項を両方とも小さく出来ることが望ましい。そこで

$\begin{aligned} \mathrm{Minimize}\ \ \|A\boldsymbol{x}-\boldsymbol{b}\|^2_2+\gamma\|\boldsymbol{x}\|_2^2 \end{aligned}$

と定式化( $\gamma\gt0$ )すれば、双方を抑えることを実現できる。この回帰手法をリッジ回帰という。
　このように目的関数に追加の項を導入して誤差に対する予測モデルのロバスト性を高めたり予測モデルの単純さを保つことは正則化という。他に $\mathcal{L}_1$ ノルム正則化付き最小二乗法( $\mathrm{LASSO}$ )

$\begin{aligned} \mathrm{Minimize}\ \ \|A\boldsymbol{x}-\boldsymbol{b}\|^2_2+\gamma\|\boldsymbol{x}\|_1^2 \end{aligned}$

は $\boldsymbol{x}$ として $0$ を成分として多く含むベクトルを求めたい場合に用いる。これは凸2次計画問題に帰着できる。実際、

$\begin{aligned} \mathrm{Minimize}&\ \ \|A\boldsymbol{x}-\boldsymbol{b}\|^2_2+\gamma{}^{t}\!\boldsymbol{1}\boldsymbol{z}\\ \mathrm{subject\ to}&\ \ \boldsymbol{z}\geq\boldsymbol{x},\\ &\ \ \boldsymbol{z}\geq-\boldsymbol{x} \end{aligned}$

と変形できるからである。
　他にも差の絶対値の最大値(最大値ノルム)を最小化する問題

$\begin{aligned} \mathrm{Minimize}\ \ \|A\boldsymbol{x}-\boldsymbol{b}\|_{\infty} \end{aligned}$

は $\mathrm{Chebyshev}$ 近似問題と呼ばれる。また

$\begin{aligned} \mathrm{Minimize}\ \ \|A\boldsymbol{x}-\boldsymbol{b}\|^2_1+\gamma\|\boldsymbol{x}\|_1^2 \end{aligned}$

も考えられ、これらはいずれも線形計画化問題に帰着できる。

2.5.2　サポートベクターマシン

　データ点 $\boldsymbol{x}_1,\cdots,\boldsymbol{x}_r\in\mathbb{R}^d$ が与えられているとする。そして各点には2種類のうちいずれかのラベル(たとえば〇と×)が与えられているとする。この2種類のデータ点を分類するような直線(超平面)を求めたい。このような問題を2クラス分類と呼ぶ。ここではサポートベクトルマシンを導入し、それが凸2次計画で解けることを示す。
　ラベルを表すダミー変数(たとえば〇ならば $t_l=1,$ ×ならば $t_l=0$ )とすれば、各データ点 $\boldsymbol{s}_i$ に対して条件

$\begin{aligned} {}^{t}\!\boldsymbol{s}_l\boldsymbol{w}+v&\gt0,t_l=1\\ {}^{t}\!\boldsymbol{s}_l\boldsymbol{w}+v&\lt0,t_l=-1 \end{aligned}$

が成立するように $\boldsymbol{w}\in\mathbb{R}^d,v\in\mathbb{R}$ を定める。これはより簡潔に

$\begin{aligned} t_l({}^{t}\!\boldsymbol{s}_l\boldsymbol{w}+v)\gt0,\ l=1,\cdots,r \end{aligned}$

と書ける。すなわちもし上記のまとめた条件を満たすような $\boldsymbol{w},v$ が存在するならば、2種類のデータ点は超平面 ${}^{t}\boldsymbol{w}\boldsymbol{s}+v=0$ で分離される。この場合に線形分離可能であるという(一般にデータは線形分離可能とは限らない。)。
　この条件はさらに

$\begin{aligned} t_l({}^{t}\!\boldsymbol{s}_l\boldsymbol{w}+v)\geq1,\ l=1,\cdots,r \end{aligned}$

と置き換えることができる。実際、条件 $t_l({}^{t}\!\boldsymbol{s}_l\boldsymbol{w}+v)\gt0,\ l=1,\cdots,r$ は条件

$\begin{aligned} {}^{\exists}\varepsilon\gt0\left(t_l({}^{t}\!\boldsymbol{s}_l\boldsymbol{w}+v)\geq\varepsilon,\ l=1,\cdots,r\right) \end{aligned}$

が成立することと同値だが、これは $\displaystyle{\frac{\boldsymbol{w}}{\varepsilon}}$ および $\displaystyle{\frac{v}{\varepsilon}}$ を合貯めて $\boldsymbol{w},v$ と置き換えればその条件を得る。この条件下において、境界面 ${}^{t}\!\boldsymbol{w}\boldsymbol{s}+v=0$ から最も近い点までの距離をマージンという。
　この問題はマージンをなるべく大きく出来るのが望ましい。ここで $\displaystyle{\frac{\boldsymbol{w}}{\|\boldsymbol{w}\|_2^2}}$ の大きさが $\displaystyle{\frac{1}{\|\boldsymbol{w}\|_2}}$ であることから、マージン最大化は $\|\boldsymbol{w}\|_2$ 最小化と同値である。したがってサポートベクトルマシンは、

$\begin{aligned} \mathrm{Minimize}\ \ &{}^{t}\!\boldsymbol{w}\boldsymbol{w}\\ \mathrm{subject\ to}\ \ &t_l({}^{t}\!\boldsymbol{s}_l\boldsymbol{w}+v)\geq1,l=1,\cdots,r \end{aligned}$

という $\boldsymbol{w},v$ を決定係数とする凸2次計画問題に帰着できる。
　他方でデータが線形分離可能でない場合、上記の最適化問題は実行可能解を持たない、すなわち誤分類されるデータ点が必ず存在する。誤分類の程度は小さく、かつ正しく部類されるデータ点に関するマージンは大きい境界面を求めることが目的になる。この目的のためには、誤分類されたデータ点について、制約

$\begin{aligned} t_l({}^{t}\!\boldsymbol{s}_l\boldsymbol{w}+v)\geq1,l=1,\cdots,r \end{aligned}$

を違反した程度に応じてペナルティを課す。たとえば、

$\begin{aligned} \phi(z)=\begin{cases} 0,&z\geq1,\\ 1-z&z\lt1 \end{cases} \end{aligned}$

と定義すると、 $\phi(t_l({}^{t}\!\boldsymbol{s}\boldsymbol{w}+v) )$ は制約を満たすと $0,$ そうでない場合に正の値を取る。このようにして違反することを抑える働きをする。これは最適化問題

$\begin{aligned} \mathrm{Minimize}\ \ {}^{t}\!\boldsymbol{w}\boldsymbol{w}+\gamma\displaystyle{\sum_{l=1}^{r}\phi(t_l({}^{t}\!\boldsymbol{s}_l\boldsymbol{w}+v) )},\ \gamma\gt0 \end{aligned}$

を解くことで実現できる。
　なおこの問題は

$\begin{aligned} \mathrm{Minimize}\ \ \ &{}^{t}\!\boldsymbol{w}\boldsymbol{w}+\gamma\displaystyle{\sum_{l=1}^{r}e_l},&\\ \mathrm{subject\ to}\ \ \ &t_l({}^{t}\!\boldsymbol{s}_l\boldsymbol{w}+v)+e_l\geq1,&l=1,\cdots,r,\\ &e_l\geq0,&l=1,\cdots,r \end{aligned}$

と変形できる。これは $\boldsymbol{w},v,e_1,\cdots,e_r$ を決定変数とする凸2次計画問題である。

3.　凸計画

線形計画問題や凸2次計画問題を含むより一般的な枠組みとして凸計画がある。
凸計画問題では任意の局所最適解が大域的最適解であるという性質がある。

3.0　数学的準備：勾配ベクトルとヘッセ行列

　以降の議論で用いるために、数学的な準備をする。
　集合 $D\subset\mathbb{R}^n,D\neq\emptyset$ で定義された $f:D\rightarrow\mathbb{R}$ が $\boldsymbol{x}^{*}\in D$ で微分可能であるならば、 ${}^{\forall}\!\boldsymbol{x}\in D$ に対して

$\begin{aligned} f(\boldsymbol{x})=&f(\boldsymbol{x}^{*})+\displaystyle{\sum_{i=1}^{n}\frac{\partial f}{\partial x_i}}\left(\boldsymbol{x}^{*}\right)(x_i-x_i^{*})\\ &+\sqrt{\displaystyle{\sum_{i=1}^{n}(x_i-x_i^{*})^2}}\delta_1\left(\boldsymbol{x}^{*};\boldsymbol{x}-\boldsymbol{x}^{*}\right) \end{aligned}$

が成り立つ。ここで

$\begin{aligned} \boldsymbol{x}&=\begin{bmatrix}x_1\\\vdots\\x_n\end{bmatrix},\\ \boldsymbol{x}^{*}&=\begin{bmatrix}x_1^{*}\\\vdots\\x_n^{*}\end{bmatrix} \end{aligned}$

と表し、 $\delta_1\left(\boldsymbol{x}^{*};\cdot\right):\mathbb{R}^n\rightarrow\mathbb{R}$ は

$\begin{aligned} \displaystyle{\lim_{\boldsymbol{x}\rightarrow\boldsymbol{x}^{*}}\delta_1\left(\boldsymbol{x}^{*};\boldsymbol{x}-\boldsymbol{x}^{*}\right)}=0 \end{aligned}$

を満たすものとする。
　更に $f$ が $\boldsymbol{x}=\boldsymbol{x}^{*}$ で2回微分可能ならば、 ${}^{\forall}\!\boldsymbol{x}\in D$ に対して

$\begin{aligned} f(\boldsymbol{x})=&f(\boldsymbol{x}^{*})+\displaystyle{\sum_{i=1}^{n}\frac{\partial f}{\partial x_i}}\left(\boldsymbol{x}^{*}\right)(x_i-x_i^{*})\\ &+\displaystyle{\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{\partial^2 f}{\partial x_i\partial x_j}\left(\boldsymbol{x}^{*}\right)(x_i-x_i^{*})(x_j-x_j^{*})}\\ &+\left\{\displaystyle{\sum_{i=1}^{n}}\right\}\delta_2\left(\boldsymbol{x}^{*};\boldsymbol{x}-\boldsymbol{x}^{*}\right) \end{aligned}$

が成り立つ。ここで $\delta_2\left(\boldsymbol{x}^{*}:\cdot\right):\mathbb{R}^n\rightarrow\mathbb{R}$ は

$\begin{aligned} \displaystyle{\lim_{\boldsymbol{x}\rightarrow\boldsymbol{x}^{*}}\delta_2\left(\boldsymbol{x}^{*}:\boldsymbol{x}-\boldsymbol{x}^{*}\right)}=0 \end{aligned}$

を満たす。
　 $\boldsymbol{x}$ を変数とする $\boldsymbol{g}\left(\boldsymbol{x}\right)=\begin{bmatrix}g_1\left(\boldsymbol{x}\right)\\\vdots\\g_p\left(\boldsymbol{x}\right)\end{bmatrix}\in\mathbb{R}^p$ が $\boldsymbol{x}=\boldsymbol{x}^{*}\in D$ において微分可能ないし2回微分可能であるとは、その成分の実数値関数

$\begin{aligned} g_i:D\rightarrow\mathbb{R} \end{aligned}$

がそれぞれ $\boldsymbol{x}=\boldsymbol{x}^{*}$ において微分可能ないし2回微分可能であることを意味する。
　以上を踏まえて、勾配ベクトル、ヘッセ行列およびヤコビ行列を定義する。

定義3.1　勾配ベクトル、ヘッセ行列およびヤコビ行列　 $f:\mathbb{R}^n\rightarrow\mathbb{R}$ に対して、

$\begin{aligned} \nabla f(\boldsymbol{x})&=\begin{bmatrix}\displaystyle{\frac{\partial f}{\partial x_1}}\\\vdots\\\displaystyle{\frac{\partial f}{\partial x_n}}\end{bmatrix}\in\mathbb{R}^n,\\ \nabla^2 f(\boldsymbol{x})&=\begin{bmatrix} \displaystyle{\frac{\partial^2 f}{\partial x_1^2}}&\cdots&\displaystyle{\frac{\partial^2 f}{\partial x_1\partial x_n}}\\ \vdots&\ddots&\vdots\\ \displaystyle{\frac{\partial^2 f}{\partial x_n\partial x_1}}&\cdots&\displaystyle{\frac{\partial^2 f}{\partial x_n^2}}\end{bmatrix}\in\mathbb{R}^{n\times n},\\ \end{aligned}$

をそれぞれ $f$ の勾配ベクトルおよびヘッセ行列という。特に $f$ が2回微分可能かつそれらの導関数が連続であれば、ヘッセ行列は対称である。
　また　 $g:\mathbb{R}^n\rightarrow\mathbb{R}^{p},p\geq1$ に対して、

$\begin{aligned} \nabla\boldsymbol{g}(\boldsymbol{x})=\begin{bmatrix}\nabla g_1(\boldsymbol{x}),&\cdots,&\nabla g_p(\boldsymbol{x})\end{bmatrix}=\begin{bmatrix} \displaystyle{\frac{\partial g_1}{\partial x_1}}(\boldsymbol{x})&\cdots&\displaystyle{\frac{\partial g_1}{\partial x_n}}(\boldsymbol{x})\\ \vdots&\ddots&\vdots\\ \displaystyle{\frac{\partial g_p}{\partial x_1}}(\boldsymbol{x})&\cdots&\displaystyle{\frac{\partial g_p}{\partial x_n}}(\boldsymbol{x}) \end{bmatrix}\in\mathbb{R}^{p\times n} \end{aligned}$

をヤコビ行列という。

　これらの計算上の性質について簡単にまとめておく。

定義3.2　勾配ベクトルとヘッセ行列の性質　 $\boldsymbol{c}\in\mathbb{R}^n,$ $Q\in\mathbb{R}^{n\times n}$ が与えられたとき、変数ベクトル $\boldsymbol{x}\in$ $\mathbb{R}^n$ に関する勾配ベクトルおよびヘッセ行列について、以下が成り立つ。

$\nabla\left({}^{t}\!\boldsymbol{c}\boldsymbol{x}\right)=\boldsymbol{c}$
$\nabla\left({}^{t}\!\boldsymbol{x}Q\boldsymbol{x}\right)=\left(Q+{}^{t}\!Q\right)\boldsymbol{x}$
$\nabla^2\left({}^{t}\!\boldsymbol{x}Q\boldsymbol{x}\right)=Q+{}^{t}\! Q$

( $\because$ 　 $\boldsymbol{x}=\begin{bmatrix}x_1\\\vdots\\x_n\end{bmatrix}\in\mathbb{R}^n,$ $\boldsymbol{c}=\begin{bmatrix}c_1\\\vdots\\c_n\end{bmatrix}\in\mathbb{R}^n$ および

$\begin{aligned} Q=\begin{bmatrix}q_{11}&\cdots&q_{1n}\\\vdots&\ddots&\vdots\\q_{n1}&\cdots&q_{nn}\end{bmatrix} \end{aligned}$

として定義に則り計算する。

$\begin{aligned} \nabla\left({}^{t}\!\boldsymbol{c}\boldsymbol{x}\right)&=\begin{bmatrix}\displaystyle{\frac{\partial}{\partial x_{1}}}\left(\displaystyle{\sum_{j=1}^{n}c_ix_i}\right)\\\vdots\\\displaystyle{\frac{\partial}{\partial x_{n}}}\left(\displaystyle{\sum_{j=1}^{n}c_ix_i}\right)\end{bmatrix}\\ &=\begin{bmatrix}c_1\\\vdots\\c_n\end{bmatrix}=\boldsymbol{c} \end{aligned}$

である。また

$\begin{aligned} {}^{t}\!\boldsymbol{x}Q\boldsymbol{x}&=\begin{bmatrix}x_1&\cdots&x_n\end{bmatrix}\begin{bmatrix}q_{11}&\cdots&q_{1n}\\\vdots&\ddots&\vdots\\q_{n1}&\cdots&q_{nn}\end{bmatrix}\begin{bmatrix}x_1\\\vdots\\x_n\end{bmatrix}\\ &=\begin{bmatrix}\displaystyle{\sum_{i=1}^{n}x_i q_{i1}}&\cdots&\displaystyle{\sum_{i=1}^{n}x_i q_{in}}\end{bmatrix}\begin{bmatrix}x_1\\\vdots\\x_n\end{bmatrix}\\ &=\displaystyle{\sum_{i=1}^{n}\sum_{j=1}^{n}x_{i}q_{ij}x_{j}} \end{aligned}$

について、

$\begin{aligned} \nabla\left({}^{t}\!\boldsymbol{x}Q\boldsymbol{x}\right)&= \begin{bmatrix} \displaystyle{\frac{\partial}{\partial x_1}\sum_{i=1}^{n}\sum_{j=1}^{n}x_{i}q_{ij}x_{j}}\\ \vdots\\ \displaystyle{\frac{\partial}{\partial x_n}\sum_{i=1}^{n}\sum_{j=1}^{n}x_{i}q_{ij}x_{j}} \end{bmatrix}\\ &=\begin{bmatrix} \displaystyle{\sum_{j=1}^{n}\left(\frac{\partial}{\partial x_1}\sum_{i=1}^{n}x_{i}\right)q_{ij}x_{j}}+\displaystyle{\sum_{i=1}^{n}x_{i}q_{ij}\left(\frac{\partial}{\partial x_1}\sum_{j=1}^{n}x_{j}\right)}\\ \vdots\\ \displaystyle{\sum_{j=1}^{n}\left(\frac{\partial}{\partial x_n}\sum_{i=1}^{n}x_{i}\right)q_{ij}x_{j}}+\displaystyle{\sum_{i=1}^{n}x_{i}q_{ij}\left(\frac{\partial}{\partial x_n}\sum_{j=1}^{n}x_{j}\right)} \end{bmatrix}\\ &=\begin{bmatrix} \displaystyle{\sum_{j=1}^{n}q_{1j}x_{j}}+\displaystyle{\sum_{i=1}^{n}q_{i1}x_{i}}\\ \vdots\\ \displaystyle{\sum_{j=1}^{n}q_{nj}x_{j}}+\displaystyle{\sum_{i=1}^{n}q_{in}x_{i}}\\ \end{bmatrix}\\ &=\begin{bmatrix} \displaystyle{\sum_{j=1}^{n}q_{1j}x_{j}}\\ \vdots\\ \displaystyle{\sum_{j=1}^{n}q_{nj}x_{j}} \end{bmatrix}+ \begin{bmatrix} \displaystyle{\sum_{i=1}^{n}q_{i1}x_{i}}\\ \vdots\\ \displaystyle{\sum_{i=1}^{n}q_{in}x_{i}} \end{bmatrix}\\ &=Q\boldsymbol{x}+{}^{t}\!Q\boldsymbol{x}\\ &=\left(Q+{}^{t}\!Q\right)\boldsymbol{x} \end{aligned}$

が成り立つ。
　更に

$\begin{aligned} \nabla^2\left({}^{t}\!\boldsymbol{x}Q\boldsymbol{x}\right)&=\begin{bmatrix} \displaystyle{\frac{\partial^2}{\partial x_1^2}\sum_{i=1}^{n}\sum_{j=1}^{n}x_{i}q_{ij}x_{j}}&\cdots&\displaystyle{\frac{\partial^2}{\partial x_1^2}\sum_{i=1}^{n}\sum_{j=1}^{n}x_{i}q_{ij}x_{j}}\\ \vdots&\ddots&\vdots\\ \displaystyle{\frac{\partial^2}{\partial x_nx_1}\sum_{i=1}^{n}\sum_{j=1}^{n}x_{i}q_{ij}x_{j}}&\cdots&\displaystyle{\frac{\partial^2}{\partial x_n^2}\sum_{i=1}^{n}\sum_{j=1}^{n}x_{i}q_{ij}x_{j}} \end{bmatrix}\\ &=\nabla\left(\left(Q+{}^{t}\!Q\right)\boldsymbol{x}\right)\\ &=Q+{}^{t}\!Q \end{aligned}$

である。　 $\blacksquare$ )

例：勾配・ヘッセ行列
　関数
$\begin{aligned} f(\boldsymbol{x})=2x_1^2-2x_1x_2+\displaystyle{\frac{1}{3}}x_2^3-x_2^2 \end{aligned}$
の点 $\bar{\boldsymbol{x}}=(1,1)^{\prime}$ における勾配とヘッセ行列を求める。
　まず勾配とヘッセ行列の各成分を定義により求めると
$\begin{aligned} \nabla f(\bar{\boldsymbol{x}})=\begin{bmatrix} 4x_1-2x_2\\ -2x_1+x_2^2-2x_2 \end{bmatrix},\nabla^2 f(\bar{\boldsymbol{x}})=\begin{bmatrix} 4&-2\\ -2&2x_2-2 \end{bmatrix} \end{aligned}$
である。したがって点 $\bar{\boldsymbol{x}}=(1,1)^{\prime}$ における勾配とヘッセ行列は
$\begin{aligned} \nabla f(\boldsymbol{x})=\begin{bmatrix} 2\\-3 \end{bmatrix},\nabla^2 f(\boldsymbol{x})=\begin{bmatrix} 4&-2\\2&0 \end{bmatrix} \end{aligned}$
である。

参考文献

寒野善博[著]/駒木文保[編](2019)「最適化手法入門」(講談社)
東京大学工学教程編纂委員会[編]、寒野　善博[著]、土谷　隆[著](2014)「東京大学工学教程基礎系数学最適化と変分法」(丸善出版)
矢部博(2006)「工学基礎　最適化とその応用」(数理工学社)
Kochenderfer, Mykel J., Wheeler, Tim A. (2019), "Algorithms for Optimization", The MIT Press (https://algorithmsbook.com/optimization/files/optimization.pdf)

*1:なお最適化に影響しないため、 $r=0$ とおいた。

はじめに

2. 線形計画と凸2次計画

2.4 凸2次計画問題

2.5 応用例

2.5.1 回帰分析と正則化

2.5.2 サポートベクターマシン

3. 凸計画

3.0 数学的準備：勾配ベクトルとヘッセ行列