SOME RESULTS CONCERNING AN APPLICATION OF THE QUANTILE OPTIMIZATION THEORY Andrei V.Naumov Department of Applied Mathematics Moscow Aviation Institute Moscow, 125080, Russia Technical Report 92-28 April, 1992. 1

SOME RESULTS CONCERNING AN APPLICATION OF THE QUANTILE OPTRIMIZATION THEORY ANDREI V.NAUMOV Department of Applied Mathematics, Moscow Aviation Institute, Moscow, Russia, 125080 (Revised on April 15, 1992) 1 Introduction. This presentation is devoted to stochastic optimization problems with criteria in the form of quantile function. I would like to consider two examples of quantile optimization theory application to water-supply system design problem and to nursing budget planning model. Some theoretical results concerning solutions of these problems will be cosidered too. To the recent time in the literature concerning stochastic programming, quantile optimization problems (QOP) were considered as a special case of probabilistic or chance constrained programming problems (CCPP). First papers in which QOP were investigated as independent class of stochastic programming problems, were published in late 70th - early 80th (for example, see [9]). Most powerful results in this area had been reflected in the monography of?Aalyshev and Kibzun [10], where, as a generalization of CCPP, QOP were considered in the following form: u, =arg min i(u), a E (0,1), (1.1) uEU 1

where U is a set of feasible solutions, a is a reliability (or confidence) level and ca:(u) is a quantile function of the following form: >(u) = min{p: P{w: I(u, w) <, Q(u, w) < 0}> a}, E H E 1, (1.2) where D(u, w) is a scalar function, which characterises a quality of our strategy u E fRn; w E?Rm is a random variable with given distribution function; Q(u, w) is a vector function of restrictions, and "P" means "probability". According to Prekopa's paper [13], under CCPP I mean problem in the following form: min 1(u) (1.3) subject to: P(q (u, w) < 0, q2(u, w) < O,..., qr(u, wW)< 0) > a hi(u) > bi,..., hm(u) > bm where q1(u, w),..., qr(u, w) are the elements of the vector function Q(u, w), and system of restrictions h1(u) > bi,..., hm(u) > bm describes the set of feasible solutions U. Indeed, problem (1.3) can be rewritten in the equivalent form of quantile optimization problem (1.1), where objective quantile function is: (I (u) = min{(: P{w: ' (u) < W; q (u, w) < 0,..., qr(u, w) < 0} > a}, (1.4) and the set of feasible solutions is U = {hl(u) < bi,..., hm(u) < bm}. Most powerful result of Malyshev, Kibzun's monography is the Generalised Minimax Approach (GMA). It establishes an equivalence between QOP (1.1) and the 2

following minimax problem: (Eac, a) = arg min [sup D(u,w)] (1.5) EEEa,UEU wEE subject to: q*(E, u) < Here, q*(E, u) = supwEE Q(u, w), Ea is a family of confidence sets with probability measure a. Let us define: I (E, u) = sup ((u, w). wEE Then, by definition, the equivalence between the problems (1.1) and (1.5) means, that i) I(E~ )) = (); ii) For every, E Ua,, there exist E, E E., subject to T(Ec,,uc,) = a(us,). Here Uc, is a set of all optimal solutions of the problem (1.1); iii) For every couple (E., Ui,), which is optimal in the problem (1.5), the following condition holds: T(Ea, ic,) = 4a(i,). Optimization with respect to confidence set E is a difficult operation in the problem (1.5), but the following proposition takes place: Proposition. For fixed confidence set E, an optimal solution (E, uE) of the problem (1.5), without optimization with respect to E, has a property: <Ia(Uut) <_ (E, uE). (1.6) 3

A quality of the upper bound i1(E, uE) essentially depends on a confidence set E selection, but in many cases we can obtain T(E,uE), which is close to the optimal value Ib(ua). I will illustrate this fact with an example. There are several reasons to survey and develop an application of the quantile optimization technique to economic models. The first one is, that according to Prekopa's paper [13], in general, methods for the solution of probabilistic constrained programming problems, which are often used to describe economic systems, ( even in the case of linear functions V1(u), qi(u, w), hj(u) ) are based on the application of suitable nonlinear programming solution technique, supplied by Monte Carlo simulation procedures to find values and gradients of probability functions. In many practically important cases, however, the confidence level a is interpreted as a system reliability, so a is close to unity. In this case, the procedure for calculating value and gradient of the probability function, using Monte Carlo simulation or multidimensional integration techniques, becomes complicated or loses precision. On the other hand, by transforming initial problem to minimization of auxiliary random variable distribution quantile function, we can use GMA to obtain an appropriate quality upper bound on the optimal value of the initial problem objective function. Moreover, in some cases it is possible to reduce initial problem to unconditional quantile optimization, i. e. quantile optimization problem without additional constraint Q(u, w) < 0. An algorithm for this reduction in the case of linear functions 4(u, w), Q(u, w), and polyhedral set U was presented in [6]. Such reduction allows us to use effectively stochastic quasi 4

gradient algorithms [4], [5], which were developed especially for quatile optimization in high reliability level systems. The second reason is that for some economic systems an application of quantile optimization models can be more adequate than CCPP, and it may be especially useful if we would like to make a decision with high confidence level. So, I would like to consider the following two examples of linear systems, and show how the quantile optimization technique can be applied to them. 2 Water-supply system design model. Let us consider a system for fresh water production in desert distant region, where fresh water sources are absent. Let h = (hl,..., h,) be a nonrandom vector of monthly water demands over n months and let u' = (u1,..., u,) be a nonrandom vector of monthly external supply plans. The internal water-supply system consists of a solar powered plant for water production with area S and cistern of volume V, where the remaining water is kept. The solar powered plant's productivity depends on monthly solar activity and can be expressed as a random vector w = (wl,...,w,). The probability distribution of random vector w is known. The total cost of the water-supply system is given by: n o = <(o(S, V, u') = alS + a2V + ao uj (2.1) j=1 where a1 is the cost per m2 of the solar powered plant; 5

a2 is the cost per m3 of the cistern; ao is the cost per m3 of externally delivered water. The surplus water at the end of jth month is expressed by: xj = min(xj_l, V) + Swj + uj - hj, o =, j = 1, n, (2.2) where min(xj_1, V) is water remaining from the previous month, which can not exceed the volume of the cistern. The system works normally if the following condition is satisfied: Xj >, j =,n. (2.3) Since equation (2.2) includes the random vector w, then satisfying (2.3) is a random event. The optimization problem is to find nonnegative system parameters S, V, and nonnegative external water supply parameter u, which minimize the objective function (2.1). The optimal parameters are: u* = arg min o(ii), (2.4) 5EU by given values of ao, al, a2, h and distribution w, subject to a probabilistic constraint: P(u) = P{w: minxj(ui,w) > 0} > c. (2.5) 1,n Here a E (0, 1) is the given system reliability and u E U = {(u1,..., u,, S, V): S > O V >0, u 0,U O, j=,n}. 6

Using (2.2) and (2.3), we can transform (2.5) to the probabilistic constraint of simultaneously satisfying of N = n * (n + 1)/2 bilinear inequalities, because every jth month we must add j inequalities to the previous inequality system. Let us explain this fact in an example over n=2 months. Then (2.5) is: Xl = wlS + ul - hi > 0 P w ' >_ a. (2.6) x2 = min (xl, V)+ w25 + U2 + - h2 > 0 In fact, this system of inequalities is equivalent to the probability of satisfying N = 3 inequalities of the following form: wlS + ul - hi > 0 P w: (w1 + w2)S + ui + 2 - h - h > O > >. (2.7) V + w2S +u2- h2 > 0 Hence, the problem (2.4),(2.5) is a stochastic program with a linear objective function and probabilistic constraints of satisfying N bilinear inequalities, and it can be solved using nonlinear programming solution technique [11], with Monte Carlo simulation procedure to find a value of the probability function (2.5). Let us reduce the problem (2.4), (2.5) to unconditional quantile minimization. First of all, let's show how to do this on the example over n = 2 months considered above. Then initial CCPP is: min (2.8) U1,U2,S,V subject to (2.7), u > 0, u2 >, S > 0, V > 0, and y = alS + a2V + ao(ul + u2) (2.9) 7

Let us express variable ul, using ~0, S, V, u2 from (2.9): Ul= (p - aiS - a2V - aoU2)/ao. (2.10) Let's- also define a new variable z = V - ~o/2a2. Then, after changing variables, we get the following problem: min Jp: P(u2, S, Z) ~ a}, U2,S,z (2.11) subject to u2 ~ 0, S > PW0(U2,Si z)=j w:j 0, where 4~1(U2, S, Z, w) = 2(al - aowi)S + 2a2Z + 2aoU2 + 2aoh1 4D2(U2, S, Z, W) = 2(al - ao(wil+ W2))S + 2a2Z + 2ao(hi + h2) (D3(U2, S, z, w) = -2a2W2S - 2a2Z - 2a2U2 + 2a2h2 4D4(U2i S z7 w) = -2a2Z ( 5 (U 2, S, Z, W) = 2ajS + 2a2Z + 2aou2 < o < (p < (p < (p < (p (2.12) Here, the consraints on the functions ~(D4.), V(D.5() are obtained from the restrictions u1 ~ 07 V> 0. Then by the definition (1.2): min{V: PU2 S, z) ~ a} = 4a(U2, Z, ~ (2.13) where Oa (U2, Z, S) is a quantile function of a distribution of the following random variable: 4D (U2z,ZS, W) = max C (U2, ZISiW).I So, the equivalent quantile optimization problem for this case is: mmn ~(u 2), u2 EU2 8 (2.14) (2.15)

where u2 E U2 = {(S,z, u2): S > 0, u2 _> 0}. By analogy, in general case (over n month) u E U = {(S, z,U2,...un): S > 0,Uj > O j = 2, n, (2.16) and (%a(u) is a quantile function of a distribution of the following random variable:,i() i(+ = sf,(w) + f,(Z, U2,..., n), i = N (u, W) = max_ $N+1(.) = -2a2z (2.17) i=l,N+2 ON+2(') = 2alS + 2a2z + 2ao?=2 uj. Here, ]f(') are linear functions, and fi(w) have the form: ki fi(w) = di - dt L wn, li < k, < n, i = 1, N, (2.18) m=li where df,dj,li,k; are some constants. Then initial optimization problem can be reduced to the following form of quantile optimization problem without additional probabilistic restrisctions: ua = arg min D,,(u), (2.19) UEU where U from (2.16). This problem is a bilinear quantile optimization. However, even not all linear CCPP can be reduced to unconditional quantile optimization. General algorithm for this reduction, which distinguishes a class of such problems, was considered in [6], and I will talk about it below in my presentation. 9

3 Two-stage quantile optimization problem for nursing workforce budget preparing. In modern literature concerning stochastic programming, there are a lot of publications devoted to two-stage stochastic programming problems with criteria in the form of mathematical expectation, but I don't know any papers, where such problems with first stage objective function in the form of quantile function were considered. There are some reasons for this. The first one is that more powerful results in the quantile optimization theory had been obtained only in the last several years. The second reason is that the nature of two-stage programming problems implice that we know a realization of the random variable ( usualy demand ) on the second stage of the problem. Hence, we can exactly satisfy second stage constraints ( if we will not consider a question of an existence a feasible solution of the second stage problem). So, CCPP could not be applied adequately to describe these systems. However, two-stage quantile optimization statement can be especially useful when we would like to estimate our possibility to satisfy, for example, workforce budget requirements with high confidence level. This estimate can be used, for instance, when we would like to make a decision about the begining of a new business. One attempt to apply probabilistic constrained programming models to two-stage system of energy network planning was undertaken in [14]. The objective function of the optimization problem considered in this paper is still in the form of mathematical 10

expectation, but author puts a probability restriction on the first stage of the problem to take into consideration the question of an existence of the second stage problem feasible solution. Here I would like to consider an example of application quantile optimization theory to nursing workforce butget preparation. Different models of this problem with criteria in the form of mathematical expectation were considered in [2]. Here I am going to consider a simple single period agregate probabilistic model. Let us denote: R - a number of regular-time nursing hours; 0 - a number of overtime nursing hours; A - a number of agency nursing hours; p - a fraction of the productive regular-time workforce available (0 < p < 1); r, 6, a - costs per hour of regular-time, overtime and agency nurse respectively; d - random demand in total nursing hours in considered period with given distribution function. A maximum available overtime workforce is bounded by factor g times the productive regular-time workforce. Then the considered problem can be formulated as a twostage stochastic optimization, where the second stage optimization problem is: I(R, d) = min O0 + aA (3.1) O,A 11

subjec to: O+ A+pR > d -0 > -gpR (3.2) A > 0;0 > 0 Here, an optimal value of the problem (3.1) objective function is a budget plan for overtime and agency nurse during cosidered period. Since D(R, d) depends on the random demand d, then 1>(R, d) is a random variable. Let us define a,(R) as a confidence level a quantile function of the random variable ~ (R, d) distribution, i.e. o(R) = min{': P{ (R, d) < ) >_ a}. (3.3) Then the first stage problem can be formulated as follows:, = minR(rR +,(R)) (3.4) s.t. R > O So, let us define the problem (3.1),(3.2),(3.4) as a two-stage quantile optimization problem, and 4a here is an estimate of a minimal value of the foundation, which is necessary to satisfy the random demand of total nursing hours in the considered period with given confidence level a. In the case of single period model, even an exact solution of the considered problem can be found, using GMA and linear programming solution techniques. 12

4 An algorithm for reduction linear CCPP to an equivalent unconditional QOP. Let us consider initial linear CCPP problem in the following form: ( = cTu -- min (4.1) u subject to: 0o(u) = P{w: Au + Bw < b} > a A1u < b1 where u is (nxl) vector of control variables; c, b, bl are accordingly (nxl), (mxl), (mixl) given deterministic vectors; w is (m2xl) random vector with given probability distribution; A, Al, B are given deterministic matrices of appropriate dimensions. Consider the general solution of the equation c = cTu. It can be written in the following form [1]: u = (c)+ + (I -(c)+cT)z, (4.2) where I is (nxn) identity matrix; z E R3 and (cT)+ is the pseudoinverse with respect to vector cT. The pseudoinverse (cT)+ can be defined [1] as a matrix (nxl), which satisfies the Penrose conditions [12]: (cT)+CT(CT)+ = (cT)+ CT(cT)+cT = cT (4.3) 13

cT(cT)+ and (cT)+cTare symmetric matrices. Then we can select (cT)+ as [8]: (CT)+ = Vc(cTVc)-, (4.4) where V is (nxn) matrix, which satisfies the following conditions: TVc $ 0 (4.5) VccT is symmetric. Let us write the conditions of the initial problem (4.1) using general solution (4.2): P{w: A(cT)+( + A(I - (cT)+cT)z + Bw < b} > a (4.6) A1(CT)+o + Al(I - (cT)+cT)z < b1 Our goal is to reduce (4.6) to the following form: P{w: A*z + B*w - b* < *} c a (4.7) A*z < b, where A* = (I, S..., ')T, (* E sm; A*, B*, b*, A1, b6 are deterministic matrices and vectors with corresponding dimensions: (m*xn),(m*xm2),(m*xl), (m;xn), (m;xl); m*, m1 are new dimensions. It is obvious, that according to this goal, it is sufficient to select matrix V in such a way, that every element of the column vector A(cT)+ becomes negative, every element of the column vector Ai(cT)+ becomes nonpositive, and matrix V satisfies (4.5). When some ith element of the column vector Ai(cT)+ is negative, we add: the corresponding row Ali.(I - (cT)+cT)/(Ai.(cT)+) to matrix A*, a row consisting of 14

zeroes to matrix B*, an element bl1/(Ali.(cT)+) to column vector b* and an element p to column vector p*. This allows us to obtain an equivalent system of restrictions in the form (4.7). Let us consider V as a matrix of n2 variables vij, i = l,n, j = l,n. Hence, by (4.4),(4.5),(4.6), for obtaining the required matrix V, it is nesessary to find feasible solution of one of the following systems of restrictions: Ai.Vc < -e, i = 1, m, TVc > e, (4.8) V.C.j =Vj.C.i, i,j 1,n, j i, Al1.Vc < O, i 1,Tm or Ai.Vc > e, i = l,m, cTVc< -e, (4.9) Vi.C.j =.,, i n, iv n j, Al.Vc > O, i = 1,m, where C = ccT. Both (4.8) and (4.9) are systems of linear inequalities and equations. To obtain nonstrong inequalities, we replace zero on the right side of the strong inequalities (4.8), (4.9) by a small parameter e, which has an absolute value close to zero. In this case, we can apply the first phase of the standard symplex method [11] to find feasible solutions of the restriction systems (4.8),(4.9). Hence, it was shown, that the following lemma holds: 15

Lemma 4.1 If there exists a feasible solution of at least one of the restriction systems (4.8),(4.9), then the initial problem's restriction system can be reduced to the form in (4.7). If we obtained the system of inequalities (4.7), then we can write initial optimization problem (4.1) in the following form: -- min (4.10) subject to: P{w: A*.z + b.w - b? <_ p, i = 1, m*} > a, Alz < bl. Problem (4.10) is an unconditional quantile minimization problem: 4,a(z) - min z (4.11) subject to: A*z < b, where!a(z) is a confidence level a quantile function of auxiliary random variable: i1(z, w) = max {A.z + B*.w - b}. i=l,m* (4.12) Lemma 4.1 selects some class of the initial optimization problems (4.1), which can be reduced to the form (4.11). 16

5 An improved guaranteeing solution algorithm. Let us define a general case of linear QOP in the following form: = _ 4<(u) - min (5.1) subject to: A*u < b* A1 1i, where 4i,(u) = min{p: P{A*u + B*w - b* < *; Au + Bw - b < 0} > a}, and =0* = ((p, i,..., f() E Rm. Here the control variable u has dimension (nxl); the random vector w has dimension (m2xl); vectors b, b*, b1 are accordingly (mxl),(m*xl),(m;xl) given vectors, and other matrices and vectors have corresponding dimensions. In spite of the problem (2.19) contains bilinear constraints, specific structure of this restrictions, when all linear functions fi(w) times on the same positive variable S, allows us to consider this problem as a particular case of the problem in general form (5.1). This question was discussed in details in [15]. Hence, the algorithm presented below can be applied to (2.19) too. Let us define the guaranteeing solution as a vector U,, which secures an upper bound?a on the optimal value of the problem (5.1) objective function. Assume also, for simplicity, that random vector w has normal distribution whith given parameters. Then according to GMA, the problem for obtaining the guaranteeing solution of (5.1) can be written in the following form: p -- min (5.2) u 17

subject to: maxwEaE Ai u + B.w - b? < cp, i = 1, m*, maxwEE, A1.u + B,.w - b < 0 =, I =, m, (5.3) A*u < b* Let us consider the confidence set E,, as a sphere Eoa centered at the mathematical expectation of the random vector w, and P(Eo,,) = a. Denote a radius of the confidence sphere Eoa as Ro. All functions in (5.3) are linear functions of the control variable u, and random vector w. Maximums in (5.3) with Eo0a instead of Eca can be found analytically. Suppose they are attained at the points w~ e Rm2 for i = l,m* and at the points w? E Rm2 for I= 1,m. Define the solution of (5.2),(5.3) as (uO, V), where u~i is an optimal value of the control variables, and Do~ is an optimal value of the objective function. Let us consider a new confidence sphere Eic, with radius R1 < Ro, then P(E1a) < ar. Consider also a solution of a new problem (5.2),(5.3) with El, instead of Eo,0 Define it (ul, t^D). Then the following set: B.*w < ~ +,-1 Au i = 1, m* C - w: (5.4) Bi.w < b - A.ut, i = A1, m has the property: E1 E C. Hence, P(C) > P(EIx). Lemma 5.1 If P(C) > a, then 1y is an upper bound on the quantile function optimal value of problem (5.1) and the following inequality holds: <. <_ ~. 18

The proof. of this lemma you can find in [6]. This lemma allows us to present the following algorithm to obtain an improved guaranteeing solution (u&,,4 ) of the problem (5.1): Step 0. k = 0. Set linear program (5.2),(5.3) solution Io as an upper bound on the I,(.). Step 1. Decrease with given decrement ha a radius of the confidence sphere Eka. Find a solution (U'+', $k+') of the linear programming problem (5.2),(5.3) with new confidence sphere instead of the Eka. Step 2. Check the inequality P(C) > a, where C is from (5.4) with (ui+1, $1). Step 3. If P(C) > a, then set k = k + 1 and continue the cycle from Step 1. Step 4. In the opposite case, we select the previous step's linear program solution, k, as an upper bound Ad on the optimum value of a,(.) in the problem (5.1) and set ua = A. The algorithm presented above allows us to obtain an upper bound on the optimal value of the objective function in the general problem (5.1). Moreover, when the initial CCPP can be reduced fo an unconditional quantile optimization problem in the form, for example (4.11), we propose to use the stochastic quasi gradient procedure for quantile function optimization [4],[5] to obtain an asymptotically exact solution. Let us define exact solution of the problem (4.11) as (Za, Va), then this procedure can be expressed in the following form: zk+l = pU(Zk _- k(Z)pk), z0 E U, (5.5) 19

where U = {z: Atz < b6}; pu(z) is a projector to the set U; pk is a k-th term of nonrandom sequence of step multipliers; k is the number of the procedure step. The quantile function 4a(Z) stochastic quasi gradient Ok(z) is the following random vector: 1 n Ok (Z) 2= k E [(1'..., Zj- + Pk,., Zn+l)- Q (Zi,..., Zj - /k,..., n+i]ej, (5.6) where /k is a nonrandom decreasing sequence term; n is the dimension of vector z; j, j = 1, n, are random variables, which have uniform distribution on [zj - 3k, Zj + /3k]; br(z) are independent quantile function estimates, obtained using a r sized sample of random variable 4)1(z, w); ej,j = 1, n, are basis vectors. To find the stochastic quasi gradient, Ok(Z), we propose to use the following statistics of the random variable <1l(z, w): t1 (Z=) [Ta] (5.7) 0c2(Z) = Tr - (T)r - Tr-_)(/ + ln(r) + ln(l - r)) where [ra] is the whole path of the ra value; D[,a] is the [ra]th term in the variational sequence of the random variable l1(z, w) sample, which have size r; D, -_1 are extreme right terms of the variational sequence; / is the Euler's constant. For the 4il(z) statistic, it is nesessary to use a sample size at least several times lager than Ta = [3-1] +1, and to build the empirical cumulative distribution function of the random variable 4l(z,w). On the other hand for;2 (z), it is sufficient to use the sample size r = Ta and we need only the extreme members of the sample to obtain this statistic. So,2(z) allows us to estimate high confidence level quantile 20

function using small size samples. Statistical properties of the estimates (3.10) were analyzed in [4],[7]. Conditions of the strong convergence of zk to z, are considered in [3],[5]. 6 Approach to the solution of nursing budget preparing problem. According to [9] for the function A,(R) from (3.3) the following equation holds: I,(R) = min max (R, d), (6.1) EEEa dEE where '1(R, d) is from (3.1); Ea is a family of confidence sets with probability measure a. For considered case of the single period model, E E R', i.e. E is confidence level a interval of the random variable d. Then we can consider the following problem to find value of the quantile function 4c(R): I,,(R) = min maxmin(50+ + aA) (6.2) EEEa dEE O,A subject to: O + A + pR > d -0 > -gpR (6.3) A > 0;O >0 By the fundamental duality theorem [11], if there exists a solution of the second stage programming problem (3.1),(3.2), then we can consider as equivalent a dual problem 21

for it and change the order of maximization in obtained problem: (I?(R) = min maxmax vl(d - pR) - v2gpR (6.4) EEEa vl,v2 dEE subject to l - v2 < vl <a V1 > 0; V2 > 0 where v, v2 are dual variables. Let us fix the confidence interval E, then maximum with respect to random variable d can be found analitically as a right side d* of the confidence interval E, because of the nonnegativety of the dual variable vl. Then for every R an upper bound on a,(R) can be found as a solution of the following problem: a (R) = max vl(d* - pR) - v2gpR (6.5) V1,V2 subject to vl - V2 < 6 vI < a Vi > 0; v2 ~ 0 If there exists a solution of initial problem, then using again the fundumental duality theorem we can obtain a problem to find a guaranteeing solution in the following form: = min rR + F (6.6) R,O,A 22

subject to 0o +aA = F O+ A +pR > d* -0 > -gpR A> 0;O > 0;R >0 where 4F is an upper bound on the minimal value AI. In this simple case of single period model, we can even find an exact solution of the initial problem. The confidence set E is an interval in R1, so it can be parametrised by the parameter d E '1, which is the right side bound of this interval. By nonnegativety of dual variable v1, maximum with respect to d in the problem (6.4) is attained at d, i.e. d* = d. Hence, by the structure of the objective function and va > 0, the optimal confidence interval has a minimal right side bound, i.e d* is a confidence level a quantile of the random variable d distribution. So, an optimal solution of initial problem can be found using standard simplex method to solve linear programming problem (6.6). Considered problem was solved for the confidence level a = 0.99. Initial data for this problem was: r = 4.9556; o = 6.7591; a = 8.7877; g = 0.2. The factor of the productive regular-time workforce available was: p = 0.8828. Random demand in nursing hours had normal distribution with mathemetical expectation dl = 12414, and variance d2 = 1666. Optimal solution of the problem (6.6) in this case is quite obvious. The demand can be satisfied using only a regular-time nurse, because of a cheapest cost factor. So the 23

solution is: optimal value of the control variable R = 19723.6067, optimal value of the objective function, i.e. minimum value of the foundation, which is necessory to satisfy demand with given confidence level, <* = 97742.3054. However, in the case of multiperiod model, the solution is not so obvious, and developing of the algorithm to solve this problem seems to be an interesting topic for future investigation. 7 Numerical results concerning water-supply model. Considered water-supply system design problem was solved over n = 6 months for two reliability levels: a = 0.99 and ac = 0.999. Initial data for this problem are: al = 3.75[unit/m2]; a2 = 10[unit/m3]; ao = 25[unit/m3]. The object water demand per month: h = [29.6; 0.0001; 23.9; 36.2; 82.1; 173.4]. We approximate the distribution of the random vector w by a normal distribution with the following parameters: Mt = [0.00837; 0.00828; 0.0185; 0.0631; 0.123; 0.137] at = [0.000582; 0.000552; 0.00123; 0.00421; 0.00818; 0.00916]. Random variables wj, j = 1,6, are independent. We choose a short system life for obtaining compact results, that are convenient for analysis. The results are sensitive to the ao, a1, a2, Mt, Ot parameters relations. We omit the sensitivity analysis of this problem here. It is more important that this 24

example reflects correlations between the guaranteeing and asymptotic exact solution of this problem, and the process of improving the guaranteeing solution using the guaranteeing solution algorithm. Results of the guaranteeing and asymptotically exact solutions are given with the accuracy 0.01 for a = 0.99 and ac = 0.999 in Table 1. Table 1. Guaranteeing and Asymptotic Exact Solutions Guaranteeing solution Asymptotic exact solution GS AES abs( GS-AES ) a I 0.99 0.999 0.99 0.999 0.99 0.999 (p 4905.96 4995.02 4879.05 4973.78 26.91 21.24 S 1000.19 1017.03 1001.29 1017.22 1.1 0.19 V 61.33 63.21 59.14 61.11 2.19 2.1 wl 22.48 22.61 22.06 22.76 0.42 0.15 W2 0. 0. 0. 0. 0. 0. W3. 0. 0. 0. 0. 0. W4 O. 0. 0. 0. 0. 0. }5 0. 0. 0. 0. 0. 0. ~w 0. 0. 0. 0. 0. 0. The process of improving the guaranteeing solution for a = 0.99, using the algorithm from the section 4, is reflected in the Table 2. Table 2. Improving of the guaranteeing solution. I r Guaranteeing solution P(C) 4.093 5189.61 0.9998 3.693 5100.92 0.9996 3.293 5015.09 0.9993 2.893 4931.99 0.9937 2.700 4905.96 0.9901 I The probability of the set C was calculated using a Monte Carlo simulation procedure with sample size 10000. Before solving this problem, we transformed it into a problem, 25

in which the random vector w has a standard normal distribution. So, r in the Table 2 is the radius of the confidence sphere for a standard normal vector (N(0, I)). We start the guaranteeing solution algorithm from the confidence sphere Ca (a = 0.99) with the radius r = 4.093. From Table 2, we see that in this case, using the guaranteeing solution algorithm, we can improve the standard guaranteeing solution (5189.61) by approximately 6 percent. Table 1 shows, that for the given conditions, the optimal water supply system satisfies demand by using fresh water produced by the solar powered plant. Only in the first month, when the plant productivity is small, do we need to use an external water supply. This fact can also be explained by the small capital cost of solar powered plant construction in this model example. Table 1 illustrates, that, with increasing a, the guaranteeing solution tends to the asymptotically exact solution. This fact allows us to use effectively the guaranteeing solution algorithm by itself, and also to accelerate convergence of stochastic quasigradient methods using the guaranteeing solution as a good start point. 8 Conclusion and open problems. In conclusion I hope, that considered models show that quantile optimization methods can be successfully applied to different kinds of economic systems, especially if we need 26

to make a decision with high confidence level. Algorithm for reduction of some class of linear CCPP considered in the presentation allows us to apply quantile optimization methods to such problems too. Presented guaranteeing solution algorithm can be used effectively to improve an upper bound on the optimal value of the objective function in considered problems. Further improvement can be attained by application of stochastic quasi gradient procedures for asymptotically exact solution in quantile optimization systems. By example of nursing workforce budget planning problem it was shown, that in some cases quantile optimization models allow us to describe system more adequately than CCPP. To compare the results of calculation for this problem with the solution of the same problem, but with a criteria in the form of mathematical expectation, we can see essensual difference between obtained estimates. So, estimate obtained by using mathematical expectation criterion [2] may be very optimistic in some cases, and comparison of these two solutions can give additional useful information to make a final decision. Numerical results concerning water-supply model show, that improved upper bound is close to asymptotically exact solution, and can be used as a good approximation and also as a good start point for stochastic quasi gradient algorithm to improve its convergence. All this results lead us to develop research in this area and to find a solution for 27

problems, that are still open. Some of these problems are: i) To extend obtained results to the linear-quadratic case; ii) To find necessary and maybe sufficient conditions of confidence set optimality in linear QOP; iii) To investigate convexity of quantile criteria in two-stage linear QOP and a question of solution existence for such problems; iiii) To extend obtained results to multi-stage linear QOP (multiperiod case). References. 1. A.Albert, Regression and the Moore-Penrose Pseudoinverse (Academic Press, New York, 1972). 2. E.P.C.Kao and M.Queyranne, "Budgeting costs of nursing in a hospital," Management Science, v 31, 5, 1985. 3. A.I.Kibzun, "Probabilistic optimization problems," Department of Industrial and Operations Engineering, Technical report 91-34, University of Michigan, Ann Arbor, 1991. 4. A.I.Kibzun and V.Yu.Kurbakovskiy, "Guaranteeing approach to solving quantile optimization problems," Anals of Oper. Res., v30, 1991. 5. A.I.Kibzun and V.Yu.Kurbakovskiy, "Numerical methods for runway space minimization under random disturbances," Izvestia Academii Nauk USSR, Tekhnicheskaya Kibernetika, 1, 1991. 6. A.I.Kibzun and A.V.Naumov, "Applying quantile optimization technique to some 28

class of probabilistic constrained programming problems," Department of Industrial and Operations Engineering, Technical report 92-14, University of Michigan, Ann Arbor, 1992. 7. V.Yu.Kurbakovsky, "Accelerate method for high confidence level quantile estimating," in collection of works VNIISI: Nonhomogeneous system dynamic, vol 14 -VNIISI, Moscow,(1989) (in Russian) 8. R.S.Liptser and A.N.Shiryayev, Statisties of random processes 2 Applications (Springer-Verlag, New York, 1978.) 9. V.V.Malyshev and A.I.Kibzun, "Generalised Minimax Approach to stochastic programming problems," in proceedings of the International Conference on Stochastic Programming: Kiev, USSR, 1984. 10. V.V.Malyshev and A.I.Kibzun, Analysis and synthesis of aircrafts high accuracy control (Mashinostroenie, Moscow, 1987), (in Russian) 11. K.G.Murty, Linear programming (Wiley Sons, 1983). 12. R.Penrose, "A generalized inverse for matrices," Proc. Cambridge Philos. Soc. 52, 1956. 13. A.Prekopa, "Numerical solution of probabilistic constrained programming problems," in: Yu.Ermoliev and R.J.B.Wets, ed., Numerical techniques for stochastic optimization (Springer-Verlag, 1987). 14. A.Prekopa, "Network planning using two-stage programming under uncertainty," in: P.Kall and A.Prekopa, ed., Recents results in stochastic programming, proceedings 29

(Springer-Verlag, 1980). 15. A.I.Kibzun and A.V.Naumov, "Quantile optimization technique with application to chance constrained programming problem for water-supply system design," Department of Industrial and Operations Engineering, Technical report 92-5, University of Michigan, Ann Arbor, 1992. 30