Complexity of general continuous minimization problems: A survey

GAVIANO, MARCO;LERA, DANIELA

2005-01-01

---

Abstract

The problem of finding a local or a global minimum of a real function on a set S, a subset of Rn,  provides a mathematical tool for solving many real world problems. Deterministic and stochastic algorithms have been proposed in the case of f being a general nonlinear function. The numerical cost of these algorithms, that can be the number of function evaluations or the number of elementary operations required when executed, has been investigated in the last few years. In this paper we survey the main results by classifying them according to the field they refer to: local minimization, global minimization and checking the optimality conditions. Further, few results concerning the information that an algorithm may use, are surveyed.