Inexact restoration and adaptive mesh refinement for optimal control

Nahid Banihashemi; C. Yalçın Kaya

doi:10.3934/jimo.2014.10.521

Article Contents

2014, Volume 10, Issue 2: 521-542. Doi: 10.3934/jimo.2014.10.521

This issue Previous Article On an optimal control problem in laser cutting with mixed finite-/infinite-dimensional constraints Next Article Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems

Inexact restoration and adaptive mesh refinement for optimal control

Nahid Banihashemi^1, and
C. Yalçın Kaya^2,

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

Received: August 31, 2012

Revised: July 31, 2013

Published: March 2014

Abstract Related Papers Cited by

Abstract

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.

Keywords:

State- and control-constrained optimal control,
inexact restoration,
Euler discretization,
adaptive mesh refinement,
container crane.

Mathematics Subject Classification: Primary: 49K15, 49M05, 49M25; Secondary: 65K10.

Citation:

Related Papers

Cited by

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.