数理解析研究所講究録
1068 巻 1998 年 171-181

171

自己双対システムを使った零点法
文部省統計数理研究所

水野毒心*(Shinji Mizuno)

1998 年 10 月

Abstract
線形計画問題を実際に内点法で解く場合に重要な問題の–つに、 初期点をいかに求めるかといったことがある。 これにはいくつがのアプローチがあるが、 ここでは、 自己双対システムを使う方法を二つ紹介する。 –方は Ye, Todd, and Mizuno [11] により提案された方法であり、他方は最近 Nesterov, Todd, and Ye [8] により提案された方法である。 これらの方法は、 センターパスを逆方向に追跡するといったように、一見全く異なるように見える。 Mizuno and Todd [5] は、 これら二つの方法の関連を詳細に調べた。

その結果の–部についても紹介する。

1 、はじめに線形計画問題を解く内点法は、 Karmarkar [1] により提案されて以来、活発に研究されてきた。 線形計画問題を実際に内点法で解く場合に重要な問題の–つに、初期点をいかに求めるかといったことがある。 これにはいくつかのアプローチがあり、大きな係数を使った人工問題を作る方法、初期点をまず求めて (Phae I) から問題を解く (Phase II) 方法、勝手な正の初期点を使うインフィージブル内点法などがある。 ここでは、それらとは異なり、 自己双対システムを使う方法を紹介する。 この方法は、 Ye, Todd, and Mizuno[11] により提案され| その後\supset Xu, Hung, and Ye [9], Xu and Ye [10] らによりさらに研究された。 この方法の特徴には、勝手な初期内点を使うことができる、 反復回数が多項式オーダで理論的におさえられている、問題の実行不能性を判定できる、 実行可能な*〒 106-8569

港区南麻布 4-6-7, mizuno@ism .ac.jp

172

場合には解を計算できる、 big$\mathrm{M}$と呼ばれる大きな係数を必要としないといったことがある。

本論では、二つの異なった自己双対システムを使った内点法を紹介する。 –方は Ye,Todd, and Mizuno [11] により提案された方法であり、 自己双対線形計画問題を使う。他方は最近 Nesterov, Todd, and Ye [8] により提案された方法である。 これらの方法は、センターパスを逆方向に追跡するといったように、一見全く異なるように見える。 Mizunoand Todd [5] は、 これら二つの方法の関連を詳細に調べた。 その結果の–部についても紹介する。

2線形計画問題と双対問題
次の標準形の線形計画問題を考える。
$(P)$

minimize$c^{T}x$subject to $Ax=b$ ,ここで、 $A,$ $b,$$c$

は $m\cross n$ 行列、$x\geq 0$.

は与えられたデータであり、適当な自然数 $m$ と $n(m\leq n)$ に対して、 $A$$b$

は $m$ 次元ベクトル、$c$は $n$ 次元ベクトルである。 また、$x$は $n$ 次元の変数ベクトルである。行列 $A$ のランクが $m$ であると仮定する。一般に線形計画問題は、上記のように線形の等式と不等式であらわされた制約条件を満たす解呼ばれる) のなかで、 線形の目的関数値を最小化$x$(実行可能解と(あるいは最大化) する解 (最適解と呼ばれる) を求める問題である。 最適解での目的関数値を最適値という。

上で定義した標準形の問題を主問題とするとき、その双対問題は、次のようにあらわされる。
$(D)$maximize$b^{T}y$subject to$A^{T}y+s=c$ ,ここで、 y は $m$ 次元の変数ベク トル、.

$s$$s\geq 0$.

は $n$ 次元のスラック変数ベクトルである。

線形計画問題の主問題と双対問題に関する基本的性質をいくかまとめて示す。
双対問題の双対問題は、主問題と –致する。 したがって、以下の性質は主問題と双対問題を入れ替えても成立する。

.

$\bullet$

主問題に最適解が存在すれば、双対問題にも最適解が存在し、その最適値は等しい。

主問題が実行可能であるがその最適解が存在しないならば、双対問題は実行不能である。

173$\bullet$

主問題が実行不能であるならば、双対問題は実行可能で最適解を持たないか、 あるいは実行不能である。
.
.
. .

.

.. . .

$|$$\cdot$$\mathrm{c}$$\bullet$.

.

.

主問題と双対問題が実行可能であれぱ、 ともに最遙解を持ち、任意の最適解において相補性条件が成立する。 ここで、相補性条件とは、主問題の非負変数

題の非負変数$s$$x$と双対問の問に条件

or$x_{i}=0$

for each$s_{i}=0$$i$,

あるいは別な表現をすると$x_{s=}\mathrm{o}$が成立することである。 ただし、

$X=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(X)$は、ベクトル$x$の要素を対角要素とする対角行列をあらわす。
$\bullet$

主問題と双対問題が実行可能であれぱ、強相補性条件をみたす最適解 (強相補解と呼ぶ) が存在する。 強相補性条件とは、 すべての要素$x_{i}>0$and$x_{i}=0$

and$i$に対して$s_{i}=0$または$s_{i}$$>0$が成立することである。 この条件は$X_{S=}0$,$x+s>0$とあらわすこともできる。
$\bullet$

主問題と双対問題の実行可能解が相補性条件をみたせば、それぞれの最適解である。

主問題と双対問題の問のこれらの性質を利用することにより、内点法には、主問題を解く主内点法以外にも、 双対問題を解く双対内点法、 主問題と双対問題を同時に解く主双対内点法などがある。 本論では、 それらとは異なる自己双対システムを使う内点法を紹介する。 その方法も、 上記の主問題と双対問題の問の性質をうまく利用する。

1743自己双対線形計画問題
前節で定義した線形計画問題 (P) とその双対問題 (D) に対して、Ye, Todd, and Mizuno[11] は、 次の線形計画問題を導入した。

minimize$(SD_{1})$$h^{0}\theta$

subject to$Ax$$-A^{T}y$ここで、 適当な初期点$-b\tau$$+b^{0}\theta$$-c^{0}\theta$$+c\tau$$b^{T}y$$-c^{T}x$$-(b^{0})\tau y$$+(c^{0})^{T}x$$+g^{0}\tau$$x\geq 0$$\tau\geq 0$$(y^{0}, x^{0}, \tau, \theta^{0}0, S^{0}, \kappa^{0})$$-S$$-g^{0}\theta$$-\kappa$$0$,$=$$0$,$=$$0$,$=$$s\geq 0$$\kappa\geq 0$$-h^{0}$

,.

に対して、

,

$b^{0}$$:=$$b\tau^{0}-Ax^{0}$$c^{0}$$:=$$c\tau^{0}-A\tau y0-S0$$g^{0}$$:=$$b^{T}y^{0_{-}}c\kappa^{0}T_{X}0_{-}$$h^{0}$$:=$$(x^{0})^{T}S+\tau\kappa 000$,(1),である。初期点は、条件 $(x^{0}, \tau^{00}, s, \kappa^{0})>0$ と $\theta^{0}=1$ をみたすとする。 (は特に何も仮定しな》。 また、文献 [11] では、 さらに $\tau^{0}=1$ とこれらの条件から、 初期点$=$$(y^{000}, X, \mathcal{T}, \theta^{0}, S^{0}, \kappa^{0},)$$\kappa^{0}=1$

において、 問題$y^{0}$の値についても仮定している。)$(\mathrm{S}\mathrm{D}_{1})$のはじめの 3 つの等式と不等式は明らかに成立し、 4 番目の等式も$-(b0)\tau y0_{+}(_{C}0)T0gX+\tau^{0}0$$=$$-(b_{\mathcal{T}^{0_{-}}}A_{X^{0}})^{T}y^{0}+(c\tau^{0_{-}}A^{T}y^{0_{-}}s0)^{T}x0+(b^{\tau_{y}0_{-C}\tau 0}X-\kappa^{0_{)\mathcal{T}^{0}}}$$=$$-(x^{0})\tau \mathrm{o}0s-\tau\kappa 0$$=$$-h^{0}$

により成立する。 したがって、 この初期点は線形計画問題

問題$(\mathrm{S}\mathrm{D}_{1})$$(\mathrm{S}\mathrm{D}_{1})$の実行可能解である。の特徴は、 制約条件の係数行列が歪対称 (skew-symmetric) となっていることである。 このことから、 この問題の双対問題は、適当に変換を施せば主問題と –致する。 すなわち、$(\mathrm{S}\mathrm{D}_{1})$は自己双対線形計画問題である。

補題 1 自己双対問題 $(SD_{1})$ は最適解を持ち、 その最適値は$(y^{*****}, X, \mathcal{T}, 0, s, \kappa)$

は、相補性条件$X^{*}s^{*}=0$,$0$である。任意の最適解

175$\tau^{*}\kappa^{*}=0$をみたす。 ここで、

$X^{*}=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(x)*$は対角行列をあらわす。 また、 強相補性条件$X^{*}.s^{*}=0$,.

,$\tau^{*}\kappa^{*}=0$$x^{*}+s^{*}>0$,$\tau^{*}+\kappa^{*}>0$をみたす最適解が存在する。
証明 :自己双対問題$(\mathrm{S}\mathrm{D}_{1})$の双対問題は、$(\mathrm{S}\mathrm{D}_{1})$

その目的関数は-h0\theta である。) したがって、 問題と –致する。 (ただし、最大化問題でとその双対問題が実行可能であ$(\mathrm{S}\mathrm{D}_{1})$るから、 それぞれの問題の最適解が存在する。 また、最適値は、 主問題と双対問題で等しく、 その符号が異なることから、 ともに$0$である。線形計画問題の主問題と双対問題の最適解が椙補性条件をみたし、強相補解が存在することから、 自己双対問題の最適解にも同様なことがいえるので、 補題に述べたことが成立する。

口補題 2 自己双対問題 $(SD_{1})$ の強相補解を $(y^{*}, x^{*}, \tau^{*}, 0, s\kappa)*,*$ とする。 このとき、 $\tau^{*}>0$または $\kappa^{*}>0$ である。 もし、 $\tau^{*}>0$ ならば$x^{*}/\tau^{*}$と $(y^{*}, s^{*})/\tau^{*}$ は、 それぞれ主問題 $(P)$と双対問題 $(D)$ の最適解である。 もし、 $\kappa^{*}>0$ ならば、主問題 $(P)$ あるいは双対問題$(D)$ の少なくとも–方が実行不能である。

証明 : まずはじめに、 $\tau^{*}>0$ とする。 このとき、問題を代入し、両辺を\tau *で除することにより、$x^{*}/\tau^{*}$(D) の実行可能解である。 そして、と$x^{*}/\tau^{*}$$(\mathrm{S}\mathrm{D}_{1})$の制約式において、 $\theta=0$と $(y^{*}, s^{*})/\tau^{*}$ は、主問題 (P) と双対問題$s^{*}/\tau^{*}$

が相補性条件をみたすので、最適解である。

つぎに、 $\kappa^{*}>0$ であるとする。 このとき、 相補性条件より、 $\tau^{*}=0$ である。 制約条.

件と $\tau^{*}=0,$ $\theta^{*}=0$ より、$Ax^{*}$$=$$0$$-A^{T}y^{*}-S*$$=$$0$$b^{T}y^{*}-C-\kappa^{*}\tau_{X}*$$=$$0$が成立する。 この 3 番目の式より、$\kappa^{*}=b^{T\tau}y^{*}-cx^{*}>0$176である。 したがって、 $b^{T}y^{*}>0$ または $c^{T}x^{*}<0$ である。 このとき、 $b^{T}y^{*}>0$ ならば主問題 (P) が実行不能であり、$<0$ ならば双対問題 (D) が実行不能である。実際、 も$c^{T}x^{*}$.

し主問題 (P) が実行可能ならば (実行可能解を$0$$\overline{x}$とすれば)、 $A^{T}y^{*}+s^{*}=0$ から$=$$(A_{\overline{X}}-b)\tau_{y}*$$=$$-(s^{*})\tau-\overline{x}b^{T}y^{*}$となるので、 $b^{T}y^{*}=-(s^{*})^{T_{\overline{X}}}\leq 0$ であり、双対問題 (D) が実行可能ならば (実行可能解を$(\overline{y},\overline{s})$とすれば)、$Ax^{*}=0$ から$0$$=$$=$$(A^{\tau_{\overline{y}-}T*}+\overline{S}C)x$$\overline{s}x^{*}-\tau CX^{*}\tau$となるので、 $c^{T_{X}*}=\overline{s}^{T_{X}*}\geq 0$ である。

口

この補題の結果により、 自己双対線形計画問題の強相補解を求めることにより、問題(P) と (D) を解くことができる。 次節では、 このような解を求める方法を紹介する。
本節の最後に、 双対ギャップ xT5+\tau \mbox{\boldmath $\kappa$}の値が\theta の値に比例することを示す。
補題 3 問題 $(SD_{1})$ の任意の実行可能解は、$x^{\tau_{s+\theta}0\tau 00}\mathcal{T}\kappa=((X)S+\mathcal{T}\kappa^{0})$をみたす。

証明 : 問題$(\mathrm{S}\mathrm{D}_{1})$の制約式の両辺に一を乗じると、係数行列が歪対称であ$(y^{T}, x^{T}, \tau, \theta)$ることからほとんどの項が消去され、 次の関係式が得られる$x^{T_{S+\mathcal{T}\kappa=\theta h}0}$.

ここで、 $h^{0}=(x^{0})^{T}S^{0}+\tau^{0}\kappa^{0}$ を代入すれば、補題の関係式が得られる。

この結果からも、 $\theta=0$ ならば、 $(x, \tau)$ と$(s, \kappa)$

口の間に相補性条件が成立することがわかる。

4

自己双対線形計画問題の網点法
自己双対線形計画問題$(\mathrm{S}\mathrm{D}_{1})$の強相補解を求める内点法を紹介する。その方法は、線形計画問題の主双対内点法と多くの点で類似している。

177

まず、

$(\mathrm{S}\mathrm{D}_{1})$の実行可能領域を$:=.$$.F_{1}-${ $(y,$$x,$ $\tau,$$\theta,$$s.’\kappa):(\mathrm{S}\mathrm{D}_{1})^{\text{の実}}.\text{行可能解_{、}}$

ただし\theta $>0$ }とする。 この領域のセンターパス$P_{1}:=\{(y,x, \mathcal{T}, \theta, s, \kappa)\in F1 :X_{S=\mu e}, \mathcal{T}\kappa=\mu, \mu>0\}$とその近傍$N_{1}(\beta)$

$:=$

{

$(y, x,\tau, \theta, s,\kappa.)\in F_{1}$:$||(Xs-\mu e,\mathcal{T}\kappa-\mu)||p\leq\beta\mu$,$\mu=(x^{T}S+\tau\kappa)/(n+1),\mu>0\}$を定義する。 ここで、 $e=(1,1, \cdots, 1)^{T},$ $\beta\in(0,1)$ は適当な定数であり$\text{、}||\cdot||_{p}$は$\ell_{P}$

ノルムをあらわす。
センターパス$P_{1}$

は、実行可能領域内の–次元の滑らかなパスになっている。 そして、パス上の点は、 $\muarrow 0$ のときに問題$N_{1}(\beta)$$(\mathrm{S}\mathrm{D}_{1})$の強相補解に収束する。 この性質は、近傍内の点列でも成立する、 すなわち、任意の点列 $\{(y^{k}, x^{k}, \tau^{k}, \theta k, s, \kappa)kk\in N_{1}(\beta)\}$において、 $karrow\infty$ のとき $(x^{k})^{T_{S^{k}}}+\tau^{k}\kappa^{k}arrow 0$ ならば、任意の集積点は強相補解である。

したがって、 内敵法により近傍$N_{1}(\beta)$

内に点列を生成することにより、 センターパス$\ovalbox{\tt\small REJECT}$を\mu \rightarrow 0 の方向へ追跡すれば、 自己双対線形計画問題の強相補解を求めることが可能となる。 こめような内点法をパス追跡法と呼ぶ。

パス追跡法$\bullet$

ステップ

$0$

: 初期点

$(y^{000}, x, \mathcal{T}, \theta^{0}, S^{0}, \kappa^{0})$と定数\beta \in $(0, 1)$ を初期点が近傍$N_{1}(\beta)$

内に入るように定める。 $k=0$ とする。
$\bullet$

ステップ 1: $\mu^{k}=((x^{k})^{\tau_{S^{k}}}+\tau^{k}\kappa^{k})/(n+1)$ とする o 適当な\mu \in $[0, \mu^{k}]$ の値を定め、この$\mu$に対応するパス上の点を定義する方程式系に点て $–=-$$\bullet$

トン法を適用し、

ステップ 2: 近傍$N_{1}(\beta)$$–=\mathrm{L}-$トン方向$(y^{kk}, X, \mathcal{T}^{k}, \theta k,kk)s,$$(\triangle y, \triangle x, \Delta_{\mathcal{T}}, \triangle\theta, \triangle S, \triangle\kappa)$$\kappa$を計算する。

から出ない適当なステップサイズ\alpha を求めて$(y, x, \tau, \theta 1, s^{k1k}k+1k+1k+1k++,+1\kappa)$$=$$(y^{kkk}, x, \tau, \theta^{k}, S, \kappa)kk+\alpha(\triangle y, \triangle x, \triangle \mathcal{T}, \triangle\theta, \triangle S, \Delta\kappa)\in N_{1}(\beta)$とする。
$\bullet$

ステップ 3:k を 1 増加し、 ステップ 1 へ行く。

におい178
ここで、二つのパラメータ (ステップ 1 の\mu とステップ 2 の ) の求め方を変えること$\alpha$により、 さまざまなパス追跡法を構築することができる。主双対内点法で提案されている方法が利用でき、 たとえば、 ショートステップ法 (Kojima, Mizuno, and Yoshise [3],Monteiro and Adler
Todd, and Ye$[6])_{\text{、}}$$[7])_{\text{、}}$

ロングステップ法 (Kojima, Mizuno, and Yoshise [2], Mizuno,プレディクタ. コレクタ法 (Mizuno, Todd, and Ye [6]) $k$ どが利用できる。 また、パス追跡法以外に、 主双対ポテンシャル減少法 (Kojima, Mizuno, andYoshise [4] も自己双対線形計画問題に適用できる。
$)$

5

自己双対システム
線形計画問題 (P) に対して、 Nesterov, Todd, and Ye [8] は、つぎの自己双対システムを導入した。 (文献 [8] では、 より –般的な非線型計画問題を対象としているが、 ここでは線形計画問題について述べる。)$Ax$$(SD_{2})$$-A^{T}y$$-b\tau$$+c\tau$$-\kappa$$x\geq 0\cdot\tau\geq 0$

はY
ここで、 $b^{000},$$c,$$g$$-S$$-c^{T_{X}}$$b^{T}y$$-b^{0}$$=$$s\geq 0$$\kappa\geq 0$$=$$c^{0}$,$=$$g^{0}$,,.

(1) により定義されている。 したがって、初期点 ($y^{0},$ $x^{0},$$0$$\tau,$os,$\kappa^{0}$)は、 このシステムの条件をすべてみたす。 このシステムをみたす点の集合に含まれるような半直線の方向$(y, X, \mathcal{T}, S, \kappa)$($\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{e}\mathrm{S}\mathrm{S}\mathrm{i}\mathrm{o}\mathrm{n}$direction) を考える、 すなわち、等式条件の右辺をゼロとした次の条件$Ax$$-A^{T}y$$b^{T}y$$-b\tau$$+c\tau$$-S$$-c^{T_{X}}$$x\geq 0$$-\kappa$$\tau\geq 0$$s\geq 0$

$=$

$0$

,$=$$0$,$=$$0$,(2)$\kappa\geq 0$をみたすベクトル $(y, x, \tau, s, \kappa)$ を考える。 このような方向を$(y^{*}, x^{*}, \mathcal{T}^{*}, S\kappa)*,*$とすると

き、 係数行列が歪対称であることから、 上の条件式にこの点を代入し、 両辺にベクトル$-((y^{*})^{T}, (x^{*})T,$ $\tau)$を乗じれば$(x^{*})^{\tau_{S^{*}}}+\tau\kappa^{*}=*0$が得られる。 それぞれの成分が非負であることから、 相補性条件$X^{*}s^{*}=0,$$\tau^{*}\kappa^{*}=0$

179が成立する。 このことからも類推されるように、 次の結果が得られる。

補題 4$(y^{*}, x^{*}, \mathcal{T}^{*}, S\kappa)*,*$

ならば、$x^{*}/\tau^{*}$

を問題 $(SD_{2})$ の recession direction であるとする o もし $\tau^{*}>0$と $(y^{*}, s^{*})/\tau^{*}$ は、それぞれ主問題 $(P)$ と双対問題 $(D)$ の最適解である。 もし\sim $>0$ ならぱ、主問題 $(P)^{\text{あるい}}.\text{は双対問題}$ $(D)$ の少なくとも –方が実行不能である。
.

証明 : 上記の条件 (2) より、 問題$(\mathrm{S}\mathrm{D}_{2})$をほどこせば、 自己双対線形計画問題のrecession direction は、適当なスケーリング$(\mathrm{S}\mathrm{D}_{1})$の最適解である。 したがって、補題 2 からこの結果が得られる。

口

また、補題 1 より、 recession direction には、強相補性条件をみたすものが存在する。

そのような方向$(y^{*},x^{*}, \mathcal{T}^{*}, S\kappa)*,*$

を求めれば、 $\tau^{*}>0$ または $\kappa^{*}>0$ であるので、上記の結果から主問題 (P) と双対問題 (D) を解くことができる。
Nesterov, Todd, and Ye [8] は、問題
$F_{2}:=${ $(y,$$(\mathrm{S}\mathrm{D}_{2})$$x,$ $\tau,$ $S,$ $\kappa):(\mathrm{S}\mathrm{D}_{2})$の条件をみたす点の集合‘’の条件をみたす}に対して、 センターパス$P_{2}:=\{(y, x, \tau, S, \kappa)\in F2:xS=\mu e, \tau\kappa=\mu,\mu>0\}$とその近傍$:=$$N_{2}(\beta)$$\{(y, x, \tau,S, \kappa)\in F2:||(Xs-\mu e, \mathcal{T}\kappa-\mu)||p\leq\beta\mu$,$\mu=(x^{T}s+\tau\kappa)/(n+1),\mu>0\}$を導入した。 そして、近傍$N_{2}(\beta)$

内に点画を生成し、 センターパス乃を\mu \rightarrow \infty の方向に追跡した点をスケーリングすることにより、強相補性条件をみたす recession direction(あるいはその近似) を求めることができることを示した。 そして、 そのような点点を求めるための内濠法を提序した。

— つのアプローチの関係

6.,

ここまでに、線形計画問題を解くために自己双図システム使う方法を二つ紹介した。

前節で X– 明したこ$\text{と}$からも類推されるように、 この二つの方法には密接な関係がある。

Mizuno and Todd [5] は、 その関係を詳しく調べた。 ここでは、 その結果の–部を簡単に紹介する。

180

写像\Phi :$F_{1}arrow F_{2}$を$\Phi(y,x, \mathcal{T}, \theta,s, \kappa)=(y, x, \mathcal{T},s, \kappa)/\theta$により定卜する。 この写像は、全単射 (one-to-One. and ont.o) であり、逆写像も簡単に求められる。 この写像により、問題$(\mathrm{S}\mathrm{D}_{1})$のセンターパス$P_{1}$上の点は、問題ンターパス P2 上に移る。 ただし、 その方向は逆向きである、 すなわち、$P_{1}$$(\mathrm{S}\mathrm{D}_{2})$のセ上で\mu が減少する向きに点が移動すれば、 乃で対応した点は\mu が増加する方向に動く。 同様に、 問題$(\mathrm{S}\mathrm{D}_{1})$のセンタ一パスの近傍$N_{1}(\beta)$

上の点も、写豫\Phi により、近傍$N_{2}(\beta)$

上に移る。

Mizuno and Todd [5] は、二つの自己双対システムの両点法に使われる探索方向とステップサイズの関係も調べた。 その結果、 ロングステップ法あるいはプレディクタコ

レクタ法を適用した場合には、適当な初期点とパラメータを設定することにより、生成される点列が写像\Phi により完全に対応していることを明らかにした。 他方、 ショートス

テップ法などで生成される点列に対しては、 このような対応が得られないことも示した。
また、 ポテンシャル減少法と呼ばれる内点法では、適当なポテンシャル関数を採用することにより、二つの自己双対システムに適用したときに、 写像\Phi により完全に対応した点列を生成することを明らかにした。

参考文献[1] N. K. Karmarkar, A new polynomial-time algorithm for linear programming, $C_{om}-$binatorica, 4:373-395, 1984.

[2] M. Kojima, S. Mizuno, and A. Yoshise, A Primal-Dual Interior-Point Algorithm for

Linear Programming; in N. Megiddo ed., Progress in Mathematical Programming,Interior Point and Related Methods, Springer-Verlag, 29-47, 1989.
[3] M. Kojima, S. Mizuno, and A. Yoshise, A Polynomial-Time Algorithm for a Classof Linear Complementarity Problems; Mathematical Programming Vol. 44, No. 1,1-26, 1989.

[4] M. Kojima, S. Mizuno and A. Yoshise: An $O(n^{0.5}L)$ Iteration Potential Reduction

Algorithm for Linear Complementarity Problems; Mathematical Programming Vol.
50, No. 3, 331-342, 1991.

[5] S. Mizuno and M. J. Todd, On two homogeneous self-dual systems for linear pro-181

gramming and its extensions, Research Menorandum 687, The Institute of Statistical Mathematics, Tokyo, 1998.
[6] S. Mizuno, M. J. Todd, and Y. Ye, On Adaptive-Step Primal-Dual Interior-Point

Algorithms for Linear Programming; Mathematics of Operations Research Vol. 18,No. 4, 964-981, 1993.
[7] R. D. C. Monteiro and I. Adler, Interior path following.primal-dual algorithms:

Part I: Linear programming, Mathematical Programming, 44:27-41, 1989.
[8] Yu. E. Nesterov, M. J. Todd and Y. Ye, Infeasible-start primal-dual methods andinfeasibility detectors for nonlinear programming problems, to appear in Mathematical Programming.
[9] X. Xu, P.-F. Hung, and Y. Ye, A simplified homogeneous and self-dual linear

programming algorithm and its implementation, Annals of Operations Research,
62:151-171, 1996.
[10] X. Xu and Y. Ye, A generalized homogeneous and self-dual linear programmingalgorithm, Operations Research Letters, 17, 1995.
[11] Y. Ye, M. J. Todd, and S. Mizuno, An $O(\sqrt{n}L)$ -iteration homogeneous and self-dual linear program. ming algorithm, Math.ematics of Operations Research, 19:53-67,1994.