Newton iterations in implicit time-stepping scheme for differential linear complementarity systems

Xiaojun Chen, Shuhuang Xiang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

21 Citations (Scopus)

Abstract

We propose a generalized Newton method for solving the system of nonlinear equations with linear complementarity constraints in the implicit or semi-implicit time-stepping scheme for differential linear complementarity systems (DLCS). We choose a specific solution from the solution set of the linear complementarity constraints to define a locally Lipschitz continuous right-hand-side function in the differential equation. Moreover, we present a simple formula to compute an element in the Clarke generalized Jacobian of the solution function. We show that the implicit or semi-implicit time-stepping scheme using the generalized Newton method can be applied to a class of DLCS including the nondegenerate matrix DLCS and hidden Z-matrix DLCS, and has a superlinear convergence rate. To illustrate our approach, we show that choosing the least-element solution from the solution set of the Z-matrix linear complementarity constraints can define a Lipschitz continuous right-hand-side function with a computable Lipschitz constant. The Lipschitz constant helps us to choose the step size of the time-stepping scheme and guarantee the convergence.
Original languageEnglish
Pages (from-to)579-606
Number of pages28
JournalMathematical Programming
Volume138
Issue number1-2
DOIs
Publication statusPublished - 1 Apr 2013

Keywords

  • Differential linear complementarity problem
  • Generalized Newton method
  • Least-element solution
  • Least-norm solution
  • Nondegenerate matrix
  • Z-matrix

ASJC Scopus subject areas

  • Mathematics(all)
  • Software

Cite this