blog.monophile.net

コンピュータに関するメモ。

著者

山本一彰(Takaaki Yamamoto)

東京工業大学において計算機科学と応用数学を学び、 情報科学芸術大学院大学[IAMAS]においてメディア表現を専攻し修了。 2015年にコンビネータ論理を基に計算完備な計算手法 "論理珠算"を開発し、 それを含む体系である"算道"を構成した。 その成果により、2016年に 第19回 文化庁メディア芸術祭 アート部門 新人賞 (文部科学大臣賞) を受賞。 現在はSRE(サイト信頼性エンジニア)として生計をたててている。

投稿

二次形式の平方完成

概要

強凸二次形式の最小元と最小値を求めるために、二次形式の平方完成をしてみました。

平方完成(正則の場合)

まずは元の式と平方完成した後の式を比較します。 \(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*}\]