On homogeneous and self-dual algorithms for LCP |
| |
Authors: | Yinyu Ye |
| |
Institution: | (1) Department of Management Sciences, The University of Iowa, 52242 Iowa City, IA, USA |
| |
Abstract: | We present some generalizations of a homogeneous and self-dual linear programming (LP) algorithm to solving the monotone linear
complementarity problem (LCP). Again, while it achieves the best known interior-point iteration complexity, the algorithm
does not need to use any “big-M” number, and it detects LCP infeasibility by generating a certificate. To our knowledge, this is the first interior-point
and infeasible-starting algorithm for the LCP with these desired features.
Research supported in part by NSF Grant DDM-9207347, the University of Iowa Oberman Fellowship and the Iowa College of Business
Administration Summer Grant. Part of this work is done while the author is visiting the Delft Optimization Center at the University
of Technology, Delft, Netherlands, supported by the Dutch Organization for Scientific Research (NWO). |
| |
Keywords: | Linear complementarity problem Homogeneous and self-dual model Infeasible-starting algorithm |
本文献已被 SpringerLink 等数据库收录! |
|