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!
cited_by
cites
container_end_page
container_issue
container_start_page
container_title arXiv.org
container_volume
creator Li, Jingwang
Su, Housheng
description 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.
format article
fullrecord <record><control><sourceid>proquest</sourceid><recordid>TN_cdi_proquest_journals_2864708125</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2864708125</sourcerecordid><originalsourceid>FETCH-proquest_journals_28647081253</originalsourceid><addsrcrecordid>eNqNir0KwjAURoMgWLTvEHAupDf9W6UqOnVxL6G9YkpManKL0qe3gw_g9HHO-VYsAinTpMoANiwOYRBCQFFCnsuIHY7YoSWvjJ6x57WzYQFtKandNJpFNSPpp54VaWf5W9ODXy1-VEe88aozuGPruzIB499u2f58utWXZPTuNWGgdnCTt0tqoSqyUlQp5PK_1xfHWjn9</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2864708125</pqid></control><display><type>article</type><title>Decentralized Constraint-Coupled Optimization with Inexact Oracle</title><source>Publicly Available Content Database (Proquest) (PQ_SDU_P3)</source><creator>Li, Jingwang ; Su, Housheng</creator><creatorcontrib>Li, Jingwang ; Su, Housheng</creatorcontrib><description>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.</description><identifier>EISSN: 2331-8422</identifier><language>eng</language><publisher>Ithaca: Cornell University Library, arXiv.org</publisher><subject>Algorithms ; Controllability ; Convergence ; Graph theory ; Graphs ; Mathematical analysis ; Matrices (mathematics) ; Optimization ; Tracking</subject><ispartof>arXiv.org, 2023-10</ispartof><rights>2023. This work is published under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/2864708125?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>780,784,25753,37012,44590</link.rule.ids></links><search><creatorcontrib>Li, Jingwang</creatorcontrib><creatorcontrib>Su, Housheng</creatorcontrib><title>Decentralized Constraint-Coupled Optimization with Inexact Oracle</title><title>arXiv.org</title><description>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.</description><subject>Algorithms</subject><subject>Controllability</subject><subject>Convergence</subject><subject>Graph theory</subject><subject>Graphs</subject><subject>Mathematical analysis</subject><subject>Matrices (mathematics)</subject><subject>Optimization</subject><subject>Tracking</subject><issn>2331-8422</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2023</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><recordid>eNqNir0KwjAURoMgWLTvEHAupDf9W6UqOnVxL6G9YkpManKL0qe3gw_g9HHO-VYsAinTpMoANiwOYRBCQFFCnsuIHY7YoSWvjJ6x57WzYQFtKandNJpFNSPpp54VaWf5W9ODXy1-VEe88aozuGPruzIB499u2f58utWXZPTuNWGgdnCTt0tqoSqyUlQp5PK_1xfHWjn9</recordid><startdate>20231005</startdate><enddate>20231005</enddate><creator>Li, Jingwang</creator><creator>Su, Housheng</creator><general>Cornell University Library, arXiv.org</general><scope>8FE</scope><scope>8FG</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>HCIFZ</scope><scope>L6V</scope><scope>M7S</scope><scope>PIMPY</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope></search><sort><creationdate>20231005</creationdate><title>Decentralized Constraint-Coupled Optimization with Inexact Oracle</title><author>Li, Jingwang ; Su, Housheng</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-proquest_journals_28647081253</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2023</creationdate><topic>Algorithms</topic><topic>Controllability</topic><topic>Convergence</topic><topic>Graph theory</topic><topic>Graphs</topic><topic>Mathematical analysis</topic><topic>Matrices (mathematics)</topic><topic>Optimization</topic><topic>Tracking</topic><toplevel>online_resources</toplevel><creatorcontrib>Li, Jingwang</creatorcontrib><creatorcontrib>Su, Housheng</creatorcontrib><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Engineering Collection</collection><collection>Engineering Database</collection><collection>Publicly Available Content Database (Proquest) (PQ_SDU_P3)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering collection</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Li, Jingwang</au><au>Su, Housheng</au><format>book</format><genre>document</genre><ristype>GEN</ristype><atitle>Decentralized Constraint-Coupled Optimization with Inexact Oracle</atitle><jtitle>arXiv.org</jtitle><date>2023-10-05</date><risdate>2023</risdate><eissn>2331-8422</eissn><abstract>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.</abstract><cop>Ithaca</cop><pub>Cornell University Library, arXiv.org</pub><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier EISSN: 2331-8422
ispartof arXiv.org, 2023-10
issn 2331-8422
language eng
recordid cdi_proquest_journals_2864708125
source Publicly Available Content Database (Proquest) (PQ_SDU_P3)
subjects Algorithms
Controllability
Convergence
Graph theory
Graphs
Mathematical analysis
Matrices (mathematics)
Optimization
Tracking
title Decentralized Constraint-Coupled Optimization with Inexact Oracle
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-27T14%3A31%3A07IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=document&rft.atitle=Decentralized%20Constraint-Coupled%20Optimization%20with%20Inexact%20Oracle&rft.jtitle=arXiv.org&rft.au=Li,%20Jingwang&rft.date=2023-10-05&rft.eissn=2331-8422&rft_id=info:doi/&rft_dat=%3Cproquest%3E2864708125%3C/proquest%3E%3Cgrp_id%3Ecdi_FETCH-proquest_journals_28647081253%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2864708125&rft_id=info:pmid/&rfr_iscdi=true