Complexity of a Noninterior Path-Following Method for the Linear Complementarity Problem期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Complexity of a Noninterior Path-Following Method for the Linear Complementarity Problem

Authors:

Affiliation:

(1) Department of Mathematics, University of Washington, Seattle, Washington;(2) Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada

Abstract:

We study the complexity of a noninterior path-following method for the linear complementarity problem. The method is based on the Chen–Harker–Kanzow–Smale smoothing function. It is assumed that the matrix M is either a P-matrix or symmetric and positive definite. When M is a P-matrix, it is shown that the algorithm finds a solution satisfying the conditions Mx-y+q=0 and $left| {{text{min{ }}x,y{text{} }}} right|_infty leqslant varepsilon$ in at most

$mathcal{O}((2 + beta )(1 + (1/l(M)))^2 log ((1 + (1/2)beta )mu _0 )/varepsilon ))$

Newton iterations; here, beta

and µ₀ depend on the initial point, l(M) depends on M, and epsiv

> 0. When Mis symmetric and positive definite, the complexity bound is

$mathcal{O}((2 + beta )C^2 log ((1 + (1/2)beta )mu _0 )/varepsilon ),$

where

$C = 1 + (sqrt n /(min { lambda _{min } (M),1/lambda _{max } (M)} ),$

and $lambda _{min } (M),lambda _{max } (M)$ are the smallest and largest eigenvalues of M.

Keywords:

Linear complementarity noninterior path-following methods complexity of algorithms

本文献已被 SpringerLink 等数据库收录！

设为首页 | 免责声明 | 关于勤云 | 加入收藏