Nonsmooth Optimization

Iteration-Complexity of a Linearized Proximal Multiblock ADMM Class for Linearly Constrained Nonconvex Optimization Problems

  • Jefferson Gonçalves Melo
  • Renato D.C. Monteiro
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    This paper analyzes the iteration-complexity of a class of linearized proximal multiblock alternating direction method of multipliers (ADMM) for solving linearly constrained nonconvex optimization problems. The subproblems of the linearized ADMM are obtained by partially or fully linearizing the augmented Lagrangian with respect to the corresponding minimizing block variable. The derived complexity bounds do not … Read more

    Linear Convergence of Proximal Incremental Aggregated Gradient Methods under Quadratic Growth Condition

  • Hui Zhang
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , , ,

    Under the strongly convex assumption, several recent works studied the global linear convergence rate of the proximal incremental aggregated gradient (PIAG) method for minimizing the sum of a large number of smooth component functions and a non-smooth convex function. In this paper, under the quadratic growth condition{a strictly weaker condition than the strongly convex assumption, … Read more

    Direct Search Methods on Reductive Homogeneous Spaces

  • Dreisigmeyer David
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags ,

    Direct search methods are mainly designed for use in problems with no equality constraints. However, there are many instances where the feasible set is of measure zero in the ambient space and no mesh point lies within it. There are methods for working with feasible sets that are (Riemannian) manifolds, but not all manifolds are … Read more

    A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications

  • Xudong Li
  • Defeng Sun
  • Kim-Chuan Toh
    • Categories Nonsmooth Optimization, Quadratic Programming Tags , ,

    For a symmetric positive semidefinite linear system of equations $\mathcal{Q} {\bf x} = {\bf b}$, where ${\bf x} = (x_1,\ldots,x_s)$ is partitioned into $s$ blocks, with $s \geq 2$, we show that each cycle of the classical block symmetric Gauss-Seidel (block sGS) method exactly solves the associated quadratic programming (QP) problem but added with an … Read more

    BFGS convergence to nonsmooth minimizers of convex functions

  • Jiayi Guo
  • Adrian Lewis
    • Categories Nonsmooth Optimization, Unconstrained Optimization

    The popular BFGS quasi-Newton minimization algorithm under reasonable conditions converges globally on smooth convex functions. This result was proved by Powell in 1976: we consider its implications for functions that are not smooth. In particular, an analogous convergence result holds for functions, like the Euclidean norm, that are nonsmooth at the minimizer. CitationManuscript: School of … Read more

    CONVEX GEOMETRY OF THE GENERALIZED MATRIX-FRACTIONAL FUNCTION

  • James V. Burke
  • Tim Hoheisel
  • Yuan Gao
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , ,

    Generalized matrix-fractional (GMF) functions are a class of matrix support functions introduced by Burke and Hoheisel as a tool for unifying a range of seemingly divergent matrix optimization problems associated with inverse problems, regularization and learning. In this paper we dramatically simplify the support function representation for GMF functions as well as the representation of … Read more

    Algorithmic Differentiation for Piecewise Smooth Functions: A Case Study for Robust Optimization

  • Sabrina Fiege
  • Andreas Griewank
  • Kshitij Kulshreshtha
  • Andrea Walther
    • Categories Nonsmooth Optimization Tags , , ,

    This paper presents a minimization method for Lipschitz continuous, piecewise smooth objective functions based on algorithmic differentiation (AD). We assume that all nondifferentiabilities are caused by abs(), min(), and max(). The optimization method generates successively piecewise linearizations in abs-normal form and solves these local subproblems by exploiting the resulting kink structure. Both, the generation of … Read more

    On Nonconvex Decentralized Gradient Descent

  • Wotao Yin
  • Jinshan Zeng
    • Categories Network Optimization, Nonsmooth Optimization Tags , , ,

    Consensus optimization has received considerable attention in recent years. A number of decentralized algorithms have been proposed for {convex} consensus optimization. However, to the behaviors or consensus \emph{nonconvex} optimization, our understanding is more limited. When we lose convexity, we cannot hope our algorithms always return global solutions though they sometimes still do sometimes. Somewhat surprisingly, … Read more

    A TVSCAD approach for image deblurring with impulsive noise

  • Guoyong Gu
  • Junfeng Yang
  • Suhong Jiang
    • Categories Nonsmooth Optimization Tags , , , , , , , ,

    We consider image deblurring problem in the presence of impulsive noise. It is known that \emph{total variation} (TV) regularization with L1-norm penalized data fitting (TVL1 for short) works reasonably well only when the level of impulsive noise is relatively low. For high level impulsive noise, TVL1 works poorly. The reason is that all data, both … Read more

    Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems

  • Max L. N. Gonçalves
  • Jefferson Gonçalves Melo
  • Renato D.C. Monteiro
    • Categories Convex and Nonsmooth Optimization, Nonsmooth Optimization Tags , , ,

    This paper establishes convergence rate bounds for a variant of the proximal alternating direction method of multipliers (ADMM) for solving nonconvex linearly constrained optimization problems. The variant of the proximal ADMM allows the inclusion of an over-relaxation stepsize parameter belonging to the interval (0,2). To the best of our knowledge, all related papers in the … Read more