Smooth path-following methods for computing refinements of stationary points of polynomial mappings on polytopes

Abstract

The finite-dimensional variational inequality provides a broad unifying setting for the study of optimization and equilibrium problems and serves as the main computational framework for the practical solution of a host of continuum problems in the mathematical sciences. 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. However, 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 of what the outcome of such a problem should be. To reduce this ambiguity and eliminate some of these counterintuitive stationary points, the notions of perfect equilibrium and proper equilibrium formulated in game theory have been extended in the literature to a variational inequality problem with respect to a continuous mapping on a polytope. These extensions have led to the concepts of perfect stationary point and proper stationary point, respectively. The introduction of the concept of perfect stationary point substantially reduces the set of stationary points. However, a variational inequality problem can still have many perfect stationary points, some of which are undesirable. The proper stationary point, which is also called the robust stationary point in the literature has been formulated to exclude some of these undesirable perfect stationary points. The introduction of perfect and proper stationary points eliminates counterintuitive stationary points to a significant degree, and thus will have many potential applications. Perfect stationary point and proper stationary point are two strict refinements of the stationary point concept. Their existence is guaranteed by the continuity of a mapping and the nonemptiness and boundedness of polytopes. The computation of perfect and proper stationary points plays an important role in applications of variational inequality problem. However, very few methods for computing these refinements of a stationary point are available. Existing algorithms generate a piecewise linear path leading to a proper stationary point, but they miss the differentiability of the problem and can be very time-consuming even when the dimension is not high. Numerical analysis in the literature shows that smooth path-following methods can efficiently compute stationary points, which naturally leads to the following question: can smooth path-following methods be found for computing the refinements of a stationary point? In this thesis, a smooth path-following method is developed to effectively determine a perfect stationary point for a polynomial mapping on a polytope. By incorporating a logarithmic barrier term into an artificial linear objective function with an appropriate convex combination, a smooth path is constructed to a perfect stationary point through closely approximating some stationary points of the mapping on a perturbed polytope. A predictor-corrector method is adopted for numerically following the path. Extensive numerical results further confirm the effectiveness of the method. A smooth path-following method is also developed to compute a proper stationary point for a polynomial mapping on a polytope. The basic idea of the method is to closely approximate some stationary points of the mapping on a perturbed polytope derived from the original polytope. Compared with the computation of a perfect stationary point, the domain of a proper stationary point is perturbed in a more strict manner. Following the definition of proper stationary points, by introducing an extra variable varying between zero and one, we obtain a barrier objective function from an appropriate convex combination of a logarithmic barrier term and an artificial linear objective function with the mapping of a point as its coefficients. The optimality condition of this barrier objective function yields a barrier variational inequality problem that deforms from a trivial problem to the original one when the extra variable varies from one to zero. A smooth path is constructed, starting from the unique solution of the trivial problem and ending at a proper stationary point of the original problem. The numerical performance of the approach shows it to be quite stable in computing a proper stationary point. However, the notion of proper stationary point can lead to a severe numerical problem in computation and limit the scale of the problem. To remedy this deficiency, a perfect d-proper stationary point, which is a strict refinement of the concept of perfect stationary point, is proposed to the solution of a variational inequality problem, where d is a positive number less than one that measures the degree of properness of a stationary point. The smaller the value of d; the higher the degree of properness. It is proven that every polynomial mapping on a polytope has a perfect d-proper stationary point. An interior-point path-following approach is developed to determine the perfect d-proper stationary point of a polynomial mapping on a polytope. It is shown that this refinement of stationary points is much easier to compute than a proper stationary point while applications to examples illustrate that the perfect d-proper stationary point is a proper stationary point even when d is large.

Date of Award	2 Oct 2015
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Chuangyin DANG (Supervisor)