APPLYING THE QUANTILE OPTIMIZATION METHODS TO WATER-SUPPLY SYSTEM DESIGN Andrei V.N-umov Department of Industrial and Operations Engineering University of Michigan Ann Arbor, Mi 48109 Vitali Yu.Kurbakovsky Department of Applied Mathematics Moscow Aviation Institute Moscow, 127080, USSR Bairam M.Muradov Institute of Sun Ashchabad, 744032, Turkmenia. Technical Report 91-29 November, 1991. ~ t t $,,'. t:'ft,; 4;i, ^, r t...,' i,'if.. / *?',/?:'/.'1, / ~*'

APPLYING THE QUANTILE OPTIMIZATION METHODS TO WATER-SUPPLY SYSTEM DESIGN Andrei V.Naumov Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109 and Vitali Yu.Kurbakovsky Department of Applied Mathematics Moscow Aviation Institute Moscow, 127080, USSR and Bairam M.Muradov Institute of Sun Ashchabad, 744032, Turkmenia. ( Revised on October 28, 1991.) Abstract In this paper we consider an optimimization problem in water supply systems. This problem can be formulated as a minimization with probabilistic constraints. We present a nontraditional approach for the solution of this problem using quantile optimization algorithms. It may be practically useful, because the confidence level of probabilistic constraints is closed to unity, and it is difficult to use other gradient methods [1],[5],[8]. We present a method to obtain a guaranteeing solution of this 1

problem based on the Generalized Minimax Approach [4] and a sequence of linear program solutions. We show how to use stochastic quasi-gradient algorithms for quantile function optimization [2],[3] in this case. Numerical results are also discussed. Keywords: optimization problem, probabilistic constraints, quantile optimization algorithm, guaranteeing solution, stochastic quasi-gradient algorithm. 1 Introduction. Optimization in water-supply systems often arises in the design of distant solar powered plant for fresh water production when fresh water sources are absent. The model considers stochastic deviation of the solar plant power and the possibility of monthly external fresh water supplies. The objective function of this problem is the sum of the capital cost of solar powered plant constraction and the cost of external water supplies. We consider the probability of complete satisfaction of the demands to be restricted. Similar problems were considered in [1],[6],[7],[8]. In general, previous methods for such problems are based on efficient probability function calculation and different kind of gradient methods using. However these methods are inefficient for solution of the problem under consideration, because their computational reguirements depend on the probabilistic constraints confidence level a approximatly as ~. A(1)2 [4]. We 2

consider the problem, where a is interpreted as the reliability of the system, and so a is close to unity. Our approach is based on transforming the initial problem to an equivalent unconditional quantile optimization problem. It is a specific convolution of a nonrandom objective function and probabilistic constraints. Our method for the equivalent problem uses known numerical algorithms [2],[3], which are suited to deal with high confidence level quantile functions. We also consider a guaranteeing solution method, i.e. a method for obtaining an upper bound on the optimal value of the objective function. In fact that the upper bound tends to an exact optimal value of objective function as a increases [4]. So guaranteeing solution is a good initial condition for the stochastic quasi-gradient method [3]. A combination of these methods can be effectively used for the original problem solution. 2 Problem statesment. Let h = (h,..., h,) be a nonrandom vector of monthly water demends over n months and w = (w,..., w,) 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(m2) and cistern of volume V(m3) for keeping monthly water overflow. The solar powered plant's productivity depends on monthly solar activity and can be expressed as a random vector t = (t1,..., tn). The probability distribution of random vector t is known with support SR. The total cost of the water-supply system is given 3

by: n ( =,(S,V,w) = aS+bV+q w, (2.1) j=1 where a is the cost per m2 of solar powered plant; b is cost per m3 of cistern; q is cost per m3 of externally delivered water. The surplus water at the end of ith month is expressed by: xj = xj-1 + Stj + wj - hj xO =O j = l,n (2.2) Xj-1 = min(xj_l, V) where xj-1 is water remainder from previous month, which can not exceed the volume of the cistern. The system works normally if the following condition is satisfied: mminxj > 0 (2.3) j=1,n Since equation (2.2) includes the random vector t, then holding (2.3) is random event. The optimization problem is to find nonnegative system parameters 5, V and nonnegative external water supply parameter w, which minimizes the objective function (2.1). The optimal parameters are: (S* V* w) = arg min (S, V, w) (2.4) S,V,uw by given values of a, b, q, h and distribution t, subject to probabilistic constraint: P(S, V, w) P{t: minxj(t) } a (2. 5) l,n 4

Here a E (0, 1) is the given system reliability. Using (2.2) and(2.3) we can transform (2.5) to the probabilistic constraint of simultaneously holding of N = n * (n + 1)/2 bilinear inequalities, because every ith month we must add i inequalities to the previous inequality system. Problem (2.4),(2.5) is a stochastic program with a nonrandom objective function and probabilistic constraints. 3 Reduction to a quantile optimization problem. Let us reduce the problem (2.4),(2.5) to a quantile optimization problem. This means that we must optimize a confidence level a quantile function for some auxiliary random variable distribution. This allows us to use effective numerical algorithms for high confidence level quantile function minimization. Let us express variable w1 using (S, V, ) and (wj, j = 2,n) from (2.1). Define a new variable z = V - (/2. After changing variables, the probability constraint (2.5) can be reduced to the following form: P{t: Fi(S, z, W2,... Wt) < i =1, N} > a (3.1) where functions Fi have the structure: Fi() Sfi(t) + fi(z, W2,..., w,). (3.2) Here, fi(*) are linear functions, and fi(t) have the form: ki fi(t) tm li< k < n i=,N (3.3) m=li 5

Define value (,(S, z, w2,..., Wn) as the minimal value of 1I when constraints (3.1) hold. <{(a) is the confidence level ac quantile function of random variable F's distribution, where F = F(S,z,w2,...,wn,t) = maxi{Fi(.)}. Define u = (S,z,w2,...,Wn). Then the initial problem can be reduced to the following form: u, = arg min a (u) (3.4) subject to: u E U = {u: S> 0;V> 0;wj > j =,n} 4 Guaranteeing solution algorithm. The quantile optimization problem (3.4) is computationally difficult, because the quantile function 4a(u) can not be expressed analytically. First we consider an algorithm for obtaining a guaranteeing solution of this problem. We use the Generalized Minimax Approach [4] to rewrite problem (3.4) as: (ua,Ea) = arg min max F(u, t) (4.1) UEU, EaEEa tEEac where E, is the class of confidence sets whith probability measure a. Denote B as the Borel a- field on the disturbance space. Then E, E B. Choosing an optimum set Ea EQ E is a difficult operation. However if we want to find a guaranteeing solution, we can replace Ea by some initial approximation Eo E E Ea. For standard Gaussian random disturbances it is convenient to select Eo as a sphere C, [4]. The center of 6

C, is the mathematical expectation point of the random vector t and P(C,) = a. In this case then the radius of Ca, can be obtained analytically. Then the function: 0,(u) = max F(u, t) (4.2) tECa will be a majorant of the quantile function c,(u) (3.4), i.e.: c (u)< c,(u) Vu E U (4.3) Given u E U and (4.2), 4ca(u) is the minimal value 4X, that satisfies all of the inequalities: max Fi(u,t) < J i = 1,N (4.4) tECa For every i = 1, N, the maximum in (4.4) is attained at the point t' E Rn, which is a tangency point of the hyperplane fi(t) = const and sphere Ca and can be found analytically. Hence, for calculating the guaranteeing solution, it is sufficient to solve the following linear programming problem: ut = arg min D (4.5) uEU subject to linear constraints: Fi(u, t?) < (< i =1,N (4.6) This problem can be solved by the standard simplex algorithm. Suppose that the guaranteeing solution (u,,,a) is discovered. Then the set of all vectors t satisfying following inequalities: Fi(u,t) _< i-1,N (4.7) 7

is a polyhedral set: C = {t: fi(t) < ci(Oa, u) i = 1,N} (4.8) where $D - f(~)i c O(4u0Ia) = = 1,N (4.9) S and u~ = (, 2,.., Wn). By construction of t, the polyhedron fi(t) < f(t) i = 1,N (4.10) is circumscribed around sphere Ca. By (4.10),(4.6) and that S > 0, all t which satisfy (4.10) belong to C. Hence Ca E C, and P(C) > a, because polyhedron (4.10) circumscribed the sphere Ca. Let us consider a new confidence sphere Cal with a radius R.i < Ro, where Ra is the radius of Ca. It is obvious that P(Cai) < a. Choose at the sphere Cal points t,* by analogy with the selection of t'. Now, consider problem (4.5) subject to: Fi(u,t*) < t i = 1,N (4.11) Let (u,, C:) be a solution to this problem. Denote: C* {t: f(t) ci($;, u) i-=, N} (4.12) where the structure of ci(.) is described in (4.9). 8

Lemma 4.1 If P(C*) > a, then $D is an upper bound of the quantile function optimal value of problem (3.4) and the following inequality holds: D _< <a,. Proof of the Lemma 4.1 see in Appendix A. This Lemma allows us to present the following algorithm for obtaining an improved upper bound of the I,(*): Step 1. We find a solution (uA, (a) of the linear programming problem (4.5),(4.6), where tt i = 1, N are selected on confidence sphere C, with probability measure a, and the t? maximize F(.-) (3.2). Step 2. Using a numerical simulation algorithm, we check inequality P(C) > a, where C is from (4.8). Step 3. If P(C) > a, we decrease the confidence sphere radius with the given increment h, and continue the cycle from Step 1. Step 4. In the opposite case, we select the previous step's linear program solution, a(-), as an upper bound on the optimum value of 4a(-) in problem (3.4) and set Uc = Uc,. 5 Stochastic quasi-gradient algorithm. As mentioned above, the quantile function can not be analyticaly expressed in this problem. This complicates obtaining an exact solution. We propose algorithms, wlkich are based on the idea of using stochastic quasi-gradient vector of (a( ). Let us 9

consider possible ways of getting quantile function statistical estimates. Using these estimates we can calculate a stochastic quasi-gradient vector. Denote an independent sample of random vector t values as {tk}k=l and {Fk4=. to be an ordered collection of function F(u,tk) values: F1 < F2 <... < FT, i.e. a variational sequence. Then the confidence level ca quantile function Da(u) of random variable F(u, t) distribution can be estimated by the following statistic: D,(u) = F[ra], = [ (5.1) where [Tra] is the integer path of the ra value. Estimate (5.1) is fF- consistent and I' (u) is also an asymptotically effective estimate. However, when we deal with a high confidence level quantile function, it is difficult to use this estimate, because in this case the sample size must be more then T, = [(1-1)], and process of the variational sequence tracing becomes very complicated. In this case we prefer to use another estimation procedure, based on an asymptotic propety of extremal order statistics F1, F,1, i.e. extreme right terms of the variational sequence: 4)(U) = Fr -(F - F.-1)(/ + ln(r) + ln(1 - r)) (5.2) where r < [(1 )]. Estimate (5.2) allows us to estimate high confidence level quantile function using small size samples. Moreover, we need only extreme members of the sample. Statistical propeties of estimates (5.1),(5.2) were analyzed in [2],[3], where the fitness of these estimates for using in stochastic quasi-gradient algorithms for quantile function minimization was shown. 10

Let us define a quantile function stochastic quasi-gradient as a random vector: (u) = 2 T [c(il,, u, +,..., ) - b(il,., ~ - I,..., ur]ei (5.3) iP3,=1 where p3s is a nonrandom decreasing sequence term; r is the dimention of vector u; ui i = 1, r are random variables, which have uniform distribution on [uis -3, ui+,3]; s (u) are independent quantile function estimates (5.1),(5.2); e, i = 1 r are basis vectors. The stochastic quasi-gradient procedure for quantile function minimization is: u+1 = pu(uS - q(u)p8) u~ E U (5.4) where pu(u) is projector to the set U; p, is a nonrandom sequence of step multipliers; s is the number of the procedure step. Conditions of strong convergence of us to uc are considered in [3]. As an initial condition u~ for procedure (5.4) we take Ua, the guaranteeing solution obtained in Section 4. 6 Numerical example. The considered problem is a system with n = 6 months. Two reliability levels, a = 0.99 and ac = 0.999 are considered. Initial data for this problem are: a = 3.75[unit/m2]; b = 10[unit/m3]; q = 25[unit/m3]. The object water demand per month: h = [29.6; 0.0001; 23.9; 36.2; 82.1; 173.4]. 11

We suppose, that the random vector t has normal distribution with parameters: Et = [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 tj j = 1,6 are independent. This problem is model one. We choose short system life for obtaining results convenient for analysis. The results essentially depend on the a,q,Et,at parameters relations. We omit the description of computational aspects of this problem. It is more important that this example reflects correlations between guaranteeing and stochastic quasi-gradient approaches. Results of the guaranteeing and asymptotically exact solutions are given for a = 0.99 and a, = 0.999 in Table 1. Results are given with accuracy two significant figure after point. Table 1.: Numerical Example Solutions Guaranteeing solution Asymptotic exact solution GS AES abs( GS-AES ) var. a = 0.99 al = 0.999 a = 0.99 al = 0.999 a = 0.99 1 = 0.999 (I 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 wi 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 0. 0. 0. 0. 0. 0. W5 0. 0. 0. 0. 0. 0. w6 0. 0. 0. 0. 0. 0. From the table, we see that for the given conditions the optimal water supply 12

system satisfies demand by using fresh water produced by the solar powered plant. Only in the first month, when plant productivity is small, does the optimal solution uses an external water supply. This fact can be explained also by the small capital cost of solar powered plant construction. With increasing a, the guaranteeing solution tends to the asymtotically exact solution. This fact allows us effectively to use the guaranteeing solution algorithm itself, and also to accelerate convergence of stochstic quasi-gradient methods using guaranteeing solution as a good start point. 7 Conclusion. Choosing optimal water supply system structure is a typical optimization problem with probabilistic constraints. We present a nontraditional algorithm for this problem solution, reducing it to a quantile optimization problem. This approach allows us to avoid the main lack of solution procedures for optimization problems with probabilistic constraints. Algorithms traditionally used suffer increasing computational difficulties and decreasing precision when the confidence level a increases. We considered the guaranteeing solution algorithm for obtaining successively improving upper bounds on the objective function value. This algorithm can be reduced to the sequential solution of linear programming problems. The computational requirements depend of the confidence level a only by checking the condition P(C) > a under each iteration of the algorithm, where C is polyhedral set of random vector t. However, 13

we can regulate the number of iterations by choosing the negative increment of the confidence sphere radius. On the other hand, under increasing of a, the guaranteeing solution tends to the exact one. Thus we can obtain a good approximation of the exact solution and find a good starting condition for the stochastic quasi-gradient method. Moreover, the computational complecity of the considered stochastic quasi-gradient method (o(l1~)) increases more slowly than previous methods (o((1_j))) So the combination of the two presented methods is an effective algorithm for solving the cosidered problems. Appendix A Proof. of Lemma 4.1 1. Consider set C* (4.12) as a confidence set instad of Ca. Then inequalities (4.6) are: (D* - f'(~\iW) a S + f,(u~) < i = 1,N (7.1) where u~ = (z, w2,..., w). It is obvious, that (7.1) holds for the solution (Uc, 4a). Hence (,u, 4) is a feasiable solution for problem (4.5),(4.6), where t? i = 1,N are selected on the confidence A A 1 set C*. It follows from the condition of the lemma, that P(C*) > a. Therefore,,, is an upper bound on the objective function optimal value in the problem (3.4) [4]. 14

2. Functions fi(') (3.3) are linear combinations of tj j = 1,n with nonnegative coefficients. By Ra > Rat, and the fact that vector Et consists of positive elements, the following inequalities hold: fi(tt*) < fi(t) i = 1,N (7.2) In fact, (U., ha) is the solution of the problem (4.5),(4.6). So by (3.2),(7.2) and S > O, inequalities Fi(iuI,t*) _<D a i=1,N (7.3) also hold. Hence, ( D&, Ia) is a feasible solution for problem (4.5),(4.11), where the t,* are selected on the cofidence set C,1. However (Ua, Ax) is the optimal solution of this problem. Therefore, (D < (0a. This completes the proof of this Lemma. Acknowledgements - The authors are indebted to Prof Andrei I.Kibzun for suggested scheme of guaranteeing solution improving and many helpful discussions. REFERENCES [1] U.M.Ermoliev,Stochastic optimization methods, Nauka, Moscow, 1976 (in Russian) [2] A.I.Kibzun, V.U.Kurbakovsky, "Numerical methods for runway space minimization under random disturbances",in Izv. AN USSR, Technic. Kibern., 1 (1991) (in Russian) [3] V.U.Kurbakovsky, "Accelerate method for high confidence level quantile esti15

mating", in collection of works VNIISI: Nonhomogeneous system dynamic, vol 14- VNIISI, Moscow, 1989 (in Russian) [4] V.V.Malyshev, A.I.Kibzun, Analysis and synthesis of aircrafts high accuracy control, Mashinostroenie, Moscow, 1987, (in Russian) [5] J.Mayer, " Probabilistic constrained programming: redused gradient algorithm implemented on PC", International institute for applyed system analasis, A 23-61, Laxenburg, Austria, May 1988. [6] A.Prekopa, " On probabilistic constrained programming", in: Proceedings of the Princeton symposium on Mathematical Programming, Princeton University Press, Princeton, New York, 1970,pp 113-138. [7] A.Prekopa, S.Ganezer, I.Deak and K.Patyi,"The STABIL Stochastic Programming Model and its Experimental Application to the Electrical Energy Sector of Hungarian Economy", in: Stochastic programming, Proceeding of the International Conference of Stochastic Programming, Oxford, England,1974, (edited by M.A.N. Dempster), Academic Press, 1980,pp 369-385. [8] S.P.Uriasiev, Adaptive algorithms for stochastic optimization theory and game theory, Nauka, Moscow, 1990 (in Russian) 16