×

zbMATH — the first resource for mathematics

Approximate solution of system of equations arising in interior-point methods for bound-constrained optimization. (English) Zbl 07353217
Summary: 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.
MSC:
90C30 Nonlinear programming
90C51 Interior-point methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bertsekas, DP, On the Goldstein-Levitin-Polyak gradient projection method, IEEE Trans. Automatic Control, AC-21, 2, 174-184 (1976) · Zbl 0326.49025
[2] Bertsekas, DP, Projected Newton methods for optimization problems with simple constraints, SIAM J. Control Optim., 20, 2, 221-246 (1982) · Zbl 0507.49018
[3] Byrd, RH; Liu, G.; Nocedal, J., On the local behavior of an interior point method for nonlinear programming, 37-56 (1998), Boston: Addison-Wesley-Longman, Boston · Zbl 0902.65021
[4] Byrd, RH; Lu, P.; Nocedal, J.; Zhu, CY, A limited memory algorithm for bound constrained optimization, SIAM J. Sci. Comput., 16, 5, 1190-1208 (1995) · Zbl 0836.65080
[5] Coleman, TF; Li, Y., On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds, Math. Program., 67, 2, 189-224 (1994) · Zbl 0842.90106
[6] Conn, AR; Gould, NIM; Toint, PL, Global convergence of a class of trust region algorithms for optimization with simple bounds, SIAM J. Numer. Anal., 25, 2, 433-460 (1988) · Zbl 0643.65031
[7] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust region methods. Society for Industrial and Applied Mathematics (2000). doi:10.1137/1.9780898719857. URL doi:10.1137/1.9780898719857 · Zbl 0958.65071
[8] Facchinei, F.; Júdice, J.; Soares, Ja, An active set Newton algorithm for large-scale nonlinear programs with box constraints, SIAM J. Optim., 8, 1, 158-186 (1998) · Zbl 0911.90301
[9] Forsgren, A.; Gill, PE, Primal-dual interior methods for nonconvex nonlinear programming, SIAM J. Optim., 8, 4, 1132-1152 (1998) · Zbl 0915.90236
[10] Forsgren, A.; Gill, PE; Griffin, JD, Iterative solution of augmented systems arising in interior methods, SIAM J. Optim., 18, 2, 666-690 (2007) · Zbl 1143.49024
[11] Forsgren, A.; Gill, PE; Shinnerl, JR, Stability of symmetric ill-conditioned systems arising in interior methods for constrained optimization, SIAM J. Matrix Anal. Appl., 17, 1, 187-211 (1996) · Zbl 0878.49021
[12] Forsgren, A.; Gill, PE; Wright, MH, Interior methods for nonlinear optimization, SIAM Rev., 44, 4, 525-597 (2002) · Zbl 1028.90060
[13] Gill, PE; Murray, W.; Ponceleón, DB; Saunders, MA, Preconditioners for indefinite systems arising in optimization, SIAM J. Matrix Anal. Appl., 13, 292-311 (1992) · Zbl 0749.65037
[14] Gondzio, J.; Sobral, FNC, Quasi-Newton approaches to interior point methods for quadratic problems, Comput. Optim. Appl., 74, 1, 93-120 (2019) · Zbl 1427.90290
[15] Gould, N.; Orban, D.; Toint, P., Numerical methods for large-scale nonlinear optimization, Acta Numer., 14, 299-361 (2005) · Zbl 1119.65337
[16] Gould, NIM; Orban, D.; Toint, PL, CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization, Comput. Optim. Appl., 60, 3, 545-557 (2015) · Zbl 1325.90004
[17] Griva, I.; Nash, S.; Sofer, A., Linear and nonlinear optimization (2009), London: Society for Industrial and Applied Mathematics, London · Zbl 1159.90002
[18] Hager, WW; Zhang, H., A new active set algorithm for box constrained optimization, SIAM J. Optim., 17, 2, 526-557 (2006) · Zbl 1165.90570
[19] Heinkenschloss, M.; Ulbrich, M.; Ulbrich, S., Superlinear and quadratic convergence of affine-scaling interior-point Newton methods for problems with simple bounds without strict complementarity assumption, Math. Program., 86, 3, 615-635 (1999) · Zbl 0945.49023
[20] Kanzow, C.; Klug, A., On affine-scaling interior-point Newton methods for nonlinear minimization with bound constraints, Comput. Optim. Appl., 35, 2, 177-197 (2006) · Zbl 1151.90552
[21] Kim, D.; Sra, S.; Dhillon, I., Tackling box-constrained optimization via a new projected quasi-newton approach, SIAM J. Scientific Computing, 32, 3548-3563 (2010) · Zbl 1220.93085
[22] Lin, CJ; Moré, JJ, Newton’s method for large bound-constrained optimization problems, SIAM J. Optim. (1999) · Zbl 0957.65064
[23] Morini, B.; Simoncini, V., Stability and accuracy of inexact interior point methods for convex quadratic programming, J. Optim. Theory Appl., 175, 2, 450-477 (2017) · Zbl 1381.65046
[24] Nocedal, J.; Wright, SJ, Numerical optimization (2006), New York: Springer, New York · Zbl 1104.65059
[25] Orban, D., Siqueira, A.S.: JuliaSmoothOptimizers: Infrastructure and solvers for continuous optimization in Julia (2019). doi:10.5281/zenodo.2655082. URL https://juliasmoothoptimizers.github.io
[26] Ortega, JM; Rheinboldt, WC, Iterative Solution of Nonlinear Equations in Several Variables (2000), Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, Philadelphia, PA, USA · Zbl 0949.65053
[27] Schwartz, A.; Polak, E., Family of projected descent methods for optimization problems with simple bounds, J. Optim. Theory Appl., 92, 1, 1-31 (1997) · Zbl 0886.90140
[28] Vanderbei, RJ; Shanno, DF, An interior-point algorithm for nonconvex nonlinear programming, Computational optimization (1999) · Zbl 1040.90564
[29] Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 1, 25-57 (2006) · Zbl 1134.90542
[30] Waltz, RA; Morales, JL; Nocedal, J.; Orban, D., An interior algorithm for nonlinear optimization that combines line search and trust region steps, Math. Program., 107, 3, 391-408 (2006) · Zbl 1134.90053
[31] Wright, MH, Ill-Conditioning and computational error in interior methods for nonlinear programming, SIAM J. Optim., 9, 1, 84-111 (1999) · Zbl 0957.65056
[32] Wright, SJ, Stability of linear equations solvers in interior-point methods, SIAM J. Matrix Anal. Appl., 16, 4, 1287-1307 (1995) · Zbl 0840.65058
[33] Wright, SJ, Effects of finite-precision arithmetic on interior-point methods for nonlinear programming, SIAM J. Optim., 12, 1, 36-78 (2001) · Zbl 0994.90139
[34] Zhu, C.; Byrd, RH; Lu, P.; Nocedal, J., Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization, ACM Trans. Math. Softw., 23, 4, 550-560 (1997) · Zbl 0912.65057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.