数理解析研究所講究録
第 747 巻 1991 年 62-72

62
Stochastic Programming と Reverse Convex Programming1

浩 (Hiroshi Morita)

大阪府立大学総合科学部

森田

岡山大学工学部

石井博昭 (Hiroaki Ishii). 逆凸計画問題 (Reverse convex programming problem)
非凸型の計画問題はいくつかの局所的な最小点をもっているので大域的な最小点を見つけるには実行可能領域全体を調べることが必要となるが、一般にそれは容易ではない。非凸型の計画問題の中でも特殊な型の問題に対しては大域的な最小点を見つけるためのアルゴリズムが示されており、 その内の一つの問題に逆凸計画閥題 (reverse convex programming problem)がある。逆凸計画問題とは、 凸関数である目的関数を補集合が凸集合であるような集合の共通部分を制約集合にもつ最小化問題であり、 次のように定式化される。
$P_{1}$:$f(x)$

最小化条,

件 1 $(x)\geq 0,$ $i=1,2,$ $\ldots,m(\geq n)$.

ただし、 $f$ : $R^{n}arrow R^{1}$ は凹関数で、 $g;$ : $R^{n}arrow R^{1}$ は準凸関数である、 $g:(x)\geq 0$ は不等号の向きを逆にすると凸領域を表すことから逆凸領域 (reverse convex region) と呼ばれている。 逆凸計画問題は Rosen [14] によって最初に考えられ ‘ Meyer [6] らによって Kuhn-Tncker 点へ収束する点列を生成するアルゴリズムが提案されている。 逆凸計画問題の一般的な解法としては Ueing [13] の組合せ的手法 ‘

Rosen [14] の繰り返し線形化手法や Tuy [10] の切除平面法などが知られている。 組合せ的手法は小点を見つげるもので、 $m$ や$n$${}_{m}C_{n}$個の逆-逆凸計画問題を解きその中から大域的最が大きくなると扱いにくい。 線形化手法は 1 つの実行可能解が任意に与えられたとき逆凸制約式を線形化した線形計画問題を繰り返し解く方法で、 その解は Kuhn-Tucker 点へ収束することが示されている。

本稿では後で述べる確率的計画問題から生じる最適化問題に適用した切除平面法について簡単に説明する。 逆凸制約式を満足する点の集合 $G\equiv\{x|g_{i}(x)\geq 0, i=1,2, \ldots, m\}$ の凸包を conv $G$ と表すとき 、P2:最小化$f(x)$

条$r\in$件,conv$G$の最適解は conv $G$ の端点の集合 $V(convG)$ の中に存在する。$V(convG)=V(G)\subset G\subset convG$より、問題$P_{1}$の最適解は G の端点すなわち conv $G$ の端点を探せば十分であることがわかる。

163
まず、線形計画問題に 1 本の逆凸制約式 $g(\geq 0$ が付加された以下の問題
最小化$p_{s:}$$c’x$,$g(z)\geq 0$$\iota\geq 0$,.

ただし、 $A$ は $m\cross n$ 行列 $(m\geq n)$ 、$b,$$x\geq 0$を作るようにすればよい。
$x^{h}$との交点

P4::は凸関数である。 また、 $D_{0}\equiv\{x|Ax=$$R^{n}arrow R^{1}$$z_{j^{h}}$$x^{h}$$x^{k}$

から$D_{0}\backslash G$

件$\alpha_{j}$$n$の最適解は多面体の辺と $G$ の交をある多面体 $D$ 上の退化していない端点で $x^{h}\not\in G$ とする。 こ$d_{i}^{h}$$n$

個のアフィン独立な端点$\{s_{1}^{h}, s_{2}^{h}, \ldots, s_{n}^{h}\}$は $s_{i}^{h}-x^{h}$ と表され、 この方向の延長線と個の一次元最小化問題を解けば求められる。

$g(x^{h}+\alpha_{j}d_{j}^{h})\geq 0$$\alpha_{j}^{*}$

,とすると

(1)

$z_{j}^{h}=x_{j}^{h}+\alpha_{j}^{l}d_{j}^{h}$

P4 が実行可能でないときには$\alpha_{j}^{*}$

は 1 以上の適当な値とする。

$1,2,$ $\ldots,$ $n$ はアフィン独立であり、 これらの点で定まる(2)$H(x^{h})$cut $H(x^{h})$ は: $eM^{-1}(x-x^{h})\geq 1$で与えられる。 ただし、($)

$D_{0}$,

問題 P4 の最適解をとなるが、 問題$p_{\}$を取り除くような切除平面を求めて ‘ conv $(D_{0}\cap G)$

から出ている $D$ の辺の方向は次の最小化
条$D_{0}$に隣接する $D$ の端点の集合 $adj(x^{h})$ はで構成される。
$G$$g$} は空でなく有界であるとする。 このとき問題点の中に存在する。そこでのときを考察する。

,$A\sim=b$件

条$p_{\}$$M=[z_{1}^{h}-x^{h}, z_{2}^{h}-ae^{h}, \ldots,z_{n}^{h}-x^{h}]$は $nX_{-}n$ 行列で、 $e=(1,1, \ldots, 1)$ は$7t$次元ベクトルである。

2$z_{j^{h}},$$j=$

64
定理. $D\supset(D\cap H(x^{h}))\supset(D\cap G)$ .

証明: [3, Theorem 10]$x^{k}$が退化している場合は$j=1,2,$$d_{j}^{h},$I$\ldots$$x^{h}$に隣接する $D$ の端点は, nn’(nn’ はその個数) も$n$$n$個以上存在し、 その方向ベクトル個以上存在するので ‘ (2) 式の cut は一意に決められないし cut の中に実行可能領域を切り落としてしまうものが存在することもある。実行可能領域を切り落とさない cut として ‘ Carvajal-Moreno は次のような cut を与えている。

(4)$H(x^{h})$ただし、$p_{\epsilon:}$$(y_{0}^{*}, y^{*})$

最小化
条は次の問題:$y^{*}(x-\iota^{h})\geq y_{0}^{l}$の最適解である。

$P_{5}$$y0$

件$\alpha_{j}^{*}yd_{j}^{h}\geq y0,$

$j=1,2_{t}\ldots,$ $n’$$\sum_{:=1}^{n’}\alpha_{i}^{*}yd_{i}^{h}\leq 1$,.

$n’=n$ の場合はもちろん (2) 式と (4) 式は一致する。 この cut $H(x^{h})$ を用いた問題$p_{\}$の解法アルゴリズムは以下のようになる。

アルゴリズム$-\backslash 1$

ステップ $0k=0$ とする。
ステップ 1$D=D_{h}$ならばステップ 2$D$として、問題 $\min\{c’x|x\in D\}$ を解く。 この問題の最適解$x^{h}$は問題$p_{\}$糾 $1=D_{h}\cap H(x^{h})$$x^{h}$が $x^{h}\in G$の最適解となり終了。 そうでなければステップ 2 へ。
としてステップ 1 へ。

このアルゴリズムは複数の逆凸制約式の存在する線形計画問題に対して拡張することができる。 問題 P2 において $g:R^{u}arrow R^{l}$ とする。

$x^{h}$が満たしていない逆凸制約式の番号の集合を $L=\{i|g_{i}(ae^{h})<0\}$ としたときステップ 2 において

(5)

$H(ae^{h})=\cap H(x^{h};i)$$i\in L$とおけばよい (アルゴリズムー 2)。ここで、 $H$ ($z^{h}$; i) は点$r^{h}$と第$i$番目の逆凸制約式から求めた cut を表す。

複数の逆凸制約式をもつ問題に対する Toy または Carvajal-Moreno の切除平面法の収束性は保証されておらず、 実行可能でない点へ収束してしまうような問題例も示されている [3]。

365
ただ一つの逆凸制約式をもつ問題に対しては、 最適解への収束性 [11] あるいは有限回で最適解が見つけられるアルゴリズム [4] などが論じられている。

2. 確率的計画問題 (Stochastic programming problem)
確率的計画法は確率的変動を含む最適化問題を取り扱っており、 不確実性のもとでの意思決定などに用いられている手法である。確率的計画法では確率的変動は、 その分布が明らかである subjective risk と呼ばれるものと、 分布のもつ事前確率のみがわかっているsubjectiveuncertainty と呼ばれるものに区別されている。前者が主に確率計画法の研究対象として取り扱われてきたが、 最近では統計的アプローチにより後者も取り扱われるようになっている。
確率空間 $(\Omega,A, P)$ が与えられたとき、 確率的計画問題は$SP_{1}$:最小化
条$f_{0}(x, \omega)$,件轟 $(2, \omega)\leq 0,$ $i=1,2,$$\epsilon\in X\subset R^{n},$$\omega\in\Omega$と表される。ここで轟, $i=0,1,$$\ldots,$$\ldots,$$m$,.

$m$

は$R^{n}$上の実数値関数、 $X$ は$R^{n}$のある部分集合である。

確率的変動をもつ制約式の実行可能性にはいくつかの定義が考えられる。 たとえば、 平均値が実行可能であること(6)$B\{f:(x, \omega)\}\leq 0$とか、 実行可能となる確率を一定以上に保つこと(7)$Pr\{f:(x,\omega)\leq 0\}\geq\alpha$などである。 (7) 式を機会制約条件 (chance constr 可 nt) と呼ぶ。機会制約条件は等価な確定制約式に変換することができるが、一般に得られる制約式は計算上扱いにくい形 (非線形、非凸形) になることが多い。確率的変動をもつ目的関数にもいくつかの等価確定式が考えられている。平均を最小にする$E$モデル、平均と分散を同時に考える EV モデル、 目的関数の値がある目標値以下になる確率を最大にする確率最大化モデルなどが挙げられる。
最適化問題を記述しているパラメータに未知のものがあるときには何らかの情報をもとにそれらを推定する必要がある。確率的計画法における統計的アプローチは情報理論と密接に4

66関連しており、 その一つとして機会制約条件に対するサンプルのもつ情報の価値などがベイズ流の考え方に基づいて示されている [5]。
他の統計的アプローチとして、 ゲーム理論的なミニマックスアプローチがある。 確率分布の分布パラメータが確実に知られていない場合にその分布の生じる可能性のある中で最も悲観的な状況において最適化を図るというアプローチである。 この問題は以下のように定式化される。

SP2:

最小化

,$F\in \mathcal{F}$

条件$F$$\max B_{F}[f_{0}(x, \omega)+\phi(ae, \omega)]$は確率分布、$x\in X\subset R^{n},$$\mathcal{F}$$\omega\in\Omega$.

は $F$ の属する分布のクラス、 \phi $,$($るための調整に要するペナルディ費用を表す。 問題$\omega)$は$SP_{2}$$F\in \mathcal{F}$のとき実行可能性を維持すの特別な場合として、 単純リコース

問題に対する最適解の安定性は Dupa\v{c}ov\’a [2] によって議論されている。
信頼領域という概念を取り入れた統計的アプローチとして、確率的変動が時系列データとして与えられている問題に対し最適解や最適値の信頼領域を構成するという考え方もあるが $[1]$、我々が従来より考察してきた問題はミニマックスアプローチに信頼領域を取り入れたものである。問題$SP_{2}$のように分布 $F$ をクラスれた分布パラメータ$\theta$の信頼領域$S_{\theta}$$\mathcal{F}$に限定するときに、得られたサンプルにより推定さを用いてクラス分布 $F$ を限定するモデルを提案している $[7,8]$。

$\mathcal{F}$の部分クラス$\mathcal{F}_{0}=\mathcal{F}(\cdot|\theta\in S_{\theta})$に[7] では制約式の右辺が未知パラメータをもつ正規分布にしたがう確率的線形計画問題、 [8] では目的関数の係数が未知である線形計画問題に対して、得られたサンプルから構成された信頼領域を用いた手法 (confidence region method)を考察している。
逆凸制約式が現れるのは線形制約式の係数に未知のものが含まれている問題で、 線形制約式の信頼領域を線形回帰分析によって推定したときである。 次章でその問題と解法を述べる。

8. 未知係数を含んだ制約式をもつ線形計画問題
未知係数が含まれている線形の制約式をもつ線形計画問題 LP を考察する。
$n$

LP:

最小化

条

件

$\sum_{i=1}9^{X}i$$\sum_{i=1}^{\mathfrak{n}}a$,$ae=b_{i},\cdot i=1,2,$ $\ldots,$ $m$

5,

67

$\sum_{j=1}^{n}\beta_{ij}x_{j}=\eta_{i},$$j=1,2,$ $\ldots,n$ .

$\iota_{j}\geq 0,$

ここで$\beta_{ij}t$$i=1,2,$ $\ldots,l$ ,ま未知係数、 他はすべて既知とする。 未知係数を含んだ制約式 $\beta’x=\eta$ は、 “線形回帰モデルとしてを推定した結果$\beta$$\eta$がある有意水準の下でのていること” と解釈されるものとする。

$\beta_{ij}$$\beta^{l}x$の信頼区間の中に含まれを推定するために回帰分析を用いると、 ある有意水準の下で推定される制約式は逆凸領域を形成することになる。 本章では未知係数を含んだ制約式の数 が 1 つの場合と 2 つ以上の場合に分けて、 問題 LP の解法を述べる。
$l$3.1. $l=1$ の場合 [9]有意水準$\alpha$のもとでの$\beta^{\iota_{\}}$の信頼区間を CI$(\sim;\alpha)$と表すとき、 問題 LP は次のようにみることができる。
$P$:

,最小化

$dx$

条

$A\sim=b$

件,$\eta\in CI(x;\alpha)$,$\geq 0.
$\beta$の最小二乗推定量を$\beta$、標本分散行列を $V$ と表すとき(8)$\beta’x$の信頼区間 CI$(\sim;\alpha)$

は$\hat{\beta}’x\pm\sqrt{nF_{a}(n,N-n)}$$a_{e/Vx}$を上下限とする区間となるので、 制約式 $\beta’x=\eta$ を推定した結果は次の 2 つの逆凸領域を示
す非線形不等式で表される。
$-\hat{\beta}’x+\sqrt{nF_{\alpha}(n,N-n)}\sqrt{x’Vx}+\eta\geq 0$(9)$\hat{\beta}^{1}x+\sqrt{nF_{\alpha}(n_{1}N-n)}\sqrt{x’Vae}-\eta\geq 0$

簡単のためそれぞれ $g^{-}(x)\geq 0,$ $g^{+}(x)\geq 0$ と表す。 問題 $p0$ : $\max\{c’z|x\in D_{0}\}$ の最適解を$x^{0}$とするとき、 $g^{+}(x^{0})\geq 0$ かつ $g^{-}(x^{0})\geq 0$ ならばのうち少なくとも一方はどのような$x$$x^{0}$は $P$ の最適解である。 2 つの不等式に対しても常に満たされているため、 満たされていない不等式のみを考えれば十分であり、 このとき $g(x)$ は次のように決められる。

(10)$g(x)=\{\begin{array}{l}g^{+}(W)g^{+}(x^{0})<0\emptyset\ \yen g^{-}(W)g^{-}(W^{0})<0\emptyset k\not\equiv\end{array}$668
したがって問題 $P$ は問題$p_{\}$のような線形計画問題に 1 本の逆凸制約式が付加された問題とみることができる。 このとき問題 $P$ の最適解は多面体する。 アルゴリズムー 1 によって$x^{h},$$k=0,1,2,$$\ldots$の辺と曲面$D_{0}$$\theta G$, を求めていくとき、の交点の中に存在$ae^{h}$が多面体辺上になければ問題 $P$ の最適解になり得ないので Tuy cut を構成することなしにから取り除くようにする。 これには$x^{h}$に隣接する端点ればよい。 また ‘ Tuy cut の作り方によると多面体$D_{0}$$S_{2}hh\ldots$$\delta_{1},$$P$のを$D_{h}$魂を通る平面でカットすの 1 つの辺には高々 1 個の在し得ない。 よって、有限個の Toy cut を用いることで問題$x^{h}$$D_{0}$$x^{h}$しか存の最適解を見つけることができる。 そのアルゴリズムは付録に示す (アルゴリズムー \S )。

3.2. $l\geq 2$ の場合$l\geq 2$の場合も未知係数を含んだ制約式; を $\eta_{i}\in CI_{i}(x;\alpha),$ $i=1,2,$$\sum_{j}^{n_{=1}}\beta_{ij j}=\eta$$l$$\ldots,$と解釈することで、 $l=1$ と同様に問題 $P$ を定式化することができる。
$P$:

最小化
条

件

$c^{\iota_{\}}$,$A\sim=b$,$\eta_{\dot{n}}\in CI_{i}(x;\alpha),$$i=1,2,$ $\ldots,l$ ,$\geq 0.
ここで窮 $\in CI_{i}(x;\alpha)$ を (10) のように $g:(ae)\geq 0$ と表す。 $l\geq 2$ のとき最適解は$D_{0}$の辺上にあるとは限らない。 アルゴリズムー 2 を適用しただけでは、切除平面の傾きが目的関数の傾きに次第に近づいていくとき、 点列$\{x^{h}\}$が最適解に到達しないことがある。 [$]定理. 問題 $\min\{dx|x\in D_{h}\}$ の最適解の点列$\{x^{h}\}$が実行可能でない点へ収束するとき、 切除平面の傾きは目的関数の傾きに平行になる。

証明: 点列$\epsilon$$\{r^{h}\}$が実行可能でない集積点蕾をもつとき、十分大きなとなるので、 点$ae^{h+1}\in D_{k}\cap H(x^{h})$$x^{h}$と$H(x^{h})$の距離をに対して $||x^{h}-x^{h+1}||<_{-}$

dist $(x^{h}, H(x^{h}))$ と表すと、$x^{h}\in D_{k}\backslash H(x^{h})$とより、 dist $(x^{h}, H(x^{h}))<\epsilon$ となる。このとき $D_{h+1}=D_{h} \cap[\bigcap_{i\in L}H(x^{h}; i)]$より

dist(11)$k$$(ae^{h}, H(x^{h}; i))\leq\epsilon$$c’x^{k}\geq c’z_{j^{h}}(i),$$j=1,2,$ $\ldots,n$$z_{i^{h}}(i)\in H(x^{h}; i),$7$j=1,2,$$\ldots,$$n$

69が得られる。 ここで$z_{i}^{h}(\ovalbox{\tt\small REJECT},$$j=1,2,$ $\ldots,n$ は$x^{h}$から出る多面体$D_{h}$の辺の延長線と逆凸制約式 $g_{i}(x)\geq 0$ の交点を表わしている。 $H(x^{h})$ が目的関数に平行にならなければ、 (11)式より$||x^{h}-z_{j}^{h}(i)||\leq\epsilon$$\iota^{h}\in D_{0},$$z_{j^{h}}(i)\in G$となるであるから、$z_{j}^{k}(i)$が少なくとも 1 つ存在しなければならない。 一方、$\overline{x}\in D_{0}\cap G$となり邑が実行可能でないことに反する。

I

点列が実行可能でない点へ収束したときには、 再度点列が最適解に向かって動き出すようにしてやらねばならない。 $|dx^{h}-c’x^{h+1}|\leq\epsilon_{1}$ となったとき、との距離 $d(x^{h})$ が$\epsilon_{2}$$x^{h}$が実行可能 (実行可能領域以下として判定する) でないならば、 切除平面は目的関数に平行に近づいているため,$|| \max dz_{i}^{h}(i)-\min_{ii,j,j}dz_{j}^{h}(i)||\leq\epsilon$(12)$\min_{i,j}dz_{i}^{h}(i)\leq c’x^{h+1}\leq\max c’z_{j^{h}}(\iota’):,j$となる。 このとき

(13)$c’\overline{x}=\min c’z_{j}^{h}(i)>c’r^{*}$となるため、新たに切除平面$\overline{H}(ae^{h})$: $d’ \min c’z_{j}^{h}(i)$ を入れても主問題$P$の実行可能領域が取り除かれることはない。 問題 $P^{h+1}$ : $\max\{dae|x\in D_{h}\cap\overline{H}(x^{h})\}$ の最適解 $x^{h+1}$ は切除平面$\overline{H}(x^{k})$上に存在し、 $x^{h+i}$ の隣接端点の少なくとも一つは多面体$D_{0}$の頂点となっているので、(14)$\Vert\min_{:_{\dot{J}}}c’z_{j}^{h+1}(i)-c’x^{h+1}||\geq\delta$となる。 ただし$\delta$は問題量である。 したがって点列$P^{0}$の 2 つの基底解の目的関数の値が異なるときの差の下限を表す$\{x^{h}\}$が実行可能でない点へ収束したときにはこの切除平面$\overline{H}(x^{h})$を入れることにより、 点列を蓼から最適解に向かって再び動かすことができる。 アルゴリズ
ムを付録に示す (アルゴリズムー 4)。
アルゴリズムー 4 の生成する点列は最適解へ収束しているが、 その中途段階においては実行可能でない点列を生成している。 そのためアルゴリズムを途中で止めて最適解の近似値を得ようとするときなどにはその時点での実行可能な点が要求される。 そこで、各々の$x^{k}$に対して逆凸制約式を線形化した問題を解くことによって最適値の上限を与える。逆凸領域 $g_{i}(x)\geq 0$ 上の$x^{h}$(15)に最も近い点を $x^{h}(i)$ と表すとき、先に出てきた実行可能領域と$d(x^{h})= \sum_{:\in z}||x^{h}-x^{h}(i)\Vert$8$ae^{h}$との距離 $d(x^{h})$ を、

70で与える。 このとき問題最小化$P$$c^{i}x$件

条$P$の逆凸制約式を線形化した問題 $P$ ’,$A\sim=b$,$\nabla g_{i}(x^{h}(i))’(x-x^{h}(i))\geq 0,$$i=1,2,$$l$$\ldots,$,$\geq 0.の最適解は常に問題 $P$ ’ の実行可能解を与え、 さらに
題$P$’ の最適解も問題$P$$x^{h}$が問題$P$’ の最適解に収束することがわかる。

付録アルゴリズムー 3, 4

procedure CPMEP:
begin

Set $karrow 0$ とする;
問題

$P^{0}$

whileを解く;$x_{h}\not\in D$

do

begin

irが多面体の辺上にある
then Tuy または Carvajal-Moreno の cut $H(x^{h})$ を作る$r^{h}$else$s_{1}^{h},$$D_{0}$$\epsilon^{h},$$\ldots$, 魂を通る平面を cut とする;

$D_{h}+\iotaarrow D_{h}\cap H(x^{h})$とする;とする;を解く;$karrow k+1$

問題

$P^{h}$end’ は問題$P$の最適解である;

end.
アルゴリズムー 3

9’ の最適解に収束すると問71
CPMEP’:

procedurebeginとする;$karrow 0$

repeatbegincutを作る。 ただし $\overline{H}(z^{0})=R^{n}$ とする;とする;$karrow k+1$ とする;問題を解く;$\overline{H}(x^{h})$$D_{h+1}arrow D_{h}\cap\overline{H}(x^{h})$$P^{h}$

while $|dx_{h}-c’x_{h-1}|>\epsilon_{1}$ dobegincutを作る;$H( \iota^{h})=\bigcap_{i\epsilon r}H(r^{h};i)$$D_{h+1}arrow D_{h}\cap H(ae^{h})$とする;とする;を解く;$harrow h+1$

問題

$P^{h}$

end
end

until
$x_{h}$$d(\_{h)}\leq\epsilon_{2}$は問題$P$;の最適解である;

end.
アルゴリズムー 4

参考文献[1] T.Cipra, “Prediction in Stochastic Linear Programming,” Kybernetika 23 (1987) 214-

226.
[2] J.Dupa\v{c}ov\’a, “Stability in Stochastic Programming with Recourse–Estimated Pa-rameters,” Mathematical Programming 28 (1984) 72-83.

[3] R.J.HiUestad and S.E.Jacobsen, “Reverse Convex Programming,” $Ap$plied Mathemat-ics and optimization 6 (1980) 63-78.
[4] R.J.HiUestad and S.E.Jacobsen, “Linear Programs with an Additional Reverse ConvexConstraint,” Applied Mathematics and optimization 6 (1980) 257-269.
[5] R.Jagannathan, “Use of Sample Information in Stochastic Recourse and Chance-Constrained Programming Models,” Management Science 31 (1985) 96-108.
[6] R.Meyer, “The Validity of a Family of optimization Method,” SIAM Journal ofControl 8 (1970) 41-54.

10

72[7] H.Morita, H.lshii and T.Nishida, “Confidence Region Method for Stochastic Program-ming Problem,” Journal of Operation Research Society of Japan 30 (1987) 218-230.
$\ell$[8] H.Morita, HJshii and T.Nishida, (Stochastic Programming with Estimated Objec-tive,” Technology Reports of the Osaka University 39 (1989) 1-7.
[9] H.Morita, H.Ishii and T.Nishida, “Stochastic Linear Programming Problem with PartiaUy Estimated$C$

onstraint, Mathematica Japonica 35 (1990) 551-559.
)[10] H.Tuy, “Concave Programming Under Linear Constraints,” Soviet Mathematics 5(1964) 1437-1440.
[11] H.Tuy, “Convex Programs with an Additional Reverse Convex Constraint,” Journ$al$of optimization Theory and Applications 52 (1987) 463-485.
[12] H.Tuy, “Global Minimization of a Difference of Two Convex Functions,” MathematicalProgramming Study 30 (1987) 150-182.
[13] U.Ueing, “A Combinatorial Method to Compute a Global Solution of Certain Non-Convex optimization Problems,“ in: F.A.Lootsma, ed., Numerical Methods for NonLinear optimization, (Academic Press, New York, 1972) pp.223-224.
[14] J.B.Rosen, “Iterative Solution of Nonlinear Optimal Control Problems,” SIAM Jour-nal of Control 4 (1966) 223-244.

11$\cdot$