Manuscript ID : TAA-2211-1127 Visit : 124 Page: 1 - 17

Article Type: Original Research

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

Subject Areas : Operations Research

1 - Young Researchers and Elite Club, Arak Branch, Islamic Azad University, Arak, Iran.
2 - Department of Industrial Engineering, Islamic Azad University of Arak, Arak, Iran.

Received: 2022-11-12 Accepted : 2022-12-09 Published : 2024-06-15

Keywords: Nonlinear Programming, Operation Research, Optimization, Lingo software, Polynomial,

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.

References:

Full-Text:

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

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.

$C:\Users\Sepehr\Documents\MATLAB\New Folder\New Folder\New Folder\New Folder\1.jpg$

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.

$C:\Users\Sepehr\Documents\MATLAB\New Folder\New Folder\New Folder\New Folder\2.jpg$

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

On inverse data envelopment analysis under weight restrictions
Print Date : 2024-06-15
The Relationship Between Company Strategies and Effective Factors According to The Degree of Cost Stickiness
Print Date : 2024-06-15

Share To

Article Url

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