Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/103436
Title: Interior point algorithms for linear complementarity problems based on large neighborhoods of the central path
Authors: Zhao, G. 
Keywords: Complexity
High-order power series
Interior point algorithm
Large neighborhood
Large step
Linear complementarity problem
Issue Date: May-1998
Citation: Zhao, G. (1998-05). Interior point algorithms for linear complementarity problems based on large neighborhoods of the central path. SIAM Journal on Optimization 8 (2) : 397-413. ScholarBank@NUS Repository.
Abstract: In this paper we study a first-order and a high-order algorithm for solving linear complementarity problems. These algorithms are implicitly associated with a large neighborhood whose size may depend on the dimension of the problems. The complexity of these algorithms depends on the size of the neighborhood. For the first-order algorithm, we achieve the complexity bound which the typical large-step algorithms possess. It is well known that the complexity of large-step algorithms is greater than that of short-step ones. By using high-order power series (hence the name high-order algorithm), the iteration complexity can be reduced. We show that the complexity upper bound for our high-order algorithms is equal to that for short-step algorithms.
Source Title: SIAM Journal on Optimization
URI: http://scholarbank.nus.edu.sg/handle/10635/103436
ISSN: 10526234
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

47
checked on Oct 19, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.