Abstract Generated abstract
The paper studies a class of nonlinear stochastic programming problems, including nonconvex cases, in which a measurable decision function is constrained by probabilities of membership in random sets and by an expected linear operator inequality. For the case of two probabilistic constraints, the authors reduce an auxiliary problem without the expectation constraint to an extremal problem with integral functionals and give an explicit formula for the optimal lower bound in terms of probabilities of nine set-intersection configurations. They then relate the original and auxiliary problems through weak consistency, showing that under appropriate closure conditions, and in finite-dimensional spaces under ordinary consistency, the optimal values coincide. The paper also describes the structure of nearly admissible minimizing sequences via localized perturbations near finitely many points.
Full Text
UDC 519.3
MATHEMATICS
A. D. IOFFE, D. B. YUDIN
ON SOME PROBLEMS OF NONLINEAR STOCHASTIC PROGRAMMING
(Presented by Academician A. A. Dorodnitsyn, 13 XI 1968)
Problems of planning and control under conditions of incomplete information can be written in terms of stochastic programming (see, for example, (¹)). Published works on stochastic programming concern mainly linear problems. In (²) methods are studied for the numerical solution of convex stochastic conditional extremum problems. In the present paper approaches are considered to the formulation and solution of a fairly broad class of nonlinear (including nonconvex) stochastic problems. A number of known models of stochastic programming fit into the proposed scheme.
1°. Let \((\Omega, F, p)\) be a probability space on the compact set \(\Omega\), and let \(X, Y\) be separable \(B\)-spaces. To each \(\omega \in \Omega\) there are assigned nonempty sets \(G_0(\omega), \ldots, G_n(\omega) \subset X\) and a linear operator \(A(\omega) : X \to Y\) defined on the whole space \(X\).
It is assumed that: a) all the sets \(\{x, \omega : x \in G_i(\omega)\}\), \(i = 0, 1, \ldots, n\), are Borel; b) \(G_0(\omega) \ne X\) with probability 1; c) \(A(\omega)\) is a measurable operator-function, i.e., for any measurable \(x(\omega)\) the function \(y(\omega) = A(\omega)x(\omega)\) is measurable.
Problem I. It is required to minimize
\[ P\{x(\omega) \in G_0(\omega)\} \tag{1} \]
under the conditions
\[ P\{x(\omega) \in G_i(\omega)\} \ge \alpha_i, \qquad i = 1, \ldots, n; \tag{2} \]
\[ M\{A(\omega)x(\omega)\} \le b, \qquad b \in Y. \tag{3} \]
In what follows the case \(n = 2\) is considered. The same methods are applicable also in the general case. The additional difficulties arising here are of a purely combinatorial nature.
2°. Consider the auxiliary Problem II, obtained from Problem I by discarding condition (3).
Problem II. It is required to minimize
\[ P\{x(\omega) \in G_0(\omega)\} \]
under the conditions
\[ P\{x(\omega) \in G_0(\omega)\} \ge \alpha_i, \qquad i = 1, 2. \]
The events corresponding to the following nine situations are pairwise incompatible and the probability of at least one of them is equal to 1.
\[ \begin{aligned} (1)\;& (G_1 \cap G_2) \setminus G_0 \ne \varnothing;\\ (2)\;& \varnothing \ne G_1 \cap G_2 \subset G_0,\; G_1 \setminus G_0 \ne \varnothing,\; G_2 \setminus G_0 \ne \varnothing;\\ (3)\;& \varnothing \ne G_1 \cap G_2 \subset G_0,\; G_1 \setminus G_0 \ne \varnothing,\; G_2 \setminus G_0 = \varnothing;\\ (4)\;& \varnothing \ne G_1 \cap G_2 \subset G_0,\; G_1 \setminus G_0 = \varnothing,\; G_2 \setminus G_0 \ne \varnothing;\\ (5)\;& \varnothing \ne G_1 \cap G_2 \subset G_0,\; G_1 \setminus G_0 = \varnothing,\; G_2 \setminus G_0 = \varnothing;\\ (6)\;& G_1 \cap G_2 = \varnothing,\; G_1 \setminus G_0 \ne \varnothing,\; G_2 \setminus G_0 \ne \varnothing;\\ (7)\;& G_1 \cap G_2 = \varnothing,\; G_1 \setminus G_0 \ne \varnothing,\; G_2 \setminus G_0 = \varnothing;\\ (8)\;& G_1 \cap G_2 = \varnothing,\; G_1 \setminus G_0 = \varnothing,\; G_2 \setminus G_0 \ne \varnothing;\\ (9)\;& G_1 \cap G_2 = \varnothing,\; G_1 \setminus G_0 = \varnothing,\; G_2 \setminus G_0 = \varnothing. \end{aligned} \]
Denote by \(p_i\) the probability of event \((i)\).
Obviously, for the consistency of problem II it is necessary and sufficient that
\[ 0 \leq \alpha_i \leq 1\quad (i=1,2),\qquad \alpha_1+\alpha_2+p_6+p_7+p_8+p_9 \leq 2. \tag{4} \]
In what follows condition (4) is assumed to be satisfied.
Introduce the functions
\[ \varphi_i(x,\omega)= \begin{cases} 1, & x\in G_i(\omega),\\ 0, & x\notin G_i(\omega). \end{cases} \]
Then
\[ P\{x(\omega)\in G_i(\omega)\}=\int_{\Omega}\varphi_i(\omega,x(\omega))\,dp_\omega . \]
Problem II is transformed into an extremal problem with an integral functional and integral constraints, and the methods developed in (3) are applicable to its solution.
Denote by \(S_2(\alpha_1,\alpha_2)\) the required lower bound of the functional (1) under the conditions (2).
Theorem 1. \(S_2(\alpha_1,\alpha_2)\) is equal to the greatest of the following 7 numbers
\[ \begin{aligned} \text{(I)}\quad & \alpha_1+\alpha_2-1-(p_1-p_9),\\ \text{(II)}\quad & \alpha_2-p_1-p_2-p_4-p_6-p_8,\\ \text{(III)}\quad & 2\alpha_1+\alpha_2-2-(p_1-p_8-p_9),\\ \text{(IV)}\quad & \alpha_1-p_1-p_2-p_3-p_6-p_7,\\ \text{(V)}\quad & \alpha_1+2\alpha_2-2-(p_1-p_7-p_9),\\ \text{(VI)}\quad & \frac12\bigl[\alpha_1+\alpha_2-1-(p_1-p_5-p_9)\bigr],\\ \text{(VII)}\quad & 0. \end{aligned} \tag{5} \]
We shall now clarify the nature of the solution of the problem. Consider 7 equations
\[ \begin{aligned} \text{(I)}\quad \varphi_1+\varphi_2-\varphi_0 &= \begin{cases} 2 & \text{in situation } (1),\\ 1 & \text{in } \quad (2)\div(8),\\ 0 & \text{in } \quad (9); \end{cases} \\[0.8em] \text{(II)}\quad \varphi_2-\varphi_0 &= \begin{cases} 1 & \text{in situations } (1),(2),(4),(6),(8),\\ 0 & \text{in } \quad (3),(5),(7),(9); \end{cases} \\[0.8em] \text{(III)}\quad 2\varphi_1+\varphi_2-\varphi_0 &= \begin{cases} 3 & \text{in situation } (1),\\ 2 & \text{in } \quad (2)-(7),\\ 1 & \text{in } \quad (8),(9); \end{cases} \\[0.8em] \text{(IV)}\quad \varphi_1-\varphi_0 &= \begin{cases} 1 & \text{in situations } (1)\div(3),(6),(7),\\ 0 & \text{in } \quad (4),(5),(8),(9); \end{cases} \\[0.8em] \text{(V)}\quad \varphi_1+2\varphi_2-\varphi_0 &= \begin{cases} 3 & \text{in situation } (1),\\ 2 & \text{in } \quad (2)-(6),(8),\\ 1 & \text{in } \quad (7),(9); \end{cases} \\[0.8em] \text{(VI)}\quad \frac{\varphi_1+\varphi_2}{2}-\varphi_0 &= \begin{cases} 1 & \text{in situation } (1),\\ \frac12 & \text{in } \quad (2)-(4),(6)-(8),\\ 0 & \text{in } \quad (5),(9); \end{cases} \\[0.8em] \text{(VII)}\quad \varphi_0&=0. \end{aligned} \tag{6} \]
Theorem 2. Suppose \(S_2(\alpha_1,\alpha_2)\) is equal to the \(i\)-th number of system (5). Then there exists a solution \(x(\omega)\) of problem II satisfying conditions (2) and the \(i\)-th equation of system (6).
\(3^\circ\). Let us return to problem I. We shall call a sequence \(x_n(\omega)\) nearly admissible if
\[ \lim_{n\to\infty} P\{x_n(\omega)\in G_i(\omega)\}\geq \alpha_i,\qquad M\bigl(A(\omega)x_n(\omega)\bigr)=y'_n+y''_n, \]
where \(y'_n \leq b,\; y''_n\to 0\).
If the set of almost admissible sequences is nonempty, then problem I is called weakly consistent. With each almost admissible sequence \(\{x_n(\omega)\}\) we associate the functional
\[ \varliminf_{n\to\infty} P\{x_n(\omega)\in G_0(\omega)\} \]
and denote by \(S(a_1,a_2)\) its greatest lower bound over all almost admissible sequences, and by \(S_1(a_1,a_2)\) the greatest lower bound of (1) in problem I.
Let \(L\) be the set of elements of the space \(Y\) that can be represented in the form
\[ y=M\{A(\omega)x(\omega)\}=\int_\Omega A(\omega)x(\omega)\,dp_\omega . \]
Obviously, \(L\) is a linear manifold.
Theorem 3. Problem I is weakly consistent if and only if problem II is consistent and there exists an element \(y\in \overline{L}\) (the closure of \(L\)) satisfying the inequality \(y\leq b\).
If, moreover, \(Y\) is finite-dimensional, then weak consistency of problem I is equivalent to its consistency.
Theorem 4. If problem I is weakly consistent, then
\[ S(a_1,a_2)=S_2(a_1,a_2). \]
If, moreover, \(Y\) is finite-dimensional, then
\[ S_1(a_1,a_2)=S_2(a_1,a_2). \]
Let \(F\subset \Omega\) be an arbitrary measurable set, and let \(L_F\) be the collection of elements \(y\in Y\) represented in the form
\[ y=\int_F A(\omega)x(\omega)\,dp_\omega . \]
For any \(\omega\in\Omega\), denote by \(L_\omega=\bigcap L_F\), where the intersection is taken over all neighborhoods \(F\) of the point \(\omega\). Finally, let \(\sum_{\omega\in\Omega} L_\omega\) be the collection of all possible finite sums \(y_1+\cdots+y_n,\; y_i\in L_{\omega_i}\).
Theorem 5. Let problem I be weakly consistent. Then for any \(\varepsilon>0\) there exist a function \(x(\omega)\) and a vector \(y\in \sum L_\omega,\; y=y_1+\cdots+y_n,\; y_i\in L_{\omega_i}\), such that:
a) \(P\{x(\omega)\in G_0(\omega)\}\leq S_1(a_1,a_2)+\varepsilon\);
b) \(P\{x(\omega)\in G_i(\omega)\}\geq a_i-\varepsilon,\quad i=1,2;\)
c) \(M\{A(\omega)x(\omega)\}+y=y'+y''\), where \(y'\leq b,\; \|y''\|<\varepsilon\);
d) \(x(\omega)\), with probability \(1-\varepsilon\), satisfies Theorem 2.
Corollary. Let \(Y=R^n\) and let problem I be consistent. Then, if \(x_0(\omega)\) is a solution of problem II, there exist points \(\omega_1,\ldots,\omega_r\) \((r\leq n)\) and vectors \(y_1,\ldots,y_r,\; y_i\in L_{\omega_i}\), such that
\[ M\{A(\omega)x_0(\omega)\}+\sum y_i\leq b . \]
From the last corollary and the definition of \(L_\omega\), the structure of almost admissible minimizing sequences for problem I follows at once. These sequences are formed by functions \(x_n(\omega)\) representable as the sum
\[ x_n(\omega)=x_0(\omega)+\sum_i x_{in}(\omega), \]
where \(x_{in}(\omega)\) is different from zero only in some neighborhood of the point \(\omega_i\), having measure not exceeding \(1/n\), and
\[ \int_\Omega A(\omega)x_{in}(\omega)\,dp_\omega=y_i,\qquad i=1,2,\ldots,r\leq n . \]
Received
11 XI 1968
References
- E. G. Gol’shtein, D. B. Yudin, New Directions in Linear Programming, Moscow, 1966.
- D. B. Yudin, Economics and Mathematical Methods, No. 6 (1968).
- A. D. Ioffe, V. M. Tikhomirov, Doklady Akademii Nauk, 184, No. 4 (1968).