American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C
  • NACO Home
  • This Issue
  • Next Article
    On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization
March  2021, 11(1): 63-73. doi: 10.3934/naco.2020015

Piecewise quadratic bounding functions for finding real roots of polynomials

Djamel Aaid 1,, , Amel Noui 2, and  Özen Özer 3,

1. 

Department of the Common Base Natural and Life Sciences, Batna 2 University, Algeria
2. 

Faculty of Mathematics and Computer Science, Batna 2 University, Algeria
3. 

Department of Mathematics, Faculty of Science and Arts, Kirklareli University, 39100, Kirklareli, Turkey

* Corresponding author: Djamel Aaid

Received  June 2019 Revised  September 2019 Published  March 2021 Early access  October 2021

In this paper, our main interest is to create/ construct a new useful and outstanding algorithm to obtain roots of the real polynomial represented by $ f(x) = c_{0}+c_{1}x+...+c_{i}x^{i}+...+c_{n}x^{n} $ where coefficients of the polynomials are real numbers and $ x $ is a real number in the closed interval of $ \mathbb{R} $. Also, our results are supported by numerical examples. Then, a new algorithm is compared with the others (writer classical methods) and this algorithm is more useful than others.

Keywords: Global optimization, Piecewise Quadratic Upper Function, Piecewise Quadratic Lower Function, Root-finding, Branch and Reduce, Branch and Bound.
Mathematics Subject Classification: 26C10, 90C20, 90C25, 90C90.
Citation: Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control and Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015
References:
[1]

D. Aaid, A. Noui and M. Ouanes, New technique for solving univariate global optimization, Archivum Mathematicum, 53 (2017), 19-33. 

[2]

C. S. Adjiman, I. P. Androulakis and C. A. Floudas, A global optimization method, $\alpha$bb, for general twice-differentiable constrained nlpsii. implementation and computational results, Computers & Chemical Engineering, 22 (1998), 1159-1179. 

[3]

X.-D. Chen and W. Ma, A planar quadratic clipping method for computing a root of a polynomial in an interval, Computers & Graphics, 46 (2015), 89-98. 

[4]

X.-D. Chen and W. Ma, Rational cubic clipping with linear complexity for computing roots of polynomials, Applied Mathematics and Computation, 273 (2016), 1051-1058.  doi: 10.1016/j.amc.2015.10.054.

[5]

X.-D. Chen, W. Ma and Y. Ye, A rational cubic clipping method for computing real roots of a polynomial, Computer Aided Geometric Design, 38 (2015), 40-50.  doi: 10.1016/j.cagd.2015.08.002.

[6]

C. De Boor, Applied mathematical sciences, in A Practical Guide To Splines, Vol. 27, (1978), Spriger-Verlag.

[7]

A. Djamel, N. Amel, Z. Ahmed, O. Mohand and L. T. H. An, A quadratic branch and bound with alienor method for global optimization, in XII Global Optimization Workshop, (2014), 41–44.

[8]

A. Djamel, N. Amel and O. Mohand, A piecewise quadratic underestimation for global optimization, in The Abstract Book, (2013), 138.

[9]

P. Jiang, X. Wu and Z. Liu, Polynomials root-finding using a slefe-based clipping method, Communications in Mathematics and Statistics, 4 (2016), 311-322.  doi: 10.1007/s40304-016-0086-1.

[10]

H. A. Le Thi and M. Ouanes, Convex quadratic underestimation and branch and bound for univariate global optimization with one nonconvex constraint, Rairo-Operations Research, 40 (2006), 285-302.  doi: 10.1051/ro:2006024.

[11]

H. A. Le Thi, M. Ouanes and A. Zidna, An adapted branch and bound algorithm for approximating real root of a ploynomial, in International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences, Springer, (2008), 182–189.

[12]

H. A. Le Thi, M. Ouanes and A. Zidna, Computing real zeros of a polynomial by branch and bound and branch and reduce algorithms, Yugoslav Journal of Operations Research, 24. doi: 10.2298/YJOR120620004L.

[13]

M. Ouanes, H. A. Le Thi, T. P. Nguyen and A. Zidna, New quadratic lower bound for multivariate functions in global optimization, Mathematics and Computers in Simulation, 109 (2015), 197-211.  doi: 10.1016/j.matcom.2014.04.013.

[14]

A. Shpak, Global optimization in one-dimensional case using analytically defined derivatives of objective function, The Computer Science Journal of Moldova, 3 (1995), 168-184. 

show all references

References:
[1]

D. Aaid, A. Noui and M. Ouanes, New technique for solving univariate global optimization, Archivum Mathematicum, 53 (2017), 19-33. 

[2]

C. S. Adjiman, I. P. Androulakis and C. A. Floudas, A global optimization method, $\alpha$bb, for general twice-differentiable constrained nlpsii. implementation and computational results, Computers & Chemical Engineering, 22 (1998), 1159-1179. 

[3]

X.-D. Chen and W. Ma, A planar quadratic clipping method for computing a root of a polynomial in an interval, Computers & Graphics, 46 (2015), 89-98. 

[4]

X.-D. Chen and W. Ma, Rational cubic clipping with linear complexity for computing roots of polynomials, Applied Mathematics and Computation, 273 (2016), 1051-1058.  doi: 10.1016/j.amc.2015.10.054.

[5]

X.-D. Chen, W. Ma and Y. Ye, A rational cubic clipping method for computing real roots of a polynomial, Computer Aided Geometric Design, 38 (2015), 40-50.  doi: 10.1016/j.cagd.2015.08.002.

[6]

C. De Boor, Applied mathematical sciences, in A Practical Guide To Splines, Vol. 27, (1978), Spriger-Verlag.

[7]

A. Djamel, N. Amel, Z. Ahmed, O. Mohand and L. T. H. An, A quadratic branch and bound with alienor method for global optimization, in XII Global Optimization Workshop, (2014), 41–44.

[8]

A. Djamel, N. Amel and O. Mohand, A piecewise quadratic underestimation for global optimization, in The Abstract Book, (2013), 138.

[9]

P. Jiang, X. Wu and Z. Liu, Polynomials root-finding using a slefe-based clipping method, Communications in Mathematics and Statistics, 4 (2016), 311-322.  doi: 10.1007/s40304-016-0086-1.

[10]

H. A. Le Thi and M. Ouanes, Convex quadratic underestimation and branch and bound for univariate global optimization with one nonconvex constraint, Rairo-Operations Research, 40 (2006), 285-302.  doi: 10.1051/ro:2006024.

[11]

H. A. Le Thi, M. Ouanes and A. Zidna, An adapted branch and bound algorithm for approximating real root of a ploynomial, in International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences, Springer, (2008), 182–189.

[12]

H. A. Le Thi, M. Ouanes and A. Zidna, Computing real zeros of a polynomial by branch and bound and branch and reduce algorithms, Yugoslav Journal of Operations Research, 24. doi: 10.2298/YJOR120620004L.

[13]

M. Ouanes, H. A. Le Thi, T. P. Nguyen and A. Zidna, New quadratic lower bound for multivariate functions in global optimization, Mathematics and Computers in Simulation, 109 (2015), 197-211.  doi: 10.1016/j.matcom.2014.04.013.

[14]

A. Shpak, Global optimization in one-dimensional case using analytically defined derivatives of objective function, The Computer Science Journal of Moldova, 3 (1995), 168-184. 

Figure 1.  The underestimator in ($ BB $) and ($ BR $)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  The underestimator in our method ($ BBR $)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Tightness of our underestimator $ p(x) $ than the $ q(x) $ used in the classical methods ($ BB $) and ($ BR $)
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Numerical results of Example 1
Zeros of polynom Zeros found with BR Zeros found with BB Zeros found with BBR
0.100000000 0.100000000 0.100000000 0.100000000
0.200000000 0.199999999 0.199999999 0.199999999
0.300000000 0.300000000 0.299999999 0.300000000
0.400000000 0.400000000 0.400000000 0.400000000
0.500000000 0.500000000 0.500000000 0.500000000
0.600000000 0.600000000 0.600000000 0.600000000
0.700000000 0.700000000 0.700000000 0.700000000
0.800000000 0.800000000 0.800000000 0.800000000
0.900000000 0.899999999 0.899999999 0.900000000
Relative Error 0.000000002 0.000000003 0.000000001
number of iterations 25 22 06
Time (second) 0.082000000 0.010000000 0.000000000
Table Options

Download as excel

Zeros of polynom Zeros found with BR Zeros found with BB Zeros found with BBR
0.100000000 0.100000000 0.100000000 0.100000000
0.200000000 0.199999999 0.199999999 0.199999999
0.300000000 0.300000000 0.299999999 0.300000000
0.400000000 0.400000000 0.400000000 0.400000000
0.500000000 0.500000000 0.500000000 0.500000000
0.600000000 0.600000000 0.600000000 0.600000000
0.700000000 0.700000000 0.700000000 0.700000000
0.800000000 0.800000000 0.800000000 0.800000000
0.900000000 0.899999999 0.899999999 0.900000000
Relative Error 0.000000002 0.000000003 0.000000001
number of iterations 25 22 06
Time (second) 0.082000000 0.010000000 0.000000000
Table 2.  Numerical results of Example 2
Zeros of polynom Zeros found with BR Zeros found with BB Zeros found with BBR
0.020600000 0.020599999 0.020600000 0.020600000
0.056600000 0.056600000 0.056600000 0.056600000
0.079900000 0.079900000 0.079899999 0.079899999
0.210000000 0.210000000 0.209999999 0.210000000
0.397300000 0.397300000 0.397299999 0.397300000
0.446600000 0.446599999 0.446600000 0.446599999
0.577600000 0.577600000 0.577599999 0.577600000
0.955100000 0.955100000 0.955099999 0.955100000
0.979100000 0.979100000 0.979099999 0.979100000
0.983500000 0.983499999 0.983500000 0.983500000
Relative Error 0.000000003 0.000000006 0.000000002
number of iterations 27 32 12
Time (second) 0.076100000 0.052000000 0.016000000
Table Options

Download as excel

Zeros of polynom Zeros found with BR Zeros found with BB Zeros found with BBR
0.020600000 0.020599999 0.020600000 0.020600000
0.056600000 0.056600000 0.056600000 0.056600000
0.079900000 0.079900000 0.079899999 0.079899999
0.210000000 0.210000000 0.209999999 0.210000000
0.397300000 0.397300000 0.397299999 0.397300000
0.446600000 0.446599999 0.446600000 0.446599999
0.577600000 0.577600000 0.577599999 0.577600000
0.955100000 0.955100000 0.955099999 0.955100000
0.979100000 0.979100000 0.979099999 0.979100000
0.983500000 0.983499999 0.983500000 0.983500000
Relative Error 0.000000003 0.000000006 0.000000002
number of iterations 27 32 12
Time (second) 0.076100000 0.052000000 0.016000000
Table 3.  Numerical results of Example 3
Zeros of polynom Zeros found with BR Zeros found with BB Zeros found with BBR
0.500000000 0.499999999 0.500000000 0.500000000
0.250000000 0.249999999 0.249999999 0.250000000
0.125000000 0.124999999 0.125000000 0.124999999
0.062500000 0.062500000 0.062499999 0.062500000
0.031250000 0.031249999 0.031250000 0.031249999
0.015625000 0.015625000 0.015624999 0.015624999
0.007812500 0.007812500 0.007812500 0.007812500
0.003906250 0.003906250 0.003906250 0.003906250
Relative Error 0.000000004 0.000000003 0.000000003
number of iterations 36 27 11
Time (second) 0.096200000 0.027300000 0.036100000
Table Options

Download as excel

Zeros of polynom Zeros found with BR Zeros found with BB Zeros found with BBR
0.500000000 0.499999999 0.500000000 0.500000000
0.250000000 0.249999999 0.249999999 0.250000000
0.125000000 0.124999999 0.125000000 0.124999999
0.062500000 0.062500000 0.062499999 0.062500000
0.031250000 0.031249999 0.031250000 0.031249999
0.015625000 0.015625000 0.015624999 0.015624999
0.007812500 0.007812500 0.007812500 0.007812500
0.003906250 0.003906250 0.003906250 0.003906250
Relative Error 0.000000004 0.000000003 0.000000003
number of iterations 36 27 11
Time (second) 0.096200000 0.027300000 0.036100000
Table 4.  Numerical results of Example 4
Zeros of polynom Zeros found with BR Zeros found with BB Zeros found with BBR
0.137793470 0.137793487 0.137793487 0.137793486
0.729454549 0.729454566 0.729454566 0.729454565
1.808342901 1.808342880 1.808342880 1.808342881
3.401433697 3.401433705 3.401433705 3.401433705
5.552496140 5.552496161 5.552496160 5.552496160
8.330152746 8.330152734 8.330152735 8.330152735
11.843785837 11.843785821 11.843785821 11.843785821
16.279257831 16.279257837 16.279257837 16.279257837
21.996585811 21.996585793 21.996585792 21.996585792
29.920697012 29.920697000 29.920697001 29.920697002
Relative Error 0.000000001 0.000000001 0.000000001
number of iterations 23 13 07
Time (second) 0.001200000 0.020000000 0.000000000
Table Options

Download as excel

Zeros of polynom Zeros found with BR Zeros found with BB Zeros found with BBR
0.137793470 0.137793487 0.137793487 0.137793486
0.729454549 0.729454566 0.729454566 0.729454565
1.808342901 1.808342880 1.808342880 1.808342881
3.401433697 3.401433705 3.401433705 3.401433705
5.552496140 5.552496161 5.552496160 5.552496160
8.330152746 8.330152734 8.330152735 8.330152735
11.843785837 11.843785821 11.843785821 11.843785821
16.279257831 16.279257837 16.279257837 16.279257837
21.996585811 21.996585793 21.996585792 21.996585792
29.920697012 29.920697000 29.920697001 29.920697002
Relative Error 0.000000001 0.000000001 0.000000001
number of iterations 23 13 07
Time (second) 0.001200000 0.020000000 0.000000000
[1]

Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2087-2102. doi: 10.3934/jimo.2019044
[2]

Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial and Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647
[3]

Z.Y. Wu, H.W.J. Lee, F.S. Bai, L.S. Zhang. Quadratic smoothing approximation to $l_1$ exact penalty function in global optimization. Journal of Industrial and Management Optimization, 2005, 1 (4) : 533-547. doi: 10.3934/jimo.2005.1.533
[4]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial and Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177
[5]

Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial and Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499
[6]

Yulin Zhao. On the monotonicity of the period function of a quadratic system. Discrete and Continuous Dynamical Systems, 2005, 13 (3) : 795-810. doi: 10.3934/dcds.2005.13.795
[7]

Michal Málek, Peter Raith. Stability of the distribution function for piecewise monotonic maps on the interval. Discrete and Continuous Dynamical Systems, 2018, 38 (5) : 2527-2539. doi: 10.3934/dcds.2018105
[8]

Magnus Aspenberg, Viviane Baladi, Juho Leppänen, Tomas Persson. On the fractional susceptibility function of piecewise expanding maps. Discrete and Continuous Dynamical Systems, 2022, 42 (2) : 679-706. doi: 10.3934/dcds.2021133
[9]

Yilei Tang. Global dynamics and bifurcation of planar piecewise smooth quadratic quasi-homogeneous differential systems. Discrete and Continuous Dynamical Systems, 2018, 38 (4) : 2029-2046. doi: 10.3934/dcds.2018082
[10]

Yves Edel, Alexander Pott. A new almost perfect nonlinear function which is not quadratic. Advances in Mathematics of Communications, 2009, 3 (1) : 59-81. doi: 10.3934/amc.2009.3.59
[11]

Eunice Mureithi. Effects of buoyancy on the lower branch modes on a Blasius boundary layer. Discrete and Continuous Dynamical Systems - B, 2007, 8 (3) : 613-622. doi: 10.3934/dcdsb.2007.8.613
[12]

Anass Belcaid, Mohammed Douimi, Abdelkader Fassi Fihri. Recursive reconstruction of piecewise constant signals by minimization of an energy function. Inverse Problems and Imaging, 2018, 12 (4) : 903-920. doi: 10.3934/ipi.2018038
[13]

Ábel Garab. Unique periodic orbits of a delay differential equation with piecewise linear feedback function. Discrete and Continuous Dynamical Systems, 2013, 33 (6) : 2369-2387. doi: 10.3934/dcds.2013.33.2369
[14]

Zhichuan Zhu, Bo Yu, Li Yang. Globally convergent homotopy method for designing piecewise linear deterministic contractual function. Journal of Industrial and Management Optimization, 2014, 10 (3) : 717-741. doi: 10.3934/jimo.2014.10.717
[15]

Jaume Llibre, Yilei Tang. Limit cycles of discontinuous piecewise quadratic and cubic polynomial perturbations of a linear center. Discrete and Continuous Dynamical Systems - B, 2019, 24 (4) : 1769-1784. doi: 10.3934/dcdsb.2018236
[16]

Zongming Guo, Xuefei Bai. On the global branch of positive radial solutions of an elliptic problem with singular nonlinearity. Communications on Pure and Applied Analysis, 2008, 7 (5) : 1091-1107. doi: 10.3934/cpaa.2008.7.1091
[17]

Laurent Imbert, Michael J. Jacobson, Jr., Arthur Schmidt. Fast ideal cubing in imaginary quadratic number and function fields. Advances in Mathematics of Communications, 2010, 4 (2) : 237-260. doi: 10.3934/amc.2010.4.237
[18]

Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104
[19]

Prof. Dr.rer.nat Widodo. Topological entropy of shift function on the sequences space induced by expanding piecewise linear transformations. Discrete and Continuous Dynamical Systems, 2002, 8 (1) : 191-208. doi: 10.3934/dcds.2002.8.191
[20]

Hang Zheng, Yonghui Xia. Chaotic threshold of a class of hybrid piecewise-smooth system by an impulsive effect via Melnikov-type function. Discrete and Continuous Dynamical Systems - B, 2022  doi: 10.3934/dcdsb.2021319

 Impact Factor: 

Tools

Metrics

  • PDF downloads (26)
  • HTML views (19)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy