×

A randomized approximation algorithm for the minimal-norm static-output-feedback problem. (English) Zbl 1329.93112

Summary: A new randomized algorithm is suggested, for extracting static-output-stabilizing-feedbacks, with approximately minimal-norm, for LTI systems. The algorithm has two similar stages, where in the first one the feasibility problem is solved, and in the second one the optimization problem is solved. The formulation is unified for the feasibility and for the optimization problems, as well as for continuous-time or discrete-time systems. The method is demonstrated by applying it to the hard (conjectured to be NP-hard) problem of the minimal-gain static-output-stabilizing-feedback, and to the hard (conjectured to be NP-hard) problem of regional pole-placement via static-output-feedback in non-convex or unconnected regions. A proof of convergence (in probability) that captures the two rounds of the algorithm is given, and complexity analysis is provided, under some mild assumptions.

MSC:

93D15 Stabilization of systems by feedback
93B40 Computational methods in systems theory (MSC2010)
93B52 Feedback control
93B55 Pole and zero placement problems
PDFBibTeX XMLCite
Full Text: DOI

References:

[2] Apkarian, P.; Noll, D., Nonsmooth \(H_\infty\) synthesis, IEEE Transactions on Automatic Control, 51, 1, 7186 (2006)
[3] Arnold, W. F.; Laub, A. J., Generalized Eigenproblem algorithms and software for algebraic Riccati equations, Proceedings of the IEEE, 72, 1746-1754 (1984)
[5] Badea, C.; Grivaux, S.; Müller, V., The rate of convergence in the method of alternating projections, St. Petersburg Mathematical Journal, 23, 3, 413-434 (2012) · Zbl 1294.47026
[6] Bauschke, H. H.; Borwein, J. M., On projection algorithms for solving convex feasibility problems, SIAM Review, 38, 367-426 (1996) · Zbl 0865.47039
[7] Bauschke, H. H.; Borwein, J. M.; Lewis, A. S., On the method of cyclic projections for convex sets in Hilbert space, (Research report (1994), Simon Fraser University)
[8] Bélisle, C. J.P., Convergence theorems for a class of simulated annealing algorithms on \(R^d\), Applied Probability, 29, 885-895 (1992) · Zbl 0765.65059
[9] Bini, D. A.; Iannazzo, B.; Meini, B., Numerical solution of algebraic Riccati equations, (Fundamentals of algorithms (2012), SIAM: SIAM Philadelphia) · Zbl 1244.65058
[10] Blondel, V.; Tsitsiklis, J. N., NP-hardness of some linear control design problems, SIAM Journal on Control and Optimization, 35, 6, 2118-2127 (1997) · Zbl 0892.93050
[11] Boender, C. G.E.; Romeijn, H. E., (Handbook of global optimization. Handbook of global optimization, chapter stochastic methods, vol. 2 (1995), Kluwer Academic Publishers), 829-869 · Zbl 0833.90100
[13] Bunse-Gerstner, A.; Byres, R.; Mehrmann, V., Numerical methods for algebraic riccati equations, (Bittanti, Sergio, Workshop on the Riccati equation in control systems and signals (1989), Pitagora Editrice: Pitagora Editrice Bologna), 107-125, June
[14] Chilali, M.; Gahinet, P., \(H_\infty\) design with pole placement constraints: an LMI approach, IEEE Transactions on Automatic Control, 41, 3, 358-367 (1996) · Zbl 0857.93048
[15] Chilali, M.; Gahinet, P.; Apkarian, P., Robust pole placement in LMI regions, IEEE Transactions on Automatic Control, 44, 12, 2257-2270 (1999) · Zbl 1136.93352
[16] Eremenko, A.; Gabrielov, A., Pole placement by static output feedback for generic linear systems, SIAM Journal on Control and Optimization, 41, 1, 303-312 (2002) · Zbl 1031.93086
[17] Fu, M., Pole placement via static output feedback is NP-hard, IEEE Transactions on Automatic Control, 49, 5, 855-857 (2004) · Zbl 1365.93196
[19] Helton, J. W.; Vinnikov, V., Linear matrix inequality representation of sets, Communications on Pure and Applied Mathematics, 60, 5, 654-674 (2007) · Zbl 1116.15016
[21] Karlheinz, S., Abstract algebra with applications (1994), Marcel Dekker, Inc.
[22] Leibfritz, F., COMPl \({}_e\) ib: Constrained matrix-optimization problem library-a collection of test examples for nonlinear semidefinite programs, (Control system design and related problems. Tech. Report (2003))
[23] Leibfritz, F., Description of the benchmark examples in COMPl \({}_e\) ib 1.0. Tech. Report (2003)
[24] Leibfritz, F.; Lipinski, W., COMPl \({}_e\) ib 1.0-user manual and quick reference. Tech. Report (2004)
[26] Nemirovskii, A., Several NP-hard problems arising in robust stability analysis, Mathematics Control Signal Systems, 6, 99-105 (1993) · Zbl 0792.93100
[27] Pan, V. Y., Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding, Elsevier Journal of Symbolic Computation, 33, 5, 701-733 (2002) · Zbl 1004.65061
[29] Peretz, Y., A characterization of all the static stabilizing controllers for LTI systems, Linear Algebra and its Applications, 437, 2, 525-548 (2012) · Zbl 1238.93083
[30] Piziak, R.; Odell, P. L., Matrix theory: from generalized inverses to Jordan form, volume 288 (2007), Chapman & Hall/CRC, February · Zbl 1114.15002
[31] Polyak, B.; Khlebnikov, M.; Shcherbakov, P., An LMI approach to structured sparse feedback design in linear control systems, Proc. Eur. Control Conf. ECC-2013, Zürich, 833-838 (2013)
[32] Quoc, T. D.; Gumussoy, S.; Michiels, W.; Diehl, M., Combining convex-concave decompositions and linearization approaches for solving BMIs, with application to static output feedback, IEEE Transactions on Automatic Control, 57, 6, 1377-1390 (2012) · Zbl 1369.90170
[33] Romeijn, H. E.; Smith, R. L., Simulated annealing for constrained global optimization, Global Optimization, 5, 101-126 (1994) · Zbl 0819.90103
[34] Rudin, W., (Real and complex analysis. Real and complex analysis, Mathematics series (1987), McGRAW-Hill international editions) · Zbl 0925.00005
[35] Schmid, R.; Pandey, A.; Nguyen, T., Robust pole placement with Moore’s algorithm, IEEE Transactions on Automatic Control, 59, 500505 (2014) · Zbl 1360.93269
[36] Solis, F. J.; Wets, R. J-B., Minimization by random search techniques, Mathematics Of Operations Research, 6, 1, 19-30 (1981) · Zbl 0502.90070
[37] Spencer, B. F.; Sain, M. K., Controlling buildings: A new frontier in feedback, IEEE Control Systems, 17, 6, 19-35 (1997)
[38] Syrmos, V. L.; Abdallah, C.; Dorato, P.; Grigoradis, K., Static output feedback: A survey, Automatica, 33, 125-137 (1997) · Zbl 0872.93036
[39] Tempo, R.; Calafiore, G.; Dabbene, F., Randomized algorithms for analysis and control of uncertain systems (2005), Springer-Verlag: Springer-Verlag London · Zbl 1079.93002
[40] Tempo, R.; Ishii, H., Monte Carlo and Las Vegas randomized algorithms for systems and control, European Journal of Control, 13, 189-203 (2007) · Zbl 1293.93698
[41] Toker, O.; Özbay, H., On the NP-hardness of solving bilinear matrix inequalities and simultaneous stabilization with static output feedback, Proc. ACC., 2525-2526 (1995)
[42] Vidyasagar, M.; Blondel, V. D., Probabilistic solutions to some NP-hard matrix problems, Automatica, 37, 1397-1405 (2001) · Zbl 1031.93165
[43] Xu, Y. L.; Teng, J., Optimum design of active/passive devices for tall buildings under earthquake excitation, 11, 109-127 (2002), Wiley Interscience, John Wiley & Sons, Ltd.
[44] Xu, J.; Zikatanov, L., The method of alternating projections and the method of subspace corrections in Hilbert space, Journal of the American Mathematical Society, 15, 3, 573-597 (2002) · Zbl 0999.47015
[45] Yang, J. N.; Lin, S.; Jabbari, F., \(H_2\)-based control strategies for civil engineering structures, Journal Of Structural Control, John Wiley & Sons, Ltd., 10, 205-230 (2003)
[46] Yang, K.; Orsi, R., Generalized pole placement via static output feedback: A methodology based on projections, Automatica, 42, 2143-2150 (2006) · Zbl 1104.93036
[47] Zabinsky, Z. B., Stochastic adaptive search for global optimization. Nonconvex optimization and its applications (2003), Kluer Academic Publishers
[48] Zheng, F.; Wang, Q. G.; Lee, T. H., On the design of multivariable PID controllers via LMI approach, Automatica, 38, 517-526 (2002) · Zbl 1064.93017
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.