Optimization Online


An algorithmic characterization of P-matricity II: adjustments, refinements, and validation

Ibtihel Ben Gharbia (ibtihel.ben-gharbia***at***ifpen.fr)
Jean Charles Gilbert (Jean-Charles.Gilbert***at***inria.fr)

Abstract: The paper "An algorithmic characterization of P-matricity" (SIAM Journal on Matrix Analysis and Applications, 34:3 (2013) 904916, by the same authors as here) implicitly assumes that the iterates generated by the Newton-min algorithm for solving a linear complementarity problem of dimension n, which reads 0 ⩽ x ⊥ (M x + q) ⩾ 0, are uniquely determined by some index subsets of [[1, n]]. Even if this is satisfied for a subset of vectors q that is dense in R^n, this assumption is improper, in particular in the statements where the vector q is not subject to restrictions. The goal of the present contribution is to show that, despite this blunder, the main result of that paper is preserved. This one claims that a nondegenerate matrix M is a P-matrix if and only if the Newton-min algorithm does not cycle between two distinct points, whatever is q. The proof is not more complex, requiring only some adjustments, which are essential however.

Keywords: linear complementarity problem, NM-matrix, Newton-min algorithm, P-matricity characterization, P-matrix, semismooth Newton method.

Category 1: Complementarity and Variational Inequalities

Citation: SIAM Journal on Matrix Analysis and Applications (to appear)

Download: [PDF]

Entry Submitted: 09/29/2018
Entry Accepted: 09/29/2018
Entry Last Modified: 04/12/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society