逆凸計画問題に対する内部近似法の改良
富山短期大学
経営情報学科
山田修司
(Syuuji YAMADA)
大阪大学大学院
工学研究科
佐藤研吾
(Kengo SATO)
大阪大学大学院
工学研究科
谷野哲三
(Tetsuzo TANINO)
大阪大学大学院
工学研究科
乾口雅弘
(Masahiro INUIGUCHI)
1
はじめに
大域的最適化の分野において
, 代表的な問題の-つに閉凸集合
$X$
の内部集合の補集合と閉凸集合
$\mathrm{Y}$の
共通集合を実行可能集合にもつ逆凸計画問題がある.
この問題は配置問題や経済モデルなどにみられ
,
ま
た
, 凹最小化問題, 凸差計画問題など多くの非線形計画問題は
,
等価な逆凸計画問題に変換できることが
知られている. –般に, 逆凸計画問題の実行可能集合が凸集合ではなく,
従来の非線形計画問題の解法に
より直接大域的最適解を求めることは困難である.
しかし,
この問題は国守集合
$x$
の内部集合の補集合
上における準凸関数最小化問題と等価であり,
その双対問題は閉凸集合
$X$
の極集合上における準凸関数最
大化問題となる
.
したがって
,
この双対性を利用することで
,
元の逆凸計画問題の大域的最適解を得ること
が可能となる
.
本研究では,
一般の有界な閉凸集合の内部集合
$X$
の補集合と閉凸集合
$\mathrm{Y}$の共通集合を実行可能集合に
もつ凸関数最小化問題を対象とする
.
従来,
このような逆凸計画問題に対しては外部近似法や内部近似法
に基づいた逐次解法が提案されている.
この外部近似法に基づいた解法は
, 閉凸集合
$x$
を生成する凸関
数を凸多面体上で最大化する部分問題を逐次的に解くことによって
, 逆凸計画問題の大域的最適解を得る
手法であり,
内部近似法に基づいた解法は
, 閉凸集合
$X$
を内部から凸多面体によって近似し, 部分問題と
してその凸多面体の内部集合の補集合と閉凸集合
$\mathrm{Y}$の共通集合上で目的関数の最小化を逐次的に行うこ
とで
,
大域的最適解を得る手法である.
しかし
,
これらの解法には実際にアルゴリズムを実行する上でい
くつかの問題点が挙げられる
.
外部近似法に基づくアルゴリズムでは,
各反復において凸多面体の頂点集
合を正確に計算する必要があり
, 実際の数値実験では計算精度に関して困難が生じることがある.
また内
部近似法においても, 部分問題を解く際に,
複数のアフィン関数それぞれにより生成される半空間と集合
$Y$の共通集合が空集合であるか否かの判定を行う必要があり
,
さらに,
内部から集合
$x$
を近似する凸多
面体を拡張する際に,
制約なし連続微分不可能な凸関数最小化問題を解く必要がある.
そこで,
本研究で
は従来の内部近似法に対してペナルティ関数法を適用することでこの判定を回避し
,
さらに各反復におい
て直線探索を行うことで元の問題の最適値を過小評価する逐次近似解法を提案する
.
2
逆凸計画問題
本研究では次の逆凸計画問題を対象とする
.
$(RCP)\{$
而 ni 而 ze
$f(x)$
,
subject to
$x\in Y\backslash \mathrm{i}\mathrm{n}\mathrm{t}X$.
ただし
,
$f$:
$R^{n}arrow R$
は微分可能な凸関数,
集合
$X\subset R^{n}$はコンパクトな凸集合
,
$Y\subset R^{n}$は閉凸集合と
(A1)
$Y\backslash \mathrm{i}\mathrm{n}\mathrm{t}X\neq_{-}\emptyset$.
(A2)
ある
$\alpha$.
$\in R$に対して
,
$\{x\in R^{n} :
f(x)\leq\alpha\}$
は空ではないコンパクト集合である.
(A3)
$X=\{x\in R^{n}$
:
$Pj(X)\leq 0,$
$j=1,$
$\ldots,t_{x\}},$$Y=\{x\in R^{n} :
r_{j}(x)\leq 0, j=1, \ldots, t_{Y}\}$
とする
.
ただ
し,
$Pj(X)$
:
$R^{n}arrow R(j=1, \ldots, t_{X}),$
$r_{j}(x)$:
$R^{n}arrow R(j=1, \ldots, t_{Y})$
は微分可能な凸関数である.
また
, ある
$x_{X},$ $\prime y_{Y}\in R^{n}$に対して
,
$Pj(xx)<0(j=1, \ldots, t_{x),r_{j}(X}Y)<0(j=1, \ldots, t_{Y})$
が成立
する
.
ここで
,
$p(x)= \max\{p_{j}(X) : j=1, \ldots, t_{X}\},$ $r(x)= \max\{r_{j}(X) : j=1, \ldots, t_{Y}\}$
とする
.
このとき
, 仮
定
(A3)
より
,
$X=\{x\in R^{n} :
p(x)\leq 0.\},$
$Y=\{x\in R^{n} :
r(x)\leq 0\}$
,
int
$X=\{x\in R^{n} :
p(x)<0\}$
,
int
$Y=\{x\in R^{n} :
r(x)<0\}$
となる
.
また
, 仮定
(A2)
より,
$R^{n}$上における関数
$f(x)$
の最小値が存在す
る
.
さらに
,
任意の
$\beta\geq\min\{f(x) :
x\in R^{n}\}$
に対して
,
$\{x\in R^{n} : f(x)\leq\beta\}$
は空でないコンパクト集
合である
.
仮定
(A1)
より,
問題
$(RCP)$
.
の実行可能解
$x’$が存在し,
このとき問題
$(RCP)$
は次の問題と
等価である
.
minimize
$f(x)$
,
subject
to
$x\in(Y\backslash \mathrm{i}n\mathrm{t}X)\cap\{x\in R^{n} : f(x)\leq f(x’)\}$.
$\{x\in R^{n} :
f(x)\leq f(x’)\}$
はコンパクト集合であることから, 問題
$(RCP)$
は最適解をもつ. 仮定
(A1), (A2)
より
,
集合
$Y$は空でなく
$Y$上で関数
$f(x)$
を最小とする解
$x^{0}$が存在することがわかる.
$x^{0}\in R^{n}\backslash \mathrm{i}\mathrm{n}\mathrm{t}$$X$
ならば
,
$x^{0}$は問題
$(RCP)$
の解である.
そこで
,
本研究を通じて以下の仮定を置く
.
(A4)
$x^{0}=0$
とする
(
すなわち
$r(\mathrm{O})\leq 0,$ $\mathrm{O}\in Y$).
さらに,
$p(0)<0$
つまり
$\mathrm{O}\in \mathrm{i}\mathrm{n}\mathrm{t}$$X$
とする
.
(A5)
$M>\triangle(X)$
である.
ただし
,
$\triangle(X)$は
$X$
の直径で,
$\triangle(X):=\max\{||x-y|| :
x,y\in X\}$
である.
問題
$(RCP)$
は次の問題に等価である.
minimize
$g(x)$
,
(1)
subject
to
$x\in R^{n}\backslash \mathrm{i}\mathrm{n}\mathrm{t}X$.
ここで
,
$g(x):=f(x)+\delta(x|\mathrm{Y})$
である
.
ただし
,
$\delta(x|X)=\{$
$0$
$x\in X$
の場合
,
$+\infty$ $x\not\in X$
\mbox{\boldmath$\sigma$})1台,
とする.
目的関数
$g(x):R^{n}arrow\overline{R}(\overline{R}=R\cup\{-\infty\}\cup\{+\infty\})$は準凸関数であり
, 仮定
(A4)
より,
$g(\mathrm{O})=$$\inf\{g(x) : x\in R^{n}\}$
である
. この問題
$(MP)$
の双対問題は次のようになる
.
$(DP)$
(2)
ただし
,
関数
$g^{H}(u)$
は関数
$g(x)$
の準共役関数,
集合
$X^{\mathrm{o}}$は集合
$X$
の極集合であり,
以下のように定義
される.
$g^{H}(u)=\{$
$- \sup\{f(x):x\in R^{n}\}$
$u=0$
の場合
,
$- \inf\{f(x):\langle u,x\rangle\geq 1\}$
$u\neq 0$
の場合
,
$X^{\mathrm{O}}=\{u\in R^{n} :\langle u,x\rangle\leq 1,\forall x\in X\}$
,
である
.
仮定
(A4)
と双対理論より,
$X^{\mathrm{o}}$はコンパクトな凸集合であり,
さらに
$g^{H}(u)$
は準凸関数であるので,
問
題
$(DP)$
は
$R^{n}$上のコンパクトな凸集合上での準凸最大化問題となる
.
$\min(MP),$
$\max(DP)$
をそれぞれ
問題
$(MP)$
,
問題
$(DP)$
の最適値を表すものとする.
問題
$(MP)$
は問題
$(RCP)$
と等価で而 n(MP)
$=$$\min(RcP)<+\infty$
であり
, さらに問題
$\langle$$MP)$
と問題
$(DP)$
の双対関係から
$\min(MP)=-\max(DP)$
で
ある
(Konno, Thach and Tuy [2], Chapter 4).
3
内部近似法に基づいた従来のアルゴリズム
本章では
, 本研究で対象とする問題
$(RCP)$
に対して
,
Yamada,
Tanino and
In 萌與 chi
[3]
によって提
案されている内部近似法に基づくアルゴリズムについて述べる
.
これは
,
逆凸制約を生成する閉凸集合
$X$
に対して,
$S_{k}\subset X$を満たす凸多面体の列
$S_{1}\subset S_{2}$C.
.
.
$\subset S_{k}\subset\ldots\subset X$を生成し
, 集合
$Y\backslash \mathrm{i}\mathrm{n}\mathrm{t}S_{k}$上に
おいて関数
$f(x)$
を逐次的に最小化することにより問題
$(RCP)$
の大域的最適解を求める解法である.
31
問題
$(MP)$
および
$(DP)$
に対する緩和問題
問題
$(MP)$
を解くことが困難な理由として集合
$X$
が凸多面体でないことが挙げられる
.
集合
$X$
が凸
多面体ならば, 問題
$(MP)$
の実行可能集合を半空間の和集合によって表すことができ,
それぞれの半空間
上で関数
$g(x)$
を最小化することによって,
問題
$(MP)$
は容易に解くことができる.
本節では,
次の問題について考える.
$(P)\{$
minimize
$g(x)$
,
subject
to
$x\in R^{n}\backslash \mathrm{i}\mathrm{n}\mathrm{t}S$,
ただし
,
集合
$S$は
$S\subset X,$ $\mathrm{O}\in \mathrm{i}\mathrm{n}\mathrm{t}S$を満たす凸多面体である.
このとき
,
$R^{n}\backslash \mathrm{i}\mathrm{n}\mathrm{t}$ $S\supset R^{n}\backslash \mathrm{i}\mathrm{n}\mathrm{t}X$なの
で
,
問題
$(P)$
は問題
$(MP)$
の緩和問題である
.
さらに関数
$g$の定義から, 問題
$(P)$
は次の問題と等価で
ある
.
$\{$
minimize
$f(x)$
,
subject to
$x\in Y\backslash \mathrm{i}\mathrm{n}\mathrm{t}S$.
$(Y\backslash \mathrm{i}\mathrm{n}\mathrm{t}S)\supset(Y\backslash \mathrm{i}\mathrm{n}\mathrm{t}X)\neq\emptyset$
なので
, 仮定
(A2)
より
,
$\mathrm{Y}\backslash \mathrm{i}\mathrm{n}\mathrm{t}S$上における関数
$f(x)$
の最小解
が存在し,
これは問題
$(P)$
の最適解でもある.
したがって
, 問題
$(P)$
の最小値を
$\min(P)$
と表すと,
$\min(P)\leq\min(MP)<+\infty$
が成り立つ
.
問題
$(P)$
の双対問題は次のように表すことができる
.
$(D)\{$
maximize
$g^{H}(u)$
,
subject to
$u\in S^{\mathrm{o}}$.
$S\subset X$
であることから
, 問題
$(D)$
の実行可能集合は
$x\circ$を含むので, 問題
$(D)$
は問題
$(DP)$
の緩和問題
である
.
ここで,
$S$は
$\mathrm{O}\in \mathrm{i}\mathrm{n}\mathrm{t}S$を満たす凸多面体なので, 実行可能集合
$S^{\mathrm{o}}$も凸多面体である
.
したが
$\text{っ}$て
,
問題
$(D)$
は凸多面体
$S^{\mathrm{o}}$上における準凸最大化問題であるため
, 問題
$(D)$
の最適解は
$S^{\mathrm{O}}$の頂点集
合
$V(S^{\mathrm{o}})$に含まれる.
問題
$(D)$
の最適値を
$\max(D)$
と表すと
, 問題
$(D)$
は問題
$(P)$
の双対問題であり
,
問題
$(DP)$
の緩和問題であることから,
$\max(D)=-\min(P)\geq-\min(MP)=\max(DP)>-\infty$
が成り
立つ
(Konno, Thach and Tuy [2], Chapter 4).
したがって
, 問題
$(D)$
の最適解は
$V(S^{\mathrm{o}})$から得られる
.
ここで,
双対性から
,
$S^{\mathrm{o}}=\{u\in R^{n} : \langle u, z\rangle\leq 1, \forall z\in V(S)\}$
,
(3)
$S=\{x\in R^{n} : \langle v, x\rangle\leq 1, \forall v\in V(S^{\mathrm{o}})\}$
.
が成立するので
,
$0\not\in V(S^{\circ})$である
.
任意の
$v\in V(S^{\circ})$に対して
,
$g^{H}(v)=- \inf\{g(X):\langle v,x\rangle\geq 1\}$
が成立する
.
関数
$g$の定義から,
任意の
$v\in V(S^{\circ})$
に対して
,
$g^{H}(v)=\{$
$-\infty$ $(Y\cap\{x\in R^{n}:\langle v,x\rangle\geq 1\}=\emptyset)$
,
$- \inf\{f(x) : \langle v,x\rangle\geq 1, x\in \mathrm{Y}\}$ $(Y\cap\{x\in R^{n} : \langle v,x\rangle\geq 1\}\neq\emptyset)$
,
補題 31
[3]
$Y\cap\{x\in R^{n} : \langle v,x\rangle\geq 1\}\neq\emptyset$を満たす
$v\in V(S^{\circ})$が存在する
.
$Y\cap\{x\in R^{n} : \langle v,x\rangle\geq 1\}\neq\emptyset$
を満足するすべての
$v\in V(S^{\mathrm{o}})$の集合を
$\Gamma$とする
. このとき補題 31 よ
り
,
$\Gamma\neq\emptyset$である.
ここで
,
すべての
$v\in\Gamma$に対して次の凸最小化問題を考える.
$(SP(v))$
仮定
(A2)
より
,
任意の
$v\in\Gamma$に対して,
問題
$(SP(v))$
は最適解
$x^{v}$をもつ.
このとき,
問題
$(SP(v))$
の
最適値を
$\min(SP(v))$
とすると,
$g^{H}(v)=- \min(SP(v))=-f(x^{v})$
が成り立つ.
したがって,
$f(x^{\hat{v}})=$$\min\{f(x^{v}):v\in V(S^{\mathrm{o}})\}$
ならば
$\hat{v}\in\Gamma$は問題
$(D)$
の最適解である.
さらに,
$x^{\hat{v}}$は問題
$(P)$
の最適解であ
る
(Konno,
Thach and
Tuy [2],
Proposition 43).
しかし,
$\Gamma$を生成,
すなわち
$Y\cap\{x\in R^{n} : \langle v, x\rangle\geq 1\}$$(v\in V(S^{\mathrm{o}}))$
が空であるか否かを判定するためには, すべての
$v\in V(S^{\mathrm{o}})$に対して
, 次の制約あり凸最小
化問題
minimize
$r(x)$
,
subject to
$\langle v,x\rangle\geq 1$,
を解く必要がある.
そこで
, 次節では
Yamada,
Tanino and Inuguchi [3]
によって提案された
$\Gamma$を生成す
る必要のない手法を説明する
.
3.2
ペナルティ関数法による緩和問題の過小評価
本節では,
ペナルティ関数を用いることにより緩和問題
$(P)$
を過小評価する内部近似法について述べる.
前節において問題
$(P)$
の最適解を得るために, すべての
$v\in\Gamma\backslash V(S^{\mathrm{o}})$に対して凸制約をもつ凸最小化
問題である問題
$(SP(v))$
を解く必要があった
.
そこで,
$S\subset X$を
$\mathrm{O}\in \mathrm{i}\mathrm{n}\mathrm{t}S$を満たす凸多面体とし, 任
意の
$v\in V(S^{\circ})$に対して次の問題を考える
.
$(SP1(v, \mu))\{$
mlnimize
$F_{v,\mu}(x)=f(x)+\mu\theta_{v}(x)$
,
subject to
$x\in R^{n}$
.
ただし
,
$\theta_{v}(x)=\sum_{j=1}^{t_{Y}}[\max\{0, r_{j}(X)\}]^{S}+[\max\{0, h(x,v)\}]^{s},$
$s>1,$
$\mu>0$
とする.
このとき
, 問題
$(SP1(v,\mu))$
の目的関数
$F_{v,\mu}(x)$は凸関数なので
, 問題
$(SP1(v,\mu))$
は制約なし凸最小化問題である.
ま
た
, $s>1$ のとき関数
$F_{v,\mu}(x)$は連続微分可能である
(Bazaraa,
Sherali
and Shetty [1], Chapter 9).
この
ように
, ペナルティ関数法を用いることによ
$\text{っ}$て制約あり凸最小化問題
$(SP(v))$
を制約なし凸最小化問題
$(SP1(v, \mu))$
に変換することができる
.
本章では, 各反復で問題
$(SP(v))$
の代わりに問題
$(SP1(v, \mu))$
を
解くアルゴリズムに対しても
,
問題
$(MP)$
の最適解への大域的収束性が保証されることを示す
.
次の補題 32 から, 任意の
$v\in V((S_{k})\circ)$
に対して問題
$(SP1(v,\mu))$
の最適解の存在性が保証される
.
補題 32
[3]
すべての
$v\in R^{n},$
$\mu>0$
に対して
,
関数
$F_{v,\mu}(x)$は
$R^{n}$上に最小値をもつ.
補題
32
から
,
すべての
$v\in V(S_{k}^{\mathrm{O}})$に対して関数
$F_{v,\mu}(x)$が
$R^{n}$上に最小値をもつので
,
ペナルティ関
数法を用いた内部近似法では,
各反復において
$\Gamma_{k}$を生成しなくても良いことがわかる
.
問題
$(SP1(v,\mu))$
の最適値を
$\min(SP1(v,\mu))$
と表すと
, 関数
$g^{H}(u)$
の定義から,
$v\not\in\Gamma$ならば,
$\min(SP1(v, \mu))<-g^{H}(v)=+\infty$
であり
,
$v\in\Gamma$ならば, 任意の
$x\in Y\cap\{x\in R^{n} :
\langle v,x\rangle\geq, l\}$
に
対して
$F_{v,\mu}=f(x)$
である.
ゆえに
,
$\min(SP1(v,\mu))$
$= \min\{F_{v,\mu}(x) :
x\in R^{n}\}$
$\leq\min\{F_{v,\mu}(x) : \langle v,x\rangle\geq 1, x\in \mathrm{Y}\}$
$= \min\{f(X) : \langle v,x\rangle\geq 1, x\in Y\}$
(4)
$= \min(SP(v))$
$=-g^{H}(v)$
が成立する.
したがって
, 問題
$(SP1(v,\mu))$
と緩和問題
$(P),$
$(D)$
の間には次のような関係が成立する
.
$\min(P)$
$= \min\{\min(SP(v)) : v\in\Gamma\}$
$\geq\min\{\min(SP1(v,\mu)):v\in\Gamma\}$
(5)
$\geq\min\{\min(SP1(v,\mu)):v\in V(S^{\mathrm{o}})\}$
,
$\max(D)$
$= \max\{g^{H}(v):v\in V(S^{\mathrm{o}})\}$
(6)
$\leq\max\{-\min(SP1(v,\mu)):v\in V(S^{\mathrm{o}})\}$
.
33
アルゴリズム
Yamada,
Tanino and Inuiguchi [3]
によって提案された問題
$(MP)$
に対するペナルティ関数を用いた内
部近似法アルゴリズムは次のとおりである.
アルゴリズム
IA-PI
ステップ
$0$.
パラメータ
$\mu_{1}>0,$
$B>1,$
$s>1$ を選ぶ
.
$V_{1}\subset X$かつ
$\mathrm{O}\in \mathrm{i}n\mathrm{t}(\mathrm{c}\mathrm{o}V_{1})$を満たす有限集合
$\ovalbox{\tt\small REJECT}$を生成する
.
$S_{1}=\mathrm{c}\mathrm{o}V_{1}$とし
,
$(S_{1})^{\mathrm{o}}$の頂点集合
$V((S_{1})0)$
を求める
.
$karrow 1$
としてステップ 1\sim .
ステップ
1.
すべての
$v\in V((S_{k})0)$
に対して
,
制約なし凸最小化問題
$(SP1\langle v,\mu_{k}))$の最適解を
$x_{v}^{k}$とす
る.
さらに,
$v^{k} \in\arg\min\{F_{v,\mu}(kx)v:kv\in V((S_{k})\mathrm{O})\}$
を求める
.
$x(k)=x^{k}v^{k}$
とし
,
$A_{k}=F_{v,\mu k}k(x(k))$
とする
.
ステップ
2.
$\mathrm{a}$
.
$p(x\langle k))\geq 0,$$r(x(k))\leq 0$
ならば
,
アルゴリズムを停止する
.
このとき
,
$x(k),$
$A_{k}$はそれぞれ
問題
$(MP)$
の最適解および最適値である
.
$\mathrm{b}$.
その他の場合,
次の制約なし凸最小化問題の最適解を
$z^{k}$,
最適値を
$\omega^{k}$とする
.
$\{$minimize
$\phi(x;v^{k})=\max\{p(x), h(x,v)k\}$
,
subject
to
$x\in R^{n}$
.
(7)
ただし,
$h(x, v^{k})=-\langle v^{k}, x\rangle+1$
である.
ここで,
$\mu_{k+1}V_{k1}+$$==\{$
$V_{k}\cup\{Z^{k}\}$if
$\omega_{k}<0$,
$V_{k}$if
$\omega_{k}=0$,
$B\mu_{k}$if
$\theta_{v^{k}}$(x(み))
$>0$
,
$\mu_{k}$if
$\theta_{v^{k}}(x(k))=0$
,
とする
.
さらに
$S_{k+1}=\mathrm{c}\mathrm{o}V_{k+1}$とし
,
$V((S_{k+1})0)$
を求める
.
み
$arrow$み
+1
として
, ステップ
1.
へ
.
補題
32
から
, 任意の
$v\in V((S_{k})0),$
$k=1,2,$
$\ldots$,
に対して
,
$R^{n}$上における凡
,\mu k
$(x)$
の最小値が存在
することがわかる
.
補題 33
[3]
アルゴリズム
IA-Pl
の任意の反復みにおいて,
$A_{k} \leq\min(RcP)$
が成立する.
定理
3.1
[3]
アルゴリズム
IA-Pl
の任意の反復みにおいて
,
$p(x(k))\geq 0,$
$r(x(k))\leq 0$
ならば,
$x(k)$
は
補題
33,
定理 31 より, アルゴリズム
IA-PI
の停止基準が満足されるならば
,
$x(k),$
$A_{k}$はそれぞれ問題
$(MP)$
の最適解および最適値である.
また,
次の定理より,
アルゴリズム
IA-PI
の大域的収束性が保証される.
定理
32
[3]
アルゴリズム
IA-Pl
により生成される点列
$\{v^{k}\}$の集積点を
$\overline{v}$とする
.
このとき,
$\overline{v}\in X^{\mathrm{o}}$である.
定理
33
[3]
アルゴリズムハ-Pl
$\iota\text{\v{c}}$より生成される点列
{x(
み
)}
は無限点列であるとする
.
このとき
,
{x(
み
)}
の任意の集積点
$\overline{x}$は問題
$(RCP)$
の最適解である.
定理
34
[3]
アルゴリズム
IA-Pl
により生成される点列
$\{v^{k}\}$は無限点列であるとする
.
このとき
,
$\{v^{k}\}$の任意の集積点
$\overline{v}$は問題
$(DP)$
の最適解である.
4
内部近似法の改良
(1)
第 3 章で説明したアルゴリズム
IAM-PI
は
,
各反復で問題
$(SP1(v,\mu))$
の鼠適解を得ることで大域的収
束性が保証される
. 本章では
,
各反復において問題
$(SP1(v,\mu))$
の最適値を過小評価する新たな手法を提案
する.
新たに提案される手法は
, 逐次的に過小評価を厳密にすることで,
大域的収束性が保証される.
41
アルゴリズム
各反復において問題
$(SP1(v,\mu))$
の最適比を過小評価するアルゴリズムは次のとおりである
.
アルゴリズム
IA-P2
数列
$\{\tau_{k}\}$は
$\lim_{karrow\infty^{\mathcal{T}}k}=0,$$\tau_{k}>0(k=1,2, \ldots)$
を満たすものとする
.
ステップ
$0$.
パラメータ
$\mu_{1}>0,$
$B>1,$
$s>1$ を選ぶ.
$V_{1}\subseteq X$かつ
$\mathrm{O}\in \mathrm{i}n\mathrm{t}$(
$\mathrm{c}\mathrm{o}$Vl)
を満たす有限集合
$\ovalbox{\tt\small REJECT}$を生成する
.
$S_{1}=\mathrm{c}\mathrm{o}$巧とし,
$(S_{1})^{\mathrm{o}}$の頂点集合
$V((s_{1})0)$
を求める
.
み
$arrow 1$としてステップ
1
ヘ
.
ステップ
1.
すべての
$v\in V((s_{k})0)$
に対して
, 制約なし凸最小化問題
$(SP1(v, \mu k))$
を考える
.
この問題
に対して,
$||\nabla F_{v,\mu k}(X^{k}v)||<\tau_{k}$
(8)
を満たす
$x_{v}^{k}$を求める.
さらに
,
$v^{k} \in\arg\min\{F_{v,\mu_{k}}\langle x_{v}^{k})-||\nabla F_{v,\mu}k(x_{v}^{k})||\cdot M(x_{v}^{k}) : v\in V((S_{k})0)\}$
を求める.
ただし
,
$M(x_{v}^{k})=\{$
$M$
$(_{X_{v}^{k}\in}X)$,
$M+||x_{v}|k|$
$(x_{v}^{k}\not\in X)$,
とする.
$x(\text{み})=x_{v^{k}}^{k}$とし
,
$A_{k}=F_{v^{k},\mu_{k}}(x(k))-||\nabla F_{v^{k},\mu_{k}}(x(k))||\cdot M(X(\text{み}))$
とする
.
$\mathrm{a}$
.
$A_{k}=F_{v^{k},\mu_{k}}$(x(み)),
$p(x(k))\geq 0,$
$r(x(k))\leq 0$
ならば,
アルゴリズムを停止する
.
このとき
,
x(
み
),
$A_{k}$ばそれぞれ問題
$(MP)$
の最適解および最適値である
.
$\mathrm{b}$.
その他の場合
,
$v^{k}$に対する制約なし凸最小化問題
(7)
の最適解を
$z^{k}$,
最適値を
$\omega^{k}$とする
.
こ
こで,
$\mu_{k+1}V_{k+1}$$==\{$
$V_{k}\cup\{Z^{k}\}$if
$\omega_{k}<0$,
$V_{k}$if
$\omega_{k}=0$,
$B\mu_{k}$if
$\theta_{v^{k}}(x(k))>0$
,
$\mu_{k}$if
$\theta_{v^{k}}(x(k))=0$
,
とする
.
さらに
$S_{k+1}=\mathrm{c}\mathrm{o}V_{k+1}$とし
,
$V((S_{k+1})\mathrm{O})$を求める
.
$karrow k+1$
として
, ステップ
1.
へ.
補題
3.2,
さらに
$F_{v,\mu k}$$(x)$
は連続微分可能性から,
式
(8)
を満たす
$x_{v}^{k}$が存在する
.
このような
$x_{v}^{k}$は最
急降下法や準
—
$=-$
トン法などにより求めることができる
.
補題 41
アルゴリズム
IA-P2
の任意の反復んにおいて
,
$A_{k} \leq\min(RcP)$
が成立する
.
証明
.
仮定
(A4)
より
, $\min(RcP)=$
而
n{f(x)
:
$x\in(\mathrm{b}\mathrm{d}X)\mathrm{n}Y$}
である
.
ただし,
$\mathrm{b}\mathrm{d}X$は
$X$
の境界
集合を表す
.
ここで
,
$\tilde{\Gamma}_{k}=\{v\in V((S_{k})0) : \langle v, x\rangle\geq 1,x\in X\cap Y\}$とする. 任意のたに対して,
$S_{k}\subset X$より
,
$( \mathrm{b}\mathrm{d}X)\cap Y\subset(X\cap Y)\backslash \mathrm{i}\mathrm{n}6S_{k}=\bigcup_{v\in\overline{\Gamma}_{k}}\{X\in X\cap Y:\langle v, x\rangle\geq 1\}$である.
したがって,
$\min(RcP)$
$= \min\{f(x) :
x\in(\mathrm{b}\mathrm{d}X)\cap Y\}$
$\geq\min\{f(x) :x\in(X\cap Y)\backslash \mathrm{i}\mathrm{n}\mathrm{t}S_{k}\}$
$= \min_{v\in\overline{\Gamma}_{k}}\min\{f(X) : \langle v,x\rangle\geq 1,x\in X\cap Y\}$
$= \min_{v\in\overline{\Gamma}_{k}}\min\{Fv,\mu k(X) : \langle v,x\rangle\geq 1, x\in X\cap Y\}$
$\geq \mathrm{I}\dot{\mathrm{m}}\mathrm{n}v\in\overline{\mathrm{r}}_{k}\min\{F_{v,\mu_{k}}(x) :x\in X\}$
$\geq$
$\min$
$\min\{F_{v,\mu_{k}}(Xv):x\in X\}$
$v\in V((s_{k})\circ)$$\geq$
$\min$
$\min\{F_{v,\mu k}(x^{v})+\langle\nabla F_{v,\mu k}(x^{v}),X-X\rangle v :
x\in X\}$
$v\in V((s_{k})\circ)$
$\geq$
$\min$
$\min\{F_{v,\mu_{k}}(x^{v})-||\nabla F_{v,\mu}k(x^{v})||\cdot||x-X|v| :
x\in X\}$
$v\in V((s_{k})\circ)$
$\geq\min_{v\in V((s_{k}\rangle^{\circ})}F_{v,\mu}(kxv)-||\nabla F_{v},\mu k(x)v||\cdot M(X^{v})$
$=A_{k}$
が成立するので
,
$A_{k} \leq\min(RCP)$
である.
$\square$定理
41
アルゴリズム
IA-P2 の任意の反復
$k$において
,
$A_{k}=F_{v^{k},\mu_{k}}(x(k)),$
$p(x(k))\geq 0,$ $r(x(k))\leq 0$
ならば
,
$x(k)$
は問題
$(RCP)$
の最適解である.
証明
.
$p(x(k))\geq 0,$ $r(x(k))\leq 0$
より,
$x(k)$
は問題
$(RCP)$
の実行可能解である
.
したがって
,
$f(x(k))\geq$
$\min(RcP)$
である.
さらに
, $f(x(k))=Fk(v,\mu kx(k))=Ak$
なので
, 補題
41
より
,
$f(x(k)) \leq\min(RcP)$
である.
したがって
,
f(x(み))
$=$而 n(RCP)
となるので,
$x(k)$
は問題
$(RCP)$
の最適解である
.
口
補題 41, 定理 4.1 より,
アルゴリズム
IA-P2
の停止基準が満足されるならば
, x(み),
$A_{k}$はそれぞれ問
題
$(MP)$
の最適解および最適値である.
4.2
アルゴリズムの収束性
本節では
,
アルゴリズム
IA-P2
によって生成される
$\{v^{k}\}$が無限点列である場合のアルゴリズムの収束
性について述べる.
補題
42
$\lim_{karrow\infty}||F_{v^{k},\mu_{k}}(x(k))||$.
M(X(
み
))
$=0$
が成立する
.
証明
.
まず
,
$\lim \mathrm{s}\mathrm{u}\mathrm{p}karrow\infty||x(k)11<+\infty$を示す
.
便宜上,
$\lim_{karrow\infty}||x(\text{み})||=+\infty$とする
. 仮定
(A2)
より
,
任意の
$\alpha\geq f(\mathrm{O})$に対して
$\{x\in R^{n} : f(x)\leq\alpha\}$
はコンパクト集合であり
,
すべての
$k$に対
して $f(x(k))>\alpha$
としても
–般性を失わない.
ここで
,
$\{x \in R^{n} : f(x)\leq\alpha\}$
のコンパクト性から
$\{x\in R^{n} : f(x)\leq\alpha\}\subset B(\mathrm{O}, \beta)$
を満たす
$\beta>0$
が存在する
.
さらに
,
$\nabla f(x)$は連続なので,
$\epsilon_{\min}=$$\min\{||\nabla f(X)|| :
f(x)=\alpha\},$
$\epsilon_{\max}=\max\{||\nabla f(X)|| :
f(x)=\alpha\}$
となる
$\epsilon_{\mathrm{r}\mathrm{n}\mathrm{i}\mathrm{n}},$ $\epsilon_{1\mathrm{n}\mathrm{a}\mathrm{x}}>0$が存在する.
このと
き
,
$\alpha>f(\mathrm{O})$より,
$0<\epsilon_{\min}\leq\epsilon_{\max}$である
.
ここで
,
任意の
$k$に対して
$y^{k} \in\arg\max\{\langle X(k),x\rangle :
f(x)\leq\alpha\}$
とおくと
, 凸計画問題の最適性条件から
,
$\nabla f(y^{\mathrm{k}})=\nu_{k}X(k)(\nu_{k}>0)$である
.
したがって
, 式
(8)
と
$A_{k}$および関数
$F_{v^{k},\mu_{k}}(X)$の定義から,
$A_{k}$
$=F_{v^{k},\mu k}(x(k))-||\nabla F_{v^{k},\mu k}(X(k))||\cdot M(x(k))$
$\geq F_{v^{k},\mu_{k}}(X(k))-’\Gamma_{k}\cdot M(X(k))$$\geq f(x(k))-\mathcal{T}_{k}\cdot M(X(k))$
$\geq f(y^{k})+\langle\nabla f(y)k,x(k)-y^{k}\rangle-\mathcal{T}k$
.
$M(_{X(k)})$
$\geq\alpha+\langle\nu_{k}x(k),x(k)\rangle-\langle\nu_{k}x(k),y^{k}\rangle-\tau_{k}(M+||x(k)||)$ $=\alpha+l\text{ノ_{}k}||x(k)||^{2}-\langle l^{\text{ノ}}kx(k),yk\rangle-\tau k(M+||X(k)||)$ $\geq\alpha+\epsilon_{\min}||x(^{\text{み}})||-\mathit{6}_{\max}||y|k|-\mathcal{T}_{k}(M+||X(k)||)$ $\geq\alpha+(_{\mathcal{E}_{\min}}-\tau k)||_{X}(k)||-\epsilon\max\beta-rkM$
である
.
よ
o
て
,
$\lim_{karrow}\inf_{\infty}A_{k}$ $\geq\lim_{karrow}\inf_{\infty}(\alpha+(\epsilon_{\min^{-\mathcal{T}_{k}}})||x(k)||-\epsilon\max\beta-\tau_{k}M)$ $\geq\alpha-\epsilon_{\max}\beta+\lim_{karrow}\inf(_{\mathcal{E}_{\min}}-\infty\tau_{k})||x(k)||-\lim_{karrow}\sup_{\infty}\tau kM$ $= \alpha-\epsilon_{\max}\beta+\lim_{karrow}\inf_{\infty}(\epsilon_{\min}-\mathcal{T}k)||X(k)||$$=+\infty$
が成り立つ
.
これは
,
補題 41 に矛盾する.
したがって
,
$\lim\sup_{karrow\infty}||x(k)||<\delta$
を満たす
$\delta>0$が存在
する.
このとき
,
$\lim\sup||F_{v^{k},\mu_{k}}(x(k))||\cdot M(x(k))\leq\lim\sup\tau_{k}(M+\delta)=0$
$karrow\infty$ $karrow\infty$が成立する
.
口
補題
43
アルゴリズム
IA-P2
により生成される点列
$\{x(k)\}$
および
$\{v^{k}\}$は無限点列であるとする.
この
とき
,
$\lim_{karrow\infty}\theta_{v}k(x(k))=0$である.
証明
.
関数
$\theta_{v^{k}}$の定義から
, 任意の
$x\in R^{n},$
$k\in\{1,2, \ldots\}$
に対して
$\theta_{v^{k}}(X)\geq 0$である
.
したが
って,
$\lim\inf_{karrow\infty}\theta_{v}k(X(k))\geq 0$が成立するので
,
$\lim \mathrm{s}\mathrm{u}\mathrm{p}k\prec\infty\theta v^{k}(x(k))\leq 0$を示せば良い
.
ここで
,
$\beta:=\lim\sup_{karrow\infty}\theta_{v}k(x(k))>0$
とする.
このとき
,
$1\mathrm{i}\mathrm{n}_{4arrow\infty^{\theta}q}v^{k}(x(k_{q}))=\beta$となる
$\{x(k)\}$
の部分列
$\{x(k_{q})\}$
が存在し
, 任意の
$q$に対して–般性を失うことなく
$\theta_{v^{k_{q}}}(x(k_{q}))>0$と仮定することができる
.
ま
た
, アルゴリズム
IA-P2
のステップ
$2\mathrm{b}$における
$\mu_{k}$
の定義から,
任意の
$q$に対して
,
$\mu_{k_{q+1}}\geq B\mu_{k_{q}}>\mu_{k_{q}}$る
$x’\in R^{n}$
が存在する.
補題 4.2 より,
$\lim_{qarrow}\inf_{\infty}A_{k_{q}}$ $= \lim \mathrm{i}n\mathrm{f}qarrow\infty(F_{v^{k_{q}},\mu_{k}q}(x(\text{み_{}q}))-||\nabla F_{v^{k}}q,\mu k_{q}(x(k_{q}))||\cdot M(X(k_{q})))$
$\geq\lim\inf F_{v,\mu}qarrow\infty kqk_{q}(x(k_{q}))+\lim_{qarrow}\inf_{\infty}(-||\nabla Fkvq,\mu_{k_{q}}(x(k_{q}))||\cdot M\langle_{X(}\text{み})q))$
$= \lim_{qarrow}\inf_{\infty}F_{v^{k_{q}}},\mu k_{q}(x(k_{q}))-\lim\sup(||\nabla F_{v}k_{q},\mu_{k}q(x(k_{q}))||\cdot M(X(k_{q})))$
$qarrow\infty$ $= \lim\inf F_{v^{k_{q}}},\mu_{k_{q}}(x(k_{q}))$ $qarrow\infty$ $= \lim_{qarrow}\inf_{\infty}(f(x(k_{q}))+\mu_{k_{q}}\theta_{v^{k_{q}}}(x\langle k_{q})))$ $\geq\lim\inf(f(x’)+\mu_{k_{q}}\theta_{v^{k_{q}}}(x(k_{q})))$ $qarrow\infty$ $=f(x’)+ \lim_{qarrow}\inf_{\infty}\mu k\theta_{v}k_{q}q(x(k_{q}))$
$=f(X’)+\infty\cdot\beta$
$=\infty$が成立する
.
これは
,
補題 41 に矛盾する.
したがって
,
$\lim\sup_{karrow\infty}\theta_{v}k(X\langle k))\leq 0$である
. 以上から,
$\lim_{karrow\infty}\theta_{v}k$(X(
み
))
$=0$
である.
口
補題
44 アルゴリズムハ-P2 により生成される同列
{x(
み
)}
は無限点列であるとする
.
このとき
,
$\{x(k)\}$
は集積点をもつ.
証明
.
補題
41, 42 および関数
$F_{v,\mu}(x)$の定義から,
$\min(RcP)$
$\geq\lim\sup A_{k}$
ん\rightarrow \infty
$= \lim_{-}\sup(F_{v^{k},\mu k}(x(k))-||\nabla F_{v^{k},\mu_{k}}(X(k))||\cdot M(X(\text{
み})))$
$\geq\lim_{\mathrm{L}\perp}\sup_{-}F_{v^{k},\mu k}(x(k))-\lim\inf_{\infty karrow}||\nabla F_{v^{k},\mu k}(X(k))||\cdot M(x(k))$
$= \lim\sup F_{v,\mu_{k}}k$
(x(
み
))
ん\rightarrow \infty
$= \lim\sup f(x(k))$
$karrow\infty$
が成立する.
これは
, ある
$\epsilon>0$に対して
,
$\{x(k)\}_{k\geq\overline{k}}\subset\{x\in R^{n} :
f(x)\leq\min(RcP)+\epsilon\}$
を満たすた
が存在することを意味している.
仮定
(A2)
から,
$\{x\in R^{n} :
f(x)\leq\min(RcP)+\epsilon\}$
はコンパクト集合な
ので
,
$\{x(k)\}$
は集積点をもつ.
$\square$定理 42
アルゴリズム
IA-P2
により生成される点列
$\{x(k)\}$
は無限点列であるとする
.
このとき
,
$\{x(k)\}$
の任意の集積点
$\overline{x}$は問題
$(RCP)$
の実行可能集合
$Y\backslash \mathrm{i}n\mathrm{t}X$に含まれる.
証明
.
$\{x(k)\}$
が集積点をもち,
$\{v^{k}\}$がコンパクト集合
$(S_{1})^{\mathrm{o}}$に含まれることから,
一般性を失わずに
$\{x(k)\},$
$\{v^{k}\}$がそれぞれ語,
$\overline{v}$に収束すると仮定することができる
.
定理
32
から
$\overline{v}\in x\circ$であるから
,
$X\subset\{x\in R^{n} : \langle\overline{v},x\rangle\leq 1\}$
が成り立つ
.
$[ \max\{0,r_{j}(x(\text{み_{}q}))\}]^{S}\geq 0$および補題
43
から
,
$0$
$= \lim\theta_{v^{k}}(X(k))$
$karrow\infty$
$= \lim_{karrow\infty}(\sum_{j=1}^{t_{Y}}[\max\{\mathrm{o}, rj(X(\text{み}))\}]s+[\max\{0, -\langle v^{k}, x(\text{み})\rangle+1\}]^{S}\mathrm{I}$
$> \lim[\max\{0, -\langle v^{k},x(k)\rangle+1\}]^{s}$
$-_{karrow\infty}$
が成立する
.
これは
,
$\langle\overline{v},\overline{x}\rangle\geq 1$を意味している
.
したがって,
$\overline{x}\not\in \mathrm{i}n\mathrm{t}X$である.
さらに,
補題 43 およ
び
$r_{j},$$j=1,$
$\ldots,t_{Y}$の連続性から,
$0$
$= \lim_{karrow\infty}\theta(_{X}v^{k}(k))$
$= \lim_{karrow\infty}(\sum_{j=1}^{t_{Y}}[\max\{\mathrm{o}, r_{j}(x(k))\}]s+[\max\{0, -\langle v^{k}, x(k)\rangle+1\}]^{s}\mathrm{I}$
$\geq\lim_{karrow\infty}\sum_{j=1}^{t_{Y}}[\max\{0,r_{j}(x(k))\}]^{s}$
$= \sum_{j=1}^{t_{Y}}[\max\{0,r_{j}(\overline{x})\}]s$
が成立する
.
したがって
,
$r_{j}(\overline{x})\leq 0,$$j=1,$
$\ldots,$$t_{Y}$
である
. 以上から,
$\overline{x}\in Y\backslash \mathrm{i}n\mathrm{t}X$
である.
口
定理
43
アルゴリズム
IA-P2
により生成される点列
$\{x(k)\}$
は無限点列であるとする
.
このとき
,
$\{x(k)\}$
の任意の集積点
$\overline{x}$は問題
$(RCP)$
の最適解である.
証明
.
定理 42 から,
$\overline{x}\in Y\backslash \mathrm{i}n\mathrm{t}X$であるから,
$f( \overline{x})\geq\min(RcP)$
である.
$\{x(k)\}$
が集積点をもち
,
$\{v^{k}\}\subset(S_{1})^{\mathrm{o}}$
であることから
,
{x(
み
)},
$\{v^{k}\}$がそれぞれ
$\overline{x}$,
$\overline{v}$に収束すると仮定する. 任意のたに対し
て
,
$\mu_{k}\theta_{v^{k}}(x(k))\geq 0$なので
, 補題
4.1,
4.2
より
,
$\min(RcP)$
$\geq\lim A_{\text{ん}}$$karrow\infty$
$= \lim(F_{v^{k},\mu k}(X(k))-||\nabla F_{v^{k},\mu k}(X(k))||\cdot M(x(k)))$
$karrow\infty$
$= \lim_{karrow\infty}F_{v,\mu}k(kx(k))-\lim_{arrow k\infty}||\nabla F_{v,\mu_{k}}k(x(k))||\cdot M(x(k))$
$= \lim F_{v^{k},\mu_{k}}(x(k))$
$karrow\infty$
$= \lim$
(
$f(x(k))+\mu k\theta v^{k}$
(x(
み
)))
$karrow\infty$
$\geq\lim$
f(x(
み
))
$karrow\infty$ $=f(\overline{x})$となる
.
したがって
,
$f( \overline{x})=\min(RCP)$
である
.
口
定理
44
アルゴリズムハ
-P2
により生成される点列
$\{v^{k}\}$は無限点列であるとする
.
このとき
,
$\{v^{k}\}$の
任意の集積点
$\overline{v}$は問題
$(DP)$
の最適解である.
証明
.
定理 32 より,
$\overline{v}$は問題
$(DP)$
の実行可能集合に含まれる.
したがって
,
$g^{H}( \overline{v})\leq\max(DP)$
で
ある.
ここで
,
$\lim_{qarrow\infty^{v^{k}}}q=\overline{v}$を満たす
$\{v^{k}\}$の部分列を
$\{v^{k_{q}}\},$ $\{v^{\text{ん_{}q}}\}$に対応する
$\{x(k)\}$
の部分列を
$\{x(k_{q})\}$とすると
,
一般性を失うことなく
,
$\{x(k_{q})\}$は
$\overline{x}$に収束すると仮定できる
.
補題
43
より
,
$\lim_{qarrow\infty}\theta_{v^{k_{q}}}(x(k_{q}))=\lim_{qarrow\infty}(\sum_{j=1}^{t_{Y}}[\max\{0, rj(X(k_{q}))\}]^{S}+[\max\{0, h(x(k_{q}),vkq)\}]^{s)}=0$であるから
,
$0\geq 1\mathrm{i}\mathrm{n}_{4arrow\infty}h(x(k)q’ v^{k}q)=1\mathrm{i}\mathrm{n}_{4arrow\infty}(-\langle v, X(k_{q}k_{q})\rangle+1)=-\langle\overline{v},\overline{x}\rangle+1$,
つまり
,
$\langle\overline{v},\overline{x}\rangle\geq 1$である
.
また
, 定理 42, 43
から
,
$\overline{x}\in Y\backslash \mathrm{i}\mathrm{n}\mathrm{t}X\subset Y$であり
,
$f( \overline{x})=\min(RC\prime P)$なので,
$g^{H}(\overline{v})$ $=- \inf\{g(x):\langle\overline{v},x\rangle\geq 1\}$
$=- \inf\{f(x) : \langle\overline{v},x\rangle\geq 1,x\in Y\}$
$\geq-f(\overline{x})$
$=- \min(RcP)$
$= \max(DP)$
5
内部近似法の改良
(2)
第 4 章で提案したアルゴリズムは,
各反復においてすべての
$v\in V((S_{k})\circ)$
に対して
(8)
を満足する問
題
$(SP1(v, \mu_{k}))$
の暫定解
$x_{v}^{k}$を求めることで大域的収束性が保証される
. 本章では,
各反復において
,
ある
つの
$v\in V((S_{k})0)$
に対して直線探索を用いて暫定解
$x_{v}^{k}$を更新する新たな手法を提案する
.
新たに提案
されるアルゴリズムは
,
冗長な
$v\in V((Sk)0)$
に対して暫定解を更新することなく,
問題
$(RCP)$
の最適解
を求めることができる.
5.1
アルゴリズム
直線探索を用いて問題
$(SP1(v, \mu_{k}))$
の暫定解
$x_{v}^{k}$を更新するアルゴリズムは次のとおりである.
アルゴリズム
IA-P3
ステップ
$0$.
$\mu_{1}>0,$
$B>1,$
$S>1,$
$\tau_{1}>0,$$\nu<1(\nu>0)$
とする
.
$V_{1}\subset X$かつ
$\mathrm{O}\in \mathrm{i}n\mathrm{t}(\mathrm{c}\mathrm{o}V_{1})$を満たす有
限集合研を生成する
.
$S_{1}=\mathrm{c}\mathrm{o}$ $V_{1}$とし
,
$V((S_{1})0)$
を求める
. 任意の
$v\in V((S_{k})^{\mathrm{o}}$に対して,
$x_{v}^{1}=0$とし
,
$\overline{x}(0)=0$とする.
$karrow 1$
として
,
ステップ
1
ヘ
.
ステップ
1. 次を満たす砂
$\in V((s_{k})0)$
を選ぶ.
$F_{v^{k},\mu k}(X_{v}k)k-||\nabla F_{v^{k},\mu k}(X_{v^{k}}k)||\cdot M(x^{k})v^{k}$ $=$
$\min$
$F_{v,\mu_{k}}(X^{kkk}v)-||\nabla F_{v},\mu k(_{X_{v}})||\cdot M(x)v$.
$(9)$
$v\in V((s_{k})\circ)$また
,
$x(k)=X_{v^{k}}^{k},$ $A_{k}=Fkv,\mu k(X_{v^{k}}^{k})-||\nabla F_{v,\mu_{k}}k(x_{v}^{k}k)||\cdot M(x^{k}k)v$とし
,
ステップ
2
$\text{へ}$.
ステップ
2.
$A_{k}=F_{v^{k},\mu k}(x(k)),$
$p(x(\text{み}))\geq 0,$$r(x(k))\leq 0$
ならば,
アルゴリズムを停止する
.
このとき
,
$x(k)$
は問題
$(RCP)$
の最適解である
. その他の場合,
ステップ
3
ヘ.
ステップ
3.
$||\nabla F_{v,\mu_{k}}k(x(k))||<$布ならば
,
$v^{k}$に対する問題
(7)
の最適値を
$\omega_{k}$,
最適解を
$z^{k}$
とする.
こ
こで
,
$V_{k+1}=\{$
$V_{k}\cup\{z^{k}\}$,
$\omega_{k}<0$の場合
,
$V_{k}$,
$\omega_{k}=0$の場合,
$\mu_{k+1}=\{$
$B\mu_{k}$,
$\theta_{v^{k}}$(x(み))
$>0$
の場合
,
$\mu_{k}$,
$\theta_{v^{k}}(x(k))=0$
の場合
,
とする.
また,
$S_{k+1}=\mathrm{c}\mathrm{o}V_{k+1}$とし
,
$V((S_{k+1})0)$
を求める
. 任意の
$v\in V((S_{k})0)$
に対して
,
$x_{v}^{k+1}=\{$
$x(k)$
, if
$v\in V((s_{k+1})\circ)\backslash V((Sk)\circ)$,
$x_{v}^{k}$
,
otherwise.
とする
.
$\tau_{k+1}=\nu\tau_{k},\overline{x}(k)=x(k)$とし
,
$karrow k+1$
として
,
ステップ
1
へ
.
その他の場合
,
ステップ
4
$\text{へ}$
.
ステップ
4.
次を満たす
$x_{v^{k}}^{k+1}$を求める
.
$F_{v^{k},\mu_{k}}(x_{v^{k}})k+1= \min_{\lambda>0}F_{v}k,\mu k(x(k)-\lambda\nabla Fkv,\mu k(x(k)))$
.
任意の
$v\in V((s_{k})\mathrm{O})\backslash \{v^{k}\}$に対して
,
$x_{v}^{k+1}=x_{v}k$とする
.
$\mu k+1=\mu_{k},$
$\tau_{k+1}=\tau_{k},\overline{x}(\text{み})=\overline{X}(k-1)$と
補題
41
の証明と同様にして
,
アルゴリズム
IA-P3 の任意の反復
$k$において,
$A_{k} \leq\min(RcP)$
が
成立することが示される
. また,
定理 4.1
と同様にして
,
アルゴリズム
IA-P3 の任意の反復
$k$において
,
$A_{k}=F_{v^{k},\mu k}(x(k)),$
$p(x(k))\geq 0,$ $r(x(k))\leq 0$
ならば,
$x(k)$
は問題
$(RCP)$
の最適解であることがわかる.
5.2
アルゴリズムの収束性
本節では,
アルゴリズム
IA-P3
によって生成される
$\{v^{k}\}$が無限点列である場合のアルゴリズムの収束
性について述べる
.
補題 51 任意
$k$に対して, 次を満たす
$\hat{k}\geq k$が存在する
.
$||\nabla F_{v^{\dot{k}},\mu_{\dot{k}}}(X(\hat{k}))||<\tau_{\hat{k}}$
.
証明
.
ここで,
任意の
$k’\geq k$
に対して
$||\nabla F_{v^{\overline{k}},\mu_{\hat{k}}}(x(\hat{\text{み}}))||\geq\tau_{\hat{k}}$を仮定して矛盾を導く.
仮定および
\tau
ん
,
$\mu_{k}$の定義から
$\tau_{k^{t}}=\tau_{k},$$\mu_{k’}=\mu_{k}(k’\geq k)$
となる.
また,
$S_{k}$の定義から
$S_{k’}=S_{k}(k’\geq k)$
となる
.
このと
き
,
$V((S_{k})\circ)$の要素が有限個であることから,
次を満たす
$\hat{v}\in V((S_{k})\circ)$および部分列
$\{v^{k_{q}’}\}\subset\{v^{\text{ん^{}\prime}}\}_{k}’\geq k$が存在する.
$\hat{v}=v^{k_{\iota}^{l}}=v^{k_{2}’}=.$. .
$=v^{k_{q}}’=\cdots$.
また,
アルゴリズム
IA-P3
のステップ
4 から, 任意の
$q$に対して, 次が成立する.
$F(x(k_{q}’))v^{k_{q}’},\mu k;q$ $=F_{\hat{v},\mu_{k_{q}’}}$$(x(k_{q}’))$ $> \min_{\lambda>0\mu_{k}}F_{\hat{v}},q’(x(k_{q}’)-\lambda\nabla F_{\overline{v},\mu_{k_{q}}}, (x(k_{q}’)))$ $\geq F_{\hat{v},\mu_{k_{q}’}}(X(k’)q+1)$ $=F_{k,v^{q+},\mu_{k^{l}}}’(1X(k_{q+}’)1)q+1^{\cdot}$さらに, 補題 32 より旧\leftarrow \acute
対して
$F_{\hat{v},\mu k}$は最小値をもつ. したがって,
$F_{\hat{v},\mu k}$は連続微分可能な凸関数なの
で,
最急降下法の収束性から
,
次が成立する.
$\lim_{qarrow\infty}F_{k_{q} ,v\mu}’,(k_{q}’X(k_{q}’))=\lim_{arrow}F_{\hat{v}},(\mu k\prime X(k’q\infty qq))=\min_{\in xRn}F_{\hat{v},\mu k^{r}}(qX)$
.
よって
,
li%\rightarrow \infty
$||\nabla F\prime v^{k_{q}},\mu k\prime q(x(k_{q}^{;}))||=0$が成り立つ
.
これは仮定に矛盾する
. したがって, 任意
$k$
に対し
て,
$||\nabla F_{v^{\overline{k}},\mu k}(X(\hat{k}))||<\tau_{\hat{k}}$を満たす
$\hat{k}\geq k$が存在する
$\square$ $=$
定理
51 アルゴリズムハ-P3 より生成される点列
$\{\overline{x}(k)\}$の任意の集積点は問題
$(RCP)$
の制約集合に
含まれる. さらに,
$\{\overline{x}(k)\}$の任意の集積点は問題
$(RCP)$
の最適解である.
証明
.
部分列
$\{\overline{x}(k_{q})\}\subset\{\overline{x}(k)\}$は次を満たすものとする.
$\overline{x}(k_{0}^{\wedge})=\overline{x}(\mathrm{o})=0$,
$\overline{x}(k_{q})\neq\overline{X}(k-q1),$$\forall q\geq 1$
,
(10)
$\forall k,$ $\exists q$
such that
$\overline{x}(k)=\overline{x}(k_{q})$.
このとき
,
$\overline{x}(k)\}$の定義から
,
任意の
$q$に対して
$\overline{x}(\text{み_{}q})=x(k)q$となる. アルゴリズム
IA-P3
のステップ
3
から, 任意の
$q$に対して
$||\nabla F_{v^{k},\mu k_{q}}q(\overline{x}(k_{q}))||<\tau_{k_{q}}$が成り立つ
. また, 任意の
$q$に対して,
となるので, 補題 42 の証明と同様にして
垣 m
$||\nabla F_{V^{k}\mu}q,k_{q}(\overline{x}(k_{q}))||\cdot M(\overline{X}(k)q)=0$$qarrow\infty$
が示される.
さらに
, 補題 43,
44
の証明と同様に
$\lim_{qarrow}\infty\theta_{v^{k_{q}}}(\overline{x}(k_{q}))=0$および
$\{\overline{x}(k_{q})\}$が集積点をも
つことが示される.
したがって, 定理
42
の証明と同様にして
,
$\{\overline{x}(k_{q})\}$の任意の集積点は問題
$(RCP)$
の
制約集合に含まれることがわかる.
よって
,
(10)
より
,
$\{\overline{x}(k)\}$の任意の集積点は問題
$(RCP)$
の制約集合
に含まれることが示された.
また
, 定理 43 の証明と同様にして,
$\{\overline{x}(k)\}$の任意の集積点は問題
$(RCP)$
の最適解であることが示さ
れる
.
$\square$定理
51
より
,
$\lim_{karrow\infty}f(\overline{x}(k))=\min(RcP)$が成立する
. また,
定理 51 から,
$\lim\inf_{karrow\infty P}(\overline{X}(k))\geq 0$かつ
him
$\sup_{karrow\infty}r(\overline{x}(k))\leq 0$となる
.
したがっ
て
,
$\{\overline{x}(k)\}\subset\{x(k)\}$なので,
アルゴリズム
IA-P3 を有限回の反復で停止させるために, 許容誤差
$\gamma_{1},$ $\gamma_{2}$,
$\gamma_{3}>0$
