Abstract
In this paper we propose an algorithm using only the values of the objective function and constraints for solving one-dimensional global optimization problems where both the objective function and constraints are Lipschitzean and nonlinear. The constrained problem is reduced to an unconstrained one by the index scheme. To solve the reduced problem a new method with local tuning on the behavior of the objective function and constraints over different sectors of the search region is proposed. Sufficient conditions of global convergence are established. We also present results of some numerical experiments.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Archetti, F. and F. Schoen (1984), A survey on the global optimization problems: general theory and computational approaches,Annals of Operations Research,1, 87–110.
Breiman, L. and A. Cutler (1993), A deterministic algorithm for global optimization,Math. Programming,58, 179–199.
Bulatov, V.P. (1977),Embedding Methods in Optimization Problems, Nauka, Novosibirsk, (In Russian).
Csendes, T. (1989), An interval method for bounding level sets of parameter estimation problems,Computing,41, 75–86.
Dixon, L.C.W. and G.P. Szegö (1978),Towards global optimization, 2, North-Holland, Amsterdam.
Evtushenko, Yu.G., M.A. Potapov and V.V. Korotkich (1992), Numerical methods for global optimization,Recent Advances in Global Optimization, ed. by C.A. Floudas and P.M. Pardalos, Princeton University Press, Princeton.
Hansen, P., B. Jaumard and S.-H. Lu (1992), Global optimization of univariate Lipschitz functions: 1–2,Math. Programming,55, 251–293.
Horst, R. and H. Tuy (1993),Global Optimization — Deterministic Approaches, Springer-Verlag, Berlin.
Lucidi, S. (1994), On the role of continuously differentiable exact penalty functions in constrained global optimization,J. of Global Optimization,5, 49–68.
Markin, D.L. and R.G. Strongin (1987), A method for solving multi-extremal problems with non-convex constraints, that uses a priori information about estimates of the optimum,USSR Computing Mathematics and Mathematical Physics,27(1), 33–39.
Mladineo, R. (1992), Convergence rates of a global optimization algorithm,Math. Programming,54, 223–232.
Pardalos, P.M. and J.B. Rosen (1990), Eds.,Computational Methods in Global Optimization,Annals of Operations Research,25.
Pintér, J. (1992), Convergence qualification of adaptive partition algorithms in global optimization,Math. Programming,56, 343–360.
Ratschek, H. and J. Rokne (1988),New Computer Methods for Global Optimization, Ellis Horwood, Chichester.
Rinnooy Kan, A.H.G. and G.H. Timmer (1989), Global optimization,Optimization, Ed. by G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd, North-Holland, Amsterdam.
Sergeyev, Ya.D. (1994), An algorithm for finding the global minimum of multiextremal Lipschitz functions, inOperations Research '93, eds. A. Bachem, U. Derigs, M. Junger, R. Schrader, Physica-Verlag, 463–465.
Sergeyev, Ya.D. (1995), An information global optimization algorithm with local tuning, to appear inSIAMJ. Optimization.
Sergeyev, Ya.D. (1995), A one-dimensional deterministic global minimization algorithm, to appear inComputing Mathematics and Mathematical Physics.
Sergeyev, Ya.D. and V.A. Grishagin (1994), A parallel method for finding the global minimum of univariate functions,J. Optimization Theory and Applications,80(3), 513–536.
Strongin, R.G. (1978),Numerical Methods on Multiextremal Problems, Nauka, Moscow, (In Russian).
Strongin, R.G. (1989), The information approach to multiextremal optimization problems, Stochastics & Stochastics Reports,27, 65–82.
Strongin, R.G. (1992), Algorithms for multi-extremal mathematical programming problems employing the set of joint space-filling curves,J. of Global Optimization,2, 357–378.
Strongin, R.G. and D.L. Markin (1986), Minimization of multiextremal functions with nonconvex constraints,Cybernetics,22(4), 486–493.
Strongin, R.G. and Ya.D. Sergeyev (1992), Global multidimensional optimization on parallel computer,Parallel Computing,18, 1259–1273.
Sukharev, A.G. (1989),Minmax Algorithms inProblems of Numerical Analysis, Nauka, Moscow, (In Russian).
Törn, A. and A. Žilinskas (1989),Global Optimization, Springer-Verlag, Lecture Notes in Computer Science,350.
Vasiliev, F.P. (1988),Numerical Methods for Solving Extremal Problems, Nauka, Moscow, (In Russian).
Zhang, Baoping, G.R. Wood and W.P. Baritompa (1993), Multidimensional bisection: the performance and the context,J. of Global Optimization,3, 337–358.
Zhigljavsky, A.A. (1991),Theory of Global Random Search, Kluwer Academic Publishers, Dordrecht.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Sergeyev, Y.D., Markin, D.L. An algorithm for solving global optimization problems with nonlinear constraints. J Glob Optim 7, 407–419 (1995). https://doi.org/10.1007/BF01099650
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01099650