Interior point method on semi-definite linear complementarity problems using the Nesterov-Todd (NT) search direction: polynomial complexity and local convergence

Chee Khian Sim

doi:10.1007/s10589-019-00110-z

Interior point method on semi-definite linear complementarity problems using the Nesterov-Todd (NT) search direction: polynomial complexity and local convergence

Chee Khian Sim

Research output: Contribution to journal › Article › peer-review

207 Downloads (Pure)

Abstract

We consider in this paper an infeasible predictor-corrector primal-dual path following interior point algorithm using the Nesterov-Todd (NT) search direction to solve semi-definite linear complementarity problems. Global convergence and polynomial iteration complexity of the algorithm are established. Two sufficient conditions are also given for superlinear convergence of iterates generated by the algorithm. Preliminary numerical results are finally provided when the algorithm is used to solve semi-definite linear complementarity problems.

Original language	English
Article number	0
Pages (from-to)	583-621
Number of pages	39
Journal	Computational Optimization and Applications
Volume	74
Issue number	2
Early online date	22 May 2019
DOIs	https://doi.org/10.1007/s10589-019-00110-z
Publication status	Published - 1 Nov 2019

Keywords

Nesterov-Todd (NT) Direction
Predictor-Corrector Primal-Dual Path Following Interior Point Algorithm
Semi-definite Linear Complementarity Problem
Polynomial Complexity
Local Convergence

Access to Document

10.1007/s10589-019-00110-z

Interior point methodFinal published version, 560 KBLicence: CC BY

3 Citations
2 Article

Superlinear convergence of an interior point algorithm on linear semi-definite feasibility problems
Sim, C. K., 13 Sept 2024, (Early online) In: Optimization Methods and Software. 21 p.
Research output: Contribution to journal › Article › peer-review

Open Access
File
11 Downloads (Pure)
Superlinear convergence of an infeasible predictor-corrector path-following interior point algorithm for a semidefinite linear complementarity problem using the Helmberg-Kojima-Monteiro direction
Sim, C.-K., 2011, In: SIAM Journal on Optimization. 21, 1, p. 102-126
Research output: Contribution to journal › Article › peer-review

Dataset for Paper "Interior point method on semi-definite linear complementarity problems using the Nesterov-Todd (NT) search direction: Polynomial complexity and local convergence"
Sim, C. K. (Creator), University of Portsmouth, 2019
DOI: 10.17029/4c5cdf06-1c02-4c05-8b31-593d17365bd7
Dataset

File

Cite this

@article{019752ab65ef487f8fec356762754b60,

title = "Interior point method on semi-definite linear complementarity problems using the Nesterov-Todd (NT) search direction: polynomial complexity and local convergence",

abstract = "We consider in this paper an infeasible predictor-corrector primal-dual path following interior point algorithm using the Nesterov-Todd (NT) search direction to solve semi-definite linear complementarity problems. Global convergence and polynomial iteration complexity of the algorithm are established. Two sufficient conditions are also given for superlinear convergence of iterates generated by the algorithm. Preliminary numerical results are finally provided when the algorithm is used to solve semi-definite linear complementarity problems.",

keywords = "Nesterov-Todd (NT) Direction, Predictor-Corrector Primal-Dual Path Following Interior Point Algorithm, Semi-definite Linear Complementarity Problem, Polynomial Complexity, Local Convergence",

author = "Sim, {Chee Khian}",

year = "2019",

month = nov,

day = "1",

doi = "10.1007/s10589-019-00110-z",

language = "English",

volume = "74",

pages = "583--621",

journal = "Computational Optimization and Applications",

issn = "0926-6003",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

T1 - Interior point method on semi-definite linear complementarity problems using the Nesterov-Todd (NT) search direction: polynomial complexity and local convergence

AU - Sim, Chee Khian

PY - 2019/11/1

Y1 - 2019/11/1

N2 - We consider in this paper an infeasible predictor-corrector primal-dual path following interior point algorithm using the Nesterov-Todd (NT) search direction to solve semi-definite linear complementarity problems. Global convergence and polynomial iteration complexity of the algorithm are established. Two sufficient conditions are also given for superlinear convergence of iterates generated by the algorithm. Preliminary numerical results are finally provided when the algorithm is used to solve semi-definite linear complementarity problems.

AB - We consider in this paper an infeasible predictor-corrector primal-dual path following interior point algorithm using the Nesterov-Todd (NT) search direction to solve semi-definite linear complementarity problems. Global convergence and polynomial iteration complexity of the algorithm are established. Two sufficient conditions are also given for superlinear convergence of iterates generated by the algorithm. Preliminary numerical results are finally provided when the algorithm is used to solve semi-definite linear complementarity problems.

KW - Nesterov-Todd (NT) Direction

KW - Predictor-Corrector Primal-Dual Path Following Interior Point Algorithm

KW - Semi-definite Linear Complementarity Problem

KW - Polynomial Complexity

KW - Local Convergence

U2 - 10.1007/s10589-019-00110-z

DO - 10.1007/s10589-019-00110-z

M3 - Article

SN - 0926-6003

VL - 74

SP - 583

EP - 621

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

IS - 2

M1 - 0

ER -

Interior point method on semi-definite linear complementarity problems using the Nesterov-Todd (NT) search direction: polynomial complexity and local convergence

Abstract

Keywords

Access to Document

Fingerprint

Research output

Superlinear convergence of an interior point algorithm on linear semi-definite feasibility problems

Superlinear convergence of an infeasible predictor-corrector path-following interior point algorithm for a semidefinite linear complementarity problem using the Helmberg-Kojima-Monteiro direction

Datasets

Dataset for Paper "Interior point method on semi-definite linear complementarity problems using the Nesterov-Todd (NT) search direction: Polynomial complexity and local convergence"

Cite this