{'fraction_non_alphanumeric': 0.0450647927277416, 'fraction_numerical': 0.010895493520727226, 'mean_word_length': 4.483209614704843, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Moving-Horizon Dynamic Power System State Estimation Using Semidefinite Relaxation

Accurate power system state estimation (PSSE) is an essential prerequisite for reliable operation of power systems. Different from static PSSE, dynamic PSSE can exploit past measurements based on a dynamical state evolution model, offering improved accuracy and state predictability. A key challenge is the nonlinear measurement model, which is often tackled using linearization, despite divergence and local optimality issues. In this work, a moving-horizon estimation (MHE) strategy is advocated, where model nonlinearity can be accurately captured with strong performance guarantees. To mitigate local optimality, a semidefinite relaxation approach is adopted, which often provides solutions close to the global optimum. Numerical tests show that the proposed method can markedly improve upon an extended Kalman filter (EKF)-based alternative.


I. INTRODUCTION
The electric power system is a large-scale cyber-physical system, composed of thousands of physical and computational modules, spanning over a wide geographical area. The energy management system (EMS)/supervisory control and data acquisition (SCADA) systems are responsible for monitoring, control and optimization of the power grid, performing a slew of tasks including bad data detection and analysis, economic dispatch, and optimal power flow [1]- [3]. Accurate power system state estimation (PSSE) is an essential prerequisite for these functions, providing the operator with basic visibility to real-time states of power systems. PSSE is also critical for security assessment necessary to detect instabilities and contingencies, and to determine necessary corrective actions [4].
The state of a power system refers to the complex voltages consisting of voltage magnitudes and phase angles, at all buses in the grid. Given the network topology and impedance parameters, all nodal and line electrical quantities of interest are completely characterized by the system states. The goal of PSSE is to estimate the system states from the measurements of related quantities, such as power injections and flows, and voltage magnitudes and angles, at a subset of buses. Depending on whether system dynamics are taken into account, PSSE can be divided into two paradigms: static PSSE and dynamic PSSE (also called forecasting-aided PSSE) [4].
When SCADA measurements are involved, the PSSE problem becomes nonlinear and nonconvex. Traditionally, PSSE has been solved via weighted nonlinear least-squares, invoking Gauss-Newton iterations. Thus, the method is potentially susceptible to locally optimal solutions, sensitive to initialization, and troubled with convergence issues. This may become increasingly problematic in the challenging scenarios of future power systems, where system states may change significantly between measurements due to, e.g., massive integration renewables, the presence of bad data, or, cyber-attacks.
A recent progress made for mitigating these issues in the context of static PSSE is based on a semidefinite relaxation (SDR) approach, which was demonstrated empirically to yield solutions close to the globally optimal ones at polynomialtime complexity [5]. SDR is well motivated in various applications in signal processing and communication [6], as well as in optimal power flow problems [7]- [9]. In a nutshell, the measurement model, which is nonlinear in system states v, is re-expressed as linear in the rank-1 outer product V := vv H (· H denotes Hermitian transpose), which leads to a semidefinite programming problem except for the rank-1 constraint. Dropping the nonconvex rank constraints yields a convex problem, from whose solutions the desired rank-1 solutions can be recovered using various heuristics.
While static PSSE utilizes only the measurements of current time, dynamic PSSE can leverage past measurements as well, based on the dynamical model governing the system states. The dynamics of power systems could be due to the changing frequency, or the changing line parameters. To circumvent the nonlinearity in the measurement model, approximate state estimation techniques such as the extended Kalman filter (EKF) and the unscented Kalman filter (UKF) have been advocated [10], [11]. However, such approximations can suffer from divergence due to their inability to accurately incorporate the underlying nonlinear dynamics.
Recently, moving-horizon estimation (MHE) for nonlinear dynamical systems has attracted much attention [12], because it can provide state estimates with bounded error under appropriate assumptions [12]. Moreover, constrained MHE has been shown to offer an asymptotically stable estimator for nonlinear dynamical systems with deterministic noise terms [13].
Rigorous comparison of MHE and EKF for nonlinear chemical processes corroborated the robustness and improved estimation performance of the MHE method [14]. When applied to the dynamic PSSE problem, however, the MHE formulation is still nonconvex, and thus difficult to yield globally optimal solutions. The key contribution of the present paper is to leverage SDR to convexify the problem and thus attain efficient near-optimal solutions. The remainder of this paper is organized as follows. The power grid model and the (static) PSSE formulation are introduced in Section II. The SDR approach for PSSE is reviewed in Section III. In Section IV, the MHE strategy for dynamic PSSE is presented and the SDR reformulation is described. The results of numerical tests are presented in Section V, and the conclusions are drawn in Section VI.
Notations: All matrices (vectors) are denoted by boldface letters. (·) T and (·) H represent transpose and complexconjugate transpose, respectively; · F is the matrix Frobenius norm, · the vector Euclidean norm, Tr(·) the matrix trace, and rank(·) the matrix rank; finally, |·| signifies the magnitude of a complex number.
L measurements of the following types are taken: Active (reactive) power injection at bus n, denoted by P n (Q n ); active (reactive) power flow out of bus m to bus l, denoted by P mn (Q mn ); and voltage magnitude at bus n, denoted by |V n |. Then, collect the measurements in an L × 1 vector z : It turns out that the measured quantities P n , Q n , P mn , Q mn , |V n | are quadratic functions of v. To specify this, collect injected currents at all buses in vector i := [I 1 , I 2 , . . . , I N ] T ∈ C N , and let Y ∈ C N ×N denote the so-called bus admittance matrix, whose entries are defined as where y mn is line admittance between buses m and n;ȳ nn the shunt admittance of bus n to the ground; and N n the set of buses with transmission lines connected to bus n. Upon denoting the shunt admittance at bus n corresponding to line (m, n) byȳ mn , the current flowing from bus m to bus n is given by I mn =ȳ mn V m + y mn (V m − V n ). Then the complex power injection at bus n is P n + jQ n = V n (I n ) H , and the complex power flowing out from bus m to bus n is P mn + jQ mn = V m (I mn ) H . Likewise, the squared bus voltage magnitude can also be expressed as Then, the measurement model is given by where h ℓ (·) is quadratic in v, and η ℓ is the measurement noise.
The goal of PSSE is to obtain an estimate of v from z. The static PSSE is formulated as a weighted nonlinear least-squares (LS) problem given bŷ where w ℓ represents the weight for the ℓ-th measurement, inversely proportional to the variance of η ℓ . Problem (3) is nonlinear and nonconvex. Thus, iterative algorithms based on Gauss-Newton updates are often employed to find locally optimal solutions. Next, an SDR approach that targets globally optimal solutions is reviewed.

III. SDR APPROACH FOR PSSE
The idea is to re-express the quadratic function h ℓ of v as a linear function of the rank-1 matrix V := vv H . Let e n denote the n-th canonical basis of R N , and define a number of admittance-related matrices together with and H V,n := e n (e n ) T .
With these definitions, the following relations hold for every n ∈ N and every (m, n) ∈ E P n = Tr H P,n V , Q n = Tr H P,n V P mn = Tr H P,mn V , Q mn = Tr H Q,mn V and |V n | 2 = Tr H V,n V .
Then, z ℓ can be expressed as where H ℓ is one of H P,n , H P,mn , H Q,n , H Q,mn and H V,n , corresponding to the type of the ℓ-th measurement. Then problem (3) is equivalent to s. to V 0, and rank(V) = 1.
SDR amounts to dropping the nonconvex rank constraint in (8b), yielding a convex optimization problem, which can be efficiently solved.

A. MHE for Dynamic PSSE
For dynamic PSSE, the state-space model adopted is: with the following notations state-transition matrix to be updated online; given compact sets, with 0 ∈ E and 0 ∈ H .
Different from standard Kalman filtering set-ups, the initial state v 0 , the process noise {ξ k }, and the measurement noise {η k } in MHE are assumed to be unknown deterministic vectors, which take values from Y , E , and H , respectively. The constraints E and H can be interpreted as a strategy for modeling the bounded disturbances or random variables with truncated densities [13]. We resort to the MHE strategy to perform dynamic PSSE because of well-appreciated advantages of MHE in nonlinear state estimation, such as accurate yet tractable incorporation of nonlinearities with consequent asymptotic stability. To be specific, given appropriate assumptions including that the nonlinear system is uniformly observable, and that the states belong to a compact set, MHE turns out to be an asymptotically stable observer [13,Prop. 3.4].
The key idea behind MHE is to capitalize on a sliding window of past observations to perform state estimation. Thus, the information vector containing M past measurements as well as the current one at time k is given by Therefore, per time instant k, it is only necessary to determinê v k−M|k , since the other M − 1 estimates can be iteratively computed via (12).
Considering that the statistics of v 0 , {ξ k }, {η k } are unknown, the LS estimation criterion is given by where the nonnegative weights µ and λ are design parameters, tuned depending on the relative confidence in the state predictionv k−M and the measurements, respectively. In a nutshell, the MHE strategy can be stated as follows.

B. SDR for MHE
The limitation of MHE is that it requires online solutions of dynamic (nonconvex) optimization problems [cf. (14)], which are typically solved by Gauss-Newton iterations. Instead, the fresh idea here is to leverage the SDR technique to find the near globally optimum solutions for MHE-based dynamic PSSE.
In light of (12),v k−M+1|k , . . . ,v k|k can be directly calculated once we obtain the estimatev k−M|k . Similarly, by definingV k−M|k :=v k−M|kv H k−M|k , we can propagate the noise-free dynamics to obtain [cf. (12)] and H V,n s := T H s (e n (e n ) T )T s .
Then, it can be clearly seen that Moreover, letV k−M :=v k−Mv H k−M be the outer product formed from the prior estimatev k−M . Approaches to obtain v k−M fromV k−M|k−1 will be discussed later.
Then, the SDR-based MHE problem can be formulated as withV 0 :=v 0|M−1v H 0|M−1 . The positive semidefinite constraint (19b) together with the rank constraint (19c) ensure thatv k−M|k can be recovered fromV k−M|k . However, this formulation is nonconvex due to the rank constraint. Thus, SDR approach amounts to removing (19c) to obtain a convex optimization problem.
Due to the relaxation, optimal solutionV k−M|k to the SDR problem (19a)-(19b) may be of rank greater than 1. Still, one can recoverv k−M|k fromV k−M|k using a number of heuristics. One way is to perform eigen-decomposition of V k−M|k asV where r is the rank ofV k−M|k , σ 1 ≥ σ 2 ≥ . . . ≥ σ r > 0 are the ordered eigenvalues ofV k−M|k , and q i is the eigenvector corresponding to eigenvalue σ i . Then, the best rank-one approximation ofV k−M|k in the LS sense is σ 1 q 1 q H 1 . Thus, v k−M|k can be approximated to √ σ 1 q 1 . Another approach is to resort to randomization, where one generates random vectors according to N (0,V k−M|k ), and picks the one that minimizes the cost. Such a randomization procedure has been empirically found to yield reasonable performance [6]. Oncê v k−M|k is obtained via any of such heuristics, estimateŝ v k−M+1|k ,v k−M+2|k , . . . ,v k|k can be found again using (12).
The computational complexity of solving (19a)-(19b) is rather high in the present form, although it is still polynomial in N . There are two promising directions under investigation. One is to exploit rich sparsity structure in H ℓ to simplify the formulation. Another direction is to consider special network structures such as the radial topology common in transmission networks. This allows second-order cone programming (SOCP) formulations, which can be solved faster [15].

V. NUMERICAL TESTS
The proposed SDR-based MHE approach was tested using the IEEE 6-bus system with 11 transmission lines, and compared to an existing approach that is based on the EKF [10]. For this, a Matlab toolbox called MATPOWER [16] was used to generate the pertinent power flows and meter measurements. To solve (19a)-(19b), the CVX and SeDuMi packages were used [17], [18].
To simulate the slow evolution of the power system states, transition matrix F k = diag(1, 1.05, 1.05, 1.05, 0.95, 0.95) was employed and each entry of the process noise ξ k was generated by having both the magnitude and angle sampled according to a uniform distribution over the interval [−0.05, 0.05]. The voltage magnitudes of initial state v 0 was formed to have Gaussian distributed entries with mean 1 and standard deviation 0.1, and angles uniformly distributed over [−0.5π, 0.5π]. Bus 1 was chosen as the reference with angle 0 in order to fix the phase angle ambiguity [5]. The active and reactive power flows across lines 1-7 together with voltage  magnitudes at all 6 buses were measured. Every measurement was corrupted by noise randomly generated over interval [−0.05, 0.05]. The simulation horizon, the length of the sliding window are, respectively, 40, 2, and the design parameters are set to µ = 1, and λ = 0.0075. Fig. 1 compares the root-mean-square-errors (RMSEs) of the proposed approach against those of EKF, where the results were based upon 100 independent realizations. Fig. 2-4 depict the dynamic evolution of both estimates calculated by the two approaches together with the true states v 2 k of bus 2, v 4 k of bus 4, v 6 k of bus 6, respectively, where the real part is shown at the top panel and the imaginary part at the bottom. It can be clearly seen that the proposed method exhibits improved RMSE performance relative to EKF, which may even diverge from the true state depending on the initialization.

VI. CONCLUSION
A dynamic PSSE algorithm has been proposed for power systems, which capitalizes on a set of recent measurements in a sliding window fashion. Since the measurement model for power grids is inherently nonlinear, traditional dynamic PSSE methods have relied on EKF/UKF approaches. Unfortunately, depending on initialization and the severity of dynamics, existing algorithms may be divergent. In contrast, the proposed approach leverages the MHE strategy and the SDR technique to accurately incorporate nonlinear dynamics, thus providing improved estimation accuracy and robustness. Numerical tests using the IEEE 6-bus system corroborated those performance claims. Further enhancements to account for false data injection as well as to reduce computational complexity are left for future work.