convex optimization

Some Modified Fast Iteration Shrinkage Thresholding Algorithms with a New Adaptive Non-monotone Stepsize Strategy for Nonsmooth and Convex Minimization Problems

  • Hongwei Liu
  • Wang Ting
  • Zexian Liu
    • Categories Convex and Nonsmooth Optimization Tags , , , , ,

    The ” fast iterative shrinkage-thresholding algorithm ” (FISTA) is one of the most famous first order optimization scheme, and the stepsize, which plays an important role in theoretical analysis and numerical experiment, is always determined by a constant related to the Lipschitz constant or by a backtracking strategy. In this paper, we design a new … Read more

    Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysis

  • Courtney Paquette
  • Elliot Paquette
  • Bart van Merrienboer
  • Fabian Pedregosa
    • Categories Global Optimization Tags , ,

    Average-case analysis computes the complexity of an algorithm averaged over all possible inputs. Compared to worst-case analysis, it is more representative of the typical behavior of an algorithm, but remains largely unexplored in optimization. One difficulty is that the analysis can depend on the probability distribution of the inputs to the model. However, we show … Read more

    Convergence of Proximal Gradient Algorithm in the Presence of Adjoint Mismatch

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

    We consider the proximal gradient algorithm for solving penalized least-squares minimization problems arising in data science. This first-order algorithm is attractive due to its flexibility and minimal memory requirements allowing to tackle large-scale minimization problems involving non-smooth penalties. However, for problems such as X-ray computed tomography, the applicability of the algorithm is dominated by the … Read more

    Stokes, Gibbs and volume computation of semi-algebraic sets

  • Didier Henrion
  • Jean-Bernard Lasserre
  • Matteo Tacchi
    • Categories Infinite Dimensional Optimization, Semi-definite Programming Tags , ,

    We consider the problem of computing the Lebesgue volume of compact basic semi-algebraic sets. In full generality, it can be approximated as closely as desired by a converging hierarchy of upper bounds obtained by applying the Moment-SOS (sums of squares) methodology to a certain infinite-dimensional linear program (LP). At each step one solves a semidefinite … Read more

    Learning Dynamical Systems with Side Information

  • Amir Ali Ahmadi
  • Bachir El Khadir
    • Categories Convex Optimization, Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , ,

    We present a mathematical and computational framework for the problem of learning a dynamical system from noisy observations of a few trajectories and subject to side information. Side information is any knowledge we might have about the dynamical system we would like to learn besides trajectory data. It is typically inferred from domain-specific knowledge or … Read more

    A Subspace Acceleration Method for Minimization Involving a Group Sparsity-Inducing Regularizer

  • Frank E. Curtis
  • Daniel P. Robinson
  • Yutong Dai
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , , , , ,

    We consider the problem of minimizing an objective function that is the sum of a convex function and a group sparsity-inducing regularizer. Problems that integrate such regularizers arise in modern machine learning applications, often for the purpose of obtaining models that are easier to interpret and that have higher predictive accuracy. We present a new … Read more

    An inexact version of the symmetric proximal ADMM for solving separable convex optimization

  • Vando A. Adona
  • Max L. N. Gonçalves
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    In this paper, we propose and analyze an inexact version of the symmetric proximal alternating direction method of multipliers (ADMM) for solving linearly constrained optimization problems. Basically, the method allows its first subproblem to be solved inexactly in such way that a relative approximate criterion is satisfied. In terms of the iteration number $k$, we … Read more

    A parallel splitting ALM-based algorithm for separable convex programming

  • Bingsheng He
  • Shengjie Xu
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Parallel Algorithms Tags , , , ,

    The augmented Lagrangian method (ALM) provides a benchmark for tackling the canonical convex minimization problem with linear constraints. We consider a special case where the objective function is the sum of $m$ individual subfunctions without coupled variables. The recent study reveals that the direct extension of ALM for separable convex programming problems is not necessarily … Read more

    A search direction inspired primal-dual method for saddle point problems

  • Shengjie Xu
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , , ,

    The primal-dual hybrid gradient algorithm (PDHG), which is indeed the Arrow-Hurwicz method, has been widely used in image processing areas. However, the convergence of PDHG was established only under some restrictive conditions in the literature, and it is still missing for the case without extra constraints. In this paper, from a perspective of the variational … Read more

    Deriving Solution Value Bounds from the ADMM

  • Jonathan Eckstein
    • Categories Convex Optimization, Nonsmooth Optimization Tags ,

    This short paper describes a simple subgradient-based techniques for deriving bounds on the optimal solution value when using the ADMM to solve convex optimization problems. The technique requires a bound on the magnitude of some optimal solution vector, but is otherwise completely general. Some computational examples using LASSO problems demonstrate that the technique can produce … Read more