nonsmooth

A nearly linearly convergent first-order method for nonsmooth functions with quadratic growth

  • Damek Davis
  • Liwei Jiang
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , , , ,

    Classical results show that gradient descent converges linearly to minimizers of smooth strongly convex functions. A natural question is whether there exists a locally nearly linearly convergent method for nonsmooth functions with quadratic growth. This work designs such a method for a wide class of nonsmooth and nonconvex locally Lipschitz functions, including max-of-smooth, Shapiro’s decomposable … Read more

    Optimal Convergence Rates for the Proximal Bundle Method

  • Mateo Díaz
  • Benjamin Grimmer
    • Categories Convex Optimization, Unconstrained Optimization Tags , , , ,

    We study convergence rates of the classic proximal bundle method for a variety of nonsmooth convex optimization problems. We show that, without any modification, this algorithm adapts to converge faster in the presence of smoothness or a Hölder growth condition. Our analysis reveals that with a constant stepsize, the bundle method is adaptive, yet it … Read more

    A Nonmonontone Accelerated Proximal Gradient Method with Variable Stepsize Strategy for Nonsmooth and Nonconvex Minimization Problems

  • Hongwei Liu
  • Wang Ting
    • Categories Nonsmooth Optimization Tags , , , , ,

    We propose a new nonmonontone accelerated proximal gradient method with variable stepsize strategy for minimizing the sum of a nonsmooth function with a smooth one in the nonconvex setting. In this algorithm, the objective function value be allowed to increase discontinuously, but is decreasing from the overall point of view. The variable stepsize strategy don’t … Read more

    The Landscape of the Proximal Point Method for Nonconvex-Nonconcave Minimax Optimization

  • Benjamin Grimmer
  • Haihao Lu
  • Vahab S. Mirrokni
  • Pratik Worah
    • Categories Robust Optimization, Unconstrained Optimization Tags , , , , , ,

    Minimax optimization has become a central tool for modern machine learning with applications in generative adversarial networks, robust optimization, reinforcement learning, etc. These applications are often nonconvex-nonconcave, but the existing theory is unable to identify and deal with the fundamental difficulties posed by nonconvex-nonconcave structures. In this paper, we study the classic proximal point method … Read more

    A fully mixed-integer linear programming formulation for economic dispatch with valve-point effects, transmission loss and prohibited operating zones

  • Huangyue Chen
  • Jinbao Jian
  • Shanshan Pan
  • Linfeng Yang
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering Tags , , , , ,

    Economic dispatch (ED) problem considering valve-point effects (VPE), transmission loss and prohibited operating zones (POZ) is a very challenging issue due to its intrinsic non-convex, non-smooth and non-continuous natures. To achieve a near globally solution, a fully mixed-integer linear programming (FMILP) formulation is proposed for such an ED problem. Since the original loss function is … Read more

    On the Convergence to Stationary Points of Deterministic and Randomized Feasible Descent Directions Methods

  • Amir Beck
  • Nadav Hallak
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , ,

    We study the class of nonsmooth nonconvex problems in which the objective is to minimize the difference between a continuously differentiable function (possibly nonconvex) and a convex (possibly nonsmooth) function over a convex polytope. This general class contains many types of problems, including difference of convex functions (DC) problems, and as such, can be used … Read more

    The Sound of APALM Clapping: Faster Nonsmooth Nonconvex Optimization with Stochastic Asynchronous PALM

  • Damek Davis
  • Brent Edmunds
  • Madeleine Udell
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    We introduce the Stochastic Asynchronous Proximal Alternating Linearized Minimization (SAPALM) method, a block coordinate stochastic proximal-gradient method for solving nonconvex, nonsmooth optimization problems. SAPALM is the first asynchronous parallel optimization method that provably converges on a large class of nonconvex, nonsmooth problems. We prove that SAPALM matches the best known rates of convergence — among … Read more

    Virtuous smoothing for global optimization

  • Jon Lee
  • Daphne Skipper
    • Categories Convex and Nonsmooth Optimization, Global Optimization, Nonlinear Optimization Tags , , , ,

    In the context of global optimization and mixed-integer non-linear programming, generalizing a technique of D’Ambrosio, Fampa, Lee and Vigerske for handling the square-root function, we develop a virtuous smoothing method, using cubics, aimed at functions having some limited non-smoothness. Our results pertain to root functions ($w^p$ with $0

    The Asynchronous PALM Algorithm for Nonsmooth Nonconvex Problems

  • Damek Davis
    • Categories Nonsmooth Optimization Tags , , , , ,

    We introduce the Asynchronous PALM algorithm, a new extension of the Proximal Alternating Linearized Minimization (PALM) algorithm for solving nonconvex nonsmooth optimization problems. Like the PALM algorithm, each step of the Asynchronous PALM algorithm updates a single block of coordinates; but unlike the PALM algorithm, the Asynchronous PALM algorithm eliminates the need for sequential updates … Read more

    Convergence analysis of the Peaceman-Rachford splitting method for nonsmooth convex optimization

  • Deren Han
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , ,

    In this paper, we focus on the convergence analysis for the application of the Peaceman-Rachford splitting method to a convex minimization model whose objective function is the sum of a smooth and nonsmooth convex functions. The sublinear convergence rate in term of the worst-case O(1/t) iteration complexity is established if the gradient of the smooth … Read more