Algorithms for computing the global infimum and minimum of a polynomial function
Tóm tắt
By catching the so-called strictly critical points, this paper presents an effective algorithm for computing the global infimum of a polynomial function. For a multivariate real polynomial f, the algorithm in this paper is able to decide whether or not the global infimum of f is finite. In the case of f having a finite infimum, the global infimum of f can be accurately coded in the Interval Representation. Another usage of our algorithm is to decide whether or not the infimum of f is attained when the global infimum of f is finite. In the design of our algorithm, the well-known Wu’s method plays an important role.
Tài liệu tham khảo
Basu S, Pollack R, Roy M F. Algorithms in Real Algebraic Geometry, Algorithms and Computation in Math. 10. Berlin: Springer-Verlag, 2003
Bochnak J, Coste M, Roy M F. Real Algebraic Geometry. New York-Berlin-Heidelberg: Springer-Verlag, 1998
Guo F, Safey EI Din M, Zhi L H. Global Optimization of Polynomials Using Generalized Critical Values and Sums of Squares. In: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation. New York: ACM, 2010, 107–114
Hanzon B, Jibetean D. Global minimization of a multivariate polynomial using matrix methods. J Global Optimization, 2003, 27: 1–23
Hägglöf K, Lindberg P O, Stevenson L. Computing global minima to polynomial optimization problems using Gröbner bases. J Global Optimization, 1995, 7: 115–125
Heck A. Introduction to Maple. New York-Berlin-Heidelberg: Springer-Verlag, 1993
Knebusch M. On the extension of real places. Comment Math Helv, 1973, 48: 354–369
Lam T Y. The Theory of Ordered Fields. In: Lecture Notes in Pure and Appl. Math. 55. New York: M Dekker, 1980
Mishra B. Algorithmic Algebra, Texts and Monographs in Computer Science. New York-Berlin-Heidelberg: Springer-Verlag, 1993
Nie J, Demmel J, Sturmfels B. Minimizing polynomials via sums of squares over the gradient ideal. Math Program Ser A, 2006, 106: 587–606
Parrilo P A, Sturmfels B. Minimizing polynomial functions. In: Algorithmic and quantitative real algebraic geometry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 60. Providence: Amer Math Soc, 2003, 83–100
Prestel A. Lectures on Formally Real Fields. In: Lecture Notes in Math 1093. Berlin-Heidelberg-New York: Springer-Verlag, 1984
Uteshev A Y, Cherkasov T M. The search for the maximum of a polynomial. J Symbolic Comput, 1998, 25: 587–618
Wu W T. Mathematics Mechanization: Mechanical Geometry Theorem-Proving, Mechanical Geometry Problem-Solving and Polynomial Equations-Solving. Beijing/Dordrecht-Boston-London: Science Press/Kluwer Academic Publishers, 2000
Zeng G X. The software RRUR. In: [email protected], password: shengao2010
Zeng G X, Xiao S J. Computing the rational univariate representations for zero-dimensional systems by Wu’s method (in Chinese). Sci Sin Math, 2010, 40: 999–1016
Zeng G X, Zeng X N. An effective decision method for semidefinite polynomials. J Symbolic Comput, 2004, 37: 83–99