Date of Award
Doctor of Philosophy
Electrical and Computer Engineering
This dissertation studies non-convex optimizations under the strong duality condition. In general, non-convex problems are non-deterministic polynomial-time (NP) hard and hence are difficult to solve. However, when strong duality holds, one can recover primal optimal solutions by efficiently solving their convex, associated Lagrange dual relaxations instead.
For certain non-convex optimizations, such as optimal power flow (OPF), phase recovery, and etc., it has been shown that strong duality holds under most circumstances. Consequently, their associated Lagrange dual problems, usually expressed in semi-definite programming (SDP) forms, have attracted the attention of researchers. However, we notice that these SDP Lagrange duals are in general not amenable to be solved in a distributed manner. To address this issue, we propose two distributed approaches in this dissertation to study those non-convex optimizations under the condition of strong duality.
Our first approach is called the continuous-time optimization dynamics approach. Rather than considering the Lagrange dual alone, this approach studies the primal and dual problems together at the same time. By viewing primal and dual variables of an optimization problem as opponents playing a min-max game, the evolution of the optimization dynamical system can be interpreted as a competition between two players. This competition will not stop until those players achieve a balance, which turns out to be an equilibrium to the optimization dynamics and is mathematically characterized as a Karush-Kuhn-Tucker (KKT) point.
A convergence analysis is then developed in this dissertation, showing that under certain conditions a KKT equilibrium of the associated optimization dynamics is locally asymptotically stable. However, after the optimization dynamics converges to a KKT equilibrium, we have to further check whether or not the obtained KKT point is globally optimal, since KKT conditions are only necessary for the local optimality of non-convex problems. It motivates us to investigate under what conditions a KKT point can be guaranteed as a global optimum.
Then in the dissertation we derive a global optimality condition for general quadratically constrained quadratic programmings (QCQPs). If an isolated KKT point of a general QCQP satisfies our condition, then it is locally asymptotically stable with respect to the optimization dynamics. We next apply the optimization dynamics approach to a special class of non-convex QCQPs, namely, the OPF problems. We discover that their associated optimization dynamical systems possess an intrinsic distributed structure. Simulations are also provided to show the effectiveness of our continuous-time optimization dynamics approach.
Alternatively, we also propose a consensus-based, decomposed SDP relaxation approach to solve OPF problems. Here we continue to exploit the distributed structure of power networks, which finally enables us to decompose the standard SDP relaxation into a bunch of smaller size SDPs. Then each bus in the power network should locally solve its own decomposed SDP relaxation and meanwhile a global OPF solution can be achieved by running a consensus over the whole power network. Hence this approach can be implemented in a distributed manner. We show that the size of our decomposed SDP relaxation scales linearly as the power network expands, so it can greatly fasten the OPF computation speed.
Ma, Xu, "Distributed approaches for solving non-convex optimizations under strong duality" (2016). Graduate Theses and Dissertations. 15769.