A recursive semi-smooth Newton method for linear complementarity problems
Philipp Hungerlaender (philipp.hungerlaenderaau.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.
Entry Submitted: 09/21/2016
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|