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

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 language English Tilburg CentER, Center for Economic Research 32 2015-019 Published - 1 Jun 2015

Publication series

Name CentER Discussion Paper 2015-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).