An Interior-Point Path-Following Method for Computing a Perfect Stationary Point of a Polynomial Mapping on a Polytope

Chuangyin Dang, Xiaoxuan Meng, Dolf Talman

Research output: Working paperDiscussion paperOther research output

453 Downloads (Pure)

Abstract

As a refinement of the concept of stationary point, the notion of perfect stationary point was formulated in the literature. Although simplicial methods could be applied to approximate such a point, these methods do not make use of the possible differentiability of the problem and can be very time-consuming even for small-scale problems. To fully exploit the differentiability of the problem, this paper develops an interior-point path-following method for computing a perfect stationary point of a polynomial mapping on a polytope. By incorporating a logarithmic barrier term into the linear objective function with an appropriate convex combination, the method closely approximates some stationary points of the mapping on a perturbed polytope, especially when the perturbation is sufficiently small. It is proved that there exists a smooth path which starts from a point in the interior of a polytope and ends at a perfect stationary point. A predictor-corrector method is adopted for numerically following the path. Numerical results further confirm the effectiveness of the method.
Original languageEnglish
Place of PublicationTilburg
PublisherCentER, Center for Economic Research
Number of pages32
Volume2015-019
Publication statusPublished - 1 Jun 2015

Publication series

NameCentER Discussion Paper
Volume2015-019

Keywords

  • variational inequiality problem
  • perfect stationay point
  • interior-point path-following method
  • predictor-corrector method

Fingerprint Dive into the research topics of 'An Interior-Point Path-Following Method for Computing a Perfect Stationary Point of a Polynomial Mapping on a Polytope'. Together they form a unique fingerprint.

  • Cite this

    Dang, C., Meng, X., & Talman, D. (2015). An Interior-Point Path-Following Method for Computing a Perfect Stationary Point of a Polynomial Mapping on a Polytope. (CentER Discussion Paper; Vol. 2015-019). CentER, Center for Economic Research.