Decentralized Constraint-Coupled Optimization with Inexact Oracle

We propose an inexact decentralized dual gradient tracking method (iDDGT) for decentralized optimization problems with a globally coupled equality constraint. Unlike existing algorithms that rely on either the exact dual gradient or an inexact one obtained through single-step gradient descent, iDDGT...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-10
Main Authors: Li, Jingwang, Su, Housheng
Format: Article
Language:English
Subjects:
Algorithms
Controllability
Convergence
Graph theory
Graphs
Mathematical analysis
Matrices (mathematics)
Optimization
Tracking
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We propose an inexact decentralized dual gradient tracking method (iDDGT) for decentralized optimization problems with a globally coupled equality constraint. Unlike existing algorithms that rely on either the exact dual gradient or an inexact one obtained through single-step gradient descent, iDDGT introduces a new approach: utilizing an inexact dual gradient with controllable levels of inexactness. Numerical experiments demonstrate that iDDGT achieves significantly higher computational efficiency compared to state-of-the-art methods. Furthermore, it is proved that iDDGT can achieve linear convergence over directed graphs without imposing any conditions on the constraint matrix. This expands its applicability beyond existing algorithms that require the constraint matrix to have full row rank and undirected graphs for achieving linear convergence.
ISSN:2331-8422