Douglas–Rachford algorithm for control- and state-constrained optimal control problems

Regina S. Burachik; Bethany I. Caldwell; C. Yalçın Kaya; Regina S. Burachik; Bethany I. Caldwell; C. Yalçın Kaya

doi:10.3934/math.2024675

AIMS Mathematics

2024, Volume 9, Issue 6: 13874-13893. doi: 10.3934/math.2024675

Previous Article Next Article

Research article Special Issues

Douglas–Rachford algorithm for control- and state-constrained optimal control problems

Mathematics, UniSA STEM, University of South Australia, Mawson Lakes, S.A. 5095, Australia

Received: 14 January 2024 Revised: 29 March 2024 Accepted: 09 April 2024 Published: 15 April 2024
MSC : 34H05, 49M37, 49N10, 65K10, 65L10

We consider the application of the Douglas–Rachford (DR) algorithm to solve linear-quadratic (LQ) control problems with box constraints on the state and control variables. We have split the constraints of the optimal control problem into two sets: one involving the ordinary differential equation with boundary conditions, which is affine, and the other, a box. We have rewritten the LQ control problems as the minimization of the sum of two convex functions. We have found the proximal mappings of these functions, which we then employ for the projections in the DR iterations. We propose a numerical algorithm for computing the projection onto the affine set. We present a conjecture for finding the costates and the state constraint multipliers of the optimal control problem, which can, in turn, be used to verify the optimality conditions. We conducted numerical experiments with two constrained optimal control problems to illustrate the performance and the efficiency of the DR algorithm in comparison with the traditional approach of direct discretization.
- optimal control,
- Douglas–Rachford algorithm,
- harmonic oscillator,
- control constraints,
- state constraints,
- numerical methods
Citation: Regina S. Burachik, Bethany I. Caldwell, C. Yalçın Kaya. Douglas–Rachford algorithm for control- and state-constrained optimal control problems[J]. AIMS Mathematics, 2024, 9(6): 13874-13893. doi: 10.3934/math.2024675

Related Papers:

Abstract

We consider the application of the Douglas–Rachford (DR) algorithm to solve linear-quadratic (LQ) control problems with box constraints on the state and control variables. We have split the constraints of the optimal control problem into two sets: one involving the ordinary differential equation with boundary conditions, which is affine, and the other, a box. We have rewritten the LQ control problems as the minimization of the sum of two convex functions. We have found the proximal mappings of these functions, which we then employ for the projections in the DR iterations. We propose a numerical algorithm for computing the projection onto the affine set. We present a conjecture for finding the costates and the state constraint multipliers of the optimal control problem, which can, in turn, be used to verify the optimality conditions. We conducted numerical experiments with two constrained optimal control problems to illustrate the performance and the efficiency of the DR algorithm in comparison with the traditional approach of direct discretization.

References

[1]	H. M. Amman, D. A. Kendrick, Computing the steady state of linear quadratic optimization models with rational expectations, Econ. Lett., 58 (1998), 185–191. http://dx.doi.org/10.1016/S0165-1765(97)00263-2 doi: 10.1016/S0165-1765(97)00263-2
[2]	F. J. Aragón Artacho, J. M. Borwein, M. K. Tam, Douglas–Rachford feasibility methods For matrix completion problems, ANZIAM J., 55 (2014), 299–326. http://dx.doi.org/10.1017/S1446181114000145 doi: 10.1017/S1446181114000145
[3]	F. J. Aragón Artacho, R. Campoy, V. Elser, An enhanced formulation for solving graph coloring problems with the Douglas–Rachford algorithm, J. Glob. Optim., 77 (2020), 383–403. http://dx.doi.org/10.1007/s10898-019-00867-x doi: 10.1007/s10898-019-00867-x
[4]	U. M. Ascher, R. M. M. Mattheij, R. D. Russell, Numerical Solution of Boundary Value Problems for Ordinary Differential Equations, Philadelphia: SIAM Publications, 1995. http://dx.doi.org/10.1137/1.9781611971231
[5]	N. Banihashemi, C. Y. Kaya, Inexact restoration for Euler discretization of box-constrained optimal control problems, J. Optim. Theory Appl., 156 (2013), 726–760. http://dx.doi.org/10.1007/s10957-012-0140-4 doi: 10.1007/s10957-012-0140-4
[6]	H. H. Bauschke, 8 queens, sudoku, and projection methods, The Mathematical Interests of Peter Borwein, The IRMACS Centre, 2008. Available from: https://carmamaths.org/resources/jon/Preprints/Talks/Inverse Probs/Earlier/Bauschke-IRMACS08.pdf.
[7]	H. H. Bauschke, R. S. Burachik, C. Y. Kaya, Constraint splitting and projection methods for optimal control of double integrator, In: Splitting Algorithms, Modern Operator Theory, and Applications, Cham: Springer, 45–68, 2019. http://dx.doi.org/10.1007/978-3-030-25939-6_2
[8]	H. H. Bauschke, P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Cham: Springer, 2017. http://dx.doi.org/10.1007/978-3-319-48311-5
[9]	H. H. Bauschke, V. R. Koch, Projection methods: Swiss Army knives for solving feasibility and best approximation problems with halfspaces, arXiv: 1301.4506.
[10]	H. H. Bauschke, W. M. Moursi, On the Douglas–Rachford algorithm, Math. Program., 164 (2017), 263–284. http://dx.doi.org/10.1007/s10107-016-1086-3 doi: 10.1007/s10107-016-1086-3
[11]	R. S. Burachik, B. I. Caldwell, C. Y. Kaya, Projection methods for control-constrained minimum-energy control problems, arXiv: 2210.17279.
[12]	R. S. Burachik, B. I. Caldwell, C. Y. Kaya, Douglas–Rachford algorithm for control-constrained minimum-energy control problems, ESAIM: COCV, 30 (2024), 18 http://dx.doi.org/10.1051/cocv/2024004 doi: 10.1051/cocv/2024004
[13]	R. S. Burachik, B. I. Caldwell, C. Y. Kaya, W. M. Moursi, Optimal control duality and the Douglas–Rachford algorithm, SIAM J. Control Optim., 62 (2024), 680–698. http://dx.doi.org/10.1137/23M1558549 doi: 10.1137/23M1558549
[14]	R. S. Burachik, C. Y. Kaya, S. N. Majeed, A duality approach for solving control-constrained linear-quadratic optimal control problems, SIAM J. Control Optim., 52 (2014), 1423–1456. http://dx.doi.org/10.1137/130910221 doi: 10.1137/130910221
[15]	C. Büskens, H. Maurer, SQP-methods for solving optimal control problems with control and state constraints: adjoint variables, sensitivity analysis and real-time control, J. Comput. Appl. Math., 120 (2000), 85–108. http://dx.doi.org/10.1016/S0377-0427(00)00305-8 doi: 10.1016/S0377-0427(00)00305-8
[16]	B. Christiansen, H. Maurer, O. Zirn, Optimal control of machine tool manipulators, In: Recent Advances in Optimization and Its Applications in Engineering, Berlin: Springer, 2010,451–460. http://dx.doi.org/10.1007/978-3-642-12598-0_39
[17]	J. Douglas, H. H. Rachford, On the numerical solution of heat conduction problems in two and three space variables, Trans. Amer. Math. Soc., 82 (1956), 421–439. http://dx.doi.org/10.2307/1993056 doi: 10.2307/1993056
[18]	J. Eckstein, D. P. Bertsekas, On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), 293–318. http://dx.doi.org/10.1007/BF01581204 doi: 10.1007/BF01581204
[19]	R. Fourer, D. M. Gay, B. W. Kernighan, AMPL: A Modeling Language for Mathematical Programming, 2 Eds., New York: Duxbury/Thomson, 2003. Available from: https://ampl.com/wp-content/uploads/BOOK.pdf.
[20]	S. Gravel, V. Elser, Divide and concur: a general approach to constraint satisfaction, Phys. Rev. E, 78 (2008), 036706. http://dx.doi.org/10.1103/PhysRevE.78.036706 doi: 10.1103/PhysRevE.78.036706
[21]	R. F. Hartl, S. P. Sethi, R. G. Vickson, A survey of the maximum principles for optimal control problems with state constraints, SIAM Rev., 37 (1995), 181–218. http://dx.doi.org/10.1137/1037043 doi: 10.1137/1037043
[22]	C. Y. Kaya, Inexact restoration for Runge-Kutta discretization of optimal control problems, SIAM J. Numer. Anal., 48 (2010), 1492–1517. http://dx.doi.org/10.1137/090766668 doi: 10.1137/090766668
[23]	H. B. Keller, Numerical Methods for Two-point Boundary-Value Problems, Philadelphia: Society for Industrial and Applied Mathematics, 1972.
[24]	B. Kugelmann, H. J. Pesch, New general guidance method in constrained optimal control, part 1: numerical method, J. Optim. Theory Appl., 67 (1990), 421–435. http://dx.doi.org/10.1007/BF00939642 doi: 10.1007/BF00939642
[25]	P.-L. Lions, B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16 (1979), 964–979. http://dx.doi.org/10.1137/0716071 doi: 10.1137/0716071
[26]	H. Maurer, J.-H. R. Kim, G. Vossen, On a state-constrained control problem in optimal production and maintenance, In: Optimal Control and Dynamic Games, Boston: Springer Verlag, 2005,289–308. http://dx.doi.org/10.1007/0-387-25805-1_17
[27]	H. Maurer, H. J. Oberle, Second order sufficient conditions for optimal control problems with free final time: the Riccati approach, SIAM J. Control Optim., 41 (2002), 380–403. http://dx.doi.org/10.1137/S0363012900377419 doi: 10.1137/S0363012900377419
[28]	T. Mouktonglang, Innate immune response via perturbed LQ-control problem, Advanced Studies in Biology, 3 (2011), 327–332.
[29]	W. J. Rugh, Linear system theory, 2 Eds., London: Pearson, 1996.
[30]	T. L. Schmitz, K. S. Smith, Mechanical vibrations modeling and measurement, New York: Springer, 2011. http://dx.doi.org/10.1007/978-1-4614-0460-6
[31]	J. Stoer, R. Bulirsch, Introduction to numerical analysis, 3 Eds., New York: Springer-Verlag, 2002. http://dx.doi.org/10.1007/978-0-387-21738-3
[32]	B. F. Svaiter, On weak convergence of the Douglas–Rachford method, SIAM J. Control Optim., 49 (2011), 280–287. http://dx.doi.org/10.1137/100788100 doi: 10.1137/100788100
[33]	A. Wächter, L. T. Biegler, On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming, Math. Program., 106 (2006), 25–57. http://dx.doi.org/10.1007/s10107-004-0559-y doi: 10.1007/s10107-004-0559-y

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)