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

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

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

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

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

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

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

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

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

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

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

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

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

[14]

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

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

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

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

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

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

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

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

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

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

[24]

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

[25]

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

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

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

[28]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[14]

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

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

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

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

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

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

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

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

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

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

[24]

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

[25]

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

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

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

[28]

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

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

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

[1]

Luís Tiago Paiva, Fernando A. C. C. Fontes. Adaptive time--mesh refinement in optimal control problems with state constraints. Discrete & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Related Fields, 2021  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 & Continuous Dynamical Systems - B, 2007, 8 (3) : 569-587. doi: 10.3934/dcdsb.2007.8.569

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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 & Games, 2014, 1 (1) : 57-78. doi: 10.3934/jdg.2014.1.57

[18]

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

[19]

Ana P. Lemos-Paião, Cristiana J. Silva, Delfim F. M. Torres. A sufficient optimality condition for delayed state-linear optimal control problems. Discrete & Continuous Dynamical Systems - B, 2019, 24 (5) : 2293-2313. doi: 10.3934/dcdsb.2019096

[20]

Claude Stolz. On estimation of internal state by an optimal control approach for elastoplastic material. Discrete & Continuous Dynamical Systems - S, 2016, 9 (2) : 599-611. doi: 10.3934/dcdss.2016014

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]