数理解析研究所講究録 1349 巻 2004 年 166-176166

特殊な確率計画問題に対する主双対内点法
東京工業大学社会理工学研究科

小崎

敏寛 *( Toshihiro KOSAKI)

水野

眞治 \dagger (Shinji MIZUNO)Tokyo Institute of Technology

2003 年 12 月 15 日

概要

確率計画問題に現れる特殊な構造を持つ大規模な線形計画問題を扱う. この線形計画問題では, 係数行列の右上部分が 0 行列であり, その右下部分が対角行列となっている. この特殊構造を利用する主双対内点法を提案し, その反復回数が一般の主双対内点法に比べ少なくなることを示す、Keyword: 内点法, センターパス, 双対定理, 確率計画問題

1

はじめに
内点法は,

1984 年に Karmarkar [2] によって提案され, その後爆発的に研究されている. 現在では, 大規模な線形計画問題を解く,

標準的な解法として多くのパッケージソ
フトに内点法が採用されている. 内点法の中で, 最もよく使われているのは, Kojima,
Mizuno and Yoshise[3] によって提案された主双対内点法である.
不確実な状況下での最適化を扱うものとして, 確率計画問題がある. 確率計画問題は,不確実性を詳細に記述しようとすると問題が複雑 大規模になり, 解くことが困難になるという欠点をもつ. しかし, 大規模になっても問題の特殊な構造を利用することで計算時間の短縮をはかることができる.
不確実性を表現するにはさまざまな方法があるが, ここでは有限個のシナリオからなる 2 期間の確率計画問題を扱う. このような問題は, 特殊な構造を持った大規模な線形計画問題に定式化することができる. 本論では, その問題の特徴を利用した主双対内点法を提案する. 提案するアルゴリズムの特徴は, 構造のない同程度の問題に適用した場合に比べ, 反復回数を減少できることにある.
$*\mathrm{k}’\mathrm{o}\mathrm{s}\mathrm{a}\mathrm{k}\mathrm{i}\underline{\cap\alpha}$

me.titech .ac.jp,$\overline{\mathrm{T}}152$-8552 東京都目黒区大岡山 2-21-1-8552 東京都目黒区大岡山 2-21-1$\dagger_{\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{u}\mathrm{n}\mathrm{o}@\mathrm{m}\mathrm{e}.\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{c}\mathrm{h}.\mathrm{a}\mathrm{c}.\mathrm{j}\mathrm{p}},\overline{\mathrm{T}}152$

187

2 節では, 確率計画問題を説明し, その最適条件を示す, 3 節では, その問題に対するアルゴリズムを提案する. 提案したアルゴリズムの解析を 4 節で行う. 5 節において, 得られた結果をまとめる.

2

問題

2.1

確率計画問題2 段階の確率計画問題を考える.

ここでは, 有限個のシナリオからなる,

シナリオの数を $N$ とすれば, そのような確率計画問題は, 次の線形計画問題と等価になる.
$\min$

$c$

Tx

$+$

p1qTy1$+$P2qfy2$+\cdot\cdot$.

$+pNqN\prime \mathit{1}^{1}$y$f\mathrm{v}$$Ax$$\mathrm{s}.\mathrm{t}$$=b$$+W$1y1$T_{1}x$,$=f\iota_{1}$,[ 2y2(1)$\gamma$$T_{2}x$$+\mathrm{M}$

.
.

.

.

$\cdot$.
$\cdot$+V N\acute yN$T_{N^{X}}$$x\geq 0,$$y_{1}\geq 0$,$y_{2}\geq 0$,$y_{N}\geq 0$$=h_{N)}$.

この問題については, たとえば文献 [1] を参照すること
ここで, $x\in R^{n}$ は現時点 (–期) での決定変数であり, $J\in R^{n’}$ はシナリオ が起きたときの二期の決定変数である.
$\mathrm{r}$$i$$p_{i}\in R$

は, シナリオ$i$の生起確率を表し,$c\in R^{n},$$q_{i}\in R^{n’}$:$A$

目的関数あるいは制約条件式を表すためのデータである.
上の問題 (1) において,$c_{1}=c,$,$T_{i},$$\mathrm{L}\mathrm{I}_{i}^{f},$$b$\in Rm,$h_{i}\in R^{m^{l}}$は,$x_{1}=x_{j}x_{2}^{T}=(y_{1}^{T}, y_{\mathit{2}}^{T}/, \cdots)y_{N}^{T}),$$A_{1}=A,$ $b_{1}=b$$c_{2}^{T}=(p_{1}q_{2}^{T}, p_{2}q_{2}^{T}, \cdots , p_{r\iota}q_{r\iota}^{T})$,$A_{2}=(\begin{array}{l}T_{1}T_{2}\vdots T_{N}\end{array}),$$A_{3}=(\begin{array}{llll}W_{1} \nu V_{2} \ddots \mathcal{V}V_{N}\end{array}),$$b_{2}=(\begin{array}{l}h_{1}h_{2}\prime\vdots h_{N}\end{array})$とすれば, 問題 (1) は而$\mathrm{s}$$\mathrm{n}$.t.

$c_{1}^{T}x_{1}$$+c_{2}^{T}x_{2}$,$A_{1^{X_{1}}}$$A_{2^{X_{1}}}$$+A_{3}x_{2}$$(X_{1}, x_{2})\geq 0$,$=b_{1}$,$=b_{2}$

,

(2)

,

168

と書き換えることができる. ここで, $n_{1}=n,$ $n_{2}=n’ N,$ $m_{1}=m,$ $m_{2}=m’ N$ とすれは次元のベクトと次元のベクトル,はとは次元のベクトル,ば,は次元のベクトルであり, 行列ル,, A3 はそれぞれ対応するサイズの行列である.
$c_{1}$$b_{2}$$m_{2}$

さら {こ,$x_{2}$$n_{1}$$x_{1}$$A_{1},$$x^{T}=(x_{1}^{T}, x_{2}^{T}),$$c^{T}=(c_{1}^{T}, c_{2}^{T})$$b_{1}$$n_{2}$$c_{2}$$m_{1}$$A_{2}$,$A=(\begin{array}{ll}A_{1} OA_{2} A_{3}\end{array})$$)b=(\begin{array}{l}b_{1}b_{2}\end{array})$とすれば, 上の問題 (2) は次の標準形の線形計画問題として表すことができる.
$\min$$\mathrm{s}.\mathrm{t}$$c$.

T $x$ ,

$Ax=b$ ,$x\geq 0$,

問題 (2) を主問題とすると, その双対問題は$\max$$\mathrm{s}.\mathrm{t}$.

$b_{1}^{T}y_{1}$$A_{1}^{T}y_{1}$$+b\tau_{y_{2}}2$.

$+A\tau_{y_{2}}2$,$=c_{2}$ ,$+s1$$A_{3}^{T}y_{2}$$+s2$$(s_{1}, s_{2})$$\geq 0$$=c_{1}$(3),となる. ただし変数は $(y_{1}, y_{2}, s_{1}, s_{2})\in R^{m_{1}+m_{2}+n_{1}+n_{2}}$ である. 主問題と双対問題のペアの実行可能領域は$\mathcal{F}:=\{\begin{array}{llllll} A_{1}x_{1} =b_{1} A_{2}x_{1} +A_{3}x_{2} =b_{2}\vdots(x_{1},x_{2},y_{1},y_{2},s_{1},s_{2}) .

A_{1}^{T}y_{1} +A_{2}^{T}y_{2} +s_{1} =c_{1}\vdots A_{3}^{T}y_{2} +s_{2} =c_{2}\vdots (x_{1},x_{2},s_{1},s_{2}) \geq 0 \vdots\end{array}\}$であり, その実行可能内点の集合は$\mathcal{F}^{0}:=\{(x_{1}, x_{2}, y_{1}, y_{2}, s_{1}, s_{2})\in F:(x_{1}, x_{2}, s_{1}, s_{2})>0\}$である. 線形計画問題の主問題と双対問題に内点が存在する, すなわち, 集合

ではないと仮定する.

$\mathcal{F}^{0}$

が空

189

2.2

最適条件

問題 (2) に最適解存在し, 条件$(x_{1}, x_{2})$が存在するとすれば, 双対問題 (3) に最適解 $(y_{1}, y_{2}, s1, s_{2})$ が$A_{1}x_{1}$$A_{2}x_{1}$$+A3x2$$A_{1}^{T}y_{1}$$+A2y_{2}$$A_{3}^{T}y_{2}$$(x_{1}, x_{2})$$=$$b_{2}$$+s1$$c_{1}$

$+s2$

$=$

$c_{2}$$J\mathrm{Y}_{2}^{r}s_{2}$をみたす- 逆に,

$b_{1}$$=$$X_{1}s_{1}$$(x_{1}, x_{2}, s_{1}, s_{2})$

$=$

$=$

0,

$=$

0

,
,
,

,

$\geq 0$と $(y_{1}, y_{2}, s_{1}, s_{2})$ が上 己の条件をみたせば, それら (はそれぞれ主$\equiv[]-$問題と双対問題の最適解となる.
パラメータ $\mu>0$ に対して, 上の最適条件を少し変更した条件$A_{1}x_{1}$$=$$b_{1}$$=$$b_{2}$,,$A_{2}x_{1}$$+A3x2$$A_{1}^{T}y_{1}$$+A2y_{2}$

$+s1$

$=$

$c_{1}$$A_{3}^{T}y_{2}$

$+s2$

$=$

$c_{2}$

$=$

$\mu$

e1,

$=$

$\mu$

e2

$X_{1}s_{1}$$J\mathrm{Y}_{2}s_{2}$$(x_{1}, x_{2}, s_{1}, s_{2})$,,$\geq 0$とを考える. ここで,はすべての要素が 1 となるベクトルである. 集が空ではないので, この条件式をみたす点が唯一つ存在し, それを解析的中心と合呼ぶ.
$e_{1}\in R^{n_{1}}$$e_{2}$$\in R^{n_{2}}$$F^{0}$

2 つのパラメータ$(\mu_{1}, \mu_{2})>0$

に対する条件$A_{1}x_{1}$$A_{2}x_{1}$$+A3x2$$A_{1}^{\prime\tau}y_{1}$$+A\prime \mathrm{r}_{y_{2}}2$$A_{3}^{T}y_{2}$$b_{1}$$=$$b_{2}$,,,,$+s\mathrm{l}$$=$$c_{1}$

$+s2$

$=$

$c_{2}$

$=$

$\mu$

1e1,

$=$

$\mu$

2e2

$X_{1}s_{1}$$\lambda_{2}^{r}s_{2}$$(x_{1}, x_{2}, \mathrm{s}_{1}, s_{2})$$=$$\geq 0$をみたす解も唯一つ存在するので, それを $w($ \mu 1, $\mu_{2}):=(x_{1} (\mu 1, \mu_{2}),$$y_{2}($\mu 1,$\mu_{2}),$$s_{1}($\mu 1,$\mu_{2}),$$s_{2}(\mu_{1}, \mu 2))$(4),と表すことにする. この点も解析センターと呼ぶ. 解析$x_{2}(\mu 1)\mu_{2}),$ $y_{1}(\mu_{1}, \mu 2)$

170

センターの集合$S:=\{w(\mu_{1}, \mu 2)$

は 2 次元曲面となるので,: $(\mu_{1}, \mu 2)\in(0, \infty)\cross(0, \infty)$}

それをセンター曲面と呼ぶ. また, 集合$P:=\{w(l^{A_{1}}, \mu 2)$:$\mu 1=l^{\mathrm{J}}$2,$(0, \infty)$$(\mu_{1}, \mu 2)\in$$\cross(0, \infty)\}$はセンターパスとよばれる.

3

アルゴリスムよず-, アルゴリズムの概略を説明する. 初期点として, あるパラメータ $\mu^{0}>0$ とセンが得られているとする. 定数 $\gamma\in(0,1)$ に対して, $k=0$ から
タ $w($ \mu 0,の近似点$w^{0}$$\mu^{0})$と定めの値が 倍になるように帰納的にに対して, センター(\mu k, ) を近{以するように点 を生成る. このように定めたする. (詳しい手順については後に記す。 ) このとき, アルゴリズムにより生成される点
列 $\{w^{k} : k=0,1,2, \cdots\}$ はセンターパス上の点列 { (\mu k, ) : $k=0,1$ ,} を近似すはじめて,$k$が 1 増えるごとに$\mu^{k+1}=\gamma\mu^{k}$$\mu^{k}$$\gamma$$w^{k}$$\mu^{k}$$w^{k}$$\mu^{k}$$2,$$\mu^{k}$$w$$\cdots$

る. パラメータの更新式より,$\mu^{k}=\gamma^{k}\mu^{0}$k) は線形計画問題の最も最適解の近似点となる. したがって, が大適解に近づき, そのセンターの近似点
きくなれば, 十分な精度の近似解を求めることができる.
を計算する手順を説明する. 手から次のセンターの近似点
センターの近似点のみの値を減少させたセンター
から第 1 のパラメータ順は二段階からなる. まず点を求め (ステツプ 1)’ 次に, その点からセンター) の近似点曲面 上の点 (の近似点を求める (ステップ 2).
アルゴリズムの手順を簡単に説明すると次のようになる.
[アルゴリスムの概略]であるので,とすると,$karrow\infty$$\mu^{k}arrow 0$となり, センター $w$ ($\mu^{k},$

$\mu$

$k$

$w^{k}$$w^{k+1}$$w^{k}$$w^{k}$$\mu_{1}$

$S$

$w$

$\mu^{k+1}$$w’$$\mu^{k}$、$w(\mu^{k+1}, \mu^{k+1})$

1. $\mu^{0}>0$ に対するセンター $w($ 1”,$\gamma\in$$(0, 1)$$\mu^{0})$の近似点$w^{0}$が得られているとする.

を定める. $k=0$ とする.

からセンター (k) を定める方程式系に対すると更新する.
k) の近似点
ニュートン法を適用することにより,(を求める.
3. $w’$ からセンター $w(l^{A^{k+1}}, \mu^{k+1})$ の近似点 $w^{k+1}$ をニュートン法を用いて求める.(詳細2.

$\mu^{k+1}=\gamma\mu^{k}$$w^{k}$$w$$w$

は後述する.)$\mu^{k+1},$$\mu$$\mu^{k+1},$$\mu$$w’:=(x_{1}’, x_{2}’, y_{1}’, y_{2}’, s\prime 1’ s_{2}’)$

171

4. 終 7 基準をみたしているときは終了する. そうでないときは $k=k+1$ として,テップ 1 に戻る.

ス

以下で, ステップ 1, ステップ 2 の詳細を解説する.

3.1

ステップ 1 について

アルゴリズム中のステップ 1 では, センター曲面上の点 (k) を定義している方
程式系 (4) にニュートン法を適用することにより, その近似点を求める. すなわち,におけるニュートン方向() は, 線形等式系
x2,$w$$\mu^{k+1},$$\mu$$w^{k}$$\triangle w:=$$\triangle x_{1},$$\triangle$$\triangle y_{1},$$\triangle y_{2},$$\triangle s_{1},$$=b_{1}-A_{1}x_{1}^{k}$$A_{1}\triangle x_{1}$$A_{2}\triangle x_{1}$$+A_{3}\triangle x_{2}$$A_{1}^{T}\triangle y_{1}$$+A_{2}^{T}\triangle y_{2}$$\triangle s_{2}$,$=b_{2}-A_{2}x_{1}^{k}-A_{3}x_{2}^{k}$,$+\triangle s_{1}$$=c_{1}-A_{1}^{Tk}y_{1}-A_{2}^{Tk}y_{2}-6_{1}^{k}.$$+\triangle s_{2}$$=c_{2}-A_{3}^{Tk}y_{2}-s_{2}^{k}$$S_{1}^{k}\triangle x_{1}$$+X_{1}^{k}\triangle s_{1}$$=\mu^{k+1}e_{1}-X_{1}^{k}s_{1}^{k}$$S_{2}^{k}\triangle x_{2}$$+X_{2}^{k}\triangle s_{2}$$=\mu^{k}e_{2}-\mathit{1}\mathrm{Y}_{2}^{k}s_{2}^{k}$$A_{3}^{\prime \mathrm{r}}\triangle y_{2}$

,

,

,

,

の解として与えられる. ステップサイズを 1 として, 次の点 ’ を
$w$

$w$

’

$:=$

$(x_{1}’, x_{\mathit{2}}’’, y_{1}’, y_{2}’, s_{1}’, s_{2}’)$$=$$(x_{1}^{k}, x_{2}^{k}, y_{1}^{k}, y_{2}^{k}, s_{1}^{k}, s_{2}^{k})+$($\triangle x_{1},$$\triangle$

x2,$\Delta/$yb$\triangle$

y2,$\triangle$

s1,$\triangle$

s2)

とする.

3.2

ステップ 2 についてステップ 2 では,$w’$

からセンター $w(l\iota^{k+1}, \mu^{k+1})$ の近似点 $w^{k+1}$ を求める. ステップ 2

をステップ 1 で求めたに固定する. 問題の制約式中の行列 A3がブロック対角であるので, 主問題は複数の小さな子問題に分割できる. もとの線形計
では, 変数ベクトル$x_{1}’$$x_{1}$

画問題
而$\mathrm{n}$$\mathrm{s}.\mathrm{t}$.

$c_{1}^{T}x_{1}+c_{2}^{T}x_{2}$,$A_{1}x_{1}$$A_{2}x_{1}+A_{3}x_{2}$$(x_{1}, x_{2})\geq 0$$=b_{1}$$=b_{2}$

,
,

(5)

112

において, 変数$x_{1}$

をステップ 1 で計算した$\min$$\mathrm{s}$’$x_{1}$に固定すると, 問題$c_{1}^{I^{1}}x_{1}’+c_{2}^{T}x_{2}\ulcorner$.t.

,$=b_{1)}$$A_{1}x_{1}’$$A_{2}x_{1}’+A_{3}x_{2}=b_{2}$,$(x_{1}, x_{2})\geq 0$が得られる. この問題は,
計 Eu 問題が定数ベクトルであるから,$x_{1}’$$\min$$\mathrm{s}.\mathrm{t}$$c_{2}^{T}x_{2}$.

$b_{2}’:=b_{2}-A_{2}x$t とすると線形,,$A_{3}x_{2}=b_{2}’$$x_{2}\geq 0$と等価である. (目的関数値は定数’1 だけ異なる. ) 行列上の問題は $i=1,2$ , . . , $N$ に対する次の $N$ 個の問題
$c_{1}^{T}x$$A_{3}$が対角行列であるので,$\cdot$$\min$$\mathrm{s}.\mathrm{t}$$p_{i}q_{i}^{T}y_{i}$.

,$(=h_{i}-T_{1}x_{1}’)$$W_{i}y_{i}=(.b’ 2)i$,(6)$y_{i}\geq 0$に分割できる.
この問題の双対問題は$\max$$\mathrm{s}.\mathrm{t}$.

$((b_{2}’)_{i})^{T}u_{2}$,$\dagger’V_{i}^{T}u_{2}+v_{2}=p_{i}q_{i}$,(7)$v_{2}\geq 0$であり, 最適条件は$\nu V_{i}y_{i}$$=$$(b_{2}’)_{i}$$\nu v_{i}^{\prime\tau_{u_{2}+v_{2}}}$$=$$p_{i}q_{i}$$Y_{i}v_{2}$

$=$

0,

$(y_{i}, v_{2})$$\geq$,

フ0である. またパラメータ $\mu>0$ に対して, 主問題 (6) と双対問題 (7) の組のセンターは線形等式系$W_{i}y_{i}$$=$$(b_{2}’)_{i}$$\mathrm{T}/V_{i}^{T}u_{2}+v_{2}$$=$$p_{i}q_{i}$$Y_{i}v_{2}$$=$$\mu e$$(.y_{i}, v2)$$\geq$

0

,

,

,

(8)

113

である. ステップ 1 で求めた解の部分ベクトノレをみたす点$(y_{i}, u_{2}, v_{2})$は,のときの (8) をみたすセンターの近似点となっている.

$\mu=\mu^{k}$$((x_{2}’)_{i}, (y_{\mathit{2}}’’)_{i}$, (s\sim )したがって, それぞれの分割された主問題 (6) と双対問題 (7) に内点法を適用すること
により,$\mu=\mu^{k+1}$のときの (8) をみたすセンターの近似点を計算することができる.

こ

こでの計算は, 分割された問題への内点法であるので, その計算量はステップ 1 に比べはるかに少なくなる.
このようにして, 成分ごとに点を更新することにより計算した点をば, 等式条件$=b_{1}$$A_{1}x_{1}$$A_{2}x_{1}+$$=b_{2}$$A_{3}x_{2}$$A_{3}^{T}y_{2}$$+s_{2}$$(\overline{x}_{2},\overline{y}_{2},\overline{s}_{2})$

とすれ

,
,

$=c_{2}$ プ

を正確にみたし,を近似的にみたす点を定義する条件のうち$\overline{w}:=$e1,$X_{1}s_{1}$$=\mu^{k+1}$$\lambda_{2}^{r}s_{2}$$=\mu^{k+1}e_{2}$$(x_{1}’, x- 2, y_{1}’, y- 2, s_{1}’,\overline{s}_{2})$を求めることができる. しかし, センター

(9)

$A_{1}^{T}y_{1}+A_{2}^{T}y_{2}+s_{1}=c_{1}$を近似的にみたすかどうかについては不明である. そこで, もし上の条件 (9) をみたすならば, ステップ 2 を終了する. さもなければ,

が

(S )

(10)

$(x_{1}’, x- 2, y_{1’/2}’\overline{\uparrow}, s_{1}’,\overline{s}_{\underline{9}})$$\overline{y}_{1}:=\arg\min_{y_{1}}||$$1’$$-1(A_{1}^{\tau}y_{1}+A_{2}^{\tau}\overline{y}_{2}+s_{1}’-c_{1})||_{2}$が条件 (9) を近似的にみたす. すなわち小さな定を計算する. もしをみたすならば, ステツプ 2に対して,数を終了する. 最後に制約 (9) をみたすように親問題 (5) において, ニュートン法を行い,センター $(w(\mu^{k+1}, \mu^{k+1}))$ の近似点を得て, ステップ 2 を終了する.
$(x_{1}’, x- 2,\overline{y}_{1}, y- 2, s_{1)}’\overline{s}_{2})$$\triangle>0$4$||(S_{1}’)^{-1}(A_{1}^{T}\overline{y}_{1}+A_{2}^{T}\overline{y}_{2}+s_{1}’-c_{1})||_{2}\leq\triangle$

アルゴリズムの解析[定理 1]

ベクトルと仮定する. ステツプ 1 で生或された点 ’ の部分が問題 (2) の実行可能点であるとする. このとき, ステップ 2 で生は条件$\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(A_{2}^{T})$$(y’ 1 , y_{2^{\backslash }}’, s/1)$

成された点$\subset \mathrm{R}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(A_{1}^{T})$$(\overline{y}_{1}, y- 2, s_{1}’)$$A_{1}^{T}\overline{y}_{1}+A_{2}^{T}\overline{y}_{2}+s_{1}’=c_{1}$

$w$

174

をみたす 1[証明] ステップ 1 で計算された $w’$ が実行可能であることから,$A_{1}\tau y_{1}’+A_{2}y_{\mathit{2}}’+s_{1}\tau"=c_{1}$仮定より, Range$(A_{2}^{\prime \mathrm{r}})\subset \mathrm{R}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(A_{1}^{T})$であるから,$y_{2}’$.

を固定して考えると, 任意の$\overline{y}_{2}$に対しで,$A_{2}^{T}(y_{2}’-\overline{y}_{2})=A_{1}^{T}\tilde{y}_{1}$をみたすが存在する.

$\tilde{y}_{1}$この$\tilde{y}_{1}$を用いて,$A_{1}^{l}\overline{y}_{1}+’\urcorner A\tau_{\overline{y}_{2}+}2s’ 1$$=$$A_{1}^{T}(y_{1}’+\tilde{y}_{1})+A_{2}^{T}\overline{y}_{2}+s’ 1$$=$$A_{1}^{T}y_{1}+A_{2}^{T}(y_{2}’-\overline{y}_{2})+A_{2}^{T}\overline{y}_{2}+s_{1}’$$=$$A_{1}^{T}y_{1}+A_{2}^{T}y_{2}’+s_{1}$

$=$

となる.

したがって,$\overline{y}_{1}$とすると,$\overline{y}_{1}=y_{1}’+\tilde{y}_{1}$’$c_{1}$

は問題 (10) の解である. また,$(\overline{y}_{1} ,\overline{y}_{2}, s_{1}’)$

は等式 (9) をみたす 1

(証明終)
パラメータ
$N_{\beta}$$\beta\in$$(0, 1)$に対して実行可能点からなるセンターの近傍$:=$$(\mu_{1}, \mu 2)$$\{(x_{1}, x_{2}, y_{1}, y_{2\}}s_{1}, s_{2})\in F$$||$(X1s1 $-\mu$ 1eb:$X_{2}s_{2}-\mu_{2}e_{2}$)$||_{2} \leq\beta\min\{\mu_{1)}\mu 2\}$}を定義する.
次の補題は, 内点法でよく使われる不等式であり, 後の定理の証明で使う.
[補題 1] $u^{T}v\geq 0$ をみたす と $v\in R^{n}$ に対して, 次の関係が成り立つ.
$u$

$||$

[定理 2]

Uv$||_{2} \leq\frac{\sqrt{2}}{4}||u+v||_{2}^{2}$

を変数 の次元とし, 点存在する点とする. すなわち,$n_{1}$$w^{k}$$\prime x_{1}$をセンター $w$ (\mu k,$w^{k}\in N_{\beta}(\mu^{k}, \mu^{k})$もし $\delta>0$ と$\beta\in((\mathrm{I}, 1)$(11).
$\mu^{k}$) の近傍$N_{\beta}$($\mu^{k},$

$\mu$

k) 上に

.

が

(12)

$\frac{\sqrt{2}}{4}\frac{(\delta+\beta)^{2}}{(1-\beta)(1-\delta)}\leq\beta$

をみたすならば, このとき $\gamma=(1-\delta/\sqrt{n_{1}})$ としてステップ 1 で生成される点 $w’:=$$(x_{1}’, x_{2}’, y_{1}’, y_{2}’, s\prime 1’ s_{2}’)$(は, センター $w$ ( $\mu^{k+1},$$\mu$k) の近傍わち$w’\in N_{\beta}(\mu^{k+1}, \mu^{k})$$N_{\beta}$($\mu^{k+1},$$\mu$k) 上に存在する, すな

175

である.

特に $\beta=1/4$ で $\delta=1/4$ とすると上の条件をみたす。
[証明] ニュートン方向(x2,て与えられる.
$\triangle w=$$\triangle x_{1},$$\triangle$$\triangle y_{1},$$A_{1}\triangle x_{1}$$+A_{3}\triangle$$A_{1}^{T}\triangle y_{1}$$+4T2\mathrm{x}_{y_{2}}$$\triangle s_{1},$$\triangle s_{2}$) は, 次の方程式の解とし,$=$$b_{1}-A_{1}x_{1}^{k}$$=$$b_{2}-A_{2}x_{1}^{k}-A_{3}x_{2}^{k}$$+\triangle s_{1}$$=$$c_{1}-A_{1}^{Tk}y_{1}-A_{2}^{Tk}y_{2}-s_{1}^{k}$$+2$$s_{2}$$=$$c_{2}-A_{3}^{T}y;-s_{2}^{k}$$1k\triangle s_{1}$$=$$\mu^{k+1}e_{1}-X_{1}^{k}s_{1}^{k}$

s2

$=$

$\mu^{k}e_{2}-X_{2}^{k}s_{2}^{k}$x2$A_{2}\triangle x_{1}$$\triangle y_{2},$$e\triangle_{Il2}$

X$S_{1}^{k}\triangle x_{1}$$+$$S_{2}^{k}\triangle x_{2}$$+X2\triangle$

,
,

,

(13)

,

.

以下で次の不等式が成り立つことを示す$C_{1}$$:=$$||((X_{1}^{k}+\triangle X_{1})(s_{1}^{k}+\triangle s_{1})-\mu^{k+1}e_{1},$ $(X_{2}^{k}+\triangle X_{2})(s_{1}^{k}+\triangle s_{1})-\mu^{k}e_{2}||_{2}$$\leq$$\beta\min\{\mu^{k+1}, \mu^{k}\}$

.

(14)

而 $\mathrm{n}\{\mu^{\mathrm{k}+1}, \mu^{k}\}=\mu^{k+1}$ に注意すると次の不等式が成り立っ.
$C_{2}$$:=$$\leq$$||((X_{1}^{k}S_{1}^{k})^{-1/2}(\mu^{k+1}e_{1}-X_{1}^{k}s_{1}^{k}),$$||((X_{1}^{k}S_{1}^{k})^{-1/2}(\mu^{k+1}-\mu^{k})e_{1},0)||$$||$$\leq$(

2$(X_{1}^{k}S_{1}^{k})^{-1/2}(\mu^{k}e_{1}-X_{1}^{k}s_{1}^{k}),$ $(X_{2}^{k}S_{2}^{k})^{-1/2}$($\mu^{k}e_{2}-$x ))$\frac{(\mu^{k}-\mu^{k+1})\sqrt{n_{1}}}{\sqrt{(1-\beta)\mu^{k}}}+\frac{\beta\mu^{k}}{\sqrt{(1-l9)\mu^{k}}},(w^{k}\in N_{\beta(\mu^{k},l}\sim^{k})$(!

$\leq$$\leq$$(X_{2}^{k}S_{2}^{k})^{-1/2}(\mu^{k}e_{2}-X_{2}^{k}s_{2}^{k}))||_{2}$$\mathrm{H}s\mathrm{s}$$||_{2}$より)$\frac{1}{\sqrt{1-\frac{\delta}{\sqrt{n_{1}}}}}\sqrt{\mu^{k+1}}(\mu^{k}=\frac{1}{1-\delta/_{\mathrm{V}}n_{\acute{1}}}\mu^{k+1}, \gamma=(1-\delta/\sqrt{n_{1}})\epsilon \mathrm{k}\text{り}$$\frac{(\delta+\beta)}{\sqrt{(1-\beta)(1-\delta)}}\sqrt{\mu^{k+1}}$

さらに次の不等式が成り立つ.
$C_{1}$

$=$

$||$

(2

$X_{1}\triangle s_{1}$$\frac{\sqrt{2}}{4}||$$\leq$$=$$\leq$

( Xf
$($

,

$\triangle$

X$2\triangle$

s

$2||$

2

$((13)\epsilon \mathrm{k}\text{り})$$5\mathrm{f})^{-1/2}(\mu^{k+1}e_{1}-X_{1}^{k}s_{1}^{k}),$ $(X_{2}^{k}S_{2}^{k})^{-1/2}(\mu^{k}e_{2}-X_{2}^{k}s_{2}^{k})$$\frac{\sqrt{2}}{4}C_{2}^{2}$$\frac{\sqrt{2}}{4}\frac{(\delta+\beta)^{2}}{(1-\beta)(1-\delta)}\mu^{k+1}$.

)$||_{2}^{2}((11), (13)\epsilon \mathrm{k}\text{り})$178

これは (14) が成り立つことを示す 6

したがって $C_{1}\leq\beta\mu^{k+1}$ となり,に対して,変数の非負性も次のように成り立つ. 変数 の添え字集合を とする.
$\psi_{i}(1)>0$ をみたす二次関数
si を考え:=xi$(0, 1)$ が存在して,が成り立つと仮定する. すると二次関数る. ある と\psi 。は凸でなければならない. ところが次の不等式が成り立つ.
$I$

$x$

$\psi_{i}(0),$$\psi_{\dot{l}}(\alpha)$$i$$\cdot i\in I$$s_{i}+\alpha(x_{i}\triangle s_{i}+s_{i}\triangle x_{i})+\alpha^{2}\triangle x_{i}\triangle$$\psi_{i}(\alpha)\leq 0$$\alpha\in$$\psi_{i}(\alpha)$$\geq$$x_{i}s_{i}+\alpha(x_{i}\triangle s_{i}+s_{i}\triangle x_{i})$$=$$(1-\alpha)\psi(0)+\alpha\mu_{i}((13) \ \text{り})$

$>$

0.

k) ならば, $w’\in N_{\beta(l}x^{k+1},$ k) となる.
(
あきらかに $\beta=1/4,$ $\delta=1/4$ とすると定理の条件 (12) をみたす (証明終)としてとすれば十分である. この条件をみたすには上の定最適解を得るには,理より $O(\sqrt{n_{1}}L)$ 反復が必要である. 定理としてまとめると次のようになる.
O) に存在するなら([定理 3] 問題 (2) が定理 1 の条件をみたし, 初期点が近傍ば, $O(\sqrt{n_{1}}L)$ 反復以内で問題を解くことができる.
これ (は矛盾である.

したがって,$w^{k}\in N_{\beta}$$\mu^{k},$

$\mu$

$\mu$

$2^{-L}$$\mu$$N_{\beta}$

5$\mu^{0},$$\mu$

結論と今後の課題

本論では, 有限個のシナリオからなる 2 期間確率計画問題と等価な線形計画問題を解
く内点法を提案した. この線形計画問題は, 係数行列の右上部分が 0 行列であり, その右下部分が対角行列となるという特徴を持つ.
この問題の特徴を利用し, 2 つのパラメータに対する解析センターを定義し, その全体集合であるセンター曲面上の点列を追跡することにより, 問題を解くアルゴリズムを提案した. 具体的には, 2 つのパラメータを交互に減少させるアルゴリズムであり, 従来の方法に比べ, 一度にパラメータ値を大幅に改善できることを示した.

参考文献[1] Birge, J. and Louveaux, F.: Introduction to Stochastic Programming, Springer, NewYork (1997).
[2] Karmarkar, N.: “A New Polynomial-Time Algorithm for Linear Programming”,
Combinatorica 4(1984) 373-395.

[3] Kojima, M., Mizuno, S. and Yoshise, A.: “A Primal-Dual Interior Point Algorithm
for Linear Programming” : Progress in Mathernatical Programming, Interior Foint
and Related Methods (ed. N. Megiddo) Springer, New York (1989) 29-47.