We present a proximal quasi-Newton method in which the approximation of the Hessian has the special format of “identity minus rank one” (IMRO) in each iteration. The proposed structure enables us to effectively recover the proximal point. The algorithm is applied to @math -regularized least squares problems arising in many applications including sparse recovery in compressive sensing, machine learning, and statistics. Our numerical experiment suggests that the proposed technique competes favorably with other state-of-the-art solvers for this class of problems. We also provide a complexity analysis for variants of IMRO, showing that it matches known best bounds.
The alternating direction method (ADM) is also a technique that can be applied to @math , see @cite_17 @cite_10 and references therein. It is suited for minimizing the summation of (separable) convex functions, say @math , over a linear set of constraints. The augmented Lagrangian technique then solves for @math and @math alternately while fixing the other variable. The alternating linearization method (ALM) @cite_18 also applies to minimizing composite functions. In , we linearize @math at every iteration to build the quadratic approximation model; in ALM a similar model based on @math is also minimized at every iteration. Nesterov's accelerated technique has also been adopted, and the resulting algorithm is called FALM, for fast ALM.
@cite_18 @cite_10 @cite_17
2076261573 2295652899 2111076441 1923817890
Alternating direction methods are a common tool for general mathematical programming and optimization. These methods have become particularly important in the field of variational image processing, which frequently requires the minimization of nondifferentiable objectives. This paper considers accelerated (i.e., fast) variants of two common alternating direction methods: the alternating direction method of multipliers (ADMM) and the alternating minimization algorithm (AMA). The proposed acceleration is of the form first proposed by Nesterov for gradient descent methods. In the case that the objective function is strongly convex, global convergence bounds are provided for both classical and accelerated variants of the methods. Numerical examples are presented to demonstrate the superior performance of the fast methods for a wide variety of problems. The alternating direction method of multipliers (ADMM) is widely used to solve large-scale linearly constrained optimization problems, convex or nonconvex, in many engineering fields. However there is a general lack of theoretical understanding of the algorithm when the objective function is nonconvex. In this paper we analyze the convergence of the ADMM for solving certain nonconvex consensus and sharing problems. We show that the classical ADMM converges to the set of stationary solutions, provided that the penalty parameter in the augmented Lagrangian is chosen to be sufficiently large. For the sharing problems, we show that the ADMM is convergent regardless of the number of variable blocks. Our analysis does not impose any assumptions on the iterates generated by the algorithm and is broadly applicable to many ADMM variants involving proximal update rules and various flexible block selection rules. The alternating direction method of multipliers (ADMM) has been widely used for solving structured convex optimization problems. In particular, the ADMM can solve convex programs that minimize the sum of @math convex functions whose variables are linked by some linear constraints. While the convergence of the ADMM for @math was well established in the literature, it remained an open problem for a long time whether the ADMM for @math is still convergent. Recently, it was shown in [, Math. Program. (2014), DOI 10.1007 s10107-014-0826-5.] that without additional conditions the ADMM for @math generally fails to converge. In this paper, we show that under some easily verifiable and reasonable conditions the global linear convergence of the ADMM when @math can still be ensured, which is important since the ADMM is a popular method for solving large-scale multiblock optimization models and is known to perform very well in practice even when @math . Our study aims to offer an explanation for... The alternating direction method with multipliers (ADMM) has been one of most powerful and successful methods for solving various convex or nonconvex composite problems that arise in the fields of image & signal processing and machine learning. In convex settings, numerous convergence results have been established for ADMM as well as its varieties. However, due to the absence of convexity, the convergence analysis of nonconvex ADMM is generally very difficult. In this paper we study the Bregman modification of ADMM (BADMM), which includes the conventional ADMM as a special case and often leads to an improvement of the performance of the algorithm. Under certain assumptions, we prove that the iterative sequence generated by BADMM converges to a stationary point of the associated augmented Lagrangian function. The obtained results underline the feasibility of ADMM in applications under nonconvex settings.