Distributed Optimization Approaches to Nonconvex Problems
Open Access
- Author:
- Ashour, Mahmoud
- Graduate Program:
- Electrical Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- October 14, 2020
- Committee Members:
- Constantino Manuel Lagoa, Dissertation Advisor/Co-Advisor
Constantino Manuel Lagoa, Committee Chair/Co-Chair
George Kesidis, Committee Member
Minghui Zhu, Committee Member
Necdet S Aybat, Outside Member
Kultegin Aydin, Program Head/Chair - Keywords:
- Distributed Optimization
Nonconvex Problems
Network Flow Control
Sparsity - Abstract:
- Applications of optimization theory are ubiquitous. Many applications in different fields heavily rely on efficiently solving optimization problems. Although such problems have their unique challenges as dictated by the specific application and field, many face common challenges: nonconvexity and the curse of dimensionality. This work proposes methods for handling these challenges in a variety of applications. Nonconvexity is handled either via developing convex relaxations whose solutions approximate those of the original nonconvex problems, or via developing heuristic methods that perform educated search in the space of feasible decision variables. Moreover, this work focuses on developing efficient algorithms for solving large scale optimization problems. In particular, we propose algorithms that decompose high dimensional optimization problems into several moderate size subproblems that can be handled by multiple nodes connected over some graph; hence, distributing the required computational effort. Decentralized message passing algorithms naturally emerge. An application of interest considered in this thesis is network traffic engineering. We propose decentralized algorithms for end-to-end and hop-by-hop flow control in communication networks. We aim at distributing the traffic among available routes such that the network utility is maximized. In practical applications, modeling network utility using nonconcave functions is of particular interest, e.g., video streaming. Therefore, we tackle the problem of optimizing a general class of nonconcave utility functions. The approach used to solve the resulting nonconvex network utility maximization problem relies on designing a sequence of convex relaxations whose solutions converge to a point that characterizes an optimal solution of the original problem. Distributed algorithms are proposed for the solution of the convex relaxation. Each node independently controls its traffic in a way that drives the overall network traffic allocation to an optimal operating point subject to network capacity constraints. All computations required by the algorithms are performed independently and locally at each node using local information and minimal communication overhead. For the proposed end-to-end flow control algorithms, the only nonlocal information needed is feedback that sources receive from intermediate network nodes related to the status of the links. However, for the proposed hop-by-hop flow control algorithm, information exchange is only required among immediate neighbors. The robustness of the proposed algorithms is demonstrated, where the traffic is shown to be automatically rerouted in case of a link failure or having new users joining the network. Numerical simulations are presented to validate our findings. Another application considered in this thesis is the optimal power flow problem in the presence of renewable sources and uncertain loads in a power network. The objective is to minimize a certain cost of power generation subject to probabilistically matching the power generated to that consumed by the loads. The randomness originating from renewable sources and variable loads is tackled via a technique called scenario with certificates. A distributed solution methodology is proposed through formulating the problem as a consensus nonconvex optimization problem, and employing a proximal gradient ADMM algorithm. The algorithm requires that each node performs locally a projection onto a nonconvex set via solving a quadratically constrained quadratic program. We derive lower bounds on the optimal value of the nonconvex projection problem using duality and semidefinite relaxation. Furthermore, we propose heuristic methods based on sequential convex programming and convex-concave programming that produce feasible and locally optimal points for the nonconvex projection problem. Preliminary numerical results are shown to validate our findings. We also develop a method for $\ell_{p}$ quasi-norm minimization, i.e., 0 < p < 1, where the Lp quasi-norm is used as a sparsity inducing function. The proposed method is based on a two-block ADMM algorithm. For p=s/q<1, the proposed algorithm requires solving for the roots of a scalar degree 2q polynomial for each entry of the decision variable as opposed to applying a soft thresholding operator in the case of L1. We show numerical results for two example applications, sparse signal reconstruction from few noisy measurements and spam email classification using support vector machines. Our method obtains significantly sparser solutions than those obtained by L1 minimization while achieving similar level of measurement fitting in signal reconstruction, and training and test set accuracy in classification.