数理解析研究所講究録
第 1829 巻 2013 年 80-8780

線形計画問題に対する主双対内点法における相補項の減少を考慮した変数ごとのステップサイズの計算
Computation of Indexwise Stepsizes Considering Reduction ofComplementarity Terms in a Primal-Dual Interior-Point
Method for Linear Problems
小崎敏寛 (Toshihiro Kosaki)*

概要

連続最適化問題に対するアルゴリズムの理論に基づいた高速化を考える．具体的には，線形計画問題に対する主双対内点法のステップサイズを工夫する．半正定値計画問題と二次錐計画問題にも触れる．

1

はじめに

この論文では，連続最適化問題に対するステップサイズつき反復解法を考える．反復解法において適切なステップサイズの決定は重要である．例えば damped Newton’smethod[14] や $SOR$ 法 (SuccessiveOver-Relaxation method)[5, 14, 15] など．

線形計画問題に対する内点法においては，水野 [13] に，「線形計画問題を解く内点法を実際にプログラミングする場合には，計算効率を高めるために以下のことを考慮することが大事である．
」

1. 主問題を解く主内点法，双対問題を解く双対内点法，あるいは主問題と双対問題を同時に解く主双対内点法のいずれを使うか？

2. 初期点をどうするか 9
3. 探索方向の求め方．
4. ステップサイズの決め方．

5. 連立 1 次方程式の解法．とある．この論文では，4 のステップサイズの決め方に着目する．

線形計画問題に対する主双対内点法の実装では，主問題の変数と双対問題の変数で異なるステップサイズをとる [2,4,10,18].

そうすることで収束を加速できる．この考えを発展させて，変数ごとに異なるステップサイズをとることを考える．変数ごとに分けて，異なるステップサイズをとることを許す手法をスペクトル法 (Spectral method) と名付ける．線形計画問題に対する主双対内点法では，変数ごと*toshihirokosaki@gmail.com

81にステップサイズを計算しても，他の計算量 (ほとんどを占めるのは Cholesky 分解) と比較して，計算量は少ない．
小崎 [11] では，変数ごとにステップサイズを計算$\alpha_{i}^{p*}=\min\{1, \max\{\alpha_{i}^{p}:x_{i}+\alpha_{i}^{p}\triangle x_{i}\geq 0\}\}i=1, \ldots, n$

した．双対変数のステップサイズも同様にした．この論文では，相補項$x_{i}z_{i}$(1)が減少するようにステップサイズを計算する手法を提案する．

この論文の構成は以下のようである．2 節でスペクトル法について説明する．3 節において解析の対象とする内点法について説明する．4 節で，具体的に内点法にスペクトル法を適用する．5 節で考察と今後の課題を述べる．

2

スペクトル法

この節では，スペクトル法 (spectral method) について説明する．連続最適化問題に対するステップサイズ付き反復法を考える． 反復目を考えると，探索方向として，その方向にステップサイズ$k$$\triangle x^{k}$$\alpha^{k}$

進む．式で表すと，(2)$x^{k+1}=x^{k}+\alpha^{k}\triangle x^{k}$となる．ステップサイズを変数ごとに異なる値を許すことを考える．式で表すと，ステップサイズを$\alpha_{\iota’}^{k}(i=1, \ldots, n)$として，(3)$x_{i}^{k+1}=x_{i}^{k}+\alpha_{i}^{k}\triangle x_{i}^{k}(i=1, \ldots, n)$となる．このアルゴリズムの枠組みをスペクトル法 (spectral method)と呼ぶことにする．

スペクトル法の枠組みに基づくアルゴリズムは次のようになる．

スペクトル法step 1 $k=0$ とする．初期点 $x_{i}^{0}(i=1, \ldots, n)$ が与えられる．
step 2 終了条件をみたせば終了する．

step 3 方向$\triangle x_{i}^{k}(i=1, \ldots, n)$を計算する．

step 4 ステップサイズ $\alpha_{i}^{k}(i=1, \ldots, n)$ を計算する．
step 5$(\begin{array}{l}x_{1}^{k+1}|x_{n}^{k+1}\end{array})=(\begin{array}{l}x_{1}^{k}|x_{n}^{k}\end{array})+(\begin{array}{l}\alpha_{1}^{k}\triangle x_{1}^{k}|\alpha_{n}^{k}\triangle x_{n}^{k}\end{array})$と更新する．

step 6 $k=k+1$ とする．

(4)

82
step 7step 2 に戻る．

対象とする問題とアルゴリズムの特徴は次のようになる．

1. 変数ごとに異なるステップサイズ
2. 変数

$x$

は有限次元である．

3. 変数$x$は連続変数である．

4. 方向

3

$\triangle x_{i}^{k}$を計算する反復解法である．

$\alpha_{i}^{k}$の計算と比較して，ステップサイズ$\alpha_{i}^{k}$が簡単に計算できる．

内点法
この節では，線形計画問題に対する主双対内点法 [7,9,18] について説明する．標準形の線形計画問

題 (P) を考える．

minimize

ただし，$x\in\Re^{n}$は変数，$A\in\Re^{m\cross n},$$c^{T}x$$b\in\Re^{m}$subject to $Ax=bx\geq 0$ .

(P)$y\in\Re^{m},$と $c\in\Re^{n}$ は定数．双対問題 (D) は，$z\in\Re^{n}$を変数として，maximize$X$ を対角要素をとなる．最適条件は，$b^{T}y$$x$

subject to $A^{T}y+z=cz\geq 0$(D)とする対角行列として，$Ax=b, x\geq 0, A^{T}y+z=c, z\geq 0, Xz=0$(0)となる．主双対内点法は，非負制約を強くみたす初期点から，正値性をみたしながら，主変数と双対変数を更新して，最適条件をみたすアルゴリズムである．

実際に使われる，勝手な内点を初期点とできるインフィージブル内点法 [2,8,10] を考える．そのアルゴリズムで使用する$k$

反復目の Newton 方向$\Delta w:=(\triangle x, \triangle y, \triangle z)$$A\Delta x$$=$$b-Ax^{ん}$は次の方程式系の解として得られる．

，(5a)$A^{T}\triangle y+\triangle z = c-A^{T}y^{k}-z^{k}$$Z\Delta x+X\Delta z = \gamma\mu e-Xz^{k}$

ただし $X$ と $Z$ は$x^{k}$と$z^{k}$を対角要素とする対角行列，(5b),,$\gamma\in[0,1)$(5c)はパラメータ，$\mu=\frac{x^{k^{T}}z^{k}}{n},$$e$は要素が全て 1 のベクトル．

計算時間の削減について考える．主双対内点法では，計算時間の大半は，(5) を変形した正規方程式(6)$ADA^{T}\triangle y=p$を解くのに使われる [10, 18].
するベクトル．

計算時間について，$D$は反復ごとに変化する対角要素が正の対角行列， は反復ごとに変化$p$83(総計算時間) (一反復あたりの計算時間)$=$$\cross$(反復回数)と見積もれる．計算時間の削減をするには，右辺の項のどちらかを削減することを考える．一反復あたりの計算時間を削減する手法としては，(6) を解く際の疎性の利用がある．一方，反復回数を削減する手法としては，プレディクタコレクタ法 [12] や多重センタリング法 [6] がある．スペクトル法は反復回数の削減を目的とする．
命題 1 ステップサイズ

して，ステップサイズ$\alpha$$\alpha$について二次の項を考えなければ，$x^{T}z$が 1(フルステップ) のとき$\gamma x^{T}z$はステップサイズ$\alpha$に比例して減少となる．

証明次の等式が成り立っ．
$(x+\alpha\triangle x)^{T}(z+\alpha\triangle z)=x^{T}z+\alpha(z^{T}\triangle x+x^{T}\triangle z)+\alpha^{2}\triangle x^{T}\triangle z$(7)$=x^{T}z(1+\alpha(\gamma-1))+\alpha^{2}\Delta x^{T}\Delta z$

二つ目の等号で式 (5c) を使用した．最後の式より命題が成り立っ．口主問題の残差を $r_{p}:=b-Ax$ , 双対問題の残差を $r_{d}:=c-A^{T}y-z$ として，残差を $r:=(r_{p}, r_{d})$ とする．

命題 2 残差$r\ovalbox{\tt\small REJECT}$

ま，ステップサイズ$\alpha$に比例して減少して， が 1 のときに$\alpha$$0$となる．

$A(x+\triangle x)=b$ となるように$r_{p}:=b-Ax$ を残差ベクトノレとする．
証明主変数について考える．

$\triangle x$

は決められる．すると $A\Delta x=b-Ax=r_{p}$ が成り立っ．次の反復の残差について$b-A(x+\alpha\triangle x)=b-Ax-\alpha A\triangle x$(8)$=(1-\alpha)r_{p},$より命題の関係が成り立つ．双対変数も同様に成り立っ．よって残差$r$についても成り立っ．口二つの命題から，ステップサイズは，1 以下でかっ内点であるような，できるだけ大きい値をとる方が良いと考える．

4

スペクトル法の適用例
この節では，スペクトル法を具体的なアルゴリズム (内点法) に適用する．

4.1

線形計画問題 (1)

線形計画問題に対する主双対内点法について考える．主変数 について考える．既存 [10] のステップ$x$

サイズの決め方は，$\alpha^{*}:=\min\{1, \alpha_{c}\cross\max\{a :x+\alpha\triangle x\geq 0\}\}$.

(9)

これに対して，提案するステップサイズの決め方は，変数ごとに異なる値をとることを特徴とする$\alpha_{i}^{*}:=\min\{1, \alpha_{c}\cross\max\{\alpha_{i}:x_{i}+\alpha_{i}\triangle x_{i}\geq 0\}\}(i=1, \ldots, n)$.

ただし，。は，内点であるようにするために使われる，1 よりわずかに小さい定数．例えば(10)$\alpha$など．

$\alpha$。

$=0.99995$

84

表 1: 輸送問題に対する内点法の反復回数と計算時間

次の命題により，二つの決め方の間の関係が分かる．
命題 3

mjn

$\{\alpha_{i}^{*}\}=\alpha^{*}.$

この命題より，既存の決定法では一つでも極端に小さなステップサイズがあるとその値がステップサイズになることが分かる．一方，提案するステップサイズの決定法は，変数ごとにステップサイズを決定するので，極端に小さなステップサイズがあっても他の変数のステップサイズは大きくとれる．
双対変数$z$についても同様．ただし， のステップサイズをどう決めるかの問題がある． のステップサイズを$z$のステップサイズの最小値とする．

4.1.1

$y$

$y$

輸送問題

$M$ を供給地点の数，$N$ を需要地点の数とする．この問題は，ヒッチコック型の輸送問題を考える．
変数の線形計画問題となる．この問題に対して主双対内点法を適用する．詳細は，小崎 [11] を参$MN$照．初期点を $(x^{0}, y^{0}, z^{0})=(100e, 0,100e)$ とする．計算時間は，IPMI を既存のステップサイズ，IPM2を提案したステップサイズとして，表 1 のようになる．

4.2

線形計画問題 (2) 相補項の最小値の場合分け

線形計画問題に対する主双対内点法の変数の更新にあたり，変数ごとにステップサイズを計算することを考える．そのときに相補項 (complementarity term) xizi を正 (実際は非負) の値の範囲で小さくでの最小値をするようにする．この計算は (二次の係数が正，負，零の) 二次関数の範囲求める問題になる．ただし，ステップサイズは から増やしていって，もし関数値が一度 0 になってしまったら相補項はその値 (すなわち ) をとるとする．この計算は，相補項と実行不能性の 2 目的を減少$(0\leq\alpha\leq 1)$

$O$

$O$

させる， 個の 2 目的最適化問題とみなせる．
$n$

次の関数

$f_{i}(\alpha),$$i=1,$ $\ldots,$ $n$ を考える．
$f_{i}(\alpha);=(x_{i}+\alpha\triangle x_{i})(z_{i}+\alpha\triangle z_{i})$(11)$=x_{i}z_{i}+\alpha(z_{i}\Delta x_{i}+x_{i}\triangle z_{i})+\alpha^{2}\Delta x_{i}\Delta z_{i}.$$f_{i}(0)=x_{i^{Z}i}>0$ とする．
ただし，この計算による相補項の値は次のようになる．

85
4.2.1の場合 (線形関数の場合)$\triangle x_{i}\triangle z_{i}=0$$z_{i}\triangle x_{i}+x_{i}\triangle z_{i}=0$のとき xizi ( $\alpha=1$ で$z_{i}\triangle x_{i}+x_{i}\triangle z_{i}>0$のとき xizi $(\alpha=0$ で$z_{i}\triangle x_{i}+x_{i}\triangle z_{i}<0$のとき$x_{i}z_{i}$$\alpha^{*}>1$$\Delta x_{i}\Delta z_{i}>0$$\alpha^{*}<0$は大きい方が良いので))$)$$\alpha^{*}:=-\overline{z_{i}\triangle x_{i}+x_{i}\Delta z_{i}}$$\alpha^{*}\leq 1$

4.2.2$(\alpha$として，のとき $0(\alpha=\alpha^{*}$ で$)$のとき $f_{i}(1)(\alpha=1$ で(12)$)$の場合 (二次の係数が正の場合)のとき xizi $(\alpha=0$ で$)$$0\leq\alpha^{*}\leq 1$のとき$f_{i}(\alpha^{*})\leq 0$のとき$0( \alpha=x^{*}:=\frac{-z_{i}\triangle x_{i}-x_{i}\triangle z_{i}-\sqrt{(z_{i}\triangle x_{i}+x_{i}\triangle z_{i})^{2}-4(\triangle x_{i}\triangle z_{i})x_{i}z_{i}}}{2\triangle x_{i}\triangle z_{i}}$のとき$f_{i}(\alpha^{*})(\alpha=\alpha^{*}$$f_{i}(\alpha^{*})>0$$\alpha^{*}>1$

4.2.3

でで(13)$)$のとき$\triangle x_{i}\triangle z_{i}<0$$\alpha^{*}<1/2$$f_{l}\prime(1)>0$のとき $f_{i}(1)(\alpha=1$ で$f_{i}(1)\leq 0$のとき $0(\alpha=x^{*}$ で(14)の場合 (二次の係数が負の場合)のとき$f_{i}(1)\leq 0$$\alpha^{*}\geq 1/2$$)$$)$$f_{i}(1)>0$ ならば $f_{i}(1)(\alpha=1$ で4.3$)$のとき xizi $(\alpha=0$ でならば $0(\alpha=x^{*}$ で$)$(15)$)$$)$

変数がブロック対角の半正定値計画問題

各変数ごとでなく，複数の変数ごとにステップサイズを計算する場合を考える．ブロック対角の行列変数$(\begin{array}{lll}X_{1} \ddots X_{n}\end{array})$(16)を持つ半正定値計画問題 (SDP)[3,10, 16, 17] を考える．このときブロックごとにステップサイズを決定し，$(\begin{array}{lll}X_{1}^{k+1} \ddots X_{n}^{k+1}\end{array})=(\begin{array}{lll}xf+\alpha_{1}\triangle X_{1} \ddots X_{n}^{k}+\alpha_{n}\triangle X_{n}\end{array})$と更新できる．

(17)

86
4.4

二次錐の直積を変数とする二次錐計画問題$N$ 個の二次錐の直積を変数とする二次錐
複数の変数ごとにステップサイズを計算する場合を考える．

計画問題 (SOCP)[1,3] を考える．
$\mathcal{K}_{1}:=\{x_{1};=(x_{0}^{1}, x_{1}^{1}, \ldots, x_{n_{1}}^{1}):x_{0}^{1}\geq\sqrt{(x_{1}^{1})^{2}++(x_{n_{1}}^{1})^{2}}\}$

:

(18)

$\mathcal{K}_{N}:=\{x_{N}:=(x_{0}^{N}, x_{1}^{N}, \ldots, x_{n_{N}}^{N}):x_{0}^{N}\geq\sqrt{(x_{1}^{N})^{2}++(x_{n_{N}}^{N})^{2}}\}.$

として，変数を(19)$x:=(x_{1}, \ldots, x_{N})\in \mathcal{K}:=\mathcal{K}_{1}\cross\cdots\cross \mathcal{K}_{N}$とする．このとき，各二次錐ごとに異なるステップサイズをとることができる．

5

考察と今後の課題
4.1 について考察する．表 1 より，問題のサイズが大きくなるにつれて，反復回数の減少に成功している．計算時間も同様に減少している．

4.2 について考察する．変数ごとにステップサイズを計算するとき (4.2), 相補項の減少を考慮すると，主双対で同じステップサイズになってしまう．一方，相補項を考慮せずに変数ごとにステップサイズを次の点を計算する (4.1) と，主・双対で異なるステップサイズがとれる．相補項について，尋と$z_{i}^{+}$として，$x_{i}^{+}z_{i}^{+}=0$のときはステップサイズを$\alpha_{c}\alpha^{*}$

やcx 例えば$*$$\alpha$$($$\alpha_{c}:=0.99995$ など$)$として，内点性を維持する．実装の観点では，上記の計算でステップサイズが のときは， の増加を許して残差を減少させるように，ステップサイズを大きくとった方が良いかもしれない．このアルゴリズムの問題$0$$x_{i}z_{i}$点としては，xizi は小さくなるが， が小さいと，残差をあまり減少できない．残差が単調に減少しな$\alpha$いと予想される．インフィージブル内点法になるので，解析が大変になる．また，問題のクラスによって，4.2 の場合分けの中で起こらない場合がある可能性がある．その場合を明らかにすることで，解析の負担を減らしたい．今後の課題は，数値実験を行い提案手法の有効性を確かめることである．
今後の課題として，半正定値計画問題と二次錐計画問題についても数値実験を行い，提案手法の有効性を確かめたい．

参考文献[1] F. Alizadeh and D. Goldfarb, “Second-Order Cone Programming,” Mathematical Programming,Vol. 95, 3-51, 2003.
[2] E. D. Andersen, J. Gondzio, C. M\’esz\’aros and X. Xu, “Implementation of Interior-Point Methods
for Large Scale Linear Programs,” Interior Point Methods of Mathematical Programming, ed. $T.$Terlaky, Kluwer Academic Publishers, Dordrecht, 189-252, 1996.
[3] A. Ben-Tal and A. Nemirovski, “Lectures on Modern Convex optimization: Analysis, Algorithms, and Engineering Applications,” SIAM, Philadelphia, 2001.

87[4] R. Fourer, “optimization Methods III. Solving Linear Programs by Interior-Point Methods,”

Lecture Note, Northwestern University, 2005.
[5] G. H. Golub and C. F. V. Loan, “Matrix Computations, Third edition,” Johuns Hopkins University Press, Baltimore, 1996.
[6] J. Gondzio, “Multiple Centrality Corrections in a Primal Dual Method for Linear Programming,”

Computational optimization and Applications, Vol. 6, 137-156, 1996.
[7] J. Gondzio, “Interior Point Methods 25 Years Later,” European Journal of Operational Research,

Vol. 218, 587-601, 2012.
[8] M. Kojima, N. Megiddo and S. Mizuno, “A Primal-Dual Infeasible-Interior-Point Algorithm for

Linear Programming,” Mathematical Programming, Vol. 61, 263-280, 1993.

[9] M. Kojima, S. Mizuno and A. Yoshise, “A Primal-Dual Interior-Point Algorithm for Linearprogramming,” Progress in Mathematical Programming, Interior-Point and Related Methods,Springer-Verlag, New York, 29-47, 1989.
[10] 小島政和，土谷隆，水野眞治，矢部博，“内点法，” 朝倉書店，2004.

[11] 小崎敏寛，“輸送問題に対する主双対内点法，” 数理解析研究所講究録 1773: 最適化手法の深化と広がり，107-114, 2012.

[12] S. Mehrotra, “On the Implementation of a Primal-dual Interior Point Method,” SIAM Journal
on optimization, Vol. 2, 575-601, 1992.
[13] 水野眞治，“内点法 (1)-概論$\triangleleft$

オペレーションズ．リサーチ，Vol. 35, 321-326, 1995.

[14] J. M. Ortega and W. C. Rheinbolt, “ Iterative Solution of Nonlinear Equations in Several Variables,” Academic Press, New York, 1970.

[15] 杉原正顯，室田一雄，“線形計算の数理，“ 岩波書店，2009.
[16] M. J. Todd, “Semidefinite optimization,” Acta Numerica, vol. 10, 515-560, 2001.

[17] H. Wolkowicz, R. Saigal and L. Vandenberghe, “Handbook of Semidefinite Programming,”
Kluwer Academic Publishers, 2000.

[lS] S. J. Wright, “Primal-Dual Interior-Point Methods,” SIAM, Philadelphia, 1997.