Nonsmooth Optimization

Convergence Results for Primal-Dual Algorithms in the Presence of Adjoint Mismatch

  • Andres Contreras
  • Émilie Chouzenoux
  • Jean-Christophe Pesquet
  • Marion Savanier
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , , , ,

    Most optimization problems arising in imaging science involve high-dimensional linear operators and their adjoints. In the implementations of these operators, approximations may be introduced for various practical considerations (e.g., memory limitation, computational cost, convergence speed), leading to an adjoint mismatch. This occurs for the X-ray tomographic inverse problems found in Computed Tomography (CT), where the … Read more

    A new sufficient condition for non-convex sparse recovery via weighted $\ell_r\!-\!\ell_1$ minimization

  • Jianwen Huang
  • Feng Zhang
    • Categories Data-Mining, Nonsmooth Optimization Tags , , ,

    In this letter, we discuss the reconstruction of sparse signals from undersampled data, which belongs to the core content of compressed sensing. A new sufficient condition in terms of the restricted isometry constant (RIC) and restricted orthogonality constant (ROC) is first established for the performance guarantee of recently proposed non-convex weighted $\ell_r-\ell_1$ minimization in recovering … Read more

    A Decomposition Algorithm for Two-Stage Stochastic Programs with Nonconvex Recourse

  • Hanyang Li
  • Ying Cui
    • Categories Nonsmooth Optimization, Stochastic Programming Tags , ,

    In this paper, we have studied a decomposition method for solving a class of nonconvex two-stage stochastic programs, where both the objective and constraints of the second-stage problem are nonlinearly parameterized by the first-stage variable. Due to the failure of the Clarke regularity of the resulting nonconvex recourse function, classical decomposition approaches such as Benders … Read more

    The Null Space Property of the Weighted $\ell_r-\ell_1$ Minimization

  • Jianwen Huang
  • Xinling Liu
    • Categories Data-Mining, Nonsmooth Optimization, Robust Optimization Tags , , ,

    The null space property (NSP), which relies merely on the null space of the sensing matrix column space, has drawn numerous interests in sparse signal recovery. This article studies NSP of the weighted $\ell_r-\ell_1$ minimization. Several versions of NSP of the weighted $\ell_r-\ell_1$ minimization including the weighted $\ell_r-\ell_1$ NSP, the weighted $\ell_r-\ell_1$ stable NSP, the … Read more

    Stochastic trust-region and direct-search methods: A weak tail bound condition and reduced sample sizing

  • Francesco Rinaldi
  • Luis Nunes Vicente
  • Damiano Zeffiro
    • Categories Nonsmooth Optimization, Stochastic Programming, Unconstrained Optimization Tags , , ,

    Using tail bounds, we introduce a new probabilistic condition for function estimation in stochastic derivative-free optimization which leads to a reduction in the number of samples and eases algorithmic analyses. Moreover, we develop simple stochastic direct-search and trust-region methods for the optimization of a potentially non-smooth function whose values can only be estimated via stochastic … Read more

    Retraction based Direct Search Methods for Derivative Free Riemannian Optimization

  • Vyacheslav Kungurtsev
  • Francesco Rinaldi
  • Damiano Zeffiro
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    Direct search methods represent a robust and reliable class of algorithms for solving black-box optimization problems. In this paper, we explore the application of those strategies to Riemannian optimization, wherein minimization is to be performed with respect to variables restricted to lie on a manifold. More specifically, we consider classic and line search extrapolated variants … Read more

    Global convergence and acceleration of projection methods for feasibility problems involving union convex sets

  • Jan Harold Alcantara
  • Ching-pei Lee
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization, Nonsmooth Optimization Tags , , , , , ,

    We prove global convergence of classical projection algorithms for feasibility problems involving union convex sets, which refer to sets expressible as the union of a finite number of closed convex sets. We present a unified strategy for analyzing global convergence by means of studying fixed-point iterations of a set-valued operator that is the union of … Read more

    Stable Recovery of Sparse Signals With Non-convex Weighted $r$-Norm Minus $1$-Norm

  • Jianwen Huang
  • Feng Zhang
  • Xinling Liu
  • Jianjun Wang
    • Categories Constrained Nonlinear Optimization, Data-Mining, Nonsmooth Optimization Tags , , ,

    Given the measurement matrix $A$ and the observation signal $y$, the central purpose of compressed sensing is to find the most sparse solution of the underdetermined linear system $y=Ax+z$, where $x$ is the $s$-sparse signal to be recovered and $z$ is the noise vector. Zhou and Yu \cite{Zhou and Yu 2019} recently proposed a novel … Read more

    Unmatched Preconditioning of the Proximal Gradient Algorithm

  • Marion Savanier
  • Émilie Chouzenoux
  • Jean-Christophe Pesquet
  • Cyril Riddel
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    This works addresses the resolution of penalized least-squares problems using the proximal gradient algorithm (PGA). It is known that PGA can be accelerated by preconditioning strategies. However, typical effective choices of preconditioners may correspond to intricate matrices that are not easily inverted, and lead to an increased complexity in the computation of the proximity step. … Read more

    A nested primal–dual FISTA-like scheme for composite convex optimization problems

  • Silvia Bonettini
  • Marco Prato
  • Simone Rebegoldi
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    We propose a nested primal–dual algorithm with extrapolation on the primal variable suited for minimizing the sum of two convex functions, one of which is continuously differentiable. The proposed algorithm can be interpreted as an inexact inertial forward–backward algorithm equipped with a prefixed number of inner primal–dual iterations for the proximal evaluation and a “warm–start” … Read more