composite convex optimization – Optimization Online

Optimal Nonergodic Primal-Dual Complexity of Efficient Inexact Parameter-Free Augmented Lagrangian Methods

Published: 2026/08/04, Updated: 2026/08/10

Augmented Lagrangian (AL) methods are a classical framework for constrained optimization, but for directly verifiable approximate KKT points, known first-order complexity bounds for standard inexact AL methods are suboptimal, while the best known proximal augmented Lagrangian (PAL) bounds retain an additional logarithmic factor. We consider linearly constrained convex composite problems with a smooth convex term … Read more

A Universally Optimal Primal-Dual Method for Minimizing Heterogeneous Compositions

Published: 2025/03/11, Updated: 2026/01/19

Constrained Nonlinear Optimization, Convex Optimization, Nonsmooth Optimization accelerated first-order methods, composite convex optimization, heterogeneous, optimal, universal method

This paper proposes a universal, optimal algorithm for convex minimization problems of the composite form $g_0(x)+h(g_1(x),\dots, g_m(x)) + u(x)$. We allow each $g_j$ to independently range from being nonsmooth Lipschitz to smooth, from convex to strongly convex, described by notions of H\”older continuous gradients and uniform convexity. Note that, although the objective is built from … Read more

Exact Worst-case Performance of First-order Methods for Composite Convex Optimization

Published: 2016/06/23, Updated: 2017/02/06

Convex Optimization, Nonsmooth Optimization composite convex optimization, conditional gradient, convergence rate, convex interpolation, ex- act worst-case analysis, first-order methods, optimized gradient method, performance estimation, proximal point algorithm, semidefinite programming

We provide a framework for computing the exact worst-case performance of any algorithm belonging to a broad class of oracle-based first-order methods for composite convex optimization, including those performing explicit, projected, proximal, conditional and inexact (sub)gradient steps. We simultaneously obtain tight worst-case guarantees and explicit instances of optimization problems on which the algorithm reaches this … Read more

Tight global linear convergence rate bounds for operator splitting methods

Published: 2016/03/10, Updated: 2019/01/18

Convex Optimization, Linear Programming averaged operator, composite convex optimization, error bound, friedrichs angle, global linear convergence, linear programming, linear regularity, operator splitting

In this paper we establish necessary and sufficient conditions for linear convergence of operator splitting methods for a general class of convex optimization problems where the associated fixed-point operator is averaged. We also provide a tight bound on the achievable convergence rate. Most existing results establishing linear convergence in such methods require restrictive assumptions regarding … Read more

An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems

Published: 2014/04/29

Convex Optimization, Generalized Convexity/Monoticity, Nonsmooth Optimization accelerated method, complexity, composite convex optimization, hybrid proximal extragradient, inexact proximal point method, monotone inclusion problem, saddle point problem, smoothing

This article proposes a new algorithm for solving a class of composite convex-concave saddle-point problems. The new algorithm is a special instance of the hybrid proximal extragradient framework in which a Nesterov’s accelerated variant is used to approximately solve the prox subproblems. One of the advantages of the new method is that it works for … Read more