Interior-Point Methods for Complementarity Problems
Based on Self-Regular Proximities
This chapter extends the approach for solving LO problems in the previous chapter to the case of linear and nonlinear P*(k) complementarity problems (LCPs andNCPs). First, several elementary results about P*(k) mappings are provided. To establish global convergence of the algorithm, a new smoothness condition for the mapping is introduced. This condition is closely related to the relative Lipschitz condition and applicable to nonmonotone mappings. New search directions for solving the underlying problem are proposed based on self-regular proximities. We show that if a strictly feasible starting point is available and the mapping involved satisfies a certain smoothness condition, then these new IPMs for solving P*(k) CPs have polynomial iteration bounds similar to those of their LO cousins.