Search

This work presents a novel analysis that allows to achieve tight complexity bounds of gradient-based methods for convex optimization. We start by identifying some of the pitfalls rooted in the classical complexity analysis of the gradient descent method, and show how they can be remedied. Our methodology hinges on elementary and direct arguments in the spirit of the classical analysis. It allows us to establish some new (and reproduce known) tight complexity results for several fundamental algorithms including, gradient descent, proximal point and proximal gradient methods which previously could be proven only through computer-assisted convergence proof arguments. [ABSTRACT FROM AUTHOR]

This paper introduces a method for computing points satisfying the second-order necessary optimality conditions for nonconvex minimization problems subject to a closed and convex constraint set. The method comprises two independent steps corresponding to the first- and second-order conditions. The first-order step is a generic closed map algorithm, which can be chosen from a variety of first-order algorithms, making it adjustable to the given problem. The second-order step can be viewed as a second-order feasible direction step for nonconvex minimization subject to a convex set. We prove that any limit point of the resulting scheme satisfies the second-order necessary optimality condition, and establish the scheme's convergence rate and complexity, under standard and mild assumptions. Numerical tests illustrate the proposed scheme. [ABSTRACT FROM AUTHOR]

We consider the nonnegative matrix factorization (NMF) problem with sparsity constraints formulated as a nonconvex composite minimization problem. We introduce four novel proximal gradient based algorithms proven globally convergent to a critical point and which are applicable to sparsity constrained NMF models. Our approach builds on recent results allowing one to lift the classical global Lipschitz continuity requirement through the use of a non-Euclidean Bregman based distance. Since under the proposed framework we are not restricted by the gradient Lipschitz continuity assumption, we can consider new decomposition settings of the NMF problem. Two of the derived schemes are genuine non-Euclidean proximal methods that tackle nonstandard decompositions of the NMF problem. The two other schemes are novel extensions of the well-known state-of-the-art methods (the multiplicative and hierarchical alternating least squares), thus allowing one to significantly broaden the scope of these algorithms. Numerical experiments illustrate the performance of the proposed methods. [ABSTRACT FROM AUTHOR]

We discuss the foundational role of the proximal framework in the development and analysis of some iconic first order optimization algorithms, with a focus on non-Euclidean proximal distances of Bregman type, which are central to the analysis of many other fundamental first order minimization relatives. We stress simplification and unification by highlighting self-contained elementary proof-patterns to obtain convergence rate and global convergence both in the convex and the nonconvex settings, which in turn also allows to present some novel results. [ABSTRACT FROM AUTHOR]

We consider a broad class of regularized structured total least squares (RSTLS) problems encompassing many scenarios in image processing. This class of problems results in a nonconvex and often nonsmooth model in large dimension. To tackle this difficult class of problems we introduce a novel algorithm which blends proximal and alternating minimization methods by beneficially exploiting data information and structures inherently present in RSTLS. The proposed algorithm, which can also be applied to more general problems, is proven to globally converge to critical points and is amenable to efficient and simple computational steps. We illustrate our theoretical findings by presenting numerical experiments on deblurring large scale images, which demonstrate the viability and effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

We consider the class of nondifferentiable convex problems which minimizes a nonsmooth convex objective over a single smooth constraint. Exploiting the smoothness of the feasible set and using duality, we introduce a simple first order algorithm proven to globally converge to an optimal solution with a $$\mathcal {O}(1/\varepsilon )$$ efficiency estimate. The performance of the algorithm is demonstrated by solving large instances of the convex sparse recovery problem. [ABSTRACT FROM AUTHOR]

We introduce a proximal alternating linearized minimization (PALM) algorithm for solving a broad class of nonconvex and nonsmooth minimization problems. Building on the powerful Kurdyka-Łojasiewicz property, we derive a self-contained convergence analysis framework and establish that each bounded sequence generated by PALM globally converges to a critical point. Our approach allows to analyze various classes of nonconvex-nonsmooth problems and related nonconvex proximal forward-backward algorithms with semi-algebraic problem's data, the later property being shared by many functions arising in a wide variety of fundamental applications. A by-product of our framework also shows that our results are new even in the convex setting. As an illustration of the results, we derive a new and simple globally convergent algorithm for solving the sparse nonnegative matrix factorization problem. [ABSTRACT FROM AUTHOR]

We introduce a novel approach for analyzing the worst-case performance of first-order black-box optimization methods. We focus on smooth unconstrained convex minimization over the Euclidean space. Our approach relies on the observation that by definition, the worst-case behavior of a black-box optimization method is by itself an optimization problem, which we call the performance estimation problem (PEP). We formulate and analyze the PEP for two classes of first-order algorithms. We first apply this approach on the classical gradient method and derive a new and tight analytical bound on its performance. We then consider a broader class of first-order black-box methods, which among others, include the so-called heavy-ball method and the fast gradient schemes. We show that for this broader class, it is possible to derive new bounds on the performance of these methods by solving an adequately relaxed convex semidefinite PEP. Finally, we show an efficient procedure for finding optimal step sizes which results in a first-order black-box method that achieves best worst-case performance. [ABSTRACT FROM AUTHOR]

This paper presents two classes of decomposition algorithms based on the proximal method of multipliers (PMM) introduced in the mid-1970s by Rockafellar for convex minimization. We first show that the PMM framework is at the root of many past and recent decomposition schemes suggested in the literature allowing for an elementary analysis of these methods through a unified scheme. We then prove various sublinear global convergence rate results for the two classes of PMM based decomposition algorithms for function values and constraints violation. Furthermore, under a mild assumption on the problem's data we derive rate of convergence results in terms of the original primal function values for both classes. As a by-product of our analysis we also obtain convergence of the sequences produced by the two algorithm classes to optimal primal-dual solutions. [ABSTRACT FROM AUTHOR]

The sparsity constrained rank-one matrix approximation problem is a difficult mathematical optimization problem which arises in a wide array of useful applications in engineering, machine learning, and statistics, and the design of algorithms for this problem has attracted intensive research activities. We introduce an algorithmic framework, called ConGradU, that unifies a variety of seemingly different algorithms that have been derived from disparate approaches, and that allows for deriving new schemes. Building on the old and well-known conditional gradient algorithm, ConGradU is a simplified version with unit step size that yields a generic algorithm which either is given by an analytic formula or requires a very low computational complexity. Mathematical properties are systematically developed and numerical experiments are given. [ABSTRACT FROM AUTHOR]

This paper studies gradient-based schemes for image denoising and deblurring problems based on the discretized total variation (TV) minimization model with constraints. We derive a fast algorithm for the constrained TV-based image deburring problem. To achieve this task, we combine an acceleration of the well known dual approach to the denoising problem with a novel monotone version of a fast iterative shrinkage/thresholding algorithm (FISTA) we have recently introduced. The resulting gradient-based algorithm shares a remarkable simplicity together with a proven global rate of convergence which is significantly better than currently known gradient projections-based methods. Our results are applicable to both the anisotropic and isotropic discretized TV functionals. Initial numerical results demonstrate the viability and efficiency of the proposed algorithms on image deblurring problems with box constraints. [ABSTRACT FROM AUTHOR]

We study subgradient projection type methods for solving non-differentiable convex minimization problems and monotone variational inequalities. The methods can be viewed as a natural extension of subgradient projection type algorithms, and are based on using non-Euclidean projection-like maps, which generate interior trajectories. The resulting algorithms are easy to implement and rely on a single projection per iteration. We prove several convergence results and establish rate of convergence estimates under various and mild assumptions on the problem’s data and the corresponding step-sizes. [ABSTRACT FROM AUTHOR]

We consider the class of iterative shrinkage-thresholding algorithms (ISTA) for solving linear inverse problems arising in signal/image processing. This class of methods, which can be viewed as an extension of the classical gradient algorithm, is attractive due to its simplicity and thus is adequate for solving large-scale problems even with dense matrix data. However, such methods are also known to converge quite slowly. In this paper we present a new fast iterative shrinkage-thresholding algorithm (FISTA) which preserves the computational simplicity of ISTA but with a global rate of convergence which is proven to be significantly better, both theoretically and practically. Initial promising numerical results for wavelet-based image deblurring demonstrate the capabilities of FISTA which is shown to be faster than ISTA by several orders of magnitude. [ABSTRACT FROM AUTHOR]

Abstract. We consider the problem of locating a single radiating source from several noisy measurements using a maximum likelihood (ML) criteria. The resulting optimization problem is nonconvex and nonsmooth, and thus finding its global solution is in principle a hard task. Exploiting the special structure of the objective function, we introduce and analyze two iterative schemes for solving this problem. The first algorithm is a very simple explicit fixed-point-based formula, and the second is based on solving at each iteration a nonlinear least squares problem, which can be solved globally and efficiently after transforming it into an equivalent quadratic minimization problem with a single quadratic constraint. We show that the nonsmoothness of the problem can be avoided by choosing a specific "good" starting point for both algorithms, and we prove the convergence of the two schemes to stationary points. We present empirical results that support the underlying theoretical analysis and suggest that, despite of its nonconvexity, the ML problem can effectively be solved globally using the devised schemes. [ABSTRACT FROM AUTHOR]

We consider nonmonotone projected gradient methods based on non-Euclidean distances, which play the role of barrier for a given constraint set. Our basic scheme uses the resulting projection-like maps that produces interior trajectories, and combines it with the recent nonmonotone line search technique originally proposed for unconstrained problems by Zhang and Hager. The combination of these two ideas leads to produce a nonmonotone scheme for constrained nonconvex problems, which is proven to converge to a stationary point. Some variants of this algorithm that incorporate spectral steplength are also studied and compared with classical nonmonotone schemes based on the usual Euclidean projection. To validate our approach, we report on numerical results solving bound constrained problems from the CUTEr library collection. [ABSTRACT FROM AUTHOR]

Center-based partitioning clustering algorithms rely on minimizing an appropriately formulated objective function, and different formulations suggest different possible algorithms. In this paper, we start with the standard nonconvex and nonsmooth formulation of the partitioning clustering problem. We demonstrate that within this elementary formulation, convex analysis tools and optimization theory provide a unifying language and framework to design, analyze and extend hard and soft center-based clustering algorithms, through a generic algorithm which retains the computational simplicity of the popular k-means scheme. We show that several well known and more recent center-based clustering algorithms, which have been derived either heuristically, or/and have emerged from intuitive analogies in physics, statistical techniques and information theoretic perspectives can be recovered as special cases of the proposed analysis and we streamline their relationships. [ABSTRACT FROM AUTHOR]

Interior gradient (subgradient) and proximal methods for convex constrained minimization have been much studied, in particular for optimization problems over the nonnegative octant. These methods are using non-Euclidean projections and proximal distance functions to exploit the geometry of the constraints. In this paper, we identify a simple mechanism that allows us to derive global convergence results of the produced iterates as well as improved global rates of convergence estimates for a wide class of such methods, and with more general convex constraints. Our results are illustrated with many applications and examples, including some new explicit and simple algorithms for conic optimization problems. In particular, we derive a class of interior gradient algorithms which exhibits an $O(k^{-2})$ global convergence rate estimate. [ABSTRACT FROM AUTHOR]

We study some continuous dynamical systems associated with constrained optimization problems. For that purpose, we introduce the concept of elliptic barrier operators and develop a unified framework to derive and analyze the associated class of gradient-like dynamical systems, called A-driven descent method (A-DM). Prominent methods belonging to this class include several continuous descent methods studied earlier in the literature such as steepest descent method, continuous gradient projection methods and Newton-type methods as well as continuous interior descent methods such as Lotka-Volterra-type differential equations and Riemannian gradient methods. Related discrete iterative methods such as proximal interior point algorithms based on Bregman functions and second order homogeneous kernels can also be recovered within our framework and allow for deriving some new and interesting dynamics. We prove global existence and strong viability results of the corresponding trajectories of (A-DM) for a smooth objective function. When the objective function is convex, we analyze the asymptotic behavior at infinity of the trajectory produced by the proposed class of dynamical systems (A -DM). In particular, we derive a general criterion ensuring the global convergence of the trajectory of (A-DM) to a minimizer of a convex function over a closed convex set. This result is then applied to several dynamics built upon specific elliptic barrier operators. Throughout the paper, our results are illustrated with many examples. [ABSTRACT FROM AUTHOR]

We analyze the rate of convergence of three basic projections type algorithms for solving the convex feasibility problem (CFP). Error bounds are known to be central in establishing the rate of convergence of iterative methods. We study the interplay between Slater's hypothesis on CFP and a specific local error bound (LEB). We show that without Slater's hypothesis on CFP, projections type algorithms can in fact behave quite badly, i.e., with a rate of convergence which is not bounded. We derive a new and simple convex analytic proof showing that Slater's hypothesis on CFP implies LEB and hence linear convergence of projection algorithms is guaranteed. We then propose an alternative local error bound derived from the gradient projection algorithm for convex minimization which is proven to be weaker than LEB and used to derive further convergence rate results. [ABSTRACT FROM AUTHOR]