×

Efficient parallel solution of large-scale nonlinear dynamic optimization problems. (English) Zbl 1303.90122

Summary: This paper presents a decomposition strategy applicable to DAE constrained optimization problems. A common solution method for such problems is to apply a direct transcription method and solve the resulting nonlinear program using an interior-point algorithm. For this approach, the time to solve the linearized KKT system at each iteration typically dominates the total solution time. In our proposed method, we exploit the structure of the KKT system resulting from a direct collocation scheme for approximating the DAE constraints in order to compute the necessary linear algebra operations on multiple processors. This approach is applied to find the optimal control profile of a combined cycle power plant with promising results on both distributed memory and shared memory computing architectures with speedups of over 50 times possible.

MSC:

90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Åkesson, J., Årzén, K.E., Gäfvert, M., Bergdahl, T., Tummescheit, H.: Modeling and optimization with Optimica and JModelica.org-languages and tools for solving large-scale dynamic optimization problem. Comput. Chem. Eng. 34(11), 1737-1749 (2010). doi:10.1016/j.compchemeng.2009.11.011 · doi:10.1016/j.compchemeng.2009.11.011
[2] Amestoy, P., Duff, I., L’Excellent, J.: Multifrontal parallel distributed symmetric and unsymmetric solvers. Comput. Methods Appl. Mech. Eng. 184(2), 501-520 (2000) · Zbl 0956.65017 · doi:10.1016/S0045-7825(99)00242-X
[3] Andersson, J., Åkesson, J., Casella, F., Diehl, M.: (2011, March). Integration of CasADi and JModelica.org. In 8th International Modelica Conference 2011, Dresden, Germany · Zbl 1134.90542
[4] Andersson, J., Åkesson, J., Diehl, M.: (2012) CasADi: A symbolic package for automatic differentiation and optimal control. In Recent Advances in Algorithmic, Differentiation. Springer 297-307 · Zbl 1251.65020
[5] Benson, D.A., Huntington, G.T., Thorvaldsen, T.P., Rao, A.V.: Direct trajectory optimization and costate estimation via an orthogonal collocation method. J. Guid. Control. Dyn. 29(6), 1435-1440 (2006) · doi:10.2514/1.20478
[6] Biegler, L., Cervantes, A., Wächter, A.: Advances in simultaneous strategies for dynamic process optimization. Chem. Eng. Sci. 57(4), 575-593 (2002) · doi:10.1016/S0009-2509(01)00376-1
[7] Biegler, L., Grossmann, I.: Retrospective on optimization. Comput. Chem. Eng. 28(8), 1169-1192 (2004) · doi:10.1016/j.compchemeng.2003.11.003
[8] Biegler, L. T.: (2010). Nonlinear programming: concepts, algorithms, and applications to chemical processes, Vol. 10. SIAM · Zbl 1207.90004
[9] Brenan, K. E., Campbell, S. L.-V., Petzold, L. R.: (1989). Numerical solution of initial-value problems in differential-algebraic equations, Vol. 14. SIAM · Zbl 0699.65057
[10] Casella, F., Donida, F., Åkesson, J.: (2011, August) Object-oriented modeling and optimal control: A case study in power plant start-up. In 18th IFAC World Congress, Milano, Italy · Zbl 1190.90207
[11] Cervantes, A., Biegler, L.: A stable elemental decomposition for dynamic process optimization. J. Comput. Appl. Math. 120(1), 41-57 (2000) · Zbl 0970.65071 · doi:10.1016/S0377-0427(00)00302-2
[12] Cervantes, A., Wächter, A., Tütüncü, R., Biegler, L.: A reduced space interior point strategy for optimization of differential algebraic systems. Comput. Chem. Eng. 24(1), 39-51 (2000) · doi:10.1016/S0098-1354(00)00302-1
[13] Darby, C.L., Hager, W.W., Rao, A.V.: Direct trajectory optimization using a variable low-order adaptive pseudospectral method. J. Spacecr. Rockets 48, 433-445 (2011) · doi:10.2514/1.52136
[14] DeMiguel, V., Nogales, F.: On decomposition methods for a class of partially separable nonlinear programs. Math. Oper. Res. 33(1), 119-139 (2008) · Zbl 1190.90207 · doi:10.1287/moor.1070.0282
[15] Diehl, M., Bock, H., Schlöder, J., Findeisen, R., Nagy, Z., Allgöwer, F.: Real-time optimization and nonlinear model predictive control of processes governed by differential-algebraic equations. J. Process Control 12(4), 577-585 (2002) · doi:10.1016/S0959-1524(01)00023-3
[16] Fornberg, B.: A practical guide to pseudospectral methods, vol. 1. Cambridge University Press, Cambridge (1998) · Zbl 0912.65091
[17] Forsgren, A., Gill, P.E., Wright, M.H.: Interior methods for nonlinear optimization. SIAM review 44(4), 525-597 (2002) · Zbl 1028.90060 · doi:10.1137/S0036144502414942
[18] Garg, D., Patterson, M., Hager, W.W., Rao, A.V., Benson, D.A., Huntington, G.T.: A unified framework for the numerical solution of optimal control problems using pseudospectral methods. Automatica 46(11), 1843-1851 (2010) · Zbl 1219.49028 · doi:10.1016/j.automatica.2010.06.048
[19] Garg, D., Patterson, M.A., Francolin, C., Darby, C.L., Huntington, G.T., Hager, W.W., Rao, A.V.: Direct trajectory optimization and costate estimation of finite-horizon and infinite-horizon optimal control problems using a Radau pseudospectral method. Comput. Optim. Appl. 49(2), 335-358 (2011) · Zbl 1226.49026 · doi:10.1007/s10589-009-9291-0
[20] Goulart, P., Kerrigan, E., Ralph, D.: Efficient robust optimization for robust control with constraints. Math. Progr. 114(1), 115-147 (2008) · Zbl 1143.49025 · doi:10.1007/s10107-007-0096-6
[21] Hart, W., Laird, C., Watson, J., Woodruff, D.: Pyomo-optimization modeling in Python, vol. 67. Springer, New York (2012) · Zbl 1233.90002 · doi:10.1007/978-1-4614-3226-5
[22] Hartwich, A., Marquardt, W.: Dynamic optimization of the load change of a large-scale chemical plant by adaptive single shooting. Comput. Chem. Eng. 34(11), 1873-1889 (2010) · doi:10.1016/j.compchemeng.2010.02.036
[23] Hartwich, A., Stockmann, K., Terboven, C., Feuerriegel, S., Marquardt, W.: Parallel sensitivity analysis for efficient large-scale dynamic optimization. Optim. Eng. 12(4), 489-508 (2011) · Zbl 1284.65076 · doi:10.1007/s11081-010-9104-4
[24] Houska, B., Ferreau, H.J., Diehl, M.: ACADO toolkit-An open-source framework for automatic control and dynamic optimization. Optim. Control Appl. Methods 32(3), 298-312 (2011) · Zbl 1218.49002 · doi:10.1002/oca.939
[25] HSL (2011) A collection of Fortran codes for large scale scientific computation. HSL. http://www.hsl.rl.ac.uk · Zbl 1219.49029
[26] JModelica.org (2012a). CombinedCycle.mo. https://svn.jmodelica.org/trunk/Python/src/pyjmi/examples/files. [Revision 4090] · Zbl 0970.65071
[27] JModelica.org (2012b). CombinedCycleStartup.mop. https://svn.jmodelica.org/trunk/Python/src/pyjmi/examples/files. [Revision 4090] · Zbl 1219.49028
[28] Kameswaran, S., Biegler, L.T.: Convergence rates for direct transcription of optimal control problems using collocation at Radau points. Comput. Optim. Appl. 41(1), 81-126 (2008) · Zbl 1219.49029 · doi:10.1007/s10589-007-9098-9
[29] Kocak, S., Akay, H.: Parallel Schur complement method for large-scale systems on distributed memory computers. Appl. Math. Model. 25(10), 873-886 (2001) · Zbl 0995.65132 · doi:10.1016/S0307-904X(01)00019-1
[30] Laird, C.; Biegler, L.; Bock, HG (ed.); Kostina, E. (ed.); Phu, HX (ed.); Ranacher, R. (ed.), Large-scale Nonlinear Programming for Multi-scenario Optimization, 323-326 (2008), New York · doi:10.1007/978-3-540-79409-7_22
[31] Laird, C., Biegler, L., van Bloemen Waanders, B., Bartlett, R.: Contamination source determination for water networks. J. Water Res. Plan. Manag. 131(2), 125-134 (2005) · doi:10.1061/(ASCE)0733-9496(2005)131:2(125)
[32] Laird, C., Wong, A., Akesson, J.: (2011) Parallel solution of large-scale dynamic optimization problems. In 21st European Symposium on Computer Aided Process Engineering-ESCAPE, Vol. 21
[33] Lang, Y.-D., Biegler, L.: A software environment for simultaneous dynamic optimization. Comput. Chem. Eng. 31(8), 931-942 (2007) · Zbl 1231.74256 · doi:10.1016/j.compchemeng.2006.10.017
[34] Leineweber, D., Bauer, I., Bock, H., Schlöder, J.: An efficient multiple shooting based reduced SQP strategy for large-scale dynamic process optimization. part 1: theoretical aspects. Comput. Chem. Eng. 27(2), 157-166 (2003) · doi:10.1016/S0098-1354(02)00158-8
[35] Mattsson, S., Söderlind, G.: Index reduction in differential-algebraic equations using dummy derivatives. SIAM J. Sci. Comput. 14(3), 677-692 (1993) · Zbl 0785.65080 · doi:10.1137/0914043
[36] Modelica Association (2007) The Modelica language specification version 3.0
[37] 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 · doi:10.1023/A:1021711402723
[38] Schenk, O., Gärtner, K.: Solving unsymmetric sparse systems of linear equations with PARDISO. Future Gener. Comput Syst 20(3), 475-487 (2004) · Zbl 1062.65035 · doi:10.1016/j.future.2003.07.011
[39] Scheu, H., Marquardt, W.: Sensitivity-based coordination in distributed model predictive control. J. Process Control 21(5), 715-728 (2011) · doi:10.1016/j.jprocont.2011.01.013
[40] Scott, J.: Parallel frontal solvers for large sparse linear systems. ACM Trans. Math. Softw. (TOMS) 29(4), 395-417 (2003) · Zbl 1072.65041 · doi:10.1145/962437.962440
[41] Tanaka, R., Martins, C.: Parallel dynamic optimization of steel risers. J. Offshore Mech. Arct. Eng. 133(1), 011302-011309 (2011) · doi:10.1115/1.4001955
[42] Wächter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Progr. 106(1), 25-58 (2006) · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y
[43] Word, D., Cummings, D., Burke, D., Iamsirithaworn, S., Laird, C.: A nonlinear programming approach for estimation of transmission parameters in childhood infectious disease using a continuous time model. J. R. Soc. Interface 9(73), 1983-1997 (2012) · doi:10.1098/rsif.2011.0829
[44] Zavala, V., Biegler, L.: Large-scale parameter estimation in low-density polyethylene tubular reactors. Ind. Eng. Chem. Res. 45(23), 7867-7881 (2006) · doi:10.1021/ie060338n
[45] Zavala, V., Laird, C., 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) · doi:10.1016/j.ces.2007.05.022
[46] Zhu, Y. Laird, C.: (2008) A parallel algorithm for structured nonlinear programming. In Proceeding of 5th International Conference on Foundations of Computer-Aided Process Operation, FOCAPO, pp. 345-348
[47] Zhu, Y., Legg, S., Laird, C.: (2009) Optimal design of cryogenic air separation columns under uncertainty. Computers & Chemical Engineering 34. Selected papers from the 7th International Conference on the Foundations of Computer-Aided Process Design (FOCAPD)
[48] Zhu, Y., Legg, S., Laird, C.: Optimal operation of cryogenic air separation systems with demand uncertainty and contractual obligations. Chem. Eng. Sci. 66(5), 953-963 (2011) · doi:10.1016/j.ces.2010.11.039
[49] Zhu, Y., Word, D., Siirola, J., Laird, C.: Exploiting modern computing architectures for efficient large-scale nonlinear programming. Comput. Aided Chem. Eng. 27, 783-788 (2009) · doi:10.1016/S1570-7946(09)70351-7
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.