A structured modified Newton approach for solving systems of nonlinear equations arising in interior-point methods for quadratic programming
From MaRDI portal
Publication:6166646
DOI10.1007/S10589-023-00486-ZarXiv2009.07913OpenAlexW3085530484MaRDI QIDQ6166646FDOQ6166646
Authors: David Ek, Anders Forsgren 
Publication date: 3 August 2023
Published in: Computational Optimization and Applications (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/2009.07913
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
- Methods for Modifying Matrix Factorizations
- A repository of convex quadratic programming problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization
- Iterative Solution of Nonlinear Equations in Several Variables
- Inexact Newton Methods
- A primal-dual regularized interior-point method for convex quadratic programs
- Interior Methods for Nonlinear Optimization
- Bounds on Eigenvalues of Matrices Arising from Interior-Point Methods
- Stability of Augmented System Factorizations in Interior-Point Methods
- Title not available (Why is that?)
- Inexact interior-point method
- On mutual impact of numerical linear algebra and large-scale optimization with focus on interior point methods
- Convergence analysis of an inexact feasible interior point method for convex quadratic programming
- Iterative Solution of Augmented Systems Arising in Interior Methods
- Stability of Symmetric Ill-Conditioned Systems Arising in Interior Methods for Constrained Optimization
- Maintaining LU factors of a general sparse matrix
- Ill-Conditioning and Computational Error in Interior Methods for Nonlinear Programming
- On the efficient update of rectangular LU-factorizations subject to low rank modifications
- Title not available (Why is that?)
- Quasi-Newton approaches to interior point methods for quadratic problems
- Title not available (Why is that?)
- Local path-following property of inexact interior methods in nonlinear programming
- Effects of finite-precision arithmetic on interior-point methods for nonlinear programming
- A comparison of reduced and unreduced KKT systems arising from interior point methods
- Spectral estimates for unreduced symmetric KKT systems arising from Interior Point methods
- Stability of Linear Equations Solvers in Interior-Point Methods
- Stability and accuracy of inexact interior point methods for convex quadratic programming
- Approximate solution of system of equations arising in interior-point methods for bound-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)
