A deterministic algorithm for global optimization (Q1803605): Difference between revisions

Consider the global optimization problem (1) \(\max_{x\in X} f(x)\), where \(f: X\to\mathbb{R}^ 1\) is a differentiable function and \(X\subset \mathbb{R}^ m\) is a compact polytope. To solve (1) the author presents a deterministic space covering algorithm strictly related to algorithms introduced in the literature by \textit{B. O. Shubert} [SIAM J. Numer. Analysis 9, No. 3, 379--388 (1972; Zbl 0251.65052)] and by \textit{R. H. Mladineo} [Math. Program. 34, 188--200 (1986; Zbl 0598.90075)]. While those authors assumed \(f\) to satisfy the Lipschitz condition, in this paper the following condition is assumed to hold: \[ f(x)\leq f(y)+ \nabla f(y)'(x- y)+ K\| x- y\|^ 2\quad\text{for any }x,y\in X, \] where \(K\) is a known constant. This leads to simpler geometric properties. The main idea of the algorithm is to construct a sequence of upper envelopes for \(f\); their global maxima are easily found and converge to the solution of (1). An implementation of the algorithm has been tested in solving standard test functions; the results are reported.