二乗和最適化

二乗和最適化プログラムは、線形コスト関数と、決定変数に対する特定の種類の制約を伴う最適化問題です。これらの制約は、決定変数が特定の多項式の係数として使用される場合、それらの多項式が多項式 SOSプロパティを持つ必要があるという形式です。関係する多項式の最大次数を固定する場合、二乗和最適化は、半正定値計画法におけるラッセルの緩和階層とも呼ばれます。

二乗和最適化手法は、制御理論（特に、多項式ベクトル場によって記述される動的システムの多項式リアプノフ関数の探索）、統計、金融、機械学習など、さまざまな分野に適用されています。^{[1] [2] [3] [4]}

、のベクトルと多項式が与えられた場合、二乗和最適化問題は次のように表される。 ${\displaystyle c\in \mathbb {R} ^{n}}$${\displaystyle a_{k,j}}$${\displaystyle k=1,\dots N_{s}}$${\displaystyle j=0,1,\dots ,n}$

$${\displaystyle {\begin{aligned}{\underset {u\in \mathbb {R} ^{n}}{\text{最大化}}}\quad &c^{T}u\\{\text{subject to}}\quad &a_{k,0}(x)+a_{k,1}(x)u_{1}+\cdots +a_{k,n}(x)u_{n}\in {\text{SOS}}\quad (k=1,\ldots ,N_{s}).\end{aligned}}}$$

ここで、「SOS」は二乗和 (SOS) 多項式のクラスを表します。量は決定変数です。SOS プログラムは、 SOS 多項式プログラムの双対性と、半正定値行列を使用した制約付き多項式最適化の緩和法を使用して、半正定値プログラム(SDP)に変換できます。次のセクションを参照してください。 ${\displaystyle u\in \mathbb {R} ^{n}}$

変数多項式があり、この多項式を部分集合 上で最小化したいとします。さらに、部分集合 上の制約は、それぞれが の形式( は最大 次数の多項式) の、最大 次数の多項式を使用してエンコードできるものとします。この最適化問題に対する自然な (ただし、一般に非凸) プログラムは次のようになります。ただし、次の 条件に従います。 ${\displaystyle n}$${\displaystyle p(x):\mathbb {R} ^{n}\to \mathbb {R} }$${\textstyle A\subseteq \mathbb {R} ^{n}}$${\textstyle A}$${\textstyle m}$${\displaystyle 2d}$${\textstyle a_{i}(x)=0}$${\displaystyle a_{i}:\mathbb {R} ^{n}\to \mathbb {R} }$${\displaystyle 2d}$$${\displaystyle \min _{x\in \mathbb {R} ^{n}}\langle C,x^{\leq d}(x^{\leq d})^{\top }\rangle }$$

$${\displaystyle x_{\emptyset }=1,}$$ ここで、 は、次以下のの各単項式に対して 1 つの要素を持つ 次元ベクトルです。したがって、各多重集合 に対して、は最小化したい多項式の係数の行列であり、 はサブセット 上の 次の制約をエンコードする多項式の係数の行列です。検索空間内の追加の固定定数インデックス は、多項式と を行列表現で記述する便宜上追加されています。 ${\textstyle x^{\leq d}}$${\displaystyle n^{O(d)}}$${\displaystyle x}$${\displaystyle d}$${\displaystyle S\subset [n],|S|\leq d,}$ ${\textstyle x_{S}=\prod _{i\in S}x_{i}}$${\textstyle C}$${\textstyle p(x)}$${\textstyle A_{i}}$${\textstyle a_{i}(x)}$${\displaystyle i}$${\displaystyle A\subset \mathbb {R} ^{n}}$${\displaystyle x_{\emptyset }=1}$${\textstyle p(x)}$${\textstyle a_{i}(x)}$

このプログラムは一般に非凸である。なぜなら、制約条件 ( 1 ) は凸ではないからである。この最小化問題に対する 1 つの可能な凸緩和法は、半正定値計画法を使用して、階数 1 の変数の行列を正の半正定値行列に置き換えることである。すなわち、最大で のサイズの各単項式を、最大で のインデックスの多重集合でインデックスする。このような各単項式について、プログラム内に変数を作成し、変数を配置して行列 を形成する。ここで、は行と列が最大で のサイズの からの要素の多重集合で識別される実数行列の集合である。次に、変数 に次の半正定値プログラムを記述する。 ただし、次の 条件に従う。 ${\displaystyle x^{\leq d}(x^{\leq d})^{\top}}$${\displaystyle X}$${\displaystyle 2d}$${\displaystyle S}$${\displaystyle 2d}$${\displaystyle S\subset [n],|S|\leq 2d}$${\displaystyle X_{S}}$${\displaystyle X_{S}}$${\textstyle X\in \mathbb {R} ^{[n]^{\leq d}\times [n]^{\leq d}}}$${\displaystyle \mathbb {R} ^{[n]^{\leq d}\times [n]^{\leq d}}}$${\displaystyle n}$${\displaystyle d}$${\displaystyle X_{S}}$$${\displaystyle \min _{X\in \mathbb {R} ^{[n]^{\leq d}\times [n]^{\leq d}}}\langle C,X\rangle }$$$${\displaystyle \langle A_{i},X\rangle =0\qquad \forall \ i\in [m],Q}$$ $${\displaystyle X_{\emptyset }=1,}$$ $${\displaystyle X_{U\cup V}=X_{S\cup T}\qquad \forall \ U,V,S,T\subseteq [n],|U|,|V|,|S|,|T|\leq d,{\text{ and}}\ U\cup V=S\cup T,}$$ $${\displaystyle X\succeq 0,}$$

ここで、 は最小化したい多項式の係数の行列であり、 はサブセット 上の 番目の制約をエンコードする多項式の係数の行列です。 ${\textstyle C}$${\textstyle p(x)}$${\textstyle A_{i}}$${\textstyle a_{i}(x)}$${\displaystyle i}$${\displaystyle A\subset \mathbb {R} ^{n}}$

3 番目の制約は、行列内で複数回出現する単項式の値が行列全体で等しくなるようにし、二次形式に存在する対称性を尊重するために追加されます。 ${\displaystyle X}$${\displaystyle x^{\leq d}(x^{\leq d})^{\top }}$

上記の半正定値プログラムの双対を取ると、次のプログラムが得られます。 ただし、次の条件に従います。 $${\displaystyle \max _{y\in \mathbb {R} ^{m'}}y_{0},}$$$${\displaystyle C-y_{0}e_{\emptyset }-\sum _{i\in [m]}y_{i}A_{i}-\sum _{S\cup T=U\cup V}y_{S,T,U,V}(e_{S,T}-e_{U,V})\succeq 0.}$$

制約に対応する変数（ は、でインデックス付けされた要素を除くすべての要素がゼロの行列）、各多項式制約の実変数、および各多重集合のグループ に対して、対称制約の双対変数があります。 正半定値制約により、が 上の多項式の平方和であることが保証されます。 正半定値行列の特徴付けにより、任意の正半定値行列 に対して、ベクトル に対して と書くことができます。したがって、 任意の に対して、${\displaystyle y_{0}}$${\displaystyle \langle e_{\emptyset },X\rangle =1}$${\displaystyle e_{\emptyset }}$${\displaystyle (\varnothing ,\varnothing )}$${\displaystyle y_{i}}$${\displaystyle \langle X,A_{i}\rangle =0\quad s.t.i\in [m],}$${\displaystyle S,T,U,V\subset [n],|S|,|T|,|U|,|V|\leq d,S\cup T=U\cup V}$${\displaystyle y_{S,T,U,V}}$${\displaystyle \langle X,e_{S,T}-e_{U,V}\rangle =0}$${\displaystyle p(x)-y_{0}}$${\displaystyle A\subset \mathbb {R} ^{n}}$${\textstyle Q\in \mathbb {R} ^{m\times m}}$${\textstyle Q=\sum _{i\in [m]}f_{i}f_{i}^{\top }}$${\textstyle f_{i}\in \mathbb {R} ^{m}}$${\textstyle x\in A\subset \mathbb {R} ^{n}}$$${\displaystyle {\begin{aligned}p(x)-y_{0}&=p(x)-y_{0}-\sum _{i\in [m']}y_{i}a_{i}(x)\qquad {\text{since }}x\in A\\&=(x^{\leq d})^{\top }\left(C-y_{0}e_{\emptyset }-\sum _{i\in [m']}y_{i}A_{i}-\sum _{S\cup T=U\cup V}y_{S,T,U,V}(e_{S,T}-e_{U,V})\right)x^{\leq d}\qquad {\text{by symmetry}}\\&=(x^{\leq d})^{\top }\left(\sum _{i}f_{i}f_{i}^{\top }\right)x^{\leq d}\\&=\sum _{i}\langle x^{\leq d},f_{i}\rangle ^{2}\\&=\sum _{i}f_{i}(x)^{2},\end{aligned}}}$$

ここで、ベクトルを次以下の多項式の係数と同一視しています。これにより、 を超える値が であることが二乗和により証明されます。 ${\textstyle f_{i}}$${\displaystyle d}$${\textstyle p(x)\geq y_{0}}$${\displaystyle A\subset \mathbb {R} ^{n}}$

上記は、多項式不等式によって定義される 領域にも拡張できます。${\displaystyle A\subset \mathbb {R} ^{n}}$

二乗和階層 (SOS 階層) は、ラセレ階層とも呼ばれ、累乗が大きくなり計算コストも大きくなる凸緩和の階層です。各自然数に対して、対応する凸緩和はSOS 階層の番目のレベルまたは番目のラウンドと呼ばれます。のとき、第 ラウンドは、基本的な半正定値計画、または最大 次数の多項式に対する二乗和最適化に対応します。階層の 第 レベルにある基本的な凸計画を第レベルに拡張するには、プログラムに変数と制約を追加して、プログラムが最大 次数の多項式を考慮するようにします。 ${\textstyle d\in \mathbb {N} }$${\textstyle d}$${\textstyle d}$${\textstyle 1}$${\textstyle d=1}$${\displaystyle 2}$${\textstyle 1}$${\textstyle d}$${\displaystyle 2d}$

SOS 階層の名前は、- 番目のレベルの目的関数の値が、最大で次数の多項式を使用した平方和の証明によって、双対を介して制限されるという事実に由来しています (上記の「双対性」を参照)。したがって、最大で次数の多項式を使用する平方和の証明は、目的値を制限するために使用でき、緩和の厳密さの保証を証明できます。 ${\textstyle d}$${\textstyle 2d}$${\textstyle 2d}$

バーグの定理と合わせて、これはさらに、十分な数のラウンドが与えられると、任意の固定区間で緩和が任意にタイトになることを意味しています。バーグの結果^{[5] [6]}は、制限された区間内のすべての非負の実多項式は、十分に高い次数の実多項式の二乗和を使用して、その区間で精度内で近似できることを述べています。したがって、が点 の関数としての多項式の目的値である場合、不等式が関心領域内のすべての に対して成り立つ場合、この事実の二乗和の証明がなければなりません。 を実現可能領域上で目的関数の最小値にすると、結果が得られます。 ${\textstyle \varepsilon }$${\textstyle OBJ(x)}$${\textstyle x}$${\textstyle c+\varepsilon -OBJ(x)\geq 0}$${\textstyle x}$${\textstyle c}$

変数内の関数を最適化する場合、階層の 番目のレベルは変数上の半正定値計画として記述でき、楕円体法を使用して時間内に解くことができます。 ${\textstyle n}$${\textstyle d}$${\textstyle n^{O(d)}}$${\textstyle n^{O(d)}}$

多項式が平方和（SOS ）であるとは、となる多項式が存在する場合です。たとえば、 は平方和です。 となるので、 となります 。 が 平方和であれば、すべての に対してとなること に注意してください。多項式SOSの詳細な説明が利用可能です。^{[7] [8] [9]}${\displaystyle p}$${\displaystyle \{f_{i}\}_{i=1}^{m}}$${\textstyle p=\sum _{i=1}^{m}f_{i}^{2}}$$${\displaystyle p=x^{2}-4xy+7y^{2}}$$$${\displaystyle p=f_{1}^{2}+f_{2}^{2}}$$$${\displaystyle f_{1}=(x-2y){\text{ and }}f_{2}={\sqrt {3}}y.}$$${\displaystyle p}$${\displaystyle p(x)\geq 0}$${\displaystyle x\in \mathbb {R} ^{n}}$

2 次形式は、が対称行列である場合に、として表すことができます。同様に、次数 ≤ 2 dの多項式は 、 ベクトルが次数 のすべての単項式を含む場合として表すことができます 。これは、グラム行列形式として知られています。重要な事実は、 がSOS である場合、かつ となる対称かつ半正定値行列が存在する場合に限ります。これにより、SOS 多項式と半正定値行列が結び付けられます。 ${\displaystyle p(x)=x^{T}Qx}$${\displaystyle Q}$$${\displaystyle p(x)=z(x)^{\mathsf {T}}Qz(x),}$$${\displaystyle z}$${\displaystyle \leq d}$${\displaystyle p}$ ${\displaystyle Q}$${\displaystyle p(x)=z(x)^{\mathsf {T}}Qz(x)}$

• SOSTOOLS は、GNU GPLライセンスで提供されています。リファレンス ガイドは arXiv:1310.4716 [math.OC] で入手できます。また、内部構造に関するプレゼンテーションは、こちらで入手できます。
• CDCS-sos は、大規模な SOS プログラムを処理するための拡張ラグランジュ法ソルバーである CDCS のパッケージです。
• Julia 用の JuMP の SumOfSquares 拡張。
• TSSOS for Julia は、スパース性適応モーメント SOS 階層に基づく多項式最適化ツールです。
• 制約付き多項式最適化の双対問題については、MATLAB/Octave の場合は GloptiPoly、Python の場合は Ncpol2sdpa、Julia の場合は MomentOpt を使用します。