Exploring Power System Solvers
In Fall 2020, I took a class called ECE 530: Analysis Techniques for Large-Scale Electric Systems with Prof. Richard Zhang. In this class, we explored a variety of techniques used for analyzing power systems and power flow. For our final project, we had to implement an advanced power system solver from scratch, and show that it improved on performance compared to the traditional Newton-Raphson method.
The Newton-Raphson method is known for its quadratic convergence near a solution; even large, realistic systems can usually converge within 5 iterations. Despite the high time (O(n3)) and space (O(n2)) requirements, Newton-Raphson is still one of the most favored methods for power flow solutions. Its biggest weakness is the sensitivity to initial conditions in the ability to find a solution. As initial conditions and sensitivity of the system changes, Newton-Raphson is susceptible to diverge. In my term project, I showed that the Newton-Raphson method is equivalent to a least-squares problem and can be made more robust by implementing a backtracking line search. I showed that the Newton-Raphson direction is a guaranteed descent direction, and then showed how to find a step size that guarantees that the step size results in shrinking the problem towards the least-squares solution. This added robustness finds solutions where Newton-Raphson cannot, and has very good time performance when the true solution is found.
This added robustness comes with only small time increases (<5%) for small cases, and acceptable time increases (20-50%) for large cases. This time is largely due to the increased number of steps taken during backtracking, which occurs because step sizes may be smaller, but they are guaranteed to be in a good direction. With hardware acceleration, modern computing hardware, and other optimization techniques available, using the Newton-Raphson backtracking method is well worth the time tradeoffs it incurs.
You can read my full report below.