日本オペレーションズ・リサーチ学会
2021年 秋季研究発表会

1-A-4

半正定値計画問題に対する下三角低ランク行列分解を利用した等価な非線形計画問題について
05000141
05000235
01704632

1.

京都大学
ヤフー株式会社
京都大学
京都大学

*山川雄也
池上哲哉
福田エレン秀美
山下信雄

はじめに
本研究では，次の半正定値計画問題を扱う．

(SDP)

MinimizenX∈S⟨C, X⟩

subject to A(X) = b, X ⪰ O

ここで，Sn は n 次実対称行列全体の集合を表すとし，X ⪰ O は行列 X が半正定値であることを意味する．また，関数 A : Sn → Rm は A(X) :=[⟨A1 , X⟩, . . . , ⟨Am , X⟩]⊤ で定義されるとし，行列C, A1 , . . . , Am ∈ Sn およびベクトル b ∈ Rm は与えられているとする．
SDP は，線形計画問題や二次錐計画問題などを含む広いクラスの最適化問題であり，多くの分野で応用を持つことで知られる．また，SDP を解くため，これまで多くの解法が提案されてきた．中でも，主双対内点法は最も主要な解法の一つとして知られ，多くのソルバーで実装されている．しかし，小中規模の問題に対しては高精度な解を得られると言われているが，大規模な問題に対しては，解の近傍においてニュートン方程式の計算が不安定になるという欠点も指摘されている．
行列のサイズが大きく（n が大きく），制約の本数が少ない（m が小さい）大規模な SDP を解くために，Burer et al [1, 2] は，SDP と等価な非線形計画問題（NLP）を提案した．この既存モデルは，行列 X ∈ Sn を矩形行列 R ∈ Rn×r の積
RR⊤ で置き換えることで SDP の半正定値制約を取り除き，一般的な NLP へと帰着される．さらに，r ≥ max{r ∈ N : r(r + 1)/2 ≤ m} を満たせ
ば，既存モデルは SDP と等価となることも示しており，r の値によっては SDP よりも次元が小さい問題となるというメリットがある．しかし，このモデルは狭義局所的最小解が存在しないことから，最適性の二次の十分条件が成り立たないため，局YAMAKAWA Yuya
IKEGAMI Tetsuya
FUKUDA Ellen Hidemi
YAMASHITA Nobuo

所的に速い収束性を持つ手法が有効に機能しない可能性がある．また，m の値が十分に小さくなければ，提案モデルの次元は SDP の次元より大きくなる可能性もある．
本発表では，Burer らの提案モデルを改良し，SDP と等価な NLP を提案する．既存の Burer らのモデルでは Rn×r を決定変数の空間としているが，提案モデルでは Rn×r に含まれる下三角行列全体の集合を決定変数の空間とする．従って，既存モデルに比べて変数の次元は小さくなり，また，m の値が大きい場合でも，元の SDP の次元を超えることはない．さらに，決定変数の空間を制限したことで，適切な仮定の下での狭義局所的最適解の存在を理論的に保証することが可能となる．これにより，二次法などの手法を用いることで，解への速い収束性が期待される．ここでは，提案モデルに対して逐次二次計画法（SQP 法）も提案し，数値実験によりその有効性を示す．

2.

SDP を解くための既存モデル

Burer et al [1] は，SDP を直接解く代わりに，以下のランク制約付き SDP を解くことを考えた．
MinimizenX∈S(LRSDPr )⟨C, X⟩

subject to A(X) = b, X ⪰ O,rank(X) ≤ r

この問題は，r ≥ rm := max{r ∈ N : r(r + 1)/2 ≤m} のとき，SDP と等価となることが知られている[1, Theorem 1]．ここで，X ⪰ O かつ rank(X) ≤ rを満たす行列 X ∈ Sn は，ある矩形行列 R ∈ Rn×r
を用いて X = RR⊤ と分解されるので，LRSDPrは以下のように書き換えることができる．

Minimize(NSDPr )R∈Rn×r⟨C, RR⊤ ⟩subject to A(RR⊤ ) = b

NSDPr は，以下で述べるような SDP と関連した重要な性質を持つ．
命題 1 ([1]) R∗ は NSDPr の停留点，つまり，あるv ∗ ∈ Rm が存在して，(C − A∗ (v ∗ ))R∗ = 0 を満た∗ Aすとする．ただし，A∗ (v ∗ ) := v1∗ A1 + · · · + vmmである．もし，C−A∗ (v ∗ ) ⪰ O であれば，R∗ (R∗ )⊤は SDP の最適解である．
2
命題 2 ([2]) r ≥ rm+1 であり，R∗ は NSDPr の局所最小解とする．もし，SDP は唯一解を持つならば，それは R∗ (R∗ )⊤ で与えられる．
2
命題 1 および命題 2 で述べられているように，適切な条件を満たしていれば NSDPr を解くことでSDP の解を得ることができる．しかし，NSDPr の局所最小解 R に対して，任意の直交行列 Q を R の右から掛けた行列 RQ もまた NSDPr の局所最小解となる．従って，Q をうまく選べば，RQ は R にいくらでも近づけることができるため，任意の局所最小解 R は狭義局所的最小解にはならない．つまり，二次の十分条件が成り立たないため，二次法などの速い収束性を持つ手法を適用しても，その性能を十分に発揮できない可能性がある．

3.

提案モデルとその性質

以下では，Rn×r に含まれる下三角行列全体の集合を Ln×r で表す．まず，半正定値行列の下三角行列を用いた分解に関する命題を与える．
命題 3 X ⪰ O かつ rank(X) = r < n を満たす行列 X ∈ Sn に対して，ある S ∈ Ln×r が存在して，X = SS ⊤ を満たす．
2T-NSDPr は，NSDPr にはない複数のメリットがある．一つは，NSDPr に比べて，決定変数の空間の次元が，r(r − 1)/2 次元少なくなる．また，
r = n のとき，NSDPr の決定変数の次元は元のSDP の次元を超えてしまうが，T-NSDPr は最大でも n(n + 1)/2 次元であるため，SDP の次元を超えることはない．さらに，決定変数の空間を制限したことで，以下で述べるように適切な条件の下で狭義局所的最適解を持つことが示される．
定理 1 SDP は唯一解 X ∗ を持ち，以下を満たすと仮定する．
[]∗ OX
1X∗ =, X1∗ ∈ Sℓ , rank(X1∗ ) = ℓO O
また，r ≥ rm+1 であり，S ∗ ∈ Ln×r が T-NSDPrの局所最適解であるとする．このとき，S ∗ ∈ Ln×rは T-NSDPr の 狭義局所最適解となる．
2
ここで，定理 1 では X ∗ に対してブロック対角行列であることを要求しているが，これは一般性を失わず仮定することができる．定理 1 により，T-NSDPrに対して二次法などの手法を適用すれば，最適解への速い収束性が期待される．本研究では，最適化手法として SQP 法を提案する．ただし，NSDPrおよび T-NSDPr は，ともに次の二次等式制約付き二次計画問題へと変形可能であるため，この問題に対して SQP 法を提案し，数値実験を行う．

Minimizex∈Rd⟨Hx, x⟩subject to ⟨Gj x, x⟩ = bj , j = 1, . . . , m
命題 3 を利用すると，LRSDPr は NSDPr とは異ddなる次の最適化問題へと書き換えることができる． ただし，d ∈ N，H ∈ S および Gj ∈ S (j =1, . . . , m) は，NSDPr や T-NSDPr に応じて決定Minimize ⟨C, SS ⊤ ⟩n×r
される．提案アルゴリズムの詳細および実験結果
S∈L(T-NSDPr )subject to A(SS ⊤ ) = bについては当日発表する．

参考文献
上記の T-NSDPr が，本研究で提案するモデルであり，NSDPr で見られるような類似の性質を持つ． [1] Burer, S., Monteiro, R.D.C.: A nonlinear programming algorithm for solving semideﬁnite
命題 4 S ∗ は T-NSDPr の停留点，つまり，ある∗m∗∗∗programs via low-rank factorization. Math.
w ∈ R が存在して，(C − A (w ))S = 0 を満∗∗Program. Ser. B 95, 329–357 (2003)
たすとする．もし，C − A (w ) ⪰ O であれば，S ∗ (S ∗ )⊤ は SDP の最適解である．

2[2] Burer, S., Monteiro, R.D.C.: Local minimaand convergence in low-rank semideﬁnite pro命題 5 r ≥ rm+1 であり，S ∗ は T-NSDPr の局所gramming. Math. Program. Ser A 103, 427–最小解とする．もし，SDP は唯一解を持つならば，∗∗⊤444(2005)
それは S (S ) で与えられる．
2