数理解析研究所講究録
1068 巻 1998 年 13-25

13

二重総量制約下における凸計画問題について

1

隆祐 (Ryusuke Hohzaki)

防衛大応物教室

宝崎

防衛大応物教室

飯田. 耕司 (Koji Iida)

はじめに
この報告は、 手持ちの資源総量に二重の制約がある場合の最適化問題を取り扱っており、 ある種の資源配分問題の解法について議論したものである。 資源配分問題は、 1950 年半に$\mathrm{B}.\mathrm{O}$. Koopman[5] が捜索努力量の最適配分に関する捜索問題を提起したことに由来する。 その研究を–般化し、変分法的手法により最適関数の満たすべき条件を明らかにしたのが J. de

Guenin [1] である。資源配分問題の分野で主として取り扱われる問題は、資源総量の制約の下での変数に関し分離可能な目的関数の最適化問題であるが$[3]_{\text{、}}$

非線形計画問題 [4] や大域的最適化問題 [2] の研究分野では、 目的関

数や制約関数をより -般的に取り扱うことが多く、 資源配分問題に比べるとかなり –般論的な理論や手法の議論が主となっている。

ここで扱う問題は、 問題の–般性から言えば 資源配分問題と非線形計画問題の問に位置するような問題である。 すなわち、 資源には二次元空間

上での 2 種類の重み付き総量制約が課せられており、 目的関数は必ずしも分離可能とはいえない凹関数である) 本報告では、 目的関数に対し特殊な形を仮定せずに最適解を導出する 2 つの数値解法アルゴリズムを提案し、非線形計画法における良く知られた解法に比べ\ 計算時間の面からも高速であることを検証する。

14

2

モデルの記述と定式化
資源投入による利得獲得の問題においてよく出会う次のような問題を考えよう。

(仮定 1) 二次元ベクトルで表される離散地点に資源を投入できる。 ここでは、 空間的位置と時間的位置から成る空間を考え、 どちらも離散的であるとし、 それぞれを $K=\{1, \cdots, K\},$ $T=\{1, \cdots, T\}$ で表す\supset(仮定 2). 資源投入空間 K表す。

$\varphi(i, t)$$\cross$

T の任意の点に投入する資源量を\mbox{\boldmath $\varphi$}(i)は非負であり、 その上限として許し与えられている) また、

スト$(i_{\ovalbox{\tt\small REJECT}}, t)$$c_{it}\varphi(i, t)$(ただし、$\varphi(i, t)$$c_{\mathrm{t},t}.>0$$77l_{\mathrm{i}\dagger},$

$t)$

で

$>0$ が+\infty をもの投入にはそれに比例するコである。) を要し、 各時点 t\in T での投入コストの上限として\Phi (t)、 全時点におけるコスト総量の上限として M の二重の制約がある。,(仮定 3) 資源配分計画\mbox{\boldmath $\varphi$}られる。)$f(\varphi)$$=\{\varphi(i, \theta), \uparrow \text{ノ}\in Kt\in T\}$は、$\varphi$に対し、 利得$f(\varphi)$が得に対し 2 回連続微分可能で、 かっ狭義凹関数

である。) また、 非負の有限値を要素とする変数ベクトル\mbox{\boldmath $\varphi$} に対して、$f(\varphi)$は有界である (’以上の仮定の下で、利得関数$f(\varphi)$を最大化する資源配分計画\mbox{\boldmath $\varphi$} を求めることがここでの問題である。 資源配分に関する (仮定 2) での複合した制約は多くの実例で見受けられ、 場合によっては$77\iota_{it}.=\infty$

や\Phi (t)$=\infty$とすることにより、 より緩やかな制約へ緩和することもできる。) (仮定 2) の制約を考えることにより、 ここでの問題は狭義凹関数を最大化する (凸関数を最小化する) 次のような凸計画問題となる。
$P_{M}$:$\max_{\varphi}f(\varphi)$

(1)

15

$\mathrm{s}.\mathrm{t}$.

$0\leq\varphi(i, t)\leq r\gamma \mathrm{t}_{it})$$\sum_{i=1}^{K}a_{t}\varphi$.

$i_{\text{ノ}}\in K.$$(i, t)\leq\Phi(t),$$. \sum_{\dagger=1i_{!=}}^{T}\sum^{K}C_{\mathrm{i}t}1’\varphi(i, t)\leq M$$t\in T$

(3)

.

(4)

この問題において、 もし\Sigma iK\acute$=1$

も構わないし、(2)$t\in T$’$\Sigma_{t=1}^{T}\Phi(t)$$c_{i_{\text{ノ}}t}nlit\leq\Phi(\#)$

であれば、 制約\Phi (t) を省いて\leq M であれば、 総量制約 M は問題にとって不必要となるから、 一般性を失うことなく、 パラメータ問において次式が成り立っていると仮定する。
$. \sum_{\uparrow J=1}^{K}C_{\uparrow}..f.n\iota_{\uparrow}\cdot.t>\Phi(t),$$\sum_{t,=1}^{T}\Phi(t)>M$$t\in T$

.

(5)
(6)

また、 ゼロベクトルに対し $f(0)\neq 0$ ならば、 問題 (P のを新しい利得関数$g(\varphi):=f(\varphi)-f(\mathrm{O})$の最大化問題と考えてもよく、 このとき $g(\mathrm{O})=0$ となるから、 一般に、 資源配分のない場合の利得は $f(0)=0$ であると仮定する (-)

3

最適資源配分の必要十分条件
問題 $(P_{M})$ は有限な閉凸領域における狭義凹関数の最大化問題であるから, 唯–の最適解をもつという分かり易い性質をもつ。 ここでは、 最適解の必要十分条件を導出するとともに、 最適なラグランジ $f$ 乗数に関する考察により、 解法アルゴリズムを構築するための準備を行う。

3.1

最適解の必要十分条件

前述したように、 問題の最適解は唯–存在し、 その条件に関する次のような定理が容易に導出できる。 ただし、 条件 (2) $\sim(4)$ を満たす実行可能な

16

資源配分全体を、$\Psi$で表している。

定理 1(最適解の必要十分条件)$\varphi\in\Psi$が最適であるための必要十分条

件は次で与えられる。 すなわち、 すべての $(i, t)\in K\mathrm{x}T$ に対し、$\varphi(i, t)=0$

ならば、

ならば

$0<\varphi(i, t)<m_{\mathrm{i}t}$ならば、$\varphi(i, t)=m_{it}$を満たす非負の乗数\mbox{\boldmath $\lambda$},$l\ovalbox{\tt\small REJECT}_{t}>0$

ならば、

(7)

$\frac{1}{c_{\mathrm{i}t}}\frac{\partial f(\varphi)}{\partial\varphi(i,t)}\leq\lambda+l\ovalbox{\tt\small REJECT}_{t}$(8)$\frac{}1}{c_{i_{J}f_{\text{ノ}}}\frac{\partial f(\varphi)}{\partial\varphi(/\text{ノ},t)}.=\lambda+\iota\ovalbox{\tt\small REJECT}_{t}$(9)$\frac{1}{c_{it}}\frac{\partial^{\Gamma}f(\varphi)}{\partial\varphi(\uparrow-,t)}.\geq\lambda+l\ovalbox{\tt\small REJECT}_{t}$$l\ovalbox{\tt\small REJECT}_{t},$$t=1,$, T が存在し、 かつ、 $t\in T$ に対し、$\cdots$(10),$\sum_{\mathrm{i}=1}^{\mathrm{A}^{\nearrow}}C_{\mathrm{i}\dagger\varphi}.(i_{/}, t)=\Phi(t)$及び$\lambda>0$

ならば、

(11)

$\sum_{t=1i\prime=}^{T}\sum_{1}^{K}Ci_{\text{ノ}}t\varphi(i, t)=M$が成り立つ。

Proof:

上の条件は、 問題の最適解の必要十分条件である Kuhn-Tucker

条件から導くことができる。逆に、上の条件から Kuhn-Tucker 条件を導出することもできる。

$f/\partial\varphi(i, t)/C_{\uparrow,t}$表すことにしよう。
$f(\cdot)$$\varphi_{-it}$

は、を変数\mbox{\boldmath $\varphi$}(i, ) に注目して、$t$$\varphi(?_{\text{ノ}}, t)$の狭義凹性から、り、 もし防 t(x;関数 Pi-.f\acute l(y;.D.
.

ここで、 関数

目的関数$\mathrm{Q}.\mathrm{E}$$\rho_{\mathrm{i}t}(\varphi(?\text{ノ}, t);\varphi_{-}i.t)$と以外の変数のベクトルを表している。

$\rho_{it}.(x;\varphi$-のは に関して単調減少関数であ$x$)=y が根 をもっとすれば唯 1 つであることから、 逆) を定義できる。 . $()$ の定義域は\rho i.t C) の値域により決ま$\varphi_{-\uparrow t}\text{ノ}.$$x$$p_{\mathrm{t}\prime t}^{-1}$$\varphi_{-\mathrm{t}f}.,,$

るが、 定義域を適当に解析接続して拡張することが可能であり、 任意の$y\in(-\infty, \infty)$

において連続関数\rho i-f. 1(y;$\varphi_{-it},,$) が存在するように再定義できる。 これを使えば、 (7) $\sim(9)$ 式は–括して次式で表すことができる\subset )17$\varphi(i, t)=[\rho_{it}^{-1}(\lambda+\nu t).\varphi_{-}it)]_{0}^{m}it$

.

(12)

ただし、 [x]\models 記号は以下の意味で使っている。
’$b$$[x]_{a}^{b}=$,$b\leq x$

$x$

,

$a$

,

$\mathrm{Y}$if
if $a<x<b$if$x\leq a$

また、 最適解に関する (12) 式の表現を使えば、 制約条件 (3)(4) 式はそれぞれ次のように書ける。

(13)$\uparrow_{\text{ノ}}.1\sum_{=}^{K}C_{i}.t[\rho_{i}^{-1}\prime t(\lambda+\nu_{t};\varphi-\mathrm{i}t)]_{0}^{m}it\leq\Phi(t)$$f= \sum_{\text{ノ}^{}T}\sum_{i1.=1}C_{i}t[\rho_{it}^{-1}(\lambda+l\text{ノ_{}t;\varphi}-it)]_{0}^{m}Kit\leq M$

3.2

(14)

.

制約量とラグランジュ乗数との関係

ここでは、 ラグランジ$=_{-}$

乗数と問題の局所総量制約 $\{\Phi(t), t\in T\}$ 及び全体の総量制約 $M$ との関係を議論しよう。 制約の組
$P_{M_{1}}$数を$\{M_{1}, \Phi_{1}(t)\}$をもつ問題と $\{M_{2}, \Phi_{2}(t)\}$ をもつ問題 P いのそれぞれに対する最適ラグランジュ乗$\{\lambda_{1)}\iota\ovalbox{\tt\small REJECT}_{1f}.\},$$\{\lambda_{2,2t}\iota\ovalbox{\tt\small REJECT}.\}\text{、}$最適解を\mbox{\boldmath $\varphi$}1,$\varphi_{2}$とする。 ただし、 局所制約量は双方の問題ともに同じであるとする。 このとき、$\varphi_{1}\neq\varphi_{2}$であれば、$7Yl_{\mathrm{i}t}$$f(\cdot)$の狭義凹性や (7) $\sim(11)$ 式により次式を得る。
$f( \varphi_{2})<f(\varphi_{1})+\lambda_{1}(M_{2}\sim-M_{1})+\sum_{t}\iota \text{ノ}1t(\Phi_{2}(t)-\Phi_{1}(t))$

これを利用すれば、 ラグランジ$2_{-}$.

(15)

乗数\mbox{\boldmath $\lambda$} と総量制約 $M$ との間に次のような単調な関係が存在することが言える。
定理 2 最適解が\mbox{\boldmath $\varphi$}* $=0$ である必要十分条件は、 任意の $(i, t)$ に対して偏導関数が f/\partial \mbox{\boldmath $\varphi$}(i, )$t$$|_{\varphi=0}\leq 0$に対応する最適解\mbox{\boldmath $\varphi$}* の総量の総量として得られる。

となることである。 そうでない場合、 $\lambda=0$$M_{7nax}=\Sigma_{\mathrm{i},t}.c_{\uparrow.t}\varphi^{*}(i, t)$

は、 次の問題の最適解

18$RPT$ ;

$s.t$

(16)

$\max_{\varphi}f(\varphi)$.

$0\leq\varphi(i, t)\leq rrl_{it}$,$i\in K$ ,$\sum_{\mathrm{i}=1}^{K}C_{it}\varphi(i_{\text{ノ}}, t)\leq\Phi(t))t\in T$

このとき、 Mrnax$\leq M^{/}$(17)$t\in T$.

(18)

なる任意の総量制約$M^{/}$をもつ問題 $(P_{M’})$ の最適解

も最適ラグランジ $f$ 乗数も\mbox{\boldmath $\varphi$}*及び\mbox{\boldmath $\lambda$} $=0$ のまま変わらない) すなわち、 ラグランジ IL 乗数\mbox{\boldmath $\lambda$} $=0$ に対応する総量制約の中で最小のものが Mrnax であり、 これを限界総量と呼ぶ。

いま、$\lambda\max$$:=\mathrm{s}\mathrm{u}\mathrm{p}_{i},t\{\xi|\rho_{i,t^{1}}^{-}(\xi;0)=0\}$で定義すると、 問題 $(P_{M})$ の総量

制約 $M$ とその最適なラグランジ=-乗数\mbox{\boldmath $\lambda$} に関して、 以下の対応関係がある。
$\lambda=0$に対応する総量制約は M7nax\leq M の任意の M であり、 総量 $M=0$に対応するラグランジ\supset -乗数は\mbox{\boldmath $\lambda$}7nax$\lambda\max$の\mbox{\boldmath $\lambda$} と、 $M. \max>M>$.

$\lambda\max$の\mbox{\boldmath $\lambda$}1,

Proof:$\lambda_{2}$$0$$\leq\lambda$の任意の\mbox{\boldmath $\lambda$}である。 また、 $0<\lambda<$の $M$ とは 1 対 1 に対応し、 $0<\lambda_{1}<\lambda_{2}<$は、 $M_{7nax},$ $>M_{1}>M2>0$ なる$M_{1},$$M_{2}$に対応する。)

省略。

局所総量制約\Phi (t) とラグランジ 2- 乗数偽との対応関係に関しても同じよ
うな定理を得ることができる

$()$

4

厳密解法

4.1

最適なラグランジュ乗数の導出法

ここでは、 最適解$\varphi^{*}=\{\varphi^{*}(?_{\ovalbox{\tt\small REJECT}}, t), i\in Kt\in T\}$

理 1 における最適なラグランジ$\epsilon l$

乗数\mbox{\boldmath $\lambda$}*,て議論する。 まず、 次式により、 $y\geq 0$ と所総量を表す関数$S_{t}(y, \varphi)$を定義しよう。

$l\ovalbox{\tt\small REJECT}_{t}^{*}$が得られたとして、 定を–意的に求める方法につい$\varphi\in\Psi$に対し、 $t\in T$ における局

19

ん

(19)

$S_{t}(y, \varphi):=\sum_{i=1}C_{it}[\rho^{-1}\mathrm{t}.t(y;\varphi_{-}?.t)]_{0}^{m_{it}}$

これは

$y$

についての単調非増加な運続関数であり、対しては、$S_{t}(\xi(t, \varphi),$となる\xi$\varphi)=\Phi(t)$$(\mathit{1}, \varphi)$

it に$0<\Phi(t)<\Sigma_{i}..C_{i\prime t}.m$.

が区間 $(-\infty, \infty)$ において唯存在する。 ここで、 最適解\mbox{\boldmath $\varphi$}* に対して求めた $\{\xi(t, \varphi^{*}), t\in T\}$ を小さい順に並べて、ある L こ対し\xi (tI,ら、 最適解を得たとする。 いま、$\xi(t_{1_{)}\varphi^{*}})\leq\xi(t_{2,\varphi^{*}})\leq\cdots\leq\xi(t_{T}, \varphi^{*})$$\varphi^{*}$)$\leq\lambda^{*}<\xi(t_{I+1}, \varphi^{*})$$\{\varphi^{*}(i_{\text{ノ}})tk))k=1, \cdot\cdot\cdot.

, T\}$$[\rho_{\mathrm{i}t_{k}}^{-1}(\lambda^{*}; \varphi_{-}it_{\text{ノ}k})]^{m_{it}}*0k$$\varphi^{*}(i, t_{k}.)=\{$だとすると、 相補条件 (10) 式等かは次式で表される。

,$k=1,$$\cdots,$$[\rho_{\mathrm{i}t_{k}}^{-1}(\xi(t_{k}., \varphi)*]_{0}^{7};\varphi_{-it}^{*}k)n_{it_{k}}.)k=I+1,$

ここで、 $\mu_{\lambda}(\varphi):=\max\{k|\xi(t_{k,\varphi})\leq\lambda\}$ とおくと、$I$$\cdots,$$T$$I=\mu_{\lambda^{*}}(\varphi^{*})$

ラグランジ z- 乗数\mbox{\boldmath $\lambda$} に対応する解\mbox{\boldmath $\varphi$} の重み付き総和を示す関数

であり、$Q(\lambda, \varphi)$の表

現が次のように得られる。
$Q( \lambda, \varphi):=\sum_{k=1}^{\varphi}\sum_{i=1}C\mu_{\lambda}()Kit_{k}[\oint J_{it_{k}}^{-}.(1\lambda;\varphi_{-}i\prime t_{k})]_{0}^{7n}.\dot{l}tk+k.=\mu\lambda(\sum_{)\varphi+1}^{T}\Phi(t_{k})$最適な\mbox{\boldmath $\lambda$}* は、 に関する連続な非増加関数である$\lambda$$Q(\lambda, \varphi)$.

を使って求めることができる。まとめると、最適解\mbox{\boldmath $\varphi$}* が与えられた場合の最適なラグランジ

乗数\mbox{\boldmath $\lambda$}*,$\nu_{t}^{*}$と最適解表現が次のような手順で求められる。

$Q(\mathrm{O}, \varphi^{*})\leq M$$Q(\mathrm{O}, \varphi^{*})$

適な$\{\nu_{t}^{*}\}$の場合、定理 2 の限界総量に関する性質から>M の場合は、 $k=1,$に対してはべ$Q(\lambda^{*}, \varphi^{*})=M$$\cdots,$$l^{l\wedge*}(\varphi^{*})$$=\xi(tk, \varphi^{*})-\lambda^{*}$$\lambda^{*}=0$

であり、を満足する唯–の\mbox{\boldmath $\lambda$}* が最適である。 最に対しては$\nu_{t_{k}}^{*}=0_{\text{、}}k=\mu\lambda^{*}(\varphi^{*})+1,$$\cdots,$により与えられる。 このとき、最適解$\varphi^{*}$$T$

は次のように表現できる (\urcorner$[p_{\rho_{l}}^{-}.t_{k}(1\lambda**);\varphi_{-}i_{\text{ノ}}t_{k}]_{0}m_{i}.t_{k}$,$k=1,$$\cdot.\cdot$.

$*$$l^{l}\lambda^{*(}\varphi$$,$)$\varphi^{*}(i, t_{k}.)=\{$$[\rho_{\uparrow_{\text{ノ}}t_{k}}^{-1}.(\xi(tk, \varphi)*\varphi_{-i_{\text{ノ}}};t_{k})*]_{0}m_{\dot{x}}f.k,$$k=\mu_{\lambda^{*}}..(\varphi^{*}-)+1,$$\cdot$:. , T

(20)

20

4.2

数値解法アルゴリズム

ここでは、最適解の必要十分条件及び総量制約とラグランジ=-乗数との単調な関係等を利用して、最適解を求める数値解法アルゴリズムを提案する。
(1) 勾配完結法
この解法は、 最終的に目的関数の勾配に関する条件式 (7) $\sim(9)$ を満足させることにより、 最適解を求めようとする方法である)
アルゴリズム$(\mathrm{G}\mathrm{C}1)$

すべての
$0$

$(i_{\text{ノ}}, t)$$\mathrm{G}\mathrm{C}$に対して f/\partial \mbox{\boldmath $\varphi$}(Z, )$t$$|_{\varphi=0}\leq 0$

ならば、最適解を\mbox{\boldmath $\varphi$}*$=$として終了する c)$j=0$ とし、 初期解〆を設定する$(\mathrm{G}\mathrm{C}2)T_{0}=\{t\in T|S_{t}(0, \varphi^{j})\leq\Phi(t)\}$$|T_{0}|$であるとし、

ついては、$t\in\tau_{0}$

を適当に

$()$

例えば、 $\varphi^{0}=\{0, \cdots, 0\}$。

及び $\tau^{c}=\tau-\tau_{0}$ を求める。 $L=$$t_{1)}\cdots$$S_{t}(\xi(t, \varphi)j,$ $\varphi^{j})=\Phi(t)$,$t_{L}$と順序づける。 $t\in T^{c}$ にとなる $\{\xi(t, \varphi^{j})|t\in T^{c}\}$ を求め、 小さい順に$0<\xi(t_{L+}1, \varphi^{j})\leq\xi(t_{L+2}, \varphi^{j})\leq\cdots\leq\xi(t_{T}\varphi^{j}))$と番号付けする。 ここで、

$Q(\mathrm{O}, \varphi^{j})\leq M$

ならば\mbox{\boldmath $\lambda$} $=0$ とし、 そうでなければ $Q(\lambda, \varphi^{j})=M$ を満たす唯– の\mbox{\boldmath $\lambda$}>0 を求める (\supset

及び\xi (tk,$\varphi^{j}$

この\mbox{\boldmath $\lambda$}), $k=L+1,$ $\cdots T)$ を用いて、 次式により新しい実行

可能解\mbox{\boldmath $\varphi$}^j を作成する。
$[\rho_{i}^{-1}t_{k}(\lambda;\varphi_{-}itk)j.]_{0}\mathit{7}n_{it_{k}}$,$k=1,$$\cdots,$$l^{l}\lambda(\varphi)j$$\hat{\varphi}^{j}(i_{\text{ノ}}, t_{k})=\{$$[\rho_{it_{k}}^{-1}.(\xi(tk, \varphi^{j});\varphi_{-i}.tk)j]_{0}^{7n_{it}}.k,$$(\mathrm{G}\mathrm{C}3)$

もし\mbox{\boldmath $\varphi$}^j$=\varphi^{j\prime}$

ならば、 終了 3’$\varphi^{j}$は最適解である。 そうでなければ、次の直線探索を行い、 新しい実行可能解を作成する。

.

$k=_{l^{l}\lambda(\varphi}j.)+1,$ $\cdots,\tau$$\varphi^{j+1}=\varphi^{j}+\theta^{*}(\hat{\varphi}^{j}-\varphi’j)$21$f(\varphi^{j}+\theta(\hat{\varphi}-\varphi^{j}\mathit{7}))$$f( \varphi^{j}+\theta^{*}(\hat{\varphi}^{j}-\varphi)j)=\max_{<0\theta\leq\overline{\theta}}$

ただし、

,

$\overline{\theta}=\min\{\theta_{1}, \theta_{2}\theta 3\theta 4\})-$

であり、$\theta_{1},$$\theta_{2,3}\dot{\theta},$$\theta_{4}$

.

(21)

のそれぞれは、次式により定義される値である。
$\infty,\hat{\varphi}^{j}(i, t)-\varphi^{j}(i, t)<0$

なる $(i, t)$ がなければ$\theta_{1}.--\{$$\min_{i,t}\{-\frac{\varphi^{j}(i,t)}{\varphi^{j}(i,t)-\varphi^{j}(i,t)}|\hat{\varphi}^{j}(i, t)-\varphi^{J}(i, t)<0\}$$\infty,\hat{\varphi}^{j}(i, t)-\varphi^{j}(i, t)>0$

なる $(i, t)$ がな}\iota れば$\theta_{2}.--\{$mlni,$t \{\frac{m_{i}i-\varphi^{j}(i,t)}{\varphi^{j}(i,t)-\wedge\varphi^{j}(i,t)}|\hat{\varphi}^{j}(i, t)-\varphi^{j}(i,t)>0\}$$\infty)\sum_{i}C_{it}(\hat{\varphi}^{j}(i, t)-\varphi^{j}(i, t))>0$$\theta_{3}$7, でなければなる$t$, でなければがな (1 れば$\{$$\min_{t}$$\{.\cdot\frac{\Phi(t)-\sum_{i}\alpha t\varphi j(i,t)}{\sum_{i}c_{it}(\varphi^{j}(i,t)-\varphi(i,t))j}|\sum_{i}c_{it}(\hat{\varphi}(ji, t)-\varphi^{j}(i, t))>0\}\}$$\infty,$$\Sigma_{i,t}c_{d}(\hat{\varphi}J(i,t)-\varphi r(i,f))<0\tau^{\theta}$

でなければ$\theta_{4}.--\{$$\frac{M-\Sigma_{i,l^{C}}l\mathrm{r}\varphi^{j}(i,t)}{\Sigma_{i,t^{ht(}}\varphi(i,t)-\varphi^{j}(i,t))j},$$j=j+1$ として、$(\mathrm{G}\mathrm{C}2)$における手順は、$\mathrm{T}^{\theta}!x\#\iota nf\epsilon$$(\mathrm{G}\mathrm{C}2)$$\varphi^{j\prime}$へ戻る。

が最適解だと仮定した場合の最適ラグランジ乗数を求める 4.1 節の方法に他ならない。
すように作成されており、 もし\mbox{\boldmath $\varphi$}^j$=\varphi^{j}$$\hat{\varphi}^{j}$は定理 1 の (10)$(11)$

式を満たならば、 同時に (7) $\sim(9)$ 式をも満足させることになるから、 この実行可能解が最適となる。
$(\mathrm{G}\mathrm{C}3)$

において. とならなければ、 新しい実行可能解\mbox{\boldmath $\varphi$}j+l が作成$\hat{\varphi}^{j}=\varphi^{j}$

されるが、 このとき $f(\varphi^{j})<f(\varphi^{j+1})$ となることが言えれば、 実行可能領域\Psi の有界性と$f(\cdot)$は明らかである。

の有限性から、$\varphi^{j+1}$$\lim_{jarrow\infty^{f(}}.\varphi^{j}$) が最適値に収束すること

は方向\mbox{\boldmath $\varphi$}^j-\mbox{\boldmath $\varphi$}j への画線探索で求められるから、 これが上昇方向であること、 すなわち$\nabla f(\varphi^{j})(\hat{\varphi}^{j}-\varphi^{j})>0$を確認することにより、 このアルゴリズムの最適解への収束性を証明できる (–(2) 総量完結法
この解法アルゴリズムは、 定埋 2 で述べた問題の重み付き総量制約と最適ラグランジ -乗数\mbox{\boldmath $\lambda$} との間の単調な関係を利用して、 を調整することに$=$$\lambda$より対応する重み付き総量を求め、 最終的に問題の重み付き総和の条件に22合った最適解を求めようとするものであり、 その意味でこの方法を総量完結法と呼ぼう。 最適解を\mbox{\boldmath $\varphi$}* で表すものとする。
アルゴリズムA$\mathrm{T}$(TACI) すべての $(i, t)$ に対して f/\partial \mbox{\boldmath $\varphi$}(i, )
$t$

$0$

$\mathrm{C}^{\backslash }$$|_{\varphi=0}\leq 0$

ならば、最適解を\mbox{\boldmath $\varphi$}*$=$として終了する。

ここで、 $\lambda_{\max}=\sup_{i,t}\{\xi|\rho_{it}^{-1}(\xi;\mathrm{o})=0\}$ を求めておく o(TAC2)$\lambda=0$に対応する最適解\mbox{\boldmath $\varphi$}\mbox{\boldmath $\lambda$}* と限界総量

アルゴリズム(TAC3)$AL_{\lambda}$をにより求め、 次に従う。

(i)$M_{rnax}\leq M$ ならば終了(ii)$M_{\max}>M$ ならば、$\lambda=(\underline{\lambda}+\overline{\lambda})/2$$M_{7n.ax}=\Sigma_{\mathrm{i},t}c_{it}\varphi^{\lambda*}(i, t)$)$\varphi^{\lambda*}$$\underline{\lambda}=0,$が最適解である。

$\overline{\lambda}=\lambda_{\max}$とし、 アルゴリズム$AL_{\lambda}$

とおぐ)

により

$\varphi^{\lambda*}$を求める。 この解の総量に対し、 以下の手順に従う。

(i)

(ii)

$\Sigma_{i,t^{C_{\mathrm{t}}},t}.\varphi^{\lambda*}(i, t)=M$

ならば終了。 現在の\mbox{\boldmath $\varphi$}\mbox{\boldmath $\lambda$}* が最適解である。

$\Sigma_{i,t^{C}\mathrm{i}b\varphi^{\lambda}}.*(?_{\ovalbox{\tt\small REJECT}}, t)>M$

ならば、$\underline{\lambda}=\lambda$とおき、$(\mathrm{T}\mathrm{A}\mathrm{C}3)$を繰り$\overline{\lambda}=\lambda$とおき、$(\mathrm{T}\mathrm{A}\mathrm{C}3)$

を繰り

返す。

(iii)

$\Sigma_{\mathrm{i},t}C_{it},\varphi^{\lambda*}(j_{\text{ノ}}, t)<M$

ならば、

返す。
アルゴリズム$\mathrm{T}$A$\mathrm{C}$中にあるサブプロシジャー$A4L_{\lambda}$

は、与えられたラグラ

ンジ=- 乗数\mbox{\boldmath $\lambda$} に対応する最適解\mbox{\boldmath $\varphi$}\mbox{\boldmath $\lambda$}* を求めるアルゴリズムであり、 以下のように記述される (アルゴリズム$AL_{\lambda}$(AL1) 現在の暫定解を\mbox{\boldmath $\varphi$} とする。 ある $t\in T$ に対し行して導出した$\{\overline{\varphi}(?_{\text{ノ}})t), i\in K\}$$(\mathrm{A}\mathrm{L}2)\sim(\mathrm{A}\mathrm{L}4)$を実によって $\{\varphi(i, t), i\in K\}$ を置き23$\ovalbox{\tt\small REJECT}$.

.

計る薄算を現で表す、 すべての $t\in T$ について、 演算\mbox{\boldmath $\varphi$}$=\Lambda_{t}\varphi$

を繰り返し実行し、 この\mbox{\boldmath $\varphi$} を収束させる。
$(\mathrm{A}\mathrm{L}2)$$\nu_{t}=0$

$K\}$

とおいて、

$\varphi(i, t)=[p_{i_{\text{ノ}}^{}-1}t(\lambda+\nu_{\dagger;}.\varphi-it)]^{m}0^{it}$を、 繰り返し算法となる$\{\varphi(?_{\text{ノ}}, t),$$i\in$

を用いて導出する c)$AL_{\lambda}(l\ovalbox{\tt\small REJECT}_{t})$もし、 における局所総量が\Sigma , $c_{it}.,\varphi(i, t)\leq\Phi(t)$ となれば終了) そ$t$

うでなければ、$\Sigma_{i^{C_{i_{e}}}}t[p_{i_{\text{ノ}}^{}-1}t(\lambda+\nu_{t};\varphi_{-}i.t)]\mathrm{o}m_{it}=\Phi(t)$を、 以下のステップ$(\mathrm{A}\mathrm{L}3)\underline{\nu}=0_{\text{、}}$$(\mathrm{A}\mathrm{L}4)$

また、$\overline{\nu}$により求める。

を十分大きな値に設定する。
とし、 算法$\nu_{t}=(\underline{\nu}+\overline{\nu})/2$$l\ovalbox{\tt\small REJECT}_{t};\varphi_{-}i\dagger_{\text{ノ}})]^{m_{it}}0$$(\mathrm{A}\mathrm{L}3)\sim(\mathrm{A}\mathrm{L}4)$となる$\{\varphi(i_{\text{ノ}}, t), i\in K\}$(i)$\Sigma_{i}.C_{q.t}\varphi(i, t)=\Phi(t)$ならば終了。

(ii)$\Sigma_{?_{\text{ノ}}}Ci,t\varphi(i_{\text{ノ_{})}}t)>\Phi(t)$ならば、$\Sigma_{\mathrm{t}^{C}it\varphi}.(\uparrow_{\ovalbox{\tt\small REJECT}})t)<\Phi(t)$ならば、繰り返し算法

$AL_{\lambda}(I\ovalbox{\tt\small REJECT}_{t})$を求める。 この解の におけ$\underline{\nu}=l\ovalbox{\tt\small REJECT}_{t}$$\overline{\nu}=\nu_{t}$

$t$

$()$

とおき

$(\mathrm{A}\mathrm{L}4)$を繰り返す。

とおき$(\mathrm{A}\mathrm{L}4)$を繰り返す。

は以下による (-)

繰り返し算法

現在の解\mbox{\boldmath $\varphi$} から出発し、$\nu_{t};\varphi$

により $\varphi(i,, t)=[\rho_{it}^{-1}(\lambda+$$AL_{\lambda}(\nu_{t})$る局所総量に対し、 以下の手順に従う(iii)となる脇及び\mbox{\boldmath $\varphi$}$\gamma_{\text{ノ}}=1,$$\cdots,$$K$$AL_{\lambda}(\nu_{t})$に対しその $(?,, t)$ 要素\mbox{\boldmath $\varphi$}(i, ) を$t$$[\rho_{i,t}^{-1}(\lambda+$-it)]0”’ で置き換える操作を、解が収束するまで繰り返す。

以下で、総量完結法が最適解\mbox{\boldmath $\varphi$}* を導出した後停止する証明を概観しよう。
アルゴリズム$AL_{\lambda}$

が\mbox{\boldmath $\lambda$} に対応する最適解\mbox{\boldmath $\varphi$}\mbox{\boldmath $\lambda$}* を算出して停止することの証明

は、 次のようにして可能である。 まず、 繰り返し算法$AL_{\lambda}(\nu_{t})$は、 次の凸計画問題を逐次改善法で解いていることに他ならず、 この算法により、において、 すべての$\{\varphi(?_{\text{ノ}}, t), \uparrow_{\text{ノ}}\in K\}$$i$$\in K$に対し\mbox{\boldmath $\varphi$}(i, )$t$$=[\rho_{it}^{-1}(\lambda+\nu_{t};\varphi_{-\mathrm{i}}.\dagger.)]_{0^{it}}^{m}$が求められることが言える 1-

$t$

を満たす

24

:

$LP_{\mathrm{i}t}(\lambda, U_{i})$$\mathrm{s}.\mathrm{t}$$\max_{\rho},\{.f(\varphi)-\lambda\sum_{\mathcal{T}\mathrm{i}},c_{i_{\mathcal{T}}}\varphi(r_{\text{ノ}}.\tau)-\sum U_{\mathcal{T}}\sum c_{i\varphi(}.\mathcal{T}1)\mathcal{T}\mathrm{i}i,\mathcal{T})$.
$0\leq\varphi(i_{\text{ノ}}, t)\leq m_{l,t)}.i\in K$$\{\varphi(i, \tau), i\in K, t\neq\tau\in T\}$同様に、 アルゴリズム$AL_{\lambda}$

are given.

における演算 A7\mbox{\boldmath $\varphi$} の繰り返しにより、 次の凸計画問題の唯–の最適解が逐次改善により求められる ($LP(\lambda)$$\mathrm{s}.\mathrm{t}$:$\max_{\varphi}\{f(\varphi)-\lambda\sum_{i,t}C\mathrm{i}\dagger.\varphi(i, t)\}$.
$0\leq\varphi(i, t)\leq 77l_{i}.f.$,$7_{\text{ノ}^{}\cdot}\in K,$$\cdot t\in T$$\sum_{?}..c_{\uparrow_{\text{ノ}}t}.\varphi(?_{\text{ノ}}., t)\leq\Phi(t),$$\lambda=0$$t\in T$.

の場合、 問題 $(LP(\lambda))$ は定理 2 の問題 $(RPT)$ にほかならないから、アルゴリズム$AL_{\lambda}$

により、 限界総量 $M_{7nax}$ に対応する最適解\mbox{\boldmath $\varphi$}\mbox{\boldmath $\lambda$}* が (TAC2)において得られることになる。 したがって、 (TAC2) で $M_{7n.m}\leq M$ ならば、定理 2 から、ルゴリズム$\varphi^{\lambda*}$$AL_{\lambda}$が最適解であることが言える|、 また、により得られる解$\{\varphi(i_{\text{ノ}}, t)\}$あるとすれば、 すべての $(i, t)$ に対し\mbox{\boldmath $\varphi$}(i, )$t$

かっ、 $t\in T$ に対し、 $\nu_{t}>0$ ならば\Sigma ,らば$M_{\lambda}=\Sigma_{i,t}c_{i_{\text{ノ}}t\text{ノ}}\varphi(i, t)$

した総量$M_{\lambda}$の総量がたことになるの場合は、 ア$M_{\lambda}=\Sigma_{i,t^{C_{\eta}},\dagger},\cdot,\varphi(i, t)$$=[p_{il}^{-}1(\lambda+\nu t; \varphi-i\prime t)]_{0}^{m_{?}}t$$c_{\uparrow_{\text{ノ}}t\varphi}.(?\text{ノ}, t)=\Phi(t)_{\text{、}}$

で

であり、

さらには、 $\lambda>0$ なを満たしていることになるから、 この解は\mbox{\boldmath $\lambda$} に対応の最適解\mbox{\boldmath $\varphi$}\mbox{\boldmath $\lambda$}* に他ならない,) したがって、調整することにより$\lambda>0$$\Sigma j.,t^{C}i,t\varphi^{\lambda*}(i, t)=M$$(\mathrm{T}\mathrm{A}\mathrm{C}3)$において\mbox{\boldmath $\lambda$} をとなったとき、 最適解\mbox{\boldmath $\varphi$}* が得られ

25

5

数値例
計算時間ゐ観点から、 提案した 2 っの解法アルゴリズムと非線形計画法

においてよく知られている射影勾配法及び乗数法とを比較した数値実験を行ったが、 その詳細については紙数の関係上省略する。 原問題自身がかな
り -般的な表現式となっており、 種々の目的関数の形に関して数値実験を行わなければ、各解法の優劣を明言する訳にはいかないとは言えるものの、実施した数値実験の結果の概要は以下のとおりとなった。 実験は、 ある種の最適な捜索努力配分問題を例をとり、 色々なサイズの問題を提案した解法 (勾配完結法及び総量完結法) と射影勾配法、 乗数法により解き、 要し
た CPU-Time の平均値で比較したものである。その結果、 ほとんどのケースにおいて、 総量完結法、 勾配完結法、 射影勾配法、 乗数法の順にほぼ 1

桁 (10 倍) に近い計算時間の増加傾向が見られ、 総量完結法、 勾配完結$-$

法が計算時間の面から高速であることの傍証が得られた。

参考文献[1] de Guenin, J., Optimum Distribution of Effort: an Extension of theKoopman Basic Theory, Operations Research, 9(1961), 1-9.
[2] Horst, R., Pardalos, P.M., and Thoai, N.V., Introduction to Global

Optimization, Kluwer Academic Publishers, London, 1995.
[3] Ibaraki, T., and Katoh, N., Resource Allocation Problems: Algorith-

mic Approaches, The MIT Press, London, 1988.
[4] 今野浩, 山下浩, 非線形計画法, 日科技連 ($\mathrm{O}\mathrm{R}$

ライブラリ–6), 1984.

[5] Koopman, B.O., The Optimum Distrubution of Effort, Operations

Research, 1(1953), 52-63.