数理解析研究所講究録
1068 巻 1998 年 1-12

1

弱有効解集合上での凸関数最小化問題に対する
内部近似法
山田修司, 谷野哲三, 群口雅弘

Syuuji YAMADA, Tetsuzo TANINO, Masahiro INUIGUCHI大阪大学大学院工学研究科

1

はじめに
次の多目的計画問題が与えられているものとする.
$(P)\{$

maximizesubject to$\langle_{C^{i}}, X\rangle$

,

$i,$

$x\in X\subset R^{n}$$k$$\ldots,$,,

であり, 制約集合 $X$ はコンパクトな凸集合とする. 多目的計を問題 $(P)$ に対する弱有画問題 $(P)$ において, $x\in X$ が次の条件を満足するとき, その効解という.
ただし,$c^{i}\in R^{n},$$i=1,$$k$$\ldots,$$x$$\not\in y\in X$

such that$\langle_{C^{i}}, X\rangle<\langle c^{i}, y\rangle$$\forall i\in\{1, \ldots, k\}$.

ここで, 問題 $(P)$ に対して次が成立するものとする.

(A1) $X=\{x\in R^{n} : Pj(X)\leq 0,j=1, \ldots, t\}$ と表せる. ただし,はとなる微分可能な凸関数である.

$p_{j}$: $R^{n}’arrow R(j=1, \ldots, t)$$p_{j}(\mathrm{O})<0$(A2) int
int$C\neq\emptyset$$C$となる. ただし, $C=\{.x\in R^{n} : \langle_{C^{i}}, X\rangle.\underline{<}0,. i=1, \ldots, k\}$ である. ただし,は $C$ の内部集谷を表す.

仮定 $(A1)$ より, $p(x):= \max_{j=1,\ldots,tP}j(X)$ とすると, $X=\{x\in R^{n} : p(x)\leq 0\}$ と表すことはができる. さらに仮定 $(A1)$ より, int
なので, 問題 $(P)$ の弱有効解の集合
は$X$と表すことができる. 一般に, 問題 $(P)$ に対する弱有効解集合$X\neq\emptyset$。

$X_{e}$$X_{e}$$=X\backslash \mathrm{i}\mathrm{n}\mathrm{t}(X+C)$

凸集合であるとは限らない.
.
上での凸関数最小化問題について
本研究では, 上で与えられた問題 $(P)$ の弱有効解考える. 問題 $(P)$ の制約集合 $X$ が線形制約で定義されている場合 (すなわち, $X$ は凸多面
$X_{\dot{e}}$体), Konno, Thach and Tuy [71 によってこのような問題に対する切除平面法が提案されている. 本研究では, 制約集合 $X$ が非線形制約で定義されている場合についても有効な逐次解法を提案する.

2

2

弱有効解集合上での凸関数最小化問題
次の弱有効解集合上での凸関数最小化問題について考える.
$T$minimize$(OES)\{$
subject to
ただし, 目的関数

(B1)

$f$

$f$

$f(x)$$x\in X_{e}$,: $R^{n}arrow R$ は次の仮定を満足する.

は凸関数,(B2) $f( \mathrm{O})=\inf\{f(x) : x\in R^{n}\backslash \{0\}\}$ ,(B3) $\arg\min\{f(X):x\in R^{n}\}=\{0\}$ .
問題 $(OES)$ は次のように表すことができる.
$(MP)\{$

minimizesubject to$g(x)=f(x)+\delta(x|X)$ ,$x\in R^{n}\backslash \mathrm{i}\mathrm{n}\mathrm{t}(X+C)$

,

ただし,
$0$

$\delta(x|X)=\{$$+\infty$

また, 問題

if $x\in X$ ,.
if
$x\not\in X$$(MP)\ovalbox{\tt\small REJECT}_{-}^{arrow}n_{\backslash }g-\mathrm{g})\pi \mathrm{x}\backslash 1$$(DP)\{$

maximizesubject to$g^{H}(x)$D7 \iota よのように表される.
,$x\in(X+C)^{\mathrm{o}}$,は $X+C$ の極集合, すなわち, $(X+C)^{\mathrm{o}}=\{y\in R^{n}$ :ただし, 制約集合$\forall x\in X+C\}$ , さらに目的関数: $R^{n}arrow R$ は問題 $(MP)$ の目的関数 : $R^{n}arrow R$ の準共役関数, すなわち,$(X+C)^{\mathrm{o}}$$\langle x, y\rangle\leq$$g^{H}$$1,$$- \sup\{g(u) :u\in R^{n}\}$$g^{H}(x)=\{$$- \inf\{g(u) :\langle x, u\rangle\geq 1\}$$g$

if $x=0$ ,if $x\neq 0$ ,である. 仮定 $(A1)$ より $0\in$ , int $(X+C)$ なので, 問題 $(DP)$ の制約集合$(X+C)^{\mathrm{o}}$はコンが成立する. また, 目的関数
: $R^{n}arrow R$ は準凸
パクトな凸集合で,の境界上に問題 $(DP)$ の最適解が存在する.
関数なので,
上で定義された問題 $(MP)$ と問題 $(DP)$ に対して次の双対性が成立する (Konno, Thachand Tuy [7] 参照).
$(X+c)^{\mathrm{o}}=x^{0}\cap C^{\mathrm{O}}$$g^{H}$$(X+C)^{\mathrm{o}}$$\inf(MP)=-\sup(DP)$ただし, $\inf(MP)$ は問題 $(MP)$ の最適値, $\sup(DP)$ は問題 $(DP)$ の最適値を表す.

3

3

弱有効解集合上での凸関数最小化問題に対する内部近似法

3.1

内部近似法のアルゴリズム

問題 $(MP)$ に対して次の内部近似法のアルゴリズムを提案する.

Algorithm$\mathrm{I}\mathrm{A}\mathrm{M}-(MP)$かつ $0\in$ int
Initialization.
て, Step 1 へ行く.
$S_{1}\subset X$

Step 1. 次の問題$(P_{k})\{$

問題

minimizesubject to$(D_{k})\{$$v^{k}$

Step 2. 問題$\alpha_{k}$maximizesubject to$(D_{k})$, 最適解をを生成する. $karrow 1$ とし$g(x)$ ,$x\in R^{n}\backslash \mathrm{i}\mathrm{n}\mathrm{t}$$g^{H}(x)$$(S_{k}+C)$ .

$(D_{k})$の最適解を$v^{k}$とする.

,$x\in(S_{k}+C)^{\mathrm{o}}$.

$f(x)$ ,$x\in X\cap\{x\in R^{n}.

の最適解$z^{k}$$v^{k}$\langle v^{k}, x\rangle\geq 1\}$(1).

に対する次の制約なし凸最小化問題を解き, その最適値をとする.

minimizesubject to$\{$$S_{1}$に対する次の凸計画問題の最適解を $x(k)$ とする.

minimizesubject to$\{$を満足する凸多面体

を考える.

$(P_{k})$に対する次の双対問題$(P_{k})$さらに,$S_{1}$.

$\phi(x;v)k=\max\{p(x), -\langle v^{k}, x\rangle+1\}$$x\in R^{n}$

,

(2)

.

(a) $\alpha_{k}=0$ ならばアルゴリズムを停止する. このとき, 沸は問題 $(DP)$ の最適解,$x(k)$ は問題 $(MP)$ の最適解となる.
(b) (a) の条件が成立しない場合,とする, ただしは $(S_{k}\cup\{z^{k}\})$ の凸包を表す. $karrow k+1$ として, Step 1 へ戻る.
$S_{k+1}=\mathrm{c}\mathrm{o}(S_{k}\cup\{z^{k}\})$

Algorithm$\mathrm{I}\mathrm{A}\mathrm{M}-(MP)$より生成される$S_{k},$$k=1,2,$たす. したがって, 錐 $C$ は凸多面錐なので, 任意のることがわかる. さらに, 次が成立する.
$\bullet$

任意の

$k$

に対して,

を満
, は凸多面体でありに対しては凸多面体であ$\mathrm{O}\in \mathrm{i}\mathrm{n}\mathrm{t}S_{k}$$\ldots$$k$$\mathrm{c}.\mathrm{o}(S_{k}\cup\{z^{k}\})$$(S_{k}+C)^{\mathrm{o}}$4$=(S_{k})\circ \mathrm{n}c^{0}$$(S_{k}+c)^{\circ}$$\mathfrak{l}$$=\{x\in R^{n} :ただし, $V(S_{k})$ は凸多面体\langle z, x\rangle\leq 1\forall z\in V(S_{k}), \langle u, x\rangle\leq 0\forall u\in E(C)\}$$S_{k}$の頂点集合であり, $E(C)$ は次を満たす凸多面錐 $C$ の

端方向ベクトルの有限集合である.
$C=\{x\in R^{n}$ : $x= \sum_{(u\in EC)}\lambda uu’\lambda_{u}>0\}$

任意の$\bullet$$k$.

に対して, $S_{k}+C=\{x\in R^{n} : \langle v, x\rangle\leq 1, \forall v\in V((S_{k}+C)^{\mathrm{o}})\}$ となる.

の頂点集合
上での岬町関数最大化問題なので,の最適の最適値を $\inf(P_{k})$ , 問題
から最適解諮を選ぶことができる. また, 問題
値を $\sup(D_{k})$ と表すと, $\inf(P_{k})=-\sup(D_{k})$ が成立する.
問題 $(D_{k})$ は凸多面体$(S_{k}+C)^{\mathrm{o}}$$(S_{k}+C)^{\mathrm{o}}$$(D_{k})$$(P_{k})$

3.2

凸多面体

の生成法

$S_{1}$

を生成する –方法を提案する.
を満足する凸多面体
かつ本節では,最初に, $0\in R^{n}$ を内部に含む凸多面体を生成するために, 次の集合を定義する.
$S_{1}\subset X$$T=$$S_{1}$$0\in \mathrm{i}\mathrm{n}\mathrm{t}S_{1}${ $e^{12..},$$e,.,$ e ,$e^{n+1}$}

は 番目の要素が 1 でる単位ベクトルで
ただし, 任意の $i\in\{1, \ldots , n\}$ に対して,かつあり, $e^{n+1}\in R^{n}$ はすべての要素が $-1$ のベクトルとする. 明らかに, $0\in$ int
は凸多面体となる.
は $X$ に含まれるとは限らなを生成する. 上で定義した凸多面体
次に凸多面体となるためには,い.
$e^{i}\in R^{n}$$i$$(\mathrm{c}\mathrm{o}T)$$\mathrm{c}\mathrm{o}T$$\mathrm{c}\mathrm{o}T$$S_{1}$$\mathrm{c}\mathrm{o}T\subset x$$\max\{p(e) :e\in T\}\leq 0$, すなわち $p(e^{i})>0$ とを満足すればよい. ここで, ある $i\in\{1, \ldots, n+1\}$ に対してする. このとき, 関数 が凸関数であり, $p(\mathrm{O})<0$ であることから次が成立する.
$e^{i}\not\in X$$P$$p(\lambda_{i}e^{i}+(1-\lambda i)0)=p(\lambda_{i}e^{i})\leq\lambda_{i}p(e^{i})+(1-\lambda i)p(0)=0$. また, $p(\mathrm{O})<0$ なので, $0<-p(\mathrm{O})<p(e^{i})-p(0)$ となり, $0<\lambda_{i}<1$となる. したがって, 任意の $i\in\{1, \ldots, n+1\}$ に対して

ただし,$\lambda_{i}=\frac{-p(0)}{p(\text{。^{}i})-p(0)}$$\lambda_{i}=$とし,$\overline{T}=\{\lambda_{1}e^{1}, \lambda_{2}e,., \lambda n+1e\}2..n+1$が成立する. 以上より,が成立する. また, 明らかに $0\in$ intを定めると,
が得られる.
を満足する凸多面体
かつとすることにより,である.
の頂点集合は
このとき,$(\mathrm{c}\mathrm{o}\overline{T})$$\mathrm{c}\mathrm{o}\overline{T}\subset X$$S_{1}\subset X$$S_{1}=\mathrm{c}\mathrm{o}\overline{T}$$S_{1}$$V(S_{1})=\overline{T}$$\mathrm{O}\in \mathrm{i}\mathrm{n}\mathrm{t}S_{1}$$S_{1}$

5
3.3

問題

$(P_{k})$と問題 (1) についての各反復
本節では, Algorithmの最適解が求まることを示す.
$\mathrm{I}\mathrm{A}\mathrm{M}-(MP)$において, 問題 (1) を解くことにより問題$k$$(P_{k})$Remark 3.1$S_{k}\subset X$$(S_{k}+C)^{\mathrm{o}}\supset(X+C)^{\mathrm{o}}$ならば, $S_{k}+C\subset X+C$ が成立する. さらに,が成立する.

Lemma 3.1 Algorithm $IAM-(MP)$ の反復$(S_{k})^{\mathrm{o}}\supset x\circ$

かつにおいて, $v^{k}\neq 0$ .

$k$を満足する $x’\in X$ が存在する.
に対して,)Proof 任意の $y\in$ (bdはに対しての境界集合を表す. したがって, 任意の
ただし,$g^{H}(y)>-\infty$ となる. さらに,は問題の最適解であり,$g^{H}(v^{k})>-\infty$が成り立つ. よって, $g^{H}(0)=-\infty$ なので,が成立するので,(bd)$X^{\mathrm{o}}$$\langle y, x’\rangle=1$$\cap C^{\mathrm{O}}$$x\circ$$\mathrm{b}\mathrm{d}X^{\mathrm{o}}$$y\in(\mathrm{b}\mathrm{d}X\circ)\cap C^{\mathrm{o}}$$v^{k}$$X^{\mathrm{O}}$$\cap C^{\mathrm{O}}$が示される.

$v^{k}\neq 0$

口Lemma 3.2 Algorithm $IAM-(M.P).$
して$(S_{k}+C)^{\mathrm{o}}\supset(X+C)^{\mathrm{o}}\supset$$(D_{k})$となる.

$v\not\in \mathrm{i}\mathrm{n}\mathrm{t}X^{\mathrm{O}}$. の反復において, 任意の $v\in V(S_{k}+c)\backslash \{0\}$ に対$k$はを仮定して矛盾を導く.
$(S_{k}+C)^{\mathrm{o}}=\{x\in R^{n} : \langle z, x\rangle\leq 1\forall z\in V(S_{k}), \langle u, x\rangle\leq 0\forall u\in E(C)\}$ の頂点であるので,次が成立する.

Proof

ある$\exists a^{1},$$\ldots,$に対して $v\in$ int$v\in V((S_{k}+c)^{\mathrm{o}})\backslash \{\mathrm{o}\}$$a^{r}\in V(S_{k})\cap E(C)$$x\circ$$v$

such that $\dim\{a^{1..r},., a\}=n$and$\langle a^{i}, v\rangle=b_{i}i=1,$$\ldots,$$r$

ただし, 任意の $i\in\{1, \ldots, r\}$ に対して,$b_{i}=\{$

1if $a^{i}\in V(S_{k})$ ,if $a^{i}\in E(C)$$0$となる. ここで,る $y.\in R^{n}$$x\circ\subset(S_{k})^{\mathrm{o}}=$

.

に対して

$\exists z\in V(S_{k})$

したがって,$v$$y\not\in \mathrm{i}\mathrm{n}\mathrm{t}X$such that$\{x\in R^{n} :\langle z, x..\rangle\leq 1\forall.z\in V(S_{k}.)\}$

より、次の条件を満足すが成立する.

$\langle z, y\rangle\leq 1$.

の仮定より, $\{a^{1}, \ldots, a^{r}\}\subset E(C)$ となる. このとき, $\dim\{a^{1}, \ldots, a^{r}\}=n$ よ-り$\ovalbox{\tt\small REJECT}\{x\in R^{n} :\langle a^{i}, x\rangle=0\}=\{0\}$矛盾.1 したがって, 任意のなので, v–$v\in V((S_{k}+c)^{\mathrm{o}})\backslash \{\mathrm{o}\}$Lemma 3.3 Algorithm $IAM-(MP)$ の反復
Proof.

$v^{k}$

は$(S_{k}+C)^{\mathrm{o}}$

$0$

$k$

となる. これは

に対して

において,

$k$

に

が成り立つ.

口$v\not\in \mathrm{i}\mathrm{n}\mathrm{t}X^{\mathrm{O}}$$v^{k}\not\in \mathrm{i}\mathrm{n}\mathrm{t}X^{\mathrm{O}}$の頂点なので, Lemma 3.1, 32 より,

Theorem 3.1 Algorithm $IAM-(MP)$ の反復$v\in V((S_{k}+c)^{\mathrm{o}})\backslash \{\mathrm{o}\}$.

$v^{k}\not\in \mathrm{i}\mathrm{n}\mathrm{t}X^{\mathrm{O}}$において, 次が成立する.

が示される.

口6(i)$X\cap\{x\in R^{n} :\langle v^{k}, x\rangle\geq 1\}\neq\emptyset$.

(ii) $x(k)$ は問題$(P_{k})$の制約集合に含まれる, すなわち,(iii) $x(k)$ は問題$(P_{k})$の最適解である.

$x(k)\in R^{n}\backslash \mathrm{i}\mathrm{n}\mathrm{t}(S_{k}+C)$となる.

Proof.
(i): Lemma 33 より,存在する. よって,となる. したがって,$v^{k}\not\in \mathrm{i}\mathrm{n}\mathrm{t}X^{\mathrm{o}}$(ii):$x(k)\in\{x\in R^{n} :$v^{k}\in(S_{k}+C)^{\mathrm{o}},$.

(iii):$X\cap\{x\in R^{n} :$x(k)\not\in \mathrm{i}\mathrm{n}\mathrm{t}(S_{k}+C)$$v^{k}$

を満足する $x’\in X$ が.

\langle v^{k}, x\rangle\leq 1\}\neq\emptyset$

および $((S_{k}+C)^{\mathrm{o}})^{\circ}=S_{k}+C$ より,\langle v^{k}, x\rangle\geq 1\}$となる. したがって, $x(k)$ は問題

は問題 $(D_{k})$ の最適解かつ問題 $(D_{k})$ は問題$\inf(P_{k})$$\langle v^{k}, x’\rangle\geq 1$$(P_{k})$$(P_{k})$の制約集合に含まれる.

の双対問題なので次が成立する.

$=- \sup(D_{k})$$=-g^{H}(v^{k})$$= \inf\{g(x) :\langle v^{k}, x\rangle\geq 1\}$$= \inf\{f(x) :(Lemma 3.1$X\text{り}$)\langle v^{k}, x\rangle\geq 1, x\in X\}$$= \inf(1)$ただし, inf(l) は問題 (1) を表す. したがって, $f(X(k))=g(x(k))= \inf(P_{k})$ が成立する.
口

Algorithm

3.4

本節では, Algorithm$\mathrm{I}\mathrm{A}\mathrm{M}-(MP)$の停止規準についての停止規準の妥当性を示す.

$\mathrm{I}\mathrm{A}\mathrm{M}-(MP)$Lemma 3.4 任意の $v\in R^{n}$ に対して, 問題 (2) の目的関数 $\phi(x;v)$ の最小値が存在する.
上関数 は連続関数かつ $X=\{x\in R^{n} : p(x)\leq 0\}$. はコンパクト集合なので,で関数 を最小とする解が存在する (Hestens [3], Theorem 2.1). ここで, $\alpha:=\min\{P(X)$ :に対してレベル集$x\in R^{n}\}$ とする.
このとき, 関数 は真凸関数なので, 任意の合 $L_{P}(\gamma)=\{x\in R^{n} : p(x)\leq\gamma\}$ はコンパクト集合である (Rockarfellar [12], Corollary

Proof$R^{n}$$P$$P$$\gamma\geq\alpha$$P$87.1). また, $\inf_{x\in R^{n}}\emptyset(X;v)=\mathrm{i}\mathrm{n}\mathrm{f}x\in Rn\max\{p(x), h(X, v)\}\geq\inf_{x\in R^{n}P}(x)=\alpha$ が成立するの
かつ任意の
に対して
で, $\beta:=\inf_{x\in R^{n}\phi}(X, v)$ とすると,はコンパクト集合である. よって,に対してが成り立つ. したがって, 任意の任意の $v\in R^{n}$ に対して, 問題 (2) の目的蘭数 $\phi(x;v)$ の最小値が存在する (Hestens [3],口Theorem 2.1).
$\beta\geq\alpha$$\gamma\geq\beta$$L_{p}(\gamma)\supset L_{\phi}(\gamma)\neq\emptyset$$\gamma\geq\beta$$L_{\phi}(\gamma)$が存在する. ここで, 任Lemma 3.4 より, 任意の $v\in R^{n}$ に対して, 問題 (2) の最適解
ならば諮 $\in(X+C)^{o}$ となる. また, 次が成立
意の
なので,
に対して,
$z^{k}$$k$

する.

$v^{k}\in C^{o}$$v^{k}\in X^{o}$7
Lemma 3.5 Algorithm $IAM-(MP)$ の反復(i)$\alpha_{k}\leq 0$

において,

$k$

ならば次が成立する.

$S_{k}\subset X$,(ii) $z^{k}\in X$ .

Proof. Lemma 33 より,したがって, 次が成立する.

$v^{k}\not\in \mathrm{i}\mathrm{n}\mathrm{t}X^{\mathrm{O}}$なので,$\langle v^{k},\hat{x}.\rangle\geq 1$

を満足する

.

$\alpha_{k}=\min_{x\in R^{n}}\phi(x;v^{k})\leq\phi(\hat{x};v)k=\max\{p(\hat{X}), -\langle v^{k},\hat{x}\rangle+1\}\leq 0$

また,$\alpha_{k}\leq 0$が存在する.

$\hat{x}\in X$

より, $p(z^{k})\leq\alpha_{k}\leq 0$ が成立する. したがって, $z^{k}\in X$ が成立する.

口

ここで, $S_{1}\subset X$ かつ Lemma 3.5 より次が成立する.
$\bullet$$S_{1}+C\subset S_{2}+C\subset\cdots\subset S_{k}+C\subset\cdots\subset X+C$,$\bullet(S_{1}+c)^{\circ}\supset(S_{2}+c)^{\circ}\supset\cdots\supset(S_{k}+c)^{\circ}\supset\cdot\cdot..\supset(X+c)^{\circ}$.

これより, 任意の $k\geq 2$ に対して $\sup(D_{k-1})\geq\sup(D_{k})$ となるので, 次式が成立する.
$g^{H}.$ $(v^{1}.)$.

$\geq g^{H}(v^{2})\geq\cdots\geq g^{H}(v^{k})\geq\cdots\geq\sup(DP)$

.

(3)

.

同様に, 任意の $k\geq 2$ に対して $\inf(P_{k-1})\leq\sup(P_{k})$ となるので, 次が成立する.
$f(x(1)) \leq f(x(2))\leq\cdots f(x(k))\leq\cdots\leq\inf(MP)$ .

以下では, Algorithm$\mathrm{I}\mathrm{A}\mathrm{M}-(MP)$が有限回の反復で停止した場合について考える.

Theorem 3.2 Algorithm $IAM-(MP)$ の反復
条件は$v^{k}\in x\circ$

(4)

$k$

において, $\alpha_{k}=0$ となるための必要十分が成立することである,

.

ならばが
まず,
となることを示す.
を満足する
より,が存在する. また,:.
開集合なので, 次が成立する.

Proof$\alpha_{k}=0$$v^{k}\not\in x.\circ$$\langle v^{k},\hat{x}\rangle>1$$\exists\in>0$such that$\in X^{\mathrm{o}}$$v^{k}\not\in x\circ$$\hat{x}\in X$$B(\hat{x}, \epsilon:)\subset\{x\in R^{n} :と仮定して矛盾を導く.

$\{x\in R^{n} :\langle v^{k}, x\rangle>1\}$は\langle v^{k}, x\rangle>1\}$

ただし, $B(\hat{x}, \in)--\{y\in R^{n} : ||y-\hat{x}||<\epsilon\}$ . したがって, (int $.X$ ).
に対して次が成立する.
で, 任意の $x’\in$ (int $X$ )$\cap B(\hat{X}, \epsilon)\neq\emptyset$となる. ここ$\cap B(\hat{x},\hat{\mathrm{C}})$$\alpha_{k}=\min_{x\in Rn}\emptyset(X;v)k=$而 n $\max\{p(x), -\langle v^{k}, x\rangle+1\}\leq\max\{p(X’), -\langle v^{k}, x’\rangle+1\}<0$ .

明らかに $\alpha_{k}=0$ に矛盾するので, $v^{k}\in x\circ$ となることを示された.

次に,$v^{k}\in x\circ$$X\subset\{x\in R^{n} :ならば $\alpha_{k}=0$ となることを示す.

\langle v^{k}, x\rangle\leq 1\}$$v^{k}\in x\circ$ならば,$(X^{\mathrm{O}})^{\circ}=X$なので,が成り立つ. したがって, $X\cap\{x\in R^{n} : \langle v^{k}, x\rangle>1\}=\emptyset$ . よって、次式を満たす $x\in R^{n}$ は存在しない.

8

図 1: $S_{k+1}+C$ and $(S_{k+1}+c)^{\mathrm{o}}$ ; $H(z^{k})=\{x:\langle z^{k}, X\rangle=1\}$ .

$p(x)<0$ かつ$-\langle v^{k}, x\rangle+1<0$.

したがって, 任意の $x\in R^{n}$ に対して, $\alpha_{k}=\phi(x;v^{k})\geq 0$ となる. -方, Lemma 3.5 より
口なので, $\alpha_{k}=0$ が成立する.

$\alpha_{k}\leq 0$

Theorem 3.3 Algorithm $IAM-(MP)$ の反復 においての最適解であり, さらに $x(k)$ は問題 $(MP)$ の最適解となる.
$k$$\alpha_{k}=0$ならば,$v^{k}$

は問題 $(DP)$となる. また,と仮定する. Theorem 32 より,
Proof.
が成立する. したがって, $g^{H}(v^{k}) \leq\sup(DP)$ となる. さなので,は問題となるで, $g^{H}(v^{k}) \geq\sup(DP)$らに,の最適解であり,となる. よって, $g^{H}(v^{k})-- \sup(DP)$ となり, 諮は問題 $(DP)$ の最適解となる.
かつ次に, $x(k)$ が問題 $(MP)$ の最適解となることを証明する.
が成り立つ. したがって, $x(k)$ は問題 $(MP)$ のであるので,
制約集合に含まれる. Theorem 3.1 より$v^{k}\in X^{\mathrm{O}}$$\alpha_{k}=0$$v^{k}\in(S_{k}+c)^{\circ}\subset C^{\mathrm{O}}$$v^{k}\in X^{\mathrm{o}}\cap C^{\mathrm{O}}=(X+C)^{\mathrm{o}}$$v^{k}$$(D_{k})$$(S_{k}+C)^{\mathrm{o}}\supset(X+C)^{\mathrm{o}}$$\langle v^{k}, x(k)\rangle\geq 1$$(X+C)^{\mathrm{o}}$$v^{k}\in$$x(k)\not\in \mathrm{i}\mathrm{n}\mathrm{t}(X+C)$$f(X(k))=-g^{H}(v^{k})=- \sup(DP)=\inf(MP)$ .

が成立し, $x(k)$ は問題 $(MP)$ の最適解となる.

口ならばとなる. したがっの反復んにおいて,て, $S_{k}+C\subset\{x\in R^{n} : \langle v^{k}, x\rangle\leq 1\}$ であるので, $S_{k+1}+C=\mathrm{c}\mathrm{o}(S_{k}\cup\{z^{k}\})+C\neq S_{k}+C$となる. また, $V(S_{k+1})\subset V(S_{k})\cup\{z^{k}\}$ より 1 次が成立する (図 1).

Algorithm$\alpha_{k}<0$$\mathrm{I}\mathrm{A}\mathrm{M}-(MP)$$(S_{k+1}+C)^{\mathrm{o}}=(S_{k}+C)^{\mathrm{o}}\cap\{x\in R^{n} :\langle_{Z^{k}}, X\rangle\leq 1\}\neq(S_{k}+C)^{\mathrm{o}}$Remark 32 Algorithm $IAM-(MP)$ の反復$\langle z^{k}, v\rangle=1$,$\langle v^{k}, z^{k}\rangle>1$$k$.

において, 次が成立する.

$\forall v\in V((S_{k+1}+C)^{\mathrm{o}})\backslash V((s_{k}+C)^{\mathrm{o}})$.

9
Algorithm

3.5$\mathrm{I}\mathrm{A}\mathrm{M}-(MP)$

本節では, Algorithm
まず, 次の Theorem を示す.

$\mathrm{I}\mathrm{A}\mathrm{M}-(MP)$の収束性

が有限回の反復で停止しなかった場合について考える.

Theorem 3.4 Algorithm $IAM-(MP)$ より生成される問題
意の集積点は問題 $(DP)$ の制約集合 $(X+C)^{o}$ に含まれる.

$(D_{k})$の最適解の列$\{v^{k}\}$の任はコンパクト集合 $(S_{1}+C)^{O}$ に含まれるので, 集積点が存在する. そこで,とする. Algorithmの任意の部分列をに収束するとし,の任意の集積点をおよび最適値の数列に対応して問題 (2) の最適解の列
よりProof.

$\{v^{k}\}$$\{v^{k}\}$$\{v^{k_{q}}\}$$\{v^{k}\}$$\overline{v}$$\overline{v}$$\{z^{k_{q}}\}$$\{v^{k_{q}}\}$$\mathrm{I}\mathrm{A}\mathrm{M}-(MP)$$\{\alpha_{k}\}$が存在する.
は Lemma 35 により, コンパクト集合 $X$ に含ま
を示す.
まず,
の部分列
に収束する
とすると,
れるので, 集積点が存在する. 任意の集積点をはに収束する. ここで, Algorithm
の部分列
に対応する
が存在する.
が有限回の反復で停止しない場合について考えているので, 任意の $l\in\{1,2, \ldots\}$
.
.:.
.
に対して
. したがって,$\{z^{k_{q}}\}$$\lim_{qarrow\infty^{\alpha}k_{q}}=0$$\{v^{k_{q}}\}$$\{z^{l}\}$$\{z^{l}\}$$\{z^{k_{q}}\}$$\overline{z}$$\overline{z}$$\{v^{l}\}$$\overline{v}$$\mathrm{I}\mathrm{A}\mathrm{M}-(MP)$$\alpha_{l}<0$.

$0> \alpha_{l}=\max\{p(z^{l}), h(Z^{\iota}, v^{l})\}\geq-\langle v^{l}, Z^{\iota}\rangle+1$,$\forall l\in\{1,2, \ldots\}$.

なので,よって, 任意の $l\in\{1,2, \ldots\}$ に対して$v^{l’}\in(S_{l+1}+C)^{\mathrm{o}}=(S_{l}+C)^{\mathrm{o}}\cap\{x\in$が成立する. -方, 任意の $l\in\{1,2, \ldots\}$ に対してが成立する. したがって,: $\langle z^{l}, x\rangle\leq 1\}(l’>l)$ であるので,$\langle v^{ll}, Z\rangle>1$$R^{n}$$\lim_{larrow\infty}\langle v^{l}, Z^{l}\rangle=\langle\overline{v},\overline{z}\rangle\geq 1$$\langle v^{l1}, Z^{\iota}\rangle+=\langle\overline{v},\overline{z}\rangle\leq 1$が成り立つ. . また, $X$ のコンパクト性より,が示される (Aubin, [1], Chapter 1, Section 6, Proposition 1). $X$ はコンパクト集合なので$\lim_{qarrow\infty}\langle\overline{v}, z^{k_{q}}\rangle=1$$\lim_{larrow\infty}\langle v^{\iota}, Z^{l}\rangle=\langle\overline{v},\overline{z}\rangle=1$$\mu\geq\sup\{||X|| :x\in X\}$を満足する $\mu>0(\mu\in R^{n})$ が存在する. したがって, 次式が成立

する.
$\lim_{qarrow\infty}\sup\langle v^{k}q, Z\rangle k_{q}$$= \lim_{qarrow\infty}\sup\langle v^{k_{q}} - \overline{v}, z^{k_{q}}\rangle+\lim_{qarrow\infty}\sup\langle\overline{v}, Z\rangle k_{q}$$= \lim_{qarrow\infty}\sup\langle v^{k_{q}} - \overline{v}, z^{k_{q}}\rangle+1$$\leq\lim_{qarrow\infty}\sup||vk_{q}-\overline{v}||\cdot||z^{k_{q}}||+1$$\leq\lim_{qarrow\infty}\sup||vk_{q}-\overline{v}||\cdot\mu||+1$$=0+1=1$ .
方, 次式も成立する.
$\lim_{qarrow\infty}$

inf$\langle v^{k_{q}}, Z^{k_{q}}\rangle$$= \lim_{qarrow\infty}\inf\langle v^{k_{q}} - \overline{v}, z^{k_{q}}\rangle+\lim_{qarrow\infty}\inf\langle\overline{v}, z\rangle k_{q}$$= \lim_{qarrow\infty}\inf\langle v^{k_{q}} - \overline{v}, z^{k_{q}}\rangle+1$$\geq\lim_{qarrow\infty}$

inf$||v^{k_{q}}-\overline{v}||\cdot(-||z^{k_{q}}||)+1$$\geq\lim_{qarrow\infty}\inf||v^{k_{q}}-\overline{v}||\cdot(-\mu)+1$$=0+1=1$ .
したがって,

10$\lim_{qarrow\infty}\langle v^{k_{q}}, Z\rangle k_{q}=1$(5).

となる. Lemma 35 より,$\lim_{qarrow\infty}\inf\alpha k_{q}=\lim_{qarrow\infty}$

よって,

次に,

$\lim_{qarrow\infty}\alpha_{k_{q}}=0$$\overline{x}\in x\circ$$\exists x’\in X$

また,

$h$

$\lim_{qarrow\infty}\sup\alpha_{k_{q}}\leq 0$. また, (5) より,

inf $\max\{p(z^{k_{q}}), h(zk_{q}, v^{k}q)\}\geq\lim_{qarrow\infty}\inf h(zkq, v)k_{q}=0$.

.

を証明する.

such that$\overline{v}\not\in X^{o}$とすると, 次式か成立する.

$h(x’,\overline{v})=-\langle\overline{v}, X’\rangle+1<0$.

の連続性より,$\exists\in>0$such that $B(x’, \in)\subset\{x\in R^{n} : h(x,\overline{v})<0\}$ .

なので, 任意のが成立する. このことより,となる. int$X\neq\emptyset$$\exists\delta>0$such that(int $X$ )$v\in B(\overline{v}, \delta)$,$\cap B(X\epsilon)’$$h( \overline{x}, v)<\frac{1}{2}h(\overline{x},\overline{v})<0,$がいえる. したがって, 任意の$\min_{x\in R^{n}}\phi(x;v)$$\overline{x}\in$に対して $p(\overline{x})<0$ かつ$\forall v\in B(\overline{v}, \delta)$$h(\overline{x},\overline{v})<0$.

に対して, 次が成立する.

$= \min_{x\in R}\max\{np(X), h(x, v)\}$$\leq\max\{p(\overline{X}), h(\overline{x}, v)\}$$\leq\max\{p(\overline{X}), \frac{1}{2}h(\overline{x},\overline{v})\}<0$ゆえに,.. 以上より,の任意の集積点は. よって,
は閉集合なので,$\lim_{qarrow\infty}\alpha k_{q}\leq\max\{p(\overline{x}), \nu\}<0$$\{v^{k}\}$$c\circ$$\overline{v}\in C^{\mathrm{o}}$次の Theorem より,$\{v^{k}\}$$X^{o}$.

となり, (5) に矛盾する. ;に含まれる. さらに,$\{v^{k_{q}}\}\subset(S_{1}+\dot{C})^{\mathrm{o}}\subset..\cdot c\circ$$\overline{v}\in X^{\circ}\cap c^{\circ}=(X+C)^{\mathrm{o}}$かつが成立する.

口の任意の集積点が問題 $(DP)$ の最適解であることもわかる.

Theorem 3.5 Algorithm $IAM-(MP)$ により生成される問題
任意の集積点は問題 $(DP)$ の最適解である.

$(D_{k})$の最適解の列$\{v^{k}\}$のとする. ここで, 関数の部分列をの任意の集積点を , に収束する$f$ : $R^{n}arrow R,$ $h:R^{n}\cross R^{n}arrow R$ の連続性, $X$ のコンパクト性, および任意のProof.

$\{v^{k}\}$$\overline{v}$$\{v^{k}\}$$\overline{v}$$\{v^{k_{q}}\}$$v\in c^{0}\backslash (\mathrm{i}\mathrm{n}\mathrm{t}x\circ)$に対して $\{x\in R^{n} : \langle v, x\rangle\geq 1, x\in X\}=\{x\in R^{n} : -h(X, v)\geq 0, x\in X\}\neq\emptyset$ が成立する
は上で上半連続となる (Hogan [4]). したがって, (3) よりことより, 関数$g^{H}$$C^{\mathrm{o}}\backslash (\mathrm{i}\mathrm{n}\mathrm{t}X\mathrm{O})$.

次が成立する.
$g^{H}( \overline{v})\geq\lim_{qarrow\infty}\sup g(Hv)k_{9}\geq\sup(DP)$また, Theorem 34 より$g^{H}( \overline{v})=\sup(DP)$ が成立する.

$\overline{v}\in(X+C)^{\mathrm{o}}$.

なので, $g^{H}( \overline{v})\leq\sup(DP)$ が成り立つ. したがって,また, 問題 (1) (問題 $(MP)$ ) の最適解の列 $\{X(k)\}$ に対して次が成立する.

口

11
Remark 3.3 Algorithm $IAM-(MP)$ の任意の反復関数 $f$ の仮定 $Bl,$$\langle v^{k}.’x\rangle=1\}$$B\mathit{2},$$B\mathit{3}$$k$において, 問題 (1) の最適解 $x(k)$ は,, さらに $0\in\{x\in R^{n} : \langle v^{k}, x\rangle<1\}$ より,. $x(k)\in\{x\in R^{n}$ :となる.

Remark 3.4 問題 $(MP)$ の制約集合$R^{n}\backslash \mathrm{i}\mathrm{n}\mathrm{t}(X+C)$$R^{n}\backslash \mathrm{i}\mathrm{n}\mathrm{t}(X+C)\supset X\backslash \mathrm{i}\mathrm{n}\mathrm{t}(X+C)\neq\emptyset$に対して次が成立する.

.

Theorem 3.6 Algorithm $IAM-(MP)$ より生成される問題 (1) の最適解の列 $\{X(k)\}$ の任意の集積点は問題 $(MP)$ の最適解である.
Proof 問題 (1) の最適解の列 $\{X(k)\}$ はコンパクト集合 $X$ に含まれるので, 集積点が存在し, その集積点は $X$ に含まれる. さらに, $\{X(k)\}$ の任意の集積点 に対して収束する部が存在する. また、 $\{x(k_{q})\}$ に対して, 問題 $(DP)$ の最適解の列
分列勧が存在する. Remark 3.3 より, 任意の $q\in\{1,2, \ldots\}$ に対してとなる. したがって,が成立する. また,の任意の集積点をとなる. Theorem 34 より, $\overline{v}\in(X+C)^{o}$ なので, Xに対して,となる. したがって,
かつ X
なので, 問題 $(MP)$ の制約集合に含まれる.
$\{x(k_{q})\}\subset X$ かつ
は Algorithmの反復における問題 (1) の最適解なので, 任意の $g^{H}(v^{k_{q}})=-g(x(k_{q}))=-f(x(k_{q})),$ $q=1,2,$が成立する. したがって,
Theorem 35 と関数 の連続性より,$\overline{x}$$(k_{q})\}$$\{v^{k_{q}}\}$$\langle v^{k_{q}}, X(k_{q})\rangle=1$$\lim_{qarrow\infty}\langle v^{k_{q}}, X(k_{q})\rangle=\lim_{qarrow\infty}\langle v^{k_{q}},\overline{x}\rangle=1$$\{v^{k_{q}}\}$$\langle\overline{v},\overline{x}\rangle=1$$\overline{v}$$\in \mathrm{b}\mathrm{d}(X+C)$$\overline{x}\in X$$\not\in \mathrm{i}\mathrm{n}\mathrm{t}(X+C)$$x(k_{q})$$\mathrm{I}\mathrm{A}\mathrm{M}-(MP)$$k_{q}$$\ldots,)$

$f$

.

$.=$

$\inf(MP)=-\sup(DP)=-\lim_{qarrow\infty}g^{H}(v^{k_{q}})=\lim_{qarrow\infty}f(x(k_{q}))=f(\overline{x})$となり, $\{x(k)\}$ の任意の集積点は問題 $(MP)$ の最適解となる

口

参考文献[1] Aubin, J.P., Applied Abstract Analysis, John Wiley, New York (1977).
[2] Bazaraa, M.S.,. Sherali and. Shetty, Nonlinear Programming: Theory andAlgorithms, 2nd ed., John Wiley, New York (1993).
$\mathrm{H}.\mathrm{D}$$\mathrm{C}.\mathrm{M}$[3] Hestenes, M.R., Optimization Theory: The Finite Diesinal Case, John Wiley, NewYork (1975).

[4] Hogan, W.W.,
Maps in Mathematical Programming”, SIAM Review,Vol. 15, No. 3(1973) pp.591-603.
“$\mathrm{p}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{G}-\mathrm{T}\mathrm{o}^{- \mathrm{s}\mathrm{e}}\mathrm{t}$[5] Horst, R. and H. Tuy, Global Optimization, Springer-Verlag, Berlin (1990).
[6] Horst, R. and. Pardalos, Handbook of Global Optimization, Kluwer Academic
Publishers, Dordrecht (1995).
$\mathrm{P}.\mathrm{M}$12. Thach and H. Tuy, Optimization on Low Rank Nonconvex Structures[7] Konno, H.,
Kluwer Academic Publishers, Dordrecht (1997).
$\mathrm{P}.\mathrm{T}$[8] Kuno, T., Y. Yajima and H. Konno, “An Outer Approximation Method for Minimizing the Product of Several Convex Functions on a Convex Set,” Journal of Global
Optimization, 3 (1993), pp.325-335.

Optimization Approach to Optimizing over the. Muu,. and[9] Luc,
Efficient Set,” Lecture Notes in Economics and Mathematical Systems, 452: Recent
Advances in Optimization (1996), pp.183-195.
(($\mathrm{L}.\mathrm{D}$$\mathrm{L}.\mathrm{T}$$\mathrm{G}1_{0}\mathrm{b}\mathrm{a}1$. Todd, $Optimi_{Z}ationf$ Handbooks in Op[10] Nemhauser, G.L., A.H.G.R. Kan anderations Research and Management Science, Vol.1, Elsevier Science Publishers, B.V(1989).
$\mathrm{M}.\mathrm{J}$for the Vector Maximization Problem,” Mathematical Program[11] Philip, J.,
ming, 2 (1972), pp.207-229.
($\zeta \mathrm{A}\mathrm{l}\mathrm{g}\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{m}$[12] Rockafellar, R.T., Convex Analysis Princeton University Press, Princeton,$\mathrm{N}.\mathrm{J}$. (1970).

[13] Sawaragi, Y., H. Nakayama and T. Tanino, Theory of Multiobjective Optimization,
Academic Press, Orland (1985).