首页 | 本学科首页   官方微博 | 高级检索  
     


Global optimization of univariate Lipschitz functions: II. New algorithms and computational comparison
Authors:Pierre Hansen  Brigitte Jaumard  Shi-Hui Lu
Affiliation:(1) Hill Center for the Mathematical Sciences, RUTCOR, Rutgers University, 08903 New Brunswick, NJ, USA;(2) GERAD and Ecole Polytechnique de Montréal, Qué., Canada
Abstract:We consider the following global optimization problems for a Lipschitz functionf implicitly defined on an interval [a, b]. Problem Pprime: find a globallyepsi-optimal value off and a corresponding point; Problem QPrime: find a set of disjoint subintervals of [a, b] containing only points with a globallyepsi-optimal value and the union of which contains all globally optimal points. A two-phase algorithm is proposed for Problem Pprime. In phase I, this algorithm obtains rapidly a solution which is often globallyepsi-optimal. Moreover, a sufficient condition onf for this to be the case is given. In phase II, the algorithm proves theepsi-optimality of the solution obtained in phase I or finds a sequence of points of increasing value containing one with a globallyepsi-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 smallepsi, 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 QPrime. 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.The research of the authors has been supported by AFOSR grants 0271 and 0066 to Rutgers University. Research of the second author has been also supported by NSERC grant GP0036426, FCAR grant 89EQ4144 and partially by AFOSR grant 0066. We thank Nicole Paradis for her help in drawing the figures.
Keywords:Global optimization  algorithm  univariate function  Lipschitz function  computation
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号