Subspace accelerated matrix splitting algorithms for bound-constrained quadratic programming and linear complementarity problems

Daniel Robinson(daniel.p.robinsongmail.com)
Liming Feng(fenglmillinois.edu)
Jorge Nocedal(nocedaleecs.northwestern.edu)
Jong-Shi Pang(jspangillinois.edu)

Abstract: This paper studies the solution of two problems---bound-constrained quadratic programs and linear complementarity problems---by two-phase methods that consist of an active set prediction phase and a subspace phase. The algorithms enjoy favorable convergence properties under weaker assumptions than those assumed for other methods in the literature. The active set prediction phase employs matrix splitting iterations that are tailored to the structure of the (nonconvex) bound-constrained problems and the (asymmetric) linear complementarity problems studied in this paper. Numerical results on a variety of test problems illustrate the performance of the methods.

Keywords: quadratic programming, linear complementarity, iterative methods, Jacobi iteration, Gauss-Seidel iteration, splitting methods, two-phase methods, American options pricing

Category 1: Nonlinear Optimization (Bound-constrained Optimization )

Category 2: Applications -- OR and Management Sciences (Finance and Economics )

Citation: Report 07-11 Department of Industrial Engineering and Management Sciences, 2145 Sheridan Road, Evanston, IL 60208

Download: [PDF]

Entry Submitted: 09/28/2011
Entry Accepted: 09/28/2011
Entry Last Modified: 09/28/2011

Modify/Update this entry