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

DOI10.1007/S10589-023-00486-ZMaRDI QIDQ6166646zbMATH OpenOpenAlexFDO

Authors David Ek, Anders Forsgren

Publication date 3 August 2023

Published in Computational Optimization and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2009.07913

zbMATH Keywords

interior-point methodsquasi-Newton methodsmodified Newton methodslow-rank updates

Mathematics Subject Classification ID

Quadratic programming (90C20) Interior-point methods (90C51)

Abstract: The focus in this work is on interior-point methods for inequality-constrained quadratic programs, and particularly on the system of nonlinear equations to be solved for each value of the barrier parameter. Newton iterations give high quality solutions, but we are interested in modified Newton systems that are computationally less expensive at the expense of lower quality solutions. We propose a structured modified Newton approach where each modified Jacobian is composed of a previous Jacobian, plus one low-rank update matrix per succeeding iteration. Each update matrix is, for a given rank, chosen such that the distance to the Jacobian at the current iterate is minimized, in both 2-norm and Frobenius norm. The approach is structured in the sense that it preserves the nonzero pattern of the Jacobian. The choice of update matrix is supported by results in an ideal theoretical setting. We also produce numerical results with a basic interior-point implementation to investigate the practical performance within and beyond the theoretical framework. In order to improve performance beyond the theoretical framework, we also motivate and construct two heuristics to be added to the method.

Recommendations

• On the Newton interior-point method for nonlinear programming problems
• An interior Newton method for quadratic programming
• A modified quasi-Newton method for nonlinear equations
• On the formulation and theory of the Newton interior-point method for nonlinear programming
• Quasi-Newton approaches to interior point methods for quadratic problems
• Solving nonlinear systems of equations by means of quasi-neston methods with a nonmonotone stratgy^∗
• Modified quasi-Newton methods for solving systems of linear equations
• scientific article; zbMATH DE number 1524343
• Quasi-Newton methods for solving nonlinear programming problems
• Modified Newton's methods for systems of nonlinear equations

Cites work

• scientific article; zbMATH DE number 4131946 (Why is no real title available?)
• scientific article; zbMATH DE number 5359577 (Why is no real title available?)
• scientific article; zbMATH DE number 1183039 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• A comparison of reduced and unreduced KKT systems arising from interior point methods
• A primal-dual regularized interior-point method for convex quadratic programs
• A repository of convex quadratic programming problems
• Approximate solution of system of equations arising in interior-point methods for bound-constrained optimization
• Bounds on Eigenvalues of Matrices Arising from Interior-Point Methods
• Convergence analysis of an inexact feasible interior point method for convex quadratic programming
• Effects of finite-precision arithmetic on interior-point methods for nonlinear programming
• Ill-Conditioning and Computational Error in Interior Methods for Nonlinear Programming
• Inexact Newton Methods
• Inexact interior-point method
• Interior Methods for Nonlinear Optimization
• Iterative Solution of Augmented Systems Arising in Interior Methods
• Iterative Solution of Nonlinear Equations in Several Variables
• Local path-following property of inexact interior methods in nonlinear programming
• Maintaining LU factors of a general sparse matrix
• Methods for Modifying Matrix Factorizations
• On mutual impact of numerical linear algebra and large-scale optimization with focus on interior point methods
• On the efficient update of rectangular LU-factorizations subject to low rank modifications
• Quasi-Newton approaches to interior point methods for quadratic problems
• Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization
• Spectral estimates for unreduced symmetric KKT systems arising from Interior Point methods
• Stability and accuracy of inexact interior point methods for convex quadratic programming
• Stability of Augmented System Factorizations in Interior-Point Methods
• Stability of Linear Equations Solvers in Interior-Point Methods
• Stability of Symmetric Ill-Conditioned Systems Arising in Interior Methods for Constrained Optimization

This page was built for publication: A structured modified Newton approach for solving systems of nonlinear equations arising in interior-point methods for quadratic programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166646)