• 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, (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]

Guirong Jiang, Qishao Lu. The dynamics of a Prey-Predator model with impulsive state feedback control. Discrete & Continuous Dynamical Systems - B, 2006, 6 (6) : 1301-1320. doi: 10.3934/dcdsb.2006.6.1301

[2]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437

[3]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183

[4]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[5]

Xiaohong Li, Mingxin Sun, Zhaohua Gong, Enmin Feng. Multistage optimal control for microbial fed-batch fermentation process. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021040

[6]

John T. Betts, Stephen Campbell, Claire Digirolamo. Examination of solving optimal control problems with delays using GPOPS-Ⅱ. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 283-305. doi: 10.3934/naco.2020026

[7]

Shanjian Tang, Fu Zhang. Path-dependent optimal stochastic control and viscosity solution of associated Bellman equations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (11) : 5521-5553. doi: 10.3934/dcds.2015.35.5521

[8]

Yves Dumont, Frederic Chiroleu. Vector control for the Chikungunya disease. Mathematical Biosciences & Engineering, 2010, 7 (2) : 313-345. doi: 10.3934/mbe.2010.7.313

[9]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[10]

Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329

[11]

A. K. Misra, Anupama Sharma, Jia Li. A mathematical model for control of vector borne diseases through media campaigns. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1909-1927. doi: 10.3934/dcdsb.2013.18.1909

[12]

Peter Benner, Jens Saak, M. Monir Uddin. Balancing based model reduction for structured index-2 unstable descriptor systems with application to flow control. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 1-20. doi: 10.3934/naco.2016.6.1

[13]

Wolf-Jüergen Beyn, Janosch Rieger. The implicit Euler scheme for one-sided Lipschitz differential inclusions. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 409-428. doi: 10.3934/dcdsb.2010.14.409

[14]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[15]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327

[16]

Yunfei Lv, Rong Yuan, Yuan He. Wavefronts of a stage structured model with state--dependent delay. Discrete & Continuous Dynamical Systems - A, 2015, 35 (10) : 4931-4954. doi: 10.3934/dcds.2015.35.4931

[17]

Daoyuan Fang, Ting Zhang. Compressible Navier-Stokes equations with vacuum state in one dimension. Communications on Pure & Applied Analysis, 2004, 3 (4) : 675-694. doi: 10.3934/cpaa.2004.3.675

[18]

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321

[19]

Murat Uzunca, Ayşe Sarıaydın-Filibelioǧlu. Adaptive discontinuous galerkin finite elements for advective Allen-Cahn equation. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 269-281. doi: 10.3934/naco.2020025

[20]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]