Numerical Methods and Software for Quadratic Programming Problems with Linear Complementarity Constraints

Master thesis defense

Jonas Hall

Wednesday, February 24, 2021, 10:00 - 12:00

online

*************************************************
Online via Zoom
https://uni-freiburg.zoom.us/j/95013741122
Meeting-ID: 950 1374 1122
Password: 7UNZMu.xZ
*************************************************

Mathematical programs with complementarity constraints have received a lot of attention as they are particularly difficult to solve due to their lack of constraint qualifications in every feasible point. They appear in a wide range of applications, e.g. in engineering or economics, and many solution strategies have been discussed. One popular approach is to replace the complementarity constraints with a penalization term. In this work we focus on the subclass of quadratic programs with linear complementarity constraints. We illustrate a novel approach to solving a standard penalty reformulation using sequential convex programming, which derives from linearizing the (necessarily) nonconvex penalty function. This leads to a constant objective Hessian matrix throughout all iterates, and thus enables us to solve the linear complementarity quadratic program with a single factorization of the KKT matrix. This is done by making use of the hot-starting technique employed in the quadratic programming solver qpOASES. The introduced algorithm is tested in several scenarios and compared against state-of-the-art solvers demonstrating reliability and efficiency. Further, we briefly discuss the application of this algorithm to solving nonlinear programming problems with linear complementarity constraints.