Bonettini, Silvia; Galligani, Emanuele; Ruggiero, Valeria Inner solvers for interior point methods for large scale nonlinear programming. (English) Zbl 1146.90068 Comput. Optim. Appl. 37, No. 1, 1-34 (2007). Summary: This paper deals with the solution of nonlinear programming problems arising from elliptic control problems by an interior point scheme. At each step of the scheme, we have to solve a large scale symmetric and indefinite system; inner iterative solvers, with an adaptive stopping rule, can be used in order to avoid unnecessary inner iterations, especially when the current outer iterate is far from the solution. In this work, we analyse the method of multipliers and the preconditioned conjugate gradient method as inner solvers for interior point schemes. We discuss the convergence of the whole approach, the implementation details and report the results of numerical experimentation on a set of large scale test problems arising from the discretization of elliptic control problems. A comparison with other interior point codes is also reported. Cited in 2 Documents MSC: 90C30 Nonlinear programming 90C51 Interior-point methods 90C06 Large-scale problems in mathematical programming Keywords:method of multipliers; preconditioned conjugate gradient method Software:HSL; ipfilter; IP-PCG; Ipopt; CG+ PDFBibTeX XMLCite \textit{S. Bonettini} et al., Comput. Optim. Appl. 37, No. 1, 1--34 (2007; Zbl 1146.90068) Full Text: DOI References: [1] Altman, A., Gondzio, J.: Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization. Optim. Methods Softw. 11–12, 275–302 (1999) · Zbl 0957.90101 [2] Apostol, T.M.: Mathematical Analysis, 2nd edn. Addison-Wesley, Reading (1974) · Zbl 0309.26002 [3] Argáez, M., Tapia, R., Velázquez, L.: Numerical comparisons of path-following strategies for a primal–dual interior-point method for nonlinear programming. J. Optim. Theory Appl. 114, 255–272 (2002) · Zbl 1026.90095 [4] Bergamaschi, L., Gondzio, J., Zilli, G.: Preconditioning indefinite systems in interior point methods for optimization. Comput. Optim. Appl. 28, 149–171 (2004) · Zbl 1056.90137 [5] Bonettini, S.: A nonmonotone inexact Newton method. Optim. Methods Softw. 20, 475–491 (2005) · Zbl 1138.65036 [6] Bonettini, S., Galligani, E., Ruggiero, V.: An inexact Newton method combined with Hestenes multipliers’ scheme for the solution of Karush–Kuhn–Tucker systems. Appl. Math. Comput. 168, 651–676 (2005) · Zbl 1080.65046 [7] Bonettini, S., Ruggiero, V.: Some iterative methods for the solution of a symmetric indefinite KKT system. Comput. Optim. Appl. (2006, to appear) · Zbl 1171.90547 [8] Bunch, J.R., Parlett, B.N.: Direct methods for solving symmetric indefinite systems of linear equations. SIAM J. Numer. Anal. 8, 639–655 (1971) · Zbl 0222.65038 [9] Byrd, R.H., Gilbert, J.C., Nocedal, J.: A trust region method based on interior-point techniques for nonlinear programming. Math. Program. 89, 149–185 (2000) · Zbl 1033.90152 [10] Byrd, R.H., Marazzi, M., Nocedal, J.: On the convergence of Newton iterations to non-stationary points. Technical report OTC 2001/01, Optimization Technology Center, Northwestern University, Evanston (2001) · Zbl 1072.90038 [11] D’Apuzzo, M., Marino, M.: Parallel computational issues of an interior point method for solving large bound-constrained quadratic programming problems. Parallel Comput. 29, 467–483 (2003) [12] Dembo, R.S., Eisenstat, S.C., Steihaug, T.: Inexact Newton methods. SIAM J. Numer. Anal. 19, 400–408 (1982) · Zbl 0478.65030 [13] Durazzi, C.: Numerical solution of discrete quadratic optimal control problems by Hestenes’ method. Rend. Circ. Mat. Palermo Suppl. 58(2), 133–154 (1999) · Zbl 0930.65076 [14] Durazzi, C.: On the Newton interior-point method for nonlinear programming problems. J. Optim. Theory Appl. 104, 73–90 (2000) · Zbl 0960.90093 [15] Durazzi, C., Galligani, E.: Nonlinear programming methods for solving optimal control problems. In: Giannessi, F., Maugeri, A., Pardalos, P.M. (eds.) Equilibrium Problems: Nonsmooth Optimization and Variational Inequality Models, Nonconvex Optimization and Its Applications, vol. 58, pp. 71–99. Kluwer Academic, Dordrecht (2001) · Zbl 1039.90091 [16] Durazzi, C., Ruggiero, V.: Indefinitely preconditioned conjugate gradient method for large sparse equality and inequality constrained quadratic problems. Numer. Linear Algebra Appl. 10, 673–688 (2003) · Zbl 1071.65512 [17] Durazzi, C., Ruggiero, V.: Numerical solution of special linear and quadratic programs via a parallel interior-point method. Parallel Comput. 29, 485–503 (2003) [18] Durazzi, C., Ruggiero, V.: Global convergence of the Newton interior-point method for nonlinear programming. J. Optim. Theory Appl. 120, 199–208 (2004) · Zbl 1073.90062 [19] Durazzi, C., Ruggiero, V., Zanghirati, G.: Parallel interior-point method for linear and quadratic programs with special structure. J. Optim. Theory Appl. 110, 289–313 (2001) · Zbl 1006.90087 [20] Eisenstat, S.C., Walker, H.F.: Globally convergent inexact Newton methods. SIAM J. Optim. 4, 393–422 (1994) · Zbl 0814.65049 [21] El–Bakry, A.S., Tapia, R.A., Tsuchiya, T., Zhang, Y.: On the formulation and theory of Newton interior-point method for nonlinear programming. J. Optim. Theory Appl. 89, 507–541 (1996) · Zbl 0851.90115 [22] Fletcher, R.: Practical Methods of Optimization. 2nd edn. Wiley, Chichester (1987) · Zbl 0905.65002 [23] Forsgren, A.: Inertia-controlling factorizations for optimization algorithms. Appl. Numer. Math. 43, 91–107 (2002) · Zbl 1016.65039 [24] Galligani, E.: The Newton-arithmetic mean method for the solution of systems of nonlinear equations. Appl. Math. Comput. 134, 9–34 (2003) · Zbl 1047.65031 [25] Galligani, I., Ruggiero, V.: Numerical solution of equality-constrained quadratic programming problems on vector-parallel computers. Optim. Methods Softw. 2, 233–247 (1993) [26] Galligani, E., Ruggiero, V., Zanni, L.: A minimization method for the solution of large symmetric eigenproblems. Int. J. Comput. Math. 70, 99–115 (1998) · Zbl 0936.65038 [27] Gill, P.E., Murray, D.B., Ponceleon, D.B., Saunders, M.A.: Preconditioners for indefinite systems arising in optimization. SIAM J. Matrix Anal. Appl. 13, 292–311 (1992) · Zbl 0749.65037 [28] Gill, P.E., Saunders, M.A., Shinnerl, J.R.: On the stability of Choleski factorization for symmetric quasidefinite systems. SIAM J. Matrix Anal. Appl. 17, 35–46 (1996) · Zbl 0878.49020 [29] Golub, G., Greif, C.: On solving block-structured indefinite linear systems. SIAM J. Sci. Comput. 24, 2076–2092 (2003) · Zbl 1036.65033 [30] Golub, G., Wu, X., Yuan, J.Y.: SOR-like methods for augmented system. BIT 41, 71–85 (2001) · Zbl 0991.65036 [31] Harwell Subroutine Library: A Catalogue of Subroutines (HSL 2000). AEA Technology, Harwell, Oxfordshire (2002) [32] Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303–320 (1969) · Zbl 0174.20705 [33] Hestenes, M.R.: Optimization Theory. The Finite-Dimensional Case. Wiley, New York (1975) · Zbl 0327.90015 [34] Keller, C., Gould, N.I.M., Wathen, A.J.: Constraint preconditioners for indefinite linear systems. SIAM J. Matrix Anal. Appl. 21, 1300–1317 (2000) · Zbl 0960.65052 [35] Li, C., Li, Z., Shao, X., Nie, Y., Evans, D.J.: Optimum parameter for the SOR-like method for augmented system. Int. J. Comput. Math. 81, 749–763 (2004) · Zbl 1068.65043 [36] Liu, J.W., Ng, E.G., Peyton, B.W.: On finding supernodes for sparse matrix computations. SIAM J. Matrix Anal. Appl. 14, 242–252 (1993) · Zbl 0765.65034 [37] Luenberger, D.G.: Linear and Nonlinear Programming, 2nd edn. Addison-Wesley, Reading (1984) · Zbl 0571.90051 [38] Lukšan, L., Matonoha, C., Vlček, J.: Interior-point method for non-linear non-convex optimization. Numer. Linear Algebra Appl. 11, 431–453 (2004) · Zbl 1164.90422 [39] Lukšan, L., Vlček, J.: Indefinitely preconditioned inexact Newton method for large sparse equality constrained non-linear programming problems. Numer. Linear Algebra Appl. 5, 219–247 (1998) · Zbl 0937.65066 [40] Maurer, H., Mittelmann, H.D.: Optimization techniques for solving elliptic control problems with control and state constraints: Part 1. Boundary control. Comput. Optim. Appl. 16, 29–55 (2000) · Zbl 0961.93026 [41] Maurer, H., Mittelmann, H.D.: Optimization techniques for solving elliptic control problems with control and state constraints: Part 2. Distributed control. Comput. Optim. Appl. 18, 141–160 (2001) · Zbl 0977.93037 [42] Mittelmann, H.D.: Verification of second-order sufficient optimality conditions for semilinear elliptic and parabolic control problems. Comput. Optim. Appl. 20, 93–110 (2001) · Zbl 0986.49011 [43] Mittelmann, H.D.: Private communication (2004) [44] Mittelmann, H.D., Maurer, H.: Solving elliptic control problems with interior point and SQP methods: control and state constraints. J. Comput. Appl. Math. 120, 175–195 (2000) · Zbl 0959.65081 [45] Morales, J.L., Nocedal, J., Waltz, R.A., Liu, G., Goux, J.P.: Assessing the potential of interior methods for nonlinear optimization. Technical report OTC 2001/04, Optimization Technology Center, Northwestern University, Evanston (2001) · Zbl 1062.65063 [46] Nocedal, J., Hribar, M.E., Gould, N.I.M.: On the solution of equality constrained quadratic programming problems arising in optimization. SIAM J. Sci. Comput. 23, 1375–1394 (2001) · Zbl 0999.65050 [47] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (1999) · Zbl 0930.65067 [48] Powell, M.J.D.: A method for nonlinear constraints in minimization problems. In: Fletcher, R. (ed.) Optimization, pp. 283–298. Academic, London (1969) · Zbl 0194.47701 [49] Rheinboldt, W.C.: Methods for Solving Systems of Nonlinear Equations, 2nd edn. SIAM, Philadelphia (1998) · Zbl 0906.65051 [50] Saad, Y.: Iterative Methods for Sparse Linear System. PSW, Boston (1996) · Zbl 1031.65047 [51] Saunders, M., Tomlin, J.A.: Solving regularized linear programs using barrier methods and KKT systems. Technical report SOL 96–4, Systems Optimization Lab., Dept. Oper. Res., Stanford University, Stanford (1996) [52] Van Loan, C.: On the method of weighting for equality-constrained least-squares problems. SIAM J. Numer. Anal. 22, 851–864 (1985) · Zbl 0584.65015 [53] Vanderbei, R.J.: Symmetric quasidefinite matrices. SIAM J. Optim. 5, 100–113 (1995) · Zbl 0822.65017 [54] Vanderbei, R.J., Shanno, D.F.: An interior-point algorithm for nonconvex nonlinear programming. Comput. Optim. Appl. 13, 231–252 (1999) · Zbl 1040.90564 [55] Wächter, A.: An interior point algorithm for large-scale nonlinear optimization with applications in processes engineering. Ph.D. thesis, Carnegie Mellon University, Pittsburgh (2002) [56] Wächter, A., Biegler, L.T.: Failure of global convergence for a class of interior point methods for nonlinear programming. Math. Program. 88, 565–574 (2000) · Zbl 0963.65063 [57] Wang, D., Bai, Z.Z., Evans, D.J.: On the monotone convergence of multisplitting method for a class of systems of weakly nonlinear equations. Int. J. Comput. Math. 60, 229–242 (1996) · Zbl 1001.65515 [58] Wright, M.: The interior-point revolution in optimization: history, recent developments, and lasting consequences. Bull. Amer. Math. Soc. 42, 39–56 (2005) · Zbl 1114.90153 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.