×

Deterministic global optimization with partition sets whose feasibility is not known: Application to concave minimization, reserve convex constraints, DC-programming and Lipschitzian optimization. (English) Zbl 0621.90064

A crucial problem for many global optimization methods is how to handle partition sets whose feasibility is not known. This problem is solved for broad classes of feasible sets including convex sets, sets defined by finitely many convex and reverse convex constraints and sets defined by Lipschitzian inequalities. Moreover, a fairly general theory of bounding is presented and applied to concave objective functions, to functions representable as differences of two convex functions, and to Lipschitzian functions. The resulting algorithms allow to solve any global optimization problem whose objective function is of one of these forms and whose feasible set belongs to one of the above classes. In this way, several new fields of optimization are opened to the application of global methods.

MSC:

90C30 Nonlinear programming
49M37 Numerical methods based on nonlinear programming
65H10 Numerical computation of solutions to systems of equations
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Falk, J., andSoland, R. M.,An Algorithm for Separable Nonconvex Programming Problems, Management Science, Vol. 15, pp. 550-569, 1969. · Zbl 0172.43802 · doi:10.1287/mnsc.15.9.550
[2] Horst, R.,An Algorithm for Nonconvex Programming Problems, Mathematical Programming, Vol. 10, pp. 312-321, 1976. · Zbl 0337.90062 · doi:10.1007/BF01580678
[3] Horst, R.,A Note on the Convergence of an Algorithm for Nonconvex Programming Problems, Mathematical Programming, Vol. 19, pp. 237-238, 1980. · Zbl 0437.90069 · doi:10.1007/BF01581645
[4] Benson, H. P.,On the Convergence of Two Branch-and-Bound Algorithms for Nonconvex Programming Problems, Journal of Optimization Theory and Applications, Vol. 36, pp. 129-134, 1982. · Zbl 0453.65046 · doi:10.1007/BF00934342
[5] Benson, H. P.,A Finite Algorithm for Concave Minimization over a Polyhedron, Naval Research Logistic Quarterly, Vol. 32, pp. 165-177, 1985. · Zbl 0581.90080 · doi:10.1002/nav.3800320119
[6] Rosen, J. B.,Global Minimization of a Linearly Constrained Concave Function by Partition of the Feasible Domain, Mathematics of Operations Research, Vol. 8, pp. 215-230, 1983. · Zbl 0526.90072 · doi:10.1287/moor.8.2.215
[7] Thaoi, N., andTuy, H.,Convergent Algorithms for Minimizing a Concave Function, Mathematics of Operations Research, Vol. 5, pp. 556-566, 1980. · Zbl 0472.90054 · doi:10.1287/moor.5.4.556
[8] Tuy, H., Thieu, T. V., andThai, N. Q.,A Conical Algorithm for Globally Minimizing a Concave Function over a Closed Convex Set, Mathematics of Operations Research, Vol. 10, pp. 498-514, 1985. · Zbl 0579.90078 · doi:10.1287/moor.10.3.498
[9] Al-Khayyal, F. A., andFalk, J.,Jointly Constrained Biconvex Programming, Mathematics of Operations Research, Vol. 8, pp. 273-386, 1983. · Zbl 0521.90087 · doi:10.1287/moor.8.2.273
[10] Horst, R.,On the Global Minimization of Concave Functions: Introduction and Survey, Operations Research Spektrum, Vol. 6, pp. 195-205, 1984. · Zbl 0551.65043 · doi:10.1007/BF01720068
[11] Pardalos, P. M., andRosen, J. B.,Methods for Global Concave Minimization: A Bibliographic Survey, SIAM Review, Vol. 28, 367-379, 1986. · Zbl 0602.90105 · doi:10.1137/1028106
[12] Pardalos, P. M., andRosen, J. B.,Constrained Global Optimization: Algorithms and Applications, Lecture Notes in Computer Science 268, Springer, Berlin, Germany, 1987. · Zbl 0638.90064
[13] Horst, R.,A General Class of Branch-and-Bound Methods in Global Optimization with Some New Approaches for Concave Minimization, Journal of Optimization Theory and Applications, Vol. 51, pp. 271-291, 1986. · Zbl 0581.90073 · doi:10.1007/BF00939825
[14] Soland, R. M.,An Algorithm for Separable Nonconvex Programming Problems, II: Nonconvex Constraints, Management Science, Vol. 17, pp. 759-773, 1971. · Zbl 0226.90038 · doi:10.1287/mnsc.17.11.759
[15] Horst, R., andDien, L. V.,Minimizing a DC Function Subject to Convex and Reverse Convex Constraints, Preprint, University of Trier, Trier, Germany, 1987.
[16] Tuy, H., andHorst, R.,Convergence and Restart in Branch-and-Bound Algorithms for Global Optimization. Applications to Concave Minimization and DC Optimization Problems, Mathematical Programming (to appear). · Zbl 0651.90063
[17] Horst, R., andTuy, H.,On the Convergence of Global Methods in Multiextremal Optimization, Journal of Optimization Theory and Applications, Vol. 54, pp. 253-271, 1987. · Zbl 0595.90079 · doi:10.1007/BF00939434
[18] Tuy, H.,Concave Programming under Linear Constraints, Soviet Mathematics, Vol. 5, pp. 1437-1440, 1964. · Zbl 0132.40103
[19] Zwart, P. B.,Nonlinear Programming: Counterexamples to Global Optimization Algorithms by Ritter and Tuy, Operations Research, Vol. 21, pp. 1260-1266, 1973. · Zbl 0274.90049 · doi:10.1287/opre.21.6.1260
[20] Zwart, P. B.,Global Maximization of a Convex Function with Linear Inequality Constraints, Operations Research, Vol. 22, pp. 602-609, 1974. · Zbl 0322.90049 · doi:10.1287/opre.22.3.602
[21] Jacobsen, S. E.,Convergence of a Tuy-Type Algorithm for Concave Minimization Subject to Linear Constraints, Applied Mathematics and Optimization, Vol. 7, pp. 1-9, 1981. · Zbl 0452.90060 · doi:10.1007/BF01442106
[22] Tuy, H.,On Polyhedral Annexation Method for Concave Minimization, Preprint, Institute of Mathematics, Hanoi, Vietnam, 1987.
[23] Pintèr, J..,Globally Convergent Methods for n-Dimensional Multiextremal Optimization, Optimization, Vol. 17, pp. 187-202, 1986. · Zbl 0595.90071 · doi:10.1080/02331938608843118
[24] Pintèr, J.,Extended Univariate Algorithms for n-Dimensional Global Optimization, Computing, Vol. 36, pp. 91-103, 1986. · Zbl 0572.65047 · doi:10.1007/BF02238195
[25] Pintèr, J.,Branch-and-Bound Algorithms for Solving Multiextremal Mathematical Programming Problems with Lipschitzian Structure, Working Paper, VITUKI, Budapest, Hungary, 1987.
[26] Fedorov, V. V., Editor,Problems of Cybernetics. Models and Methods in Global Optimization, USSR Academy of Sciences, Moscow, USSR, 1985 (in Russian).
[27] Strongin, R. G.,Numerical Methods for Multiextremal Problems, Nauka, Moscow, USSR, 1978 (in Russian). · Zbl 0458.65062
[28] Strongin, R. G.,Numerical Methods for Multiextremal Nonlinear Programming Problems with Nonconvex Constraints, Nondifferentiable Optimization: Motivations and Applications, Proceedings of IIASA Workshop, Sopron, Hungary, 1984; Edited by V. F. Demyanov and D. Pallaschke, IIASA, Laxenburg, Austria, 1984.
[29] Zilinskas, A.,Axiomatic Characterization of a Global Optimization Algorithm and Investigations of its Search Strategy, Operations Research Letters, Vol. 4, pp. 35-39, 1985. · Zbl 0568.90082 · doi:10.1016/0167-6377(85)90049-5
[30] Galperin, E. A.,The Cubic Algorithm, Journal of Mathematical Analysis and Applications, Vol. 112, pp. 635-640, 1985. · Zbl 0588.65042 · doi:10.1016/0022-247X(85)90268-9
[31] Pijavskii, S. A.,An Algorithm for Finding the Absolute Extremum of a Function, USSR Computational Mathematics and Mathematical Physics, Vol. 12, pp. 57-67, 1972. · Zbl 0282.65052 · doi:10.1016/0041-5553(72)90115-2
[32] Shubert, B. O.,A Sequential Method Seeking the Global Maximum of a Function, SIAM Journal on Numerical Analysis, Vol. 9, pp. 379-388, 1972. · Zbl 0251.65052 · doi:10.1137/0709036
[33] Mladineo, R. H.,An Algorithm for Finding the Global Maximum of a Multimodal, Multivariate Function, Mathematical Programming, Vol. 34, 188-200, 1986. · Zbl 0598.90075 · doi:10.1007/BF01580583
[34] Galperin, E. A.,The Beta Algorithms for Mathematical Programming, Proceedings of the 1986 Conference on Information Sciences and Systems, Department of Electrical Engineering, Princeton University, Princeton, New Jersey, pp. 318-320, 1986.
[35] Horst, R.,On Solving Lipschitzian Global Optimization Problems, Acta Mathematica Vietnamica (to appear). · Zbl 0651.90074
[36] Rockafellar, R. T.,Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970. · Zbl 0193.18401
[37] Tuy, H., Khatchaturov, V., andUtkin, S.,A Class of Exhaustive Cone Splitting Procedures in Conical Algorithms for Concave Minimization, Optimization (to appear). · Zbl 0637.90074
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.