A sequentially optimal randomized algorithm for robust feasibility problems

[ES] En este trabajo (del cual se presentó una versión preliminar en Alamo et al. (2007)) se propone un algoritmo aleatorio para determinar la factibilidad robusta de un conjunto de desigualdades lineales matriciales (Linear Matrix Inequalities, LMI). El algoritmo está basado en la solución de una secuencia de problemas de optimización semidefinida sujetos a un bajo número de restricciones. Se aporta además una cota superior del número máximo de iteraciones que requiere el algoritmo para resolver el problema de factibilidad robusta. Finalmente, los resultados se ilustran mediante un ejemplo numérico.[EN] This paper proposes a randomized algorithm for feasibility of uncertain LMIs. The algorithm is based on the solution of a sequence of semidefinite optimization problems involving a reduced number of constraints. A bound of the maximum number of iterations required by the algorithm is given. Finally, the performance and behaviour of the algorithm are illustrated by means of a numerical example.Los autores agradecen la financiacion del Ministerio de Ciencia e Innovación mediante el proyecto DPI2010-21589-C05-01.Álamo, T.; Tempo, R.; Ramírez, D.; Luque, A.; Camacho, E. (2013). Un algoritmo secuencial, aleatorio y óptimo para problemas de factibilidad robusta. Revista Iberoamericana de Automática e Informática industrial. 10(1):50-61. https://doi.org/10.1016/j.riai.2012.11.0055061101Alamo, T., Tempo, R., & Camacho, E. F. (2009). Randomized Strategies for Probabilistic Solutions of Uncertain Feasibility and Optimization Problems. IEEE Transactions on Automatic Control, 54(11), 2545-2559. doi:10.1109/tac.2009.2031207Alamo, T., Tempo, R., Ramírez, D. R., & Camacho, E. F. (2008). A new vertex result for robustness problems with interval matrix uncertainty. Systems & Control Letters, 57(6), 474-481. doi:10.1016/j.sysconle.2007.11.003Alamo, T., Tempo, R., Ramirez, D.R., Camacho, E.F., 2007. A sequentially optimal randomized algorithm for robust lmi feasibility problems. In: Proceedings of the European Control Conference. Kos, Greece.Apkarian, P., Gahinet, P., Becker, G., 1995. Self-scheduled H∞ control of linear parameter-varying systems: a design example. Automatica 31 (9), 1251-1261. DOI: DOI: 10.1016/0005-1098(95)00038-X.Apkarian, P., Tuan, H.D., 2000. Parameterized lmis in control theory. SIAM Journal on Control and Optimization 38 (4), 1241-1264. DOI: 10.1137/S036301299732612X.Barmish, B., 1994. New Tools for Robustness of Linear Systems. MacMillan Publishing Company, New York, USA.Barmish, B., Scherbakov, P., December 2000. On avoiding vertexization of robustness problems: The approximate feasibility concept. In: Proceedings of the 39th IEEE Conference on Decision and Control. Sydney, Australia, pp. 1031-1036.Becker, G., Packard, A., 1994. Robust performance of linear parametrically varying systems using parametrically-dependent linear feedback. Systems and Control Letters 23 (3), 205-215. DOI: 10.1016/0167-6911(94)90006-X.Ben-Tal, A., Nemirovski, A., 2001. Lectures on Modern Convex Optimization. Analysis, Algorithms, and Engineering Applications. MPS/SIAM Series on Optimization, Philadelphia, PA.Boyd, S., Ghaoui, L.E., Feron, E., Balakrishnan, V., 1994. Linear Matrix Inequalities in Systems and Control Theory. SIAM, Philadelphia, PA.Calafiore, G. C., & Campi, M. C. (2006). The Scenario Approach to Robust Control Design. IEEE Transactions on Automatic Control, 51(5), 742-753. doi:10.1109/tac.2006.875041Calafiore, G. C., & Dabbene, F. (2007). A probabilistic analytic center cutting plane method for feasibility of uncertain LMIs. Automatica, 43(12), 2022-2033. doi:10.1016/j.automatica.2007.04.003Calafiore, G., Dabbene, F., & Tempo, R. (2007). A survey of randomized algorithms for control synthesis and performance verification. Journal of Complexity, 23(3), 301-316. doi:10.1016/j.jco.2007.01.003Calafiore, G., & Polyak, B. T. (2001). Stochastic algorithms for exact and approximate feasibility of robust LMIs. IEEE Transactions on Automatic Control, 46(11), 1755-1759. doi:10.1109/9.964685Calafiore, G. C., Dabbene, F., & Tempo, R. (2011). Research on probabilistic methods for control system design. Automatica, 47(7), 1279-1293. doi:10.1016/j.automatica.2011.02.029Feron, E., Apkarian, P., & Gahinet, P. (1996). Analysis and synthesis of robust control systems via parameter-dependent Lyapunov functions. IEEE Transactions on Automatic Control, 41(7), 1041-1046. doi:10.1109/9.508913Fujisaki, Y., Dabbene, F., & Tempo, R. (2003). Probabilistic design of LPV control systems. Automatica, 39(8), 1323-1337. doi:10.1016/s0005-1098(03)00108-0Kanev, S., De Schutter, B., & Verhaegen, M. (2003). An ellipsoid algorithm for probabilistic robust controller design. Systems & Control Letters, 49(5), 365-375. doi:10.1016/s0167-6911(03)00115-4Liberzon, D., & Tempo, R. (2004). Common Lyapunov Functions and Gradient Algorithms. IEEE Transactions on Automatic Control, 49(6), 990-994. doi:10.1109/tac.2004.829632Nemirovskii, A. (1993). Several NP-hard problems arising in robust stability analysis. Mathematics of Control, Signals, and Systems, 6(2), 99-105. doi:10.1007/bf01211741Oishi, Y., December 2003. Probabilistic design of a robust state-feedback controller based on parameter-dependent Lyapunov functions. In: Proceedings of the 42nd IEEE Conference on Decision and Control. Maui, Hawaii USA, pp. 1920-1925.Polyak, B. T., & Tempo, R. (2001). Probabilistic robust design with linear quadratic regulators. Systems & Control Letters, 43(5), 343-353. doi:10.1016/s0167-6911(01)00117-7Scokaert, P. O. M., Mayne, D. Q., & Rawlings, J. B. (1999). Suboptimal model predictive control (feasibility implies stability). IEEE Transactions on Automatic Control, 44(3), 648-654. doi:10.1109/9.751369Tempo, R., Calafiore, G., Dabbene, F., 2005. Randomized Algorithms for Analysis and Control of Uncertain Systems. Communications and Control Engineering Series. Springer-Verlag, London.Tuan, H., Apkarian, P., Nguyen, T., dec 2001. Robust and reduced-order filtering: new lmi-based characterizations and methods. Signal Processing, IEEE Transactions on 49 (12), 2975-2984. DOI: 10.1109/78.969506.Wan, Z., & Kothare, M. V. (2002). Robust output feedback model predictive control using off-line linear matrix inequalities. Journal of Process Control, 12(7), 763-774. doi:10.1016/s0959-1524(02)00003-3Zhou, K., Doyle, J., Glover, K., 1996. Robust and Optimal Control. Prentice Hall, Englewood Cliff, NJ