Convergence rate analysis of randomized and cyclic coordinate descent for convex optimization through semidefinite programming

Hadi Abbaszadehpeivasti; Etienne de Klerk; Moslem Zamani

doi:10.23952/asvao.5.2023.2.02

Convergence rate analysis of randomized and cyclic coordinate descent for convex optimization through semidefinite programming

Research output: Contribution to journal › Article › Scientific › peer-review

153 Downloads (Pure)

Abstract

In this paper, we study randomized and cyclic coordinate descent for convex unconstrained optimization problems. We improve the known convergence rates in some cases by using the numerical semidefinite programming performance estimation method. As a spin-off we provide a method to analyse the worst-case performance of the Gauss-Seidel iterative method for linear systems where the coefficient matrix is positive semidefinite with a positive diagonal.

Original language	English
Pages (from-to)	141-153
Number of pages	13
Journal	Applied Set-Valued Analysis and Optimization
Volume	5
Issue number	2
DOIs	https://doi.org/10.23952/asvao.5.2023.2.02
Publication status	Published - Aug 2023

Keywords

Cyclic and randomized coordinate descent
Gauss-Seidel method
Semidefinite programming

Access to Document

10.23952/asvao.5.2023.2.02

coordinate descent ASVAO-TemplateAccepted author manuscript, 307 KB

Cite this

@article{88512ac0c26a4a99b8403171c0eef17b,

title = "Convergence rate analysis of randomized and cyclic coordinate descent for convex optimization through semidefinite programming",

abstract = "In this paper, we study randomized and cyclic coordinate descent for convex unconstrained optimization problems. We improve the known convergence rates in some cases by using the numerical semidefinite programming performance estimation method. As a spin-off we provide a method to analyse the worst-case performance of the Gauss-Seidel iterative method for linear systems where the coefficient matrix is positive semidefinite with a positive diagonal.",

keywords = "Cyclic and randomized coordinate descent, Gauss-Seidel method, Semidefinite programming",

author = "Hadi Abbaszadehpeivasti and \{de Klerk\}, Etienne and Moslem Zamani",

note = "Publisher Copyright: {\textcopyright} 2023 Author(s).",

year = "2023",

month = aug,

doi = "10.23952/asvao.5.2023.2.02",

language = "English",

volume = "5",

pages = "141--153",

journal = "Applied Set-Valued Analysis and Optimization",

issn = "2562-7775",

publisher = "Biemdas",

number = "2",

}

TY - JOUR

T1 - Convergence rate analysis of randomized and cyclic coordinate descent for convex optimization through semidefinite programming

AU - Abbaszadehpeivasti, Hadi

AU - de Klerk, Etienne

AU - Zamani, Moslem

PY - 2023/8

Y1 - 2023/8

N2 - In this paper, we study randomized and cyclic coordinate descent for convex unconstrained optimization problems. We improve the known convergence rates in some cases by using the numerical semidefinite programming performance estimation method. As a spin-off we provide a method to analyse the worst-case performance of the Gauss-Seidel iterative method for linear systems where the coefficient matrix is positive semidefinite with a positive diagonal.

AB - In this paper, we study randomized and cyclic coordinate descent for convex unconstrained optimization problems. We improve the known convergence rates in some cases by using the numerical semidefinite programming performance estimation method. As a spin-off we provide a method to analyse the worst-case performance of the Gauss-Seidel iterative method for linear systems where the coefficient matrix is positive semidefinite with a positive diagonal.

KW - Cyclic and randomized coordinate descent

KW - Gauss-Seidel method

KW - Semidefinite programming

UR - https://www.scopus.com/pages/publications/85168091071

U2 - 10.23952/asvao.5.2023.2.02

DO - 10.23952/asvao.5.2023.2.02

M3 - Article

SN - 2562-7775

VL - 5

SP - 141

EP - 153

JO - Applied Set-Valued Analysis and Optimization

JF - Applied Set-Valued Analysis and Optimization

IS - 2

ER -

Convergence rate analysis of randomized and cyclic coordinate descent for convex optimization through semidefinite programming

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this