×

zbMATH — the first resource for mathematics

Semistochastic decomposition scheme in mathematical programming and game theory. (English) Zbl 0749.90075
Summary: This work deals with the optimization problem \(\sup_{x\in X}\inf_{y\in Y} S(x,y)\), which plays undoubtedly a crucial part in mathematical programming and game theory. On the basis of probability theory, a solution approach — semistochastic decomposition — is proposed. This method is finite with probability 1 without any hypothesis about convexity or differentiability as it is usually required in traditional methods.
MSC:
90C30 Nonlinear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
91A05 2-person games
PDF BibTeX XML Cite
Full Text: Link EuDML
References:
[1] G. B. Dantzig, P. Wolfe: The decomposition algorithm for linear programs. Econometrica 29 (1961), 4, 767-778. · Zbl 0104.14305 · doi:10.2307/1911818
[2] J. F. Benders: Partitioning procedures for solving mixed variable programming problems. Numer. Math. 4 (1962), 238-260. · Zbl 0109.38302
[3] A. Geoffrion: Generalized Benders decomposition. J. Optim. Theory Appl. 10 (1972), 237-260. · Zbl 0229.90024 · doi:10.1007/BF00934810
[4] T. J. Van Roy: Cross decomposition for mixed integer programming. Mathematical Programming 25 (1983), 46-63. · Zbl 0505.90057 · doi:10.1007/BF02591718
[5] I. Kornai, T. Liptak: Planning on two levels. Application of Mathematics in Economical Research 4, Moscow 1965. In Russian. · Zbl 0127.36703 · doi:10.2307/1911892
[6] R. E. Burkard H. W. Hamacher, J. Tind: On general decomposition schemes in mathematical programming. Mathematical Programming Study 24 (1985), 238-252. · Zbl 0588.90093 · doi:10.1007/BFb0121054
[7] V. Z. Belinskij V. A. Volkonskii S. A. Ivankov A. B. Pomanskii, A. D. Shapiro: Iterative Methods in Game Theory and Mathematical Programming. Nauka, Moscow 1974. In Russian.
[8] V. V. Fedorov: Maximin Numerical Methods. Nauka, Moscow 1979.
[9] I. Ekeland, R. Temam: Analyse Convexe et Problemes Variationnels. Dunod, Paris 1974. · Zbl 0281.49001
[10] G. D. Maistrovskii: Gradient methods for finding saddle points. Econom. i Mat. Metody 12 (1976), 917-929. In Russian.
[11] E. G. Golstein: Gradient methods for determination of saddle points and modified Lagrangians. Proc. of the Workshop ,,Math. Optimierung - Theorie und Anwendungen” Wartburg/Eisenach 1983.
[12] R. T. Rockafellar: A dual approach to solving nonlinear programming problems by un- constrained optimization. Math. Programming 5 (1973), 354-373. · Zbl 0279.90035
[13] Tran Quoc Chien: Nondifferentiable and quasidifferentiable duality in vector optimization theory. Kybernetika 21 (1985), 4, 298-321. · Zbl 0579.90091 · eudml:28603
[14] Tran Quoc Chien: Fenchel-Lagrange duality in vector fractional programming via abstract duality scheme. Kybernetika 22 (1986), 4, 299-319. · Zbl 0616.90081 · eudml:27529
[15] Tran Quoc Chien: Perturbation theory of duality in vector optimization via the abstract duality scheme. Kybernetika 23 (1987), 1, 67-81. · Zbl 0615.49007 · eudml:27925
[16] Tran Quoc Chien: Vector nonconvex perturbational duality theory via the abstract duality scheme. Essays on Nonlinear Analysis and Optimization Problems. Ha-Noi 1987. · Zbl 0652.90092
[17] B. Gnedenko: The Theory of Probability. Nauka, Moscow 1973. · Zbl 0191.46702
[18] N. N. Vorobiev: Elements of Game Theory: Noncooperative Games. Nauka, Moscow 1984.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.