×

zbMATH — the first resource for mathematics

Structure-exploiting interior point methods. (English) Zbl 1455.65095
Grama, Ananth (ed.) et al., Parallel algorithms in computational science and engineering. Cham: Birkhäuser. Model. Simul. Sci. Eng. Technol., 63-93 (2020).
Summary: Interior point methods are among the most popular techniques for large-scale nonlinear optimization, owing to their intrinsic ability of scaling to arbitrarily large problem sizes. Their efficiency has attracted, in recent years, a lot of attention due to increasing demand for large-scale optimization in industry and engineering. General purpose nonlinear programming solvers implementing interior point methods provide a generic framework that embraces almost every optimal control problem provided that the nonlinear functions are smooth and that their first and possibly the second derivatives are also available. However, a large class of industrial and engineering problems possesses a particular structure motivating the development of structure-exploiting interior point methods. We present an interior point framework that exploits the intrinsic structure of large-scale nonlinear optimization problems, with the purpose of accelerating the solution both for single-core or multicore execution and massively parallel high-performance computing infrastructures. Since the overall performance of interior point methods relies heavily on scalable sparse linear algebra solvers, particular emphasis is given to the underlying algorithms for the distributed solution of the associated sparse linear systems obtained at each iteration from the linearization of the optimality conditions. The interior point algorithm is implemented in an object-oriented parallel solver and applied for the solution of large-scale optimal control problems solved on a daily basis for the secure transmission and distribution of electricity in modern power grids.
For the entire collection see [Zbl 1446.65003].
MSC:
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C51 Interior-point methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] R. H. Byrd, G. Liu, and J. Nocedal. On the local behavior of an interior point method for nonlinear programming. In Numerical Analysis 1997, pages 37-56. Addison Wesley Longman, 1998. · Zbl 0902.65021
[2] R. H. Byrd, J. Nocedal, and R. A. Waltz. Knitro: An Integrated Package for Nonlinear Optimization, pages 35-59. Springer US, Boston, MA, 2006. · Zbl 1108.90004
[3] N. Chiang, C. G. Petra, and V. M. Zavala. Structured nonconvex optimization of large-scale energy systems using PIPS-NLP. In 2014 Power Systems Computation Conference, pages 1-7, Aug 2014.
[4] N.-Y. Chiang and V. M. Zavala. An inertia-free filter line-search algorithm for large-scale nonlinear programming. Computational Optimization and Applications, 64(2):327-354, Jun 2016. · Zbl 1350.90031
[5] A. R. Conn, N. I. M. Gould, D. Orban, and P. L. Toint. A primal-dual trust-region algorithm for non-convex nonlinear programming. Mathematical Programming, 87(2):215-249, Apr 2000. · Zbl 0970.90116
[6] T. Demiray and G. Andersson. Optimization of numerical integration methods for the simulation of dynamic phasor models in power systems. International Journal of Electrical Power & Energy Systems, 31(9):512-521, 2009. Power Systems Computation Conference (PSCC) 2008.
[7] I. S. Duff and J. A. Scott. Stabilized bordered block diagonal forms for parallel sparse solvers. Parallel Comput., 31(3-4):275-289, Mar. 2005.
[8] R. Fletcher and S. Leyffer. Nonlinear programming without a penalty function. Mathematical Programming, 91(2):239-269, Jan 2002. · Zbl 1049.90088
[9] N. I. M. Gould, D. Orban, A. Sartenaer, and P. L. Toint. Superlinear convergence of primal-dual interior point algorithms for nonlinear programming. SIAM Journal on Optimization, 11(4):974-1002, 2001. · Zbl 1003.65066
[10] N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4(4):373-395, Dec 1984. · Zbl 0557.90065
[11] D. Kourounis, A. Fuchs, and O. Schenk. Toward the next generation of multiperiod optimal power flow solvers. IEEE Transactions on Power Systems, 33(4):4005-4014, July 2018.
[12] S. Mehrotra. On the implementation of a primal-dual interior point method. SIAM Journal on Optimization, 2(4):575-601, 1992. · Zbl 0773.90047
[13] A. Monticelli, M. V. F. Pereira, and S. Granville. Security-constrained optimal power flow with post-contingency corrective rescheduling. IEEE Transactions on Power Systems, 2(1):175-180, Feb 1987.
[14] J. Nocedal, A. Wächter„ and R. A. Waltz. Adaptive barrier update strategies for nonlinear interior methods. SIAM Journal on Optimization, 19(4):1674-1693, 2009. · Zbl 1176.49036
[15] J. Nocedal and S. J. Wright. Numerical Optimization. Springer, New York, NY, USA, second edition, 2006. · Zbl 1104.65059
[16] C. G. Petra, O. Schenk, and M. Anitescu. Real-time stochastic optimization of complex energy systems on high-performance computers. Computing in Science Engineering, 16(5):32-42, Sept 2014.
[17] C. G. Petra, O. Schenk, M. Lubin, and K. Gärtner. An augmented incomplete factorization approach for computing the Schur complement in stochastic optimization. SIAM Journal on Scientific Computing, 36(2):C139-C162, 2014. · Zbl 1296.65091
[18] D. T. Phan and X. A. Sun. Minimal impact corrective actions in security-constrained optimal power flow via sparsity regularization. IEEE Transactions on Power Systems, 30(4):1947-1956, July 2015.
[19] M. Schanen, F. Gilbert, C. G. Petra, and M. Anitescu. Toward multiperiod ac-based contingency constrained optimal power flow at large scale. In 2018 Power Systems Computation Conference (PSCC), pages 1-7, June 2018.
[20] O. Schenk, K. Gärtner, W. Fichtner, and A. Stricker. PARDISO: a high-performance serial and parallel sparse linear solver in semiconductor device simulation. Future Generation Computer Systems, 18(1):69-78, 2001. I. High Performance Numerical Methods and Applications. II. Performance Data Mining: Automated Diagnosis, Adaption, and Optimization. · Zbl 1032.68172
[21] A. Wächter. An interior point algorithm for large-scale nonlinear optimization with applications in process engineering. PhD thesis, Carnegie Mellon University, http://researcher.watson.ibm.com/researcher/files/us-andreasw/thesis.pdf, 2003.
[22] A. Wächter and L. T. Biegler. Line search filter methods for nonlinear programming: motivation and global convergence. SIAM J. Optim., 16(1):1-31 (electronic), 2005. · Zbl 1114.90128
[23] A. Wächter and L. T. Biegler. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program., 106(1, Ser. A):25-57, 2006. · Zbl 1134.90542
[24] H. Wang, C. E. Murillo-Sanchez, R. D. Zimmerman, and R. J. Thomas. On computational issues of market-based optimal power flow. IEEE Trans. on Power Syst., 22(3):1185-1193, Aug 2007.
[25] S. Wright. Primal-Dual Interior-Point Methods. Society for Industrial and Applied Mathematics, 1997. · Zbl 0863.65031
[26] R. Zimmerman and C. Murillo-Sanchez. Matpower 6.0 User’s manual. Power Systems Engineering Research Center, 2016.
[27] R.
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.