• Previous Article
    Structure of approximate solutions of Bolza variational problems on large intervals
  • DCDS-S Home
  • This Issue
  • Next Article
    Second order necessary and sufficient optimality conditions for singular solutions of partially-affine control problems
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.  Google Scholar

[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.  Google Scholar

[3]

R. ByrdJ. 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.  Google Scholar

[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.  Google Scholar

[5]

A. Forsgren, Inertia-controlling factorizations for optimization algorithms, Applied Numerical Mathematics, 43 (2002), 91-107.  doi: 10.1016/S0168-9274(02)00119-8.  Google Scholar

[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.) Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[12]

D. Luenberger and Y. Ye, Linear and Nonlinear Programming, 3rd edition, Springer, US, 2008. doi: 10.1007/978-3-319-18842-3.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

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.  Google Scholar

[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.  Google Scholar

[3]

R. ByrdJ. 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.  Google Scholar

[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.  Google Scholar

[5]

A. Forsgren, Inertia-controlling factorizations for optimization algorithms, Applied Numerical Mathematics, 43 (2002), 91-107.  doi: 10.1016/S0168-9274(02)00119-8.  Google Scholar

[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.) Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[12]

D. Luenberger and Y. Ye, Linear and Nonlinear Programming, 3rd edition, Springer, US, 2008. doi: 10.1007/978-3-319-18842-3.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

Figure 1.  Model of the truck and fluid tank, cf. [7].
Figure 2.  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.
Figure 3.  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.
Figure 4.  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$.
Table 1.  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}$
Table 2.  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]

Gervy Marie Angeles, Gilbert Peralta. Energy method for exponential stability of coupled one-dimensional hyperbolic PDE-ODE systems. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020108

[2]

Hassan Mohammad. A diagonal PRP-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2021, 17 (1) : 101-116. doi: 10.3934/jimo.2019101

[3]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[4]

Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380

[5]

Xavier Carvajal, Liliana Esquivel, Raphael Santos. On local well-posedness and ill-posedness results for a coupled system of mkdv type equations. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020382

[6]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462

[7]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[8]

Peter H. van der Kamp, D. I. McLaren, G. R. W. Quispel. Homogeneous darboux polynomials and generalising integrable ODE systems. Journal of Computational Dynamics, 2021, 8 (1) : 1-8. doi: 10.3934/jcd.2021001

[9]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[10]

Neng Zhu, Zhengrong Liu, Fang Wang, Kun Zhao. Asymptotic dynamics of a system of conservation laws from chemotaxis. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 813-847. doi: 10.3934/dcds.2020301

[11]

Ilyasse Lamrani, Imad El Harraki, Ali Boutoulout, Fatima-Zahrae El Alaoui. Feedback stabilization of bilinear coupled hyperbolic systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020434

[12]

Zhilei Liang, Jiangyu Shuai. Existence of strong solution for the Cauchy problem of fully compressible Navier-Stokes equations in two dimensions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020348

[13]

Jun Zhou. Lifespan of solutions to a fourth order parabolic PDE involving the Hessian modeling epitaxial growth. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5581-5590. doi: 10.3934/cpaa.2020252

[14]

Adel M. Al-Mahdi, Mohammad M. Al-Gharabli, Salim A. Messaoudi. New general decay result for a system of viscoelastic wave equations with past history. Communications on Pure & Applied Analysis, 2021, 20 (1) : 389-404. doi: 10.3934/cpaa.2020273

[15]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[16]

Fathalla A. Rihan, Hebatallah J. Alsakaji. Stochastic delay differential equations of three-species prey-predator system with cooperation among prey species. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020468

[17]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[18]

Mathew Gluck. Classification of solutions to a system of $ n^{\rm th} $ order equations on $ \mathbb R^n $. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5413-5436. doi: 10.3934/cpaa.2020246

[19]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078

[20]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250

2019 Impact Factor: 1.233

Metrics

  • PDF downloads (106)
  • HTML views (185)
  • Cited by (0)

[Back to Top]