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  April 2020

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 & 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.   Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

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

[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. Google Scholar

[8]

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

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

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.   Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

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

[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. Google Scholar

[8]

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

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

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, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104
[2]

Bing Yu, Lei Zhang. Global optimization-based dimer method for finding saddle points. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 741-753. doi: 10.3934/dcdsb.2020139
[3]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117
[4]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017
[5]

Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374
[6]

Rim Bourguiba, Rosana Rodríguez-López. Existence results for fractional differential equations in presence of upper and lower solutions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1723-1747. doi: 10.3934/dcdsb.2020180
[7]

Alessandro Fonda, Rodica Toader. A dynamical approach to lower and upper solutions for planar systems "To the memory of Massimo Tarallo". Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021012
[8]

Mark F. Demers. Uniqueness and exponential mixing for the measure of maximal entropy for piecewise hyperbolic maps. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 217-256. doi: 10.3934/dcds.2020217
[9]

Meilan Cai, Maoan Han. Limit cycle bifurcations in a class of piecewise smooth cubic systems with multiple parameters. Communications on Pure & Applied Analysis, 2021, 20 (1) : 55-75. doi: 10.3934/cpaa.2020257
[10]

Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems & Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067
[11]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169
[12]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296
[13]

Wei-Chieh Chen, Bogdan Kazmierczak. Traveling waves in quadratic autocatalytic systems with complexing agent. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020364
[14]

Christopher S. Goodrich, Benjamin Lyons, Mihaela T. Velcsov. Analytical and numerical monotonicity results for discrete fractional sequential differences with negative lower bound. Communications on Pure & Applied Analysis, 2021, 20 (1) : 339-358. doi: 10.3934/cpaa.2020269
[15]

Huanhuan Tian, Maoan Han. Limit cycle bifurcations of piecewise smooth near-Hamiltonian systems with a switching curve. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020368
[16]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443
[17]

Raimund Bürger, Christophe Chalons, Rafael Ordoñez, Luis Miguel Villada. A multiclass Lighthill-Whitham-Richards traffic model with a discontinuous velocity function. Networks & Heterogeneous Media, 2021  doi: 10.3934/nhm.2021004
[18]

Alain Bensoussan, Xinwei Feng, Jianhui Huang. Linear-quadratic-Gaussian mean-field-game with partial observation and common noise. Mathematical Control & Related Fields, 2021, 11 (1) : 23-46. doi: 10.3934/mcrf.2020025
[19]

Lars Grüne, Roberto Guglielmi. On the relation between turnpike properties and dissipativity for continuous time linear quadratic optimal control problems. Mathematical Control & Related Fields, 2021, 11 (1) : 169-188. doi: 10.3934/mcrf.2020032
[20]

Jingrui Sun, Hanxiao Wang. Mean-field stochastic linear-quadratic optimal control problems: Weak closed-loop solvability. Mathematical Control & Related Fields, 2021, 11 (1) : 47-71. doi: 10.3934/mcrf.2020026

 Impact Factor: 

Tools

Metrics

  • PDF downloads (119)
  • HTML views (364)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences