• Previous Article
    Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems
  • JIMO Home
  • This Issue
  • Next Article
    On an optimal control problem in laser cutting with mixed finite-/infinite-dimensional constraints
April  2014, 10(2): 521-542. doi: 10.3934/jimo.2014.10.521

Inexact restoration and adaptive mesh refinement for optimal control

1. 

School of Mathematics and Statistics, University of South Australia, Mawson Lakes , SA 5095, Australia

2. 

School of Mathematics and Statistics, University of South Australia, Mawson Lakes, S.A. 5095

Received  September 2012 Revised  August 2013 Published  October 2013

A new adaptive mesh refinement algorithm is proposed for solving Euler discretization of state- and control-constrained optimal control problems. Our approach is designed to reduce the computational effort by applying the inexact restoration (IR) method, a numerical method for nonlinear programming problems, in an innovative way. The initial iterations of our algorithm start with a coarse mesh, which typically involves far fewer discretization points than the fine mesh over which we aim to obtain a solution. The coarse mesh is then refined adaptively, by using the sufficient conditions of convergence of the IR method. The resulting adaptive mesh refinement algorithm is convergent to a fine mesh solution, by virtue of convergence of the IR method. We illustrate the algorithm on a computationally challenging constrained optimal control problem involving a container crane. Numerical experiments demonstrate that significant computational savings can be achieved by the new adaptive mesh refinement algorithm over the fixed-mesh algorithm. Conceivably owing to the small number of variables at start, the adaptive mesh refinement algorithm appears to be more robust as well, i.e., it can find solutions with a much wider range of initial guesses, compared to the fixed-mesh algorithm.
Citation: Nahid Banihashemi, C. Yalçın Kaya. Inexact restoration and adaptive mesh refinement for optimal control. Journal of Industrial and Management Optimization, 2014, 10 (2) : 521-542. doi: 10.3934/jimo.2014.10.521
References:
[1]

D. Augustin and H. Maurer, Sensitivity analysis and real-time control of a container crane under state constraints, in Online Optimization of Large Scale Systems (eds. M. Grötschel, S. O. Krumke and J. Rambau), Springer, Berlin, 2001, 69-82.

[2]

N. Banihashemi and C. Yalçin Kaya, Inexact restoration for Euler discretization of box-constrained optimal control problems, J. Optim. Theory Appl., 156 (2013), 726-760. doi: 10.1007/s10957-012-0140-4.

[3]

M. J. Berger and J. Oliger, Adaptive mesh refinement for hyperbolic partial differential equations, Journal of Computational Physics, 53 (1984), 484-512. doi: 10.1016/0021-9991(84)90073-1.

[4]

J. T. Betts and W. P. Huffman, Mesh refinement in direct transcription methods for optimal control, Optimal Control Appl. and Methods, 19 (1998), 1-21.

[5]

E. G. Birgin and J. M. Martínez, Local convergence of an inexact-restoration method and numerical experiments, J. Optim. Theory Appl., 127 (2005), 229-247. doi: 10.1007/s10957-005-6537-6.

[6]

L. F. Bueno, A. Friedlander, J. M. Martínez and F. N. C. Sobral, Inexact Restoration method for derivative-free optimization with smooth constraints, SIAM J. Optim., 23 (2013), 1189-1213. doi: 10.1137/110856253.

[7]

A. L. Dontchev and W. W. Hager, The Euler approximation in state constrained optimal control, Math. Comp., 70 (2001), 173-203. doi: 10.1090/S0025-5718-00-01184-4.

[8]

A. L. Dontchev, W. W. Hager and K. Malanowski, Error bound for Euler approximation of a state and control constrained optimal control problem, Numer. Funct. Anal. Optim., 21 (2000), 653-682. doi: 10.1080/01630560008816979.

[9]

A. L. Dontchev, W. W. Hager and V. M. Veliov, Uniform convergence and mesh independence of Newton's method for discretized variational problems, SIAM J. Control Optim., 39 (2000), 961-980. doi: 10.1137/S0363012998338570.

[10]

A. Fischer and A. Friedlander, A new line search inexact restoration approach for nonlinear programming, Comput. Optim. Appl., 46 (2010), 333-346. doi: 10.1007/s10589-009-9267-0.

[11]

R. Fourer, D. M. Gay and B. W. Kernighan, AMPL: A Modelling Language for Mathematical Programming, $ 2^{nd}$ edition, Duxbury Press, Brooks/Cole Publishing Company, 2002.

[12]

W. W. Hager, Runge-Kutta methods in optimal control and the transformed adjoint system, Numer. Math., 87 (2000), 247-282. doi: 10.1007/s002110000178.

[13]

R. F. Hartl, S. P. Sethi and R. G. Vickson, A survey of the maximum principles for optimal control problems with state constraints, SIAM Rev., 37 (1995), 181-218. doi: 10.1137/1037043.

[14]

S. Jain, Multiresolution Strategies for the Numerical Solution of Optimal Control Problems, Ph.D thesis, Georgian Institution of Technology, Atlanta, GA, 2008.

[15]

C. Y. Kaya, Inexact restoration for Runge-Kutta discretization of optimal control, SIAM J. Numer. Anal., 48 (2010), 1492-1517. doi: 10.1137/090766668.

[16]

C. Y. Kaya and J. M. Martínez, Euler discretization for inexact restoration and optimal control, J. Optim. Theory Appl., 134 (2007), 191-206. doi: 10.1007/s10957-007-9217-x.

[17]

J. Laurent-Varin, F. Bonnans, N. Berend, C. Talbot and M. Haddou, On the refinement of discretization for optimal control problems, in 16th IFAC Symposium on Automatic Control in Aerospace, Saint-Petersburg, Russia, 2004, 405-408.

[18]

K. Malanowski, C. Büskens and H. Maurer, Convergence of approximations to nonlinear optimal control problems, in Mathematical Programming with Data Perturbations (ed. A. V. Fiacco), Lecture Notes in Pure and Appl. Math., 195, Dekker, New York, 1998, 253-284.

[19]

J. M. Martínez, Inexact-restoration method with Lagrangian tangent decrease and new merit function for nonlinear programming, J. Optim. Theory Appl., 111 (2001), 39-58. doi: 10.1023/A:1017567113614.

[20]

J. M. Martínez and E. A. Pilotta, Inexact-restoration algorithm for constrained optimization, J. Optim. Theory Appl., 104 (2000), 135-163. doi: 10.1023/A:1004632923654.

[21]

B. S. Mordukhovich, Variational Analysis and Generalized Differentiation. II. Applications, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 331, Springer-Verlag, Berlin, 2006.

[22]

R. Pytlak and R. B. Vinter, Feasible direction algorithm for optimal control problems with state and control constraints: Implementation, J. Optim. Theory Appl., 101 (1999), 623-649. doi: 10.1023/A:1021742204850.

[23]

S. Repin, A Posteriori Estimates For Partial Differential Equations, Radon Series on Computational and Applied Mathematics, 4, Walter de Gruyter GmbH & Co. KG, Berlin, 2008. doi: 10.1515/9783110203042.

[24]

C. J. Roy, Grid convergence error analysis for mixed-order numerical schemes, AIAA Journal, 41 (2003), 595-604. doi: 10.2514/2.2013.

[25]

Y. Sakawa and Y. Shindo, Optimal control of container cranes, Automatica, 18 (1982), 257-266. doi: 10.1016/0005-1098(82)90086-3.

[26]

A. L. Schwarts, Theory and Implementation of Numerical Methods Based on Runge-Kutta Integration for Solving Optimal Control Problems, Ph.D thesis, University of California Berkeley, CA, 1996.

[27]

K. L. Teo and L. S. Jennings, Nonlinear optimal control problems with continuous state inequality constraints, J. Optim. Theory Appl., 63 (1989), 1-22. doi: 10.1007/BF00940727.

[28]

V. Veliov, On the time-discretization of control systems, SIAM J. Control Optim., 35 (1997), 1470-1486. doi: 10.1137/S0363012995288987.

[29]

A. Wächter, and 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. doi: 10.1007/s10107-004-0559-y.

[30]

Y. Zhao and P. Tsiotras, Density functions for mesh refinement in numerical optimal control, Journal of Guidance, Control, and Dynamics, 34 (2011), 271-277. doi: 10.2514/1.45852.

show all references

References:
[1]

D. Augustin and H. Maurer, Sensitivity analysis and real-time control of a container crane under state constraints, in Online Optimization of Large Scale Systems (eds. M. Grötschel, S. O. Krumke and J. Rambau), Springer, Berlin, 2001, 69-82.

[2]

N. Banihashemi and C. Yalçin Kaya, Inexact restoration for Euler discretization of box-constrained optimal control problems, J. Optim. Theory Appl., 156 (2013), 726-760. doi: 10.1007/s10957-012-0140-4.

[3]

M. J. Berger and J. Oliger, Adaptive mesh refinement for hyperbolic partial differential equations, Journal of Computational Physics, 53 (1984), 484-512. doi: 10.1016/0021-9991(84)90073-1.

[4]

J. T. Betts and W. P. Huffman, Mesh refinement in direct transcription methods for optimal control, Optimal Control Appl. and Methods, 19 (1998), 1-21.

[5]

E. G. Birgin and J. M. Martínez, Local convergence of an inexact-restoration method and numerical experiments, J. Optim. Theory Appl., 127 (2005), 229-247. doi: 10.1007/s10957-005-6537-6.

[6]

L. F. Bueno, A. Friedlander, J. M. Martínez and F. N. C. Sobral, Inexact Restoration method for derivative-free optimization with smooth constraints, SIAM J. Optim., 23 (2013), 1189-1213. doi: 10.1137/110856253.

[7]

A. L. Dontchev and W. W. Hager, The Euler approximation in state constrained optimal control, Math. Comp., 70 (2001), 173-203. doi: 10.1090/S0025-5718-00-01184-4.

[8]

A. L. Dontchev, W. W. Hager and K. Malanowski, Error bound for Euler approximation of a state and control constrained optimal control problem, Numer. Funct. Anal. Optim., 21 (2000), 653-682. doi: 10.1080/01630560008816979.

[9]

A. L. Dontchev, W. W. Hager and V. M. Veliov, Uniform convergence and mesh independence of Newton's method for discretized variational problems, SIAM J. Control Optim., 39 (2000), 961-980. doi: 10.1137/S0363012998338570.

[10]

A. Fischer and A. Friedlander, A new line search inexact restoration approach for nonlinear programming, Comput. Optim. Appl., 46 (2010), 333-346. doi: 10.1007/s10589-009-9267-0.

[11]

R. Fourer, D. M. Gay and B. W. Kernighan, AMPL: A Modelling Language for Mathematical Programming, $ 2^{nd}$ edition, Duxbury Press, Brooks/Cole Publishing Company, 2002.

[12]

W. W. Hager, Runge-Kutta methods in optimal control and the transformed adjoint system, Numer. Math., 87 (2000), 247-282. doi: 10.1007/s002110000178.

[13]

R. F. Hartl, S. P. Sethi and R. G. Vickson, A survey of the maximum principles for optimal control problems with state constraints, SIAM Rev., 37 (1995), 181-218. doi: 10.1137/1037043.

[14]

S. Jain, Multiresolution Strategies for the Numerical Solution of Optimal Control Problems, Ph.D thesis, Georgian Institution of Technology, Atlanta, GA, 2008.

[15]

C. Y. Kaya, Inexact restoration for Runge-Kutta discretization of optimal control, SIAM J. Numer. Anal., 48 (2010), 1492-1517. doi: 10.1137/090766668.

[16]

C. Y. Kaya and J. M. Martínez, Euler discretization for inexact restoration and optimal control, J. Optim. Theory Appl., 134 (2007), 191-206. doi: 10.1007/s10957-007-9217-x.

[17]

J. Laurent-Varin, F. Bonnans, N. Berend, C. Talbot and M. Haddou, On the refinement of discretization for optimal control problems, in 16th IFAC Symposium on Automatic Control in Aerospace, Saint-Petersburg, Russia, 2004, 405-408.

[18]

K. Malanowski, C. Büskens and H. Maurer, Convergence of approximations to nonlinear optimal control problems, in Mathematical Programming with Data Perturbations (ed. A. V. Fiacco), Lecture Notes in Pure and Appl. Math., 195, Dekker, New York, 1998, 253-284.

[19]

J. M. Martínez, Inexact-restoration method with Lagrangian tangent decrease and new merit function for nonlinear programming, J. Optim. Theory Appl., 111 (2001), 39-58. doi: 10.1023/A:1017567113614.

[20]

J. M. Martínez and E. A. Pilotta, Inexact-restoration algorithm for constrained optimization, J. Optim. Theory Appl., 104 (2000), 135-163. doi: 10.1023/A:1004632923654.

[21]

B. S. Mordukhovich, Variational Analysis and Generalized Differentiation. II. Applications, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 331, Springer-Verlag, Berlin, 2006.

[22]

R. Pytlak and R. B. Vinter, Feasible direction algorithm for optimal control problems with state and control constraints: Implementation, J. Optim. Theory Appl., 101 (1999), 623-649. doi: 10.1023/A:1021742204850.

[23]

S. Repin, A Posteriori Estimates For Partial Differential Equations, Radon Series on Computational and Applied Mathematics, 4, Walter de Gruyter GmbH & Co. KG, Berlin, 2008. doi: 10.1515/9783110203042.

[24]

C. J. Roy, Grid convergence error analysis for mixed-order numerical schemes, AIAA Journal, 41 (2003), 595-604. doi: 10.2514/2.2013.

[25]

Y. Sakawa and Y. Shindo, Optimal control of container cranes, Automatica, 18 (1982), 257-266. doi: 10.1016/0005-1098(82)90086-3.

[26]

A. L. Schwarts, Theory and Implementation of Numerical Methods Based on Runge-Kutta Integration for Solving Optimal Control Problems, Ph.D thesis, University of California Berkeley, CA, 1996.

[27]

K. L. Teo and L. S. Jennings, Nonlinear optimal control problems with continuous state inequality constraints, J. Optim. Theory Appl., 63 (1989), 1-22. doi: 10.1007/BF00940727.

[28]

V. Veliov, On the time-discretization of control systems, SIAM J. Control Optim., 35 (1997), 1470-1486. doi: 10.1137/S0363012995288987.

[29]

A. Wächter, and 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. doi: 10.1007/s10107-004-0559-y.

[30]

Y. Zhao and P. Tsiotras, Density functions for mesh refinement in numerical optimal control, Journal of Guidance, Control, and Dynamics, 34 (2011), 271-277. doi: 10.2514/1.45852.

[1]

Luís Tiago Paiva, Fernando A. C. C. Fontes. Adaptive time--mesh refinement in optimal control problems with state constraints. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4553-4572. doi: 10.3934/dcds.2015.35.4553

[2]

Matthias Gerdts, Martin Kunkel. Convergence analysis of Euler discretization of control-state constrained optimal control problems with controls of bounded variation. Journal of Industrial and Management Optimization, 2014, 10 (1) : 311-336. doi: 10.3934/jimo.2014.10.311

[3]

Luís Tiago Paiva, Fernando A. C. C. Fontes. Sampled–data model predictive control: Adaptive time–mesh refinement algorithms and guarantees of stability. Discrete and Continuous Dynamical Systems - B, 2019, 24 (5) : 2335-2364. doi: 10.3934/dcdsb.2019098

[4]

Kazimierz Malanowski, Helmut Maurer. Sensitivity analysis for state constrained optimal control problems. Discrete and Continuous Dynamical Systems, 1998, 4 (2) : 241-272. doi: 10.3934/dcds.1998.4.241

[5]

Piernicola Bettiol. State constrained $L^\infty$ optimal control problems interpreted as differential games. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 3989-4017. doi: 10.3934/dcds.2015.35.3989

[6]

Christian Clason, Barbara Kaltenbacher. Avoiding degeneracy in the Westervelt equation by state constrained optimal control. Evolution Equations and Control Theory, 2013, 2 (2) : 281-300. doi: 10.3934/eect.2013.2.281

[7]

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 and Heterogeneous Media, 2014, 9 (3) : 501-518. doi: 10.3934/nhm.2014.9.501

[8]

Cristiana J. Silva, Helmut Maurer, Delfim F. M. Torres. Optimal control of a Tuberculosis model with state and control delays. Mathematical Biosciences & Engineering, 2017, 14 (1) : 321-337. doi: 10.3934/mbe.2017021

[9]

Tobias Geiger, Daniel Wachsmuth, Gerd Wachsmuth. Optimal control of ODEs with state suprema. Mathematical Control and Related Fields, 2021, 11 (3) : 555-578. doi: 10.3934/mcrf.2021012

[10]

Max Gunzburger, Sung-Dae Yang, Wenxiang Zhu. Analysis and discretization of an optimal control problem for the forced Fisher equation. Discrete and Continuous Dynamical Systems - B, 2007, 8 (3) : 569-587. doi: 10.3934/dcdsb.2007.8.569

[11]

Canghua Jiang, Dongming Zhang, Chi Yuan, Kok Ley Teo. An active set solver for constrained $ H_\infty $ optimal control problems with state and input constraints. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 135-157. doi: 10.3934/naco.2021056

[12]

Ariela Briani, Hasnaa Zidani. Characterization of the value function of final state constrained control problems with BV trajectories. Communications on Pure and Applied Analysis, 2011, 10 (6) : 1567-1587. doi: 10.3934/cpaa.2011.10.1567

[13]

Jérome Lohéac, Jean-François Scheid. Time optimal control for a nonholonomic system with state constraint. Mathematical Control and Related Fields, 2013, 3 (2) : 185-208. doi: 10.3934/mcrf.2013.3.185

[14]

Bin Li, Kok Lay Teo, Cheng-Chew Lim, Guang Ren Duan. An optimal PID controller design for nonlinear constrained optimal control problems. Discrete and Continuous Dynamical Systems - B, 2011, 16 (4) : 1101-1117. doi: 10.3934/dcdsb.2011.16.1101

[15]

Eduardo Casas, Fredi Tröltzsch. Sparse optimal control for the heat equation with mixed control-state constraints. Mathematical Control and Related Fields, 2020, 10 (3) : 471-491. doi: 10.3934/mcrf.2020007

[16]

Lili Chang, Wei Gong, Guiquan Sun, Ningning Yan. PDE-constrained optimal control approach for the approximation of an inverse Cauchy problem. Inverse Problems and Imaging, 2015, 9 (3) : 791-814. doi: 10.3934/ipi.2015.9.791

[17]

Janosch Rieger. The Euler scheme for state constrained ordinary differential inclusions. Discrete and Continuous Dynamical Systems - B, 2016, 21 (8) : 2729-2744. doi: 10.3934/dcdsb.2016070

[18]

David González-Sánchez, Onésimo Hernández-Lerma. On the Euler equation approach to discrete--time nonstationary optimal control problems. Journal of Dynamics and Games, 2014, 1 (1) : 57-78. doi: 10.3934/jdg.2014.1.57

[19]

Evelyn Herberg, Michael Hinze. Variational discretization of one-dimensional elliptic optimal control problems with BV functions based on the mixed formulation. Mathematical Control and Related Fields, 2022  doi: 10.3934/mcrf.2022013

[20]

Changzhi Wu, Kok Lay Teo, Volker Rehbock. Optimal control of piecewise affine systems with piecewise affine state feedback. Journal of Industrial and Management Optimization, 2009, 5 (4) : 737-747. doi: 10.3934/jimo.2009.5.737

2020 Impact Factor: 1.801

Metrics

  • PDF downloads (109)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]