Advanced Search
Article Contents
Article Contents

Univariate geometric Lipschitz global optimization algorithms

Abstract Related Papers Cited by
  • In this survey, univariate global optimization problems are considered where the objective function or its first derivative can be multiextremal black-box costly functions satisfying the Lipschitz condition over an interval. Such problems are frequently encountered in practice. A number of geometric methods based on constructing auxiliary functions with the usage of different estimates of the Lipschitz constants are described in the paper.
    Mathematics Subject Classification: Primary: 65K05, 90C26; Secondary: 90C56.


    \begin{equation} \\ \end{equation}
  • [1]

    C. S. Adjiman, S. Dallwig, C. A. Floudas and A. Neumaier, A global optimization method, $\alpha$BB, for general twice-differentiable constrained NLPs - I., Theoretical advances, Comput. Chem. Engng., 22 (1998), 1137-1158.doi: 10.1016/S0098-1354(98)00027-1.


    M. Yu. Andramonov, A. M. Rubinov and B. M. Glover, Cutting angle methods in global optimization, Appl. Math. Lett., 12 (1999), 95-100.doi: 10.1016/S0893-9659(98)00179-7.


    I. P. Androulakis, C. D. Maranas and C. A. Floudas, $\alpha$BB: A global optimization method for general constrained nonconvex problems, J. Global Optim., 7 (1995), 337-363.doi: 10.1007/BF01099647.


    C. Audet, P. Hansen and G. Savard, "Essays and Surveys in Global Optimization," GERAD 25th Anniversary. Springer-Verlag, New York, 2005.


    A. M. Bagirov, A. M. Rubinov and J. Zhang, Local optimization method with global multidimensional search, J. Global Optim., 32 (2005), 161-179.doi: 10.1007/s10898-004-2700-0.


    W. Baritompa and A. Cutler, Accelerations for global optimization covering methods using second derivatives, J. Global Optim., 4 (1994), 329-341.doi: 10.1007/BF01098365.


    W. Baritompa, Customizing methods for global optimization - A geometric viewpoint, J. Global Optim., 3 (1993), 193-212.doi: 10.1007/BF01096738.


    W. Baritompa, Accelerations for a variety of global optimization methods, J. Global Optim., 4 (1994), 37-45.doi: 10.1007/BF01096533.


    K. A. Barkalov and R. G. Strongin, A global optimization technique with an adaptive order of checking for constraints, Comput. Math. Math. Phys., 42 (2002), 1289-1300.


    M. C. Bartholomew-Biggs, Z. J. Ulanowski and S. Zakovic, Using global optimization for a microparticle identification problem with noisy data, J. Global Optim., 32 (2005), 325-347.doi: 10.1007/s10898-004-1943-0.


    P. Basso, Iterative methods for the localization of the global maximum, SIAM J. Numer. Anal., 19 (1982), 781-792.doi: 10.1137/0719054.


    G. Beliakov and A. Ferrer, Bounded lower subdifferentiability optimization techniques: Applications, J. Global Optim., 47 (2010), 211-231.doi: 10.1007/s10898-009-9467-2.


    D. P. Bertsekas, "Nonlinear Programming," Athena Scientific, Belmont, Massachusetts, 1999.


    B. Betrò, Bayesian methods in global optimization, J. Global Optim., 1 (1991), 1-14.doi: 10.1007/BF00120661.


    M. Björkman and K. Holmström, Global optimization of costly nonconvex functions using radial basis functions, Optim. Eng., 1 (2000), 373-397.doi: 10.1023/A:1011584207202.


    L. Breiman and A. Cutler, A deterministic algorithm for global optimization, Math. Program., 58 (1993), 179-199.doi: 10.1007/BF01581266.


    R. G. Carter, J. M. Gablonsky, A. Patrick, C. T. Kelley and O. J. Eslinger, Algorithms for noisy problems in gas transmission pipeline optimization, Optim. Eng., 2 (2001), 139-157.doi: 10.1023/A:1013123110266.


    L. G. Casado, I. García and Ya. D. Sergeyev, Interval algorithms for finding the minimal root in a set of multiextremal non-differentiable one-dimensional functions, SIAM J. Sci. Comput., 24 (2002), 359-376.doi: 10.1137/S1064827599357590.


    M. H. Chang, Y. C. Park, and T. Y. Lee, A new global optimization method for univariate constrained twice-differentiable NLP problems, J. Global Optim., 39 (2007), 79-100.doi: 10.1007/s10898-006-9121-1.


    F. H. Clarke, "Optimization and Nonsmooth Analysis," John Wiley & Sons, New York, 1983. Reprinted by SIAM Publications, 1990.


    J. J. Cochran, "Wiley Encyclopedia of Operations Research and Management Science (8 Volumes)," Wiley, New York, 2011.doi: 10.1002/9780470400531.


    A. R. Conn, K. Scheinberg and L. N. Vicente, "Introduction to Derivative-Free Optimization," SIAM, Philadelphia, USA, 2009.doi: 10.1137/1.9780898718768.


    S. E. Cox, R. T. Haftka, C. A. Baker, B. Grossman, W. H. Mason and L. T. Watson, A comparison of global optimization methods for the design of a high-speed civil transport, J. Global Optim., 21 (2001), 415-433.doi: 10.1023/A:1012782825166.


    A. E. Csallner, T. Csendes and M. Cs. Markót, Multisection in interval branch-and-bound methods for global optimization - I. Theoretical results, J. Global Optim., 16 (2000), 371-392.doi: 10.1023/A:1008354711345.


    Yu. M. Danilin, Estimation of the efficiency of an absolute-minimum-finding algorithm, USSR Comput. Math. Math. Phys., 11 (1971), 261-267.doi: 10.1016/0041-5553(71)90020-6.


    V. F. Demyanov and V. N. Malozemov, "Introduction to Minimax," John Wiley & Sons, New York, 1974. (The 2nd English-language edition: Dover Publications, 1990).


    V. F. Demyanov and A. M. Rubinov, "Quasidifferential Calculus," Optimization Software Inc., Publication Division, New York, 1986.


    S. M. Elsakov and V. I. Shiryaev, Homogeneous algorithms for multiextremal optimization, Comput. Math. Math. Phys., 50 (2010), 1642-1654.doi: 10.1134/S0965542510100027.


    Yu. G. Evtushenko, V. U. Malkova and A. A. Stanevichyus, Parallel global optimization of functions of several variables, Comput. Math. Math. Phys., 49 (2009), 246-260.doi: 10.1134/S0965542509020055.


    Yu. G. Evtushenko, M. A. Posypkin and I. Kh. Sigal, A framework for parallel large-scale global optimization, Comp. Sci. - Res. Dev., 23 (2009), 211-215.doi: 10.1007/s00450-009-0083-7.


    Yu. G. Evtushenko and M. A. Posypkin, Coverings for global optimization of partial-integer nonlinear problems, Doklady Mathematics, 83 (2011), 268-271.doi: 10.1134/S1064562411020074.


    Yu. G. Evtushenko, Numerical methods for finding global extrema (Case of a non-uniform mesh), USSR Comput. Math. Math. Phys., 11 (1971), 38-54.doi: 10.1016/0041-5553(71)90065-6.


    Yu. G. Evtushenko, "Numerical Optimization Techniques," Translations Series in Mathematics and Engineering. Springer-Verlag, New-York, 1985.doi: 10.1007/978-1-4612-5022-7.


    D. E. Finkel and C. T. Kelley, Additive scaling and the DIRECT algorithm, J. Global Optim., 36 (2006), 597-608.doi: 10.1007/s10898-006-9029-9.


    R. Fletcher, "Practical Methods of Optimization," John Wiley & Sons, New York, 2000.


    C. A. Floudas and C. E. Gounaris, A review of recent advances in global optimization, J. Global Optim., 45 (2009), 3-38.doi: 10.1007/s10898-008-9332-8.


    C. A. Floudas, P. M. Pardalos, C. S. Adjiman, W. Esposito, Z. Gümüs, S. Harding, J. Klepeis, C. Meyer and C. Schweiger, "Handbook of Test Problems in Local and Global Optimization," Kluwer Academic Publishers, Dordrecht, 1999.


    C. A. Floudas and P. M. Pardalos, "Encyclopedia of Optimization (6 Volumes)," Kluwer Academic Publishers, 2001. (The 2nd edition: Springer, 2009).


    K. R. Fowler, J. P. Reese, C. E. Kees, J. E. Dennis Jr., C. T. Kelley, C. T. Miller, C. Audet, A. J. Booker, G. Couture, R. W. Darwin, M. W. Farthing, D. E. Finkel, J. M. Gablonsky, G. Gray and T. G. Kolda, Comparison of derivative-free optimization methods for groundwater supply and hydraulic capture community problems, Adv. Water Res., 31 (2008), 743-757.doi: 10.1016/j.advwatres.2008.01.010.


    J. M. Gablonsky and C. T. Kelley, A locally-biased form of the DIRECT algorithm J. Global Optim., 21 (2001), 27-37.doi: 10.1023/A:1017930332101.


    D. Y. Gao and H. D. Sherali, Canonical duality theory: Connection between nonconvex mechanics and global optimization, In "Advances in Applied Mathematics and Global Optimization"(eds. D. Y. Gao and H. D. Sherali), Springer, New York, (2009), 257-326.doi: 10.1007/978-0-387-75714-8_8.


    D. Y. Gao, "Duality Principles in Nonconvex Systems: Theory, Methods, and Applications," Kluwer Academic Publishers, Dordrecht, 2000.


    V. P. Gergel, A global search algorithm using derivatives, In "Systems Dynamics and Optimization" (ed. Yu. I. Neimark), NNGU Press, Nizhni Novgorod, Russia, (1992), 161-178. In Russian.


    V. A. Grishagin, Operating characteristics of some global search algorithms, In "Problems of Stochastic Search," Zinatne, Riga, 7 (1978), 198-206. In Russian.


    I. E. Grossmann, "Global Optimization in Engineering Design," Kluwer Academic Publishers, Dordrecht, 1996.


    H.-M. Gutmann, A radial basis function method for global optimization, J. Global Optim., 19 (2001), 201-227.doi: 10.1023/A:1011255519438.


    P. Hansen and B. Jaumard, Lipschitz optimization, In"Handbook of Global Optimization" (eds. R. Horst and P. M. Pardalos), Kluwer Academic Publishers, Dordrecht, 1 (1995), 407-493.


    E. M. T. Hendrix and B. G.-Toth, "Introduction to Nonlinear and Global Optimization," Springer, New York, 2010.


    J. He, L. T. Watson, N. Ramakrishnan, C. A. Shaffer, A. Verstak, J. Jiang, K. Bae and W. H. Tranter, Dynamic data structures for a direct search algorithm, Comput. Optim. Appl., 23 (2002), 5-25.doi: 10.1023/A:1019992822938.


    J. B. Hiriart-Urruty and C. Lemaréchal, "Convex Analysis and Minimization Algorithms (Parts I and II)," Springer-Verlag, Berlin, 1996.


    R. Horst, P. M. Pardalos and N. V. Thoai, "Introduction to Global Optimization," Kluwer Academic Publishers, Dordrecht, 1995. (The 2nd edition: Kluwer Academic Publishers, 2001).


    R. Horst and P. M. Pardalos, "Handbook of Global Optimization," volume 1. Kluwer Academic Publishers, Dordrecht, 1995.


    R. Horst and H. Tuy, "Global Optimization - Deterministic Approaches," Springer-Verlag, Berlin, 1996.


    R. Horst, Deterministic global optimization with partition sets whose feasibility is not known: Application to concave minimization, reverse convex constraints, DC-programming, and Lipschitzian optimization, J. Optim. Theory Appl., 58 (1988), 11-37.doi: 10.1007/BF00939768.


    V. V. Ivanov, On optimal algorithms for the minimization of functions of certain classes, Cybernetics, 4 (1972), 81-94. In Russian.


    D. R. Jones, C. D. Perttunen and B. E. Stuckman, Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79 (1993), 157-181.doi: 10.1007/BF00941892.


    D. R. Jones, M. Schonlau and W. J. Welch, Efficient global optimization of expensive black-box functions, J. Global Optim., 13 (1998), 455-492.doi: 10.1023/A:1008306431147.


    O. V. Khamisov, Global optimization of functions with a concave support minorant, Comput. Math. Math. Phys., 44 (2004), 1473-1483.


    A. G. Korotchenko, An algorithm for seeking the maximum value of univariate functions, USSR Comput. Math. Math. Phys., 18 (1978), 34-45.doi: 10.1016/0041-5553(78)90162-3.


    D. E. Kvasov, C. Pizzuti and Ya. D. Sergeyev, Local tuning and partition strategies for diagonal GO methods, Numer. Math., 94 (2003), 93-106.doi: 10.1007/s00211-002-0419-8.


    D. E. Kvasov and Ya. D. Sergeyev, Multidimensional global optimization algorithm based on adaptive diagonal curves, Comput. Math. Math. Phys., 43 (2003), 40-56.


    D. E. Kvasov and Ya. D. Sergeyev, A univariate global search working with a set of Lipschitz constants for the first derivative, Optim. Lett., 3 (2009), 303-318.doi: 10.1007/s11590-008-0110-9.


    D. Lera and Ya. D. Sergeyev, An information global minimization algorithm using the local improvement technique, J. Global Optim., 48 (2010), 99-112.doi: 10.1007/s10898-009-9508-x.


    D. Lera and Ya. D. Sergeyev, Lipschitz and {H\"older global optimization using space-filling curves}, Appl. Numer. Math., 60 (2010), 115-129.doi: 10.1016/j.apnum.2009.10.004.


    G. Liuzzi, S. Lucidi and V. Piccialli, A DIRECT-based approach exploiting local minimizations for the solution of large-scale global optimization problems, Comput. Optim. Appl., 45 (2010), 353-375.doi: 10.1007/s10589-008-9217-2.


    K. Ljungberg, S. Holmgren and Ö. Carlborg, Simultaneous search for multiple QTL using the global optimization algorithm DIRECT, Bioinformatics, 20 (2004), 1887-1895.doi: 10.1093/bioinformatics/bth175.


    D. MacLagan, T. Sturge and W. Baritompa, Equivalent methods for global optimization, In "State of the Art in Global Optimization" (eds. C. A. Floudas and P. M. Pardalos), Kluwer Academic Publishers, Dordrecht, (1996), 201-211.doi: 10.1007/978-1-4613-3437-8_13.


    O. L. Mangasarian, "Nonlinear Programming," McGraw-Hill, New York, 1969. Reprinted by SIAM Publications, 1994.


    C. D. Maranas and C. A. Floudas, Global minimum potential energy conformations of small molecules, J. Global Optim., 4 (1994), 135-170.doi: 10.1007/BF01096720.


    C. C. Meewella and D. Q. Mayne, An algorithm for global optimization of Lipschitz continuous functions, J. Optim. Theory Appl., 57 (1988), 307-322.doi: 10.1007/BF00938542.


    C. C. Meewella and D. Q. Mayne, Efficient domain partitioning algorithms for global optimization of rational and Lipschitz continuous functions, J. Optim. Theory Appl., 61 (1989), 247-270.doi: 10.1007/BF00962799.


    R. H. Mladineo, An algorithm for finding the global maximum of a multimodal multivariate function, Math. Program., 34 (1986), 188-200.doi: 10.1007/BF01580583.


    J. Mockus, W. Eddy, A. Mockus, L. Mockus and G. Reklaitis, "Bayesian Heuristic Approach to Discrete and Global Optimization," Kluwer Academic Publishers, Dordrecht, 1996.


    J. Mockus, "Bayesian Approach to Global Optimization," Kluwer Academic Publishers, Dordrecht, 1989.


    C. G. Moles, P. Mendes and J. R. Banga, Parameter estimation in biochemical pathways: A comparison of global optimization methods, Genome Res., 13 (2003), 2467-2474.doi: 10.1101/gr.1262503.


    A. Molinaro, C. Pizzuti and Ya. D. Sergeyev, Acceleration tools for diagonal information global optimization algorithms, Comput. Optim. Appl., 18 (2001), 5-26.doi: 10.1023/A:1008719926680.


    A. Molinaro and Ya. D. Sergeyev, Finding the minimal root of an equation with the multiextremal and nondifferentiable left-hand part, Numer. Algorithms, 28 (2001), 255-272.doi: 10.1023/A:1014063303984.


    V. N. Nefedov, Some problems of solving Lipschitzian global optimization problems using the branch and bound method, Comput. Math. Math. Phys., 32 (1992), 433-445.


    Yu. I. Neimark and R. G. Strongin, The information approach to the problem of search of extrema of functions, Engineering Cybernetics, 1 (1966), 17-26.


    A. Neumaier, Complete search in continuous global optimization and constraint satisfaction, In "Acta Numerica 2004" (ed. A. Iserles), Cambridge University Press, UK, 13 (2004), 271-369.doi: 10.1017/CBO9780511569975.004.


    J. Nocedal and S. J. Wright, "Numerical Optimization," Springer-Verlag, Dordrecht, 1999. (The 2nd edition: Springer, 2006).


    P. M. Pardalos and M. G. C. Resende, "Handbook of Applied Optimization," Oxford, University Press, New York, 2002.


    P. M. Pardalos and H. E. Romeijn, "Handbook of Optimization in Medicine," Springer, New York, 2009.


    R. Paulavičius, J. Žilinskas and A. Grothey, Investigation of selection strategies in branch and bound algorithm with simplicial partitions and combination of Lipschitz bounds, Optim. Lett., 4 (2010), 173-183.doi: 10.1007/s11590-009-0156-3.


    J. D. Pintér, "Global Optimization in Action (Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications)," Kluwer Academic Publishers, Dordrecht, 1996.


    J. D. Pintér, Global Optimization: Scientific and Engineering Case Studies, Nonconvex Optimization and Its Applications, Springer-Verlag, Berlin, 85 (2006).


    S. A. Piyavskij, An algorithm for finding the absolute minimum of a function, In "Optimum Decison Theory," Inst. Cybern. Acad. Science Ukrainian SSR, Kiev, 2 (1967), 13-24. In Russian.


    S. A. Piyavskij, An algorithm for finding the absolute extremum of a function, USSR Comput. Math. Math. Phys., 12 (1972), 57-67. (In Russian: Zh. Vychisl. Mat. Mat. Fiz., 12 (1972), 888-896.)doi: 10.1016/0041-5553(72)90115-2.


    S. Rebennack, P. M. Pardalos, M. V. F. Pereira and N. A. Iliadis, "Handbook of Power Systems I," Springer, New York, 2010.


    M. G. C. Resende and P. M. Pardalos, "Handbook of Optimization in Telecommunications," Springer, New York, 2006.


    R. T. Rockafellar, "Convex Analysis," Princeton University Press, Princeton, NJ, USA, 1970. Reprinted in 1996.


    F. Schoen, On a sequential search strategy in global optimization problems, Calcolo, 19 (1982), 321-334.


    Ya. D. Sergeyev, P. Daponte, D. Grimaldi and A. Molinaro, Two methods for solving optimization problems arising in electronic measurements and electrical engineering, SIAM J. Optim., 10 (1999), 1-21.doi: 10.1137/S1052623496312393.


    Ya. D. Sergeyev and V. A. Grishagin, Parallel asynchronous global search and the nested optimization scheme, J. Comput. Anal. Appl., 3 (2001), 123-145.doi: 10.1023/A:1010185125012.


    Ya. D. Sergeyev and D. E. Kvasov, Global search based on efficient diagonal partitions and a set of Lipschitz constants, SIAM J. Optim., 16 (2006), 910-937.doi: 10.1137/040621132.


    Ya. D. Sergeyev and D. E. Kvasov, "Diagonal Global Optimization Methods," FizMatLit, Moscow, 2008. In Russian.


    Ya. D. Sergeyev and D. L. Markin, An algorithm for solving global optimization problems with nonlinear constraints, J. Global Optim., 7 (1995), 407-419.doi: 10.1007/BF01099650.


    Ya. D. Sergeyev, "Divide the best" algorithms for global optimization, Technical Report 2-94, Department of Mathematics, University of Calabria, Rende(CS), Italy, 1994.


    Ya. D. Sergeyev, Global optimization algorithms using smooth auxiliary functions, Technical Report 5, ISI-CNR, Institute of Systems and Informatics, Rende(CS), Italy, 1994.


    Ya. D. Sergeyev, A global optimization algorithm using derivatives and local tuning, Technical Report 1, ISI-CNR, Institute of Systems and Informatics, Rende(CS), Italy, 1994.


    Ya. D. Sergeyev, An information global optimization algorithm with local tuning, SIAM J. Optim., 5 (1995), 858-870.doi: 10.1137/0805041.


    Ya. D. Sergeyev, A one-dimensional deterministic global minimization algorithm, Comput. Math. Math. Phys., 35 (1995), 705-717.


    Ya. D. Sergeyev, A method using local tuning for minimizing functions with Lipschitz derivatives, In "Developments in Global Optimization" (eds. I. M. Bomze, T. Csendes, R. Horst, and P. M. Pardalos), Kluwer Academic Publishers, (1997), 199-216.


    Ya. D. Sergeyev, Global one-dimensional optimization using smooth auxiliary functions, Math. Program., 81 (1998), 127-146.doi: 10.1007/BF01584848.


    Ya. D. Sergeyev, On convergence of "Divide the Best" global optimization algorithms, Optimization, 44 (1998), 303-325.doi: 10.1080/02331939808844414.


    Ya. D. Sergeyev, Multidimensional global optimization using the first derivatives, Comput. Math. Math. Phys., 39 (1999), 711-720.


    Ya. D. Sergeyev, Univariate global optimization with multiextremal non-differentiable constraints without penalty functions, Comput. Optim. Appl., 34 (2006), 229-248.doi: 10.1007/s10589-005-3906-x.


    Z. Shen and Y. Zhu, An interval version of Shubert's iterative method for the localization of the global maximum, Computing, 38 (1987), 275-280.doi: 10.1007/BF02240102.


    B. O. Shubert, A sequential method seeking the global maximum of a function, SIAM J. Numer. Anal., 9 (1972), 379-388.doi: 10.1137/0709036.


    C. P. Stephens and W. Baritompa, Global optimization requires global information, J. Optim. Theory Appl., 96 (1998), 575-588.doi: 10.1023/A:1022612511618.


    A. S. Strekalovsky, "Elements of Nonconvex Optimization," Nauka, Novosibirsk, 2003. In Russian.


    R. G. Strongin and D. L. Markin, Minimization of multiextremal functions with nonconvex constraints, Cybernetics, 22 (1986), 486-493.doi: 10.1007/BF01075079.


    R. G. Strongin and Ya. D. Sergeyev, "Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms," Kluwer Academic Publishers, Dordrecht, 2000.


    R. G. Strongin, Multiextremal minimization for measurements with interference, Engineering Cybernetics, 16 (1969), 105-115.


    R. G. Strongin, "Numerical Methods in Multiextremal Problems (Information-Statistical Algorithms)," Nauka, Moscow, 1978. In Russian.


    A. G. Sukharev, "Minimax Algorithms in Problems of Numerical Analysis," Nauka, Moscow, 1989. In Russian.


    L. N. Timonov, An algorithm for search of a global extremum, Engineering Cybernetics, 15 (1977), 38-44.


    A. Törn and A. Žilinskas, "Global Optimization," Lecture Notes in Computer Science, Springer-Verlag, Berlin, 350 (1989).


    R. J. Vanderbei, Extension of Piyavskii's algorithm to continuous global optimization, J. Global Optim., 14 (1999), 205-216.doi: 10.1023/A:1008395413111.


    L. T. Watson and C. Baker, A fully-distributed parallel global search algorithm, Engineering Computations, 18 (2001), 155-169.doi: 10.1108/02644400110365851.


    G. R. Wood and B. P. Zhang, Estimation of the Lipschitz constant of a function, J. Global Optim., 8 (1996), 91-103.doi: 10.1007/BF00229304.


    G. R. Wood, Multidimensional bisection applied to global optimisation, Comput. Math. Appl., 21 (1991), 161-172.doi: 10.1016/0898-1221(91)90170-9.


    A. A. Zhigljavsky and A. Žilinskas, "Stochastic Global Optimization," Springer, N. Y., 2008.


    A. Žilinskas, Axiomatic approach to statistical models and their use in multimodal optimization theory, Math. Program., 22 (1982), 104-116.doi: 10.1007/BF01581029.


    A. Žilinskas, "Global Optimization. Axiomatics of Statistical Models, Algorithms, and Applications," Mokslas, Vilnius, 1986. In Russian.

  • 加载中

Article Metrics

HTML views() PDF downloads(417) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint