A structured modified Newton approach for solving systems of nonlinear equations arising in interior-point methods for quadratic programming

The focus in this work is interior-point methods for quadratic optimization problems with linear inequality constraints where the system of nonlinear equations that arise are solved with Newton-like methods. In particular, the concern is the system of linear equations to be solved at each iteration. Newton systems give high quality solutions but there is an interest in designing modified Newton systems which are computationally less expensive but normally at the expense of lower quality solutions. We propose a structured modified Newton approach where the Jacobian of each Newton system is approximated by a Jacobian at a previous point plus a sequence of low-rank update matrices. The updates are such that the Jacobian approximation preserves its sparsity structure and in consequence may be viewed as a Jacobian evaluated at a different point. We introduce the theoretical setting, motivate the approach by theoretical results applicable in the asymptotic region and give numerical results for a set of convex quadratic programs. In an attempt to improve performance we also motivate and construct two heuristics to be added to the method.

Article

Download

View A structured modified Newton approach for solving systems of nonlinear equations arising in interior-point methods for quadratic programming