Abstract
Stochastic optimization problems with probabilistic and quantile objective functions are considered. The probability objective function is defined as the probability that the value of losses does not exceed a fixed level. The quantile function is defined as the minimal value of losses that cannot be exceeded with a fixed probability. Sample approximations of the considered problems are formulated. A method to estimate the accuracy of the approximation of the probability maximization and quantile minimization is described for the case of a finite set of feasible strategies. Based on this method, we estimate the necessary sample size to obtain (with a given probability) an epsilon-optimal strategy to the original problems by solving their approximations in the cases of finite set of feasible strategies. Also, the necessary sample size is obtained for the probability maximization in the case of a bounded infinite set of feasible strategies and a Lipschitz continuous probability function.
Access provided by Autonomous University of Puebla. Download conference paper PDF
Similar content being viewed by others
Keywords
1 Introduction
Problems of stochastic programming with probabilistic and quantile objective functions are encountered in many applied problems, where special attention is paid to the reliability of the system. These problems and methods for solving them are well covered in [1].
In this paper, we research the sample average approximation (SAA) method for solving stochastic programming problems with probabilistic and quantile objective functions. This method is based on statistical estimation of the objective function. For the expectation objective function, the convergence of the SAA method is proved in [2]. The SAA method was applied to stochastic programming problems with probabilistic constraints in [3], where the convergence of the method was proved for a special case of the problem. In [4], the possibility of approximating a stochastic programming problem with probabilistic and quantile objective function was investigated. The hypo-convergence of sampling probability functions is proved, which in turn guarantees the convergence of the approximation of the probability maximization and quantile minimization problems with respect to the value of the objective function and with respect to the optimization strategy.
From recent works on the SAA, [5] can be noted, where general approach to study approximations of stochastic programming problems is suggested. In [6], confidence bounds on the optimal objective value are constructed.
When the SAA method is applied, the reduced problem can be considered as a stochastic optimization problem with discrete distribution of the vector of random parameters. These problems can be reduced to mixed integer programming problems [7], which can be solved by using available software.
To apply the SAA method, it is useful to know the quality of the obtained approximate solution. In [8,9,10], in the case of a finite set of feasible strategies, an estimate of the required sample size was obtained to approximate an expectation minimization problem. This result was extended for the case of a Lipschitz continuous expectation function in [8]. To estimate the required number of realizations of the random vector, the exponential estimation of large deviations was used. In [11], the rate of convergence is studied for stochastic programming problems with probabilistic constraints.
This paper presents sample size estimates for problems of stochastic programming with probabilistic and quantile objective function. For the probability maximization, we consider cases of finite and bounded set of feasible strategies. For the quantile minimization, the case of finite set of feasible strategies is considered.
2 Statement
Let \((\mathcal {X}, \mathcal {F}, \mathbf {P})\) be a complete probability space. Let X be a random vector defined on this probability space. For simplicity, we assume that \(\mathcal X \subset \mathbb R^m\) is a closed set.
Let us denote by \(\varPhi (\cdot ) :U \times \mathcal {X} \rightarrow (-\infty , +\infty )\) a loss function, where \(U \subset \mathbb {R}^n\) is a nonempty compact set of strategies u. We assume that the function \((u, x) \mapsto \varPhi (u, x)\) is lower semi-continuous in \(u\in U\) and \(\mathcal B(U) \times \mathcal F\)-measurable in \(x\in \mathcal X\), where \(\mathcal B(U)\) is the Borel \(\sigma \)-algebra of subsets U. These conditions guarantees that the function \((u, x) \mapsto \varPhi (u, x)\) is a normal integrand [12].
Let us introduce the probability function
and quantile function
where \(\alpha \in (0, P^*)\) is a given reliability level,
We consider the probability maximization problem
and the quantile minimization problem
The sets of \(\varepsilon \)-optimal solutions to problems (1) and (2) are denoted by
respectively.
3 Sample Approximation
Let \(X_1, \ldots , X_N\) be a sample generated by random vector X, i.e., random vectors \(X_k\), \(k = \overline{1,N}\), are independent identically distributed with distribution function \(F(x) = \mathbf {P}\lbrace X \leqslant x \rbrace \). We assume that the sample is defined on a complete probability space \((\varOmega , \mathcal {F'}, \mathbf {P'})\). This probability space may differ from the space \((\mathcal {X}, \mathcal {F}, \mathbf {P})\). However, below we will use the same letter \(\mathbf P\) for the probability \(\mathbf P'\), because it is clear which probability space is considered. Then we can write the frequency of the event \(\lbrace \varPhi (u, X) \leqslant \varphi \rbrace \) as
where
By using (3), the quantile function can be estimated by
The sample approximation of the probability maximization problem is formulated as
and the sample approximation of the quantile minimization problem is formulated as
From [4] it follows that quantile function (4) coincides with the order statistics of sample values \(\lbrace \varPhi _k \rbrace _{k=1}^N \) for the random variable \(\varPhi \triangleq \varPhi (u,X)\) that has index \(\lceil \alpha N \rceil \) and is called the sample quantile, where \(\lceil x \rceil \triangleq \min \lbrace k \in \mathbb {N}:x \leqslant k \rbrace \).
4 Estimation of the Necessary Sample Size for Probability Maximization
In [4] the convergence of the approximating stochastic programming problems (5) and (6). These results, however, do not show the quality of solutions for a given sample of size N. In this section, we find upper bounds on the necessary sample size to consider a solution to (5) as an approximate solution to problem (1).
4.1 Case of Finite Set of Feasible Strategies
Let us begin with the case when the set U is finite. Its cardinality is denoted by |U|.
We consider the event
The event \(\left\{ \hat{U}_\varphi ^{(N)} \not \subset U_\varphi ^\varepsilon \right\} \) means that there exists an optimal solution \(u_\varphi ^{(N)}\) to the approximation problem (5) such that \(u_\varphi ^{(N)}\) is not \(\varepsilon \)-optimal solution to the true problem (1).
Then, given that the set U is finite, we can find an upper bound for the probability
Let \(u^*\) be an optimal solution to the true problem (1). If there several optimal solution to problem (1), then \(u^*\) can be taken arbitrarily. It follows from (7) that
Let us introduce the random variables
Notice that \(\xi _k\) are independent. Then we can write
where \(t > 0\). By Chebyshev’s inequality,
where
is the moment-generating function of the random variable \(\xi _1\).
Lemma 1
Let M(t) be the function defined by (10). Let \( 0< \varepsilon < \alpha ^*\). Then
If \(\alpha ^* \le \frac{1+\varepsilon }{2}\), then
Proof
Let us introduce the events
Then
where
Since \(u^*\) is an optimal solution to the true problem (1) and \(u\in U \setminus U_\varphi ^\varepsilon \), it holds that
From (11) and (12), it follows that
Therefore,
The function \(t \mapsto M(t)\) is convex. From the optimality conditions, we obtain
if \(p_+ > 0\). From (14), it follows that
Thus,
If \(p_+ = 0\), then equality (15) holds too.
The function \((p_+, p_-) \mapsto Q(p_+, p_-)\) is concave (see, for example, [13, P. 74]). Let us find
subject to (13), (14), and (15). Since the unconditional maximum of \(Q(p_+, p_-)\) is attained when \(p_+ = p_-\), the conditional maximum is attained when the constraint (14) is active. Taking into account the constraint \(p_+ + p_- \le 1\), it is easy to see that
Thus, Lemma 1 is proved.
Let us prove a theorem on the necessary sample size to approximate the true problem (1).
Theorem 1
Let \(\beta \in (0, 1)\). If the set U is finite and
then
Moreover, if it is known that \(\alpha ^* \le \frac{1 + \varepsilon }{2}\), then inequality (17) holds if
Proof
First, let us consider the case \(\alpha ^* \le \varepsilon \). Then, it is obvious that
hence, the assertion of the theorem is true.
If \(\alpha ^* > \varepsilon \) and \(\alpha ^* \le \frac{1 + \varepsilon }{2}\), then, from (8), (9), and Lemma 1, it follows that
Thus, inequality (17) holds if
Since
we obtain that inequality (17) holds for
In the case when \(\alpha ^* > \varepsilon \) and \(\alpha ^* > \frac{1 + \varepsilon }{2}\), the theorem is proved in the same manner. Theorem 1 is proved.
Remark 1
In [9, Theorem 5.17], a result similar to Theorem 1 is proved for the maximization of the expectation function. By applying this result to problem (1), it can be obtained that inequality (17) holds for
It is easy to check that
for \(\varepsilon \in (0,1)\). Thus, the sample estimate (16) improves the result in [8] for maximization of the probability function.
Remark 2
To apply the sample estimate (18), we need to know exact solution to problem (1). However, the sample approximation is construct to estimate \(\alpha ^*\). Sometimes, it possible to find an upper bound \(\bar{\alpha }\ge \alpha ^*\). If \(\bar{\alpha }\le \frac{1 + \varepsilon }{2}\), then we can improve the sample estimate (16). It is guaranteed that inequality (17) holds if
4.2 Case of Bounded Set of Feasible Strategies
Let us consider the case when U is a bounded, not necessarily finite, subset of \(\mathbb {R}^n\). The diameter of U is denoted by
where the norm \(\Vert u \Vert = \max \lbrace |u_1|, \ldots , |u_n| \rbrace \) is used.
We suppose that the probability function \(u\mapsto P_\varphi (u)\) is Lipschitz continuous on U with a Lipschitz constant L, i.e.
for all \(u, v\in U\).
Theorem 2
Let \(\beta \in (0, 1)\). If the assumption (19) is satisfied and
then
Proof
First, let us check that the event \(\left\{ \hat{U}_\varphi ^{(N)} \subset U_\varphi ^\varepsilon \right\} \in \mathcal F'\). Since the function \((u, x)\mapsto \varPhi (u, x)\) is a normal integrand, the function \(u\mapsto P_\varphi (u)\) is upper semi-continuous and the set \(U_\varphi ^\varepsilon \) is compact [4]. Also, the \(u\mapsto \hat{P}_\varphi ^{(N)}(u)\) is upper semi-continuous for all fixed realizations of the sample. The compactness of U and semi-continuity of these function imply that the supremum
is attained and is a measurable function of the sample. Thus, the considered event can be represented as
where
The set \(U_k\) is compact, so the function
is measurable and, hence,
Let \(\tilde{U}\) be a finite subset of U. Let
The value of \(\nu \) shows the maximal distance between an arbitrary point of U and the nearest point of \(\tilde{U}\). The set \(\tilde{U}\) can be selected in such a way that
It will be assumed that condition (22) is satisfied.
Let
where
Since the function \(u\mapsto P_\varphi (u)\) is Lipschitz continuous, the condition \(u\in \tilde{U}^\varepsilon _\varphi \) implies \( u\in U^{\varepsilon +L\nu }_\varphi . \) If \(\gamma \in (0, 1)\) is a fixed number and \(L\nu =(1-\gamma )\varepsilon \), then
From (23) and Theorem 1, it follows that
if
Since \(\gamma \) is selected arbitrarily, the theorem is proved.
Remark 3
A similar result for minimization of the expectation function is proved in [8]. This result can be obtained from Theorem 2 if \(t = 1/2\). Additional optimization in \(t\in (0, 1)\) can improve the result [8] for the special case of probability maximization. If the exact value of the infimum is difficult to find, then the sample estimate N can be found by substituting several values of \(t\in (0,1)\) into (20). The minimal value of the obtained numbers can be set as the sample estimate N.
Remark 4
To apply the sample estimate (20), the Lipschitz constant is need to know. If the function \(u \mapsto P_\varphi (u)\) is continuously differentiable on the set U, then, from the mean value theorem, it follows that
Therefore, we can take \(L = \sup _{w \in U} \Vert \nabla P_\varphi (w)\Vert \). Methods to find the gradient of the probability function are described in [14, 15].
5 Estimation of the Necessary Sample Size for Quantile Minimization
In this section, we find upper bounds on the necessary sample size to consider a solution to (6) as an approximate solution to problem (2). We assume that the set U is finite.
We suppose that the following assumption is satisfied.
Assumption 1
The random variable \(\varPhi (u, X)\) is absolutely continuous for all \(u\in U\) with probability density function \(p_u(\cdot )\) continuous at the point \(\varphi _\alpha (u)\) with its neighborhood. Also, there exists a number \(C > 0\) such that
As for the probability function, consider the event
Then we can find an upper bound for the probability
Let us fix an optimal solution to the true problem (2) \(u^*\). From (24), we obtain
Let us define the random variables
Notice that the random variables \(\varphi _\alpha ^{(N)} (u^*)\) and \(\varphi _\alpha ^{(N)} (u)\) can be dependent. We need to find an upper bound on the probability
By the Mosteller theorem [16], the distribution of the order statistics \(\varphi _\alpha ^{(N)} (u^*)\) and \(\varphi _\alpha ^{(N)} (u)\) converges to a normal distribution:
Therefore, we can write
Thus, for any \(0<\varepsilon '<\varepsilon \), there exists \(\tilde{N}(\varepsilon ')\in \mathbb N\) such that
for all \(N > \tilde{N}(\varepsilon ')\). We would like to notice that \(\tilde{N}(\varepsilon ')\) can depend on u. So, the maximal value of \(\tilde{N}(\varepsilon ')\) should be taken.
By Cantelli’s inequality, for \(N > \tilde{N}(\varepsilon ')\),
Thus, from (25), the theorem follows.
Theorem 3
Let U be a finite set, \(\beta \in (0,1)\). Assumption 1 is supposed to be satisfied. Then
for sufficiently large N.
Now, we can obtain the corollary from Theorem 3.
Corollary 1
Let assumptions of Theorem 3 be satisfied. Then
if
and \(N > \tilde{N}(\varepsilon ')\).
Proof
From (28), it follows that the assertion of the theorem is true if
By solving this inequality, we obtain (29). The corollary is proved.
Remark 5
Unfortunately, it is difficult find bounds on the value \(\tilde{N}(\varepsilon ')\). To use the estimate (29), inequalities (26) and (27) should be checked. It can be made by statistical methods.
6 Conclusion
In the paper, sample size estimates for approximation of stochastic optimization problems with probabilistic and quantile objective functions are obtained. These estimates are quite rough for practical use, but they allow us to judge the complexity of the solution to the original problem. In future research, it is planned to improve this result for special cases of stochastic optimization problems. We hope that it is possible to describe a class of problems for which exponential bounds can be obtained instead of (28). Also, a more general case of quantile minimization problem on a bounded set should be studied.
References
Kibzun, A.I., Kan, Y.S.: Stochastic Programming Problems with Probability and Quantile Functions. Wiley, Chichester, New York, Brisbane, Toronto, Singapore (1996)
Artstein, Z., Wets, R.J.-B.: Consistency of minimizers and the SLLN for stochastic programs. J. Convex Anal. 2, 1–17 (1996)
Pagnoncelli, B.K., Ahmed, S., Shapiro, A.: Sample average approximation method for chance constrained programming: theory and applications. J. Optim. Theory Appl. 142, 399–416 (2009). https://doi.org/10.1007/s10957-009-9523-6
Kibzun, A.I., Ivanov, S.V.: On the convergence of sample approximations for stochastic programming problems with probabilistic criteria. Automat. Remote Control. 79(2), 216–228 (2018). https://doi.org/10.1134/S0005117918020029
Hess, C., Seri, R.: Generic consistency for approximate stochastic programming and statistical problems. SIAM J. Optim. 29(1), 290–317 (2019). https://doi.org/10.1137/17M1156769
Guigues, V., Juditsky, A., Nemirovski, A.: Non-asymptotic confidence bounds for the optimal value of a stochastic program. Optim. Method. Softw. 32(5), 1033–1058 (2017). https://doi.org/10.1080/10556788.2017.1350177
Kibzun, A.I., Naumov, A.V., Norkin, V.I.: On reducing a quantile optimization problem with discrete distribution to a mixed integer programming problem. Automat. Remote Control. 74(6), 951–967 (2013). https://doi.org/10.1134/S0005117913060064
Shapiro, A.: Monte Carlo sampling methods. In: Ruszczyński, A., Shapiro, A. (eds.) Handbooks in OR Handbooks in Operations Research and Management Science & MS, North-Holland, Dordrecht, The Netherlands, vol. 10, pp. 353–425 (2003). https://doi.org/10.1016/S0927-0507(03)10006-0
Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on Stochastic Programming. Society for Industrial and Applied Mathematics, Philadelphia (2009)
Kleywegt, A.J., Shapiro, A., Homem-De-Mello, T.: The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2), 479–502 (2001). https://doi.org/10.1137/S1052623499363220
Luedtke, J., Ahmed, S.: A sample approximation approach for optimization with probabilistic constraints. SIAM J. Optim. 19(2), 674–699 (2008). https://doi.org/10.1137/070702928
Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02431-3
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, New York (2004)
Kibzun, A., Uryasev, S.: Differentiability of probability function. Stochast. Anal. Appl. 16(6), 1101–1128 (1998). https://doi.org/10.1080/07362999808809581
Van Ackooij, W., Henrion, R.: Gradient formulae for nonlinear probabilistic constraints with Gaussian and Gaussian-like distributions. SIAM J. Optim. 24(4), 1864–1889 (2014). https://doi.org/10.1137/130922689
Mosteller, F.: One some useful inefficient statistics. Ann. Math. Stat. 17, 317–408 (1946)
Acknowledgements
The work is supported by the Russian Foundation for Basic Research (project 19-07-00436).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Ivanov, S.V., Zhenevskaya, I.D. (2019). Estimation of the Necessary Sample Size for Approximation of Stochastic Optimization Problems with Probabilistic Criteria. In: Khachay, M., Kochetov, Y., Pardalos, P. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2019. Lecture Notes in Computer Science(), vol 11548. Springer, Cham. https://doi.org/10.1007/978-3-030-22629-9_39
Download citation
DOI: https://doi.org/10.1007/978-3-030-22629-9_39
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-22628-2
Online ISBN: 978-3-030-22629-9
eBook Packages: Computer ScienceComputer Science (R0)