The plain Newton-min algorithm for solving the linear complementarity problem (LCP) "0 x. (Mx+q) 0" can be viewed as an instance of the plain semismooth Newton method on the equational version "min(x, M...
详细信息
The plain Newton-min algorithm for solving the linear complementarity problem (LCP) "0 x. (Mx+q) 0" can be viewed as an instance of the plain semismooth Newton method on the equational version "min(x, Mx + q) = 0" of the problem. This algorithm converges for any q when M is an M-matrix, but not when it is a P-matrix. When convergence occurs, it is often very fast (in at most n iterations for an M-matrix, where n is the number of variables, but often much faster in practice). In 1990, Harker and Pang proposed to improve the convergence ability of this algorithm by introducing a stepsize along the Newton-min direction that results in a jump over at least one of the encountered kinks of the min-function, in order to avoid its points of nondifferentiability. This paper shows that, for the Fathi problem (an LCP with a positive definite symmetric matrix M, hence a P-matrix), an algorithmic scheme, including the algorithm of Harker and Pang, may require n iterations to converge, depending on the starting point.
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...
详细信息
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.
暂无评论