Abstract
In this paper we are concerned with the optimal control problem consisting in minimizing the time for reaching (visiting) a fixed number of target sets, in particular more than one target. Such a problem is of course reminiscent of the famous “Traveling Salesman Problem” and brings all its computational difficulties. Our aim is to apply the dynamic programming technique in order to characterize the value function of the problem as the unique viscosity solution of a suitable Hamilton–Jacobi equation. We introduce some “external” variables, one per target, which keep in memory whether the corresponding target is already visited or not, and we transform the visiting problem in a suitable Mayer problem. This fact allows us to overcome the lacking of the Dynamic Programming Principle for the originary problem. The external variables evolve with a hysteresis law and the Hamilton–Jacobi equation turns out to be discontinuous
Similar content being viewed by others
References
Bagagiolo, F.: Dynamic programming for some optimal control problems with hysteresis. Nonlinear Differ. Equ. Appl. 9, 149–174 (2002)
Bagagiolo, F.: Viscosity solutions for an optimal control problem with Preisach hysteresis nonlinearities. ESAIM Control Optim. Calc. Var. 10, 271–294 (2004)
Bardi, M., Capuzzo Dolcetta, I.: Optimal Control and Viscosity Solution of Hamilton–Jacobi–Bellman Equation. Birkhäuser, Boston (1997)
Bellman, R.: Dynamic programming treatment of the travelling salesman problem. J. ACM 9, 61–63 (1962)
Benetton, M.: Su di un problema di visita ottima. Master Thesis in Mathematics, University of Trento, July 2010
Crandall, M.G., Lions, P.L.: Viscosity solutions of Hamilton–Jacobi equations. Trans. Am. Math. Soc. 277, 1–42 (1983)
Crandall, M.G., Evans, L.C., Lions, P.L.: Some properties of viscosity solutions of Hamilton–Jacobi equations. Trans. Am. Math. Soc. 282, 487–502 (1984)
Day, M.V.: Neumann-type boundary conditions for Hamilton–Jacobi equations in smooth domains. Appl. Math. Optim. 53, 359–381 (2006)
Gudovich, A., Quincampoix, M.: Optimal control with hysteresis nonlinearity and multidimensional play operator. SIAM J. Control Optim. 42, 788–807 (2011)
Ilchmann, A., Logemann, H., Ryan, E.P.: Tracking with prescribed transient performance for hysteretic systems. SIAM J. Control Optim. 48, 4731–4752 (2010)
Ishii, H.: A boundary value problem of the Dirichlet type for the Hamilton–Jacobi equations. Ann. Sc. Norm. Super. Pisa, Cl. Sci. 16, 105–135 (1989)
Lions, P.L.: Neumann type boundary conditions for Hamilton–Jacobi equations. Duke Math. J. 52, 793–820 (1985)
Soner, H.M.: Optimal control with state-space constraint. SIAM J. Control Optim. 24, 552–561 (1983)
Visintin, A.: Differential Models of Hysteresis. Springer, Heidelberg (1994)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bagagiolo, F., Benetton, M. About an Optimal Visiting Problem. Appl Math Optim 65, 31–51 (2012). https://doi.org/10.1007/s00245-011-9150-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00245-011-9150-0