Difference-of-Convex (DC) minimization, referring to the problem of minimizing the difference of two convex functions, has been found rich applications in statistical learning and studied extensively for decades. However, existing methods are primarily based on multi-stage convex relaxation, only leading to weak optimality of critical points. This paper proposes a coordinate descent method for minimizing DC functions based on sequential nonconvex approximation. Our approach iteratively solves a nonconvex one-dimensional subproblem globally, and it is guaranteed to converge to a coordinate-wise stationary point. We prove that this new optimality condition is always stronger than the critical point condition and the directional point condition when the objective function is weakly convex. For comparisons, we also include a naive variant of coordinate descent methods based on sequential convex approximation in our study. When the objective function satisfies an additional regularity condition called emph{sharpness}, coordinate descent methods with an appropriate initialization converge emph{linearly} to the optimal solution set. Also, for many applications of interest, we show that the nonconvex one-dimensional subproblem can be computed exactly and efficiently using a breakpoint searching method. We present some discussions and extensions of our proposed method. Finally, we have conducted extensive experiments on several statistical learning tasks to show the superiority of our approach. Keywords: Coordinate Descent, DC Minimization, DC Programming, Difference-of-Convex Programs, Nonconvex Optimization, Sparse Optimization, Binary Optimization.
Optimal power flow (OPF) is the fundamental mathematical model in power system operations. Improving the solution quality of OPF provide huge economic and engineering benefits. The convex reformulation of the original nonconvex alternating current OPF (ACOPF) model gives an efficient way to find the global optimal solution of ACOPF but suffers from the relaxation gaps. The existence of relaxation gaps hinders the practical application of convex OPF due to the AC-infeasibility problem. We evaluate and improve the tightness of the convex ACOPF model in this paper. Various power networks and nodal loads are considered in the evaluation. A unified evaluation framework is implemented in Julia programming language. This evaluation shows the sensitivity of the relaxation gap and helps to benchmark the proposed tightness reinforcement approach (TRA). The proposed TRA is based on the penalty function method which penalizes the power loss relaxation in the objective function of the convex ACOPF model. A heuristic penalty algorithm is proposed to find the proper penalty parameter of the TRA. Numerical results show relaxation gaps exist in test cases especially for large-scale power networks under low nodal power loads. TRA is effective to reduce the relaxation gap of the convex ACOPF model.
This paper proposes to use stochastic conic programming to address the challenge of large-scale wind power integration to the power system. Multiple wind farms are connected through the voltage source converter (VSC) based multi-terminal DC (VSC-MTDC) system to the power network supported by the Flexible AC Transmission System (FACTS). The optimal operation of the power network incorporating the VSC-MTDC system and FACTS devices is formulated in a stochastic conic programming framework accounting the uncertainties of the wind power generation. A methodology to generate representative scenarios of power generations from the wind farms is proposed using wind speed measurements and wind turbine models. The nonconvex transmission network constraints including the VSC-MTDC system and FACTS devices are convexified through the proposed second-order cone AC optimal power flow model (SOC-ACOPF) that can be solved to the global optimality using interior point method. In order to tackle the computational challenge due to the large number of wind power scenarios, a modified Benders decomposition algorithm (M-BDA) accelerated by parallel computation is proposed. The energy dispatch of conventional power generators is formulated as the master problem of M-BDA. Numerical results for up to 50000 wind power scenarios show that the proposed M-BDA approach to solve stochastic SOC-ACOPF outperforms the traditional single-stage (without decomposition) solution approach in both convergence capability and computational efficiency. The feasibility performance of the proposed stochastic SOC-ACOPF model is also demonstrated.
Nonsmooth sparsity constrained optimization captures a broad spectrum of applications in machine learning and computer vision. However, this problem is NP-hard in general. Existing solutions to this problem suffer from one or more of the following limitations: they fail to solve general nonsmooth problems; they lack convergence analysis; they lead to weaker optimality conditions. This paper revisits the Penalty Alternating Direction Method (PADM) for nonsmooth sparsity constrained optimization problems. We consider two variants of the PADM, i.e., PADM based on Iterative Hard Thresholding (PADM-IHT) and PADM based on Block Coordinate Decomposition (PADM-BCD). We show that the PADM-BCD algorithm finds stronger stationary points of the optimization problem than previous methods. We also develop novel theories to analyze the convergence rate for both the PADM-IHT and the PADM-BCD algorithms. Our theoretical bounds can exploit the inherent sparsity of the optimization problem. Finally, numerical results demonstrate the superiority of PADM-BCD to existing sparse optimization algorithms. Keywords: Sparsity Recovery, Nonsmooth Optimization, Non-Convex Optimization, Block Coordinate Decomposition, Iterative Hard Thresholding, Convergence Analysis
Frequency response and voltage support are vital ancillary services for power grids. In this paper, we design and experimentally validate a real-time control framework for battery energy storage systems (BESSs) to provide ancillary services to power grids. The objective of the control system is to utilize the full capability of the BESSs to provide ancillary services. We take the voltage-dependent capability curve of the DC-AC converter and the security requirements of BESSs as constraints of the control system. The initial power set-points are obtained based on the droop control approach. To guarantee the feasibility of the power set-points with respect to both the converter capability and BESS security constraints, the final power set-points calculation is formulated as a nonconvex optimization problem. A convex and computationally efficient reformulation of the original control problem is then proposed. We prove that the proposed convex optimization gives the global optimal solution to the original nonconvex problem. We improve the computational performance of this algorithm by discretizing the feasible region of the optimization model. We achieve a 100 ms update time of the controller setpoint computation in the experimental validation of the utility-scale 720 kVA / 560 kWh BESS on the EPFL campus.
We give the definition of s-Vector control by using the complex power vector in the p-q plane to quantify the feasible operational region of battery energy storage system (BESS) and to find the optimal power set-point solution. The s-Vector control features in the avoidance of using costly optimization solvers to solve optimization models online which is also an execution time bottleneck in real-time control. The advantages of s-Vector control are fast and stable computational efficiency. We validate a s-Vector based real-time controller of BESS to provide frequency response and voltage support as ancillary services for the power grid. The objective is to maximize the utility of the BESS asset. We formulate the dynamic capability curve of the DC-AC converter and the security requirements of the battery cells as constrains of the control system. The initial power set-points are obtained based on the traditional droop control approach. Based on s-Vector control, a fast optimization solution algorithm is proposed to find the optimal power set-point and guarantee the security. According to the experimental validation in our 720 kVA / 560 kWh BESS on EPFL campus, we achieve 100 ms of refreshing the real-time control loop. As a benchmark, using optimization solver requires 200 ms to update the real-time control loop.
This paper proposes a control method for battery energy storage systems (BESSs) to provide concurrent primary frequency and local voltage regulation services. The actual variable active and reactive power capability of the converter, along with the state-of-charge of the BESS, are jointly considered by the optimal operating point calculation process within the real-time operation. The controller optimizes the provision of grid services, considering the measured grid and battery statuses and predicting the battery DC voltage as a function of the current trajectory using a three-time-constant model (TTC). A computationally-efficient algorithm is proposed to solve the formulated optimal control problem. Experimental tests validate the proposed concepts and show the effectiveness of the employed control framework on a commercial utility-scale 720 kVA/560 kWh BESS.
We derive the branch ampacity constraint associated to power losses for the convex optimal power flow (OPF) model based on the branch flow formulation. The branch ampacity constraint derivation is motivated by the physical interpretation of the transmission line {Pi}-model and practical engineering considerations. We rigorously prove and derive: (i) the loop constraint of voltage phase angle, required to make the branch flow model valid for meshed power networks, is a relaxation of the original nonconvex alternating current optimal power flow (o-ACOPF) model; (ii) the necessary conditions to recover a feasible solution of the o-ACOPF model from the optimal solution of the convex second-order cone ACOPF (SOC-ACOPF) model; (iii) the expression of the global optimal solution of the o-ACOPF model providing that the relaxation of the SOC-ACOPF model is tight; (iv) the (parametric) optimal value function of the o-ACOPF or SOC-ACOPF model is monotonic with regarding to the power loads if the objective function is monotonic with regarding to the nodal power generations; (v) tight solutions of the SOC-ACOPF model always exist when the power loads are sufficiently large. Numerical experiments using benchmark power networks to validate our findings and to compare with other convex OPF models, are given and discussed.
Sparse optimization is a central problem in machine learning and computer vision. However, this problem is inherently NP-hard and thus difficult to solve in general. Combinatorial search methods find the global optimal solution but are confined to small-sized problems, while coordinate descent methods are efficient but often suffer from poor local minima. This paper considers a new block decomposition algorithm that combines the effectiveness of combinatorial search methods and the efficiency of coordinate descent methods. Specifically, we consider a random strategy or/and a greedy strategy to select a subset of coordinates as the working set, and then perform a global combinatorial search over the working set based on the original objective function. We show that our method finds stronger stationary points than Amir Beck et al.s coordinate-wise optimization method. In addition, we establish the convergence rate of our algorithm. Our experiments on solving sparse regularized and sparsity constrained least squares optimization problems demonstrate that our method achieves state-of-the-art performance in terms of accuracy. For example, our method generally outperforms the well-known greedy pursuit method.
Composite function minimization captures a wide spectrum of applications in both computer vision and machine learning. It includes bound constrained optimization, $ell_1$ norm regularized optimization, and $ell_0$ norm regularized optimization as special cases. This paper proposes and analyzes a new Generalized Matrix Splitting Algorithm (GMSA) for minimizing composite functions. It can be viewed as a generalization of the classical Gauss-Seidel method and the Successive Over-Relaxation method for solving linear systems in the literature. Our algorithm is derived from a novel triangle operator mapping, which can be computed exactly using a new generalized Gaussian elimination procedure. We establish the global convergence, convergence rate, and iteration complexity of GMSA for convex problems. In addition, we also discuss several important extensions of GMSA. Finally, we validate the performance of our proposed method on three particular applications: nonnegative matrix factorization, $ell_0$ norm regularized sparse coding, and $ell_1$ norm regularized Dantzig selector problem. Extensive experiments show that our method achieves state-of-the-art performance in term of both efficiency and efficacy.
