Primal-Dual Methods for Saddle-Point Problems with Applications to Decentralized Constrained Convex Optimization

Open Access
Author:
Yazdandoost Hamedani, Erfan
Graduate Program:
Industrial Engineering
Degree:
Doctor of Philosophy
Document Type:
Dissertation
Date of Defense:
June 05, 2020
Committee Members:
  • Necdet S Aybat, Dissertation Advisor/Co-Advisor
  • Necdet S Aybat, Committee Chair/Co-Chair
  • Vinayak V Shanbhag, Committee Member
  • Xingyuan Fang, Committee Member
  • Constantino Manuel Lagoa, Outside Member
  • Ling Rothrock, Program Head/Chair
Keywords:
  • saddle-point problem
  • primal-dual algorithm
  • decentralized optimization
  • convex optimization
  • time-varying network
Abstract:
Saddle-point (SP) problems form an important class of computational problems with the aim of minimizing a function over one variable while maximizing over the other. This setting captures a wider class of problems than optimization problems. In particular, when the objective function is convex-concave, it includes convex optimization problems with nonlinear conic constraints as a special case, which itself includes LP, QP, QCQP, SOCP, and SDP as its subclasses. One of the goals of this thesis is to develop efficient and practical first-order methods to solve convex-concave SP problems. The next part of this thesis is dedicated to addressing the challenge of solving distributed optimization problems over communication networks consisting of agents with computational capabilities. In these problems, the information/data are privately owned by the agents and the main goal is for agents to collaboratively find an optimal solution that every agent agrees on by communicating with their neighbors only. Based on the primal-dual method developed in the first part of the thesis, we develop efficient first-order algorithms to solve distributed resource allocation and constrained consensus optimization problems. In the first part, we begin by proposing a primal-dual algorithm with a new momentum term based on partial gradient extrapolation to solve convex-concave SP problems. More importantly, we consider SP problems with a general coupling term that is not assumed to be bilinear; therefore, when compared to the significant majority of related work on primal-dual methods in the literature, our research captures a broader range of SP problems with nonlinear coupling terms, e.g., robust classification, distance metric learning, and kernel matrix learning. One of the main obstacles of implementing first-order algorithms is their dependency on some global parameters that might be unavailable, e.g., Lipschitz constants of the partial gradients. Using a backtracking line-search method we are able to estimate local Lipschitz constants obviating the need for knowing global Lipschitz constants. Through a powerful yet simple analysis, we demonstrate some unified results on the convergence of the proposed method. In particular, we obtain some optimal convergence rate results under both convex and semi-strongly convex settings. In the second part, we then consider cooperative multi-agent resource sharing and consensus optimization problems over both static and time-varying communication networks (with possibly directed edges), where only local communications between neighboring agents are allowed. For both problems, to handle the challenge arising due to time-varying communication networks, the following two key ideas are adopted: (i) A novel formulation of the problem in terms of a consensus set which is independent of the network topology; (ii) Suitably increasing the communication rounds in the course of algorithms to control the error inherited by the disagreements among the nods. More specifically, in a multi-agent resource sharing problem, the objective is to minimize the sum of agent-specific composite convex functions subject to a conic constraint coupling the agents’ decisions. We propose a decentralized variant of the primal-dual algorithm proposed in the first part of the thesis to solve the saddle-point formulation of the sharing problem on static and time-varying (un)directed communication networks; we show that the decentralized primal-dual iterate sequence converges to an SP defined by a primal optimal solution and a consensual dual price for the coupling constraint. Furthermore, we provide optimal iteration complexities in terms of suboptimality, infeasibility, and consensus violation of agents’ dual price assessments. For all proposed algorithms we examine the effect of underlying network topology on the convergence rates of the proposed decentralized algorithm. Moreover, in multi-agent constrained consensus optimization, the objective is to minimize the sum of agent-specific (possibly non-smooth) composite convex functions over agent-specific private (non)linear conic constraint sets; hence, the optimal consensus decision should lie in the intersection of these private sets. Depending on the sum function is either merely convex or strongly convex, we propose decentralized variants of the primal-dual algorithm developed in the first part to solve these problems. For these decentralized algorithms, we also provide convergence rates in terms of sub-optimality, infeasibility, and consensus violation with optimal iteration complexity matching the known lower complexity bounds. Overall, we demonstrate that all the proposed algorithms presented in this thesis enjoy optimal convergence rate guarantees for the problem classes considered, and superiority of the methods have been verified through numerical tests on several real-world problems.