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

419 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

Fingerprint

Path-following Methods
Polynomial Mapping
Stationary point
Interior Point
Polytope
Computing
Differentiability
Predictor-corrector Methods
Path
Convex Combination
Linear Function
Logarithmic
Interior
Refinement
Objective function
Perturbation
Numerical Results
Term

Keywords

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

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). Tilburg: CentER, Center for Economic Research.
Dang, Chuangyin ; Meng, Xiaoxuan ; Talman, Dolf. / An Interior-Point Path-Following Method for Computing a Perfect Stationary Point of a Polynomial Mapping on a Polytope. Tilburg : CentER, Center for Economic Research, 2015. (CentER Discussion Paper).
@techreport{07b7a0e7f8144ec2a3a7e6cec16cbab9,
title = "An Interior-Point Path-Following Method for Computing a Perfect Stationary Point of a Polynomial Mapping on a Polytope",
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.",
keywords = "variational inequiality problem, perfect stationay point, interior-point path-following method, predictor-corrector method",
author = "Chuangyin Dang and Xiaoxuan Meng and Dolf Talman",
year = "2015",
month = "6",
day = "1",
language = "English",
volume = "2015-019",
series = "CentER Discussion Paper",
publisher = "CentER, Center for Economic Research",
type = "WorkingPaper",
institution = "CentER, Center for Economic Research",

}

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, Tilburg.

An Interior-Point Path-Following Method for Computing a Perfect Stationary Point of a Polynomial Mapping on a Polytope. / Dang, Chuangyin; Meng, Xiaoxuan ; Talman, Dolf.

Tilburg : CentER, Center for Economic Research, 2015. (CentER Discussion Paper; Vol. 2015-019).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

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

AU - Dang, Chuangyin

AU - Meng, Xiaoxuan

AU - Talman, Dolf

PY - 2015/6/1

Y1 - 2015/6/1

N2 - 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.

AB - 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.

KW - variational inequiality problem

KW - perfect stationay point

KW - interior-point path-following method

KW - predictor-corrector method

M3 - Discussion paper

VL - 2015-019

T3 - CentER Discussion Paper

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

PB - CentER, Center for Economic Research

CY - Tilburg

ER -

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