A fast algorithm for the semi-definite relaxation of the state estimation problem in power grids

Stephane Chretien; Paul Clarkson

doi:10.3934/jimo.2018161

Article Contents

2020, Volume 16, Issue 1: 431-443. Doi: 10.3934/jimo.2018161

This issue Previous Article A hybrid chaos firefly algorithm for three-dimensional irregular packing problem Next Article Group decision making approach based on possibility degree measure under linguistic interval-valued intuitionistic fuzzy set environment

A fast algorithm for the semi-definite relaxation of the state estimation problem in power grids

Stephane Chretien and
Paul Clarkson

National Physical Laboratory, Hampton Road, Teddington, Middlesex, TW11 0LW, UK

* Corresponding author: Stéphane Chrétien

Received: June 2017

Revised: June 2018

Early access: November 2018

Published: October 2019

Abstract Full Text(HTML) Figure(6) / Table(1) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 93B, Secondary: 90-08.

Citation:

Full Text(HTML)

Figure 1. Comparison of Sum of Squared Errors for the IEEE-30 network: New method vs. SDP relaxation (using YALMIP) with noise standard deviation equal to.2 when power is observed at half the number of buses chosen at random.

Download: Full-size image PowerPoint slide

Figure 2. Comparison of computation times for the IEEE-30 network: New method vs. SDP relaxation (using YALMPI) with noise standard deviation equal to.2 when power is observed at half the number of buses chosen uniformly at random.

Download: Full-size image PowerPoint slide

Figure 3. Example of evolution of the objective function as a function of iteration number for one realisation of a random noise for the IEEE-30 network.

Download: Full-size image PowerPoint slide

Figure 4. Example of evolution of the euclidean distance between successive $A$-iterates as a function of iteration number for one realisation of a random noise for the IEEE-30 network.

Download: Full-size image PowerPoint slide

Figure 5. Mean Squared Error obtained using the estimator based on the new method with noise standard deviation equal to.2 when power is observed at half the buses. The buses selected for observation were selected uniformly at random.

Download: Full-size image PowerPoint slide

Figure 6. Computation times using the new method with noise standard deviation equal to.2 when power is observed at half the buses. The buses selected for observation were selected uniformly at random.

Download: Full-size image PowerPoint slide

Result:

$W_{opt}$

Choose $A^{(1,1)} \in \mathbb C^{n\times k}$

$\underline {First\;stage} $

$\begin{array}{l} {\bf{while}}\;s \le S - 1\;{\bf{do}}\\ \;\left| \begin{array}{l} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\nabla g(A) = 2\;\sum\limits_{l = 1}^L \; ( - {z_l}\;\alpha (H_l^* + {H_l})A\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; + 2\;{\alpha ^2}\;{\rm{trace}}({H_l}A{A^*})(H_l^* + {H_l})A).\;\;\;\;\;\;\;\;\;\;\left( 8 \right)\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{{\tilde A}^{(t,s + 1)}} = {A^{(t,s)}} - \eta \nabla g({A^{(t,s)}})\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left( 9 \right)\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{A^{(t,s + 1)}} = \frac{1}{{\left\| {{{\tilde A}^{(t,s + 1)}}} \right\|}}\;{{\tilde A}^{(t,s + 1)}}.\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left( {10} \right) \end{array} \right.\\ {\bf{end}} \end{array}$

Set $A^{(t+1,1)}=A^{(t,S)}$.

$\underline {Second\;stage}$

Set

$\begin{align} W_{opt}&= \alpha^{(t+1)} \ A^{(t+1,1)}A^{(t+1,1)^*} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left( {11} \right) \end{align}$

with
\begin{align} \alpha^{(t+1)} & = \frac{\sum\nolimits_{l=1}^L z_l\ \textrm{trace }(H_l A^{(t+1, 1)}A^{(t+1, 1)^*})}{\sum\nolimits_{l=1}^L \left(\textrm{trace }(H_l A^{(t+1, 1)}A^{(t+1, 1)^*})\right)^2} \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \left({12} \right) \end{align}
Algorithm 1: The two stage optimisation procedure

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	H. Bai, G. Li, S. Li, Q. Li, Q. Jiang and L. Chang, Alternating optimization of sensing matrix and sparsifying dictionary for compressed sensing, IEEE Transactions on Signal Processing, 63 (2015), 1581-1594. doi: 10.1109/TSP.2015.2399864.
[2]	R. G. Baraniuk, Compressive sensing [lecture notes], IEEE Signal Processing Magazine, 24 (2007), 118-121.
[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. doi: 10.1214/14-AOS1204.
[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. doi: 10.1137/15M1054079.
[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 and R. D. C. Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Mathematical Programming, 95 (2003), 329-357. doi: 10.1007/s10107-002-0352-8.
[9]	J.-F. Cai, E. J. Candès and Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, 20 (2010), 1956-1982. doi: 10.1137/080738970.
[10]	E. J. Candes, The restricted isometry property and its implications for compressed sensing, Comptes Rendus Mathematique, 346 (2008), 589-592. doi: 10.1016/j.crma.2008.03.014.
[11]	E. J. Candès and B. Recht, Exact matrix completion via convex optimization, Foundations of Computational Mathematics, 9 (2009), 717. doi: 10.1007/s10208-009-9045-5.
[12]	E. J. Candes and T. Tao, Decoding by linear programming, IEEE Transactions on Information Theory, 51 (2005), 4203-4215. doi: 10.1109/TIT.2005.858979.
[13]	E. J. Candès and T. Tao, The power of convex relaxation: Near-optimal matrix completion, IEEE Transactions on Information Theory, 56 (2010), 2053-2080. doi: 10.1109/TIT.2010.2044061.
[14]	E. J. Candès and M. B. Wakin, An introduction to compressive sampling, IEEE Signal Processing Magazine, 25 (2008), 21-30.
[15]	S. Chrétien, An alternating l_1 approach to the compressed sensing problem, IEEE Signal Processing Letters, 17 (2010), 181-184.
[16]	S. Chrétien and S. Darses, Sparse recovery with unknown variance: A lasso-type approach, IEEE Transactions on Information Theory, 60 (2014), 3970-3988. doi: 10.1109/TIT.2014.2301162.
[17]	S. Chrétien and T. Wei, Sensing tensors with gaussian filters, IEEE Transactions on Information Theory, 63 (2017), 843-852. doi: 10.1109/TIT.2016.2633413.
[18]	M. A. Davenport and J. Romberg, An overview of low-rank matrix recovery from incomplete observations, IEEE Journal of Selected Topics in Signal Processing, 10 (2016), 608-622.
[19]	Y. C. Eldar and G. Kutyniok, Compressed Sensing: Theory and Applications, Cambridge University Press, 2012. doi: 10.1515/dmvm-2014-0014.
[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. doi: 10.1109/TCNS.2014.2309732.
[21]	S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing, Birkhäuser Basel, 2013. doi: 10.1007/978-0-8176-4948-7.
[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 and N. Verzelen, High-dimensional regression with unknown variance, Statistical Science, (2012), 500-518. doi: 10.1214/12-STS398.
[24]	R. A. Jabr, Exploiting sparsity in sdp relaxations of the opf problem, IEEE Transactions on Power Systems, 2 (2012), 1138-1139.
[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.
[27]	G. Kutyniok, Theory and applications of compressed sensing, GAMM-Mitteilungen, 36 (2013), 79-101. doi: 10.1002/gamm.201310005.
[28]	J. Lavaei and S. H. Low, Zero duality gap in optimal power flow problem, IEEE Transactions on Power Systems, 27 (2012), 92-107.
[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. doi: 10.1109/TCNS.2014.2323634.
[31]	R. Madani, J. Lavaei and R. Baldick, Convexification of power flow equations for power systems in presence of noisy measurements, preprint, 2016.
[32]	D. K. Molzahn, J. T. Holzer, B. C. Lesieutre and C. L. DeMarco, Implementation of a large-scale optimal power flow solver based on semidefinite programming, IEEE Transactions on Power Systems, 28 (2013), 3987-3998.
[33]	J. Nocedal and S. Wright, Numerical Optimization, Springer Science & Business Media, 2006.
[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 (1968), 22-28.
[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 (1990), 80-87.
[41]	Y. Zhang, R. Madani and J. Lavaei, Power system state estimation with line measurements, 2016.
[42]	Z. Zhang and S. Aeron, Exact tensor completion using t-svd, IEEE Transactions on Signal Processing, 65 (2017), 1511-1526. doi: 10.1109/TSP.2016.2639466.
[43]	H. Zhu and G. B. Giannakis, Power system nonlinear state estimation using distributed semidefinite programming, IEEE Journal of Selected Topics in Signal Processing, 8 (2014), 1039-1050.
[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.