smooth optimization

A Finite-Difference Trust-Region Method for Convexly Constrained Smooth Optimization

  • Dânâ Davar
  • Geovani Nunes Grapiglia
    • Categories Bound-constrained Optimization, Nonlinear Optimization Tags , , , ,

    We propose a derivative-free trust-region method based on finite-difference gradient approximations for smooth optimization problems with convex constraints. The proposed method does not require computing an approximate stationarity measure. For nonconvex problems, we establish a worst-case complexity bound of \(\mathcal{O}\!\left(n\left(\frac{L}{\sigma}\epsilon\right)^{-2}\right)\) function evaluations for the method to reach an \(\left(\frac{L}{\sigma}\epsilon\right)\)-approximate stationary point, where \(n\) is the … Read more

    On the Acceleration of Proximal Bundle Methods

  • David Fersztand
  • Xu Andy Sun
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , ,

    The proximal bundle method (PBM) is a fundamental and computationally effective algorithm for solving nonsmooth optimization problems. In this paper, we present the first variant of the PBM for smooth objectives, achieving an accelerated convergence rate of \(\frac{1}{\sqrt{\epsilon}}\log(\frac{1}{\epsilon})\), where \(\epsilon\) is the desired accuracy. Our approach addresses an open question regarding the convergence guarantee of … Read more

    Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtracking

  • Frederik Kunstner
  • Mark Schmidt
    • Categories Convex Optimization, Nonlinear Optimization Tags , ,

    The backtracking line-search is an effective technique to automatically tune the step-size in smooth optimization. It guarantees similar performance to using the theoretically optimal step-size. Many approaches have been developed to instead tune per-coordinate step-sizes, also known as diagonal preconditioners, but none of the existing methods are provably competitive with the optimal per-coordinate stepsizes. We … 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

    Limited-memory Common-directions Method for Large-scale Optimization: Convergence, Parallelization, and Distributed Optimization

  • Ching-pei Lee
  • Po-Wei Wang
  • Chih-Jen Lin
    • Categories Parallel Algorithms, Unconstrained Optimization Tags , , ,

    In this paper, we present a limited-memory common-directions method for smooth optimization that interpolates between first- and second- order methods. At each iteration, a subspace of a limited dimension size is constructed using first-order information from previous iterations, and an ef- ficient Newton method is deployed to find an approximate minimizer within this subspace. With … Read more

    OSGA: A fast subgradient algorithm with optimal complexity

  • Arnold Neumaier
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , , , , ,

    This paper presents an algorithm for approximately minimizing a convex function in simple, not necessarily bounded convex domains, assuming only that function values and subgradients are available. No global information about the objective function is needed apart from a strong convexity parameter (which can be put to zero if only convexity is known). The worst … Read more