An Interior-Point Path-Following Method for Computing Perfect Stationary Points of Polynomial Mappings on Polytopes and its Applications

Description

A stationary point of a continuous mapping on a polytope (a bounded polyhedron) is a solution to the variational inequality problem associated with the mapping and polytope. It has many applications in such areas as economics, finance, game theory, and mathematical optimization. Nevertheless, as pointed out in the literature, a variational inequality problem can have many stationary points and some of these stationary points may be undesirable or inconsistent with our intuitive notions about what should be the outcome of a variational inequality problem. To reduce this ambiguity and eliminate some of these counterintuitive stationary points, the notion of perfect equilibrium formulated in game theory has been extended to a variational inequality problem with respect to a continuous mapping and a polytope in the literature. This extension leads to the concept of perfect stationary point. The existence of a perfect stationary point is guaranteed by the continuity of the mapping and the nonemptyness and boundedness of the polytope.The computation of stationary point plays a fundamental role in its applications. The project aims to develop an interior--?point path--?following approach to the effective determination of a perfect stationary point for a polynomial mapping on a polytope. The basic idea of the approach is to closely approximate some stationary point of the mapping on a perturbed polytope derived from a perturbation of the original polytope. For any point in the polytope, we will introduce an appropriate convex combination to incorporate a logarithmic barrier term into the linear objective function with the mapping of the point as its coefficients and formulate an unconstrained optimization problem. An application of the optimality condition together with a fixed--?point argument will lead to a system of polynomial equations, all the solutions of which form a semialgebraic set. The emphasis of the development will be on fully exploiting polynomial form of the mapping and differentiability of the problem. As that in interior--?point methods, we will formulate a smooth path that leads to a perfect stationary point. The existence of such a path will be ensured by the subtraction of a perturbation term and applications of Mas--?Colell’s fixed--?point theorem, Sard’s theorem, the implicit function theorem and a result on the semialgebraic set. To numerically follow the smooth path, an efficient predictor--?corrector method will be adapted by taking advantages of the special structures and sparsity of the problem. To further verify the effectiveness and efficiency of the method, extensive numerical experiments will be carried out systematically. The ultimately expected outcome of the project will be an effective and efficient interior--?point path--?following method for computing a perfect stationary point of a polynomial mapping on a polytope. The well--?known Stone--?Weierstrass theorem shows that a continuous function can be approximated by a polynomial function to any given precision. This implies that the method can also be utilized to determine a perfect stationary point for a continuous mapping on a polytope.?