skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Alternating Direction Method of Multipliers for Decomposable Saddle-Point Problems
Saddle-point problems appear in various settings including machine learning, zero-sum stochastic games, and regression problems. We consider decomposable saddle-point problems and study an extension of the alternating direction method of multipliers to such saddle-point problems. Instead of solving the original saddle-point problem directly, this algorithm solves smaller saddle-point problems by exploiting the decomposable structure. We show the convergence of this algorithm for convex-concave saddle-point problems under a mild assumption. We also provide a sufficient condition for which the assumption holds. We demonstrate the convergence properties of the saddle-point alternating direction method of multipliers with numerical examples on a power allocation problem in communication channels and a network routing problem with adversarial costs.  more » « less
Award ID(s):
1652113
PAR ID:
10399778
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton)
Page Range / eLocation ID:
1 to 8
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. (, 2023 IEEE Statistical Signal Processing Workshop (SSP))
    We consider the problem of inferring the conditional independence graph (CIG) of a sparse, high-dimensional, stationary matrix-variate Gaussian time series. All past work on matrix graphical models assume that i.i.d. observations of matrix-variate are available. Here we allow dependent observations. We consider a sparse-group lasso based frequency-domain formulation of the problem with a Kronecker-decomposable power spectral density (PSD), and solve it via an alternating direction method of multipliers (ADMM) approach. The problem is bi-convex which is solved via flip-flop optimization. We provide sufficient conditions for local convergence in the Frobenius norm of the inverse PSD estimators to the true value. This results also yields a rate of convergence. We illustrate our approach using numerical examples. 
    more » « less
  2. (, IEEE Transactions on Signal Processing)
    We consider the problem of inferring the conditional independence graph (CIG) of a sparse, high-dimensional, stationary matrix-variate Gaussian time series. All past work on high-dimensional matrix graphical models assumes that independent and identically distributed (i.i.d.) observations of the matrix-variate are available. Here we allow dependent observations. We consider a sparse-group lasso-based frequency-domain formulation of the problem with a Kronecker-decomposable power spectral density (PSD), and solve it via an alternating direction method of multipliers (ADMM) approach. The problem is biconvex which is solved via flip-flop optimization. We provide sufficient conditions for local convergence in the Frobenius norm of the inverse PSD estimators to the true value. This result also yields a rate of convergence. We illustrate our approach using numerical examples utilizing both synthetic and real data. 
    more » « less
  3. ; (, ArXivorg)
    Distributed optimization, where the computations are performed in a localized and coordinated manner using multiple agents, is a promising approach for solving large-scale optimization problems, e.g., those arising in model predictive control (MPC) of large-scale plants. However, a distributed optimization algorithm that is computationally efficient, globally convergent, amenable to nonconvex constraints and general inter-subsystem interactions remains an open problem. In this paper, we combine three important modifications to the classical alternating direction method of multipliers (ADMM) for distributed optimization. Specifically, (i) an extra-layer architecture is adopted to accommodate nonconvexity and handle inequality constraints, (ii) equality-constrained nonlinear programming (NLP) problems are allowed to be solved approximately, and (iii) a modified Anderson acceleration is employed for reducing the number of iterations. Theoretical convergence towards stationary solutions and computational complexity of the proposed algorithm, named ELLADA, is established. Its application to distributed nonlinear MPC is also described and illustrated through a benchmark process system. 
    more » « less
  4. ; ; (, IEEE Transactions on Smart Grid)
    The electric power distribution network (PDN) and the transportation network (TN) are generally operated/coordinated by different entities. However, they are coupled through electric vehicle charging stations (EVCSs). This paper proposes to coordinate the operation of the two systems via a fully decentralized framework where the PDN and TN operators solve their own operation problems independently, with only limited information exchange. Nevertheless, the operation problems of both systems are generally mixed-integer programs (MIP), for which mature algorithms like the alternating direction method of multipliers (ADMM) may not guarantee convergence. This paper applies a novel distributed optimization algorithm called the SD-GS-AL method, which is a combination of the simplicial decomposition, gauss-seidel, and augmented Lagrangian, which can guarantee convergence and optimality for MIPs. However, the original SD-GS-AL may be computationally inefficient for solving a complex engineering problem like the PDN-TN coordinated optimization investigated in this paper. To improve the computational efficiency, an enhanced SD-GS-AL method is proposed by redesigning the inner loop of the algorithm, which can automatically and intelligently determine the iteration number of the inner loop. Simulations on the test cases show the efficiency and efficacy of the proposed framework and algorithm. 
    more » « less
  5. ; (, 2019 IEEE 29th International Workshop on Machine Learning for Signal Processing (MLSP))
    In this paper we propose a quasi-Newton algorithm for the celebrated nonnegative matrix factorization (NMF) problem. The proposed algorithm falls into the general framework of Gauss-Newton and Levenberg-Marquardt methods. However, these methods were not able to handle constraints, which is present in NMF. One of the key contributions in this paper is to apply alternating direction method of multipliers (ADMM) to obtain the iterative update from this Gauss-Newton-like algorithm. Furthermore, we carefully study the structure of the Jacobian Gramian matrix given by the Gauss-Newton updates, and designed a way of exactly inverting the matrix with complexity $$\cO(mnk)$$, which is a significant reduction compared to the naive implementation of complexity $$\cO((m+n)^3k^3)$$. The resulting algorithm, which we call NLS-ADMM, enjoys fast convergence rate brought by the quasi-Newton algorithmic framework, while maintaining low per-iteration complexity similar to that of alternating algorithms. Numerical experiments on synthetic data confirms the efficiency of our proposed algorithm. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email