American Institute of Mathematical Sciences

• Previous Article
Second order necessary and sufficient optimality conditions for singular solutions of partially-affine control problems
• DCDS-S Home
• This Issue
• Next Article
Structure of approximate solutions of Bolza variational problems on large intervals
December 2018, 11(6): 1259-1282. doi: 10.3934/dcdss.2018071

A study of structure-exploiting SQP algorithms for an optimal control problem with coupled hyperbolic and ordinary differential equation constraints

 1 Institut für Mathematik und Rechneranwendung (LRT-1), Universität der Bundeswehr München, Werner-Heisenberg-Weg 39, 85577 Neubiberg/München, Germany 2 Center for Computational Mathematics, University of California, San Diego, 9500 Gilman Drive, La Jolla, CA 92093-0112, USA

* Corresponding author: Sven-Joachim Kimmerle

Received  April 2017 Revised  September 2017 Published  June 2018

In this article, structure-exploiting optimisation algorithms of the sequential quadratic programming (SQP) type are considered for optimal control problems with control and state constraints. Our approach is demonstrated for a 1D mathematical model of a vehicle transporting a fluid container. The model involves a fully coupled system of ordinary differential equations (ODE) and nonlinear hyperbolic first-order partial differential equations (PDE), although the ideas for exploiting the particular structure may be applied to more general optimal control problems as well. The time-optimal control problem is solved numerically by a full discretisation approach. The corresponding nonlinear optimisation problem is solved by an SQP method that uses exact first and second derivative information. The quadratic subproblems are solved using an active-set strategy. In addition, two approaches are examined that exploit the specific structure of the problem: (A) a direct method for the KKT system, and (B) an iterative method based on combining the limited-memory BFGS method with the preconditioned conjugate gradient method. Method (A) is faster for our model problem, but can be limited by the problem size. Method (B) opens the door for a potential extension of the truck-container model to three space dimensions.

Citation: Jan-Hendrik Webert, Philip E. Gill, Sven-Joachim Kimmerle, Matthias Gerdts. A study of structure-exploiting SQP algorithms for an optimal control problem with coupled hyperbolic and ordinary differential equation constraints. Discrete & Continuous Dynamical Systems - S, 2018, 11 (6) : 1259-1282. doi: 10.3934/dcdss.2018071
References:
 [1] J. T. Betts, Practical Methods for Optimal Control Using Nonlinear Programming, 2nd edition, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2010. doi: 10.1137/1.9780898718577. [2] M. Breuß, The correct use of the Lax-Friedrichs method, ESAIM: Mathematical Modelling and Numerical Analysis, 38 (2004), 519-540. doi: 10.1051/m2an:2004027. [3] R. Byrd, J. Nocedal and R. Schnabel, Representations of quasi-Newton matrices and their use in limited memory methods, Mathematical Programming, 63 (1994), 129-156. doi: 10.1007/BF01582063. [4] I. S. Duff, MA57-A code for the solution of sparse symmetric definite and indefinite systems, ACM Trans. Math. Softw., 30 (2004), 118-144. doi: 10.1145/992200.992202. [5] A. Forsgren, Inertia-controlling factorizations for optimization algorithms, Applied Numerical Mathematics, 43 (2002), 91-107. doi: 10.1016/S0168-9274(02)00119-8. [6] M. Gerdts, SQP Filtertoolbox within Software Package OCPID-DAE1, Optimal Control and Parameter Identification with Differential-Algebraic Equations of Index 1. Users Guide (Online Documentation), Universität der Bundeswehr München, Neubiberg/München, 2010. (Available from: http://www.optimal-control.de/index.php/software.) [7] M. Gerdts and S.-J. Kimmerle, Numerical optimal control of a coupled ODE-PDE model of a truck with a fluid basin, Discrete Contin. Dynam. Systems - A, 2015 (2015), 515--524. doi: 10.3934/proc.2015.0515. [8] P. E. Gill and E. Wong, Methods for convex and general quadratic programming, Math. Prog. Comp., 7 (2015), 71-112. doi: 10.1007/s12532-014-0075-x. [9] P. E. Gill, E. Wong, W. Murray and M. A. Saunders, User's Guide for SNOPT Version 7.4: Software for Large-Scale Nonlinear Programming, 2015. [10] S.-J. Kimmerle and M. Gerdts, Necessary optimality conditions and a semi-smooth Newton approach for an optimal control problem of a coupled system of Saint-Venant equations and ordinary differential equations, Pure Appl. Funct. Anal., 1 (2016), 231-256. [11] D. Liu and J. Nocedal, On the limited memory BFGS method for large scale optimization, Mathematical Programming, 45 (1989), 503-528. doi: 10.1007/BF01589116. [12] D. Luenberger and Y. Ye, Linear and Nonlinear Programming, 3rd edition, Springer, US, 2008. doi: 10.1007/978-3-319-18842-3. [13] J. Nocedal and S. J. Wright, Numerical Optimization, 2nd edition, Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006. doi: 10.1007/b98874. [14] N. Petit and P. Rouchon, Dynamics and solutions to some control problems for water-tank systems, IEEE Transactions on Automatic Control, 47 (2002), 594-609. doi: 10.1109/9.995037. [15] J.-H. Webert, Structure-exploiting Optimization Algorithms for an Optimal Control Problem with Coupled Hyperbolic and Ordinary Differential Equation Constraints M. Sc. thesis, Universität der Bundeswehr München, Neubiberg/München, 2015.

show all references

References:
 [1] J. T. Betts, Practical Methods for Optimal Control Using Nonlinear Programming, 2nd edition, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2010. doi: 10.1137/1.9780898718577. [2] M. Breuß, The correct use of the Lax-Friedrichs method, ESAIM: Mathematical Modelling and Numerical Analysis, 38 (2004), 519-540. doi: 10.1051/m2an:2004027. [3] R. Byrd, J. Nocedal and R. Schnabel, Representations of quasi-Newton matrices and their use in limited memory methods, Mathematical Programming, 63 (1994), 129-156. doi: 10.1007/BF01582063. [4] I. S. Duff, MA57-A code for the solution of sparse symmetric definite and indefinite systems, ACM Trans. Math. Softw., 30 (2004), 118-144. doi: 10.1145/992200.992202. [5] A. Forsgren, Inertia-controlling factorizations for optimization algorithms, Applied Numerical Mathematics, 43 (2002), 91-107. doi: 10.1016/S0168-9274(02)00119-8. [6] M. Gerdts, SQP Filtertoolbox within Software Package OCPID-DAE1, Optimal Control and Parameter Identification with Differential-Algebraic Equations of Index 1. Users Guide (Online Documentation), Universität der Bundeswehr München, Neubiberg/München, 2010. (Available from: http://www.optimal-control.de/index.php/software.) [7] M. Gerdts and S.-J. Kimmerle, Numerical optimal control of a coupled ODE-PDE model of a truck with a fluid basin, Discrete Contin. Dynam. Systems - A, 2015 (2015), 515--524. doi: 10.3934/proc.2015.0515. [8] P. E. Gill and E. Wong, Methods for convex and general quadratic programming, Math. Prog. Comp., 7 (2015), 71-112. doi: 10.1007/s12532-014-0075-x. [9] P. E. Gill, E. Wong, W. Murray and M. A. Saunders, User's Guide for SNOPT Version 7.4: Software for Large-Scale Nonlinear Programming, 2015. [10] S.-J. Kimmerle and M. Gerdts, Necessary optimality conditions and a semi-smooth Newton approach for an optimal control problem of a coupled system of Saint-Venant equations and ordinary differential equations, Pure Appl. Funct. Anal., 1 (2016), 231-256. [11] D. Liu and J. Nocedal, On the limited memory BFGS method for large scale optimization, Mathematical Programming, 45 (1989), 503-528. doi: 10.1007/BF01589116. [12] D. Luenberger and Y. Ye, Linear and Nonlinear Programming, 3rd edition, Springer, US, 2008. doi: 10.1007/978-3-319-18842-3. [13] J. Nocedal and S. J. Wright, Numerical Optimization, 2nd edition, Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006. doi: 10.1007/b98874. [14] N. Petit and P. Rouchon, Dynamics and solutions to some control problems for water-tank systems, IEEE Transactions on Automatic Control, 47 (2002), 594-609. doi: 10.1109/9.995037. [15] J.-H. Webert, Structure-exploiting Optimization Algorithms for an Optimal Control Problem with Coupled Hyperbolic and Ordinary Differential Equation Constraints M. Sc. thesis, Universität der Bundeswehr München, Neubiberg/München, 2015.
Model of the truck and fluid tank, cf. [7].
Optimal solution: control force $u(t)$ (left) and fluid column height $h(t, x) + b(x)$ (right) for $N = 300$, $M = 10$ (final time minimised, $T = 10.8s$) and a straight fluid tank bottom.
Optimal solution: control force $u(t)$ (left) and fluid column height $h(t, x) + b(x)$ (right) for $N = 300$, $M = 10$ (final time and fluid-level deviation minimised, $T = 19.1s$) and a straight fluid tank bottom.
Optimal solution: control force $u(t)$ (left) and fluid column height $h(t, x) + b(x)$ (right) for $N = 150$, $M = 5$ (final time minimised, $T = 11.5s$). The bottom of the fluid tank is given by the linear function $b(x) = - x/8 + 1/2, \, 0 \leq x \leq L = 4$.
Solution output of Problem (1) with $M = 5$ and $N = 150$. $\texttt{CV}$ and $\texttt{KKT}$ denote the norm of the constraint violation and the norm of the gradient of the Lagrangian, respectively. $\texttt{QPIT}$ is the number of QP iterations and $\texttt{OBJ}$ the value of the objective function.
 $\texttt{ITER}$ $\texttt{QPIT}$ $\texttt{ALPHA}$ $\texttt{OBJ}$ $\texttt{CV}$ $\texttt{KKT}$ $\texttt{0}$ $\texttt{0}$ $\texttt{0.0000E+00}$ $\texttt{0.100000050000E+01}$ $\texttt{0.9893E+02}$ $\texttt{0.1000E+00}$ $\texttt{1}$ $\texttt{224}$ $\texttt{0.1000E+01}$ $\texttt{0.102710574197E+01}$ $\texttt{0.1811E+02}$ $\texttt{0.2648E-01}$ $\texttt{2}$ $\texttt{6}$ $\texttt{0.1000E+01}$ $\texttt{0.107819921922E+01}$ $\texttt{0.2086E+00}$ $\texttt{0.5244E-02}$ $\texttt{3}$ $\texttt{24}$ $\texttt{0.1000E+01}$ $\texttt{0.109015429623E+01}$ $\texttt{0.4723E-02}$ $\texttt{0.2969E-03}$ $\texttt{4}$ $\texttt{5}$ $\texttt{0.1000E+01}$ $\texttt{0.109049950972E+01}$ $\texttt{0.3198E-05}$ $\texttt{0.4477E-06}$ $\texttt{5}$ $\texttt{3}$ $\texttt{0.1000E+01}$ $\texttt{0.109049961114E+01}$ $\texttt{0.4253E-11}$ $\texttt{0.4570E-12}$ $\texttt{END OF SQP METHOD}$
 $\texttt{ITER}$ $\texttt{QPIT}$ $\texttt{ALPHA}$ $\texttt{OBJ}$ $\texttt{CV}$ $\texttt{KKT}$ $\texttt{0}$ $\texttt{0}$ $\texttt{0.0000E+00}$ $\texttt{0.100000050000E+01}$ $\texttt{0.9893E+02}$ $\texttt{0.1000E+00}$ $\texttt{1}$ $\texttt{224}$ $\texttt{0.1000E+01}$ $\texttt{0.102710574197E+01}$ $\texttt{0.1811E+02}$ $\texttt{0.2648E-01}$ $\texttt{2}$ $\texttt{6}$ $\texttt{0.1000E+01}$ $\texttt{0.107819921922E+01}$ $\texttt{0.2086E+00}$ $\texttt{0.5244E-02}$ $\texttt{3}$ $\texttt{24}$ $\texttt{0.1000E+01}$ $\texttt{0.109015429623E+01}$ $\texttt{0.4723E-02}$ $\texttt{0.2969E-03}$ $\texttt{4}$ $\texttt{5}$ $\texttt{0.1000E+01}$ $\texttt{0.109049950972E+01}$ $\texttt{0.3198E-05}$ $\texttt{0.4477E-06}$ $\texttt{5}$ $\texttt{3}$ $\texttt{0.1000E+01}$ $\texttt{0.109049961114E+01}$ $\texttt{0.4253E-11}$ $\texttt{0.4570E-12}$ $\texttt{END OF SQP METHOD}$
Sequence of problems with gradually refined discretisations solved with $\texttt{sqpfiltertoolbox}$ Method (A) and $\texttt{SNOPT}$. $\texttt{SQPIT}$ states the number of SQP iterations.
 $\underline{\rm{\texttt{problem}}\ \rm{\texttt{data:}}}$ $\texttt{FEASTOL = 1.00E-008}$ $\alpha_0$ = $\texttt{1.00E-001}$ $\texttt{OPTTOL = 1.00E-008}$ $\alpha_1$ = $\texttt{0}$ $\mu$ = $\texttt{1.00E-012}$ $\alpha_2$ = $\texttt{1.00E-007}$ $\texttt{threshold = 1.00E-002}$ $\alpha_3$ = $\texttt{1.00E+000}$ $\texttt{initialisation by collocation}$ $\alpha_4$ = $\texttt{1.00E-007}$ $c_0$ = $\texttt{1.00E-003}$ $\texttt{N}$ $\texttt{M}$ $\tilde{J}$ $\texttt{SQPIT}$ $\texttt{QPIT}$ $t[s]$ $t[s]$ $\texttt{SNOPT}$ $\texttt{150}$ $\texttt{5}$ $\texttt{1.0905}$ $\texttt{5}$ $\texttt{263}$ $\texttt{10.4}$ $\texttt{1.6}$ $\texttt{300}$ $\texttt{10}$ $\texttt{1.0870}$ $\texttt{3}$ $\texttt{47}$ $\texttt{19.4}$ $\texttt{7.8}$ $\texttt{450}$ $\texttt{15}$ $\texttt{1.0840}$ $\texttt{3}$ $\texttt{49}$ $\texttt{91.6}$ $\texttt{25.4}$ $\texttt{600}$ $\texttt{20}$ $\texttt{1.0810}$ $\texttt{3}$ $\texttt{49}$ $\texttt{281.9}$ $\texttt{99.0}$ $\texttt{900}$ $\texttt{30}$ $\texttt{1.0751}$ $\texttt{4}$ $\texttt{110}$ $\texttt{2824.7}$ $\texttt{1541.0}$ $\texttt{1200}$ $\texttt{40}$ $\texttt{1.0705}$ $\texttt{4}$ $\texttt{289}$ $\texttt{22333.2}$ $\texttt{162545.6}$
 $\underline{\rm{\texttt{problem}}\ \rm{\texttt{data:}}}$ $\texttt{FEASTOL = 1.00E-008}$ $\alpha_0$ = $\texttt{1.00E-001}$ $\texttt{OPTTOL = 1.00E-008}$ $\alpha_1$ = $\texttt{0}$ $\mu$ = $\texttt{1.00E-012}$ $\alpha_2$ = $\texttt{1.00E-007}$ $\texttt{threshold = 1.00E-002}$ $\alpha_3$ = $\texttt{1.00E+000}$ $\texttt{initialisation by collocation}$ $\alpha_4$ = $\texttt{1.00E-007}$ $c_0$ = $\texttt{1.00E-003}$ $\texttt{N}$ $\texttt{M}$ $\tilde{J}$ $\texttt{SQPIT}$ $\texttt{QPIT}$ $t[s]$ $t[s]$ $\texttt{SNOPT}$ $\texttt{150}$ $\texttt{5}$ $\texttt{1.0905}$ $\texttt{5}$ $\texttt{263}$ $\texttt{10.4}$ $\texttt{1.6}$ $\texttt{300}$ $\texttt{10}$ $\texttt{1.0870}$ $\texttt{3}$ $\texttt{47}$ $\texttt{19.4}$ $\texttt{7.8}$ $\texttt{450}$ $\texttt{15}$ $\texttt{1.0840}$ $\texttt{3}$ $\texttt{49}$ $\texttt{91.6}$ $\texttt{25.4}$ $\texttt{600}$ $\texttt{20}$ $\texttt{1.0810}$ $\texttt{3}$ $\texttt{49}$ $\texttt{281.9}$ $\texttt{99.0}$ $\texttt{900}$ $\texttt{30}$ $\texttt{1.0751}$ $\texttt{4}$ $\texttt{110}$ $\texttt{2824.7}$ $\texttt{1541.0}$ $\texttt{1200}$ $\texttt{40}$ $\texttt{1.0705}$ $\texttt{4}$ $\texttt{289}$ $\texttt{22333.2}$ $\texttt{162545.6}$
 [1] Matthias Gerdts, Sven-Joachim Kimmerle. Numerical optimal control of a coupled ODE-PDE model of a truck with a fluid basin. Conference Publications, 2015, 2015 (special) : 515-524. doi: 10.3934/proc.2015.0515 [2] Sabine Eisenhofer, Messoud A. Efendiev, Mitsuharu Ôtani, Sabine Schulz, Hans Zischka. On an ODE-PDE coupling model of the mitochondrial swelling process. Discrete & Continuous Dynamical Systems - B, 2015, 20 (4) : 1031-1057. doi: 10.3934/dcdsb.2015.20.1031 [3] Maria Laura Delle Monache, Paola Goatin. A front tracking method for a strongly coupled PDE-ODE system with moving density constraints in traffic flow. Discrete & Continuous Dynamical Systems - S, 2014, 7 (3) : 435-447. doi: 10.3934/dcdss.2014.7.435 [4] Jean-Frédéric Gerbeau, Benoit Perthame. Derivation of viscous Saint-Venant system for laminar shallow water; Numerical validation. Discrete & Continuous Dynamical Systems - B, 2001, 1 (1) : 89-102. doi: 10.3934/dcdsb.2001.1.89 [5] Hermano Frid. Invariant regions under Lax-Friedrichs scheme for multidimensional systems of conservation laws. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 585-593. doi: 10.3934/dcds.1995.1.585 [6] Marie-Odile Bristeau, Jacques Sainte-Marie. Derivation of a non-hydrostatic shallow water model; Comparison with Saint-Venant and Boussinesq systems. Discrete & Continuous Dynamical Systems - B, 2008, 10 (4) : 733-759. doi: 10.3934/dcdsb.2008.10.733 [7] Emmanuel Audusse, Fayssal Benkhaldoun, Jacques Sainte-Marie, Mohammed Seaid. Multilayer Saint-Venant equations over movable beds. Discrete & Continuous Dynamical Systems - B, 2011, 15 (4) : 917-934. doi: 10.3934/dcdsb.2011.15.917 [8] Georges Bastin, Jean-Michel Coron, Brigitte d'Andréa-Novel. On Lyapunov stability of linearised Saint-Venant equations for a sloping channel. Networks & Heterogeneous Media, 2009, 4 (2) : 177-187. doi: 10.3934/nhm.2009.4.177 [9] Paolo Baiti, Alberto Bressan, Helge Kristian Jenssen. Instability of travelling wave profiles for the Lax-Friedrichs scheme. Discrete & Continuous Dynamical Systems - A, 2005, 13 (4) : 877-899. doi: 10.3934/dcds.2005.13.877 [10] Ciro D'Apice, Peter I. Kogut, Rosanna Manzo. On relaxation of state constrained optimal control problem for a PDE-ODE model of supply chains. Networks & Heterogeneous Media, 2014, 9 (3) : 501-518. doi: 10.3934/nhm.2014.9.501 [11] Hassen Arfaoui, Faker Ben Belgacem, Henda El Fekih, Jean-Pierre Raymond. Boundary stabilizability of the linearized viscous Saint-Venant system. Discrete & Continuous Dynamical Systems - B, 2011, 15 (3) : 491-511. doi: 10.3934/dcdsb.2011.15.491 [12] Adam Bobrowski, Katarzyna Morawska. From a PDE model to an ODE model of dynamics of synaptic depression. Discrete & Continuous Dynamical Systems - B, 2012, 17 (7) : 2313-2327. doi: 10.3934/dcdsb.2012.17.2313 [13] E. Audusse. A multilayer Saint-Venant model: Derivation and numerical validation. Discrete & Continuous Dynamical Systems - B, 2005, 5 (2) : 189-214. doi: 10.3934/dcdsb.2005.5.189 [14] Youshan Tao, J. Ignacio Tello. Nonlinear stability of a heterogeneous state in a PDE-ODE model for acid-mediated tumor invasion. Mathematical Biosciences & Engineering, 2016, 13 (1) : 193-207. doi: 10.3934/mbe.2016.13.193 [15] Wen-ling Zhao, Dao-jin Song. A global error bound via the SQP method for constrained optimization problem. Journal of Industrial & Management Optimization, 2007, 3 (4) : 775-781. doi: 10.3934/jimo.2007.3.775 [16] Roberto Triggiani. The coupled PDE system of a composite (sandwich) beam revisited. Discrete & Continuous Dynamical Systems - B, 2003, 3 (2) : 285-298. doi: 10.3934/dcdsb.2003.3.285 [17] François Bouchut, Vladimir Zeitlin. A robust well-balanced scheme for multi-layer shallow water equations. Discrete & Continuous Dynamical Systems - B, 2010, 13 (4) : 739-758. doi: 10.3934/dcdsb.2010.13.739 [18] Nora Aïssiouene, Marie-Odile Bristeau, Edwige Godlewski, Jacques Sainte-Marie. A combined finite volume - finite element scheme for a dispersive shallow water system. Networks & Heterogeneous Media, 2016, 11 (1) : 1-27. doi: 10.3934/nhm.2016.11.1 [19] George Avalos, Roberto Triggiani. Semigroup well-posedness in the energy space of a parabolic-hyperbolic coupled Stokes-Lamé PDE system of fluid-structure interaction. Discrete & Continuous Dynamical Systems - S, 2009, 2 (3) : 417-447. doi: 10.3934/dcdss.2009.2.417 [20] Kun Wang, Yinnian He, Yueqiang Shang. Fully discrete finite element method for the viscoelastic fluid motion equations. Discrete & Continuous Dynamical Systems - B, 2010, 13 (3) : 665-684. doi: 10.3934/dcdsb.2010.13.665

2017 Impact Factor: 0.561