Direct method of hierarchical nonlinear optimization - reassessment after 30 years

• Autorzy: Karbowski A.
• Języki publikacji: EN

Abstrakty

EN

We consider the optimization problems which may be solved by the direct decomposition method. It is possible when the performance index is a monotone function of other performance indices, which depend on two subsets of decision variables: an individual for every inner performance index and a common one for all. Such problems may be treated as a generalization of separable problems with the additive cost and constraints functions. In the paper both the underlying theory and the basic numerical techniques are presented and compared. A special attention is paid to the guarantees of convergence in different classes of problems and to the effectiveness of calculations.

Słowa kluczowe

EN

hierarchical optimization; decomposition; direct method; Benders method; cutting plane method; distributed computations

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2004
• Tom: nr 3
• Strony: 3--11
• Opis fizyczny: Bibliogr. 17 poz.

Twórcy

autor

Karbowski A.

• Research and Academic Computer Network (NASK), Wąwozowa st 18, 02-796 Warsaw, Poland,

Bibliografia

• [1] J. F. Benders, „Partitioning procedures for solving mixed-variables programming problems", Numer. Math., vol. 4, pp. 238-252, 1962.
• [2] D. P. Bertsekas, Nonlinear Programming. 2nd ed. Belmont: Athena Scienti_c, 1999.
• [3] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. Englewood Cliffs: Prentice Hall, 1989.
• [4] S. Elhedhli, J. L. Go_n, and J.-P. Vial, „Nondifferentiable optimization: cutting plane methods", in Encyclopedia of Optimization, C. A. Floudas and P. M. Pardalos, Eds. Dordrecht: Kluwer, 2001, vol. 4, pp. 40-45.
• [5] A. M. Geoffrion, „Generalized Benders decomposition", J. Opt. Theory Appl., vol. 10, pp. 237-260, 1972.
• [6] G. Golub and J. M. Ortega, Scientific Computing: an Introduction with Parallel Computing. San Diego: Academic Press, 1993.
• [7] L. Grippo and M. Sciandrone, „On the convergence of the block nonlinear Gauss-Seidel method under convex constraints", Report R. 467, Istituto di Analisi dei Sistemi ed Informatica, CNDR, Settembre 1998.
• [8] A. Grothey, S. Leyffer, and K. I. M. McKinnon, „A note on feasibility in Benders decomposition", Numerical Analysis Report NA/188, Dundee University, 1999.
• [9] A. V. Fiacco, Introduction to Sensitivity and Stability Analysis in Nonlinear Programming, Mathematics in Science and Engineering. New York: Academic Press, 1983, vol. 165.
• [10] W. Findeisen, F. N. Bailey , M. Brdyś, K. Malinowski, P. Tatjewski, and A. Woźniak, Control and Coordination in Hierarchical Systems. Chichester: Wiley, 1980.
• [11] C. A. Floudas, „Generalized Benders decomposition, GBD", in Encyclopedia of Optimization, C. A. Floudas and P. M. Pardalos, Eds. Dordrecht: Kluwer, 2001, vol. 2, pp. 207-218.
• [12] C. A. Floudas, A. Aggarwal, and A. R. Ciric, „Global optimum search for nonconvex NLP and MINLP problems", Comput. Chem. Eng., vol. 13, no. 10, pp. 1117-1132, 1989.
• [13] C. A. Floudas and V. Visweswaran, „A primal-relaxed dual global optimization approach", J. Opt. Theory Appl., vol. 78, no. 2, pp. 187-225, 1993.
• [14] J. E. Kelley, „The cutting-plane method for solving convex programs", J. Soc. Indust. Appl. Math., vol. 8, pp. 703-712, 1960.
• [15] A. Nemirovski and D. Yudin, Problem Complexity and Method Efficiency in Optimization. Chichester: Wiley, 1983.
• [16] N. Z. Shor, Minimization Methods for Non-differentiable Functions. Berlin: Springer Verlag, 1985.
• [17] Optimization Methods for Large-Scale Systems with Applications, D. A. Wismer, Ed. New York: McGraw-Hill, 1971.