Global optimization of univariate Lipschitz functions: II. New algorithms and computational comparison. Hansen, P., Jaumard, B., & Lu, S. Mathematical Programming, 55(1):273–292, Apr, 1992.
Global optimization of univariate Lipschitz functions: II. New algorithms and computational comparison [link]Paper  doi  abstract   bibtex   
We consider the following global optimization problems for a Lipschitz functionf implicitly defined on an interval [a, b]. Problem P´x: find a globally$ε$-optimal value off and a corresponding point; Problem Q\textacutedbl: find a set of disjoint subintervals of [a, b] containing only points with a globally$ε$-optimal value and the union of which contains all globally optimal points. A two-phase algorithm is proposed for Problem P´x. In phase I, this algorithm obtains rapidly a solution which is often globally$ε$-optimal. Moreover, a sufficient condition onf for this to be the case is given. In phase II, the algorithm proves the$ε$-optimality of the solution obtained in phase I or finds a sequence of points of increasing value containing one with a globally$ε$-optimal value. The new algorithm is empirically compared (on twenty problems from the literature) with a best possible algorithm (for which the optimal value is assumed to be known), with a passive algorithm and with the algorithms of Evtushenko, Galperin, Shen and Zhu, Piyavskii, Timonov and Schoen. For small$ε$, the new algorithm requires only a few percent more function evaluations than the best possible one. An extended version of Piyavskii's algorithm is proposed for problem Q\textacutedbl. A sufficient condition onf is given for the globally optimal points to be in one-to-one correspondance with the obtained intervals. This result is achieved for all twenty test problems.
@Article{Hansen1992c,
    author      = {Hansen, Pierre and Jaumard, Brigitte and Lu, Shi-Hui},
    title       = {Global optimization of univariate Lipschitz functions: II. New algorithms and computational comparison},
    doi         = {10.1007/BF01581203},
    issn        = {1436-4646},
    journal     = {Mathematical Programming},
    month       = {Apr},
    number      = {1},
    pages       = {273--292},
    url         = {https://doi.org/10.1007/BF01581203},
    volume      = {55},
    year        = {1992},
    abstract    = {We consider the following global optimization problems for a Lipschitz functionf implicitly defined on an interval [a, b]. Problem P{\textasciiacutex}: find a globally$\epsilon$-optimal value off and a corresponding point; Problem Q{\textacutedbl}: find a set of disjoint subintervals of [a, b] containing only points with a globally$\epsilon$-optimal value and the union of which contains all globally optimal points. A two-phase algorithm is proposed for Problem P{\textasciiacutex}. In phase I, this algorithm obtains rapidly a solution which is often globally$\epsilon$-optimal. Moreover, a sufficient condition onf for this to be the case is given. In phase II, the algorithm proves the$\epsilon$-optimality of the solution obtained in phase I or finds a sequence of points of increasing value containing one with a globally$\epsilon$-optimal value. The new algorithm is empirically compared (on twenty problems from the literature) with a best possible algorithm (for which
                  the optimal value is assumed to be known), with a passive algorithm and with the algorithms of Evtushenko, Galperin, Shen and Zhu, Piyavskii, Timonov and Schoen. For small$\epsilon$, the new algorithm requires only a few percent more function evaluations than the best possible one. An extended version of Piyavskii's algorithm is proposed for problem Q{\textacutedbl}. A sufficient condition onf is given for the globally optimal points to be in one-to-one correspondance with the obtained intervals. This result is achieved for all twenty test problems.}
}

Downloads: 0