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

RAIRO - Operations Research (2006)

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

## Access Full Article

top## Abstract

top## How to cite

topLe 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- W. Baritompa and A. Cutler, Accelerations for global optimization covering methods using second derivates. J. Global Optim.4 (1994) 329–341. Zbl0821.90095
- E. Baumann, Optimal centered forms. BIT28 (1988) 80–87. Zbl0641.65043
- C de Boor, A practical Guide to Splines Applied Mathematical Sciences. Springer-Verlag (1978). Zbl0406.41003
- 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
- P.G. Ciarlet, The Finite Element Method for Elliptic Problems. Studies Math. Appl. (1979).
- J.E. Falk and R.M. Soland, An algorithm for separable nonconvex programming problems. Manage. Sci.15 (1969) 550–569. Zbl0172.43802
- D. Famularo, Y.D. Sergeyev and P. Pugliese, Test Problems for Lipschitz Univariate Global Optimization with Multiextremal Constraints. Publication online. Zbl1211.90180
- 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.
- 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
- V.P. Gergel, A Global Optimization Algorithm for Multivariate functions with Lipschitzian First Derivatives, J. Global Optim. 10 (1997) 257–281. Zbl0880.90122
- K. Glashoff and S.A. Gustafson, Linear Optimization and Approximation. Amplitude Math. Sciences, Springer-Verlag (1983). Zbl0526.90058
- E. Gourdin, B. Jaumard and R. Ellaia, Global Optimization of Hölder Functions. J. Global Optim.8 (1996) 323–348. Zbl0848.90110
- E. Hansen, Global optimization using interval analysis the multi-dimensional case. Numer. Math.34 (1980) 247270. Zbl0442.65052
- E. Hansen, Global Optimization using Interval Analysis. Pure Appl. Math.165, Marcel Dekker, New York (1992). Zbl0762.90069
- 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
- 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
- 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
- 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
- R. Horst and P.M. Pardalos, Handbook of Global Optimization. Kluwer Academic Publishers, Dordrecht (1995). Zbl0805.00009
- R. Horst and H. Tuy, Global Optimization – Deterministic Approaches. Springer-Verlag, Berlin (1993). Zbl0704.90057
- 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
- M. Locatelli and F. Schoen, An adaptive stochastic global optimization algorithm for one dimensional functions. Ann. Oper. Res.58 (1995) 263–278. Zbl0841.90114
- 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
- R. Moore, Interval Analysis. Prentice-Hall, Englewood Cliffs, New Jersey, (1966). Zbl0176.13301
- 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
- S.A. Pijavskii, An Algorithm for Finding the Absolute Extremum of a Function. USSR. Comput. Math. Math. Physics12 (1972) 57–67. Zbl0282.65052
- 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
- H. Ratschek and J. Rokne, New Computer Methods for Global Optimization. Wiley, New York (1982). Zbl0648.65049
- D. Ratz, A nonsmooth global optimization technique using slopes the one-dimensional case. J. Global Optim.14 (1999) 365–393. Zbl0959.65078
- 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
- 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
- Ya.D. Sergeyev, An One-Dimensional Deterministic Global Minimization Algorithm. Russian J. Comput. Math. Math. Phys.35 705–717.
- 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
- 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
- Ya.D. Sergeyev, Global one-dimensional optimization using smooth auxiliary functions. Math. Program.81 (1998) 127–146. Zbl0920.90133
- 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
- A. Zilinskas, On Global One-Dimensional Optimization. Engineering Cybernetics, Izvestija AN USSR4 (1976) 71–74.