×

Numerical solution of optimal control problems with explicit and implicit switches. (English) Zbl 1458.49024

Summary: In this article, we present a unified framework for the numerical solution of optimal control problems (OCPs) constrained by ordinary differential equations with both implicit and explicit switches. We present the problem class and qualify different types of implicitly switched systems. This classification significantly affects opportunities for solving such problems numerically. By using techniques from generalized disjunctive programming, we transform the problem into a counterpart one wherein discontinuities no longer appear implicitly. Instead, the new problem contains discrete decision variables and vanishing constraints. Recent results from the field of mixed-integer optimal control theory enable us to omit integrality constraints on variables, and allow to solve a relaxed OCP. We use a ‘first discretize, then optimize’ approach to solve the problem numerically. A direct method based on adaptive collocation is used for the discretization. The resulting finite dimensional optimization problems are mathematical programs with vanishing constraints, and we discuss numerical techniques to solve sequences of this challenging problem class. To demonstrate the efficacy and merit of our proposed approach, we investigate three benchmark problems for hybrid dynamic systems.

MSC:

49M25 Discrete approximations in optimal control

Software:

SNOPT
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achtziger, W.; Kanzow, C., Mathematical programs with vanishing constraints: Optimality conditions and constraint qualifications, Math. Program. Ser. A, 114, 69-99 (2008) · Zbl 1151.90046 · doi:10.1007/s10107-006-0083-3
[2] Allgor, R. J.; Barton, P. I., Mixed-integer dynamic optimization. I—Problem formulation, Comput. Chem. Eng., 23, 4, 567-584 (1999) · doi:10.1016/S0098-1354(98)00294-4
[3] Antsaklis, P. and Koutsoukos, X., On hybrid control of complex systems: A survey, 3rd International Conference ADMP’98, Automation of Mixed Processes: Dynamic Hybrid Systems, Reims, France, March 1998, pp. 1-8.
[4] Balas, E., Disjunctive programming and a hierarchy of relaxations for discrete optimization problems, SIAM J. Algebr. Discr. Methods, 6, 3, 466-486 (1985) · Zbl 0592.90070 · doi:10.1137/0606047
[5] Bansal, V.; Sakizlis, V.; Ross, R.; Perkins, J. D.; Pistikopoulos, E. N., New algorithms for mixed-integer dynamic optimization, Comput. Chem. Eng., 27, 647-668 (2003) · doi:10.1016/S0098-1354(02)00261-2
[6] Baumrucker, B. T.; Biegler, L. T., MPEC strategies for optimization of a class of hybrid dynamic systems, J. Process Control, 19, 8, 1248-1256 (2009) · doi:10.1016/j.jprocont.2009.02.006
[7] Bemporad, A., Borrelli, F., and Morari, M., Piecewise linear optimal controllers for hybrid systems, Proceedings of the 2000 American Control Conference. ACC (IEEE Cat. No.00CH36334), Chicago, Illinois, USA, Vol. 2, 2000, pp. 1190-1194.
[8] Bemporad, A.; Ferraritrecate, G.; Morari, M., Observability and controllability of piecewise affine and hybrid systems, IEEE Trans. Automat. Control, 45, 1864-1876 (1999) · Zbl 0990.93010 · doi:10.1109/TAC.2000.880987
[9] Bemporad, A.; Morari, M., Control of systems integrating logic, dynamics, and constraints, Automatica, 35, 3, 407-427 (1999) · Zbl 1049.93514 · doi:10.1016/S0005-1098(98)00178-2
[10] Bengea, S. C.; Decarlo, R. A., Optimal control of switching systems, Automatica, 41, 1, 11-27 (2005) · Zbl 1088.49018
[11] Biegler, L. T., Solution of dynamic optimization problems by successive quadratic programming and orthogonal collocation, Comput. Chem. Eng., 8, 243-248 (1984) · doi:10.1016/0098-1354(84)87012-X
[12] Bock, H.G., Randwertproblemmethoden zur Parameteridentifizierung in Systemen nichtlinearer Differentialgleichungen, Bonner Mathematische Schriften Vol. 183, Universität Bonn, Bonn, 1987. · Zbl 0622.65064
[13] Bock, H.G. and Plitt, K.J., A multiple shooting algorithm for direct solution of optimal control problems, Proceedings of the 9th IFAC World Congress (Budapest), Pergamon Press, Budapest, Hungary, 1984, pp. 242-247.
[14] Borrelli, F., Baotić, M., Bemporad, A., and Morari, M., An efficient algorithm for computing the state feedback optimal control law for discrete time hybrid systems, Proceedings of the 2003 American Control Conference, 2003, Vol. 6, Denver, Colorado, USA, pp. 4717-4722.
[15] Borrelli, F.; Baotić, M.; Bemporad, A.; Morari, M., Dynamic programming for constrained optimal control of discrete-time linear hybrid systems, Automatica, 41, 1709-1721 (2005) · Zbl 1125.49310 · doi:10.1016/j.automatica.2005.04.017
[16] Brandt-Pollmann, U., Numerical solution of optimal control problems with implicitly defined discontinuities with applications in engineering, Ph.D. thesis, Universität Heidelberg, 2004. · Zbl 1060.65066
[17] Branicky, M. S.; Borkar, V. S.; Mitter, S. K., A unified framework for hybrid control: Model and optimal control, IEEE Trans. Automat. Control, 43, 1, 31-45 (1998) · Zbl 0951.93002 · doi:10.1109/9.654885
[18] Christiansen, B., Maurer, H., and Zirn, O., Optimal control of a voice-coil-motor with coulombic friction, Proceedings of the IEEE Conference on Decision and Control, Cancun, Mexico, 2008, pp. 1557-1562.
[19] Engell, S.; Frehse, G.; Schnieder, E., Modelling, Analysis and Design of Hybrid Systems (2003), Springer, Berlin Heidelberg
[20] Filippov, A. F., Differential equations with discontinuous right hand side, AMS Transl., 42, 199-231 (1964) · Zbl 0148.33002
[21] Garg, D.; Patterson, M. A.; Hager, W. W.; Rao, A. V.; Benson, D. A.; Huntington, G. T., An overview of three pseudospectral methods for the numerical solution of optimal control problems, Adv. Astronaut. Sci., 135, 1, 475-487 (2009)
[22] Gerdts, M. and Sager, S., Mixed-integer DAE optimal control problems: Necessary conditions and bounds, in Control and Optimization with Differential-Algebraic Constraints, L. Biegler, S.L. Campbell, and V. Mehrmann, eds., SIAM, Philadelphia, PA, USA, 2012, pp. 189-212. · Zbl 1317.90323
[23] Gill, P. E.; Murray, W.; Saunders, M. A., SNOPT: An SQP algorithm for large-scale constrained optimization, SIAM J. Optim., 12, 979-1006 (2002) · Zbl 1027.90111 · doi:10.1137/S1052623499350013
[24] Goebel, R.; Sanfelice, R. G.; Teel, A., Hybrid dynamical systems, IEEE Control Syst. Mag., 29, 2, 28-93 (2009) · Zbl 1395.93001 · doi:10.1109/MCS.2008.931718
[25] Gonzalez, H., Vasudevan, R., Kamgarpour, M., Sastry, S.S., Bajcsy, R., and Tomlin, C.J., A descent algorithm for the optimal control of constrained nonlinear switched dynamical systems, Proceedings of the 13th International Conference on Hybrid Systems: Computation and Control, Stockholm, Sweden, 2010, pp. 51-60. · Zbl 1360.49023
[26] Gonzalez, H., Vasudevan, R., Kamgarpour, M., Sastry, S.S., Bajcsy, R., and Tomlin, C.J., A numerical method for the optimal control of switched systems, Proceedings of the 49th IEEE Conference on Decision and Control, Atlanta, GA, USA, 2010, pp. 7519-7526. · Zbl 1078.35051
[27] Guignard, M., Generalized Kuhn-Tucker conditions for mathematical programming problems in a Banach space, SIAM J. Control, 7, 2, 232-241 (1969) · Zbl 0182.53101 · doi:10.1137/0307016
[28] Hante, F. M.; Sager, S., Relaxation methods for mixed-integer optimal control of partial differential equations, Comput. Optim. Appl., 55, 1, 197-225 (2013) · Zbl 1272.49026 · doi:10.1007/s10589-012-9518-3
[29] Hedlund, S.; Rantzer, A., Convex dynamic programming for hybrid systems, IEEE Trans. Automat. Control, 47, 9, 1536-1540 (2002) · Zbl 1364.90338 · doi:10.1109/TAC.2002.802753
[30] Hiskens, I. A.; Pai, M. A., Trajectory sensitivity analysis of hybrid systems, IEEE Trans. Circuits Syst. I, Fundam. Theory Appl., 47, 2, 204-220 (2000) · doi:10.1109/81.828574
[31] Hoheisel, T., Mathematical programs with vanishing constraints, Ph.D. thesis, Julius-Maximilians-Universität Würzburg, 2009.
[32] Huntington, G.T., Benson, D., and Rao, A.V., A comparison of accuracy and computational efficiency of three pseudospectral methods, Proceedings of the AIAA Guidance, Navigation, and Control Conference, Hilton Head, South Carolina, 2007, pp. 840-864.
[33] Imura, J.; Van Der Schaft, A., Characterization of well-posedness of piecewise-linear systems, IEEE Trans. Automat. Control, 45, 9, 1600-1619 (2000) · Zbl 0978.34012 · doi:10.1109/9.880612
[34] Jung, M., Kirches, C., and Sager, S., On perspective functions and vanishing constraints in mixed-integer nonlinear optimal control, in Facets of Combinatorial Optimization—Festschrift for Martin Grötschel, M. Jünger and G. Reinelt, eds., Springer, Berlin Heidelberg, 2013, pp. 387-417. · Zbl 1320.49011
[35] Kerrigan, E.C. and Mayne, D.Q., Optimal control of constrained, piecewise affine systems with bounded disturbances, Proc. 41th IEEE Conf. on Decision and Control, Las Vegas, NV, USA, 2002, pp. 1552-1557.
[36] Kirches, C., A numerical method for nonlinear robust optimal control with implicit discontinuities and an application to powertrain oscillations, Diploma thesis, Heidelberg University, 2006.
[37] Kirches, C.; Potschka, A.; Bock, H. G.; Sager, S., A parametric active set method for a subclass of quadratic programs with vanishing constraints, Pac. J. Optim., 9, 2, 275-299 (2013) · Zbl 1270.90042
[38] Leine, R. I.; Van Campen, D. H.; Van De Vrande, B. L., Bifurcations in nonlinear discontinuous systems, Nonlinear Dyn., 23, 2, 105-164 (2000) · Zbl 0980.70018 · doi:10.1023/A:1008384928636
[39] Leine, R.I., Bifurcations in discontinuous mechanical systems of filippov-type, Ph.D. thesis, Techn. Univ. Eindhoven, The Netherlands, 2000.
[40] Leine, R. I.; Van Campen, D. H.; De Kraker, A.; Van Den Steen, L., Stick-slip vibrations induced by alternate friction models, Nonlinear Dyn., 16, 1, 41-54 (1998) · Zbl 0908.70021 · doi:10.1023/A:1008289604683
[41] Lenders, F., Numerical methods for mixed-integer optimal control with combinatorial constraints
[42] Loxton, R. C.; Teo, K. L.; Rehbock, V., Optimal control problems with multiple characteristic time points in the objective and constraints, Automatica, 44, 11, 2923-2929 (2008) · Zbl 1160.49033 · doi:10.1016/j.automatica.2008.04.011
[43] Mangasarian, O. L.; Fromovitz, S., Fritz John necessary optimality conditions in the presence of equality and inequality constraints, J. Math. Anal. Appl., 17, 37-47 (1967) · Zbl 0149.16701 · doi:10.1016/0022-247X(67)90163-1
[44] Martin, R. B., Optimal control drug scheduling of cancer chemotherapy, Automatica, 28, 6, 1113-1123 (1992) · doi:10.1016/0005-1098(92)90054-J
[45] Mohideen, M. J.; Perkins, J. D.; Pistikopoulos, E. N., Towards an efficient numerical procedure for mixed integer optimal control, Comput. Chem. Eng., 21, S457-S462 (1997) · doi:10.1016/S0098-1354(97)87544-8
[46] Mombaur, K.D., Stability optimization of open-loop controlled walking robots, Ph.D. thesis, Universität Heidelberg, 2001. · Zbl 0986.93003
[47] Piccoli, B., Necessary conditions for hybrid optimization, Proceedings of the 38th IEEE Conference on Decision and Control, 1999, Vol. 1, Phoenix, Arizona, USA, pp. 410-415.
[48] Raman, R.; Grossmann, I. E., Modelling and computational techniques for logic based integer programming, Comput. Chem. Eng., 18, 7, 563-578 (1994) · doi:10.1016/0098-1354(93)E0010-7
[49] Roll, J.; Bemporad, A.; Ljung, L., Identification of piecewise affine systems via mixed-integer programming, Automatica, 40, 1, 37-50 (2004) · Zbl 1037.93023 · doi:10.1016/j.automatica.2003.08.006
[50] Saccon, A., Wouw, N.V.D., and Nijmeijer, H., Sensitivity analysis of hybrid systems with state jumps with application to trajectory tracking, IEEE Conference on Decision and Control, Los Angeles, California, USA, Vol. 27, 2014, pp. 3065-3070.
[51] Sager, S., Numerical methods for mixed-integer optimal control problems, Ph.D. thesis, Universität Heidelberg, 2006. · Zbl 1094.65512
[52] Sager, S.; Bock, H. G.; Diehl, M., The integer approximation error in mixed-integer optimal control, Math. Program. A, 133, 12, 1-23 (2012) · Zbl 1259.90077 · doi:10.1007/s10107-010-0405-3
[53] Sager, S.; Reinelt, G.; Bock, H. G., Direct methods with maximal lower bound for mixed-integer optimal control problems, Math. Program., 118, 1, 109-149 (2009) · Zbl 1160.49032 · doi:10.1007/s10107-007-0185-6
[54] Scholtes, S., Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM J. Optim., 11, 918-936 (2001) · Zbl 1010.90086 · doi:10.1137/S1052623499361233
[55] Von Stryk, O. and Glocker, M., Decomposition of mixed-integer optimal control problems using branch and bound and sparse direct collocation, Proc. ADPM 2000—The 4th International Conference on Automatisation of Mixed Processes: Hybrid Dynamical Systems, Dortmund, Germany, 2000, pp. 99-104.
[56] Sussmann, H.J., A maximum principle for hybrid optimal control problems, Conference proceedings of the 38th IEEE Conference on Decision and Control (Phoenix), Phoenix, Arizona, USA, 1999.
[57] Tabuada, P., Verification and Control of Hybrid Systems: A Symbolic Approach (2009), Springer Science & Business Media, Springer, Boston, MA, USA · Zbl 1195.93001
[58] Wei, S.; Uthaichana, K.; Žefran, M.; Decarlo, R. A.; Bengea, S., Applications of numerical optimal control to nonlinear hybrid systems, Nonlinear Anal. Hybrid Syst., 1, 2, 264-279 (2007) · Zbl 1165.90650 · doi:10.1016/j.nahs.2006.10.007
[59] Woon, S. F.; Rehbock, V.; Loxton, R., Towards global solutions of optimal discrete-valued control problems, Optim. Control Appl. Methods, 33, 5, 576-594 (2012) · Zbl 1275.49057 · doi:10.1002/oca.1015
[60] Xu, X.; Antsaklis, P. J., Results and Perspectives on Computational Methods for Optimal Control of Switched Systems, 540-555 (2003), Springer: Springer, Berlin, Heidelberg · Zbl 1038.49034
[61] Xu, X.; Antsaklis, P. J., Optimal control of switched systems based on parameterization of the switching instants, IEEE Trans. Automat. Control, 49, 1, 2-16 (2004) · Zbl 1365.93308 · doi:10.1109/TAC.2003.821417
[62] Zhu, F.; Antsaklis, P. J., Optimal control of hybrid switched systems: A brief survey, Discrete Event Dyn. Syst., 25, 3, 345-364 (2015) · Zbl 1328.93137 · doi:10.1007/s10626-014-0187-5
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.