# American Institute of Mathematical Sciences

doi: 10.3934/jimo.2018161

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

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

* Corresponding author: Stéphane Chrétien

Received  June 2017 Revised  June 2018 Published  November 2018

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.

Citation: Stephane Chretien, Paul Clarkson. A fast algorithm for the semi-definite relaxation of the state estimation problem in power grids. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2018161
##### References:

show all references

##### References:
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.
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.
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.
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.
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.
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.
 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
 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
 [1] Yi Xu, Jinjie Liu, Liqun Qi. A new class of positive semi-definite tensors. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-11. doi: 10.3934/jimo.2018186 [2] Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129 [3] Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319 [4] Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317 [5] Wei Huang, Ka-Fai Cedric Yiu, Henry Y. K. Lau. Semi-definite programming based approaches for real-time tractor localization in port container terminals. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 665-680. doi: 10.3934/naco.2013.3.665 [6] Monika Eisenmann, Etienne Emmrich, Volker Mehrmann. Convergence of the backward Euler scheme for the operator-valued Riccati differential equation with semi-definite data. Evolution Equations & Control Theory, 2019, 8 (2) : 315-342. doi: 10.3934/eect.2019017 [7] Stéphane Chrétien, Sébastien Darses, Christophe Guyeux, Paul Clarkson. On the pinning controllability of complex networks using perturbation theory of extreme singular values. application to synchronisation in power grids. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 289-299. doi: 10.3934/naco.2017019 [8] Sihem Guerarra. Positive and negative definite submatrices in an Hermitian least rank solution of the matrix equation AXA*=B. Numerical Algebra, Control & Optimization, 2019, 9 (1) : 15-22. doi: 10.3934/naco.2019002 [9] Vladimir V. Chepyzhov, Anna Kostianko, Sergey Zelik. Inertial manifolds for the hyperbolic relaxation of semilinear parabolic equations. Discrete & Continuous Dynamical Systems - B, 2019, 24 (3) : 1115-1142. doi: 10.3934/dcdsb.2019009 [10] Helene Frankowska, Elsa M. Marchini, Marco Mazzola. A relaxation result for state constrained inclusions in infinite dimension. Mathematical Control & Related Fields, 2016, 6 (1) : 113-141. doi: 10.3934/mcrf.2016.6.113 [11] Tiffany A. Jones, Lou Caccetta, Volker Rehbock. Optimisation modelling of cancer growth. Discrete & Continuous Dynamical Systems - B, 2017, 22 (1) : 115-123. doi: 10.3934/dcdsb.2017006 [12] Claude Stolz. On estimation of internal state by an optimal control approach for elastoplastic material. Discrete & Continuous Dynamical Systems - S, 2016, 9 (2) : 599-611. doi: 10.3934/dcdss.2016014 [13] Peng Cui, Hongguo Zhao, Jun-e Feng. State estimation for discrete linear systems with observation time-delayed noise. Journal of Industrial & Management Optimization, 2011, 7 (1) : 79-85. doi: 10.3934/jimo.2011.7.79 [14] Dominique Chapelle, Philippe Moireau, Patrick Le Tallec. Robust filtering for joint state-parameter estimation in distributed mechanical systems. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 65-84. doi: 10.3934/dcds.2009.23.65 [15] Elena K. Kostousova. State estimation for linear impulsive differential systems through polyhedral techniques. Conference Publications, 2009, 2009 (Special) : 466-475. doi: 10.3934/proc.2009.2009.466 [16] Ferenc Hartung. Parameter estimation by quasilinearization in differential equations with state-dependent delays. Discrete & Continuous Dynamical Systems - B, 2013, 18 (6) : 1611-1631. doi: 10.3934/dcdsb.2013.18.1611 [17] W. Y. Tan, L.-J. Zhang, C.W. Chen. Stochastic modeling of carcinogenesis: State space models and estimation of parameters. Discrete & Continuous Dynamical Systems - B, 2004, 4 (1) : 297-322. doi: 10.3934/dcdsb.2004.4.297 [18] Redouane Qesmi, Hans-Otto Walther. Center-stable manifolds for differential equations with state-dependent delays. Discrete & Continuous Dynamical Systems - A, 2009, 23 (3) : 1009-1033. doi: 10.3934/dcds.2009.23.1009 [19] Ciro D'Apice, Peter I. Kogut, Rosanna Manzo. On relaxation of state constrained optimal control problem for a PDE-ODE model of supply chains. Networks & Heterogeneous Media, 2014, 9 (3) : 501-518. doi: 10.3934/nhm.2014.9.501 [20] Frank Jochmann. Power-law approximation of Bean's critical-state model with displacement current. Conference Publications, 2011, 2011 (Special) : 747-753. doi: 10.3934/proc.2011.2011.747

2018 Impact Factor: 1.025