Iteration complexity of an interior-point algorithm for nonlinear p∗-complementarity problems

Abstract

This paper provides an analysis of the iterative complexity of a predictor-corrector type interior-point algorithm for a class of non-monotone nonlinear complementarity problems, i.e., the nonlinear P∗-complementarity problems, which is quite general because it includes as a special case the monotone complementarity problem. At each corrector step, one has to compute an approximate solution of a nonlinear system such that a certain accuracy requirement is satisfied. The proof of the iterative complexity of the proposed algorithm requires that the mapping associated the problem satisfies a scaled Lipschitz condition.

Keywords:

• Interior-point algorithm
• nonlinear P∗-complementarity problem
• iterative complexity
• scaled Lipschitz condition

C.R. Categories:

• G1.6 optimization
• G1.2