On Newton's polygons, Gröbner bases and series expansions of perturbed polynomial programs

• Autorzy: Konstantin Avrachenkov , Vladimir Ejov , Jerzy A. Filar
• Języki publikacji: EN

Abstrakty

EN

In this note we consider a perturbed mathematical programming problem where both the objective and the constraint functions are polynomial in all underlying decision variables and in the perturbation parameter ε. Recently, the theory of Gröbner bases was used to show that solutions of the system of first order optimality conditions can be represented as Puiseux series in ε in a neighbourhood of ε = 0. In this paper we show that the determination of the branching order and the order of the pole (if any) of these Puiseux series can be achieved by invoking a classical technique known as the "Newton's polygon" and using it in conjunction with the Gröbner bases techniques.

Kategorie tematyczne

• 65K10: Optimization and variational techniques
• 13P10: Gr\"obner bases; other bases for ideals and modules (e.g., Janet and border bases)
• 34D15: Singular perturbations

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Banach Center Publications
• Rocznik: 2006
• Tom: 71
• Numer: 1
• Strony: 29-38

Daty

wydano

2006

Twórcy

autor

Konstantin Avrachenkov

• INRIA Sophia Antipolis, 2004 route des Lucioles, B.P. 93, 06902, France

autor

Vladimir Ejov

• School of Mathematics and Statistics, University of South Australia, Mawson Lakes, SA 5095, Australia

autor

Jerzy A. Filar

• School of Mathematics and Statistics, University of South Australia, Mawson Lakes, SA 5095, Australia

Identyfikatory

DOI

10.4064/bc71-0-2