Printer Friendly

Solutions to 8th order polynomial minimization problem *.

Abstract

This paper presents a special canonical dual transformation method for finding global minimizer of a class of 8th order polynomials. The method can be used to solve the 7th order nonlinear algebraic equations that are their derivatives. Applications are illustrated by examples.

1 Primal Problem and its Canonical Dual

This paper presents a method to find global minimizer of the following 8th order polynomial minimization problem

[P.sub.8](x) = 1/2[a.sub.2]([y.sub.2(x)).sup.2] + [b.sub.2][y.sub.2](x) + [c.sub.2] - dx, (1)

where [y.sub.2](x) = 1/2 [a.sub.1] [([y.sub.1](x)).sup.2] + [b.sub.1][y.sub.1](x) + [c.sub.1], [y.sub.1](x) = 1/2[a.sub.0][x.sup.2] + [b.sub.0]x + [c.sub.0], (2)

where [a.sub.i]; [b.sub.i]; [c.sub.i](i = 0; 1; 2); and d are given constants. In this paper, we assume that [a.sub.i] [not equal to] 0 (i = 0; 1; 2). The criticality condition of [P.sub.8](x) leads to a 7th order nonlinear algebraic equation ([a.sub.2][y.sub.2](x) + [b.sub.2])([a.sub.1][y.sub.1](x) + [b.sub.1])([a.sub.0]x + [b.sub.0]) - d = 0 (3)

Clearly, direct methods for solving this 7th order nonlinear algebraic equation are very difficult, or even impossible. Also, identifying the global minimizer of [P.sub.8](x) is a fundamentally difficult task in global optimization. The canonical duality theory developed in [1] is a potentially useful methodology, and can be used to solve a relatively large class of nonlinear algebraic and differential equations. The associated triality theory can be used to identify both global minimizer and local extrema. In the recent paper [2], a special polynomial [P.sub.n](x) with [b.sub.i] = 0(i = 0, 1, 2, ..., n) has been studied. The purpose of this paper is to generalize this result to solve the 7th order nonlinear equation and to identify global minimizer of [P.sub.8](x).

2 Canonical Dual Polynomial

From the pattern of the 8th order polynomial defined in (1), we can let

[y.sub.2](x) = [U.sub.1]([y.sub.1](x)) = [P.sub.4](x) = 1/2[a.sub.1][([y.sub.1](x)).sup.2] + [b.sub.1][y.sub.1](x) + [c.sub.1], (4)

which is a quadratic function of [y.sub.1]. The dual variable [s.sub.1] of [y.sub.1] is defined as

[s.sub.1] = [U'.sub.1]([y.sub.1]) = [a.sub.1][y.sub.1] + [b.sub.1]. (5)

By solving this duality relation, we have

[y.sub.1]([s.sub.1]) = [s.sub.1] - [b.sub.1]/[a.sub.1].

Thus, by using the Legendre transformation

[U.sup.*.sub.1] ([s.sub.1]) = [y.sub.1]([s.sub.1])[s.sub.1] - [U.sub.1]([y.sub.1]([s.sub.1])), (7)

the Legendre conjugate function [U.sup.*.sub.1] ([s.sub.1]) is well-defined as

[U.sup.*.sub.1]([s.sub.1]) = - [c.sub.1] - [b.sub.1](s.1] - [b.sub.1])/[a.sub.1] + [s.sub.1] ([s.sub.1] - [b.sub.1])/[a.sub.1] - [([s.sub.1] - [b.sub.1]).sup.2]/[2a.sub.1] = [([s.sub.1] - [b.sub.1]).sup.2]/[2a.sub.1] - [c.sub.1] (8)

In the same way, [U.sub.2] is set equal to

[U.sub.2]([y.sub.2](x)) = 1/2[a.sub.2][([y.sub.2](x)).sup.2] + [b.sub.2][y.sub.2](x) + [c.sub.2]. (9)

The duality relation between [y.sub.2] and [s.sub.2] is

[s.sub.2] = [U'.sub.2]([y.sub.2]) = [a.sub.2][y.sub.2] + [b.sub.2]. (10)

Then, the Legendre conjugate of [U.sub.2]([y.sub.2]) is

[U.sup.*.sub.2] ([s.sub.2]) = - [c.sub.2] - [b.sub.2]([s.sub.2] - [b.sub.2]/[a.sub.2] + [s.sub.2] ([s.sub.2] - [b.sub.2])/[a.sub.2] - [([s.sub.2] - [b.sub.2]).sup.2]/[2a.sub.2] = [([s.sub.2] - [b.sub.2]).sup.2]/[2a.sub.2] - [c.sub.2] (11)

By the fact that

[U.sub.2]([y.sub.2]) + [U.sup.*.sub.2]([s.sub.2]) = [y.sub.2][s.sub.2], (12)

the polynomial (1) can be written as

[P.sub.8](x) = [U.sub.2](x) + [c.sub.2] - dx = [y.sub.2](x)[s.sub.2] - [U.sup.*.sub.2]([s.sub.2]) + [c.sub.2] - dx. (13)

Manipulation of equations (4) and (7) gives

[y.sub.2] = [U.sub.1] = [y.sub.1][s.sub.1] - [U.sup.*.sub.1]([s.sub.1]). (14)

Therefore,

[P.sub.8](x) = [s.sub.2]([y.sub.1](x)[s.sub.1] - [U.sup.*.sub.1]) - [U.sup.*.sub.2] + [c.sub.2] - dx. (15)

Let [XI](x, [s.sub.1]; [s.sub.2]) equal to equation (15). Further simplication yields

[XI](x, [s.sub.1], [s.sub.2]) = [s.sub.2][(1/2 [a.sub.0][x.sup.2] + [b.sub.0]x + [c.sub.0])[s.sub.1] - [U.sup.*.sub.1]([s.sub.1])] - [U.sup.*.sub.2] ([s.sub.2]) + [c.sub.2] - dx. (16)

By solving [partial derivative][XI]/[partial derivative]x we have

x([s.sub.1]; [s.sub.2]) = x[s.sub.1][s.sub.2] = d/[a.sub.0][s.sub.1][s.sub.2] - [b.sub.0]/[a.sub.0]. (17)

Substituting this x into (16) and setting the final equation equal to [P.sup.d]([s.sub.1], [s.sub.2]), the canonical dual function can be obtained as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (18)

By combining (4), (6) and (10) and simplifying, the relation between [s.sub.1] and [s.sub.2] is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (19)

By substituting (19) into (18) and letting s = [s.sub.1], the canonical dual function is finally obtained as [P.sup.d](s) = [P.sup.d](s, [s.sub.2](s)). By using Mathematica, [P.sub.d](s) can be calculated as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (20)

From the canonical duality theory [1], we have the following result:

Theorem 1 If s is a critical point of [P.sup.d](s), then

x(s) = d/[a.sub.0][s.sub.2]s - [b.sub.0]/[a.sub.0], (21)

with

[s.sub.2] = [a.sub.2]([s.sup2.sub.1] - [b.sup.2.sub.1]/[2a.sub.1] + [c.sub.1]) + [b.sub.2] (22)

is a critical point of P(x) and P(x) = [P.sup.d](s). Moreover, if s is the largest critical point, then x(s) is a global minimizer of P(x).

3 Applications

3.1 Example 1

Let [a.sub.0] = .1; [a.sub.1] = .51; [a.sub.2] = .5; [b.sub.0] = 0; b1 = 0; [b.sub.2] = 0; [c.sub.0] = -6; [c.sub.1] = 0; [c.sub.2] = .5; d = 1:5, we have

[P.sub.8](x) = 0:5 - 1:5x + 0.0162563[(-6 + 0.05[x.sup.2]).sup.4]. (23)

This is a nonconvex polynomial of degree eight with one global minimizer, one local minimizer and one local maximizer as shown in Fig. 1.

[FIGURE 1 OMITTED]

The canonical dual of this [P.sub.8](x) has a very simple form

[P.sup.d](s) = 0.5 + 0.490196[(-6 - 46.818/[s.sup.6])[s.sup.3] - 0.720877[s.sup.4]. (24)

Its graph is shown in Fig. 2.

[FIGURE 2 OMITTED]

The criticality condition [P.sup.d](s) = 0 has three real roots

[s.sub.1] = 1.32632 > [s.sub.2] = -1.5917 > [s.sub.3] = -3.02909. (25)

From equation (21), we have [x.sub.1] = 13.1154, [x.sub.2] = -7.58817, and [x.sub.3] = -1.10099. It is easy to check that

P([x.sub.1]) = -18.4294 = [P.sup.d]([s.sub.1]) < P([x.sup.2]) = 13.4246 = [P.sup.d]([s.sub.2]) < P([x.sub.3]) = 22.3811 = [P.sup.d]([s.sub.3]). (26)

This shows that x1 is a global minimizer, x2 is a local minimizer, and x3 is a local maximizer (see Fig. 3).

[FIGURE 3 OMITTED]

3.2 Example 2

In Example 1, if we let [a.sub.0] = .1; [a.sub.1] = .51; [a.sub.2] = .5; [b.sub.0] = -.1; b1 = -.2; b2 = 0; [c.sub.0] = -7.5; [c.sub.1] = 5; [c.sub.2] = .5; d = -1:5, the graph of the polynomial [P.sub.8](x) is shown in Fig. 4.

[FIGURE 4 OMITTED]

In this case, the canonical dual function [P.sup.d](s) has a total of seven critical points (see Fig. 5).

[FIGURE 5 OMITTED]

[s.sub.7] = -4.03877 < [s.sub.6] = -2.58867 < [s.sub.5] = -1.82974 < [s.sub.4] = -0.537399 < [s.sub.3] = 0.467103 < [s.sub.2] = 2.04221 < [s.sub.1] = 2.43476.

By the Theorem 1 we know that [x.sub.1] = _14:9475 is a global minimizer of P([.sub.x]) and P([x.sub.1]) = [P.sup.d]([s.sub.1]) = -21.7721. (see Fig. 6).

[FIGURE 6 OMITTED]

4 Conclusions

The results of this paper can be used to find the all critical points of the eighth polynomial derivative of equation (1). One advantage of using this way to find the critical values of [P.sub.8] is that, when the derivative of [P.sup.d](s) is set to 0 and the critical values of [P.sup.d](s) are found, the critical value with the largest value of s is the absolute minimum.

Supplementary File

A Mathematica file is available for those who wish to experiment with these techniques.

Acknowledgements

Special thanks go to David Gao, who showed how to use the method on 4th degree polynomials of the form P4 = [1/2[a.sub.1][([y.sub.1]).sup.2] + [b.sub.1][y.sub.1] + [c.sub.1]. The author also would like to offer his sincere thanks to Dr. Ning Ruan for suggestive discuss and detailed comments, which improved this paper dramatically. This research project was under supervision of Mr. Michael Collver at Blacksburg High School.

References

[1] Gao, D.Y. (2000). Duality Principles in Nonconvex Systems: Theory, Methods and Applications. Kluwer Academic Publishers, Dordrecht/Boston/London, xviii+454pp.

[2] Gao, D.Y. (2006). Complete solutions to a class of polynomial minimization problems, J. Global Optimization, 35, 131-143.

* The main result of this paper was announced at the 2007 Virginia State Science and Engineering Fair and received an award.

Timothy K. Gao

timkgao@gmail.com

Blacksburg High School

VA 24060

USA
COPYRIGHT 2007 Mathematics and Technology, LLC
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2007 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Gao, Timothy K.
Publication:Electronic Journal of Mathematics and Technology
Article Type:Report
Geographic Code:1USA
Date:Oct 1, 2007
Words:1818
Previous Article:QuickBoard: the airplane boarding problem.
Next Article:MathPlayer: fully accessible web-based Math.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |