Nonsmooth Optimization

An Accelerated Inexact Dampened Augmented Lagrangian Method for Linearly-Constrained Nonconvex Composite Optimization Problems

  • Weiwei Kong
  • Renato D.C. Monteiro
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    This paper proposes and analyzes an accelerated inexact dampened augmented Lagrangian (AIDAL) method for solving linearly-constrained nonconvex composite optimization problems. Each iteration of the AIDAL method consists of: (i) inexactly solving a dampened proximal augmented Lagrangian (AL) subproblem by calling an accelerated composite gradient (ACG) subroutine; (ii) applying a dampened and under-relaxed Lagrange multiplier update; … Read more

    MPCC Strategies for Nonsmooth NLPs

  • Kexin Wang
  • Lorenz T. Biegler
    • Categories Complementarity and Variational Inequalities, Nonsmooth Optimization Tags , , ,

    This paper develops solution strategies for large-scale nonsmooth optimization problems. We transform nonsmooth programs into equivalent mathematical programs with complementarity constraints (MPCCs), and then employ NLP-based strategies for their so- lution. For this purpose, two NLP formulations based on complementarity relaxations are put forward, one of which applies a parameterized formulation and operates with a … Read more

    Inertial-relaxed splitting for composite monotone inclusions

  • Ernesto Ore Albornoz
  • Philippe Mahey
  • Eladio Ocaña Anaya
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , ,

    In a similar spirit of the extension of the proximal point method developed by Alves et al. \cite{alvegm20}, we propose in this work an Inertial-Relaxed primal-dual splitting method to address the problem of decomposing the minimization of the sum of three convex functions, one of them being smooth, and considering a general coupling subspace. A … Read more

    Comparing Solution Paths of Sparse Quadratic Minimization with a Stieltjes Matrix

  • Ziyu He
  • Shaoning Han
  • Andrés Gómez
  • Ying Cui
  • Jong-Shi Pang
    • Categories Nonsmooth Optimization, Quadratic Programming, Statistics Tags , , ,

    This paper studies several solution paths of sparse quadratic minimization problems as a function of the weighing parameter of the bi-objective of estimation loss versus solution sparsity. Three such paths are considered: the “L0-path” where the discontinuous L0-function provides the exact sparsity count; the “L1-path” where the L1-function provides a convex surrogate of sparsity count; … Read more

    A Local MM Subspace Method for Solving Constrained Variational Problems in Image Recovery

  • Émilie Chouzenoux
  • Ségolène Martin
  • Jean-Christophe Pesquet
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , , , ,

    This article introduces a new Penalized Majorization-Minimization Subspace algorithm (P-MMS) for solving smooth, constrained optimization problems. In short, our approach consists of embedding a subspace algorithm in an inexact exterior penalty procedure. The subspace strategy, combined with a Majoration-Minimization step-size search, takes great advantage of the smoothness of the penalized cost function, while the penalty … Read more

    Subgradient methods near active manifolds: saddle point avoidance, local convergence, and asymptotic normality

  • Damek Davis
  • Dmitriy Drusvyatskiy
  • Liwei Jiang
    • Categories Nonsmooth Optimization

    Nonsmooth optimization problems arising in practice, whether in signal processing, statistical estimation, or modern machine learning, tend to exhibit beneficial smooth substructure: their domains stratify into “active manifolds” of smooth variation, which common proximal algorithms “identify” in finite time. Identification then entails a transition to smooth dynamics, and permits the use of second-order information for … Read more

    On Properties of Univariate Max Functions at Local Maximizers

  • Tim Mitchell
  • Michael L. Overton
    • Categories Nonsmooth Optimization Tags , , , ,

    More than three decades ago, Boyd and Balakrishnan established a regularity result for the two-norm of a transfer function at maximizers. Their result extends easily to the statement that the maximum eigenvalue of a univariate real analytic Hermitian matrix family is twice continuously differentiable, with Lipschitz second derivative, at all local maximizers, a property that … Read more

    An abstract convergence framework with application to inertial inexact forward-backward methods

  • Silvia Bonettini
  • Peter Ochs
  • Marco Prato
  • Simone Rebegoldi
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    In this paper we introduce a novel abstract descent scheme suited for the minimization of proper and lower semicontinuous functions. The proposed abstract scheme generalizes a set of properties that are crucial for the convergence of several first-order methods designed for nonsmooth nonconvex optimization problems. Such properties guarantee the convergence of the full sequence of … Read more

    A Semismooth Newton-Type Method for the Nearest Doubly Stochastic Matrix Problem

  • Hao Hu
  • Xinxin Li
  • Henry Wolkowicz
  • Haesol Im
    • Categories Convex and Nonsmooth Optimization, Nonsmooth Optimization Tags , , , ,

    We study a semismooth Newton-type method for the nearest doubly stochastic matrix problem where both differentiability and nonsingularity of the Jacobian can fail. The optimality conditions for this problem are formulated as a system of strongly semismooth functions. We show that the so-called local error bound condition does not hold for this system. Thus the … Read more

    FISTA and Extensions – Review and New Insights

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

    The purpose of this technical report is to review the main properties of an accelerated composite gradient (ACG) method commonly referred to as the Fast Iterative Shrinkage-Thresholding Algorithm (FISTA). In addition, we state a version of FISTA for solving both convex and strongly convex composite minimization problems and derive its iteration complexities to generate iterates … Read more