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