A Fast Temporal Decomposition Procedure for Long-Horizon Nonlinear Dynamic Programming

References

• [1] Barrows C, Hummon M, Jones W, Hale E (2014) Time domain partitioning of electricity production cost simulations. Technical report, National Renewable Energy Laboratory, Golden, CO).Google Scholar
• [2] Beccuti A, Geyer T, Morari M (2004) Temporal lagrangian decomposition of model predictive control for hybrid systems. 43rd IEEE Conf. Decision Control, vol. 3 (IEEE, Piscataway, NJ), 2509–2514.Google Scholar
• [3] Bertsekas D (1996) Constrained Optimization and Lagrange Multiplier Methods (Athena Scientific, Belmont, MA).Google Scholar
• [4] Bock H, Plitt K (1984) A multiple shooting algorithm for direct solution of optimal control problems. IFAC Proc. Volumes 17(2):1603–1608.Crossref, Google Scholar
• [5] Bock HG, Diehl MM, Leineweber DB, Schlöder JP (2000) A direct multiple shooting method for real-time optimization of nonlinear DAE processes. Nonlinear Model Predictive Control (Birkhäuser, Basel, Switzerland), 245–267.Crossref, Google Scholar
• [6] Boggs PT, Tolle JW (1995) Sequential quadratic programming. Acta Numerica 4:1–51.Crossref, Google Scholar
• [7] Boyd S (2010) Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, vol. 3 (Now Publishers, Delft, Netherlands).Crossref, Google Scholar
• [8] Buikis A (1999) A mathematical model for the heat treatment of glass fabric sheets. IMA J. Management Math. 10(1):55–86.Crossref, Google Scholar
• [9] Buikis A, Kalis H (1999) The mathematical modelling of the nonlinear heat transport in thin plate. Math. Model. Anal. 4(1):44–50.Crossref, Google Scholar
• [10] Byrd RH, Nocedal J, Waltz RA (2006) Knitro: An integrated package for nonlinear optimization. Nonconvex Optimization and Its Applications (Springer, Boston), 35–59.Google Scholar
• [11] Byrd RH, Schnabel RB, Shultz GA (1988) Parallel quasi-newton methods for unconstrained optimization. Math. Programming 42(1–3):273–306.Crossref, Google Scholar
• [12] Cao T, Hall J, van de Geijn R (2002) Parallel Cholesky factorization of a block tridiagonal matrix. Proc. Internat. Conf. Parallel Processing Workshop (IEEE, Piscataway, NJ), 327–335.Google Scholar
• [13] Chiang N, Petra CG, Zavala VM (2014) Structured nonconvex optimization of large-scale energy systems using PIPS-NLP. Power Systems Comput. Conf. (IEEE, Piscataway, NJ), 1–7.Google Scholar
• [14] Curtis FE, Jiang H, Robinson DP (2014) An adaptive augmented Lagrangian method for large-scale constrained optimization. Math. Programming 152(1–2):201–245.Crossref, Google Scholar
• [15] Dias BH, Tomim MA, Marcato ALM, Ramos TP, Brandi RBS, da Silva IC Jr, Filho JAP (2013) Parallel computing applied to the stochastic dynamic programming for long term operation planning of hydrothermal power systems. Eur. J. Oper. Res. 229(1):212–222.Crossref, Google Scholar
• [16] Diehl M, Ferreau HJ, Haverbeke N (2009) Efficient numerical methods for nonlinear MPC and moving horizon estimation. Nonlinear Model Predictive Control (Springer, Berlin, Heidelberg), 391–417.Crossref, Google Scholar
• [17] Diehl M, Findeisen R, Bock H, Allgöwer F, Schlöder J (2005) Nominal stability of real-time iteration scheme for nonlinear model predictive control. IEE Proc. Control Theory Appl. 152(3):296–308.Crossref, Google Scholar
• [18] Diehl M, Bock H, Schlöder JP, Findeisen R, Nagy Z, Allgöwer F (2002) Real-time optimization and nonlinear model predictive control of processes governed by differential-algebraic equations. J. Process Control 12(4):577–585.Crossref, Google Scholar
• [19] Domahidi A, Zgraggen AU, Zeilinger MN, Morari M, Jones CN (2012) Efficient interior point methods for multistage problems arising in receding horizon control. IEEE 51st IEEE Conf. Decision Control (IEEE, Piscataway, NJ), 668–674.Google Scholar
• [20] Dunn JC, Bertsekas DP (1989) Efficient dynamic programming implementations of Newton’s method for unconstrained optimal control problems. J. Optim. Theory Appl. 63(1):23–38.Crossref, Google Scholar
• [21] Dunning I, Huchette J, Lubin M (2017) JuMP: A modeling language for mathematical optimization. SIAM Rev. 59(2):295–320.Crossref, Google Scholar
• [22] Fletcher R (1973) An exact penalty function for nonlinear programming with inequalities. Math. Programming 5(1):129–150.Crossref, Google Scholar
• [23] Frasch JV, Sager S, Diehl M (2015) A parallel quadratic programming method for dynamic optimization problems. Math. Programming Comput. 7(3):289–329.Crossref, Google Scholar
• [24] Frasch JV, Gray A, Zanon M, Ferreau HJ, Sager S, Borrelli F, Diehl M (2013) An auto-generated nonlinear MPC algorithm for real-time obstacle avoidance of ground vehicles. Eur. Control Conf. (IEEE, Piscataway, NJ), 4136–4141.Google Scholar
• [25] Frison G, Sorensen HHB, Dammann B, Jorgensen JB (2014) High-performance small-scale solvers for linear model predictive control. Eur. Control Conf. (IEEE, Piscataway, NJ), 128–133.Google Scholar
• [26] Glad T, Polak E (1979) A multiplier method with automatic limitation of penalty growth. Math. Programming 17(1):140–155.Crossref, Google Scholar
• [27] Hong M, Luo ZQ, Razaviyayn M (2016) Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM J. Optim. 26(1):337–364.Crossref, Google Scholar
• [28] Keerthi SS, Gilbert EG (1988) Optimal infinite-horizon feedback laws for a general class of constrained discrete-time systems: Stability and moving-horizon approximations. J. Optim. Theory Appl. 57(2):265–293.Crossref, Google Scholar
• [29] Kirches C, Wirsching L, Bock H, Schlöder J (2012) Efficient direct multiple shooting for nonlinear model predictive control on long horizons. J. Process Control 22(3):540–550.Crossref, Google Scholar
• [30] Laine F, Tomlin C (2019) Parallelizing LQR computation through endpoint-explicit Riccati recursion. IEEE 58th Conf. Decision Control (IEEE, Piscataway, NJ), 1395–1402.Google Scholar
• [31] Lemaréchal C (2001) Lagrangian relaxation. Lecture Notes in Computer Science (Springer, Berlin, Heidelberg), 112–156.Google Scholar
• [32] Li W, Todorov E (2007) Iterative linearization methods for approximately optimal control and estimation of non-linear stochastic system. Internat. J. Control 80(9):1439–1453.Crossref, Google Scholar
• [33] MathWorks (2022) Nonlinear heat transfer in thin plate. https://www.mathworks.com/help/pde/ug/nonlinear-heat-transfer-in-a-thin-plate.html.Google Scholar
• [34] Na S, Anitescu M (2020) Exponential decay in the sensitivity analysis of nonlinear dynamic programming. SIAM J. Optim. 30(2):1527–1554.Crossref, Google Scholar
• [35] Na S, Anitescu M (2023) Superconvergence of online optimization for model predictive control. IEEE Trans. Automatic Control 68(3):1383–1398.Crossref, Google Scholar
• [36] Na S, Anitescu M, Kolar M (2023) An adaptive stochastic sequential quadratic programming with differentiable exact augmented Lagrangians. Math. Programming 199:721–791.Google Scholar
• [37] Na S, Anitescu M, Kolar M (2023) Inequality constrained stochastic nonlinear optimization via active-set sequential quadratic programming. Math. Programming, ePub ahead of print March 2, https://doi.org/10.1007/s10107-023-01935-7.Crossref, Google Scholar
• [38] Na S, Shin S, Anitescu M, Zavala VM (2022) On the convergence of overlapping Schwarz decomposition for nonlinear optimal control. IEEE Trans. Automatic Control 67(11):5996–6011.Crossref, Google Scholar
• [39] Nielsen I, Axehill D (2015) A parallel structure exploiting factorization algorithm with applications to model predictive control. 54th IEEE Conf. Decision Control (IEEE, Piscataway, NJ), 3932–3938.Google Scholar
• [40] Nielsen I, Axehill D (2016) An o (log n) parallel algorithm for Newton step computations with applications to moving horizon estimation. Eur. Control Conf. (IEEE, Piscataway, NJ), 1630–1636.Google Scholar
• [41] Nocedal J, Wright SJ (2006) Numerical Optimization, Springer Series in Operations Research and Financial Engineering, 2nd ed. (Springer, New York).Google Scholar
• [42] O’Donoghue B, Stathopoulos G, Boyd S (2013) A splitting method for optimal control. IEEE Trans. Control Systems Tech. 21(6):2432–2442.Crossref, Google Scholar
• [43] Petra CG, Schenk O, Lubin M, Gäertner K (2014) An augmented incomplete factorization approach for computing the Schur complement in stochastic optimization. SIAM J. Sci. Comput. 36(2):C139–C162.Crossref, Google Scholar
• [44] Pillo G (1994) Exact penalty methods. Algorithms for Continuous Optimization (Springer, Netherlands), 209–253.Crossref, Google Scholar
• [45] Pillo GD, Grippo L (1979) A new class of augmented Lagrangians in nonlinear programming. SIAM J. Control Optim. 17(5):618–628.Crossref, Google Scholar
• [46] Pillo GD, Lucidi S (2002) An augmented Lagrangian function with improved exactness properties. SIAM J. Optim. 12(2):376–406.Crossref, Google Scholar
• [47] Pillo GD, Grippo L, Lampariello F (1980) A method for solving equality constrained optimization problems by unconstrained minimization. Optimization Techniques (Springer-Verlag), 96–105.Crossref, Google Scholar
• [48] Roulet V, Srinivasa S, Fazel M, Harchaoui Z (2022) Iterative linear quadratic optimization for nonlinear control: Differentiable programming algorithmic templates. Preprint, submitted July 13, https://arxiv.org/abs/2207.06362.Google Scholar
• [49] Schäfer A, Kühl P, Diehl M, Schlöder J, Bock HG (2007) Fast reduced multiple shooting methods for nonlinear model predictive control. Chemical Engrg. Processing Process Intensification 46(11):1200–1214.Crossref, Google Scholar
• [50] Schittkowski K (1982) The nonlinear programming method of Wilson, Han, and Powell with an augmented Lagrangian type line search function. Numerische Mathematik 38(1):83–114.Crossref, Google Scholar
• [51] Shin S, Zavala VM (2021) Diffusing-horizon model predictive control. IEEE Trans. Automatic Control 68(1):188–201.Crossref, Google Scholar
• [52] Shin S, Anitescu M, Zavala VM (2022) Exponential decay of sensitivity in graph-structured nonlinear programs. SIAM J. Optim. 32(2):1156–1183.Crossref, Google Scholar
• [53] Shin S, Zavala VM, Anitescu M (2020) Decentralized schemes with overlap for solving graph-structured optimization problems. IEEE Trans. Control Network Systems 7(3):1225–1236.Crossref, Google Scholar
• [54] Shin S, Faulwasser T, Zanon M, Zavala VM (2019) A parallel decomposition scheme for solving long-horizon optimal control problems. IEEE 58th Conf. Decision Control (IEEE, Piscataway, NJ), 5264–5271.Google Scholar
• [55] Tassa Y, Erez T, Todorov E (2012) Synthesis and stabilization of complex behaviors through online trajectory optimization. IEEE/RSJ Internat. Conf. Intelligent Robots Systems (IEEE, Piscataway, NJ), 4906–4913.Google Scholar
• [56] Topaloglou N, Vladimirou H, Zenios SA (2008) A dynamic stochastic programming model for international portfolio management. Eur. J. Oper. Res. 185(3):1501–1524.Crossref, Google Scholar
• [57] Verschueren R, Zanon M, Quirynen R, Diehl M (2017) A sparsity preserving convexification procedure for indefinite quadratic programs arising in direct optimal control. SIAM J. Optim. 27(3):2085–2109.Crossref, Google Scholar
• [58] Wächter A, Biegler LT (2005) Line search filter methods for nonlinear programming: Local convergence. SIAM J. Optim. 16(1):32–48.Crossref, Google Scholar
• [59] Wächter A, Biegler LT (2005) Line search filter methods for nonlinear programming: Motivation and global convergence. SIAM J. Optim. 16(1):1–31.Crossref, Google Scholar
• [60] Wächter A, Biegler LT (2005) On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Programming 106(1):25–57.Crossref, Google Scholar
• [61] Wan W, Biegler LT (2016) Structured regularization for barrier NLP solvers. Comput. Optim. Appl. 66(3):401–424.Crossref, Google Scholar
• [62] Wang Y, Yin W, Zeng J (2018) Global convergence of ADMM in nonconvex nonsmooth optimization. J. Sci. Comput. 78(1):29–63.Crossref, Google Scholar
• [63] Wright SJ (1990) Solution of discrete-time optimal control problems on parallel computers. Parallel Comput. 16(2–3):221–237.Crossref, Google Scholar
• [64] Wright SJ (1991) Parallel algorithms for banded linear systems. SIAM J. Sci. Statist. Comput. 12(4):824–842.Crossref, Google Scholar
• [65] Xu W, Anitescu M (2018) Exponentially accurate temporal decomposition for long-horizon linear-quadratic dynamic optimization. SIAM J. Optim. 28(3):2541–2573.Crossref, Google Scholar
• [66] Xu W, Anitescu M (2019) Exponentially convergent receding horizon strategy for constrained optimal control. Vietnam J. Math. 47(4):897–929.Crossref, Google Scholar
• [67] Zanelli A, Dinh QT, Diehl M (2020) Stability analysis of real-time methods for equality constrained NMPC. IFAC-PapersOnLine 53(2):6570–6576.Crossref, Google Scholar
• [68] Zanon M, Frasch JV, Vukov M, Sager S, Diehl M (2014) Model predictive control of autonomous vehicles. Optimization and Optimal Control in Automotive Systems (Springer Cham, Switzerland), 41–57.Crossref, Google Scholar
• [69] Zavala VM, Anitescu M (2014) Scalable nonlinear programming via exact differentiable penalty functions and trust-region Newton methods. SIAM J. Optim. 24(1):528–558.Crossref, Google Scholar