Solve the Polynomial Functions Conditional Extreme by Applying the Groebner Basis Method

Junyu Luo, Shengzhen Ding

Department of Mathematics, Science and Statistics, Zhaoqing University, Zhaoqing, China.

DOI: 10.4236/ojapps.2022.1211132                

Abstract

In this paper, an algebraic method which is based on the groebner bases theory is proposed to solve the polynomial functions conditional extreme. Firstly, we describe how to solve conditional extreme value problems by establishing Lagrange functions and calculating the differential equations derived from the Lagrange functions. Then, by solving the single variable polynomials in the groebner basis, the solution of polynomial equations could be derived successively. We overcome the high number of variables and constraints in the extreme value problem. Finally, this paper illustrates the calculation process of this method through the general procedures and examples in solving questions of conditional extremum of polynomial function.

Keywords

Groebner Basis, Polynomial Equations, Conditional Extremum

1. Introduction

In real life, we will encounter additional conditions of the multivariate function of the most problem, that the function of the independent variable in addition to meeting the conditions in the domain of definition also needs to meet the corresponding conditions of a certain. For example: the volume of a certain rectangular box of material saving problem. Let the rectangular body of the length, width and height of the three variables $x,y,h$, respectively, the volume V must determine the length, width and height of the rectangular body, so that in the case of a certain volumeV surface area $S=2xy+2xh+2yh$ material most economical [1]. Such additionally conditioned extremes are called conditional extremes.

There are usually two methods of conditional extremes: the first: converting the conditional extrema into unconditional extrema, which we can find in [2]. In many cases, however, the conversion of a conditional extreme value into an unconditional extreme value is not so simple. We can see this in [3]. Second, the Lagrange multiplier method. This method does not need to convert the conditional extrema into unconditional extrema. Since the Lagrange multiplier method is necessary for the existence of conditional extrema, the point we find is the point where the extrema may exist, and then we have to continue to rely on the definite. We then continue to determine whether or not the point is a conditional extreme value point based on the definite or actual meaning. When there are many variables and constraints in an extreme value problem, this often makes the calculation difficult.

In this paper, the polynomial equations are converted to an equivalent triangular form by computing the reduced groebner bases under the pure lexicographic monomial order, then, the triangular equations can be solved by a successive back-substitution manner just like the elimination theory. By this way, the computational effort of solving systems of differential equations is reduced. Finally, we give a concrete example to illustrate the calculation.

2. Preliminaries

To find the possible extreme value points of the function $z=f\left(x_1,x_2,\cdots ,x_n\right)$ under the additional conditional polynomial equations:

$\{\begin{array}{l}{\phi }_1\left(x_1,\cdots ,x_n\right)=0,\\ ⋮\\ {\phi }_m\left(x_1,\cdots ,x_n\right)=0.\end{array}$ (1)

We first make the Lagrange function [4]:

$L\left(x_1,x_2,\cdots ,x_n\right)=f\left(x_1,x_2,\cdots ,x_n\right)+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i\cdot {\phi }_i\left(x_1,x_2,\cdots ,x_n\right),}$

Where ${\lambda }_i\left(i=1,2,\cdots ,m\right)$ is the parameter, and then find the first order partial derivatives of the Lagrange function for $x_i\left(i=1,2,\cdots ,n\right)$ respectively, and make them zero. The following sets of polynomial differential equations are obtained.

$\{\begin{array}{l}\frac{\partial f\left(x_1,\cdots ,x_n\right)}{\partial x_1}+{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\lambda }_i\cdot \frac{\partial {\phi }_i\left(x_1,\cdots ,x_n\right)}{\partial x_1}}=0\\ ⋮\\ \frac{\partial f\left(x_1,\cdots ,x_n\right)}{\partial x_n}+{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\lambda }_i\cdot \frac{\partial {\phi }_i\left(x_1,\cdots ,x_n\right)}{\partial x_n}}=0\\ {\phi }_1\left(x_1,\cdots ,x_n\right)=0\\ ⋮\\ {\phi }_m\left(x_1,\cdots ,x_n\right)=0\end{array},$ (2)

Finally, solve Equation (2) to obtain $x_i,i=1,2,\cdots ,n$ and ${\lambda }_i,i=1,2,\cdots ,m$, so that each $x_i$ is the possible extreme value of the function z under the additional condition polynomial Equations (1), and then determine whether it is extreme according to the actual problem. Therefore, the key to solving polynomial function conditional extreme value problems is to find the solution to the system of polynomial Equations (2), and the application of groebner’s method for its solution, to bring a great deal of convenience to the calculation.

3. The Groebner Basis Theory and Solving Polynomials with Conditional Extrema

The groebner bases theory was proposed by Austria mathematician Bruno Buchberg in his 1965 doctoral thesis [5]. He used the division algorithm to systematically study the problem of ideal generators of multivariate polynomial rings over a number field. The more abstract groebner basis theory was developed by L.R. Obbian in 1986 [6]. Prof. Mulan Liu et al. used the groebner basis theory to study linear recursive Lie algebras over rings and to inscribe the structure of linear recursive Lie algebras. In recent years, groebner basis theory has been rapidly developed in the fields of algebraic equation solving, polynomial factoring and so on [7] [8] [9].

3.1. Groebner Basis

$K\left[{\rm X}\right]$ is the polynomials which are defined on the field K with variables ${\rm X}=\left(x_1,x_2,\cdots ,x_n\right)$.

Theorem 1(Hilbert’s basis theorem) [10]: Denote $I\subset K\left[{\rm X}\right]$ as an ideal, each ideal $I\subset K\left[{\rm X}\right]$ is finitely generated, there exists $g_1,g_2,\cdots ,g_l\in I$,

$I=\left\{{\displaystyle \underset{i=1}{\overset{l}{\sum }}{h}_i}{g}_i:h_1,\cdots ,h_l\in K\left[{\rm X}\right]\right\}$. And where $I=\langle g_1,g_2,\cdots ,g_l\rangle$.

Definition 1: Let $G=\left\{g_1,g_2,\cdots ,g_n\right\}$ denotes a groebner base of I under a mono mial order, if $\forall f\in K\left[{\rm X}\right]$, then

$Lt\left[f\right]=c\cdot Lt\left[g_i\right],i=1,2,\cdots ,n,\left(i<n\right).$

where $g_i$ is a nonzero polynomial, $Lt\left[f\right]$ and $Lt\left[g_i\right]$ denote the first terms of f and $g_i$ respectively, c is an arbitrary constant.

According to the theorem 1, there is a groebner bases consisting of finitely many polynomials for the ideal I. Generally speaking, the groebner basis depends on the choice of monomial order, in other words, different monomial order generate varying groebner bases. The basic concept of monomial order can be found in [11], here we will just introduce another definition and theorem which are necessary.

Definition 2 [12]: Denote $I\subset K\left[{\rm X}\right]$ as an ideal, $V\left[I\right]$ represents the set as following:

$V\left[I\right]=\left\{x\in K^n:\forall f_i\in I,f_i\left(x\right)=0\right\}.$

where $x=\left(x_1,x_2,\cdots ,x_n\right)$. It easy to see that $V\left[I\right]$ is the zero set of the ideal I. For a non-zero ideal, although it contains infinite different polynomials, the zero set $V\left[I\right]$ is determined by finite polynomial equations.

Theorem 2: $I\subset K\left[{\rm X}\right]$ is an ideal, $G=\left\{g_1,g_2,\cdots ,g_l\right\}$ is the reduced groebner bases of I under the pure lexicographical monomial order, where $x_1>x_2>\cdots >x_n$. For any $0\le l\le n-1$, the set $G_l=G\cap K\left[x_{l+1},x_{l+2},\cdots ,x_n\right]$ is the groebner basis of the elimination ideal $I_l$.

Proof. Obviously, $G\cap K\left[x_1,x_2,\cdots ,x_n\right]\subseteq I\cap K\left[x_1,x_2,\cdots ,x_n\right]$. Assuming that there is $f\left(x_1,x_2,\cdots ,x_n\right)\in I\cap K\left[x_1,x_2,\cdots ,x_n\right]$ holds. Due to G is the groebner bases ofI, $\exists g_i,1\le i\le l$, $Lt\left(g_i\right)|Lt\left(f\right)$. Under the pure lexicographical monomial order, we can get the result of $g_i\in G\cap K\left[x_1,x_2,\cdots ,x_n\right]$. And finally, according to Hilbert’s basis theorem, $G\cap K\left[x_1,x_2,\cdots ,x_n\right]$ is the groebner bases of $I\cap K\left[x_1,x_2,\cdots ,x_n\right]$.

Theorem 3: $I=\langle f_1,f_2,\cdots ,f_s\rangle \subset C\left[x_1,x_2,\cdots ,x_n\right]$ and $I_1$ is the first elimination ideal. For any $1\le i\le s$, $f_i=g_i\left(x_1,x_2,\cdots ,x_n\right)x_1^{N_i}$. Where $N_i\ge 0$, $g_i\in C\left[x_1,x_2,\cdots ,x_n\right],g_i\ne 0$. Assuming that we have a partial solution $\left(a_2,\cdots ,a_n\right)\notin V\left(g_1,g_2,\cdots ,g_s\right)$, then there exists $a_1\in C$, $\left(a_2,\cdots ,a_n\right)\in V\left(I\right)$.

Proof. The ideal I in the polynomial ring $K\left[x_1,\cdots ,x_n\right]$ is generated by the polynomial $f,g$, i.e. $I=\langle f,g\rangle$. Where

$\begin{array}{l}f=a_0{x}_1^l+\cdots +a_l,\\ g=b_0{x}_1^m+\cdots +b_m,a_0\ne 0,b_0\ne 0,a_i,b_i\in K\left[x_2,\cdots ,x_n\right].\end{array}$

Denote $I_1=I\cap K\left[x_2,\cdots ,x_n\right]$ be the first eliminative ideal of I. We let c be a vector such that $\stackrel{\to }{c}=\left(c_2,\cdots ,c_n\right)\in V\left[I_1\right]$. If $a_0\left(\stackrel{\to }{c}\right)$ and $b_0\left(\stackrel{\to }{c}\right)$ are not at the same time zero, then there exists $c_1\in K$, such that $\left(c_1,c_2,\cdots ,c_n\right)\in V\left[I\right]$. Clearly there is $\langle f,g+x_1^{N}f\rangle \subseteq \langle f,g\rangle$ holds.

Another aspect, $g=\left(\left(g+x_1^{N}f\right)-x_1^{N}f\right)\in \langle f,g+x_1^{N}f\rangle$, so we can obtain that $\langle f,g\rangle =\langle f,g+x_1^{N}f\rangle$, $N\in Z^{+}$ holds. When taking N to be sufficiently large, there is ${\mathrm{deg}}_{x_1}\left(g+x_1^{N}f\right)>{\mathrm{deg}}_{x_1}g$ holds. Therefore $Lc\left(g+x_1^{N}f\right)=a_0$, $a_0\left(\stackrel{\to }{c}\right)\ne 0$, where $Lc\left(g+x_1^{N}f\right)$ denotes the first coefficient of the polynomial $g+x_1^{N}f$. Then, $\exists c_1\in K$, $f\left(c_1,\stackrel{\to }{c}\right)=0$, $g\left(c_1,\stackrel{\to }{c}\right)+c_1^{N}f\left(c_1,\stackrel{\to }{c}\right)=0$.

Hence $g\left(c_1,\stackrel{\to }{c}\right)=0$.

Theorem 2 and 3 are also known as the elimination theorems. It guarantees the continuous separation of variables $\left(x_1,x_2,\cdots ,x_n\right)$. In other words, in the monomial order of a pure dictionary, the reduced groebner bases G under is always in the following triangular form:

$G=\{\begin{array}{l}{g}_1=g_1\left(x_1,x_2,\cdots ,x_n\right)\\ g_2=g_2\left(x_2,\cdots ,x_n\right)\\ ⋮\\ g_n=g_n(\; x\; n\; )\end{array}$

Thus, the process of solving a polynomial equation generated by Lagrange functions can be divided into two steps: first, to calculate the groebner basis of a differential equation under the pure lexicographical monomial order of $x_1>x_2>\cdots >x_n$ ; and second, to solve the triangular polynomial equations by solving the last and acquiring its solution, then to replace each polynomial equation with the penultimate polynomial equation and repeat the process until the first one is solved. In this way, we could ultimately obtain all the possible solutions of the differential equations.

3.2. Example of Demonstration Solving Process

Therefore, the key to solving the conditional extreme value problem of polynomial function is to find the solution of polynomial Equation (2), and the application of groebner method for its solution provides a great deal of computational convenience. An Example is given below.

Consider the standard equation of the ellipsoidal surface:

$\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}=1,\left(a>0,b>0,c>0\right).$

where variables $x,y,z$ denote the horizontal, vertical and vertical axes of the ellipsoidal system of right angles in space separately, and $a,b,c$ are arbitrary positive constants. Find the largest volume of the rectangular body that is internally connected to the ellipsoidal plane. Let $V=x\cdot y\cdot z,\left(x>0,y>0,z>0\right)$ represent the size of rectangular box [13].

Make a Lagrange function:

$L\left(x,y,z\right)=xyz+\lambda \left(\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}-1\right).$

where $\lambda$ is the parameter. The system of polynomial differential equations is obtained by finding its partial derivatives with respect to $x,y,z$ and making them zero:

$\{\begin{array}{l}\frac{\partial L}{\partial x}=yz+2\lambda \frac{x}{a^2}=0\\ \frac{\partial L}{\partial y}=xz+2\lambda \frac{y}{b^2}=0\\ \frac{\partial L}{\partial z}=xy+2\lambda \frac{z}{c^2}=0\end{array}$ (3)

We now consider to solve polynomial Equation (3) using the groebner based approach:

$\{\begin{array}{l}y\cdot z+\frac{2\lambda x}{a^2}=0\\ x\cdot z+\frac{2\lambda y}{b^2}=0\\ x\cdot y+\frac{2\lambda z}{c^2}=0\\ \frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}-1=0\end{array}$

The above system of equations has only a limited number of solutions and the ideal can be calculated:

$\langle y\cdot z+\frac{2\lambda x}{a^2},x\cdot z+\frac{2\lambda y}{b^2},x\cdot y+\frac{2\lambda z}{c^2},\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}-1\rangle$

In the pure lexicographical monomial order, the symbol computing software Maple or Mathematic can calculate the reduced groebner bases as follows :

$G=\left[-1+\frac{12}{a^2{b}^2{c}^2}{\lambda }^2,\frac{1}{a}x+\frac{2}{abc}\lambda ,\frac{1}{b}y+\frac{2}{abc}\lambda ,\frac{1}{c}z+\frac{2}{abc}\lambda \right]$

Solve from equation $-1+\frac{12}{a^2{b}^2{c}^2}{\lambda }^2=0$ to obtain $\lambda =\pm \frac{abc}{2\sqrt{3}}$.

Then substitute $\lambda$ to the equation of (3),and abandoning solutions that do not satisfy the constraint that $x,y$ and z are all variables greater than zero, there are three solutions:

$x=\frac{a}{\sqrt{3}},y=\frac{b}{\sqrt{3}},z=\frac{c}{\sqrt{3}}.$

Thus, the volume of a rectangular body with length $\frac{a}{\sqrt{3}}$, width $\frac{b}{\sqrt{3}}$ and height $\frac{c}{\sqrt{3}}$ is the largest among the rectangular bodies connected internally to the ellipsoidal plane, and its value is $V=\frac{8abc}{3\sqrt{3}}$.

4. Conclusions

In this paper, a groebner bases based method has been proposed to solve the polynomial functions conditional extreme. Comparing with the traditional direct method of solving systems of differential equations, this method has the following two main advantages:

1) No need to determine directly whether the system of polynomial differential equations has solutions or not;

2) All the solutions can be found with significant savings in computational effort to solve especially when there are many variables and constraints in the conditional extreme value problem.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Shnurkov, P.V. (2016) Solution of the Unconditional Extremum Problem for a Linear-Fractional Integral Functional on a Set of Probability Measures. Doklady Mathematics, 94, 550-554. https://doi.org/10.1134/S1064562416050161
[2]	Chionh, E.W., Zhang, M. and Goldman, R.N. (2002) Fast Computation of the Bezout and Dixon Resultant Matrices. Symbolic Computation, 33, 13-29. https://doi.org/10.1006/jsco.2001.0462
[3]	Cox, D., Little, J. and Oshea, D. (2006) Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. 3rd Edition, Springer, New York.
[4]	Márquez-Campos, G., Ojeda, I. and Tornero, J.M. (2015) On the Computation of the Apéry Set of Numerical Monoids and Affine Semigroups. Semigroup Forum, 91, 139-158. https://doi.org/10.1007/s00233-014-9631-y
[5]	Dong, R.N. and Wang, D.M. (2019) Computing Strong Regular Characteristic Pairs with Groebner Bases. Journal of Symbolic Computation, 104, 312-327.
[6]	Huang, Z.Y., England, M., Davenport, J.H. and Paulson, L.C. (2016) Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition with Groebner Bases. 2016 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), Timisoara, 24-27 September 2016. https://doi.org/10.1109/SYNASC.2016.020
[7]	Zhou, N., Wu, J.Z. and Gao, X.Y. (2013) Algebraic Verification Method for SEREs Properties via Groebner Bases Approaches. Journal of Applied Mathematics, 2013, Article ID: 272781. https://doi.org/10.1155/2013/272781
[8]	Grolet, A. and Thouverez, F. (2015) Computing Multiple Periodic Solutions of Nonlinear Vibration Problems Using the Harmonic Balance Method and Groebner Bases. Mechanical Systems and Signal Processing, 52-53, 529-547. https://doi.org/10.1016/j.ymssp.2014.07.015
[9]	Moore, R.E. and Yang, C.T. (1959) Interval Analysis I. Technical Document LMSD-285875.
[10]	Arnon, D.S. and Collins, G.E. (1983) Cylindrical Algerbraic Decomposition I: The Basic Algorithm. SIAM Journal on Computing, 13. https://doi.org/10.1137/0213054
[11]	Kearfott, R.B. (1990) Preconditioners for the Interval Gauss-Seidel Method. SIAM Journal on Numerical Analysis, 27, 809-822. https://doi.org/10.1137/0727047
[12]	Hentenryck, P., Van Mc Allester, D. and Kapur, D. (1997) Solving Polynomial Systems Using a Branch and Prune Approach. SIAM Journal on Numerical Analysis, 34, 797-927. https://doi.org/10.1137/S0036142995281504
[13]	Yang, K.H., Yuan, Z.B., Wei, W., Yuan, R.Y. and Yu, W.S. (2015) Solve the Selective Harmonic Elimination Problem with Groebner Bases Theory. 2015 34th Chinese Control Conference (CCC), Hangzhou, 28-30 July 2015. https://doi.org/10.1109/ChiCC.2015.7260897