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

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

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

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

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

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

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

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

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

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

[11]

R. Fourer, D. M. Gay and B. W. Kernighan, AMPL: A Modelling Language for Mathematical Programming,, $ 2^{nd}$ edition, (2002).

[12]

W. W. Hager, Runge-Kutta methods in optimal control and the transformed adjoint system,, Numer. Math., 87 (2000), 247. 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. doi: 10.1137/1037043.

[14]

S. Jain, Multiresolution Strategies for the Numerical Solution of Optimal Control Problems,, Ph.D thesis, (2008).

[15]

C. Y. Kaya, Inexact restoration for Runge-Kutta discretization of optimal control,, SIAM J. Numer. Anal., 48 (2010), 1492. 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. 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, (2004), 405.

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

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

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

[21]

B. S. Mordukhovich, Variational Analysis and Generalized Differentiation. II. Applications,, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], (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. doi: 10.1023/A:1021742204850.

[23]

S. Repin, A Posteriori Estimates For Partial Differential Equations,, Radon Series on Computational and Applied Mathematics, (2008). doi: 10.1515/9783110203042.

[24]

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

[25]

Y. Sakawa and Y. Shindo, Optimal control of container cranes,, Automatica, 18 (1982), 257. 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, (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. doi: 10.1007/BF00940727.

[28]

V. Veliov, On the time-discretization of control systems,, SIAM J. Control Optim., 35 (1997), 1470. 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. 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, 34 (2011), 271. 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, (2001), 69.

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

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

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

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

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

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

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

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

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

[11]

R. Fourer, D. M. Gay and B. W. Kernighan, AMPL: A Modelling Language for Mathematical Programming,, $ 2^{nd}$ edition, (2002).

[12]

W. W. Hager, Runge-Kutta methods in optimal control and the transformed adjoint system,, Numer. Math., 87 (2000), 247. 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. doi: 10.1137/1037043.

[14]

S. Jain, Multiresolution Strategies for the Numerical Solution of Optimal Control Problems,, Ph.D thesis, (2008).

[15]

C. Y. Kaya, Inexact restoration for Runge-Kutta discretization of optimal control,, SIAM J. Numer. Anal., 48 (2010), 1492. 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. 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, (2004), 405.

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

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

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

[21]

B. S. Mordukhovich, Variational Analysis and Generalized Differentiation. II. Applications,, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], (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. doi: 10.1023/A:1021742204850.

[23]

S. Repin, A Posteriori Estimates For Partial Differential Equations,, Radon Series on Computational and Applied Mathematics, (2008). doi: 10.1515/9783110203042.

[24]

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

[25]

Y. Sakawa and Y. Shindo, Optimal control of container cranes,, Automatica, 18 (1982), 257. 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, (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. doi: 10.1007/BF00940727.

[28]

V. Veliov, On the time-discretization of control systems,, SIAM J. Control Optim., 35 (1997), 1470. 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. 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, 34 (2011), 271. 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 & 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]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

Stepan Sorokin, Maxim Staritsyn. Feedback necessary optimality conditions for a class of terminally constrained state-linear variational problems inspired by impulsive control. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 201-210. doi: 10.3934/naco.2017014

[20]

Matthias Gerdts, Martin Kunkel. A nonsmooth Newton's method for discretized optimal control problems with state and control constraints. Journal of Industrial & Management Optimization, 2008, 4 (2) : 247-270. doi: 10.3934/jimo.2008.4.247

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (5)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]