Optimization Online


A recursive semi-smooth Newton method for linear complementarity problems

Philipp Hungerlaender (philipp.hungerlaender***at***aau.at)
Joaquim Judice (joaquim.judice***at***co.it.pt)
Franz Rendl (franz.rendl***at***aau.at)

Abstract: A primal feasible active set method is presented for finding the unique solution of a Linear Complementarity Problem (LCP) with a P-matrix, which extends the globally convergent active set method for strictly convex quadratic problems with simple bounds proposed by [P. Hungerlaender and F. Rendl. A feasible active set method for strictly convex problems with simple bounds. SIAM Journal on Optimization, 25(3):1633–1659, 2015]. Based on a guess of the active set, a primal-dual pair (x,u) is computed that satisfies stationarity and the complementary condition. If x is not feasible, the variables connected to the infeasibilities are added to the active set and a new primal-dual pair (x,u) is computed. This process is iterated until a primal feasible solution is generated. Then a new active set is determined based on the feasibility information of the dual variable u. We prove that the algorithm stops after a finite number of steps with the unique solution of the LCP. An extension of the algorithm with similar convergence properties is also introduced for finding the unique solution of the Bound Linear Complementarity Problem (BLCP) with a P-matrix. Computational experience indicates that these approaches are very efficient for solving large-scale LCPs and BLCPs in practice.

Keywords: primal-dual active set methods, semismooth Newton methods, linear complementarity problem, convex quadratic programming, global convergence

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Nonlinear Optimization (Bound-constrained Optimization )

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Technical report, Alpen-Adria Universität Klagenfurt, Mathematics, Optimization Group, TR-AAUK-M-O-16-09-21, 2016.

Download: [PDF]

Entry Submitted: 09/21/2016
Entry Accepted: 09/21/2016
Entry Last Modified: 12/15/2016

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