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

$$\begin{aligned} P_\varphi (u) \triangleq \mathbf {P}\lbrace \varPhi (u, X) \leqslant \varphi \rbrace , \end{aligned}$$

and quantile function

$$\begin{aligned} \varphi _\alpha (u) \triangleq \min \lbrace \varphi : P_\varphi (u) \geqslant \alpha \rbrace , \end{aligned}$$

where \(\alpha \in (0, P^*)\) is a given reliability level,

$$\begin{aligned} P^*= \sup _{u \in U} \mathbf {P} \lbrace \varPhi (u, X) < +\infty \rbrace . \end{aligned}$$

We consider the probability maximization problem

$$\begin{aligned} \alpha ^* \triangleq \sup _{u\in U} P_\varphi (u) \end{aligned}$$
(1)

and the quantile minimization problem

$$\begin{aligned} \varphi ^* \triangleq \inf _{u\in U}\varphi _\alpha (u). \end{aligned}$$
(2)

The sets of \(\varepsilon \)-optimal solutions to problems (1) and (2) are denoted by

$$\begin{aligned} U_\varphi ^\varepsilon \triangleq \{u\in U :P_\varphi (u) \ge \alpha ^* - \varepsilon \}, \\ V_\alpha ^\varepsilon \triangleq \{u\in U :\varphi _\alpha (u) \le \varphi ^* + \varepsilon \} \end{aligned}$$

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

$$\begin{aligned} P_\varphi ^{(N)} \triangleq \frac{1}{N} \sum _{k=1}^N \chi _{(-\infty , \varphi ]} (\varPhi (u, X_k)). \end{aligned}$$
(3)

where

$$\begin{aligned}\chi _A(x)\triangleq {\left\{ \begin{array}{ll} 0, &{} x \in A;\\ 1, &{} x \notin A. \end{array}\right. } \end{aligned}$$

By using (3), the quantile function can be estimated by

$$\begin{aligned} \varphi _\alpha ^{(N)}(u) \triangleq \min \{\varphi :P^{(N)}_\varphi (u)\ge \alpha \}. \end{aligned}$$
(4)

The sample approximation of the probability maximization problem is formulated as

$$\begin{aligned} \hat{U}_\varphi ^{(N)} \triangleq {{\,\mathrm{Arg}\,}}\max _{u\in U} P^{(N)}_\varphi (u),\, N\in \mathbb N; \end{aligned}$$
(5)

and the sample approximation of the quantile minimization problem is formulated as

$$\begin{aligned} \hat{V}_\alpha ^{(N)}\triangleq {{\,\mathrm{Arg}\,}}\min _{u\in U} \varphi _\alpha ^{(N)}(u), \, N\in \mathbb N. \end{aligned}$$
(6)

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

$$\begin{aligned} \left\{ \hat{U}_\varphi ^{(N)} \not \subset U_\varphi ^\varepsilon \right\} = \bigcup _{u\in U\setminus U_\varphi ^\varepsilon }\bigcap _{y \in U}\left\{ \hat{P}_\varphi ^{(N)}(u) \geqslant \hat{P}_\varphi ^{(N)} (y)\right\} . \end{aligned}$$

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

$$\begin{aligned} \mathbf {P}\left\{ \hat{U}_\varphi ^{(N)} \not \subset U_\varphi ^\varepsilon \right\} \le \sum _{u \in U\setminus U_\varphi ^\varepsilon } \mathbf {P} \left( \bigcap _{y \in U} \left\{ \hat{P}_\varphi ^{(N)}(u) \ge \hat{P}_\varphi ^{(N)}(y) \right\} \right) . \end{aligned}$$
(7)

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

$$\begin{aligned} \mathbf {P}\left\{ \hat{U}_\varphi ^{(N)} \not \subset U_\varphi ^\varepsilon \right\}&\le \sum _{u \in U \setminus U^\varepsilon _\varphi } \mathbf {P} \left\{ P_\varphi ^{(N)} (u) \ge P_\varphi ^{(N)} (u^*) \right\} \nonumber \\&\le |U| \max _{u\in U\setminus U_\varphi ^\varepsilon } \mathbf P\left\{ \hat{P}_\varphi ^{(N)}(u) \ge \hat{P}_\varphi ^{(N)}(u^*) \right\} . \end{aligned}$$
(8)

Let us introduce the random variables

$$\begin{aligned} \xi _k = \chi _{(-\infty , \varphi ]} (\varPhi (u, X_k)) - \chi _{(-\infty , \varphi ]} (\varPhi (u^*, X_k)). \end{aligned}$$

Notice that \(\xi _k\) are independent. Then we can write

$$\begin{aligned} \mathbf P\left\{ \hat{P}_\varphi ^{(N)}(u) \ge \hat{P}_\varphi ^{(N)}(u^*) \right\} = \mathbf P\left\{ \sum _{k=1}^N \xi _k \ge 0\right\} = \mathbf P\left\{ \exp \left( t\sum _{k=1}^N \xi _k\right) \ge 1\right\} , \end{aligned}$$

where \(t > 0\). By Chebyshev’s inequality,

$$\begin{aligned} \mathbf P\left\{ \exp \left( t\sum _{k=1}^N \xi _k\right) \ge 1\right\} \le \mathbf E\left[ \exp \left( t\sum _{k=1}^N \xi _k\right) \right] = (M(t))^N, \end{aligned}$$
(9)

where

$$\begin{aligned} M(t) \triangleq \mathbf E\left[ \exp \left( t\xi _1\right) \right] \end{aligned}$$
(10)

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

$$\begin{aligned} \inf _{t > 0} M(t) \le \sqrt{1-\varepsilon ^2}. \end{aligned}$$

If \(\alpha ^* \le \frac{1+\varepsilon }{2}\), then

$$\begin{aligned} \inf _{t > 0} M(t) \le 2\sqrt{(\alpha ^* - \varepsilon ) \alpha ^*} + 1 + \varepsilon - 2\alpha ^* \le \sqrt{1-\varepsilon ^2}. \end{aligned}$$

Proof

Let us introduce the events

$$\begin{aligned} A \triangleq \{\varPhi (u, X) \le \varphi \},\\ B \triangleq \{\varPhi (u^*, X) \le \varphi \}. \end{aligned}$$

Then

$$\begin{aligned} M(t) = p_+ e^t + p_- e^{-t} + 1 - p_+ - p_-, \end{aligned}$$

where

$$\begin{aligned} p_+ = \mathbf P(A\,\cap \,\overline{B}),\quad p_- = \mathbf P(\overline{A}\,\cap \,B). \end{aligned}$$
(11)

Since \(u^*\) is an optimal solution to the true problem (1) and \(u\in U \setminus U_\varphi ^\varepsilon \), it holds that

$$\begin{aligned} \mathbf P(A) \le \alpha ^* - \varepsilon , \quad \mathbf P(B) = \alpha ^*. \end{aligned}$$
(12)

From (11) and (12), it follows that

$$\begin{aligned} p_+ \in [0, \alpha ^* - \varepsilon ],\quad p_- \in [\varepsilon , \alpha ^*]. \end{aligned}$$
(13)

Therefore,

$$\begin{aligned} \varepsilon \le \mathbf P(B)- \mathbf P(A) = \mathbf P(\overline{A}\,\cap \,B) + \mathbf P(A\,\cap \,B) - (\mathbf P(A\,\cap \,\overline{B}) + \mathbf P(A\,\cap \,B)) = p_- - p_+. \end{aligned}$$
(14)

The function \(t \mapsto M(t)\) is convex. From the optimality conditions, we obtain

$$ {{\,\mathrm{Arg}\,}}\min _{t > 0} M(t) = \left\{ \frac{1}{2} \ln \frac{p_-}{p_+}\right\} $$

if \(p_+ > 0\). From (14), it follows that

$$ \frac{1}{2} \ln \frac{p_-}{p_+} > 0. $$

Thus,

$$\begin{aligned} Q(p_+, p_-) = \inf _{t>0} M(t) = 2\sqrt{p_-p_+} + 1 - p_+ - p_-. \end{aligned}$$
(15)

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

$$ \max _{p_+, p_-} Q(p_+, p_-) $$

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

$$\begin{aligned}&\inf _{t> 0} M(t) \le \\&\max _{p_+, p_-} \left\{ Q(p_+, p_-) \mid p_- - p_+ = \varepsilon ,\, p_+ + p_- \le 1,\, p_+ \in [0, \alpha ^* - \varepsilon ],\, p_- \in [\varepsilon , \alpha ^*] \right\} \\&\; = \max _{p_+} \left\{ 2\sqrt{p_+(p_+ + \varepsilon )} + 1 - 2p_+ - \varepsilon \mid p_+ + p_+ + \varepsilon \le 1,\, p_+ \in [0, \alpha ^* - \varepsilon ]\right\} \\&\quad \qquad \qquad = {\left\{ \begin{array}{ll} 2\sqrt{\frac{1-\varepsilon }{2}\cdot \frac{1+\varepsilon }{2}} + 1 - (1-\varepsilon ) - \varepsilon = \sqrt{1 - \varepsilon ^2} &{} \text {if } \alpha ^* - \varepsilon > \frac{1-\varepsilon }{2},\\ 2\sqrt{(\alpha ^* - \varepsilon ) \alpha ^*} + 1 + \varepsilon - 2\alpha ^* \le \sqrt{1-\varepsilon ^2}&{}\text {if }\alpha ^* - \varepsilon \le \frac{1-\varepsilon }{2}. \end{array}\right. } \end{aligned}$$

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

$$\begin{aligned} N \ge 2\frac{\ln |U| - \ln (1-\beta )}{|\ln (1-\varepsilon ^2)|}, \end{aligned}$$
(16)

then

$$\begin{aligned} \mathbf P\left\{ \hat{U}_\varphi ^{(N)} \subset U_\varphi ^\varepsilon \right\} \ge \beta . \end{aligned}$$
(17)

Moreover, if it is known that \(\alpha ^* \le \frac{1 + \varepsilon }{2}\), then inequality (17) holds if

$$\begin{aligned} N \ge \frac{\ln |U| - \ln (1-\beta )}{\left| \ln \left( 2\sqrt{(\alpha ^* - \varepsilon ) \alpha ^*} + 1 + \varepsilon - 2\alpha ^* \right) \right| }. \end{aligned}$$
(18)

Proof

First, let us consider the case \(\alpha ^* \le \varepsilon \). Then, it is obvious that

$$ \mathbf P\left\{ \hat{U}_\varphi ^{(N)} \subset U_\varphi ^\varepsilon \right\} = 1, $$

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

$$ \mathbf {P}\left\{ \hat{U}_\varphi ^{(N)} \not \subset U_\varphi ^\varepsilon \right\} \le \inf _{t>0}|U|(M(t))^N \le \left( 2\sqrt{(\alpha ^* - \varepsilon ) \alpha ^*} + 1 + \varepsilon - 2\alpha ^*\right) ^N. $$

Thus, inequality (17) holds if

$$\begin{aligned}&\quad |U|\left( 2\sqrt{(\alpha ^* - \varepsilon ) \alpha ^*} + 1 + \varepsilon - 2\alpha ^*\right) ^N \le 1-\beta \Leftrightarrow \\&N \ge \frac{\ln (1-\beta ) - \ln |U|}{\ln \left( 2\sqrt{(\alpha ^* - \varepsilon ) \alpha ^*} + 1 + \varepsilon - 2\alpha ^*\right) } = \frac{\ln |U| -\ln (1-\beta ) }{\left| \ln \left( 2\sqrt{(\alpha ^* - \varepsilon ) \alpha ^*} + 1 + \varepsilon - 2\alpha ^*\right) \right| }. \end{aligned}$$

Since

$$ 2\sqrt{(\alpha ^* - \varepsilon ) \alpha ^*} + 1 + \varepsilon - 2\alpha ^* \le \sqrt{1-\varepsilon ^2}, $$

we obtain that inequality (17) holds for

$$ N\ge \frac{\ln |U| -\ln (1-\beta ) }{\left| \ln \sqrt{1-\varepsilon ^2}\right| } = 2\frac{\ln |U| -\ln (1-\beta ) }{\left| \ln \left( 1-\varepsilon ^2\right) \right| }. $$

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

$$ N\ge 2\frac{\ln |U| -\ln (1-\beta ) }{\varepsilon ^2}. $$

It is easy to check that

$$ \varepsilon ^2 < \left| \ln \left( 1-\varepsilon ^2\right) \right| $$

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

$$\begin{aligned} N \ge \frac{\ln |U| - \ln (1-\beta )}{\left| \ln \left( 2\sqrt{(\bar{\alpha }- \varepsilon ) \bar{\alpha }} + 1 + \varepsilon - 2\bar{\alpha }\right) \right| }. \end{aligned}$$

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

$$ D \triangleq \sup _{u, v \in U} \Vert u - v \Vert , $$

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.

$$\begin{aligned} |P_\varphi (u) - P_\varphi (v)|\le L\Vert u-v\Vert \end{aligned}$$
(19)

for all \(u, v\in U\).

Theorem 2

Let \(\beta \in (0, 1)\). If the assumption (19) is satisfied and

$$\begin{aligned} N \ge 2\inf _{\gamma \in (0,1)} \frac{n\ln \left\lceil \frac{DL}{(1-\gamma )\varepsilon } \right\rceil - \ln (1-\beta )}{|\ln (1-\gamma ^2\varepsilon ^2)|}, \end{aligned}$$
(20)

then

$$\begin{aligned} \mathbf P\left\{ \hat{U}_\varphi ^{(N)} \subset U_\varphi ^\varepsilon \right\} \ge \beta . \end{aligned}$$
(21)

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

$$ \sup _{u\in U}\hat{P}_\varphi ^{(N)}(u) $$

is attained and is a measurable function of the sample. Thus, the considered event can be represented as

where

$$U_k = \left\{ u\in U :\inf _{v\in U_\varphi ^\varepsilon }\Vert u - v\Vert \ge \frac{1}{k}\right\} .$$

The set \(U_k\) is compact, so the function

$$ (x_1,\ldots , x_N)\mapsto \sup _{u\in U_k}\hat{P}_\varphi ^{(N)}(u) $$

is measurable and, hence,

$$\left\{ \hat{U}_\varphi ^{(N)} \subset U_\varphi ^\varepsilon \right\} \in \mathcal F'.$$

Let \(\tilde{U}\) be a finite subset of U. Let

$$ \nu \triangleq \sup _{u\in U} \inf _{v \in \tilde{U}} \Vert u-v\Vert . $$

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

$$\begin{aligned} |\tilde{U}| \le \left\lceil \frac{D}{\nu }\right\rceil ^n. \end{aligned}$$
(22)

It will be assumed that condition (22) is satisfied.

Let

$$ \tilde{U}_\varphi ^\varepsilon \triangleq \{u\in \tilde{U} :P_\varphi (u) \ge \alpha ^*_{\tilde{U}} - \varepsilon \}, $$

where

$$ \alpha ^*_{\tilde{U}} \triangleq \sup _{u\in \tilde{U}} P_\varphi (u). $$

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

$$\begin{aligned} \left\{ \hat{U}_\varphi ^{(N)} \subset \tilde{U}_\varphi ^{\gamma \varepsilon } \right\} \subset \left\{ \hat{U}_\varphi ^{(N)} \subset U_\varphi ^{\varepsilon } \right\} . \end{aligned}$$
(23)

From (23) and Theorem 1, it follows that

$$ \mathbf P \left\{ \hat{U}_\varphi ^{(N)} \subset U_\varphi ^{\varepsilon } \right\} \ge \mathbf P\left\{ \hat{U}_\varphi ^{(N)} \subset \tilde{U}_\varphi ^{\gamma \varepsilon } \right\} \ge \beta $$

if

$$ N \ge 2\frac{\ln |\tilde{U}| - \ln (1-\beta )}{|\ln (1-\gamma ^2\varepsilon ^2)|} \le 2\frac{\ln \left\lceil \frac{D}{\nu }\right\rceil ^n - \ln (1-\beta )}{|\ln (1-\gamma ^2\varepsilon ^2)|} = 2\frac{n\ln \left\lceil \frac{DL}{(1-\gamma )\varepsilon } \right\rceil - \ln (1-\beta )}{|\ln (1-\gamma ^2\varepsilon ^2)|}. $$

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

$$|P_\varphi (u) - P_\varphi (v)| \leqslant \sup _{w \in U} \Vert \nabla P_\varphi (w)\Vert \Vert u - v\Vert . $$

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

$$ \min _{u\in U}p_u(\varphi _\alpha (u)) > C. $$

As for the probability function, consider the event

$$\begin{aligned} \left\{ \hat{V}_\alpha ^{(N)} \not \subset V_\alpha ^\varepsilon \right\} = \bigcup _{u\in U\setminus V_\alpha ^\varepsilon }\bigcap _{y \in U}\left\{ \hat{\varphi }_\alpha ^{(N)}(u) \leqslant \hat{\varphi }_\alpha ^{(N)} (y)\right\} . \end{aligned}$$

Then we can find an upper bound for the probability

$$\begin{aligned} \mathbf {P}\left\{ \hat{V}_\alpha ^{(N)} \not \subset V_\alpha ^\varepsilon \right\} \le \sum _{u \in U\setminus V_\alpha ^\varepsilon } \mathbf {P} \left( \bigcap _{y \in U} \left\{ \hat{\varphi }_\alpha ^{(N)}(u) \leqslant \hat{\varphi }_\alpha ^{(N)} (y)\right\} \right) . \end{aligned}$$
(24)

Let us fix an optimal solution to the true problem (2) \(u^*\). From (24), we obtain

(25)

Let us define the random variables

$$\begin{aligned} \eta _N = \hat{\varphi }_\alpha ^{(N)} (u^*) - \hat{\varphi }_\alpha ^{(N)} (u),\quad N\in \mathbb N. \end{aligned}$$

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

$$ \mathbf P\{\eta _N \ge 0\}. $$

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:

$$\begin{aligned} \sqrt{N}\left( \varphi _\alpha ^{(N)} (u^*) - \varphi ^*\right) \xrightarrow {d} Z_{u^*} \sim \mathcal {N} \biggl ( 0,\frac{\alpha (1-\alpha )}{p_{u^*}^2(\varphi ^*)} \biggl ), \\ \sqrt{N}\left( \varphi _\alpha ^{(N)} (u) - \varphi _\alpha (u)\right) \xrightarrow {d} Z_u \sim \mathcal {N} \biggl ( 0, \frac{\alpha (1-\alpha )}{p_{u}^2(\varphi _\alpha (u))} \biggl ). \end{aligned}$$

Therefore, we can write

$$\begin{aligned}&\qquad \qquad \lim _{N\rightarrow \infty }\mathbf E \eta _N \le -\varepsilon ,\\&\limsup _{N\rightarrow \infty } \mathbf {var}\left[ \eta _N\sqrt{N}\right] < \frac{4\alpha (1-\alpha )}{C}. \end{aligned}$$

Thus, for any \(0<\varepsilon '<\varepsilon \), there exists \(\tilde{N}(\varepsilon ')\in \mathbb N\) such that

$$\begin{aligned}&\quad \mathbf E\eta _N \le -\varepsilon + \varepsilon ',\end{aligned}$$
(26)
$$\begin{aligned}&\mathbf {var}\left[ \eta _N\right] < \frac{4\alpha (1-\alpha )}{CN} \end{aligned}$$
(27)

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 ')\),

$$\begin{aligned} \mathbf P\{\eta _N \ge 0\}&\le \mathbf P\{\eta _N - \mathbf E \eta _N\ge \varepsilon - \varepsilon '\} \le \frac{\mathbf {var}\left[ \eta _N\right] }{\mathbf {var}\left[ \eta _N\right] + (\varepsilon - \varepsilon ')^2} \\&< \frac{4\alpha (1-\alpha )}{4\alpha (1-\alpha ) + (\varepsilon -\varepsilon ')^2CN}. \end{aligned}$$

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

$$\begin{aligned} \mathbf {P}\left\{ \hat{V}_\alpha ^{(N)} \not \subset V_\alpha ^\varepsilon \right\} \le |U| \frac{4\alpha (1-\alpha )}{4\alpha (1-\alpha ) + (\varepsilon -\varepsilon ')^2CN}. \end{aligned}$$
(28)

for sufficiently large N.

Now, we can obtain the corollary from Theorem 3.

Corollary 1

Let assumptions of Theorem 3 be satisfied. Then

$$ \mathbf {P}\left\{ \hat{V}_\alpha ^{(N)} \subset V_\alpha ^\varepsilon \right\} \ge \beta $$

if

$$\begin{aligned} N \ge \frac{4\alpha (1-\alpha ) (|U| + \beta - 1)}{(1-\beta )(\varepsilon - \varepsilon ')^2C} \end{aligned}$$
(29)

and \(N > \tilde{N}(\varepsilon ')\).

Proof

From (28), it follows that the assertion of the theorem is true if

$$\begin{aligned} |U| \frac{4\alpha (1-\alpha )}{4\alpha (1-\alpha ) + (\varepsilon -\varepsilon ')^2CN} \le 1-\beta . \end{aligned}$$

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.