Abstract
This work considers some methods for searching for the absolute (global) minimum of functions having concave minorants on bounded convex sets. Special methods for minimizing Lipschitz and concave functions are proposed. The methods are based on deeper cuts that use second-order information. The possibility of applying some cutting schemes that solve convex programming problems for the global minimization of concave functions on bounded convex sets is analyzed. A new original class of cuts, and a new method for minimizing concave functions, are presented. The work also considers a new approach for the solution of multi-extremal problems that is different from cutting methods. It is based on the approximation of convex sets by the convex envelopes over the convex hull of a finite number of points. This work comes close to the studies by Tuy [1,8].
Similar content being viewed by others
References
H. Tuy, Concave programming with linear constraints, Dokl. AN SSSR 159 (1964) 32–35.
V. P. Bulatov and L.I. Kasinskaya, Some methods for concave function minimization and their applications,Metody Optimizatsii i ih Prilozheniya (Nauka. Sib. Otd-nie, Novosibirsk, 1982) pp. 71–80.
V.P. Bulatov,The Imbedding Methods in Optimization Problems (Nauka. Sib. otd-nie, Novosibirsk, 1977).
L.T. Ashchepkov et al.,Methods for Solving Problems of Mathematical Programming and Optimal Control (Nauka. Sib otd-nie, Novosibirsk, 1984) p. 7–43.
J.E. Kelley, The cutting-plane method for solving convex programming, SIAM J. 8 (1960) 703–712.
J.B. Rosen, Iterative solution of nonlinear optimal control problems, SIAM J. Control (1966) 223–244.
V.P. Bulatov, The methods for solving multiextremal problems,Metody Chislennogo Analiza i Optimizatsii (Nauka, Novosibirsk, 1987).
H. Tuy and R. Horst, Convergence and restart in branch-and-bound algorithms for global optimization. Application to concave minimization and d.c. optimization problems, Math. Progr. 41 (1988) pp. 161–185.
N.I. Merenkova,Mathematical Models for Optimizing the Laying and Structure of Pipeline Systems (SEI, Irkutsk, 1977) p. 145.
V.P. Bulatov,Approximation Methods for Solving Some Problems of Mathematical Programming (Prikladnaya matematika, Irkutsk, 1969).
Author information
Authors and Affiliations
Additional information
Editors' note: The original manuscript was edited by Faiz Al-Khayyal and Panos Pardalos. In this process, we endeavoured to focus only on corrections (both technical and grammatical) and on the insertion of clarifying phrases and passages. Major insertions are flagged by footnotes. The revised manuscript was typed in TEX by Carmella Bell of Georgia Tech.
Rights and permissions
About this article
Cite this article
Bulatov, V.P. Methods for solving multi-extremal problems (global search). Ann Oper Res 25, 253–277 (1990). https://doi.org/10.1007/BF02283699
Issue Date:
DOI: https://doi.org/10.1007/BF02283699