PROBABILISTIC OPTIMIZATION PROBLEMS ANDREI I. KIBZUN Moscow Aviation Institute USSR Technical Report 91-34 November 1991

THE UNIVERSITY OF MICHIGAN Andrei I. Kibzun, Professor, Moscow Aviation Institute, USSR Lecture # 1 Probabilistic Optimization Problems Introduction The lecture is devoted to stochastic optimization problems with criteria in the form of probability (in my lectures later I will refer to these problems as probabilistic problems). The author has developed a confidence approach for solving such problems. First of all, let me describe schematically the place taken by this method among the well-known methods. For this purpose I would like to offer the following classification of optimization problems in presence of uncontrollable factors, though somebody can find it arguable. In statistics usually the Bayesian and minimax approaches are usually applied separately for estimating the unknown parameter. According to the minimax approach this parameter is assumed to be uncertain, and the a priori information about it is assumed to be given in the form of a range of uncertainty According to the Bayesian approach, the parameter is assumed to be random and its distribution is assumed to be known. Similar approaches have also been considered in control and filtering theories. Please note that the stochastic and minimax theories corresponding to these approaches have been developing independently as a rule. That is why, I think, the mathematical apparatuses of these theories don't match each other. I would like to stress that, in my opinion, using one approach or the other is a matter of faith rather then a matter of truth Supporters of the minimax theory just like atomists in philosoph\ try to split a problem "building bricks" without providing for any chance. They say God does not play dice. Another group ni scientists think to the contrary opinion. They say thatt everything in our world is so interrelated and diverse that t ht

only way out is to stochastically describe the various phenomena around us. To cut a long story short the situation reminds me the long dispute between idealists and materialists. I hope you will excuse me for such a free interpretation of these approaches. But some scientists, for example Germeyer (USSR) in his monograph, criticize this contrasting the minimax approach with the stochastic one. By the way, Wald's theory of statistical solutions can exemplify a good unity of these approaches. According to this theory, optimization problems were considered with regard to random and uncertain factors, with the maximum of averaged loss function as the optimality criterion. Similar minimax-stochastic problems have also been examined by Kurzhanskii, Ermoliev, Eliasberg (USSR), Loose, Poor, and Vastola (USA). I would like to call your attention to the fact that these scientists have examined only a formal combination of the minimax approach and the stochastic one. A good deal of effort has been devoted to overcoming the difficulties resulting from the lack of agreement between different mathematical apparatuses of the minimax theory and the stochastic one. While noting the doubtless usefulness of these scientists' works, I'd like to stress the fact that a symbiosis of the stochastic and minimax theories has been used when stating and solving minimax-stochastic problems. These works have failed to take into account the existing relationship between stochastic and minimax problems, although the following fact could have suggested this idea. Equations of the Kalman filter are true for a linear system both at Gaussian random interference and at uncertain interference from an uncertainty set in the form of an ellipsoid. Now I would like to express the main idea of my research. I think that in the near future new results in the field of optimization with uncontrollable factors should be looked for in the vertical axis, as the figure shows, by revealing links between the minimax and stochastic theories as well as the theory of fuzzy sets, rather than in the horizontal plane, that is. within separate theories. In this case a search for linking bridges between those theories will become very important. Those bridges will help carry the results from one theory into the - 2 -

other. Today I would like to tell you about my modest attempt to construct such a bridge. This bridge is constructed for stochastic problems with criterion in the form of an objective function quantile or, in short, with quantile criterion. Why do we consider these particular criteria? For the last twenty years I have been studying the problems of analysis and synthesis of the algorithms of high-precision control and estimation, as well as the problem of using the obtained results in aviation and astronautics. In 1987 a monograph devoted to these problems was published in the USSR which was written by myself in collaboration with Professor Malyshev. High precision of object position estimation as well as of its motion control is one of the main requirements when designing modern motion control systems. To provide the necessary precision one has to take into account different uncontrollable factors (random, uncertain, and fuzzy) when designing algorithms of estimation and control. Generally, we first consider random factors acting upon an object when it is functioning. For example, when one controls an aircraft, he has to take into consideration atmospheric disturbances (deviations of the atmospheric density or wind gusts), errors of working through control impulses, and deviations of geometric, aerodynamic, and other vehicle characteristics. The necessity of considering these factors influences the problem statement. Consider, for example, a terminal control problem of a certain hypothetical aircraft. The aim for this aircraft is to reach the given destination with minimal fuel consumption. It can be seen that the formulated problem can only be discussed in a probabilistic sense. Thus, it is natural to choose as the optimality criterion the minimal fuel capacity necessary to keep the probability of reaching the goal above a given value. Therefore we must choose an optimal control strategy guaranteeing that the terminal requirements will be met with the given probability. This situation appears in the majority of control problems. Many probabilistic control quality characteristics such as the probability of a successful landing, the probability of two vehicles rendezvous have become traditional. -3 -

In aircraft control problems one wants to know the probability of landing successfully. The information that the control system can land the aircraft "in an average" manner is not satisfactory, because one understands that his particular landing can be unsuccessful as 99 following landings. Some other examples of probabilistic control quality criteria can be found in the economic applications. Consider the following example, which is referenced to as the "stock-exchange paradox". Lets suppose one is going to buy some shares of stock and there are only two different types of stocks available. Let zl be the initial amount of money one is going to invest in the stocks, w i and wi2 be the profits gained in i-th year for the first and the second type of stock respectively. The vectors w.=col(w l,w 2) are independent and they have the same distribution for any i. Let ul and u2 be the fractions of the amount of money one is going to spend on the shares of the first and the second type respectively, ul + u2 = 1. Then the total amount of money after year N will be N ZN+1 = zI T1 (l+uwi+U2w2) i=l The expectation of the total amount will be a criterion of our investment efficiency 4(U1, u2) = M [ZN+I(U, u2, w11, w12,..., wN1, wN2)]= N = z1 TI (l+ulm1+u2m2) i= 1 where ml= M[wi ], m2= M[wi2].Then, it is obvious that the optimal strategy will be to invest only in the stock that gives the maximal profit, i.e. if m < m2 then u~=O, u0=1 ~1 2 '1 2 if mi> m2 then u0=1, u2=O When using this strategy our criterion is N (u, u~) = II (zl+ max{m, m2}) - 1 i=l t N oo The paradox is that this strategy leads to a probability of ruin -4 -

[P zN+1 - 1 Thus, it is not sensible to use the expectation as a criterion in this particular case. One can use quantile criterion to avoid this paradox. Nevertheless, I think that until recently inadequate attention has been paid to probabilistically stated control problems. Apparently, it can be explained by the complexities of taking into consideration probabilistic criteria in comparison with classic characteristics such as mathematical expectation and root-mean-square deviation. Also, there is a lack of methods for solving this type of problems. However, some research has been done in this field, though in a rather uncoordinated manner. In this lecture I will try to analyze the previous experience in this area. I will begin with classification. Classification of Problems According to the type of probabilistic criterion, problems can be divided into three large classes: direct problems, inverse problems, and problems with chance constraints. According to the type of object to be controlled, probabilistic optimization problems as well as other optimization problems can be divided into static ones and dynamic ones. The problems, in which the object to be controlled is described by systems of static relations such as equations or inequalities, are called static. If in this case a set of feasible controls is finite-dimensional space, the static probabilistic problems are actually the probabilistically stated problems of mathematical programming. There are problems where an object under control is described by a system of differential and finite-differential equations. I will refer to them as dynamic probabilistic problems. Though, formally, dynamic problems can be reduced to static ones with an objective function written by the dynamic relation, this division is still useful in practice. The dynamic object state control and estimation problems, when probabilistically stated, can be the examples of dynamic probabilistic problems. In this lecture I will devote most of my - 5 -

attention to static probabilistic problems. Now I will turn to a formal description of probabilistic problems. Let an arbitrary probabilistic space (Q,, P) be given, where 2 is a space of elementary events w, ~ is a o-algebra of subsets from Q, P is a probabilistic measure of subsets from 5. Either random variables, random processes, or random fields can play the role of w. In these cases the space 2 and probabilistic measure P are to be determined in accordance with the type of random factor. The most frequent is the case when realizations w are vector of finite - dimensional space Q2 = R", is a Borel cr-algebra, and a probabilistic measure is given by the probability density p(x). Assume that certain functionals >(u,w) and Q(u,w) are given that characterize the quality of strategies u E U selected from the set of feasible strategies U. In the future, to simplify the designations, we will use the symbol w for random factors as well as for its particular realization if it will not lead to misunderstanding. When the static problems considered, the functionals 4(u,w) and Q(u,w) are given in an explicit form, and when the dynamic problems are considered, the functionals 1 and Q are given in form of integrals, differential or difference equations. Parameters and functions can play the role of a strategy in static problems. Programmed control, positional control( the control law), and an algorithm of estimating can play this role in dynamic problems. The set U of feasible strategies gives not only the type of strategies mentioned above, but it also shows technical constraints imposed on the values of u. For example, the values of programmed control can be restricted by the constraint I u(t) | " 1 for all t E [O,T] and the function u(t) can be assumed piecewise-continuous. Let us assume, in future, that t he functionals t(u,w) and Q(u,w) are measurable with respect to A for each strategy u E U. This assumption is satisfied in the majority of practical problems and gives us an opportunity to consider the following probability functional P(u) AP( Su ={ w: (u,w) -< q, Q(u,w) < 0)}!1 where qp is a certain parameter. The probability Pd I, characterizes such an event that the functional Z(u,w) will rl(! - 6 -

exceed the threshold ip, and Q(u,w) will not be positive. Usually, in technical problems there are some demands which one has to satisfy in the first place. The constraint Q(u,w) ' 0 plays the role of these demands in this case. The fulfillment of the other constraints can be less categorical. At last, one can increase the threshold qp to satisfy the constraint Q(u,w) ' 0. For example, the functional t(u,w) can characterize the consumption of the control resource, and Q(u,w) can characterize the control precision, or vice-versa, depending on the control goal. The considered functional can be interpreted as a convolution of two criteria. In these terms, a direct probabilistic problem can be formulated as follows. One has to select a strategy uL as to maximize the probability functional P (u): uq = arg max P (u), qp E R1. (2) By analogy, an inverse probabilistic problem consists of choosing such a strategy ua as to minimize the quantile functional oa(u): ua arg min ta(u), a E (0,1) (3) uEU where by definition the quantile functional ta(u) is a minimal threshold qp guaranteed with a probability a: a(u) A min {o: P,(u) ' a}. (4) Note that a direct probabilistic problem of optimization can be reduced to a stochastic problem with the optimality criterion in the form of mathematical expectation uM- arg max M [X(S )] (5) uEU SX' u if we introduce a characteristic function X(S,u) of the set S, u which is equal to zero when w ~ Su and which is equal to unity when w E S. However, methods of optimization of mathematical expectation greatly depend on smoothness of functionals that are under the- sign of mathematical expectations. This property is not present in this case due to discontinuity of the function X. That is why direct problems require a special study. The quantile statement (3) can not be reduced, in principle, to the expectation problem (5). This happens since in order to calculate the quantile functional a((u), one has to minimize the parameter - 7 -

(p, and, moreover, calculate the functional Pq(u) for every fixed (p. A number of works consider a series of functionals Pi(u) = P{w: Qi(u,w) - 0}, i=ln and demand that each functional be not lower than a certain given threshold: Pj(u) > a. (the so-called per-line-chance-constraints) A certain deterministic function O0(u) is a quality criterion of the strategy u in this case. Such statements are called problems with chance constraints. One has to stress again that problems with chance constraints are a special case of inverse problems with a quantile criterion. Indeed, if in problem (3) the objective functional D(u,w)=Io(u), i.e. it does not depend on a random vector w, we arrive at a problem of minimizing the functional O (u) under the constraint P {w: Q(u,w) - 0} > a. And vice versa, if we consider the generalized strategy u = (u,t), then the problem of minimizing qp with the constraint P (u) > a is a problem with chance constraint u0 = arg min (p (u), Pa(u) > a u The problem with a chance constraint sometimes can be reduced to the quantile problem without the additional constraint Q(u,w) ' 0. In many practical cases, we can obtain this by a change of variables. Such an example will be given in the third lecture. Now we will discuss a simple example of a problem with a chance constraint. (o(u1, u2) -> min u\u2 IP{-o + u1 + w1 < 0, u1 + u2 = w2 < 0} > a. We can change the variable 2 = U2 -. Then the problem will become to(u1, u2) - min_, u2 P{u1 + wI < po, u1 + u2 = W2 ' t } = -8 -

P{max[ul + w1, U + u2 = w2] < o} > a. We can say that we now have the quantile optimization problem a(u1 2) min- U U 1, 2 where ~O(u1 U2) = o(U, U2) with an a-level quantile of random variable distribution O(U1, u2' W1, w2) = max[u1 + wl, u1 + u2 w2] It seems to me that the problem with chance constraints is more difficult than the quantile optimization problem, which is an ordinary unconditional optimization problem. Let's consider one more problem statement. The functionals 1(u,w,z) and Q(u,w,z) will now depend on the parameter z with the values from some space E. Let's fix u E U and consider all the values z such that Z, (u) A {z: Pa(u,z) > a. It is obvious that if Z(p, (ul) Zp, a(u2), then the strategy u1 is better than the strategy u2. Therefore, we can use the information about the size of Z1, (u) to make conclusions about the efficiency of strategy u. The set Zp (u) is called the set of absorption of a-level for strategy u E U. The maximal a-level set of absorption is pa= U U (pu ) Vr0'a. uEU The actual purpose of the absorption set Z1 is to determine the set of values of z for which it is possible to find a strategy u guaranteeing the fulfillment of a probabilistic constraint P { w: $(u, w, z) ---, Q(u, w, z) ' O} ' a. At the end of this section let us consider minimax-probabilistic problems of optimization, in which there are simultaneously random and uncertain factors. For example, an objective functional c(u,w,')) can also depend on an uncertain -9 -

factor r/EH. Then, one can consider the following functional instead of probability functional such as (1) PH(u) = inf P(u). (O prTH (p A strategy that maximizes a probability functional when there is the worst disturbance 7, is considered as an optimal strategy uH in this case. Such problems can be called maximin - probabilistic ones. Stochastic differential games in which a random factor makes a differential game more complicated, are considered to belong to a class of problems like that. In addition to the method mentioned above, there can be another combination of random and uncertain factors. Let a probability measure P be given from some family II. In this case, the quality of the strategies can be characterized by the functional P$(u) = inf P(u). A situation when there is a game of two players in mixed strategies, is also possible. In this case, a payoff function will depend on two strategies p and q, which are random factors for which a probability functional P (Fp,F ) can be calculated, and distributions of these strategies F and F will play the P q role of strategies u and v. Thus one arrives at the problem of optimizing a functional: Po(Fp) = F fE Pp(Fp Fq) q Direct Methods for Solving Probabilistic Problems Let us consider two main approaches to solving probabilistic problems, which unite the groups of direct and indirect methods. Methods which are based on the direct calculations of the functionals Pq(u) and a((u) can be considered as direct methods. For example, in the finite-dimensional case, it is sometimes possible to calculate integrals analytically, or the numerical procedure for calculating them is comparatively simpler. Let's consider the statistical simulation method which is usually used for the numeric calculation of statistical - 10 -

characteristics which can't be calculated analytically. When using this method, the functionals Pq,(u) and (a(u) are calculated for every feasible strategy u E U, and then the known methods of deterministic optimization, for example, nonlinear programming methods, are used in the case when U c Rm. Let's consider the details of using statistical simulation methods for calculating the functional a = P%(u) = P{S I,u}, where Su = w: (u,w) ' qp, Q(u,w) - O}. The method which is used for the estimation of probability P{SS u} is based upon the Muavre-LaPlace theorem, which states that the frequency Wn of a random event S u in n trials, as a random variable, is asymptotically Normal as n tends to infinity. Let the trials be independent and the probability of event S u in any trial be equal to a. Then we can obtain the lower bound for the probability a. This lower bound is guaranteed with probability 3 as can be seen in the equation below. W W - a PW Wn /. =l~' P / = - V a(1-a) =) In this equation p is the confidence probability (secondary with respect to a). In this equation it is assumed that the number of trials is fixed, but in actual problems one wants to find the number of trials which insures that the frequency Wn is close to the probability a being estimated. If we solve this equation with respect to u then we obtain [2n + p2(1-a)-lp p4n(l-a)+p2(1-a)2 n = [S+1 min where [.] is the whole part of the number, ns is the number of successful trials in a series of n trials, and Wn is ns divided by n. In this equation the guaranteeing number of trials depends on the confidence probability 3 (or p) and on the number oi successful trials ns. The function nmin (ns) is a step function and can be plotted as follows (Fig. 1) (for a = 0.999. 13 = 0.9999). If in m trials we get the point which is under the curve, then the actual probability P(A) is greater than or equLtl - 11 -

=o0.999; 8=0.9999 n-n s 5 4- 3 - i 2 10000 20000 Fig. 1 (m,m-m5) 30000 n I to a, and this statement is true with confidence probability 3. It can be seen on the plot that if ns is equal to n (all of the trials are successful), then fifteen thousand successful trials must be performed in a row. If there is one unsuccessful trial, then n increases considerable to hundreds of thousands. Why does the number of required trials n increase considerably when the number of successful trials n grows? Let us consider a simple example. Suppose random variable 4(u,w) has a normal distribution, then the density plot p(p) looks as presented on Fig. 2. From the plot you can see that the quantile 4o for distribution D(u,w) is the right bound of figure which has an area equal to a. Suppose that the area is calculated numerically, and the error of this calculation is e=0.01, the necessary probability level a=O.99. In this case it can happen A that the quantile estimate (ca equals to infinity. This situation happens due to so called asymptotic unstability of quantile 1o in parameter a. If it is necessary to integrate differentiable equations to obtain the result in each trial, as is the case in the estimation - 12 -

of the probability of successful landings, then the number of calculations will be extremely high. The other disadvantage of this procedure is the difficulty of setting the confidence probability level 3. For example, in an actual problem one may evaluate a probability a = 0.999 with a confidence probability i3 equal to 0.9. However, the number of necessary trials nmin considerably depends on the confidence probability level P. In addition, the Muavre-LaPlace theorem states that frequency only has a Normal distribution when n tends to infinity, but for finite n this is not true, and we have to define a new confidence probability (which is tertiary with respect to a). It is possible to use another method to combine the statistical simulation method with the search optimization method. These methods must be used in parallel, and not consecutively. The group of methods that are constructed in this way is called the stochastic approximation methods. It is not necessary to perform many trials series of the computer simulation for each step of the optimal strategy search. Only one - 13 -

series is necessary because it is combined with the strategy search. This is the main advantage of this group of methods. The rate of convergence for these algorithms is usually higher than the rate of convergence for optimization methods with the statistical simulation. The main difficulty in designing such a method is in determining the convergency condition. One algorithm from this group, the stochastic quasigradient algorithm, will be discussed in the third lecture. REFERENCES 1. Kibzun, A.I. and V.V.Malyshev problems. - Izv. AN SSSR. Teknicheskaya (in Russian). 2. Yudin, D.B. Mathematical methods o of incomplete information. - Moscow Russian). Optimization probabilistic Kibernetika, N 6, 1989. f control under conditions i, Sov. Radio, 1974. (in - 14 -

THE U N IV ER S I T Y OF MICHIGAN Andrei I. Kibzun, Professor, Moscow Aviation Institute, USSR Lecture # 2 Indirect Methods for Probabilistic Problem Solving In the previous lecture, I discussed several direct methods which are being used for probabilistic problem solving. In addition to these methods, I will now consider four indirect methods for probabilistic problem solving. I will apply them to quantile optimization problem solving, though they can also be used for solving other probabilistic problems. 1. The Mean-Square Method A lot of results have been obtained in the theory of stochastic optimization which are based on the mean-square optimality criteria. Therefore, it is only too natural to use these results in order to solve probabilistic problems. The Mean-square method is based on the Chebyshev's inequality. To make the method clear, let's assume for the simplicity that there is no the constraint Q(u, co)O, and a functional 4(u,co) has the form )(u,w)-= I0(u,w)-A0(u). Consider a mean-square criterion M(u)M [o(u,)-O(u)]2 instead of a quantile functional According to the Chebyshev's inequality;hie has

P{(: |to(U W)-Xo(U)|:]) 1 } M(U)/ 2 if Ao(u) A M[(u,w)]. As the following inequality is true, P (u)= 1 - P{o: I|o(u,t)-ho(u) )|' } - 1 -M(u)/2 the probability functional PP((u) is indirectly maximized when the mean-square criterion Da(u) is minimized in uEU. The quantile functional is estimated similarly. Note that a mean-square strategy differs greatly from strategies ua and u(,p because the Chebyshev's inequality gives a rather rough estimate, especially when the values of a and PPa(u) approach the unity. Note also that a mean-square strategy uM does not depend on parameters qp and a, which are present in the probabilistic problems. This fact stresses its roughness. However, in some cases the mean-square strategy is a good approximation and sometimes coincides with ua and uL. This is true when u and qp are vectors, the density p(x) of a random vector X has a symmetric form p(x) - f I Ix-mWI, the objective function may be expressed as follows: 'I(u,w) A g[llAo + Bul I. functions f(.),. g(.) are continuous and strictly monotonous. 2. The Deterministic Equivalent Method The deterministic equivalent method was historically the first proposed indirect method. According to this method, probabilistic constraint Po(u) > a, which is an inequality, i, replaced by the equality constraint P{o:,(u,.)-9 s gl(u), Q(u,o) ' g2(u)} = a, -2 -

and then the vectors gl(u)<O and g2(u)0O are searched for. This method is discussed thoroughly in many references, and thus I will not discuss it in my lecture. 3. The Minimax Method The main idea of the minimax method is the following: let's fix an arbitrary confidence set E from the elementary event space Q. The confidence set E is the set with probability measure greater than or equal to a, i.e. P(E) > a. Such sets form the whole family of sets Ea { E: P(E) o } Now I will assume that an uncontrollable factor X is not random but an uncertain factor with the uncertainty set E., i.e. w E E (wo belongs to E). The control strategy u E U (from set U) will be considered fixed. Let's examine the maximum functional: I (E,u) = sup 1 (u,to) W E and try to solve the minimax problem (assuming that Q(u,w)=O ): uE = arg min n (E,u), ~o f inf 4 (E,u), uEU uEU where uE and pE are the minimax control strategy and the minimax value of functional }(u, C). Is this minimax problem connected with original quantile problem? For simplicity I shall assume that Q(u,w)= 0 and that solutions to these problems exist. The answer is "yes". This connection is established in the following theorem. THEOREM 1. The pair (uE, oE) is a guaranteed solution for the quantile problem -3 -

=Pa 4 a (ua) < ac (uE) ' I (EuE) a_ pE' E E E, where Pa = inf (a(u), a e (0, 1) uEU a = arg min a(u) uEU Proof. Let E E Ea, a E (0, 1) and the pairs (ua, Pa), (uE, oE) (the solutions in quantile and minimax problems) exist. Consider a set S(P SpE pE { )o: (uE,) (- P = { c: D (uE, ) < sup m(uE,c) }, SE u E = because pE=I(E,uE) = sup(uE,w). Thus the set SE E contains the WEE (p,u set E. Thus, the probability P E (uE) A P (S E E) ' P(E) > a, <r Up, u E and so P E(UE) ac. Remember, that the definition of quantile is: t~(UE) - min {: P (uE) a } The inequality P E(UE) ' a, therefore implies that x(uE)S E. The strategy uE is not necessarily optimal for the E minimization of quantile functional a((u), and so ta(ua)<- &uE). After combining all the above inequalities we will get the necessary statement of the theorem. * Thus, the minimax methods give the possibility to find solution for the quantile optimization problem. The upper estimation pE> (Pa is true for any confidence set E from the family of sets [Ea (E E Ela). But, if we use not the best E from Ea, then, first of all, the upper estimate obtained will be too rough, and secondly, it can be more difficult to obtain the F4. - 4 -

solution of the minimax problem than the solution of the original quantile problem. 4. The Generalized Minimax Method. The possibility to obtain the quantile estimation through solving a minimax problem is demonstrated by the generalized minimax method (pa= inf inf sup 1 (u,co). EEEa uEU cE The main idea is that we can choose such a confidence set Ect E[,, that the quantile estimation will be equal to the real EX value of quantile po = p. This confidence set E is called an optimal one. This problem is interpreted in terms of two-person-zero-sum-game theory in the following way. The second player (ow E, which is nature) seeks to maximize the damage caused to the first player knowing the first player's strategy and his own opportunities, which are defined by the set E. The first player, without knowing the second player strategy, seeks to minimize his losses by choosing his own strategy and worsening the second player's opportunities. This is achieved by choosing the best confidence set E, i.e. the second player's opportunities. This problem is the problem with dependent variables, and it is known that this type of problem is unstable in criterion. That is why the initial stochastic problem can be solved only with a high consumption of time necessary for many numerical calculations. The most difficult step in the obtained problem is to find the optimal confidence set E. We will discuss the generalized minimax approach before discussing the ways oi - 5 -

choosing the set Ed. At first, I shall give some definitions. I will say that the minimax problem is equivalent to the quantile problem if the strategy u exists and the following three conditions are satisfied: 1. 4(t, Uc) = (a(u); 2. For any ua 3 Ea such that I(Ea, ua) = Da(ua); 3. For any pair (Ea,ua) it is true that (Eatux) = a((ua), where ua is an optimal strategy in the quantile problem, ('E,'u) is an optimal pair in the generalized minimax problem. THEOREM 2. The quantile problem is equivalent to the generalized minimax problem. Proof. Let the strategy ua exist, and so qpa= Ic(Ua). The definition of quantile is a(u) - min { op: Pu(ua) ' a } Consider the probability functional of optimal strategy ua: PP((ua) = P {o: (uaw):5 {} Now let us designate E= {to: (ua,) s pa} and consider the maximum functional (toaU u =) sup s(ua ) = ',a c q(Ua) w Et Thus, the second condition of problem equivalency is satisfied. Now consider the pair (tEi'U) which is optimal for the generalized minimax problem. I will use the minimax estimates obtained in the previous part of this lecture. - 6 -

P _ (U) 5 ( U a) < ^~,Ea uu - a As the second property is already proved, I can use it to find out that (po = 4(Ea,ua). The pair (E, u'a), as you remember, is optimal in the generalized minimax problem. That is why the last inequality is consistent only if it is a strict equality. And this means that the conditions 1 and 3 of problem equivalency are satisfied and, thus the quantile problem is equivalent to the generalized minimax problem. m The equivalency proved above is a base for the confidence approach. At the end of this part I will give the formula for building the confidence absorbed set in the case when the function 4(u,w,z) depends not only on u and on w, but on z. Z = U U n Zul), aO EEE uEU WEE ( where 1 o(u,W) { z: z (u, W,z) (pq } This formula is equivalent to the generalized minimax problem in which the search for an upper bound is substituted by the intersection of sets and minimization is substituted by the union of sets. This formula is deduced in the same way as the generalized minimax problem. 5. Bilateral estimates for quantile functional Now I shall consider the additional opportunities which the confidence approach gives us when it is used forrp quant i e problem solving. First of all, using this approach it is possible to obtain bilateral estimates for a quantile functional -7 -

Subject to the different conditions, it is possible to obtain the estimations, which will be given below in Lemmas 1, 2, 3, and 4. Lemma 1. If the function I(u,Co) is continuous (both in u and in o) and quasi-convex in ) E [R" for all uEU, probability measure P and Lebesque measure are mutually absolutely continuous, and the confidence set E~Ea is compact, then P.(E, u) -A inf (u, o) < (u) < *(E,u) A sup (uW), a<wEaE WE E where 9E is the boundary of set E, and the quasi-convex function 4(u,Co) is the function for which the Lebesque set S(i u {:.(uo) < p }is convex for all o. The estimates presented are the base for the numeric procedure of the confidence set transformation. These transformations of the confidence set E are aimed to make it as n close to optimal set as possible. When using this procedure, in correspondence with the generalized minimax method it is possible to obtain that the estimates ~.(En ) au) — (u, >u*(E.u) — > (u), n - oo n -> oo i.e. the upper and lower estimates are coming close while the probability measure of set E remains the same at the every n-step of procedure. Now let's define the a-order kernel of measure P. The a-order kernel of measure P is the set Sa n Eaa which is the S f a,W a II =1 intersection of all possible confidence half-spaces Eaa {: a wo b(a) }, lall = 1, where parameter b(a) is chosen to provide P(Ea, )=a. Note that the set Sa belongs to all convex confidence sets E with - 8 -

probability measure a. Lemma 2. Let the objective function I(u,co) be continuous and quasi-convex in w EIRn for all uEU, the Probability measure P and Lebesque measure are mutually absolutely continuous, a-(0.5;1), and optimal strategy u exist in the quantile problem. There is the following quantile estimation for the kernel So: SO A l* (Soc u) *(S, Uo) = sup <(ua, ) -< ( * S Thus, the value P*(Scau ) is the lower estimation for the minimal quantile po. Lemma 3. Let the objective function 4(u,cw) be continuous and quasi-convex in o E IRn for all uEU, and confidence set E be a convex polyhedron. Then oa(U) -5 max (u,w) = P*(E,u), W(EJ(E) where J(E) is the set of all vertexes of the polyhedron E. In this case one has to look over all the vertexes of polyhedron E in order to find out the value of the maximum function P(E,u). And if the function 4(u,c), in addition to the conditions mentioned above, is convex and piece wise linear in u, then maximum function P(E,u) will also be piece-wise linear in u. If, besides that, the set of feasible strategies U is a convex polyhedron, then the minimax problem can be reduced to a linear programming problem. In this case, one can easily obtain the upper estimation of a quantile po (p E, while the solution of a quantile problem is very difficult. Now let's consider the deviation of' the set E from the set -9 -

E, i.e. d(E,E) A su inf 11 -o211. wl~ \E W EE 1 r 2 Lemma 4. Let the objective function I(u,cw) be continuous and quasi-convex in w E R"n for all uEU and also satisfy the Lipschitz type condition, i.e. I(u, w1) - <(u,tw2)l k II wc- w211I for any w1, t2 such that llolll >R, 11w211 >R, Il - o211 <6, where k,y,R,6 >0. Let the probability measure is a Gaussian measure corresponding to the standard normal distribution with zero expectation and the unit matrix of covariances, confidence set E be a sphere E with radius r, P(Er)= a. Then under the assumptions mentioned above the following estimates are valid: E E E (p r= P(Eu r) > P > (Eu r) - kd'(E,E), and moreover, E (Er'u r) - (P - 0 as a - 1. This lemma states that when a is increasing, the lower and the upper quantile estimates tend to each other. It means that E when a is close enough to 1, the minimax estimate tp r becomes very close to quantile pt and is still an upper estimation. It is interesting that the minimax estimate is more precise when probability level a is higher, and the complexity of the solution does not depend on a. It is not correct when one uses the statistical simulation method or the mean-square method, because their errors increase as a increases. The usefulness of the estimates obtained will be demonstrated in the third lecture when designing the 2nd and the 3rd algorithms for quantile function minimization. - 10 -

Remark. The proofs of lemmas presented above can be found in the book: V. V. Malyshev, A. I. Kibzun. REFERENCES 1. Yudin, D.B. Mathematical methods of control under conditions of incomplete information. - Moscow, Sov. Radio, 1974. (in Russian). 2. Malyshev, V.V. and A.I.Kibzun Analysis and Synthesis of High Precision Aircraft Control. - Moscow, Mashinostroenie, 1987. (in Russian) - 11 -

TH E UNIVERSITY OF MICHIGAN Andrei I. Kibzun, Professor, Moscow Aviation Institute, USSR Lecture #3 Three Algorithms for Quantile Function Minimization The methods for solving probabilistic problems which were considered in the previous two lectures give us the opportunity to begin the design of algorithms for solving them. Three algorithms will be discussed. The first one is based on the direct method; the second and the third ones are based on the confidence method. Two examples which show the particularities of these algorithms will be given. 1. The Direct Algorithm. At first, I will consider an algorithm based on the direct method. let the following conditions hold: A) The objective function 4(u,c) depends monotonically on a quasi-convex function t(u) for any o and is continuous in uEU and CO; B) The random vector co has the Standard Normal distribution N(O,I); C) The set U of feasible strategies is compact in IRm. Now I impose no constraints on the dependence of the objective function $(u,co) on 0) except continuity. These requirements will be set below after introducing some new constraints. Under the giver assumption, the quantile of the objective function will be continuous and quasi-convex function in u. Suppose for any u it is possible to obtain the sample oi values {t(u,. i)}t j of function Z(u, ), where {Oi)t art} independent realizations of the random vector o. Let's designate them as {Di(u)}t1 the ordered series of the sample, i.e. t th i=l

values of the objective function D(u,.) arranged in increasing order. Under the assumptions made above, the random variable D(u, o) has a continuous cumulative distribution for any uEU. According to the Central Limit Theorem, the middle terms of the ordered series can be represented as t tends to infinity as: ~[at],+l(U)0~(u)+ p (1oc( U) where [aot] is a whole part of the value a-t, aE(O,1); v is a random variable with Standard Normal probability density; pU(0p) is a probability density function for the random function D(u,w); $ (u) is an a-level quantile of it's distribution. From the representation above it follows, that the statistic JtOu) - r0t]+l(U) are asymptotically unbiased and v - consistent estimate of the quantile 4a(u) for any uEU. Moreover, the bias of the estimate zt(u) A I|(u) - M[lt(u)]I has an order o(l/t) uniformly on any compact set U, i.e. there exists a constant c<oo which doesn't depend on t such that Zt(u) -< for any uEU. The estimate Tt(u) turns out to be suitable when working with high order quantiles (a>0.99). That is why the necessary sample size cannot be less than Tc =[[-]+l. Otherwise the estimate is insensitive to variations of a. Moreover, since the asymptotic representation is valid only for middle terms, it is necessary for the extreme terms to be in mean greater than the value of the minimal quantile. And it means that the sample size has to be at least several times more than Ta. In addition, every time one is going to get the quantile estimate, he has to build the empirical cumulative distribution function for random variable ((u,o). Let's consider the estimate of the other type which is based on the use of asymptotic properties of extremal order statistics, i.e. the" largest terms of the ordered series of sample {i.(u)}tit-k' k<<t. Just as the distribution of the middle terms of the ordered series can be found (and is Normal), the limiting external order statistics distribution can also be found in some cases (but it is not Normal). In particular, for the most well known distributions of the random variable D (for example, the -2 -

Normal distribution, Exponential distribution, Gamma-distribution etc.) the asymptotical behavior of extremal order statistics obeys the law: F((p) = exp(-exp(-p)), (pR1 In this case the random variable 1 is a random variable of the exponential type. Totally there exists three types of limiting distributions for the extremal statistics, but the exponential type is the most common one. I will assume later that in addition to condition A the condition A' also holds: A') The nature of dependence D(u,c) on o is such that the random variable (u,Cw) is a random variable of the exponential type for any uEU. The knowledge of these laws gives us the opportunity to calculate the estimate of the quantile function using the sample with the size less than or equal to T. in a relatively simple manner. Let's consider the estimate wt (u) t(u) - lst(u)-_wt_ou )] where 1t(u) and It_l(u) are the last two terms of the ordered series of the sample of the size t>l, g=0.5772 is the Euler constant. Lemma 1. If a random variable <(u,o) is of the exponential type for any uEU, then the error of the quantile estimate zt(u) |I M [>t(u)] - Za(u) I = o(l/t) is of order o(l/t) uniformly in uEU. Here t=[ ---]+1. Thus, the statistic It(u) calculated using a sample of the size t can be used as a quantile estimate, and moreover its bias zt(u) will be less as the quantile order a tends to one. It should be noted that the obtained estimate <t(u) is considerably simpler than the previous Tt(u) since when taking the sample it is necessary to remember only the two worst realizations to calculate the estimate <t(u). On the other hand, when calculating the estimate vt(u), it is necessary to remember them and put the whole sample in order. This is a difficult problem when the sample size is considerable. The simplicity of the mentioned above estimate gives us the opportunity to use it in stochastic recurrent procedures in which it is necessary to estimate the quantile function repeatedly for several values of u. - 3 -

The random vector t will be called the stochastic quasigradient of the quantile function - m ^ ^ EJ(ua)=- [t(iut... ui+a,... n)t( u1,,u - m)] i=l where ui are independent random variables uniformly distributed upon segments [ui-a,ui+a], e. - are unit co-ordinate vectors, i=l, m, a is a smoothing constant. Consider the stochastic quasigradient algorithm for quantile function minimization. k uk 1=n,(u'-p,~, (u, ak)),uO E U where IIU is an operator which projects a vector from space Rm on its subset U. Theorem 1.Let all the conditions mentioned above A, A', B, C hold. Moreover, let the parameters of algorithm obey with the following conditions: 2 E Pk= o, E (Pk)2o I E(Pk)/(a tk) <oo k=1 k=1 k=l k ak e ~ ' tk - o, v e, Pk >, ak > 0 k k a —T Opk >0 k k Then all of the limit points of sequence of the stochastic quasigradient algorithm vectors uk, with probability 1 belong to a set of extremal points of the quantile function. The algorithm described above belongs to a class of stochastic approximation algorithms that are similar to the algorithm of the projective gradient which is used for the minimization of deterministic functions. In the stochastic quasigradient algorithm the quasigradient Jt(u,a) plays the role of a gradient. The quasigradient is in mean turned to the direction of the quantile function gradient (if this gradient exists). The parameter Pk plays the part of a step length. The setup parameters of the algorithm pk,ak,tk can be chosen by using the considerations equivalent to the considerations used during the derivation of the stochastic approximation algorithm The step length pk has to be long enough to provide the opportunity to reach any point in [Rm from the initial point ue [Rm (the o0 condition E Pk=co ) but on the other hand the length of step ha.k= to tend to 0 ( the condition EPk < ). The sample si/t, k=1 -4 -

has to increase to infinity since the biased quantile estimate (k(u) is used and the bias of this estimate tends to 0 as the sample size increases ( the condition tk-n ). The length ak of test step that is used for calculating the quasigradient it (uk,ak) has to tend to 0 (the condition ak-iO) but slower than k the sample size increases ( the condition k/(aktk) -> ). Moreover, the length of current test step must be more than the o0 algorithm step length Pk ( the condition E(pk)/(aktk)<oo ). =1 The given conditions hold, for example, when Pk=Poktk=tk2/3 and ak=a k13 where pO is the length of the initial step, to is the initial sample size, and ao is the initial test step length. It follows that the sample size increases quickly enough. It's essential for the effectiveness of the algorithm to choose good enough initial parameters of the algorithm uo,Poto,ao. The successful choice of these parameters gives us the opportunity to obtain a good estimate for the quantile problem quickly. The method for choosing these parameters depends considerably on the problem statement and so it is impossible to give universal recommendations. At the end of this section I would like to make an important remark concerning the connection between the quantile optimization problems and minimax ones. Suppose the following minimax problem is under the consideration: u =arg min max 4(u, o)=arg min O(E,u) uU C)EE u~U where E is a set of feasible values of uncertain vector ElR"n. A set E is convex and compact. Let the function 4(u, W) satisfy conditions A and C given at the beginning of this lecture. The solution to this problem may be very difficult because of the complex dependence of the objective function in w. Instead of solving this problem it is possible to look for the solution to a quantile problem with the same objective function $(u,w) and with a random vector o distributed Normally with the parameters: mM[o], KM[(w-m)(om)T] The covariance matrix K and the vector of expectations m are chosen to provide the best approximation of the uncertainty set E by the ellipsoid of concentration: E-{ t: (o-m)TK (A)-m-) r } -5 -

with the probability measure that is equal to a. The value a will be considered as the level of objective function quantile. The algorithm described above is used to minimize it. The quantile estimate Ia(ua) has to be chosen in some sense to minimize the value of the maximum function I(E,uo). Thus, a minimax problem can be transformed to a quantile optimization one. But in some cases it is advantageous to act conversely. Let's consider the following algorithm. 2. The Minimax Algorithm. Let's now consider the minimization algorithm based on the minimax estimates of the quantile function. We understood from the perfunctory analysis of the algorithm in the first section that the convergency rate is not high. The cause of this situation is the high sensitivity of quantile criterion to computational errors. It was noted in lecture #2. Using the minimax estimates of the quantile, we can hope to find the approximate solution of an original problem, and the convergency rate to this approximation will be higher. Moreover, the conditions for using the direct algorithm are rigid enough. In particular, it is required for an objective function 1(u,)w) to depend monotonically on a quasi-convex function t(u). Now I will try to weaken this requirement. Let the random vector w still have standard Normal distribution N(O, I). The set of feasible strategies be compact. i.e. conditions B and C formulated above hold. However, the following condition must hold instead of A and A': A*) The objective function I(u,w)) is a continuous function both in uEU and in c. Let it be quasi-convex in uEU for any w anid pseudo-convex in co for any uEU. The pseudo-convexity of a function ((u,w) in o means that the objective function is differentiable, i.e. its gradient V D(u,w) exists in any point o and the following conditionr holds: if VT(u, W)(W2-o1) 0 then( u, l) ( u, w2) Under the given assumptions, the maximum function l(u)=max 1(u,w) )OzQE -6 -

where dE is a surface of a confidence SP-,- E, i.e. P(E)=a, will be quasi-convex in u. In lecture #2 I showed that the maximum function 0(u) is an upper estimate for the quantile function Da(u), i.e. 0(u)-JXc(u). And furthermore, the estimate becomes closer to the real value oa(uo) as the value of probability a tends to 1, i.e. 0(u)-4a(u) - 0 as a - 1. That leads us to beleive that a maximum function might be a good estimate for quantile function. Now I will describe the stochastic quasigradient algorithm for quantile function minimization which is similar to the one described above. The following function will be used as a statistical estimate of a quantile function n-1 Ot(U) m t(U) + - [t(U) —1(U)] where n is a dimension of the space =-Rn",,t(u) and t_ t(u) are the two last terms of the ordered series of the sample of objective function values 1(u,oj),j=7f, t is the sample size; cj are random vectors uniformly distributed on the surface dE of the confidence ball E. Thus the statistics lt(u) are estimates of the quantile function 1a(ua) since (u)and (u) is an u is estimate of 0(u). Recall that when the quantile function statistical estimate was found, as in the previous section, it was assumed that the random variable 4(u,wo) is a random variable of the exponential type. And it means that the range of values of the objective functionl(u,o) is the whole real line R1. In this case, the statistical estimate of the maximum function 0(u) is considered. If the function ((u,dc) is continuous in o, then the maximum function 0(u) will be bounded above and below on thesPheeE. Thus the random variable t(u,o) with o chosen on the surface 9E can not be a variable of the exponential type. In this case it is possible to show that the random variable 1(u,c) is a variable of the truncated exponential type, i.e. the limiting distribution of the extremal ordered statistic lt(u) is the following: F ( exp(-(-cp~)), pO<0 <P l 1, p>0 where, m-i For where = — ' - m is a dimension of the space '=0Rm. For - 7 -

simplicity, it will be assumed that in the future the level surface {o:1(u,0))=q} has first order tangency with the sphere HE. m-1 Otherwise, the constant y is equal to r+ where r is an order of tangency of these surfaces. This statement can be formulated more precisely in this way: Lemma 2. If the conditions A*,B,C are fulfilled and the random vector u is uniformly distributed on the sphere OE, then the objective function D(u,co) is a random variable of the truncated exponential type, and the error of the maximum function estimate zt(u) a | M [ ] t(u)-(u) ] is of order o(1/t) uniformly in uEU. Let's now consider the stochastic quasigradient of the maximum function I m ^ ^, A 1 ~t(u,a) = _E[t(U,...ui+a,.u)- (u u-a,.. u )]e where u'. are independent random variables uniformly distributed on the segments [u.-a,u.+a]; e. are unit coordinate vectors in the space [Rm; a is a smoothing constant. The stochastic quasigradient algorithm for the maximum function minimization will be the following: uk+l (uk-pkt kak)), uEU where IIU is an operator which projects the vector from space Rm on its subset U Theorem 2. Let conditions A*,B, and C for the problem statement hold, and the parameters of the algorithms obey the following conditions: n n 2 n EPk =~ 00 Pk < 00 S pk/(akt k) <,0 k=l k= k a->, to at-, t k(m-) -0, a > 0 P > 0 k k k k 2i4/(m-l) k k k k Then all of the limit points of the sequence of the stochastic quasigradient algorithm vectors uk belong with probability 1 to a set of extremal points of a maximum function. I must remark that the constraints on the parameters are similar to those in the previous section. The differences here are the requirement that both the test step length ak and the sample size tk increase simultaneously,. i.e. k/(at4k/m )) - 0. - 8 -

The last requirement depends on the dimension n of the random vector space Rn. When the dimension is greater than 3, this requirement results in the sample size increasing at a higher rate than analogous parameter in the quantile function minimization algorithm (when all other parameters are the same ). 3. Landing Runway Area Minimization. Now a comparatively simple example will be considered. This example will be used to illustrate the possibility of reducing the problem with the chance constraint to the quantile optimization problem. Peculiarities of the direct and the minimax algorithms discussed above will also be shown. Let Lo be a nominal length of the aircraft landing runway. Let (L and ~z be random longitudinal and cross errors of landing the aircraft caused by wind influence during landing. These errors are nonlinearly connected with the longitudinal (WL) and cross (wZ) components of the horizontal wind o (o=col(OL, t)). For simplicity, it will be assumed that magnitudes of components wL and wz are not changed during every landing. If the aircraft is controlled only through the angle of it's roll then the error components at the moment of landing will be (L=allWLoL+a12 1 Oz IoZ z=a22wz'z, a21=0 where alla12, a22 are given scalar coefficients, aL and (7z are the mean square deviations of the longitudinal and the cross wind components, wL and tz are independent random variables with standard Normal distributions, i.e. with zero expectations and unit variances. A similar model for describing a reaction under disturbances is used in a "Buran" shuttle spacecraft control system. Now it is possible to state the problem of choosing the positive parameters LI,L2,Z of the runway which play the role of "reserve" in case of undershoot, overshoot, and cross miss, respectively. These parameters have to provide that the minimal area of the runway: S(L, L2, Z)=2Z(LO+L1+L2) - min L1, L2,Z When the constraint guaranteeing a successful landing with a probability not lower than given a holds: P{C)L, (O:- Ll-L-L2, II Z}a -9 -

A reduction i n the total a rea o f the runway results i n a lowker cost o f construction. This problem i s a n example o f a typical problem with chance constraints. Now it is possible to show how t hi s problem can be reduced t o an unconditional quantile optimization problem. First, replace the variables: L I 0~+LI+L 2V2ZLL L) u=L- 2 0 1 _______ 12 Then, Z~u~'~) (u 2 L)u Now re-write the original constraints with the new notation: uI+1 L 4~~ (C 1a W +a 0r W 1l(ult u2,cLt wZ)=- 1u~2 L11 2 1fZIWZ 2+~ uI+1 L 1~(Iu2cLco) j(a'Lallo2+a 1ZII)+L12 < 4~3(2' z)=22 u 2o(L ZW 4~4(u2,w)Z)=-2a 22u o.Z&) < 1 and introduce the objective function as the maximal of the four functions mentioned above: 4~( uTu2 ~L' COZ)= Max{fl~ (ult UT OU'wZ)} Now i t i s possible to reduce the original problem with chance constraint to the unconditional quantile optimization problem where t (Xu19 u2) is the ax-order quantile of the random variable t~uivU2W I Z)which can be found from the inequality: D'{o: t(u1, u2? WLUZ)<4~a}1>a The sq ua re of a quantile f unc tion i s equal t o th e original criterion t2u u )=S(L1, L2,Z Since the area of the runway is a positive value and the function t VIs'is strictly monotonic, and thus, minimization of S is equivalent to minimization (D. = VI S. - 10 -

This quantile optimization problem was solved by using both of the algorithms described above. I want to remark here that the minimax problem could also be solved, in this case, without using the stochastic quasigradient method. In fact, thanks to the piece-wise linear structure of an objective function, its maximum on the confidence circle aE can be found analytically. It is necessary to consider the points of tangency between the confidence circle and the level curves of an objective function. After the maximum function 0(u) is found, one can use convex programming methods for minimizing it. It is easy to check that, in this case, the objective function is convex in ul and in u2. This means that the maximum function 0(u) will be convex also. This example is used here for illustrative purposes. The aim is to analyze the peculiarities of the stochastic quasigradient algorithms. An example of this is the comparison of time consumption of the algorithms. The problem has been solved by IBM-PC/AT-286 when: al= 20 sec.,a2=-20 sec.,a22= 3 sec.,L0= 1500 m,oL=oz= 5 m/sec. The table written below indicates the results: time of a a I gor i thm S[km ] count ing u u s___ ec.] 0.99 direct 0. 17 85 1.88 26.3 minimax 0.202 20 1.48 24.4 0.999 direct 0. 236 210 1.96 23.3 minimax 0.265 30 1.48 21.3 0.9999 d i re c t 0. 304 720 2.03 23.3 minimax 0.324 55 1.48 21.3 0.99999 d i rect 0. 366 3600 2.12 19.2 minimax 0.38 70 1.48 16.3 0.999999 direct 0.422 25200 2.2 18.1 minimax 0.432 90 1.48 17.4 The table shows that as a increases the upper estimate oi the quantile of runway area becomes closer to the true value oi quantile. However the convergency rate is not high. Use of t ti. direct algorithm provides an opportunity to obtain the optim;al solution through the direct minimization of a quantile function The estimate found by the minimax algorithm is greater than tt. true value of the runway area quantile. But the minimax problt rn - 11 -

solution is weakly dependent on the probability level oa as soon as this level is essential for time consumption on direct algorithm. For example, to make calculations using the direct method when a is equal to 0.999999, it was necessary to use a more powerful computer than the IBM-PC/AT-286. In practice, it is more useful to combine the two algorithms. For example, one can quickly obtain a good initial approximate solution using the minimax algorithm and then improve the solution using the direct algorithm. 4. The Linear-Quadratic Algorithm. Consider the following algorithm which is an advanced minimax algorithm. Suppose that the objective function: D(u,Wc)= max 4.(u,w) we r T T T1 5 i < where.(uo)) A (u au+bw)(+(u+d) Cj(u+di)+qi, i=lh is piece-wise linear in the random vector co and piece-wise quadratic in the strategy u. As usual, I will assume that the random vector ( has a standard Normal distribution N(0, ). To estimate the quantile 1a(ua) of the random variable 4(u,w), I will use the minimax estimate X1(u) < inf sup max. (u, W) uE U WE a i = 1 i' where 9E is the sphere of the confidence ball E, P(E)=a. Suppose that the set U of feasible strategies u is a convex polyhedron. As soon as the functions 4.(u,w) are convex and continuous in u and in o for any i=l,n, then the maximum function ((u,w) will also be convex and continuous in u and in W. Thus the upper bound of an objective function D(u,w) on the sphere 9E is attained and, therefore, the supremum can be replaced by the maximum. Moreover, the maximum function 0(u) - max c(u,w) will also be continuous and convex in u. Thus the minimum will be attained on a convex polyhedron U. The original minimax problem is reduced in this way to a convex programming problem p*= min 0(u) uEU In this case the maximum function can be written explicitly. The maximum of the function c(u,w) on the sphere aE is attained at - 12 -

the points of contact with the hyperplanes when the strategy u is fixed. The equations (uTa.+bT))+(u+d )TCi(u+d )+q=(p, i=Tl n describe hyperplanes of equal value of the function 1(u,o))=(p. If r is the radius of a sphere E, then it is possible to find n points where the objective function ((u,w) reaches it's maximal value i r (a.u+bi) [a u + bj[ i-, n Thus 0(u)= max [llaiu+biL -r + I[u+dllc.+qi] 2 A T where Ilu+di llc= (u+d) Ci(u+di). To solve the convex programming problem of 0(u) minimization, it is possible to use known methods of the undifferential optimization. Here I will not discuss them in detail. But, for example, one method of solving this problem is the subgradient algorithm k+l= k_(uk-q V(uk)] u IUIU[U 111IIV(u k)U[ l Vk(Uk )II where Vl(uk) is a sub gradient of function 0(u) in point uk, q= min q. is a minimal value of the free parameter in this 1 i-n function. It is known that a convergency rate of this algorithm decreases if the function 0(u) is not differentiable at the minimal point. To solve this problem, it is also possible to use the generalized simplex method, which is especially effective in this case. I would like to note that in particular cases the convex programming problem will become simpler. For example, if the functions i(u,))Uk a TI+cTu+qi, i=ln 1 where uk is a certain k.-th component of vector u, then the maximum function Oi(u) is piece wise linear: 0(u)= max [. Ilai II r+c u+qi] i l n i i Thus the programming problem of maximization of this function on a convex polyhedron reduces to a linear programming problem - 13 -

-r =mi n 0(u) r uEU It is possible to use the simplex method to solve this problem. The efficiency of this method is comparatively high and the solution is found after finite number of steps. I would like to call your attention to the fact that the obtained minimax estimate Ir can be considerably excessive with respect to the real quantile Oa(ua). The error of this estimation can be evaluated in an indirect way by calculating the difference between the upper estimate or and the lower estimate Os. The latter can be found in the following way. Since the objective function in this case is a convex function and, therefore, it is possible to consider the a-level kernel of Gaussian measure. In this case, it will be a sphere So with a radius p defined by the equation P{ W: col p } = a Then, according to lemma 3 from the previous lecture 0p- min max D(u,w) S (u UEU oe S - For calculation of the lower estimate it is possible to use the same algorithm that was used for the calculation of the upper estimate ir, but the radius of the confidence ball will be p instead of r. If it turns out that the difference between the two estimates is close to zero, i.e. 0tr-0-~O, then the minimax estimate can be considered satisfactory. Otherwise, it is possible to use the following method to improve this estimate:Let up and u be the strategies corresponding to the upper and the lower quantile estimates. These strategies are found when solving the corresponding minimax problems. One can use a statistical simulation method for calculating the quantiles 1a(up) and a:(ur). Next, one chooses a new zphert with radius x1=(r+p)/2 Solve the minimax problem again for this:ph-e The result is a new strategy ux, and a new quantile D (ux). Then the dichotomy method is used until the minimax value of a quantile is found: Oac= min o:(uk), R=arg min ac(ux) p<x5_r p_5 x<r Let's denote by uR the minimax strategy found for the pef E;[ with a radius R. This procedure is based on uni-modal dependent, of quantile function o((ux) on radius x. The obtained quant ii - 14 -

estimate ot-A-cvr(UR) is still the upper estimate of the desired value a(uao), but it is closer to ax(ua) than the minimax estimate r'. In practical problems, only a few steps are needed for the improvement of the minimax estimate 0r 5. Water-Supply Optimization For a Desert Region. Consider the model of water-supply for a desert region. Suppose that the region can be supplied with water carried from other regions or with water obtained using solar batteries. The model describing the way that the water reserves change in time can be stated in the following way: Zi+ = min {ziuN+1} + U. + uN+1i - hi, z1= i=T N where zi+l is the remainder of water at the end of i-th month; uN+1 is an area of solar battery; uN+2 is a tank volume where the remaining water is kept; u, i=,N is the amount of water carried to the region during the i-th month; h. is the known consumption of water during the i-th month; o. is an output of the solar battery during the i-th month. It is supposed that w. are random and mutually independent variables, and they are Normally distributed N (mi,oi). The requirement is to keep the water reserve grater than zero during all the months and the probability of the event that there is some reserve must be grater than or equal to a: P { w.: min z. 0 } > a. i =1, N+1 The other requirement is to provide the minimal expenditures, N i.e. o(u) = c7 u. + C UN + c2uN m n, o 0 1 1 N+1 2+2 ' i=1 where U = { u. > 0, i=1,N+2 }; u=col(u,...,uN+2); c is the cost of the delivered water; cl is the cost of a solar battery, c2 is the cost of a tank. This problem is the problem with chance constraint. But it can be reduced to a quantile problem by changing the variables. For simplicity I will consider the case of two months, i.e. N=2. Change the variables: 4 2u o4 = o - 4 4 - 15 -

Then the probabilistic constraint transfers to the following: P {(l, 2': max.(u,o) - ~ } ( a, i=1,3 where 1(u,&) = 2a u + 2a u3 - 2aou3wl - u4 2a h 2(u, ) =-2a2u2 - 2a2u3W2 - U4 2aoh2 %3(u,W) = 2a u3 - 2a u3(o + 03) - 2a(h1+h2) In this case D is an a-order quantile of random variable max I (ulw). i =1,3 The three above presented algorithms were used to solve thi problem. In the third algorithm due to the structure of an s objective function one gets a linear programming problem. happens since all the functions ~.(u, &) contain the same control parameter u3 multiplied by the random parameters. The results are presented in the table below. The input da in the problem were the following: It ta a =25 [rbl/m3]; a =5 [rbl/m2]; a2=10 [rbl/m3]; hl=80 [m ]3 h2=120 [m ]3 m=0.12 [m ]; m2=0.15 [m ]; a | the cost D [rbl] time consumpt ion for solving us i ng IBM PC/AT _____ [s e condss_ direct minimax linear di rect minimax I near 0.9 4151 4258 4196 360 210 10 0.99 4389 4478 4407 1200 370 40 0.999 4614 467 1 4629 4000 6 30 160 0.9999 4783 4854 4789 12500 800 6t00 0.99999 4930 5000 4939 40000 1 100 1 21)0 As you can see from this table, the minimax algorithm gives th e overestimate for the quantile, but the time necessary for calculations is only slightly dependent on the probability a. Ii the probability level close to 0.99999 then the time consumptiorl for the minimax and the linear algorithms are approximately t ht same. It happens since when using the linear algorithm it i, necessary to make statistical simulation in every step of t th algorithm and the amount of calculations increases as a increases. But the time consumption when using linear algorithmrr - 16 -

is considerably less than when using direct algorithm as in linear algorithm only one parameter is chosen, and in direct algorithm four parameters are varying. The linear algorithm gives the overestimate also, but the errors are smaller than when using minimax algorithm. A more powerful computer than IBM PC/AT was used to find the solution for the probability level ao=0.99999 using direct method. I must also note that if the statistical simulation is used consecutively with the random search method it results in increasement of the time consumptions that is necessary for the direct algorithm. REFERENCES 1. Kibzun, A.I. and V.Yu.Kurbakovskiy Guaranteeing approach to solving quantile optimization problems.- Annals of Operations research, 30, 1991. 2. Kibzun, A.I. and V.Yu.Kurbakovskiy Numerical algorithms for quantile optimization and their application for solving probabilistic problems.- Izv. AN SSSR, Teknicheskaya Kibernetika, N 1, 1991. (in Russian). 3. Galambos J. The Asymptotic Theory of Extreme Order Statistics, Wiley, 1978. 4. Ermoliev, Yu.M. Methods of Stochastic Programming, Nauka, 1976 (in Russian) 5. Kibzun, A.I. Stochastic Control of Descrete-Time Dynamic Systems. - Moscow Aviation Institute, 1991 (in Russian) - 17 -