数理解析研究所講究録
第 1685 巻 2010 年 249-258249

擬凸関数を制約に持つ DC 計画問題に対する外部近似法の改善(Improvement of an outer approximation method for solving a DC programming
problem with pseudo-convex constraint functions)

TOKUSHIGE Yusuke
Graduate School of Science and Technology, Niigata University
新潟大学大学院自然科学研究科 山田修司 YAMADA Syuuji
Graduate School of Science and Technology, Niigata University
大阪大学大学院工学研究科
谷野哲三 TANINO Tetsuzo
新潟大学大学院自然科学研究科

徳重友輔

Graduate School of Engineering, Osaka University

1

はじめに

本研究では, 擬凸関数を制約に持つ DC 計画問題 (DC programming problem) に対する外部近似法の改善を提案する. DC 計画問題に対しては, Tuy [4] により外部近似法に基づく凸多面体近似
アルゴリズムが提案されている. しかしながら, Tuy のアルゴリズムに基づく凸多面体近似は対象とする集合が変化することにより効率的でないことが知られている. このため, 本研究では凸多面体近似の効率性を向上させた新たなアルゴリズムを提案する. また, アルゴリズムの各反復において凸多面体を更新する際従来は極集合の性質を用いて計算されていた. しかしながら, この手法

は各反復において多くの連立一次方程式を解かなければならないため, 計算時間の増加を招いてしまう. このため, 本研究では新たな頂点の計算法を導入する. 導入する手法は, 既存の頂点間の連結
情報と各頂点の含まれるファセットの情報を利用する. 各反復において, 既存の頂点間の連結情報を基に新たに生成される頂点を計算し, 各頂点の含まれるファセットの情報を基に新しく生成された頂点間の連結情報を生成する. 本研究では, DC 計画問題に対して, 修正アルゴリズムを提案し,新たな頂点計算方法を導入する. また, 提案する外部近似法の有効性を計算機実験により検証する.

2

DC 計画問題
本研究では, 次の数理計画問題について考える.

(1)$\{\begin{array}{ll}minimize g(x)-h(x)subject to a_{j}(x)\leq 0, j=1, \ldots, m.\end{array}$

ただし, $g,$: $R^{n}arrow R$ は凸関数, $aj$ : $R^{n}arrow R(i=1, \ldots, m)$ は擬凸関数とする. ここで$X$ $:=\{x\in R^{n} :a_{j}(x)\leq 0, i=1, \ldots, m\}$ とする. 問題 (1) の目的関数は DC 関数 (difference of
two convex functions) であり, 制約集合 $X$ は凸集合であるので, 問題 (1) は DC 計画問題となる.
さらに問題 (1) に対して, 次を仮定する.
$h$

$F$

(Al)int $X=\{x\in R^{n}:a_{j}(x)<0, i=1, \ldots, m\}\neq\phi$. ただし, int $X$ は $X$ の内部集合を表す.

250(A2) $X$ はコンパクトである.

(A3) $r \geq\max\{\Vert x-y\Vert : x, y\in X\}$ を満たす実数 $r>0$ が与えられている.

目的関数は連続であり, 仮定 (A2) より制約集合はコンパクトなので, 問題 (1) は最適解を持つこと
がわかる.

3

Tuy のアルゴリズム
本章では [4] で提案されている Tuy の外部近似アルゴリズムを紹介する.

Tuy の外部近似アルゴリズム.
ステップ

$0$

.

問題 (1) に対して適当な実行可能解 yo$\in X$を選び, $\omega_{0}:=g(y_{0})-h$ (yo) とする.

$\tilde{t}\in$, Do $:=\{(x, t):x\in X, t\leq\tilde{t}, g(x)-t\leq\omega_{0}\}$ とし,を含む凸多面体恥を生成する.
の頂点集合 $V(P_{0})$ を計算する. また,
intの最適解の下界の1 つとする. 反復回数 $k=1$ とは問題 (1)を満たす, のをとる. ただし,

$R\cup\{+\infty\}$$D_{0}$$P_{0}$$\overline{y}\in$$X,\overline{t}<\tilde{t},$$g(\overline{y})-\overline{t}<\overline{\omega},$$h(\overline{y})-\overline{t}<0$$\overline{\omega}$$(\overline{y}$してステップ 1 へ.

ステップ 1.

$(x_{k}, t_{k})\in$

ステップ 1-1.

argmin $\{-h(x)+t :(x, t)\in V(P_{k})\}$ を計算する.

$-h(x_{k})+t_{k}\geq 0$ ならば, アルゴリズムを停止する. そのとき,$y_{k}$が問題 (1)を解く.
ステップ 1-2. $-h(x_{k})+t_{k}<0$ ならば, $\omega_{x_{k}}:=g(x_{k})-h(x_{k})$ とする.
ステップ 1-2-1.

ならば, $yk+1:=y_{k},$ $D_{k+1}:=D_{k}$ とする.

ならば, $y_{k+1};=x_{k},$ $D_{k+1};=\{(x, t):x\in X,$$g(x)-t\leq\omega_{x_{k}}\}$ とする.

ステップ 1-2-2.
$\tilde{t},$$\omega_{k}\leq\omega_{x_{k}}$$\omega_{k}>\omega_{x_{k}}$$\omega_{k+1}:=g(y_{k+1})-h(y_{k+1})$$t\leq$として, ステップ 2 へ.

ステップ 2.
$l_{k}(x_{k}, t_{k})>0$,$l_{k}(x, t)\leq 0$$\forall(x, t)\in\{(x, t):x\in X, t\leq\tilde{t}, g(x)-t\leq\omega_{k+1}\}$を満たすアフィン関数 $l_{k}(x, t)$ を生成する. ステップ 3 へ.
ステップ 3.

凸多面集合 $P_{k+1}:=P_{k}\cap\{(x, t):l_{k}(x, t)\leq 0\}$ とし, $P_{k+1}$ の頂点集合 $V(P_{k+1})$ を計算する.
ステップ 4 へ.

ステップ 4.
反復回数 $karrow k+1$ として, ステップ 1 へ.

このアルゴリズムは有限回の反復で問題 (1) の大域的最適解を求める. すべての集積点が大域的最適解となる無限暫定解列 $\{(x_{k}, t_{k})\}$ を生成する.
で近似することで保Tuy のアルゴリズムの大域的収束性は, 凸集合列 $\{D_{k}\}$ を凸多面体列$\{P_{k}\}$

証される. しかしながら$\{P_{k}\}$の近似対象集合が度々変化するため, 近似率の減少を招いてしまう.

このため, 次章ではこの点を改善する新たなアルゴリズムを提案する.

251
4

Tuy のアルゴリズムの改善

本章では, 問題 (1) に対し, Tuy のアルゴリズムを修正した次の逐次近似解法を提案する.
修正アルゴリズム.
ステップ

.

$0$

適当な実行可能解 yo $\in X$ を選び, $\omega_{0}:=g(yo)-h(y0)$ とする. また, $h_{0}(x):=h(x)+\omega 0$ とする. $\tilde{t}\in R\cup\{+\infty\},$ $D:=\{(x, t):x\in X, g(x)\leq t\leq\tilde{t}\}$ とし, $D$ を含む凸多面体
を生成する. 島の頂点集合 $V(P_{0})$ を計算する. また,
$X,$
int
を満たす
, のを
とる. 反復回数 $k=1$ としてステップ 1 へ.
$P_{0}$$g(y)<\overline{t}<\tilde{t}$$\overline{y}\in$$(\overline{y}$ステップ 1.

argmin $\{-h_{k}(x)+t : (x, t)\in V(P_{k})\}$ を計算する.

$(x_{k}, t_{k})\in$

ステップ 1-1.

$-h_{k}(x_{k})+t_{k}\geq 0$ならば, アルゴリズムを停止する. このとき,$y_{k}$が問題 (1)を解く.
ステップ 1-2.

$-h_{k}(x_{k})+t_{k}<0$ ならば, $\omega_{x_{k}}:=g(x_{k})-h_{k}(x_{k})$ステップ 1-2-1.
$h_{k}(x)+\omega_{x_{k}},$ステップ 1-2-2.
$h_{k}(x),$$\omega_{x_{k}}<0$

かつ $a_{j}(x_{k})\leq 0(j=1, \ldots, m)$ ならば, $h_{k+1}(x):=$$y_{k+1}:=x_{k}$$\omega_{x_{k}}\geq 0$$y_{k+1}:=y_{k}$

とする.

とする.
j=1, \ldots, m\}>0$ ならば, $h_{k+1}(x):=$または $\max\{a_{j}(x_{k}):とする.

ステップ 2 へ.
ステップ 2.

次を満たすアフィン関数 $l_{k}(x, t)$ を生成する.
$l_{k}(x_{k}, t_{k})>0$ ,$l_{k}(x, t)\leq 0$$\forall(x, t)\in\{(x, t):g(x)\leq t\leq\tilde{t}, x\in X\}$.

ステップ 3 へ.

ステツプ 3.

凸多面集合 $P_{k+1}:=P_{k}\cap\{(x, t) :l_{k}(x, t)\leq 0\}$ とし, $P_{k+1}$ の頂点集合 $V(P_{k+1})$ を計算する.
$karrow k+1$

として, ステップ 1 へ戻る.

この修正アルゴリズムでは, 凸多面体近似をする対象の集合 $D$ が変化しないことに注意する.
定理 1. (Kubo, Tamura, Matsui [6])凹最小化問題で, 制約集合が空でない凸多面体ならば, 最適解は制約集合の頂点集合上に存在する.
ステップ 2 の $l_{k}(x, t)$ の生成に対して,$\beta(x, t)$$:= \max\{a_{1}(x), \ldots, a_{m}(x), g(x)-t\}$とする. もし, $g(x_{k})-t_{k}\geq 0$ ならば,$\beta(x_{k}, t_{k})\geq 0$252となる. また, $g(x_{k})-t_{k}<0,$ $a_{j}(x_{k})\leq 0(i=1, \ldots, m)$ ならば,$-h_{k}(x_{k})+g(x_{k})<-h_{k}(x_{k})+t_{k}$となる. $x_{k}\in X$ より, $(x_{k}, g(x_{k}))\in D\subset P_{k}$ となるので, 定$\sim$

H に矛盾する. よって, $g(x_{k})-t_{k}<0$ならば, $a_{j’}(x_{k})>0$ を満たす $i’\in\{1, \ldots, m\}$ が存在する. したがって,$\beta(x_{k}, t_{k})>0$となる. 一方,$\beta(\overline{y}, t]<0$は超平面 $\{(x, t):\beta(x, t)=0\}$ で強分離される. そこで,とし,を選び,, のを結んだ線分と, $\{(x, t):\beta(x, t)=0\}$ の交点をである. よって, $(x_{k}, t_{k})$ とと$(\overline{y}$$(\overline{y},$$(x_{k}, t_{k})$$tJ$$(\xi_{k}, \theta_{k})$$l_{k}(x,t)=\langle s_{k},$と定義する. ただし,

$s_{k}\in\partial\beta(\xi_{k}, \theta_{k})$$(x, t)-(\xi_{k}, \theta_{k})\rangle$$\partial\beta(\xi_{k}, \theta_{k})$は$(\xi_{k}, \theta_{k})$における$\beta$の劣微分を表し,$\langle\cdot,$$\cdot\}$は$R^{n}\}_{\llcorner}^{arrow}$

おける内積

を表す.
次に修正アルゴリズムが収束することを証明する.

定理 2.
修正アルゴリズムで生成される暫定解列 $\{(x_{k}, t_{k})\}$ の任意の集積点$(\overline{x}$, のは $D$ に含まれる.

定理 3.
修正アルゴリズムで生成される暫定解列 $\{(x_{k}, t_{k})\}$ に対して次が成立する.
$-h_{k}(x_{k})+t_{k}arrow 0$

as$karrow\infty$

この 2 つの定理より, 暫定解列5.

$\{y_{k}\}$の任意の集積点は問題 (1) の大域的最適解になる.

頂点間の連結関係を用いた外部近似法
修正アルゴリズムのステップ 3 における $P_{k+1}$ の更新に伴い, $P_{k+1}$ の頂点集合 $V(P_{k+1})$ を求める必要がある.

従来, 頂点集合 $V(P_{k+1})$ の計算手法として, 極集合の性質を用いた方法が用いられていた. しかし, この手法では各反復において多くの連立一次方程式を解くことになるため, 計算時間が膨大になることが知られている. そこで, 本論文では頂点間の連結関係を用いた頂点集合の計算手法を提案する. このため, 次を定義する.
定義 1. [凸包, アフィン包]$S$を$R^{n}$の部分集合とする. このとき, $S$ の凸包 co $S$ は

co $S:=\{u\in R^{n}:u=\lambda_{1}u^{1}+\lambda_{2}u^{2}, \lambda_{1}+\lambda_{2}=1, \lambda_{1}, \lambda_{2}\geq 0, u^{1}, u^{2}\in S\}$ .
で表される. また, $S$ のアフィン包 aff $S$ はaff $S:=\{u\in R^{n}:u=\lambda_{1}u^{1}+\lambda_{2}u^{2}, \lambda_{1}+\lambda_{2}=1, \lambda_{1}, \lambda_{2}\in R, u^{1}, u^{2}\in S\}$ .
で表される.

253
定義 2. [面, ファセット, 辺]$T$を$R^{n}$の空でない凸多面集合とする. $T$ の空でない部分集合 $F$が次の条件をすべて満たすとき, $F$ は $T$ の面と呼ばれる.

1. $F=(affF)\cap T$ .

2. co$\{u^{1},$$($$u^{2}\})\cap F=\emptyset$$\forall u^{1},$$u^{2}\in T\backslash F$.

ただし, 便宜上 $T$ 自身も $T$ の面であるとする. また, $F$ が $T$ の面であり, $F$ の次元数が $n-1$ のとき, $F$ は $T$ のファセットと呼ばれる. さらに, $F$ が $T$ の面であり, $F$ の次元数が 1 のとき, $F$
は $T$ の辺と呼ばれる.
定義 3. [頂点の連結]の空でない凸多面集合とし, $v’,$ $v”(v’\neq v’’)$ を $T$ の頂点とする.
このとき, co $\{v’, v’’\}$ が $T$ の辺ならば $v’,$ $v”$ は連結しているという.

5.1

を

$T$

$R^{n}$

初期段階における頂点集合の計算

修正アルゴリズムのステップ$0$において, 制約集合 $X$ を覆う

$n$

単体

$S_{n}$

は次のように生成できる.
$S_{n}:=co\{V_{1}, \ldots, V_{n+1}\}$

ただし, $V_{n+1}:=$ yo$+ \sum_{i=1}^{n}re^{i},$,$V_{i}:=V_{n+1}-r(1+\sqrt{n})e^{i}$

. さらに

$D$

を覆う凸多面対瑞は次にしたがって生成できる.
$P_{n}:=co\{(\begin{array}{l}V_{1}\alpha+\beta\end{array}),$ただし,$x\in S_{n}\}$$\alpha$$:= \max\{g(x) :$(p\in\partial g(yo))$$i\in\{1, \ldots, 2(n+1)\}$$(\begin{array}{l}V_{n+1}\alpha+\beta\end{array}),$x\in S_{n}\},$$(\begin{array}{l}V_{n+1}\gamma-\beta\end{array})\}$$(\begin{array}{l}V_{1}\gamma-\beta\end{array}),$$\ldots,$$\ldots,$$\beta:=\max\{h(x):x\in S_{n}\},$,$:= \min\{\langle p,$$\gamma$$x-$ yo $\rangle+g$ (yo):. このとき, 頂点の生成の方法からファセットの数は $n+3$ である. 任意のに対して, $v(i)$ に連結する頂点の添え字集合$\mathcal{V}_{i}$と $v(i)$ を含むファセットの添え字集合乙は次で与えられる.
$\mathcal{V}_{i}:=\{\begin{array}{ll}(\{1, \ldots, n+1\}\backslash \{i\})\cup\{n+1+i\} if i\in\{1, \ldots, n+1\},(\{n+2, \ldots, 2(n+1)\}\backslash \{i\})\cup\{i-(n+1)\} if i\in\{n+2, \ldots,2(n+1)\},\end{array}$$\mathcal{F}_{i}:=\{\begin{array}{ll}\{1\}\cup\{2, \ldots, n+2\}\backslash \{i+1\} if i\in\{1, \ldots, n+1\},\{2, \ldots, n+2\}\backslash \{i+1-(n+1)\}\cup\{n+3\} if i\in\{n+2, \ldots, 2(n+1)\}.\end{array}$52

切除ざれる頂点の計算

修正アルゴリズムの反復 において, 任意の $i\in\{1, \ldots, \ell\}$ に対して, $v(i)=(x_{i}, t_{i})$ と連結してと $v(i)$ を含むファセットの添え字集合
いる頂点の添え字集合が与えられているものとする.
$k$$\mathcal{V}_{i}$$\mathcal{F}_{i}$すなわち, すべての $i\in\{1, \ldots, \ell\}$ に対して次が成立する.

.
$\circ$

任意の$j\in \mathcal{V}_{i}$に対して, co $\{v(i), v(j)\}$ は $(P_{k})$ の辺である.

任意の $j\in$ 斜に対して, $v(i)\in F_{j}$ である.

254

修正アルゴリズムのステップ 2 において, $l_{k}(x, t)$ の生成方法および $P_{k+1}$ の更新方法からと連結している頂点を順次調べることで, 切除される頂$V(P_{k+1})$ が成立する. したがって,
点をすべて求めることができる. 切除される頂点をすべて求めるアルゴリズムは次のとおりである.
$(x_{k}, t_{k})\not\in$$(x_{k}, t_{k})$アルゴリズム A(切除ざれるすべての頂点の計算)
ステップ

$0$

.

$\mathcal{M}:=\mathcal{M}’:=\{i_{k}\}$とする. ただし,は $v(i_{k})=(x_{k}, t_{k})$ を満たす. ステップ 1 へ.

$i_{k}$

ステップ 1.

ならば, アルゴリズムを終了する. その他の場合,$\mathcal{M}’=\emptyset$$j\in \mathcal{M}’$を選び, ステップ 2 へ.

ステップ 2.
ステップ$2\triangleleft$.

ステップ 2-1.

とし, ステップ 2-1 へ.

$\mathcal{T}=\mathcal{V}_{j}$$\mathcal{T}=\emptyset$

ならば, ステップ 3 へ. その他の場合,ステップ 2-2. $l_{k}(x_{s}, t_{s})>0$ かつ$s\not\in \mathcal{M}$ならば,$s\in \mathcal{T}$$\mathcal{M}arrow \mathcal{M}\cup\{s\},$を選び, ステップ 2-2 へ.
$\mathcal{M}’arrow \mathcal{M}’\cup\{s\}$とする.

ステップ 2-3 へ.

ステップ 2-3.

$\mathcal{T}arrow \mathcal{T}\backslash \{s\}$として, ステップ 2-1 へ戻る.

ステップ 3.
$\mathcal{M}’arrow \mathcal{M}’\backslash \{j\}$として, ステップ 1 へ戻る.

アルゴリズム A によって生成される$\forall i\in \mathcal{M},$5.3$v(i)\in V(P_{k})$$\mathcal{M}$に対して, 次が成立する.

and $v(i)\not\in V(P_{k+1})$

新たに生成ざれる頂点の計算

修正アルゴリズムの反復 のステップ 2 で新たに生成される $P_{k+1}$ の頂点を $v\in V(P_{k+1})\backslash V(P_{k})$とすると, 次を満たす $v(i’),$ $v(i”)\in V(P_{k})$ が存在する.
$k$$l_{k}(x_{i’}, t_{i’})<0,$$l_{k}(x_{i’’}, t_{i’’})>0$

and $v\in$ co $\{v(i’), v(i’’)\}$ .

また, 次が成立する.
$v\in F_{j}$$\forall j\in \mathcal{F}_{i’}\cap \mathcal{F}_{i’’}$.

のファセットの数は $n+3$ であり, $P_{k+1}$ の定義から, 反復 で新たに生成される $P_{k+1}$のファセットは一つであり, $F_{n+3+k}$ とすることができる. このとき, 明らかに $v\in F_{n+3+k}$ が成立
さらに,

$k$

$P_{1}$する.
アルゴリズム A により, $V(P_{k})$ の除かれる頂点の添え字集合$\mathcal{M}$が生成されたものとして, 新たに生成される $V(P_{k+1})$ の頂点をすべて求めるアルゴリズムは次のとおりである.

アルゴリズム $B$ (新たに生成されるすべての頂点の計算)
ステップ

$0$

.

$\mathcal{W}:=\emptyset,$$\mathcal{M}’:=\mathcal{M},$$\ell’:=\ell+1$

として, ステップ 1 へ.

255
ステップ 1.

$\mathcal{M}’=\emptyset$

ならアルゴリズムを停止する. その他の場合,$i\in \mathcal{M}’$を選び, ステップ 2 へ.

ステップ 2.

ステップ 2-0.

$\mathcal{T}=\mathcal{V}_{j}$ステップ 2-1.

$\mathcal{T}=\emptyset$とし, ステップ 2-1 へ.

なら, ステップ 3 へ. その他の場合,$s\in \mathcal{T}$を選び, ステップ 2-2 へ.

ステップ 2-2. $l_{k}(x_{s}, t_{s})<0$ なら, ステップ 2-3 へ. $l_{k}(x_{s}, t_{s})=0$ なら, ステップ 2-4 へ.

その他の場合, ステップ 2-5 へ.
ステップ 2-3. $v(\ell’),$$\mathcal{F}_{\ell’},$$\mathcal{V}_{\ell’}$を次のように定める.

$v(\ell’):=(1-\lambda)v(j)+\lambda v(s)$ただし,$\lambda=\frac{l_{k}(x_{j},t_{j})}{l_{k}(Xj,tj)-l_{k}(x_{s},t_{s})}$$\mathcal{F}_{l’};=(\mathcal{F}_{j}\cap \mathcal{F}_{s})\cup\{n+3+k\}$$\mathcal{V}_{\ell’}:=\{s\}$

,

,

.

また,
$\mathcal{V}_{s}arrow(\mathcal{V}_{s}\backslash \{j\})\cup\{\ell’\}$とする. さらに,ステップ 2-4.

$\mathcal{F}_{s},$$\mathcal{W}arrow \mathcal{W}\cup\{\ell’\},$$\mathcal{V}_{s}$$\mathcal{V}_{s}arrow \mathcal{V}_{s}\backslash \{j\}$$\mathcal{W}arrow \mathcal{W}\cup\{s\}$ステップ 2-5.
ステップ 3.

,.
として, ステップ 2-5 へ.

$\mathcal{T}arrow \mathcal{T}\backslash \{s\}$$\mathcal{M}’arrow \mathcal{M}’\backslash \{j\}$として, ステップ 2-5 へ.

と次のように修正する.

$\mathcal{F}_{s}arrow \mathcal{F}_{s}\cup\{n+3+k\}$

また,$\ell’arrow\ell’+1$として, ステップ 2-1 へ戻る.

として, ステップ 1 へ戻る.

アルゴリズム $B$ より, $V(P_{k+1})$ は次のように与えられる.
$V(P_{k+1})=\{v(i):i\in\{1, \ldots , \ell’-1\}\backslash \mathcal{M}\}$また, 任意の54$i\in \mathcal{W}$.

に対して, $v(i)\in F_{n+3+k}$ が成り立つ.

頂点間の連結情報の構築

アルゴリズム $B$ より, $V(P_{k+1})$ のすべての頂点に対してファセットに関する情報は構築されてに対する頂点 $v(i)$ の連結情報は与えられている. また, 任意
に対する頂点 $v(i)$ の $F_{n+3+k}$ に含まれない頂点との連結情報も与えられている. したおり, 任意のの $i\in \mathcal{M}$$i\in(\{1, \ldots, \ell\}\backslash \mathcal{W})\backslash \mathcal{M}$がって, 新たに構築すべき頂点間の連結情報は $\{v(i):i\in \mathcal{W}\}$ 上で構築すればよいことが分かる.
ここで, 次の定理が成立する.
定理 4. $v(i’),$ $v(i”)$ を $P_{k+1}$ の頂点とする. このとき, co $\{v(i’), v(i’’)\}$ が $P_{k+1}$ の辺であるための必要十分条件は$|\mathcal{F}_{i’}\cap \mathcal{F}_{i’’}|=n-1$である. ただし,$|\mathcal{F}_{i’}\cap \mathcal{F}_{i’’}|$は$\mathcal{F}_{i’}\cap \mathcal{F}_{i’’}$の元の個数を表す.

256
ここで,

$\mathcal{W}=${$i_{1},$$\ldots$, it} とすると, 次のアルゴリズムより, $\{V(i) :i\in \mathcal{W}\}$ での頂点の連結情報を構築することができる.
アルゴリズム $C$ (頂点間の連結情報の構築)

ステップ

$0$

. $j=1$ として, ステップ 1 へ.

ステップ 1. $j=t$ なら, アルゴリズムを終了する. その他の場合, ステップ 2 へ.
ステップ 2.
ステップ 2-0. $s=j+1$ とし, ステップ 2-1 へ.
ステップ 2-1. $s=t+1$ なら, ステップ 3 へ. その他の場合, ステップ 2-2 へ.

ステップ 2-2.

$|\mathcal{F}_{i_{j}}\cap \mathcal{F}_{i_{s}}|=n-1$

なら,$\mathcal{V}_{i_{j}}arrow \mathcal{V}_{i_{j}}\cup\{i_{s}\},$とする. ステッ$\mathcal{V}_{i_{s}}arrow \mathcal{V}_{i_{s}}\cup\{i_{j}\}$プ 2-3 へ.
ステップ 2-3. $sarrow s+1$ として, ステップ 2-1 へ戻る.
ステップ 3. $jarrow j+1$ として, ステップ 1 へ戻る.

したがって, 修正アルゴリズムのステップ において, $V(P_{1})$ を生成し, 各反復 のステップ 3
においてアルゴリズム $A,$ $B,$
を用いることで, $V(P_{k+1})$ および頂点間の連結情報を構築すること
$k$

$0$

$C$

ができる. ただし, 各反復$k$

でアルゴリズム $A,$ $B,$ $C$ を効率的に実行するためには, ステップ 3 の終了後に $V(P_{k+1})$ に含まれる頂点の添え字の番号を昇順 (あるいは降順) に整理する必要がある.

6

数値実験
修正アルゴリズムの有効性を検証するために, 次の問題に対して数値実験を行う.

$\{\begin{array}{ll}minimize g(x)-h(x):=(\frac{1}{2}\sum_{i=1}^{n}p_{ai}x_{i}^{2}-\sum_{i=1}^{n}p_{bi}x_{i}+p_{c})-(\frac{1}{2}\sum_{i=1}^{n}q_{ai}x_{i}^{2}-\sum_{i=1}^{n}q_{bi}x_{i}+q_{c})subject to a(x);=\frac{1}{2}\sum_{i=1}^{n}a_{i}(x_{i}-b_{i})^{2}-c\leq 0, x\inR^{n},\end{array}$(2)
ただし, $p_{ai},p_{bi},p_{c},$10 $(i\in\{1, \ldots, n\})$ とする.
ここで, $g(x)$ と $h(x)$ はいずれも凸関数なので, 目的関数は DC 関数である. また, 制約関数
は微分可能な凸関数なので擬凸関数である. 数値実験では, 各次元数 $n=1,$において,の値を乱数を用いて定め, 許容誤差を $\tau=0.001$ として, 20 個の問題に対して修正アルゴリズムを実行した. 実験は新潟大学大学院自然科学研究科の高速演算サー
バ (CPU:Xeron MP $3.33GHz-8MB\cross 3$ , RAM: $6GB$ , OS:Linux) で行い, プログラミングには言語を用いた. 数値実験の結果は表 1, 2 のとおりである. ただし, 表 1, 2 内のは修正アルゴリズムが停止したときの凸多面体の頂点数を表す.
$q_{ai},$ $q_{bi},$ $q_{c},$ $a_{i},$$b_{i},$$c\in\{1,$ $\ldots$ ,

$\}$

$8$

$\ldots,$$p_{ai},p_{bi},p_{c},$ $q_{ai},$ $q_{bi},$ $q_{c},$ $a_{i},$$b_{i},$$c$$C$$V_{last}$$P_{k}$

表 1 の計算時間の平均から, 次元数 が高高 6 以下の問題 (2) に対して, 修正アルゴリズムが有効であることがわかる. また, 問題の次数がの時, 外部近似は $n+1$ で行われていることに注
意する.
$n$

$n$

257

表 1: 修正アルゴリズムの数値実験結果 (平均)表 2: 修正アルゴリズムの数値実験結果 (標準偏差)7

おわりに
本研究では, 問題 (1) に対し, Tuy[4] が提案した外部近似法を改善した新たなアルゴリズムを提案した. ここでは頂点間の連結関係を用いた新たな頂点計算方法を導入した. また, 提案したアルゴリズムが大域的収束性を持っことを示した. さらに, 数値実験により修正アルゴリズムの有効性を検証した.

参考文献[1] P. Hartman, “On Functions Representable as a Difference of Convex Functions, “ Pacific
Journal of Mathematics, pp.707-713, 1959.
[2] R. T. Rockafellar, “Convex Analysis,” Princeton, 1970.
[3] H. Tuy, ”Convex Analysis and Global optimization,” Kluwer Academic Publishers, 1998.
[4] H. Tuy, “TECHNICAL NOTE: On Global Optimality Conditions and Cutting Plane Algorithms,” Joumal of optimization Theory and Applications, Vol.118, pp201-216, 2003.

258[5] S. Yamada, T. Tanaka and T. Tanino: Outer Approximation Method Incorporating a
Quadratic Approximation for a DC Programming Problem,
Journal of optimization Theory and Applications(to appear)[6] 久保幹雄, 田村明久, 松井知己編, 応用数理計画ハンドブック, 朝倉書店, 2002.