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]](https://bibbase.org/img/filetypes/link.svg "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
{"_id":"T9Abstq8a2McK89sj","bibbaseid":"hansen-jaumard-lu-globaloptimizationofunivariatelipschitzfunctionsiinewalgorithmsandcomputationalcomparison-1992","author_short":["Hansen, P.","Jaumard, B.","Lu, S."],"bibdata":{"bibtype":"article","type":"article","author":[{"propositions":[],"lastnames":["Hansen"],"firstnames":["Pierre"],"suffixes":[]},{"propositions":[],"lastnames":["Jaumard"],"firstnames":["Brigitte"],"suffixes":[]},{"propositions":[],"lastnames":["Lu"],"firstnames":["Shi-Hui"],"suffixes":[]}],"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´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.","bibtex":"@Article{Hansen1992c,\n author = {Hansen, Pierre and Jaumard, Brigitte and Lu, Shi-Hui},\n title = {Global optimization of univariate Lipschitz functions: II. New algorithms and computational comparison},\n doi = {10.1007/BF01581203},\n issn = {1436-4646},\n journal = {Mathematical Programming},\n month = {Apr},\n number = {1},\n pages = {273--292},\n url = {https://doi.org/10.1007/BF01581203},\n volume = {55},\n year = {1992},\n 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\n 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.}\n}\n\n","author_short":["Hansen, P.","Jaumard, B.","Lu, S."],"key":"Hansen1992c","id":"Hansen1992c","bibbaseid":"hansen-jaumard-lu-globaloptimizationofunivariatelipschitzfunctionsiinewalgorithmsandcomputationalcomparison-1992","role":"author","urls":{"Paper":"https://doi.org/10.1007/BF01581203"},"metadata":{"authorlinks":{}},"downloads":0,"html":""},"bibtype":"article","biburl":"https://raw.githubusercontent.com/mdolab/bib-file/refs/heads/master/mdolab.bib","dataSources":["qAPjQpsx8e9aJNrSa"],"keywords":[],"search_terms":["global","optimization","univariate","lipschitz","functions","new","algorithms","computational","comparison","hansen","jaumard","lu"],"title":"Global optimization of univariate Lipschitz functions: II. New algorithms and computational comparison","year":1992}