Convex and Nonsmooth Optimization

A Simplified Form of Block-Iterative Operator Splitting, and an Asynchronous Algorithm Resembling the Multi-Block ADMM

  • Jonathan Eckstein
    • Categories Convex Optimization Tags , , ,

    This paper develops what is essentially a simplified version of the block-iterative operator splitting method already proposed by the author and P. Combettes, but with more general initialization conditions. It then describes one way of implementing this algorithm asynchronously under a computing model inspired by modern HPC environments, which consist of interconnected nodes each having … Read more

    Randomized block proximal damped Newton method for composite self-concordant minimization

  • Zhaosong Lu
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    In this paper we consider the composite self-concordant (CSC) minimization problem, which minimizes the sum of a self-concordant function $f$ and a (possibly nonsmooth) proper closed convex function $g$. The CSC minimization is the cornerstone of the path-following interior point methods for solving a broad class of convex optimization problems. It has also found numerous … Read more

    1-Bit Compressive Sensing: Reformulation and RRSP-Based Sign Recovery Theory

  • Chunlei Xu
  • Yun-Bin Zhao
    • Categories Convex Optimization, Data-Mining Tags , , , , ,

    Recently, the 1-bit compressive sensing (1-bit CS) has been studied in the field of sparse signal recovery. Since the amplitude information of sparse signals in 1-bit CS is not available, it is often the support or the sign of a signal that can be exactly recovered with a decoding method. In this paper, we first … Read more

    A bound on the Carathéodory number

  • Masaru Ito
  • Bruno F. Lourenço
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    The Carathéodory number k(K) of a pointed closed convex cone K is the minimum among all the k for which every element of K can be written as a nonnegative linear combination of at most k elements belonging to extreme rays. Carathéodory’s Theorem gives the bound k(K) <= dim (K). In this work we observe … Read more

    On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions

  • Etienne de Klerk
  • François Glineur
  • Adrien B. Taylor
    • Categories Convex Optimization Tags , , ,

    We consider the gradient (or steepest) descent method with exact line search applied to a strongly convex function with Lipschitz continuous gradient. We establish the exact worst-case rate of convergence of this scheme, and show that this worst-case behavior is exhibited by a certain convex quadratic function. We also extend the result to a noisy … Read more

    A progressive barrier derivative-free trust-region algorithm for constrained optimization

  • Charles Audet
  • Andrew R. Conn
  • Sébastien Le Digabel
  • Mathilde Peyrega
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , ,

    We study derivative-free constrained optimization problems and propose a trust-region method that builds linear or quadratic models around the best feasible and and around the best infeasible solutions found so far. These models are optimized within a trust region, and the progressive barrier methodology handles the constraints by progressively pushing the infeasible solutions toward the … Read more

    Primal-dual potential reduction algorithm for symmetric programming problems with nonlinear objective functions

  • Leonid Faybusovich
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    We consider a primal-dual potential reduction algorithm for nonlinear convex optimization problems over symmetric cones. The same complexity estimates as in the case of linear objective function are obtained provided a certain nonlinear system of equations can be solved with a given accuracy. This generalizes the result of K. Kortanek, F. Potra and Y.Ye. We … Read more

    A Second-Order Information-Based Gradient and Function Sampling Method for Nonconvex, Nonsmooth Optimization

  • Elias Salomão Helou
  • Sandra Augusta Santos
  • Lucas E. A. Simões
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization

    This paper has the goal to propose a gradient and function sampling method that under special circumstances moves superlinearly to a minimizer of a general class of nonsmooth and nonconvex functions. We present global and local convergence theory with illustrative examples that corroborate and elucidate the theoretical results obtained along the manuscript. Article Download View … Read more

    Exact Worst-case Performance of First-order Methods for Composite Convex Optimization

  • François Glineur
  • Julien M. Hendrickx
  • Adrien B. Taylor
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , , , , , ,

    We provide a framework for computing the exact worst-case performance of any algorithm belonging to a broad class of oracle-based first-order methods for composite convex optimization, including those performing explicit, projected, proximal, conditional and inexact (sub)gradient steps. We simultaneously obtain tight worst-case guarantees and explicit instances of optimization problems on which the algorithm reaches this … Read more

    Convergence Analysis of ISTA and FISTA for “Strongly + Semi” Convex Programming

  • Ke Guo
  • Xiao-Ming Yuan
  • Shangzhi Zeng
    • Categories Convex Optimization Tags , , , , ,

    The iterative shrinkage/thresholding algorithm (ISTA) and its faster version FISTA have been widely used in the literature. In this paper, we consider general versions of the ISTA and FISTA in the more general “strongly + semi” convex setting, i.e., minimizing the sum of a strongly convex function and a semiconvex function; and conduct convergence analysis … Read more