Using Constrained Optimization to Find Real Roots of Polynomial(RRP)

محورهای موضوعی : Operations Research

Hossein Jafari ¹ (Young Researchers and Elite Club, Arak Branch, Islamic Azad University, Arak, Iran.)
Mohammad Ehsanifar ² (Department of Industrial Engineering, Islamic Azad University of Arak, Arak, Iran.)

تاریخ دریافت : 1401/08/21 تاریخ پذیرش : 1401/09/18 تاریخ انتشار : 1403/03/26

کلید واژه: Nonlinear Programming, Operation Research, Optimization, Lingo software, Polynomial,

چکیده مقاله :

The roots of a polynomial have many applications in various sciences. If the polynomial under study has a degree of 4 or more, it will be impossible to find its roots through the coefficients. In this situation, most researchers use numerical methods to find the roots. The purpose of this research is to introduce a relatively simple method for calculating the real roots of a polynomial. In fact, the proposed approach emphasizes the ability of operation research science in the area of finding roots. In the end, some numerical examples are solved with the help of lingo software to better understand the proposed method. The results indicated that the proposed method is remarkably effective in finding the roots of a polynomial.

چکیده انگلیسی:

The roots of a polynomial have many applications in various sciences. If the polynomial under study has a degree of 4 or more, it will be impossible to find its roots through the coefficients. In this situation, most researchers use numerical methods to find the roots. The purpose of this research is to introduce a relatively simple method for calculating the real roots of a polynomial. In fact, the proposed approach emphasizes the ability of operation research science in the area of finding roots. In the end, some numerical examples are solved with the help of lingo software to better understand the proposed method. The results indicated that the proposed method is remarkably effective in finding the roots of a polynomial.

متن کامل:



 

 

Research Paper

Using Constrained Optimization to Find Real Roots of Polynomial(RRP)
Article Info Article history: Received 11 March 2022 Accepted 10 June 2022   Keywords: Nonlinear Programming, Operation Research, Optimization, Polynomial, Lingo Software.		Abstract
		The roots of a polynomial have many applications in various sciences. If the polynomial under study has a degree of 4 or more, it will be impossible to find its roots through the coefficients. In this situation, most researchers use numerical methods to find the roots. The purpose of this research is to introduce a relatively simple method for calculating the real roots of a polynomial. In fact, the proposed approach emphasizes the ability of operation research science in the area of finding roots. In the end, some numerical examples are solved with the help of lingo software to better understand the proposed method. The results indicated that the proposed method is remarkably effective in finding the roots of a polynomial.

 

 

1.Introduction

It is one of the branches of applied mathematics that one of its practical aspects is significant in industrial engineering[1].

Operation Research is an interdisciplinary field of mathematics that uses fields such as mathematical programming, statistics and algorithm design to find the optimal point in optimization problems. Finding the optimal point based on problem type has different meanings and is used in decision making. Operation research issues focus on maximizing or minimizing one or more constraints. The main idea behind operation research is to find the best answer to complicated problems modeled with mathematical language and it leads to the improvement of or optimization of the performance of a system[2].

Operation research may consider a variety of variables, whether discrete, continuous, or both. For example, in optimizing the arrangement of the independent variables, the dependent variable has a discrete nature and the dependent variable (objective function) has a discrete or continuous nature[3].

One of the most powerful software in the field of variable optimization (discrete or continuous or both) is Lingo software[4].

Many problems in computer aided geometric design and computer graphics can be turned into a root-finding problem of a polynomial equation[5].

In this research we also try to use mathematical rules to define a particular problem (finding the true roots of a polynomial) as a model in the form of rules for operation research and finally solve it with the help of Lingo software which is one of the most powerful software in OR. In other words, this study adopted a step‑by‑step approach to find the real roots of a polynomial by using penalty functions in each step.

2.Polynomial

Polynomials consist of some monomials. These expressions are created by multiplying a constant number (called the coefficient) by the power of a variable. Each variable must have a constant numerical power. You see the mathematical form of a monomial:

                                                    (1) 

Polynomial  is a polynomial of degree  and the coefficient  is opposite to zero  [6].

2.1.Real polynomial 

A real polynomial is a polynomial in which all the coefficients () of a monomial have a real value[6].

2.2.The zeros of polynomial

The zeros of polynomial are numbers for which the value of polynomials is zero[6].

3.Statement of problem

Polynomials are important in all mathematical disciplines and play a crucial role. Polynomials are used for approximate functions in numerical analysis and outside of mathematics, the basic equations of economics and physics are expressed by polynomials. Polynomials are also used in linear algebra for specific matrices equations[7].

There are various ways to find the roots of a real polynomial, most of which require a derivative condition. Some other methods that do not require derivation may also have errors, such as the drawing method. The purpose of this research is to present an optimization model to find the real roots of real polynomials. To put it simply, our research does not intend to criticize previous methods but rather, it aims to introduce a new approach to researchers by which they can reach the real roots of a polynomial and provide broader scope for future research. At the end of the discussion some numerical examples will be solved using the proposed method.

4.Literature review

The following are some of the most important researches that have been done in this area:

In 1970, Hirst and Macey in an article examined the boundaries of the roots of polynomials. The researchers eventually introduced a boundary for real and complex roots with the help of several algebraic theorems. The mentioned boundary is calculated based on the value of the polynomial coefficients[8].

In 2004, Deshuang and Zheru in an article proposed a new method for calculating the real roots of a polynomial. The time complexity of the proposed algorithm is as follows. Numerical examples solved by the proposed method illustrate the high accuracy of the new algorithm in root approximation[9].

In 1999, Sanchez et al. in an article investigated the roots of fuzzy cash flow using the fuzzy internal rate of return method[10].

In 2020, Jafari et al. presented a heuristic method (HM) to calculate real internal rates of return (RIRR). Their results showed that the new method was relatively effective and capable of calculating all of the real rates[11].

5.Introducing the proposed approach

In the proposed method, first we need a few theorems that will be discussed separately as follows. And then with the help of these theories the method will be fully introduced.

Theorem (1): Imagine   is a real polynomial, then all the real zeros of  are put in the interval  as if [8].

Theorem (2): Imagine  is a real polynomial with degree ), as if then all the real zeros of  are put in the interval  , as if .

Proof:

According to theorem , thus, . It is clear that roots of  and  are equal , thus we define the new polynomial  as , in which ). It is clear that  is a real polynomial of degree  with  and we can write  as . Now according to theorem (1) it can be concluded that all the real zeros of are put in the interval  as if  . Based on the previous findings, it can be concluded that all the real roots of the polynomial  are in the interval . On the other hand, according to the hypothesis , thus it is concluded that all the real roots of polynomial are in the interval .

So the proof is complete and the verdict is in place.

Theorem (3): Imagine  is a real polynomial, then the polynomial  can have the maximum  real roots.

Proof by contradiction:

Imagine  has real roots as , thus the criterion  can be written as  .( )

By multiplying and rewriting the criterion  it is determined that  is a polynomial with a degree more than  and the result is inconsistent with the assumption of the theorem, so the positive argument is invalid and the verdict is in place.

Lemma(1): If   is a polynomial as  and the function  is defined as  Then the roots of  and  are equal.

Proof of the first part:

Imagine  is a root for , thus,

                                                                                (2)  

Thus  is also the root of .

Proof the second part:

Imagine  is a root for , thus,

                                                                                 (3)

Finally, the proof is complete.

6.The proposed method for finding real roots

Imagine that all the roots of the polynomial  are in the interval . If , it is clear that amount of  in the point  is either positive, negative or zero  .

Consider function  with the criterion . If is a root for the polynomial , based on lemma(1) it can be concluded that  is a root for  and vice versa. Also the amount of  in the point  is either positive or zero.( )

According to the previous points, it can be said that for finding the real roots of the polynomial  we can define a mathematical model as follows:

                                                                                                                     (4)

Subject to:

                                                                                                                      (5)

                                                                                                                           (6)

                                                                                                                                      (7)

According to theorem (2) the search interval can be set as  . Thus, the previous mathematical model can be rewritten as:

                                                                                                                       (8)

Subject to:

                                                                                                                       (9)

                                                                      (10)

                                                                                                                                 (11)

Now if we solve the previous optimization model we will find a real root of  which we call it . After setting the value of the first root (), we add a penalty function to the objective function criterion and the new objective function be comes . This change causes the algorithm to not converge and avoid the roots of the previous discovery in subsequent searches. Now based on theorem (3), it is enough to stop this algorithm after  runs, since the maximum objective function can have  roots. The penalty function criterion must also be defined as such that when approaching to m previously discovered roots  , the value of the objective function () Will greatly increase. Following is an example of a penalty function.

                                                                                                        (12)

Note: Given that the proposed mathematical model works to find the minimum ,  may not be zero for some solutions (That is, it is far from zero) and only minimized. Therefore, by examining the value of  in the discovered roots, incorrect roots can be removed from the total set of discovered roots. This step is called the root refinement step.

Numerical Example(1)

We intend to calculate the polynomial roots using the proposed method and Lingo software:

First, we calculate the boundaries of the roots as follows:

 

 

Now the problem-based mathematical model to find the first root is as follows:

 

Subject to:

 

 

 

After solving the previous mathematical model in Lingo software, the output is obtained as .

According to the Previously mentioned points, to find the second root we have to use the penalty function so that the algorithm used in the software does not converge to the previously discovered solution, so we change the previous mathematical model as follows:

 

Subject to:

 

 

 

 

After solving the previous mathematical model in Lingo software, the output is obtained as .

The following mathematical model is used to find the third root:

 

 

 

 

 

 

After solving the previous mathematical model in Lingo software, the output is obtained as  .

To find the fourth root we need to use the following mathematical model:

 

Subject to:

 

 

 

 

After solving the previous mathematical model in Lingo software, the output is obtained as  .

And finally, to find the fifth root, we have to use the following mathematical model:

 

Subject to:

 

 

 

 

The roots must now be refined. For this purpose, Table 1 presents the value of  for the five discovered roots.

Table 1. value of  for each root

 

Now according to Table 1 we can say that the polynomial under study has three real roots as . The position of these roots are shown in Figure 1.

 

Figure 1. The position of the roots of the investigated polynomial

 

Numerical Example(2)

We intend to calculate the polynomial roots   using the proposed method and Lingo software:

First, we calculate the boundaries of the roots as follows:

 

 

By applying the proposed method, the final results of the calculations are obtained as in Table 2.

Table 2. value of  for each root

			Decision
			To be confirmed
			To be confirmed
			Not to be confirmed
			Not to be confirmed
			To be confirmed

 

Now according to Table 2 we can say that the polynomial under study has two real roots as  . The position of these roots are shown in Figure 2.

 

Figure 2. The position of the roots of the studied polynomial

 

7.Discussion

There are various methods for calculating the root of functions including Newton's method, Secant algorithm, and drawing methods. Two major weaknesses are associated with these: 1. If the initial predictions are not precise enough, the algorithms may converge to a point that does not have a zero at all. 2. If successful, these algorithms detect only one zero. 3. In the first two methods, differentiability is a necessary condition. Whereas, the method proposed in this study does not require differentiation, and the function value per discovered root is zero.

8.Conclusion

Finding the roots of a polynomial has a special place in the various sciences, and for polynomials with a degree more than 4 there is no way to accurately find the roots and thus, numerical methods are used to find them. Calculations are done around it. In this research, we tried to help researchers and practitioners of this field to some extent by introducing a relatively simple optimization method. In fact, the proposed method further exemplifies the importance and status of operations research. Furthermore, it can be concluded that the proposed method was an effort to find the real roots of a polynomial with relatively high accuracy.

9.Suggestions for future researchers

Future studies can calculate the real roots for gray and fuzzy polynomials.

References

[1] Bellman, R.E.(1957).Dynamic Programming, Princeton University Press, Princeton.

[2] Gass, S.I., and Assad, A.A.(2011). Profiles in Operations Research: Pioneers and Innovators. Springer.

[3] Ying, K.C., and Kittipittayakorn, C.(2018). COMBINING DISCRETE EVENT AND AGENT-BASED SIMULATION FOR REDUCING DRAFTEE’S WAITING TIME IN PHYSICAL EXAMINATION CENTERS.International Journal of Industrial Engineering: Theory, Applications and Practice,2(25),175-185.

[4] Muştu, S., and Eren, T.(2018). MAXIMUM COMPLETION TIME UNDER LEARNING EFFECT IN PERMUTATION FLOWSHOP SCHEDULING PROBLEM. International Journal of Industrial Engineering: Theory, Applications and Practice ,2(25),156-174.

[5] Efremov, A., Havran, V., and Seidel, H.P.(2005). Robust and numerically stable Bézier clipping method for ray tracing NURBS surfaces. In: The 21st Spring Conference on Computer Graphics. ACM Press, New York,127–135.

[6] Landis, E.M.(1998)Second Order Equations of Elliptic and Parabolic Type, Publisher: Amer Mathematical Society.

[7] Aufmann, R.N., Barker, V.C., and Lockwood, J.(2006).Basic College Mathematics: An Applied Approach.Houghton Mifflin Company.

[8] Hirst, H.P., and Macey, W.T.(1997). Bounding the Roots of Polynomials. Taylor & Francis, Ltd. on behalf of the Mathematical Association of America,4(28), 292-295.

[9] Deshuang, H., and Zheru, C.(2004). Finding roots of arbitrary high order polynomials based on neural network recursive partitioning method. Science in China Series F: Information Sciences,2(47),232-245.

[10] Sanchez, S., Liao, T.W., Ray, H.G., and Triantaphyllou, E.(1999).An Example For Dealing With The Impreciseness Of Future Cash Flows During The Selection Of Economic Alternatives. International Journal of Industrial Engineering: Theory, Applications and Practice,6(1),38-47.

[11] Jafari, H., Faraji, M., and Khaleghi Ardehali, P.(2020).A heuristic method to calculate the real internal rate of return (RIRR).International Journal of Applied Operational Research,10(1),31-40.

 

 

			Decision
			To be confirmed
			Not to be confirmed
			Not to be conformed
			Not to be confirmed
			To be confirmed
			Not to be confirmed

* Corresponding author. Tel.: [phone] E-mail address: [e-mail]

© 2021. All rights reserved.            Hosting by IA University of Arak Press

 

---