Direct method of hierarchical nonlinear optimization - reassessment after 30 years
DOI:
https://doi.org/10.26636/jtit.2004.3.257Keywords:
hierarchical optimization, decomposition, the direct method, Benders method, cutting plane method, distributed computationsAbstract
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.
Downloads
References
[1] J. F. Benders, "Partitioning procedures for solving mixed-variables programming problems", Numer. Math., vol. 4, pp. 238-252, 1962.
View in Google Scholar
[2] D. P. Bertsekas, Nonlinear Programming. 2nd ed. Belmont: Athena Scientific, 1999.
View in Google Scholar
[3] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. Englewood Cliffs: Prentice Hall, 1989.
View in Google Scholar
[4] S. Elhedhli, J. L. Goffin, 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.
View in Google Scholar
[5] A. M. Geoffrion, "Generalized Benders decomposition", J. Opt. Theory Appl., vol. 10, pp. 237-260, 1972.
View in Google Scholar
[6] G. Golub and J. M. Ortega, Scientific Computing: an Introduction with Parallel Computing. San Diego: Academic Press, 1993.
View in Google Scholar
[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.
View in Google Scholar
[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.
View in Google Scholar
[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.
View in Google Scholar
[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.
View in Google Scholar
[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.
View in Google Scholar
[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.
View in Google Scholar
[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.
View in Google Scholar
[14] J. E. Kelley, "The cutting-plane method for solving convex programs", J. Soc. Indust. Appl. Math., vol. 8, pp. 703-712, 1960.
View in Google Scholar
[15] A. Nemirovski and D. Yudin, Problem Complexity and Method Efficiency in Optimization. Chichester: Wiley, 1983.
View in Google Scholar
[16] N. Z. Shor, Minimization Methods for Non-differentiable Functions. Berlin: Springer Verlag, 1985.
View in Google Scholar
[17] Optimization Methods for Large-Scale Systems with Applications, D. A. Wismer, Ed. New York: McGraw-Hill, 1971.
View in Google Scholar
Downloads
Submitted
Published
Issue
Section
License
Copyright (c) 2004 Journal of Telecommunications and Information Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
