A fast penalty-based Gauss-Seidel method for solving large-scale stochastic network constrained unit commitment problems

Abstract

The exponential growth of variable renewable energy (VRE) such as wind and solar generation brings grand challenges to the operational planning of power systems. The instantaneous penetration of VRE reaches over 50% in certain balancing areas in the United States. The VRE generation is characterized by a large amount of uncertainties and variabilities. Consequently, power system operators, planners and researchers have made substantial efforts to manage VRE uncertainties in the power system scheduling, such as Network-Constrained Unit Commitment (NCUC). In order to account for the impact of VRE uncertainties, there are several noteworthy NCUC approaches in the literature, each with distinctive objectives, theories, computational requirements and economic outcomes. A common approach presented in the literature is the use of stochastic programming, namely Stochastic NCUC (S-NCUC), in which the expected system operating cost is minimized across a number of scenarios, each representing a possible realization of uncertainties. S-NCUC is typically a large-scale, non-convex, and mixed-integer programming (MIP) problem. It is modeled as a two-stage stochastic problem where the first-stage unit commitment decisions are the same for all the scenarios. Generally, S-NCUC solutions can be categorized into two main approaches. First, the most straightforward approach is to use a commercially available off-the-shelf solver to solve an extensive form (EF) of S-NCUC. However, for any large-scale system with a reasonable number of scenarios, the resulting EF of SNCUC may become computationally intractable. To overcome this issue, the second approach is based on stage-wise or scenario-wise decomposition methods, which solve each individual scenario separately, usually in parallel, and a final solution is generated by coordinating all individual scenario solutions. Progressive Hedging Algorithm (PHA) is one of the main decomposition methods for solving the stochastic MIP. However, PHA is originally devised for a continuous convex program and is not provably convergent for the non-convex S-NCUC problem. The solution to the dual problem is generally primal infeasible and the once relaxed system-wide constraints may not be satisfied. An additional effort is required to restore the primal feasibility from a Lagrangian dual solution. Therefore, it is desirable to directly obtain a primally feasible solution from the Lagrangian dual iterations. This gives rise to exact augmented Lagrangian, a class of exact penalty methods whose objective is to solve a constrained optimization (primal) problem through an unconstrained optimization problem that has the same local (global) solutions as the primal problem. Nevertheless, the following two critical research questions remain unresolved:

How can we devise an effective penalty function such that an exact solution can be obtained with a zero-duality gap? If an exact solution is attained, how can we find a robust yet tight lower bound that is capable of measuring the quality of the exact solution accurately? This dissertation addresses the aforementioned first question by applying a novel Penalty- Based Gauss-Seidel (PBGS) algorithm with an exact augmented Lagrangian representation to solve S-NCUC within a scenario-based decomposition framework. To improve the computational efficiency of PBGS, an accelerating technique that skips solving scenarios meeting certain conditions has been proposed. The proposed algorithm is named “Fast PBGS.” A proof of the Fast PBGS method is given, along with the proof of convergence of PBGS. Numerical validation of these algorithms on the IEEE 118-bus and Electric Reliability Council of Texas (ERCOT)-like large-scale systems has been carried out. Fast PBGS saves computational time by an average 35% for ERCOT-like Large System and 50% for IEEE 118-bus System with 50 scenarios compared with PBGS. Numerical results demonstrate the high quality of the PBGS solution and the efficacy of the proposed algorithms. Additionally, comparing the proposed algorithms with other prevailing S-NCUC methods such as PHA and extensive-form-based MIP solutions has been completed. The comparison of Fast PBGS shows the results are closer to EF (average difference 0.92%) than the PHA solution with EF (average difference 2.18%). When it came to the computational time, the Fast PBGS outperformed both EF and PHA. An average Fast PBGS took 48% less time than EF to obtain a solution. Compared with PHA, Fast PBGS was 142% faster. The second question is addressed by applying the combined Frank Wolfe with PHA algorithm (FW-PHA). Our research shows that FW-PHA obtains superior lower bounds, i.e., up to 6% better than the PHA does on the IEEE 118-bus system. We further improve the computational efficiency of FW-PHA with a warm start technique that initializes the algorithm with a Fast PBGS solution. An out-of-sample analysis including a large number of samples is conducted to demonstrate the efficacy of the Fast PBGS.