Convex quadratic underestimation and Branch and Bound for univariate global optimization with one nonconvex constraint

Hoai An Le Thi; Mohand Ouanes

RAIRO - Operations Research (2006)

  • Volume: 40, Issue: 3, page 285-302
  • ISSN: 0399-0559

Abstract

top
The purpose of this paper is to demonstrate that, for globally minimize one dimensional nonconvex problems with both twice differentiable function and constraint, we can propose an efficient algorithm based on Branch and Bound techniques. The method is first displayed in the simple case with an interval constraint. The extension is displayed afterwards to the general case with an additional nonconvex twice differentiable constraint. A quadratic bounding function which is better than the well known linear underestimator is proposed while w-subdivision is added to support the branching procedure. Computational results on several and various types of functions show the efficiency of our algorithms and their superiority with respect to the existing methods.

How to cite

top

Le Thi, Hoai An, and Ouanes, Mohand. "Convex quadratic underestimation and Branch and Bound for univariate global optimization with one nonconvex constraint." RAIRO - Operations Research 40.3 (2006): 285-302. <http://eudml.org/doc/249771>.

@article{LeThi2006,
abstract = { The purpose of this paper is to demonstrate that, for globally minimize one dimensional nonconvex problems with both twice differentiable function and constraint, we can propose an efficient algorithm based on Branch and Bound techniques. The method is first displayed in the simple case with an interval constraint. The extension is displayed afterwards to the general case with an additional nonconvex twice differentiable constraint. A quadratic bounding function which is better than the well known linear underestimator is proposed while w-subdivision is added to support the branching procedure. Computational results on several and various types of functions show the efficiency of our algorithms and their superiority with respect to the existing methods. },
author = {Le Thi, Hoai An, Ouanes, Mohand},
journal = {RAIRO - Operations Research},
keywords = {Global optimization; branch and bound; quadratic underestimation; w-subdivision.; global optimization; quadratic underestimation; -subdivision},
language = {eng},
month = {11},
number = {3},
pages = {285-302},
publisher = {EDP Sciences},
title = {Convex quadratic underestimation and Branch and Bound for univariate global optimization with one nonconvex constraint},
url = {http://eudml.org/doc/249771},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Le Thi, Hoai An
AU - Ouanes, Mohand
TI - Convex quadratic underestimation and Branch and Bound for univariate global optimization with one nonconvex constraint
JO - RAIRO - Operations Research
DA - 2006/11//
PB - EDP Sciences
VL - 40
IS - 3
SP - 285
EP - 302
AB - The purpose of this paper is to demonstrate that, for globally minimize one dimensional nonconvex problems with both twice differentiable function and constraint, we can propose an efficient algorithm based on Branch and Bound techniques. The method is first displayed in the simple case with an interval constraint. The extension is displayed afterwards to the general case with an additional nonconvex twice differentiable constraint. A quadratic bounding function which is better than the well known linear underestimator is proposed while w-subdivision is added to support the branching procedure. Computational results on several and various types of functions show the efficiency of our algorithms and their superiority with respect to the existing methods.
LA - eng
KW - Global optimization; branch and bound; quadratic underestimation; w-subdivision.; global optimization; quadratic underestimation; -subdivision
UR - http://eudml.org/doc/249771
ER -

References

top
  1. W. Baritompa and A. Cutler, Accelerations for global optimization covering methods using second derivates. J. Global Optim.4 (1994) 329–341.  Zbl0821.90095
  2. E. Baumann, Optimal centered forms. BIT28 (1988) 80–87.  Zbl0641.65043
  3. C de Boor, A practical Guide to Splines Applied Mathematical Sciences. Springer-Verlag (1978).  Zbl0406.41003
  4. J. Calvin, and A. Ilinskas, On the convergence of the P-algorithm for one-dimensional global optimization of smooth functions. J. Optim. Theory Appl.102 (1999) 479–495.  Zbl0985.90075
  5. P.G. Ciarlet, The Finite Element Method for Elliptic Problems. Studies Math. Appl. (1979).  
  6. J.E. Falk and R.M. Soland, An algorithm for separable nonconvex programming problems. Manage. Sci.15 (1969) 550–569.  Zbl0172.43802
  7. D. Famularo, Y.D. Sergeyev and P. Pugliese, Test Problems for Lipschitz Univariate Global Optimization with Multiextremal Constraints. Publication online.  Zbl1211.90180
  8. C. Floudas and V. Visweswaran, A Global Optimization Algorithm (GOP) for Certain Classes of Nonconvex NLPs-I. Theory. Comput. Chemical Engin.14 (1990) 1394–1417.  
  9. C.A. Floudas, P.M. Pardalos, C.S. Adjiman, W.R. Esposito, Z.H. Gümüs, S.T. Harding, J.L. Klepeis, C.A. Meyer and C.A. Schweiger, Handbook of Test Problems in Local and Global Optimization. Kluwer Academic Publishers (1999).  Zbl0943.90001
  10. V.P. Gergel, A Global Optimization Algorithm for Multivariate functions with Lipschitzian First Derivatives, J. Global Optim. 10 (1997) 257–281.  Zbl0880.90122
  11. K. Glashoff and S.A. Gustafson, Linear Optimization and Approximation. Amplitude Math. Sciences, Springer-Verlag (1983).  Zbl0526.90058
  12. E. Gourdin, B. Jaumard and R. Ellaia, Global Optimization of Hölder Functions. J. Global Optim.8 (1996) 323–348.  Zbl0848.90110
  13. E. Hansen, Global optimization using interval analysis the multi-dimensional case. Numer. Math.34 (1980) 247270.  Zbl0442.65052
  14. E. Hansen, Global Optimization using Interval Analysis. Pure Appl. Math.165, Marcel Dekker, New York (1992).  Zbl0762.90069
  15. P. Hansen, B. Jaumard and J. Xiong, Decomposition and interval arithmetic applied to minimization of polynomial and rational functions. J. Global Optim.3 (1993) 421–437.  Zbl0794.90062
  16. P. Hansen, B. Jaumard and J. Xiong, Cord-slope form of Taylor's expansion in univariate global optimization. J. Optim. Theory Appl.80 (1994) 441–464.  Zbl0797.90093
  17. P. Hansen, B. Jaumard and S.-H. Lu, Global Optimization of Univariate Functions by Sequential Polynomial Approximation. Int. J. Comput. Math.28 (1989) 183–193.  Zbl0676.65063
  18. P. Hansen, B. Jaumard and S.-H. Lu, Global Optimization of Univariate Lipschitz Functions: 2. New Algorithms and Computational Comparison. Math. Program.55 (1992) 273–292.  Zbl0825.90756
  19. R. Horst and P.M. Pardalos, Handbook of Global Optimization. Kluwer Academic Publishers, Dordrecht (1995).  Zbl0805.00009
  20. R. Horst and H. Tuy, Global Optimization – Deterministic Approaches. Springer-Verlag, Berlin (1993).  Zbl0704.90057
  21. H.A. Le Thi and T. Pham Dinh, A Branch-and-Bound method via D.C. Optimization Algorithm and Ellipsoidal technique for Box Constrained Nonconvex Quadratic Programming Problems. J. Global Optim.13 (1998) 171–206.  Zbl0912.90233
  22. M. Locatelli and F. Schoen, An adaptive stochastic global optimization algorithm for one dimensional functions. Ann. Oper. Res.58 (1995) 263–278.  Zbl0841.90114
  23. F. Messine and J. Lagouanelle, Enclosure methods for multivariate differentiable functions and application to global optimization. J. Universal Comput. Sci.4 (1998) 589–603.  Zbl1063.90574
  24. R. Moore, Interval Analysis. Prentice-Hall, Englewood Cliffs, New Jersey, (1966).  Zbl0176.13301
  25. P.M. Pardalos and H.E. Romeijn, Handbook of Global Optimization, Volume 2. Nonconvex Optimization and Its Applications, Springer, Boston/Dordrecht/London (2002).  Zbl0991.00017
  26. S.A. Pijavskii, An Algorithm for Finding the Absolute Extremum of a Function. USSR. Comput. Math. Math. Physics12 (1972) 57–67.  Zbl0282.65052
  27. T. Quynh Phong, L.T. Hoai An and P. Dinh Tao, On the global solution of linearly constrained indefinite quadratic minimization problems by decomposition branch and bound method. RAIRO: Oper. res.30 (1996) 31–49.  Zbl0857.90098
  28. H. Ratschek and J. Rokne, New Computer Methods for Global Optimization. Wiley, New York (1982).  Zbl0648.65049
  29. D. Ratz, A nonsmooth global optimization technique using slopes the one-dimensional case. J. Global Optim.14 (1999) 365–393.  Zbl0959.65078
  30. A.H.G. Rinnooy and G.H. Timmer, Global Optimization: A Survey, in Handbooks of Operations Research, edited by G.L. Nemhauser et al. North-Holland, Elsevier Science Publishers (1989) 631–662.  Zbl0715.90086
  31. Ya.D. Sergeyev and V.A. Grishagin, A Parallel Method for Finding the Global Minimum of Univariate Functions. J. Optim. Theory Appl.80 (1994) 513–536.  Zbl0797.90098
  32. Ya.D. Sergeyev, An One-Dimensional Deterministic Global Minimization Algorithm. Russian J. Comput. Math. Math. Phys.35 705–717.  
  33. A. Törn and A. Zilinskas, Global Optimization, edited by G. Goos and J. Hartmanis. Springer, Berlin, Lect. Notes Comput. Sci.350 (1989).  Zbl0752.90075
  34. V. Visweswaran and C.A. Floudas, Global Optimization of Problems with Polynomial Functions in One Variable, in Recent Advances in Global Optimization, edited by A. Floudas and P.M. Pardalos. Princeton, Princeton University Press, pp. 165–199.  Zbl0781.90084
  35. Ya.D. Sergeyev, Global one-dimensional optimization using smooth auxiliary functions. Math. Program.81 (1998) 127–146.  Zbl0920.90133
  36. X. Wang and T.-S. Chang, An Improved Univariate Global Optimization Algorithm with Improved Linear Bounding Functions. J. Global Optim.8 (1996) 393–411.  Zbl0851.90119
  37. A. Zilinskas, On Global One-Dimensional Optimization. Engineering Cybernetics, Izvestija AN USSR4 (1976) 71–74.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.