EFIX: Exact fixed point methods for distributed optimization

Dušan Jakovetić, Nataša Krejić and Nataša Krklec Jerinkić ()
Additional contact information
Dušan Jakovetić: University of Novi Sad
Nataša Krejić: University of Novi Sad
Nataša Krklec Jerinkić: University of Novi Sad

Journal of Global Optimization, 2023, vol. 85, issue 3, No 5, 637-661

Abstract: Abstract We consider strongly convex distributed consensus optimization over connected networks. EFIX, the proposed method, is derived using quadratic penalty approach. In more detail, we use the standard reformulation—transforming the original problem into a constrained problem in a higher dimensional space—to define a sequence of suitable quadratic penalty subproblems with increasing penalty parameters. For quadratic objectives, the corresponding sequence consists of quadratic penalty subproblems. For generic strongly convex case, the objective function is approximated with a quadratic model and hence the sequence of the resulting penalty subproblems is again quadratic. EFIX is then derived by solving each of the quadratic penalty subproblems via a fixed point (R)-linear solver, e.g., Jacobi Over-Relaxation method. The exact convergence is proved as well as the worst case complexity of order $${{\mathcal {O}}}(\epsilon ^{-1})$$ O ( ϵ - 1 ) for the quadratic case. In the case of strongly convex generic functions, the standard result for penalty methods is obtained. Numerical results indicate that the method is highly competitive with state-of-the-art exact first order methods, requires smaller computational and communication effort, and is robust to the choice of algorithm parameters.

Keywords: Fixed point methods; Quadratic penalty method; Distributed optimization; Strongly convex problems (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-022-01221-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:85:y:2023:i:3:d:10.1007_s10898-022-01221-4

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-022-01221-4

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().