A fast algorithm for the semi-definite relaxation of the state estimation problem in power grids. (English) Zbl 1438.93220

Summary: State estimation in power grids is a crucial step for monitoring and control tasks. It was shown that the state estimation problem can be solved using a convex relaxation based on semi-definite programming. In the present paper, we propose a fast algorithm for solving this relaxation. Our approach uses the Bürer Monteiro factorisation is a special way that solves the problem on the sphere and and estimates the scale in a Gauss-Seidel fashion. Simulations results confirm the promising behavior of the method.


93E10 Estimation and detection in stochastic control theory
93B70 Networked control
90C22 Semidefinite programming


Full Text: DOI


[1] H. Bai; G. Li; S. Li; Q. Li; Q. Jiang; L. Chang, Alternating optimization of sensing matrix and sparsifying dictionary for compressed sensing, IEEE Transactions on Signal Processing, 63, 1581-1594 (2015) · Zbl 1394.94063
[2] R. G. Baraniuk, Compressive sensing [lecture notes], IEEE Signal Processing Magazine, 24, 118-121 (2007)
[3] A. Belloni, V. Chernozhukov, L. Wang, et al., Pivotal estimation via square-root lasso in nonparametric regression, The Annals of Statistics, 42 (2014), 757-788. · Zbl 1321.62030
[4] S. Bhojanapalli, B. Neyshabur and N. Srebro, Global optimality of local search for low rank matrix recovery, arXiv: 1605.07221, 2016.
[5] D. Bienstock and G. Munoz, Lp formulations for mixed-integer polynomial optimization problems, arXiv Preprint, 2015.
[6] J.-F. Bonnans, J. C. Gilbert, C. Lemaréchal and C. A. Sagastizábal, Numerical Optimization: Theoretical and Practical Aspects, Springer Science & Business Media, 2006.
[7] N. Boumal, V. Voroninski and A. S. Bandeira, The non-convex burer-monteiro approach works on smooth semidefinite programs, arXiv: 1606.04970, 2016.
[8] S. Burer; R. D. C. Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Mathematical Programming, 95, 329-357 (2003) · Zbl 1030.90077
[9] J.-F. Cai; E. J. Candès; Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, 20, 1956-1982 (2010) · Zbl 1201.90155
[10] E. J. Candes, The restricted isometry property and its implications for compressed sensing, Comptes Rendus Mathematique, 346, 589-592 (2008) · Zbl 1153.94002
[11] E. J. Candès and B. Recht, Exact matrix completion via convex optimization, Foundations of Computational Mathematics, 9 (2009), 717.
[12] E. J. Candes; T. Tao, Decoding by linear programming, IEEE Transactions on Information Theory, 51, 4203-4215 (2005) · Zbl 1264.94121
[13] E. J. Candès; T. Tao, The power of convex relaxation: Near-optimal matrix completion, IEEE Transactions on Information Theory, 56, 2053-2080 (2010) · Zbl 1366.15021
[14] E. J. Candès; M. B. Wakin, An introduction to compressive sampling, IEEE Signal Processing Magazine, 25, 21-30 (2008)
[15] S. Chrétien, An alternating l_1 approach to the compressed sensing problem, IEEE Signal Processing Letters, 17, 181-184 (2010)
[16] S. Chrétien; S. Darses, Sparse recovery with unknown variance: A lasso-type approach, IEEE Transactions on Information Theory, 60, 3970-3988 (2014) · Zbl 1360.62396
[17] S. Chrétien; T. Wei, Sensing tensors with gaussian filters, IEEE Transactions on Information Theory, 63, 843-852 (2017) · Zbl 1364.94117
[18] M. A. Davenport; J. Romberg, An overview of low-rank matrix recovery from incomplete observations, IEEE Journal of Selected Topics in Signal Processing, 10, 608-622 (2016)
[19] Y. C. Eldar and G. Kutyniok, Compressed Sensing: Theory and Applications, Cambridge University Press, 2012.
[20] G. Fazelnia, R. Madani and J. Lavaei, Convex relaxation for optimal distributed control problem, in 53rd IEEE Conference on Decision and Control, IEEE, 2014,896-903.
[21] S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing, Birkhäuser Basel, 2013. · Zbl 1315.94002
[22] R. Ge, C. Jin and Y. Zheng, No spurious local minima in nonconvex low rank problems: A unified geometric analysis, arXiv: 1704.00708, 2017.
[23] C. Giraud; S. Huet; N. Verzelen, High-dimensional regression with unknown variance, Statistical Science, 500-518 (2012) · Zbl 1331.62346
[24] R. A. Jabr, Exploiting sparsity in sdp relaxations of the opf problem, IEEE Transactions on Power Systems, 2, 1138-1139 (2012)
[25] C. Klauber and H. Zhu, Distribution system state estimation using semidefinite programming, in North American Power Symposium (NAPS), 2015, IEEE, 2015, 1-6.
[26] O. Klopp and S. Gaiffas, High dimensional matrix estimation with unknown variance of the noise, arXiv: 1112.3055, 2011. · Zbl 1468.62292
[27] G. Kutyniok, Theory and applications of compressed sensing, GAMM-Mitteilungen, 36, 79-101 (2013) · Zbl 1283.94018
[28] J. Lavaei; S. H. Low, Zero duality gap in optimal power flow problem, IEEE Transactions on Power Systems, 27, 92-107 (2012)
[29] Q. Li and G. Tang, The nonconvex geometry of low-rank matrix optimizations with general objective functions, arXiv: 1611.03060, 2016.
[30] S. H. Low, Convex relaxation of optimal power flow, part ⅱ: Exactness, arXiv: 1405.0814, 2014. · Zbl 1370.90044
[31] R. Madani, J. Lavaei and R. Baldick, Convexification of power flow equations for power systems in presence of noisy measurements, preprint, 2016. · Zbl 1482.90261
[32] D. K. Molzahn; J. T. Holzer; B. C. Lesieutre; C. L. DeMarco, Implementation of a large-scale optimal power flow solver based on semidefinite programming, IEEE Transactions on Power Systems, 28, 3987-3998 (2013)
[33] J. Nocedal and S. Wright, Numerical Optimization, Springer Science & Business Media, 2006. · Zbl 1104.65059
[34] D. Park, A. Kyrillidis, C. Caramanis and S. Sanghavi, Non-square matrix sensing without spurious local minima via the burer-monteiro approach, arXiv: 1609.03240, 2016.
[35] J. Salmon, On High Dimensional Regression: Computational and Statistical Perspectives, PhD thesis, HDR, École normale supérieure Paris-Saclay, 2017.
[36] F. Schweppe, Recursive state estimation: unknown but bounded errors and system inputs, IEEE Transactions on Automatic Control, 13, 22-28 (1968)
[37] Q. Song, H. Ge, J. Caverlee and X. Hu, Tensor completion algorithms in big data analytics, arXiv: 1711.10105, 2017.
[38] A. Virouleau, A. Guilloux, S. Gaïffas and M. Bogdan, High-dimensional robust regression and outliers detection with slope, arXiv: 1712.02640, 2017.
[39] A. Wang and Z. Jin, Near-optimal noisy low-tubal-rank tensor completion via singular tube thresholding, in Data Mining Workshops (ICDMW), 2017 IEEE International Conference on, IEEE, 2017,553-560.
[40] F. F. Wu, Power system state estimation: A survey, International Journal of Electrical Power & Energy Systems, 12, 80-87 (1990)
[41] Y. Zhang, R. Madani and J. Lavaei, Power system state estimation with line measurements, 2016. · Zbl 07044984
[42] Z. Zhang; S. Aeron, Exact tensor completion using t-svd, IEEE Transactions on Signal Processing, 65, 1511-1526 (2017) · Zbl 1414.94741
[43] H. Zhu; G. B. Giannakis, Power system nonlinear state estimation using distributed semidefinite programming, IEEE Journal of Selected Topics in Signal Processing, 8, 1039-1050 (2014)
[44] Z. Zhu, Q. Li, G. Tang and M. B. Wakin, The global optimization geometry of nonsymmetric matrix factorization and sensing, arXiv: 1703.01256, 2017.
[45] R. D. Zimmerman, C. E. Murillo-Sánchez and D. Gan, Matpower, PSERC.[Online]. Software Available at: http://www.pserc.cornell.edu/matpower, 1997.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.