×

An inertia-free filter line-search algorithm for large-scale nonlinear programming. (English) Zbl 1350.90031

Summary: We present a filter line-search algorithm that does not require inertia information of the linear system. This feature enables the use of a wide range of linear algebra strategies and libraries, which is essential to tackle large-scale problems on modern computing architectures. The proposed approach performs curvature tests along the search step to detect negative curvature and to trigger convexification. We prove that the approach is globally convergent and we implement the approach within a parallel interior-point framework to solve large-scale and highly nonlinear problems. Our numerical tests demonstrate that the inertia-free approach is as efficient as inertia detection via symmetric indefinite factorizations. We also demonstrate that the inertia-free approach can lead to reductions in solution time because it reduces the amount of convexification needed.

MSC:

90C30 Nonlinear programming
90C06 Large-scale problems in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agullo, E., Demmel, J., Dongarra, J., Hadri, B., Kurzak, J., Langou, J., Ltaief, H., Luszczek, P., Tomov, S.: Numerical linear algebra on emerging architectures: the PLASMA and MAGMA projects. J. Phys. Conf. Ser. 180, 012037 (2009)
[2] Amestoy, P.R., Guermouche, A., LExcellent, J.Y., Pralet, S.: Hybrid scheduling for the parallel solution of linear systems. Parallel Comput. 32(2), 136-156 (2006)
[3] Arora, Nikhil, Biegler, Lorenz T.: A trust region SQP algorithm for equality constrained parameter estimation with simple parameter bounds. Comput. Optim. Appl. 28(1), 51-86 (2004) · Zbl 1056.90139
[4] Balay, S., Brown, J., Buschelman, K., Eijkhout, V., Gropp, W., Kaushik, D., Knepley, M., McInnes, L., Smith, B., Zhang, H.: PETSc Users Manual Revision 3.4 (2013) · Zbl 1134.90542
[5] Benzi, M., Golub, G.H., Liesen, J.: Numerical solution of saddle point problems. Acta Numer. 14, 1-137 (2005) · Zbl 1115.65034
[6] Biegler, L.T., Zavala, V.M.: Large-scale nonlinear programming using IPOPT: an integrating framework for enterprise-wide dynamic optimization. Comput. Chem. Eng. 33(3), 575-582 (2009)
[7] Biros, G., Ghattas, O.: Parallel Lagrange-Newton-Krylov-Schur methods for PDE-constrained optimization. Part I: The Krylov-Schur solver. SIAM J. Sci. Comput. 27(2), 687-713 (2005) · Zbl 1091.65061
[8] Borzì, A., Schulz, V.: Multigrid methods for PDE optimization. SIAM Rev. 51(2), 361-395 (2009) · Zbl 1167.35354
[9] Bunch, J.R., Kaufman, L.: Some stable methods for calculating inertia and solving symmetric linear systems. Math. Comput. 31, 163-179 (1977) · Zbl 0355.65023
[10] 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
[11] Byrd, R.H., Curtis, F.E., Nocedal, J.: An inexact Newton method for nonconvex equality constrained optimization. Math. Program. 122(2), 273-299 (2010) · Zbl 1184.90127
[12] Cervantes, A.M., Wächter, A., Tütüncü, R.H., Biegler, L.T.: A reduced space interior point strategy for optimization of differential algebraic systems. Comput. Chem. Eng. 24(1), 39-51 (2000)
[13] Chiang, N., Grothey, A.: Solving security constrained optimal power flow problems by a structure exploiting interior point method. Optim. Eng. 16, 49-71 (2012) · Zbl 1364.90392
[14] Chiang, N., Petra, C.G., Zavala, V.M.: Structured nonconvex optimization of large-scale energy systems using PIPS-NLP. In: Proceedings of the 18th Power Systems Computation Conference (PSCC). Wroclaw, Poland (2014) · Zbl 1146.90055
[15] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust Region Methods, vol. 1. SIAM, Philadelphia (2000) · Zbl 0958.65071
[16] Costa, M.P., Fernandes, E.M.G.P.: Assessing the potential of interior point barrier filter line search methods: nonmonotone versus monotone approach. Optimization 60(10-11), 1251-1268 (2011) · Zbl 1231.90342
[17] Curtis, F.E., Nocedal, J., Wächter, A.: A matrix-free algorithm for equality constrained optimization problems with rank-deficient Jacobians. SIAM J. Optim. 20(3), 1224-1249 (2009) · Zbl 1195.49035
[18] Curtis, F.E., Schenk, O., Wächter, A.: An interior-point algorithm for large-scale nonlinear optimization with inexact step computations. SIAM J. Sci. Comput. 32(6), 3447-3475 (2010) · Zbl 1220.49018
[19] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201-213 (2002) · Zbl 1049.90004
[20] Duff, I.S.: Ma57—a code for the solution of sparse symmetric definite and indefinite systems. ACM Trans. Math. Softw. 30, 118-144 (2004) · Zbl 1070.65525
[21] Duff, I.S., Reid, J.K.: MA27—A Set of Fortran Subroutines for Solving Sparse Symmetric Sets of Linear Equations. UKAEA Atomic Energy Research Establishment (1982) · Zbl 1134.90053
[22] Gondzio, J., Sarkissian, R.: Parallel interior-point solver for structured linear programs. Math. Program. 96(3), 561-584 (2003) · Zbl 1023.90039
[23] Gould, N.I.M., Hribar, M.E., Nocedal, J.: On the solution of equality constrained quadratic programming problems arising in optimization. SIAM J. Sci. Comput. 23(4), 1376-1395 (2001) · Zbl 0999.65050
[24] Gould, N.I.M., Lucidi, S., Roma, M., Toint, P.L.: Solving the trust-region subproblem using the Lanczos method. SIAM J. Optim. 9(2), 504-525 (1999) · Zbl 1047.90510
[25] Gould, N.I.M.: On practical conditions for the existence and uniqueness of solutions to the general equality quadratic programming problem. Math. Program. 32(1), 90-99 (1985) · Zbl 0591.90068
[26] Haverbeke, N., Diehl, M., De Moor, B.: A structure exploiting interior-point method for moving horizon estimation. In: Proceedings of the 48th IEEE Conference on Decision and Control, pp. 1273-1278. IEEE (2009)
[27] Haynsworth, E.V.: Determination of the inertia of a partitioned Hermitian matrix. Linear Algebra Appl. 1(1), 73-81 (1968) · Zbl 0155.06304
[28] Heinkenschloss, M., Ridzal, D.: A matrix-free trust-region SQP method for equality constrained optimization. SIAM J. Optim. 24(3), 1507-1541 (2014) · Zbl 1316.90064
[29] Heroux, M.A., Willenbring, J.M.: Trilinos Users Guide. Citeseer (2003)
[30] Kawajiri, Y., Biegler, L.T.: Optimization strategies for simulated moving bed and powerfeed processes. AIChE J. 52(4), 1343-1350 (2006)
[31] Lubin, M., Petra, C.G., Anitescu, M.: The parallel solution of dense saddle-point linear systems arising in stochastic programming. Optim. Methods Softw. 27(4-5), 845-864 (2012) · Zbl 1254.90140
[32] Lubin, M., Petra, C.G., Anitescu, M., Zavala, V.M.: Scalable stochastic optimization of complex energy systems. In: International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 2011, pp. 1-10. IEEE (2011)
[33] Petra, C.G., Schenk, O., Lubin, M., Gaertner, K.: An augmented incomplete factorization approach for computing the Schur complement in stochastic optimization. SIAM J. Sci. Comput. 36(2), C139-C162 (2014) · Zbl 1296.65091
[34] Rao, C.V., Wright, S.J., Rawlings, J.B.: Application of interior-point methods to model predictive control. J. Optim. Theory Appl. 99(3), 723-757 (1998) · Zbl 0973.90092
[35] Schenk, O., Wächter, A., Hagemann, M.: Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization. Comput. Optim. Appl. 36, 321-341 (2007) · Zbl 1146.90055
[36] Schenk, O., Wächter, A., Weiser, M.: Inertia-revealing preconditioning for large-scale nonconvex constrained optimization. SIAM J. Sci. Comput. 31(2), 939-960 (2008) · Zbl 1194.35029
[37] Soler, M., Olivares, A., Staffetti, E.: Hybrid optimal control approach to commercial aircraft trajectory planning. J. Guid. Control Dyn. 33(3), 985-991 (2010)
[38] Wächter, A., Biegler, L.T.: On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Math. Program. 106, 25-57 (2006) · Zbl 1134.90542
[39] Wächter, A., Biegler, L.T.: Line search filter methods for nonlinear programming: motivation and global convergence. SIAM J. Optim. 16(1), 1-31 (2005) · Zbl 1114.90128
[40] Waltz, R.A., Morales, J.L., 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
[41] Wang, Y., Boyd, S.: Fast model predictive control using online optimization. IEEE Trans. Control Syst. Technol. 18(2), 267-278 (2010)
[42] Zavala, V.M.: Stochastic optimal control model for natural gas networks. Comput. Chem. Eng. 64, 103-113 (2014)
[43] Zavala, V.M., Biegler, L.T.: Large-scale parameter estimation in low-density polyethylene tubular reactors. Ind. Eng. Chem. Res. 45(23), 7867-7881 (2006)
[44] Zavala, V.M., Laird, C.D., Biegler, L.T.: Interior-point decomposition approaches for parallel solution of large-scale nonlinear parameter estimation problems. Chem. Eng. Sci. 63(19), 4834-4845 (2008)
[45] Zenios, S., Lasken, R.: Nonlinear network optimization on a massively parallel connection machine. Ann. Oper. Res. 14(1), 147-165 (1988)
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.