A feasible semismooth asymptotically Newton method for mixed complementarity problems

Defeng Sun, R.S. Womersley, H. Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

39 Citations (Scopus)

Abstract

Semismooth Newton methods constitute a major research area for solving mixed complementarity problems (MCPs). Early research on semismooth Newton methods is mainly on infeasible methods. However, some MCPs are not well defined outside the feasible region or the equivalent unconstrained reformulations of other MCPs contain local minimizers outside the feasible region. As both these problems could make the corresponding infeasible methods fail, more recent attention is on feasible methods. In this paper we propose a new feasible semismooth method for MCPs, in which the search direction asymptotically converges to the New ton direction. The new method overcomes the possible non-convergence of the projected semismooth Newton method, which is widely used in various numerical implementations, by minimizing a one-dimensional quadratic convex problem prior to doing (curved) line searches. As with other semismooth Newton methods, the proposed method only solves one linear system of equations at each iteration.The sparsity of the Jacobian of the reformulated system can be exploited, often reducing the size of the system that must be solved. The reason for this is that the projection onto the feasible set increases the likelihood of components of iterates being active. The global and superlinear/quadratic convergence of the proposed method is proved under mild conditions. Numerical results are reported on all problems from the MCPLIB collection [8].
Original languageEnglish
Pages (from-to)167-187
Number of pages21
JournalMathematical Programming, Series B
Volume94
Issue number1
DOIs
Publication statusPublished - 1 Dec 2002
Externally publishedYes

Keywords

  • Convergence
  • Mixed complementarity problems
  • Projected Newton method
  • Semismooth equations

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Software
  • Mathematics(all)
  • Applied Mathematics
  • Safety, Risk, Reliability and Quality
  • Management Science and Operations Research

Cite this