A lower bound on the iterative complexity of the Harker and Pang globalization technique of the Newton-min algorithm for solving the linear complementarity problem

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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Jean-Pierre Dussault, Mathieu Frappier, Jean Charles Gilbert
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2019
Materias:	15B99 47B99 49M15 65K15 90C33 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/e96a6ead91534eb1801297a47f42427e
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:e96a6ead91534eb1801297a47f42427e
record_format	dspace
spelling	oai:doaj.org-article:e96a6ead91534eb1801297a47f42427e2021-12-02T05:01:13ZA lower bound on the iterative complexity of the Harker and Pang globalization technique of the Newton-min algorithm for solving the linear complementarity problem2192-440610.1007/s13675-019-00116-6https://doaj.org/article/e96a6ead91534eb1801297a47f42427e2019-12-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621001210https://doaj.org/toc/2192-4406The 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.Jean-Pierre DussaultMathieu FrappierJean Charles GilbertElsevierarticle15B9947B9949M1565K1590C33Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 7, Iss 4, Pp 359-380 (2019)
institution	DOAJ
collection	DOAJ
language	EN
topic	15B99 47B99 49M15 65K15 90C33 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	15B99 47B99 49M15 65K15 90C33 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Jean-Pierre Dussault Mathieu Frappier Jean Charles Gilbert A lower bound on the iterative complexity of the Harker and Pang globalization technique of the Newton-min algorithm for solving the linear complementarity problem
description	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.
format	article
author	Jean-Pierre Dussault Mathieu Frappier Jean Charles Gilbert
author_facet	Jean-Pierre Dussault Mathieu Frappier Jean Charles Gilbert
author_sort	Jean-Pierre Dussault
title	A lower bound on the iterative complexity of the Harker and Pang globalization technique of the Newton-min algorithm for solving the linear complementarity problem
title_short	A lower bound on the iterative complexity of the Harker and Pang globalization technique of the Newton-min algorithm for solving the linear complementarity problem
title_full	A lower bound on the iterative complexity of the Harker and Pang globalization technique of the Newton-min algorithm for solving the linear complementarity problem
title_fullStr	A lower bound on the iterative complexity of the Harker and Pang globalization technique of the Newton-min algorithm for solving the linear complementarity problem
title_full_unstemmed	A lower bound on the iterative complexity of the Harker and Pang globalization technique of the Newton-min algorithm for solving the linear complementarity problem
title_sort	lower bound on the iterative complexity of the harker and pang globalization technique of the newton-min algorithm for solving the linear complementarity problem
publisher	Elsevier
publishDate	2019
url	https://doaj.org/article/e96a6ead91534eb1801297a47f42427e
work_keys_str_mv	AT jeanpierredussault alowerboundontheiterativecomplexityoftheharkerandpangglobalizationtechniqueofthenewtonminalgorithmforsolvingthelinearcomplementarityproblem AT mathieufrappier alowerboundontheiterativecomplexityoftheharkerandpangglobalizationtechniqueofthenewtonminalgorithmforsolvingthelinearcomplementarityproblem AT jeancharlesgilbert alowerboundontheiterativecomplexityoftheharkerandpangglobalizationtechniqueofthenewtonminalgorithmforsolvingthelinearcomplementarityproblem AT jeanpierredussault lowerboundontheiterativecomplexityoftheharkerandpangglobalizationtechniqueofthenewtonminalgorithmforsolvingthelinearcomplementarityproblem AT mathieufrappier lowerboundontheiterativecomplexityoftheharkerandpangglobalizationtechniqueofthenewtonminalgorithmforsolvingthelinearcomplementarityproblem AT jeancharlesgilbert lowerboundontheiterativecomplexityoftheharkerandpangglobalizationtechniqueofthenewtonminalgorithmforsolvingthelinearcomplementarityproblem
_version_	1718400863989399552

A lower bound on the iterative complexity of the Harker and Pang globalization technique of the Newton-min algorithm for solving the linear complementarity problem

Ejemplares similares