Computing real zeros of a polynomial by branch and bound and branch and reduce algorithms
DOI:
https://doi.org/10.2298/YJOR120620004LKeywords:
Global optimization quadratic upper function quadratic lower function root-finding Bound and Reduce Branch and Bound w-subdivisionAbstract
In this paper we propose two algorithms based on branch and bound method and reduced interval techniques to compute all real zeros of a polynomial. Quadratic bounding functions are proposed which are better than the well known linear underestimator. Experimental result shows the efficiency of the two algorithms when facing ill-conditioned polynomials.References
Pan, V.Y., “Solving a polynomial equation: some history and recent progress”, SIAM Review, 39 (1997) 187–220.
Jenkis, M.A., Traub, J.F., “A three-stage algorithm for real polynomials using quadratic iteration”, SIAM Journal on Numerical Analysis, 7 (1970) 545–566.
Mourrain, B., Vrahatis M.N., Yakoubsohn, J.C., “On the complexity of isolating real roots and computing with certainty the topological degree”, Journal of Complexity, 18 (2002) 612–640.
Wilkinson, J.H., “The evaluation of the zeros of ill-conditioned polynomials Part I”, Numer Math., 1 (1959) 150–166.
Farouki, R.T., Rajan, V.T., “Algorithms for polynomials in Bernstein form”, International journal of Computer Aided Geometric Design, 5 (1988) 1–26.
De Boor, C., A practical Guide to Splines Applied Mathematical Sciences, Springer Verlag, 1978.
Zidna, A., Michel, D., “A two-steps algorithm for approximating real roots of a polynomial in Bernstein Basis”, International Journal of Mathematics and Computers in Simulation, 77 (2008) 313–323.
Falk, J.E, Soland, R.M., “An algorithm for separable nonconvex programming problems”, Manage. Sci, 15 (1969) 550–569.
Le Thi, H.A., Ouanes, M., “Convex quadratic underestimation and Branch and Bound for univariate global optimization with one nonconvex constraint”, Rairo-Operations Research, 40 (2006) 285–302.
Le Thi, H.A., Ouanes, M., Zidna, A., “An adapted Branch and Bound Algorithm for approximating real roots of a polynomial”, MCO, (2008) 182-189.
Kiciak, P., Zidna, A., “Recursive de Casteljau bisection and rounding errors”, Journal of computer Aided Geometric Design, 21 (2004) 683–695.
Calvin, J., Ilinskas, A., “On the convergence of the P-algorithm for one dimensional global optimization of smooth functions”, Journal of Optimization Theory and Applications, 102 (1999) 479–495.
Hansen, P., Jaumard, B., Xiong, J., “Decomposition and interval arithmetic applied to minimization of polynomial and rational functions”, Journal of Global Optimization, 3 (1993) 421–437.
Hansen, P., Jaumard, B., Lu, S.H., “Global Optimization of Univariate Functions by Sequential Polynomial Approximation”, International Journal of Computer Mathematics, 28 (1989) 183–193.
Hansen, P., B., Jaumard, B., Lu, S.H., “Global Optimization of Univariate Lipschitz Functions: 2. New Algorithms and Computational Comparison”, Mathematical Programming, 55 (1992) 273–292.
Salzer, H., E., Zucker, R., “Table of the zeros and weight factors of the first fifteen Laguerre polynomials”, Bulletin of the American Mathematical Society, 55 (1949) 1004–1012.
Moore, R., Interval Analysis, Prentice-Hall, Englewood Cliffs, New Jersey, 1966.
Thai, Q.P., Le Thi H.A., Pham, D.T., “On the global solution of linearly constrained indefinite quadratic minimization problems by decomposition branch and bound method”, RAIRO, Recherche Opérationnelle, 30 (1996) 31–49.
Ratschek, H., Rokne, J., New Computer Methods for Global Optimization, Wiley, New York, 1982.
Ratz, D., “A nonsmooth global optimization technique using slopes the one dimensional case”, Journal of Global Optimization, 14 (1999) 365–393.
Visweswaran, V., Floudas, C.A., Global Optimization of Problems with Polynomial Functions in One Variable, in: Recent Advances in Global Optimization, pp. 165–199. Floudas A. and P.M Pardalos P.M. (ed.), Princeton University Press, Princeton, 1992.
Sergeyev, Ya.D., “Global one-dimensional optimization using smooth auxiliary functions”, Mathematical Programming, 81 (1998) 127–146.
Downloads
Published
Issue
Section
License
Copyright (c) 2014 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
