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

Jan-Hendrik Webert; Philip E. Gill; Sven-Joachim Kimmerle; Matthias Gerdts

doi:10.3934/dcdss.2018071

Article Contents

2018, Volume 11, Issue 6: 1259-1282. Doi: 10.3934/dcdss.2018071

This issue Previous Article Second order necessary and sufficient optimality conditions for singular solutions of partially-affine control problems Next Article Structure of approximate solutions of Bolza variational problems on large intervals

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
* Corresponding author: Sven-Joachim Kimmerle

Received: April 2017

Revised: September 2017

Published: December 2018

Abstract / Introduction Full Text(HTML) Figure(4) / Table(2) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 49J15, 49J20, 90C53, 90C55; Secondary: 35Q35, 35L04, 49N90.

Citation:

Full Text(HTML)

Figure 1. Model of the truck and fluid tank, cf. [7].

Download: Full-size image PowerPoint slide

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.

Download: Full-size image PowerPoint slide

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.

Download: Full-size image PowerPoint slide

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$.

Download: Full-size image PowerPoint slide

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}$

| Show Table

DownLoad: CSV

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}$

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

	J. T. Betts, Practical Methods for Optimal Control Using Nonlinear Programming, 2^nd edition, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2010. doi: 10.1137/1.9780898718577.
	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.
	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.
	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.
	A. Forsgren , Inertia-controlling factorizations for optimization algorithms, Applied Numerical Mathematics, 43 (2002) , 91-107. doi: 10.1016/S0168-9274(02)00119-8.
	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.)
	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.
	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.
	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.
	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.
	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.
	D. Luenberger and Y. Ye, Linear and Nonlinear Programming, 3^rd edition, Springer, US, 2008. doi: 10.1007/978-3-319-18842-3.
	J. Nocedal and S. J. Wright, Numerical Optimization, 2^nd edition, Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006. doi: 10.1007/b98874.
	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.
	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.