# American Institute of Mathematical Sciences

• Previous Article
On an optimal control problem in laser cutting with mixed finite-/infinite-dimensional constraints
• JIMO Home
• This Issue
• Next Article
Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems
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, (2001), 69. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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, (2002). Google Scholar [12] W. W. Hager, Runge-Kutta methods in optimal control and the transformed adjoint system,, Numer. Math., 87 (2000), 247. 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. doi: 10.1137/1037043. Google Scholar [14] S. Jain, Multiresolution Strategies for the Numerical Solution of Optimal Control Problems,, Ph.D thesis, (2008). Google Scholar [15] C. Y. Kaya, Inexact restoration for Runge-Kutta discretization of optimal control,, SIAM J. Numer. Anal., 48 (2010), 1492. 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. 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, (2004), 405. 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), (1998), 253. 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. 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. 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], (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. doi: 10.1023/A:1021742204850. Google Scholar [23] S. Repin, A Posteriori Estimates For Partial Differential Equations,, Radon Series on Computational and Applied Mathematics, (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. doi: 10.2514/2.2013. Google Scholar [25] Y. Sakawa and Y. Shindo, Optimal control of container cranes,, Automatica, 18 (1982), 257. 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, (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. doi: 10.1007/BF00940727. Google Scholar [28] V. Veliov, On the time-discretization of control systems,, SIAM J. Control Optim., 35 (1997), 1470. 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. 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, 34 (2011), 271. 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, (2001), 69. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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, (2002). Google Scholar [12] W. W. Hager, Runge-Kutta methods in optimal control and the transformed adjoint system,, Numer. Math., 87 (2000), 247. 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. doi: 10.1137/1037043. Google Scholar [14] S. Jain, Multiresolution Strategies for the Numerical Solution of Optimal Control Problems,, Ph.D thesis, (2008). Google Scholar [15] C. Y. Kaya, Inexact restoration for Runge-Kutta discretization of optimal control,, SIAM J. Numer. Anal., 48 (2010), 1492. 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. 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, (2004), 405. 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), (1998), 253. 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. 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. 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], (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. doi: 10.1023/A:1021742204850. Google Scholar [23] S. Repin, A Posteriori Estimates For Partial Differential Equations,, Radon Series on Computational and Applied Mathematics, (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. doi: 10.2514/2.2013. Google Scholar [25] Y. Sakawa and Y. Shindo, Optimal control of container cranes,, Automatica, 18 (1982), 257. 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, (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. doi: 10.1007/BF00940727. Google Scholar [28] V. Veliov, On the time-discretization of control systems,, SIAM J. Control Optim., 35 (1997), 1470. 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. 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, 34 (2011), 271. 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 - A, 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 - A, 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 - A, 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] 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 [10] 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 [11] 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 [12] 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 [13] 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 [14] 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 [15] 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 [16] 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 [17] 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 [18] Theodore Tachim-Medjo. Optimal control of a two-phase flow model with state constraints. Mathematical Control & Related Fields, 2016, 6 (2) : 335-362. doi: 10.3934/mcrf.2016006 [19] Vincenzo Basco, Piermarco Cannarsa, Hélène Frankowska. Necessary conditions for infinite horizon optimal control problems with state constraints. Mathematical Control & Related Fields, 2018, 8 (3&4) : 535-555. doi: 10.3934/mcrf.2018022 [20] 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

2018 Impact Factor: 1.025

## Metrics

• HTML views (0)
• Cited by (1)

• on AIMS