多項式最適化問題

【たこうしきさいてきかもんだい (polynomial optimization problem)】

　変数 $x=(x_{1},\ldots ,x_{n})$ に関する多項式 $f,g_{i}\,(i=1,\ldots ,m),h_{j}(j=1,\ldots ,l)$ を用いて記述される非線形計画問題

${\begin{array}{ll}{\mbox{min.}}&f(x)\\{\mbox{s. t. }}&g_{i}(x)\geq 0\ (i=1,\ldots ,m),\\&h_{j}(x)=0\ (j=1,\ldots ,l)\end{array}}$

を多項式最適化問題(polynomial optimization problem)と呼ぶ. 多項式計画問題は一般に非凸計画問題であり, NP 困難な最適化問題である. 変数が0または1という制約は2次の多項式で表現できるので, 多項式計画問題は 0-1 整数計画問題を特殊ケースとして含む.

　通常の非線形計画問題においては局所的最適解を求めることが目標であるが, 多項式計画問題においては, 凸計画を用いてその大域的最適値を求める方法が存在する. そのため, 多項式計画問題に対しては大域的最適化が前提となる.

　多項式最適化問題の最適値は半正定値計画(SDP)による緩和問題を解くことにより求められる. その概要は次のとおりである. 多項式計画問題に現れる多項式の次数のうち, 最大のものを$d\,$とし, $R=\{r\in N\ |\ r\geq \lceil d/2\rceil \}$ とおく. 各 $r\in R$ に対し, （多項式計画問題にコンパクトな実行可能領域が存在するなどの比較的緩やかな条件の元で）次の性質を持つSDP 緩和問題 ${\mbox{SDP}}(r)$ を生成できる [1]:

• ${\mbox{SDP}}(r)$ の最適値 $\theta _{r}$ は多項式計画問題の最適値$\theta _{\ast }$以下である.

• 任意の $r\in R$ に対して $\theta _{r+1}\geq \theta _{r}$ が成り立つ.

• ${\mbox{lim}}_{r\rightarrow \infty }\theta _{r}=\theta _{\ast }$.

SDP 緩和問題を決定する正整数 $r\in R$ を緩和次数と呼ぶ. このような性質を持つ SDP 緩和問題を構成できるという事実の背後には, ２乗和多項式（Sums Of Squares; SOS）の理論が存在する. このため, 上記で説明した SDP 緩和を SOS 緩和と呼ぶこともある.

　後述するように $r\,$ を一つ上げると ${\mbox{SDP}}(r)$ のサイズは急激に大きくなり, その結果解けなくなる場合も多い. 従って通常は最も小さな $r=\lceil d/2\rceil$ から始め, 一つずつ緩和次数を大きくしながら SDP 緩和問題の列を解いていく. 理論上は緩和次数を無限に大きくしなければ最適値は得られないが, 実際には有限の（しかもそれほど大きくない）緩和次数で最適値が達成される場合が多い. 特に実行可能解が有限個しか無い場合には, 有限の緩和次数で最適解が求められることを理論的に保証できることがある. 例えば $n\,$ 変数の$0-1\,$ 整数計画問題（を多項式計画問題に変換したもの）に対し, ある大きさの緩和次数の SDP を解けば必ずその最適解が求められることが知られている[2]. ただしその大きさの緩和次数を用いたとき, SDP 緩和問題の変数の数は $2^{n}-1$ 個必要となる.

　多項式計画問題の最適値だけでなく, 最適解を求める方法も研究されている. 多項式計画問題の最適解が1個のときには, $\theta _{r}=\theta _{\ast }$ が成り立っていれば, 多くの場合に${\mbox{SDP}}(r)$ の最適解から多項式最適化問題の最適解を簡単に抽出できる. 多項式最適化問題の最適解が複数個（ただし有限個）ある場合でも, 適当な仮定の元では${\mbox{SDP}}(r)$ の最適解からすべての最適解を抽出することが可能である [3].

　多項式計画問題の変数の数を $n\,$ としたとき, ${\mbox{SDP}}(r)$ で用いられる行列の大きさの下限と使用される変数の数はそれぞれ

$\left({\begin{array}{c}n+r\\r\end{array}}\right)\times \left({\begin{array}{c}n+r\\r\end{array}}\right)$　および　$\left({\begin{array}{c}n+2r\\2r\end{array}}\right)$

である. これより, SDP緩和問題のサイズは$n\,$, $r\,$ の増大とともに急激に大きくなることがわかる. このため, 10変数程度の問題でも緩和次数を $4\,$, $5\,$ 程度以上に大きくすることは困難な場合が多い. この状況を打開するため「通常の多項式計画問題で使われる多項式には, 非常に少ない数の項しか現れない」という性質（多項式の疎性という）を利用してSDP のサイズを縮小する方法が提案されている [5]. この方法を用いると, 適切な疎性構造を持った問題であれば数百変数の問題も解くことが可能となる. 現実に現れる多項式計画問題はほとんど疎性を持っており, これをうまく利用することが多項式計画問題を解く鍵であると考えられている.

　多くの多項式計画問題の SDP 緩和問題は極めて悪条件であることが, 数値実験により知られている. これには様々な理由が考えられる. 一つの原因としては, 多項式計画問題においては必然的に冪乗を計算することになるため, 数値の大小の幅が大きいことが挙げられる. 変数の範囲を $[0,1]\,$ に正規化することは, 数値的安定性を得るのにしばしば大きな効果を上げることが知られている. また, 最適解の近傍で変数行列（の部分行列）が Hankel 行列に近づくことも悪条件の原因の一つと推測されている. Hankel 行列は悪条件な行列で知られているが、主双対内点法においてはこの変数行列の逆行列を計算する必要があり, それが数値的に破綻する. この問題は未だ本質的には克服されていない.

　線形計画を半正定値計画や等質自己双対錐上の線形計画に拡張したのと同様の方法により, 多項式計画問題における不等式制約を, 半正定値制約や等質自己双対錐に含まれるという制約に拡張した問題も考えられている. これらの拡張された問題に対し, 一般の場合と同様に SDP 緩和問題を構成でき, その最適値が元の問題の最適値へ収束することが示されている [4]. しかしながら, 扱う SDP 緩和問題は一般にさらに巨大になる. このため, この場合にも多項式の疎性を利用する研究が進んでいる.

---

参考文献

[1] J.B. Lasserre, Global optimization with polynomials and the problems of moments. SIAM Journal on Optimization, 11 (2001) 796-817.

[2] J.B. Lasserre, An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs. SIAM Journal on Optimization, 12 (2002) 756-769.

[3] D.Henrion and J.B.Lasserre, Detecting global optimality and extracting solutions in GloptiPoly, D. Henrion, A. Garulli(Editors). Positive polynomials in control. Lecture Notes on Control and Information Sciences, Springer Verlag (2005).

[4] M. Kojima and M. Muramatsu, An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems over Symmetric Cones. Mathematical Programming, to appear.

[5] H. Waki, S. Kim, M. Kojima and M. Muramatsu, Sums of Squares and Semidefinite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity, SIAM Journal on Optimization, 17 (2006) 218-242.