×

On computing the distance to stability for matrices using linear dissipative Hamiltonian systems. (English) Zbl 1375.93110

Summary: In this paper, we consider the problem of computing the nearest stable matrix to an unstable one. We propose new algorithms to solve this problem based on a reformulation using linear dissipative Hamiltonian systems: we show that a matrix \(A\) is stable if and only if it can be written as \(A=(J-R)Q\), where \(J=-J^T\), \(R \succeq 0\) and \(Q\succ 0\) (that is, \(R\) is positive semidefinite and \(Q\) is positive definite). This reformulation results in an equivalent optimization problem with a simple convex feasible set. We propose three strategies to solve the problem in variables \((J,R,Q)\): (i) a block coordinate descent method, (ii) a projected gradient descent method, and (iii) a fast gradient method inspired from smooth convex optimization. These methods require \(\mathcal{O}(n^3)\) operations per iteration, where \(n\) is the size of \(A\). We show the effectiveness of the fast gradient method compared to the other approaches and to several state-of-the-art algorithms.

MSC:

93D21 Adaptive or robust stabilization
93C15 Control/observation systems governed by ordinary differential equations
93C05 Linear systems in control theory
93B60 Eigenvalue problems

Software:

SDPT3; SeDuMi; CVX; HIFOO
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alam, R.; Bora, S.; Karow, M.; Mehrmann, V.; Moro, J., Perturbation theory for Hamiltonian matrices and the distance to bounded-realness, SIAM Journal on Matrix Analysis and Applications, 32, 2, 484-514 (2011) · Zbl 1227.93081
[2] Beattie, C., Mehrmann, V., & Xu, H. (2015). Port-Hamiltonian realizations of linear time invariant systems. http://dx.doi.org/10.14279/depositonce-4934; Beattie, C., Mehrmann, V., & Xu, H. (2015). Port-Hamiltonian realizations of linear time invariant systems. http://dx.doi.org/10.14279/depositonce-4934
[3] Boyd, S.; El Ghaoui, L.; Feron, E.; Balakrishnan, V., Linear matrix inequalities in system and control theory (1994), Society for Industrial and Applied Mathematics · Zbl 0816.93004
[4] Burke, J. V., Henrion, D., Lewis, A. S., & Overton, M. L. (2006a). HIFOO - A MATLAB package for fixed-order controller design and \(H_\infty \)Fifth IFAC symposium on robust control design, Toulouse; Burke, J. V., Henrion, D., Lewis, A. S., & Overton, M. L. (2006a). HIFOO - A MATLAB package for fixed-order controller design and \(H_\infty \)Fifth IFAC symposium on robust control design, Toulouse
[5] Burke, J. V.; Henrion, D.; Lewis, A. S.; Overton, M. L., Stabilization via nonsmooth, nonconvex optimization, IEEE Transactions on Automatic Control, 51, 11, 1760-1769 (2006) · Zbl 1366.93490
[6] Byers, R., A bisection method for measuring the distance of a stable to unstable matrices, SIAM Journal on Scientific and Statistical Computing, 9, 875-881 (1988) · Zbl 0658.65044
[7] D’haene, T.; Pintelon, R.; Vandersteen, G., An iterative method to stabilize a transfer function in the s- and z- domains, IEEE Transactions on Instrumentation and Measurement, 55, 1192-1196 (2006)
[8] Ghadimi, S.; Lan, G., Accelerated gradient methods for nonconvex nonlinear and stochastic programming, Mathematical Programming, 156, 1-2, 59-99 (2016) · Zbl 1335.62121
[9] Golo, G.; van der Schaft, A. V.; Breedveld, P. C.; Maschke, B. M., Hamiltonian formulation of bond graphs, (Johansson, R.; Rantzer, A., Nonlinear and hybrid systems in automotive control (2003), Springer-Verlag: Springer-Verlag Heidelberg, Germany), 351-372
[10] Grant, M., Boyd, S., & Ye, Y. (2008). CVX: Matlab software for disciplined convex programming.; Grant, M., Boyd, S., & Ye, Y. (2008). CVX: Matlab software for disciplined convex programming.
[11] Grippo, L.; Sciandrone, M., On the convergence of the block nonlinear Gauss-Seidel method under convex constraints, Operations Research Letters, 26, 127-136 (2000) · Zbl 0955.90128
[12] Higham, N. J., Computing a nearest symmetric positive semidefinite matrix, Linear Algebra and its Applications, 103, 103-118 (1988) · Zbl 0649.65026
[13] Higham, N. J., Matrix nearness problems and applications (1988), Citeseer · Zbl 0681.65029
[14] Hinrichsen, D.; Pritchard, A. J., Stability radii of linear systems, Systems & Control Letters, 7, 1-10 (1986) · Zbl 0631.93064
[15] Horn, R. A.; Johnson, C. R., Matrix analysis (1985), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0576.15001
[16] Lancaster, P.; Tismenetsky, M., The theory of matrices (1985), Academic Press: Academic Press Orlando · Zbl 0516.15018
[17] Lewis, A. S., & Overton, M. L. (2009). Nonsmooth optimization via BFGS. http://www.cs.nyu.edu/overton/papers/pdffiles/bfgs_inexactLS.pdf; Lewis, A. S., & Overton, M. L. (2009). Nonsmooth optimization via BFGS. http://www.cs.nyu.edu/overton/papers/pdffiles/bfgs_inexactLS.pdf
[18] Mehl, C.; Mehrmann, V.; Sharma, P., Stability radii for linear Hamiltonian systems with dissipation under structure-preserving perturbations, SIAM Journal on Matrix Analysis and Applications, 37, 4, 1625-1654 (2016) · Zbl 1349.93332
[19] Mehl, C.; Mehrmann, V.; Sharma, P., Stability radii for real linear Hamiltonian systems with perturbed dissipation, BIT Numerical Mathematics (2017), issn: 1572-9125
[20] Moses, R. L.; Liu, D., Determining the closest stable polynomial to an unstable one, Transactions on Signal Processing, 39, 4, 901-906 (1991)
[21] Nesterov, Yu., Introductory lectures on convex optimization: A basic course, vol. 87 (2004), Springer Science & Business Media · Zbl 1086.90045
[22] Orbandexivry, F.-X.; Nesterov, Yu.; Van Dooren, P., Nearest stable system using successive convex approximations, Automatica, 49, 5, 1195-1203 (2013) · Zbl 1319.93062
[23] Ostrowski, A. M., (Solution of equations and systems of equations. Solution of equations and systems of equations, Pure and applied mathematics (1960), Academic Press) · Zbl 0115.11201
[24] Packard, A.; Doyle, J., The complex structured singular value, Automatica, 29, 1, 71-109 (1993) · Zbl 0772.93023
[25] Shi, H.-J. M., Tu, S., Xu, Y., & Yin, W. (2016). A primer on coordinate descent algorithms, arXiv:1610.00040; Shi, H.-J. M., Tu, S., Xu, Y., & Yin, W. (2016). A primer on coordinate descent algorithms, arXiv:1610.00040
[26] Sturm, J. F., Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optimization Methods and Software, 11, 1-4, 625-653 (1999) · Zbl 0973.90526
[27] Toh, K.-C.; Todd, M. J.; Tütüncü, R. H., SDPT3-a MATLAB software package for semidefinite programming, version 1.3, Optimization Methods and Software, 11, 1-4, 545-581 (1999) · Zbl 0997.90060
[28] van der Schaft, A. J. (2006). Port-Hamiltonian systems: an introductory survey. In Proc. of the international congress of mathematicians, vol. III, invited lectures; van der Schaft, A. J. (2006). Port-Hamiltonian systems: an introductory survey. In Proc. of the international congress of mathematicians, vol. III, invited lectures · Zbl 1108.93012
[29] van der Schaft, A. J.; Maschke, B. M., Port-Hamiltonian systems on graphs, SIAM Journal on Control and Optimization (2013) · Zbl 1268.05099
[30] Wilkinson, J. H., Sensitivity of eigenvalues, Utilitas Mathematica, 25, 5-76 (1984) · Zbl 0551.65018
[31] Wright, S. J., Coordinate descent algorithms, Mathematical Programming, 151, 1, 3-34 (2015) · Zbl 1317.49038
[32] Zhou, T., On nonsingularity verification of uncertain matrices over a quadratically constrained set, IEEE Transactions on Automatic Control, 56, 9, 2206-2212 (2011) · Zbl 1368.93242
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.