Gröbner bases in Asymptotic Analysis of Perturbed Polynomial Programs

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 <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$$\varepsilon.$$</EquationSource> </InlineEquation> We study the behaviour of the solutions of such a perturbed problem as <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$\varepsilon \rightarrow 0.$$</EquationSource> </InlineEquation> Though the solutions of the programming problems are real, we consider the Karush–Kuhn–Tucker optimality system as a one-dimensional complex algebraic variety in a multi-dimensional complex space. We use the Buchberger’s elimination algorithm of the Gröbner bases theory to replace the defining equations of the variety by its Gröbner basis, that has the property that one of its elements is bivariate, that is, a polynomial in <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$\varepsilon$$</EquationSource> </InlineEquation> and one of the decision variables only. Changing the elimination order in the Buchberger’s algorithm, we obtain such a bivariate polynomial for each of the decision variables. Thus, the solutions of the original system reduces to a number of algebraic functions in <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$\varepsilon$$</EquationSource> </InlineEquation> that can be represented as a Puiseux series in <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$$\varepsilon$$</EquationSource> </InlineEquation> a neighbourhood of <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$$\varepsilon=0$$</EquationSource> </InlineEquation>. A detailed analysis of the branching order and the order of the pole is also provided. The latter is estimated via characteristics of these bivariate polynomials of Gröbner bases. Copyright Springer-Verlag 2006