ProV Logo
0
Construction and Iteration-Complexity of...
Tran-Dinh, Quoc...

Free

Construction and Iteration-Complexity of Primal Sequences in Alternating Minimization Algorithms by Tran-Dinh, Quoc ( Author )
Lemonjar Open Access
Australian National University
29-08-2023
We introduce a new weighted averaging scheme using "Fenchel-type" operators to recover primal solutions in the alternating minimization-type algorithm (AMA) for prototype constrained convex optimization. Our approach combines the classical AMA idea in \cite{Tseng1991} and Nesterov's prox-function smoothing technique without requiring the strong convexity of the objective function. We develop a new non-accelerated primal-dual AMA method and estimate its primal convergence rate both on the objective residual and on the feasibility gap. Then, we incorporate Nesterov's accelerated step into this algorithm and obtain a new accelerated primal-dual AMA variant endowed with a rigorous convergence rate guarantee. We show that the worst-case iteration-complexity in this algorithm is optimal (in the sense of first-oder black-box models), without imposing the full strong convexity assumption on the objective.
-
Article
pdf
30.00 KB
English
-
MYR 0.01
-
http://arxiv.org/abs/1511.03305
Share this eBook