Convergence Analysis of an Infeasible Interior Point Algorithm Based on a Regularized Central Path for Linear Complementarity Problems |
| |
Authors: | Guanglu Zhou Kim-Chuan Toh Gongyun Zhao |
| |
Affiliation: | (1) Department of Mathematics and Statistics, Curtin University of Technology, WA, 6102, Australia;(2) Department of Mathematics, National University of Singapore, 2 Science Drive 2, Singapore, 117543 |
| |
Abstract: | Most existing interior-point methods for a linear complementarity problem (LCP) require the existence of a strictly feasible point to guarantee that the iterates are bounded. Based on a regularized central path, we present an infeasible interior-point algorithm for LCPs without requiring the strict feasibility condition. The iterates generated by the algorithm are bounded when the problem is a P* LCP and has a solution. Moreover, when the problem is a monotone LCP and has a solution, we prove that the convergence rate is globally linear and it achieves `-feasibility and `-complementarity in at most O(n2 ln(1/`)) iterations with a properly chosen starting point. |
| |
Keywords: | linear complementarity problem infeasible interior point method infeasible regularized central path global convergence polynomiality |
本文献已被 SpringerLink 等数据库收录! |
|