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.
The paper "An algorithmic Characterization of P-Matricity" [SIAM J. Matrix Anal. Appl., 34 (2013), pp. 904-916], by the same authors as here, implicitly assumes that the iterates generated by the newton-min ...
详细信息
The paper "An algorithmic Characterization of P-Matricity" [SIAM J. Matrix Anal. Appl., 34 (2013), pp. 904-916], 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 perpendicular to (Mx + 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 q is. The proof is not more complex, requiring only some adjustments, which are essential, however.
In this thesis, we consider variational inequalities in the form of partial differential equations with complementarity constraints. We construct a posteriori error estimates for discretizations using the finite eleme...
详细信息
In this thesis, we consider variational inequalities in the form of partial differential equations with complementarity constraints. We construct a posteriori error estimates for discretizations using the finite element method and the finite volume method, for inexact linearizations employing any semismooth newton solver and any iterative linear algebraic solver. First, we consider the model problem of contact between two membranes, next we consider its extension into a parabolic variational inequality, and to finish we treat a two-phase compositional flow with phase transition as an industrial application. In the first chapter, we consider the stationnary problem of contact between two membranes. This problem belongs to the wide range of variational inequalities of the first kind. Our discretization is based on the finite element method with polynomials of order p ≥ 1, and we propose two discrete equivalent formulations: the first one as a variational inequality, and the second one as a saddle-point-type problem. We employ the Clarke differential so as to treat the nondifferentiable nonlinearities. It enables us to use semismooth newtonalgorithms. Next, any iterative linear algebraic solver is used for the linear system stemming from the discretization. Employing the methodology of equilibrated flux reconstructions in the space H(div, Ω), we get an upper bound on the total error in the energy norm H 1 0 (Ω). This bound is fully computable at each semismooth newton step and at each linear algebraic step. Our estimation distinguishes in particular the three components of the error, namely the discretization error (finite elements), the linearization error (semismooth newton method), and the algebraic error (GMRES algorithm). We then formulate adaptive stopping criteria for our solvers to ulti- mately reduce the number of iterations. We also prove, in the inexact semismooth context, the local efficiency property of our estimators, up to a contact term that appears ne
It is shown that a nondegenerate square real matrix M is a P-matrix if and only if, whatever is the real vector q, the newton-min algorithm does not cycle between two points when it is used to solve the linear complem...
详细信息
It is shown that a nondegenerate square real matrix M is a P-matrix if and only if, whatever is the real vector q, the newton-min algorithm does not cycle between two points when it is used to solve the linear complementarity problem 0 <= x perpendicular to (Mx vertical bar q) >= 0.
暂无评论