Stability of equivalent programming problems of the multiple objective linear stochastic programming problems

(1)

STABILITY OF EQUIVALENT PROGRAMMING PROBLEMS

OF THE MULTIPLE OBJECTIVE LINEAR STOCHASTIC PROGRAMMING PROBLEMS

GYEQNG-MI CHQ

ABSTRACT. In this paper the stochastic multiple objective programming problems where the right-hand-side of the constraints is stochastic are considered. We define the equivalent scalar-valued problem and study the stability of the equivalent scalar-valued problem with respect to the weight parameters and probability mesures under reasonable assumptions.

1. Introduction

This paper is a sequel to [1], where the following multiple objective two-stage programming problem with complete fixed recourse was investigated.

(1)

VMIN g(x) +Edmind'y] .1 subject to Ax= b

Dx+Wy = e, ^€^on ^(3,!S,p.)

x 2:0, y 2:0,

whereA is an m x n matrix, D is anin x n matrix, x is an n-vector, dand y are ft-vectors, 1= (1, ... ,1)'isa r-vector, bisan m-vector and €is a random vector defined on the probability measure space (3,!S, p.), g(x) = (gl(X),··· ,gr(X))', gi(X) = Ci1Xl + ... +CinXn, 1 :::;

i :::;r,isa linear function,W E L(R¹ⁱ^,Rm) such that for all€E 3, {yE Received September 22, 1996.

1991 Mathematics Subject Classification: 90C15, 90C29, 90C31.

Key words and phrases: stochastic programming problem, equivalent scalar- valued problem, stability analysis.

Thiswork was partially supported by the Dongseo University Research fund.

(2)

Rn I^Wy ⁼ e- ^{Dx, y:2:} Ô} ^=I⁰ând ^{u Ê ^{R m}I^W'u ~d} =1= 0, and E~

denotes the mean operator with respect toe.

All quantities considered here belong to the reals. We use the notation

eto denote a random vector of dimension rn, as well as the specific values assumed by this random variable.

In [1], Cho defined an equivalent scalar-valued problem for the problem (1) and observed the stability of the problem with respect to the weight parameter and probability distributions of the random vector, respectively. In this paper we study the stability of the equivalent scalar-valued problem with respect to the weight parameters and the probability distributions.

In the following wewillintroduce the parametric programming analysis due to D. Klatte([3]) which we are going to use to prove our main result.

Let us consider the following programming problem with a parameter tET:

p(t) : min{f(x, t) : x E M(t)},

whereT is a metric space with distance function d(·, .), M is a closed- valued multifunction from T into Rn, and f : Rn ^X T - R is a continuous function. GivenQ C Rn, for any t E T, we define

MQ(t) = M(t) nclQ,

PQ"(t) = inf'{J{x,ifTx^E ^MQ(t)},

'l/JQ(t) ={x E MQ(t) If(x, t) = PQ(t)},

where clQ denotes the closure of Q. We call PQ the optimal value function with respect to clQ and 'l/JQ the optimal set function with respect to clQ. Now we shall give some basic definitions and theorems.

DEFINITION 1.1. Given to E T, a nonempty set X C Rn iscalled a complete local minimizing set (CLM set) for f(', to) on M(tO) if thereis an open setQcontaining X such that X = 'l/JQ(tO).

Note that a CLM set with respect top(tO) is always a subset of the set of all local minimizers ofp(tO) , and CLM set are closed under our general assumptions on the problemp(.).

(3)

DEFINITION 1.2. M: T ~ Rn,issaid to be closedattoif and only ift^k ~to, x^k ~ Xo, as k ---+ 00, and x^k E M(t^k⁾ ^=} XO E M(tO).

DEFINITION 1.3. A multifunction M from T to Rn is said to be pseudo-Lipschitzianat (XO,tO), where to ET and XO E M(tO), ifthere are neighborhoods U = U(tO) and V = V(XO) and a positive real number L such that both

M(t)nVc M(tO) +L· d(t, to) . B_n and M(tO) nV c M(t)+L .d(t, to) .B_n

hold for allt E U, where Bn^isthe closed unitball inRn, and

x +{3 .Bn ={x+{3 .u I^X E X, u E Bn },

for X c Rn and(3 E R.

THEOREM 1.4. ([3]) Consider the parametric program p(t) : fix some to ^E ^T with the following conditions:

(Cl) Assume that there existsa bounded open subset V ofRn and a nonempty subsetX ofV such that X ='l/Jv(tO).

(C2) Let the multifunction M be closed-valuedandclosed at to.

(C3) Let M beapseudo-Lipscmtzianateach pair (XO, to) E'l/Jv(tO)x {to}.

(C4) Suppose therearereal numbers pE (0,1], Lf > 0and d[ > 0 such that

for each X, yE clVand each t satisfying d(t, to) < df.

Then the following conclusions hold:

(a) The multifunction "pv is upper semicontinuous at to, i.e., for each^E>0 there exists1]>0 such that

(b) There exist positive real numbersdp andLp such that 'l/Jv (t) =f:. 0

isa CLM set forf(·,t) onM(t) andsuch that

Ipv(t) - pv(tO) I::; Lp· d(t, to)P whenever d(t, to) < dp.

(4)

It is clear that we couldalsowrite problem (1) as:

VMIN g(x)+Edmind'y: Wy = e- ^Dx,y ~ 0]·1 (2) subject to Ax= b

x~o.

Now we define a feasible solution to problem (1).

DEFINITION 1.5. ([5]) A feasible solution to (1) is a vector x such that it satisfies the first stage constraints and such that for anye^E ^{3, it}

is always possible to find a feasible solution to the second stage problem min{d'yIWy= e- ^{Dx, y} ^~ ^O}.

Let K be the set of feasible solutions of(1), then

K = {x I^Ax=^b,x ^~^O}n{x I'Ve, 3 y ~ 0 such that Wy =e- ^Dx}.

Then K is a convex polyhedron. Define

Q(x,e) = min{d'y IWy = e- ^{Dx, y} ~ O}

and

Q(x)= EdQ(x,e)].

r,[l!~!!_Qf~)is conV:E!~~(:t~Qnt!!1u,o~. So!V"~ h~v~ ~ equivalen~P!"o

gramming problem to (1).

(3) VMIN F(x) = (gl(X) +Q(x}, .. · ,gr(x)+^Q(x))'

subject to x EK.

DEFINITION 1.6.([2]) The vector x* is an efficient solution of

vMIN F(x) = (!l(x)"" , fr(x))' subject to x EK

if and only if there exists no x E K such that Ii^(x) s Ii^(x*) ^for

i = 1,· .. ,r and such that for at least onei_o one has lio(x) < lio(x*).

(5)

DEFINITION 1.7. ([2]) The vectorx* is a properly efficient solution of

VMIN F(x) =(h(x),··· ,fr(x))' subject to x EK

if and onlyifit is efficient andifthere exists a scalarM >

°

^{such that}

for each i and eachx E K satisfyingfi(X) < fi(X*),there exists at least onej such that h(x*) <hex) and (fi(X*) - fi(X))j(h(x) -h(x*)) $ M.

We define an equivalent scalar-valued probleI;ll for the problem (1) as follows;

(4)

' r

minimize LAi9i(X)+Q(x)

i=1

subject to x E K, where _L:~=1Ai = ^1, Ai > 0, i =^{1, ...} ,r.

CORORALLY 1.8. [1] x* is properly efIicient in problem (3) ifand only ifx* is optimal in problem (4) for some Awith strictly positive components.

2. Stability analysis

When we consider the stochastic programming problems, their stability with respect to the perturbations of the distributions of the un- derlying random variables plays an essential role. And since the weight parameter depends on decision makers, the stability with respect to weight parameter is also important. So we investigate the stability of the optimal solution set and optimal value functions to problem (4) with respect to the weight parameter A and the probability measure JL by applying the analysis of D. Klatte.

Define for q E (1,00) and k E (0,00),

(6)

where peRm) is the set ofall Borel probability measures on Rm. We restrict onpeRm;q,k) in our stability analysis and consider the weight parameter space as a discrete probability measure space because of its characteristics. Now we define suitable metrics on the weight parameter space and probability measure space. Define the bounded Lipschitz metricf3 on peRm) as follows;

f3(p" v) =sup{lk""g(~)p,(~)

-k""

g(~)v(~) ^I: ^g: ^R^m ~ ^R,

11 9 IIBL~ I}, for anyp, and v E peRm), where

11 9 IIBL= sup Ig(~) Î⁺^sup Îg(~) ^- ~(e) Î ^<^00,

{ER"" {=l:f d(~,~)

and

for

Note that the metric f3 metrizes the topology of weak convergence on p(Rm). Let s be a random variable defined on the sample space

n=-{ST,-S2,'·-·,-s:;.} and_SiE--R~Define a metric don-Q by

Then (n,d) is a metric space. We may treat A= {A E Rr I2:;=1Ai=

1,Ai > O} as a discrete probability measure space onn.

Define a metric don A by

for any A, AaEA. Then (A,d) is a metric space and for anyq>1,

r

' " AO_L.J _z·1 s·_z Iq <_- Mq_,

i=l

(7)

where M = max{1 ^Si 11 Si EQ}. Let AEA, J.L E p(Rm;q,k) and q> 1.

Then for z:= (s,~)E Qx Rm we obtain

LXR$ Ilzll2qd(Ax /,) =

L$ t.

^>.,

^J

^I^Si ¹²⁺^IIell²^2,^/,(d{)

::;t.

^Ai

^k.m

²^q^(M²^q ⁺1I~1I2q)J.L(~)

= 2^q(M²q+k) <^00.

For q> 1define a metric JonAx p(Rm;q,k) by

Then (A x p(Rm;q,k),J) is a metric space. We apply Theorem 1.4 to (T, d) = (A x p(Rm; q, k),J). Take M(t) = K, fixed. Denote the objective function by

Define an optimal value function <p:A x p(Rm;q, k) ^{- - - t} R and an optimal set function 'l/J:A x p(Rm ;q,k) ^{- - - t} K by

<p(A,J.L) = inf F(x,A,J.L),

xEK

'l/J(A,J-L) =^{x ^E ^K IF(x,A,J.L) =^<p(A,^J.L)}.

LEMMA 2.1. Let BeRn be a nonempty and compact set. Fix (A_{o '}J.Lo) E Ax p(Rm;q, k) and assume that 'l/J(Ao, J.Lo) ^is^nonempty^and bounded. Then there exist p E (0,1],LF > 0such that

for each x,Xo E B and each (A,J.l) E Ax p(Rm;q, k).

(8)

Proof. We have

IF(xo, >'0' J.Lo) - F(x,>.,J.L) I

s IF(xo, >'0' J.Lo) - F(x,>'0' J.Lo) I + IF(x,>'0' J.Lo) - F(x,>.,J.L) I

Sit

>'oi9i(Xo) -

t

>'oi9i(X)I+I

L_

^(Q(xô^{,e) -} ^Q(x,ê» ^J.Lo(de) Î

i=l i=l ^R=

r r

+IL >'oi9i(X) - L >'i9i(X) I

i=l i=l

+I

km

^Q(x,^e)^J.Lo(^{de) -}

fam

^Q(x,^e)^J.L(^de) ^I

Now let c= max{lIcllI,··· ,lIenll} then we have

r r r

IL >'oi9i(Xo) - L >'oi9i(X) IsL ^I^>'oi ¹¹9i(Xo) - 9i(X) I

i=l i=l i=l

r

SL>'oillezllll xo-x 11 i=l

se¹¹ ^Xo - xII,

by Cauchy-Schwarz inequality.

"Smce-"Q(x,·) ^is convexnix; q(x,·Jis""Lipscliitzian onB. Therefore

there exists some constant b>0 such that

Since B is bounded, there existsp> 0 withp= max{ 11 x III XEB}

and we have

r r r

IL >'oi9i(X) - L ^Ai9i(X) IsL I>'oi - Ai 11 ^9i(X) I

i=l i=l i=l

src 11 Ao - A1111 xII,

src11 Ao - >. 11 p

(9)

For the recourse part it is not hard to verify that for x E B, there exists· M >0 such that

IQ(x,e) - Q(x,{) I

~M·max{1I dll +¹¹ e-Dx 11,11 d11 + ¹¹ {-Dx II}·II e-{II

~M·^K·max{1I d 11 +¹¹ e¹¹ ⁺¹¹ ^D ^11,11 ^d ¹¹ ⁺^{11 {II} ⁺¹¹ ^D ^II}·II e-^{II,

whereK = max{l,p}.

Taking L(t) ⁼ M . K .(11 d 11 + ¹¹ D 11)+^{M . K . t,} there exists C > 0 such that for allfor q>1,we have

I r ^{Q(x, e)}^{P,o(de) -} r ^Q(x,e)^p,(de) ^I

lRTh lRTh

~C(l+^Mq(p,) +Mq(P,o))(3(p" P,0)1-i, where Mq(p,) = (lRTh L1(1Ie^ll)qp,(de))~, ^L1^(t) ⁼ ^{L(t)· t.}

Therefore

IF(xo, Ao' P,o) - F(x,A, p,) I~(c+b) 11 ^Xo - x 11 +rcp11 Ao - A¹¹ + C(l+Mq(p,) +Mq(P,o))(3(p" P,0)1-i

~LF(II ^X^{O -} xII +d«A,p,), (Ao,P,o))), where

Since for any fixed parameter(A,p,) problem (4) is a convex programming problem, local optimal solutions and local optimal values are global optimal solutions and global optimal values, respectively. We are now ready to deduce our main result:

THEOREM 2.2. Consider problem (4). Fix(Ao, P,o) Ê Âx^~(Rm;^q,k) and assume that1/;(Ao, P,o) îs^nonemptyând bounded. Then it follows that:

(a) For eache> 0 there existssome^1]>0 such that

(10)

whenever(>',p,) E Ax p(Rffl;q,k) andd((>',p,), (>'o,J.Lo)) <TJ.

(b) There exists positive reals 8cp and Lcp such that 7/J(>.,JL) -I0

I<p(>', JL) - <p(>'o, JLo) I:SLcp .d((>', J.L), (>'0' J.Lo)) , whenever(>.,p,) E A x peRm;q, k) andd((>', JL), (>'0' JLo)) <8cp.

Proof. We check the conditions of Theorem 1.4.

(Cl): Since7/J(>'0, J.Lo) is a global minimizing solution set, 7/J(>'0, JLo) isa eLM set. And since7/J(>'0, JLo) is bounded by assumption,7/J(>'0, JLo) is a bounded complete local minimizing set.

(02): M: A x peRm;q,k) ---) K, fixed valued. Then M is a constant multifunction. Therefore M is closed valued and closed on Ax peRm;q,k).

(C3) is trivially held.

(C4): This is proved in Lemma 2.1. The proof is complete. 0

References

[1] G. M. Cho, Stability of the multiple objective linear stochastic programming problems, Bull. of KMS 32 (1995), 287-296.

[2] Geoffrion A. M., Proper efficiency and the theory of vector maximization, J.

M. A. A. 22 (1968), 618-630.

[3] Klatte D., A note on quantitative stability results in nonlinear optimization, K.-Lommatzsch, 00., Proceedings of-l9;-Jahrestagung "Ma-thematische opti- mierung" Sellin/ GDR, seminarbericht Humboldt-Universitat (1987),77-86.

[4] ROmisch W. and Wakolbinger A., Obtaining convergence rates for approxima- tions in Stochastic programming, Bericht Nr. 308, Institute fur Mathematik, Johannes Kepler Universitat, Linz, 1986.

[5] Wets R. J. B.,Programming under uncertainty: The solution set, Siam J. Appl.

Math. 14 (1966).

[6] _ _ , Programming under uncertainty; the equivalent convex program, Siam J.Appl. Math. 14 (1966), 1143-1151.

[7] _ _ ,Stochastic programmings with fixed recourse: the equivalent determin- istic program, SIAM Review 16 (1974),309-339.

Department of Mathematics Dongseo University

Pusan 617-716, Korea

E-mail: [email protected]