blog.monophile.net

Takaaki Yamamoto

東京工業大学において計算機科学と応用数学を学び、 情報科学芸術大学院大学[IAMAS]においてメディア表現を専攻し修了。 digitiminimi Inc. において、インフラエンジニアとして生計をたててている。

各種環境の構築と管理を承ります。

  • 仮想環境: Openstack, GCP, AWS, Azure, ...
  • アプリケーション: WordPress, GitLab, Redmine, ...

List

二次形式の平方完成

いきさつ

凸二次形式の最小値を求めるために、計算しました。 この計算によって解けるのは強凸二次形式です。

平方完成(正則の場合)

まずは元の式と平方完成した後の式を比較します。 \(Q\)は対称行列で、\(q\)は一次式の係数ベクトルです。

\[ \begin{align*} f(x) &= x^T Q x + q^T x \text{ (二次形式)}\\ &= (x + z)^T Q (x + z) + c \text{ (平方完成後)}\\ &= x^T Q x + 2 z^TQx + z^TQz + c \end{align*} \]

係数を比較することによって以下の等式が成り立ちます。

\[ \begin{align*} 2 z^TQ &= q^T \\ z^TQz + c &= 0 \end{align*} \]

\(|Q| \neq 0\) (逆行列が存在) と仮定すると、 以下のようにzとcが求まります。

\[ \begin{align*} z &= \frac{1}{2} Q^{-1} q \\ c &= -z^TQz = -\frac{1}{4} q^T Q^{-1} q \end{align*} \]

\(Q \succ 0\)の場合、最小元と最小値は以下のように表されます。

\begin{align*} \text{(最小元) } &= -z = -\frac{1}{2} Q^{-1} q \\ \text{(最小値) } &= c = -z^TQz = -\frac{1}{4} q^T Q^{-1} q \end{align*}

\(Q \succeq 0\) の場合は、対角成分が0である行と列を除去した行列\(Q'\) を生成することで、同様に計算できます。 (行列の次数が減るところは、適宜調整してください。)

\[Q' := Q[I,I] \\ ( I := \{ i | Q_{ii} > 0 \})\]

\(Q\)が半正定値の場合は、ほかにも方法があって、 擬似逆行列 - Wikipedia を使うと求められると思います。 (たぶん。)