We consider in this paper a class of composite optimization problems whose objective function is given by the summation of a general smooth and nonsmooth component, together with a relatively simple nonsmooth term. We present a new class of first-order methods, namely the gradient sliding algorithms, which can skip the computation of the gradient for … Read more
Recently, a strictly contractive Peaceman- Rachford splitting method (SC-PRSM) was proposed to solve a convex minimization model with linear constraints and a separable objective function which is the sum of two functions without coupled variables. We show by an example that the SC-PRSM cannot be directly extended to the case where the objective function is … Read more
In this paper, we present a convergence rate analysis for the inexact Krasnosel’ski{\u{\i}}-Mann iteration built from nonexpansive operators. Our results include two main parts: we first establish global pointwise and ergodic iteration-complexity bounds, and then, under a metric subregularity assumption, we establish local linear convergence for the distance of the iterates to the set of … Read more
In the context of convex optimization problems in Hilbert spaces, we induce inertial effects into the classical ADMM numerical scheme and obtain in this way so-called inertial ADMM algorithms, the convergence properties of which we investigate into detail. To this aim we make use of the inertial version of the Douglas-Rachford splitting method for monotone … Read more
We present a novel framework, namely AADMM, for acceleration of linearized alternating direction method of multipliers (ADMM). The basic idea of AADMM is to incorporate a multi-step acceleration scheme into linearized ADMM. We demonstrate that for solving a class of convex composite optimization with linear constraints, the rate of convergence of AADMM is better than … Read more
This paper presents an algorithm for approximately minimizing a convex function in simple, not necessarily bounded convex domains, assuming only that function values and subgradients are available. No global information about the objective function is needed apart from a strong convexity parameter (which can be put to zero if only convexity is known). The worst … Read more
A sharp upper bound on the probability of a random vector falling outside a polytope, based solely on the first and second moments of its distribution, can be computed efficiently using semidefinite programming. However, this Chebyshev-type bound tends to be overly conservative since it is determined by a discrete worst-case distribution. In this paper we … Read more
The augmented Lagrangian method (ALM) is a benchmark for solving convex minimization problems with linear constraints. When the objective function of the model under consideration is representable as the sum of some functions without coupled variables, a Jacobian or Gauss-Seidel decomposition is often implemented to decompose the ALM subproblems so that the functions’ properties could … Read more
Recently several methods were proposed for sparse optimization which make careful use of second-order information [11, 30, 17, 3] to improve local convergence rates. These methods construct a composite quadratic approximation using Hessian information, optimize this approximation using a first-order method, such as coordinate descent and employ a line search to ensure sufficient descent. Here … Read more
In this paper, we analyze the iteration-complexity of a generalized forward-backward (GFB) splitting algorithm, recently proposed in~\cite{gfb2011}, for minimizing the large class of composite objectives $f + \sum_{i=1}^n h_i$ on a Hilbert space, where $f$ has a Lipschitz-continuous gradient and the $h_i$’s are simple (i.e. whose proximity operator is easily computable ). We derive iteration-complexity … Read more