Nonsmooth Optimization

Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decomposition

  • Ching-pei Lee
  • Ling Liang
  • Tianyun Tang
  • Kim-Chuan Toh
    • Categories Global Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    This work proposes a rapid algorithm, BM-Global, for nuclear-norm-regularized convex and low-rank matrix optimization problems. BM-Global efficiently decreases the objective value via low-cost steps leveraging the nonconvex but smooth Burer-Monteiro (BM) decomposition, while effectively escapes saddle points and spurious local minima ubiquitous in the BM form to obtain guarantees of fast convergence rates to the … Read more

    Error Bound and Isocost Imply Linear Convergence of DCA-based Algorithms to D-stationarity

  • Tao Min
  • Li Jiang-Ning
    • Categories Nonsmooth Optimization Tags , , ,

    We consider a class of structured nonsmooth difference-of-convex minimization, which can be written as the difference of two convex functions possibly nonsmooth with the second one in the format of the maximum of a finite convex smooth functions. We propose two extrapolation proximal difference-of-convex based algorithms for potential acceleration to converge to a weak/standard d-stationary … Read more

    Improved RIP-Based Bounds for Guaranteed Performance of Two Compressed Sensing Algorithms

  • Yun-Bin Zhao
  • Zhi-Quan Luo
    • Categories Constrained Nonlinear Optimization, Global Optimization Applications, Nonsmooth Optimization Tags , , , ,

    Iterative hard thresholding (IHT) and compressive sampling matching pursuit (CoSaMP) are two mainstream compressed sensing algorithms using the hard thresholding operator. The guaranteed performance of the two algorithms for signal recovery was mainly analyzed in terms of the restricted isometry property (RIP) of sensing matrices. At present, the best known bound using RIP of order … Read more

    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