×

A shooting algorithm for optimal control problems with singular Arcs. (English) Zbl 1275.49045

The authors investigate a shooting algorithm for the optimal control problem \(\varphi_0(x_0,x_T) \to \min\), \(\dot{x}_t=\sum_{i=0}^m u_{i,t} f_i(x_t)\) a.e. on \([0,T]\), \(\eta_j(x_0,x_T)=0\), \(j=1,\dots,d\), where the final time \(T\) is fixed, \(f_i: R^n \to R^n\) for \(i=0, \dots,m\) and \(\eta_j:R^{2n} \to R\) for \(j=1,\dots,d\). The functions \(\varphi_0\), \(f_i\), and \(\eta_j\) have Lipschitz-continuous second derivatives. In general, the shooting system has more equations than unknowns, and the Gauss-Newton method is used to compute a zero of the shooting system. This shooting algorithm is locally quadratically convergent, if the derivative of the shooting function is one-to-one at the solution. The main result of the paper asserts that the latter holds whenever a sufficient condition for weak optimality is satisfied. Numerical tests that validate the proposed method are included.

MSC:

49M15 Newton-type methods
49K40 Sensitivity, stability, well-posedness
49K30 Optimality conditions for solutions belonging to restricted classes (Lipschitz controls, bang-bang controls, etc.)

Software:

Shoot; Cotcot; minpack; Bocop
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Goodman, T.R., Lance, G.N.: The numerical integration of two-point boundary value problems. Math. Tables Other Aids Comput. 10, 82-86 (1956) · Zbl 0071.34006 · doi:10.2307/2002181
[2] Morrison, D.D., Riley, J.D., Zancanaro, J.F.: Multiple shooting method for two-point boundary value problems. Commun. ACM 5, 613-614 (1962) · Zbl 0106.31903 · doi:10.1145/355580.369128
[3] Keller, H.B.: Numerical Methods for Two-Point Boundary-Value Problems. Ginn-Blaisdell, Waltham (1968) · Zbl 0172.19503
[4] Bulirsch, R.: Die Mehrzielmethode zur numerischen Lösung von nichtlinearen Randwertproblemen und Aufgaben der optimalen Steuerung. Technical report, Carl-Cranz-Gesellschaft, Deutsches Zentrum für Luft- und Raumfahrt (DLR), Oberpfaffenhofen, Germany (1971)
[5] Maurer, H.: Numerical solution of singular control problems using multiple shooting techniques. J. Optim. Theory Appl. 18(2), 235-257 (1976) · Zbl 0302.65063 · doi:10.1007/BF00935706
[6] Oberle, H.J.: Numerische Behandlung singulärer Steuerungen mit der Mehrzielmethode am Beispiel der Klimatisierung von Sonnenhäusern. Ph.D. thesis, Technische Universität München (1977) · Zbl 0396.49021
[7] Oberle, H.J.: Numerical computation of singular control problems with application to optimal heating and cooling by solar energy. Appl. Math. Optim. 5(4), 297-314 (1979) · Zbl 0428.49007 · doi:10.1007/BF01442560
[8] Fraser-Andrews, G.: Finding candidate singular optimal controls: a state-of-the-art survey. J. Optim. Theory Appl. 60(2), 173-190 (1989) · Zbl 0633.49015 · doi:10.1007/BF00940004
[9] Martinon, P.: Numerical resolution of optimal control problems by a piecewise linear continuation method. Ph.D. thesis, Institut National Polytechnique de Toulouse (2005). Online: http://www.cmap.polytechnique.fr/ martinon/docs/Martinon-Thesis.pdf
[10] Vossen, G.: Switching time optimization for bang-bang and singular controls. J. Optim. Theory Appl. 144(2), 409-429 (2010) · Zbl 1185.49022 · doi:10.1007/s10957-009-9594-4
[11] Aronna, M.S.: Singular solutions in optimal control: second order conditions and a shooting algorithm. Research report Nr. 7764, INRIA (2011)
[12] Bonnard, B., Kupka, I.: Théorie des singularités de l’application entrée/sortie et optimalité des trajectoires singulières dans le problème du temps minimal. Forum Math. 5(2), 111-159 (1993) · Zbl 0779.49025
[13] Bonnard, B., Caillau, J.B., Trélat, E.: Second order optimality conditions in the smooth case and applications in optimal control. ESAIM Control Optim. Calc. Var. 13(2), 207-236 (2007) (electronic) · Zbl 1123.49014 · doi:10.1051/cocv:2007012
[14] Bonnard, B., Chyba, M.: Singular Trajectories and Their Role in Control Theory. Mathematics & Applications, vol. 40. Springer, Berlin (2003) · Zbl 1022.93003
[15] Malanowski, K., Maurer, H.: Sensitivity analysis for parametric control problems with control-state constraints. Comput. Optim. Appl. 5, 253-283 (1996) · Zbl 0864.49020 · doi:10.1007/BF00248267
[16] Bonnans, J.F., Hermant, A.: Second-order analysis for optimal control problems with pure state constraints and mixed control-state constraints. Annals of I.H.P. Nonlinear Anal. 26, 561-598 (2009) · Zbl 1158.49023
[17] Dennis, J. E.; Jacobs, D. (ed.), Nonlinear least-squares, 269-312 (1977), London
[18] Fletcher, R., Practical methods of optimization, No. 1 (1980), Chichester · Zbl 0439.93001
[19] Dennis, J.E., Gay, D.M., Welsch, R.E.: An adaptive nonlinear least-squares algorithm. ACM Trans. Math. Softw. 7, 348-368 (1981) · Zbl 0464.65040 · doi:10.1145/355958.355965
[20] Dmitruk, A.V.: Quadratic weak minimum conditions for special situations in optimal control problems. Dokl. Akad. Nauk SSSR 233(4), 523-526 (1977)
[21] Dmitruk, A.V.: Quadratic order conditions for a Pontryagin minimum in an optimal control problem linear in the control. Math. USSR, Izv. 28, 275-303 (1987) · Zbl 0682.49020 · doi:10.1070/IM1987v028n02ABEH000882
[22] Felgenhauer, U.: Structural stability investigation of bang-singular-bang optimal controls. J. Optim. Theory Appl. 152(3), 605-631 (2012) · Zbl 1237.49033 · doi:10.1007/s10957-011-9925-0
[23] Felgenhauer, U.: Controllability and stability for problems with bang-singular-bang optimal control (2011, submitted)
[24] Pontryagin, L., Boltyanski, V., Gamkrelidze, R., Michtchenko, E.: The Mathematical Theory of Optimal Processes. Wiley-Interscience, New York (1962) · Zbl 0102.32001
[25] Kelley, H.J.: A second variation test for singular extremals. AIAA J. 2, 1380-1382 (1964) · Zbl 0136.10101 · doi:10.2514/3.2562
[26] Goh, B.S.: The second variation for the singular Bolza problem. SIAM J. Control 4(2), 309-325 (1966) · Zbl 0146.11906 · doi:10.1137/0304026
[27] Goh, B.S.: Necessary conditions for singular extremals involving multiple control variables. SIAM J. Control 4, 716-731 (1966) · Zbl 0161.29004 · doi:10.1137/0304052
[28] Goh, B.S.: Necessary conditions for the singular extremals in the calculus of variations. Ph.D. thesis, University of Canterbury, New Zealand (1966)
[29] Kelley, H. J.; Kopp, R. E.; Moyer, H. G., Singular extremals, 63-101 (1967), New York · doi:10.1016/S0076-5392(09)60039-4
[30] Robbins, H.M.: A generalized Legendre-Clebsch condition for the singular case of optimal control. IBM J. Res. Dev. 11, 361-372 (1967) · Zbl 0153.41202 · doi:10.1147/rd.114.0361
[31] Bonnans, J.F.: Optimisation Continue. Dunod (2006)
[32] Levitin, E.S., Milyutin, A.A., Osmolovskiĭ, N.P.: Higher order conditions for local minima in problems with constraints. Usp. Mat. Nauk 33(6(204)), 85-148 (1978). 272 · Zbl 0409.49016
[33] Aronna, M.S., Bonnans, J.F., Dmitruk, A.V., Lotito, P.A.: Quadratic order conditions for bang-singular extremals. Numer. Algebra Control Optim. 2(3), 511-546 (2012). Special issue dedicated to Professor Helmut Maurer on the occasion of his 65th birthday · Zbl 1252.49028 · doi:10.3934/naco.2012.2.511
[34] Bell, D.J., Jacobson, D.H.: Singular Optimal Control Problems. Academic Press, New York (1975) · Zbl 0338.49006
[35] Zeidan, V.: Sufficiency criteria via focal points and via coupled points. SIAM J. Control Optim. 30(1), 82-98 (1992) · Zbl 0780.49018 · doi:10.1137/0330006
[36] Bonnard, B., Caillau, J.-B., Trélat, E.: Cotcot: Short reference manual. Technical report RT/APO/05/1, ENSEEIHT-IRIT, (2005) · Zbl 1185.49022
[37] Fuller, A.T.: Study of an optimum non-linear control system. J. Electron. Control 15, 63-71 (1963) · doi:10.1080/00207216308937555
[38] Betts, J.T.: Survey of numerical methods for trajectory optimization. AIAA J. Guid. Control Dyn. 21, 193-207 (1998) · Zbl 1158.49303 · doi:10.2514/2.4231
[39] Biegler, L. T., Nonlinear programming: concepts, algorithms, and applications to chemical processes (2010), Philadelphia · Zbl 1207.90004
[40] Gergaud, J.; Martinon, P.; Seeger, A. (ed.), An application of PL continuation methods to singular arcs problems, No. 563, 163-186 (2006), Berlin · Zbl 1108.49026 · doi:10.1007/3-540-28258-0_11
[41] Bonnans, J.F., Martinon, P., Trélat, E.: Singular arcs in the generalized Goddard’s problem. J. Optim. Theory Appl. 139(2), 439-461 (2008) · Zbl 1159.49027 · doi:10.1007/s10957-008-9387-1
[42] Clark, C.W.: Mathematical Bioeconomics. Wiley, New York (1976) · Zbl 0364.90002
[43] Aly, G.M.: The computation of optimal singular control. Int. J. Control 28(5), 681-688 (1978) · Zbl 0396.49021 · doi:10.1080/00207177808922489
[44] Goddard, R. H., A method of reaching extreme altitudes, No. 71 (1919), Washington
[45] Seywald, H., Cliff, E.M.: Goddard problem in presence of a dynamic pressure limit. J. Guid. Control Dyn. 16(4), 776-781 (1993) · Zbl 0779.70020 · doi:10.2514/3.21080
[46] Martinon, P., Gergaud, J.: Shoot2.0: An indirect grid shooting package for optimal control problems, with switching handling and embedded continuation. Research report Nr. 7380, INRIA, (2011)
[47] Garbow, B.S., Hillstrom, K.E., More, J.J.: User Guide for Minpack-1. National Argonne Laboratory, Illinois (1980)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.