Approximate solution of system of equations arising in interior-point methods for bound-constrained optimization

• Published in: Computational optimization and applications 2021-05, Vol.79 (1), p.155-191
• Main Authors: Ek, David, Forsgren, Anders
• Format: Article
• Language: English
• Subjects: Approximate solution of system of linear equations; Asymptotic error bound; Bound constrained optimization; Constrained non-linear optimizations; Constrained optimization; Constraints; Convex and Discrete Geometry; Economic and social effects; Error analysis; High-quality solutions; Interior-point method; Interior-point methods; Iterative methods; Linear equations; Linear programming; Management Science; Mathematics; Mathematics and Statistics; Newton-like approaches; Nonlinear equations; Nonlinear programming; Operations Research; Operations Research/Decision Theory; Optimization; Statistics; System of linear equations; System of nonlinear equations; Theoretical framework
• ISSN: 0926-6003; 1573-2894; 1573-2894
• DOI: 10.1007/s10589-021-00265-8

The focus in this paper is interior-point methods for bound-constrained nonlinear optimization, where the system of nonlinear equations that arise are solved with Newton’s method. There is a trade-off between solving Newton systems directly, which give high quality solutions, and solving many approximate Newton systems which are computationally less expensive but give lower quality solutions. We propose partial and full approximate solutions to the Newton systems. The specific approximate solution depends on estimates of the active and inactive constraints at the solution. These sets are at each iteration estimated by basic heuristics. The partial approximate solutions are computationally inexpensive, whereas a system of linear equations needs to be solved for the full approximate solution. The size of the system is determined by the estimate of the inactive constraints at the solution. In addition, we motivate and suggest two Newton-like approaches which are based on an intermediate step that consists of the partial approximate solutions. The theoretical setting is introduced and asymptotic error bounds are given. We also give numerical results to investigate the performance of the approximate solutions within and beyond the theoretical framework.