proximal gradient method

Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems

  • Jane J. Ye
  • Xiao-Ming Yuan
  • Shangzhi Zeng
  • Jin Zhang
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , , ,

    We understand linear convergence of some first-order methods such as the proximal gradient method (PGM), the proximal alternating linearized minimization (PALM) algorithm and the randomized block coordinate proximal gradient method (R-BCPGM) for minimizing the sum of a smooth convex function and a nonsmooth convex function from a variational analysis perspective. We introduce a new analytic … Read more

    Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization

  • Filip Hanzely
  • Peter Richtarik
  • Lin Xiao
    • Categories Convex Optimization, Nonlinear Optimization Tags , , , ,

    We consider the problem of minimizing the sum of two convex functions: one is differentiable and relatively smooth with respect to a reference convex function, and the other can be nondifferentiable but simple to optimize. The relatively smooth condition is much weaker than the standard assumption of uniform Lipschitz continuity of the gradients, thus significantly … Read more

    A Novel Approach for Solving Convex Problems with Cardinality Constraints

  • Goran Banjac
  • Paul J. Goulart
    • Categories Approximation Algorithms Tags , , , ,

    In this paper we consider the problem of minimizing a convex differentiable function subject to sparsity constraints. Such constraints are non-convex and the resulting optimization problem is known to be hard to solve. We propose a novel generalization of this problem and demonstrate that it is equivalent to the original sparsity-constrained problem if a certain … Read more

    Sparse Recovery via Partial Regularization: Models, Theory and Algorithms

  • Xiaorui Li
  • Zhaosong Lu
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Statistics Tags , , , , , , ,

    In the context of sparse recovery, it is known that most of existing regularizers such as $\ell_1$ suffer from some bias incurred by some leading entries (in magnitude) of the associated vector. To neutralize this bias, we propose a class of models with partial regularizers for recovering a sparse solution of a linear system. We … Read more

    Stochastic Approximations and Perturbations in Forward-Backward Splitting for Monotone Operators

  • Patrick L. Combettes
  • Jean-Christophe Pesquet
    • Categories Infinite Dimensional Optimization, Stochastic Programming Tags , , , , ,

    We investigate the asymptotic behavior of a stochastic version of the forward-backward splitting algorithm for finding a zero of the sum of a maximally monotone set-valued operator and a cocoercive operator in Hilbert spaces. Our general setting features stochastic approximations of the cocoercive operator and stochastic perturbations in the evaluation of the resolvents of the … Read more

    First-Order Algorithms for Convex Optimization with Nonseparate Objective and Coupled Constraints

  • Xiang Gao
  • Shuzhong Zhang
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    In this paper we consider a block-structured convex optimization model, where in the objective the block-variables are nonseparable and they are further linearly coupled in the constraint. For the 2-block case, we propose a number of first-order algorithms to solve this model. First, the alternating direction method of multipliers (ADMM) is extended, assuming that it … Read more

    A proximal gradient method for ensemble density functional theory

  • Dennis Klöckner
  • Zhaosong Lu
  • Michael Ulbrich
  • Zaiwen Wen
  • Chao Yang
    • Categories Basic Sciences Applications, Constrained Nonlinear Optimization Tags , , ,

    The ensemble density functional theory is valuable for simulations of metallic systems due to the absence of a gap in the spectrum of the Hamiltonian matrices. Although the widely used self-consistent field iteration method can be extended to solve the minimization of the total energy functional with respect to orthogonality constraints, there is no theoretical … Read more

    A Proximal Stochastic Gradient Method with Progressive Variance Reduction

  • Lin Xiao
  • Tong Zhang
    • Categories Convex and Nonsmooth Optimization, Stochastic Programming Tags , ,

    We consider the problem of minimizing the sum of two convex functions: one is the average of a large number of smooth component functions, and the other is a general convex function that admits a simple proximal mapping. We assume the whole objective function is strongly convex. Such problems often arise in machine learning, known … Read more

    Alternating Proximal Gradient Method for Convex Minimization

  • Shiqian Ma
    • Categories Convex Optimization Tags , , ,

    In this paper, we propose an alternating proximal gradient method that solves convex minimization problems with three or more separable blocks in the objective function. Our method is based on the framework of alternating direction method of multipliers. The main computational effort in each iteration of the proposed method is to compute the proximal mappings … Read more

    A Block Coordinate Descent Method for Regularized Multi-Convex Optimization with Applications to Nonnegative Tensor Factorization and Completion

  • Yangyang Xu
  • Wotao Yin
    • Categories Constrained Nonlinear Optimization, Data-Mining, Nonsmooth Optimization Tags , , , , , , ,

    This paper considers regularized block multi-convex optimization, where the feasible set and objective function are generally non-convex but convex in each block of variables. We review some of its interesting examples and propose a generalized block coordinate descent method. (Using proximal updates, we further allow non-convexity over some blocks.) Under certain conditions, we show that … Read more