Abstract Generated abstract
This paper formulates a class of convex stochastic programming problems in which the objective coefficients and constraint matrix elements are random variables with given second moments. By representing the decision variables in Hilbert spaces of square integrable random variables, the problem is reduced to maximizing a linear functional subject to deterministic expectation constraints and norm bounds. Under Slater’s condition and a nondegeneracy assumption excluding functional dependence between objective and constraint coefficients, the solution is characterized through a finite dimensional deterministic convex minimization problem for Lagrange multipliers. The paper also notes that cases violating these assumptions can be treated by feasible direction methods adapted to convex programming in Hilbert space.
Full Text
UDC 519.212.3+519.3
MATHEMATICS
D. B. Yudin
ON ONE CLASS OF STOCHASTIC PROGRAMMING PROBLEMS
(Presented by Academician L. V. Kantorovich on 12 VII 1967)
1. Let the components of the vector \(C=(c_1,\ldots,c_n)\) and the elements of the matrix
\(A=\|a_{ij}\|_{m\times n}\) be random variables defined on the probability space
\((\Omega,F,P)\). It is assumed that the second moments of the distribution of the system of random variables \(\{c_j,a_{ij}\}\) are given.
We formulate the following problem of convex stochastic programming.
It is required to determine a random vector \(X=(x_1,\ldots,x_n)\) at which the maximum is attained
\[ \mathrm{M}\left\{\sum_{j=1}^{n} c_j x_j\right\} \tag{1} \]
under the conditions
\[ \mathrm{M}\left\{\sum_{j=1}^{n} a_{ij}x_j\right\}\leq b_i,\qquad i=1,2,\ldots,m, \tag{2} \]
\[ \mathrm{M}\{x_j^2\}\leq d_j^2,\qquad j=1,2,\ldots,n, \tag{3} \]
where \(b_i,\ i=1,2,\ldots,m,\) and \(d_j,\ j=1,2,\ldots,n,\) are given numbers.
Consider, on the probability space \((\Omega,F,P)\), the Hilbert spaces \(H_j\) of random variables \(\xi_j\) with bounded mathematical expectation and bounded variance \((|\mathrm{M}\xi_j|<\infty,\ \mathrm{M}\{\xi_j^2\}<\infty)\), with scalar product \((\xi_j^{(1)},\xi_j^{(2)})=\mathrm{M}(\xi_j^{(1)}\xi_j^{(2)})\). Let the Hilbert space \(H\) be the Cartesian product \(H_j,\ j=1,2,\ldots,n\).
In terms of the Hilbert space, problem (1)—(3) takes the form
\[ \sum_{j=1}^{n} (c_j,x_j)\to \max, \tag{4} \]
\[ \sum_{j=1}^{n} (a_{ij},x_j)\leq b_i,\qquad i=1,2,\ldots,m, \tag{5} \]
\[ \|x_j\|\leq d_j,\qquad j=1,2,\ldots,n. \tag{6} \]
We adopt the following assumptions.
a) The set defined by conditions (5)—(6) contains an interior point (satisfies Slater’s condition).
b) The parameters \(c_j,\ j=1,2,\ldots,n,\) of the linear form (4) cannot be represented as linear combinations (with nonnegative coefficients) of the components of the corresponding vectors of constraints
\[ \Delta_j=c_j-\sum_{i=1}^{m}\lambda_i a_{ij}\neq 0,\qquad j=1,2,\ldots,n,\qquad \lambda_i\geq 0,\quad i=1,2,\ldots,m. \]
Conditions b), which have no meaning for deterministic extremal problems, should be regarded as natural for stochastic programming problems. They mean that, for each \(j\), the random variables \(c_j\) and \(a_{ij}\) are not functionally dependent.
- Theorem 1. The components \(x_j^*\) of the solution of problem (4)—(6) are computed from the relations
\[ x_j^* = d_j \Delta_j^*/\|\Delta_j^*\|,\qquad j=1,2,\ldots,n, \tag{7} \]
where the random variables
\[ \Delta_j^* = c_j - \sum_{i=1}^{m}\lambda_i^* a_{ij}, \]
\(\lambda_i^*,\ i=1,2,\ldots,m,\) are the components of the deterministic vector \(\Lambda^* = (\lambda_1^*,\ldots,\lambda_m^*)\), at which the value
\[ \min_{\Lambda\geq 0}\left\{\sum_{i=1}^{m}\lambda_i b_i+\sum_{j=1}^{n} d_j \|\Delta_j\|\right\}. \tag{8} \]
is attained.
The proof of the theorem is based on methods for constructing pairs of dual problems of mathematical programming in functional spaces, formulated in \((^1)\).
The solution of problem (8) of deterministic convex programming is obtained without difficulty, for example, by the Gauss—Seidel coordinate minimization method.
- For solving stochastic programming problems of the form (1)—(3) in which either of conditions a), b) is not satisfied (for example, for problems in which, for some \(j\), the coefficients \(c_j\) and all \(a_{ij},\ i=1,2,\ldots,m,\) are nonrandom), one may use the method of feasible directions, generalized and adapted for the numerical solution of convex programming problems in Hilbert space \((^2)\).
Received
28 VI 1967
CITED LITERATURE
\(^1\) E. G. Gol’shtein, DAN, 172, No. 5 (1967). \(\quad\) \(^2\) S. I. Zukhovitskii, R. A. Polyak, M. E. Primak, DAN, 163, No. 2 (1965).