Nonsmooth Optimization

Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems

  • Max L. N. Gonçalves
  • Jefferson Gonçalves Melo
  • Renato D.C. Monteiro
    • Categories Convex and Nonsmooth Optimization, Nonsmooth Optimization Tags , , ,

    This paper establishes convergence rate bounds for a variant of the proximal alternating direction method of multipliers (ADMM) for solving nonconvex linearly constrained optimization problems. The variant of the proximal ADMM allows the inclusion of an over-relaxation stepsize parameter belonging to the interval (0,2). To the best of our knowledge, all related papers in the … Read more

    On level regularization with normal solutions in decomposition methods for multistage stochastic programming problems

  • Welington de Oliveira
  • Yongjia Song
  • Wim van Ackooij
    • Categories Nonsmooth Optimization, Stochastic Programming Tags , , ,

    We consider well-known decomposition techniques for multistage stochastic programming and a new scheme based on normal solutions for stabilizing iterates during the solution process. The given algorithms combine ideas from finite perturbation of convex programs and level bundle methods to regularize the so-called forward step of these decomposition methods. Numerical experiments on a hydrothermal scheduling … Read more

    A Limited-Memory Quasi-Newton Algorithm for Bound-Constrained Nonsmooth Optimization

  • Nitish Shirish Keskar
  • Andreas Wächter
    • Categories Bound-constrained Optimization, Nonsmooth Optimization

    We consider the problem of minimizing a continuous function that may be nonsmooth and nonconvex, subject to bound constraints. We propose an algorithm that uses the L-BFGS quasi-Newton approximation of the problem’s curvature together with a variant of the weak Wolfe line search. The key ingredient of the method is an active-set selection strategy that … Read more

    Efficiency of minimizing compositions of convex functions and smooth maps

  • Dmitriy Drusvyatskiy
  • Courtney Paquette
    • Categories Nonsmooth Optimization Tags , , , , , ,

    We consider the problem of minimizing a sum of a convex function and a composition of a convex function with a smooth map. Important examples include exact penalty formulations of nonlinear programs and nonlinear least squares problems with side constraints. The basic algorithm we rely on is the well-known prox-linear method, which in each iteration … Read more

    An Algorithm for Nonsmooth Optimization by Successive Piecewise Linearization

  • Sabrina Fiege
  • Andreas Griewank
  • Andrea Walther
    • Categories Nonsmooth Optimization Tags , , , ,

    We present an optimization method for Lipschitz continuous, piecewise smooth (PS) objective functions based on successive piecewise linearization. Since, in many realistic cases, nondifferentiabilities are caused by the occurrence of abs(), max(), and min(), we concentrate on these nonsmooth elemental functions. The method’s idea is to locate an optimum of a PS objective function by … Read more

    Optimization Algorithms for Data Analysis

  • Stephen Wright
    • Categories Data-Mining, Nonsmooth Optimization, Unconstrained Optimization Tags ,

    We describe the fundamentals of algorithms for minimizing a smooth nonlinear function, and extensions of these methods to the sum of a smooth function and a convex nonsmooth function. Such objective functions are ubiquitous in data analysis applications, as we illustrate using several examples. We discuss methods that make use of gradient (first-order) information about … Read more

    Global Convergence of ADMM in Nonconvex Nonsmooth Optimization

  • Yu Wang
  • Wotao Yin
  • Jinshan Zeng
    • Categories Nonsmooth Optimization Tags , , , ,

    In this paper, we analyze the convergence of the alternating direction method of multipliers (ADMM) for minimizing a nonconvex and possibly nonsmooth objective function, $\phi(x_0,\ldots,x_p,y)$, subject to coupled linear equality constraints. Our ADMM updates each of the primal variables $x_0,\ldots,x_p,y$, followed by updating the dual variable. We separate the variable $y$ from $x_i$’s as it … Read more

    Efficient solution of quadratically constrained quadratic subproblems within the MADS algorithm

  • Nadir Amaioua
  • Charles Audet
  • Andrew R. Conn
  • Sébastien Le Digabel
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization

    The Mesh Adaptive Direct Search algorithm (MADS) is an iterative method for constrained blackbox optimization problems. One of the optional MADS features is a versatile search step in which quadratic models are built leading to a series of quadratically constrained quadratic subproblems. This work explores different algorithms that exploit the structure of the quadratic models: … Read more

    The Rate of Convergence of Augmented Lagrange Method for a Composite Optimization Problem

  • Jihong Zhang
  • Liwei Zhang
  • Yule Zhang
    • Categories Applications - OR and Management Sciences, Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    In this paper we analyze the rate of local convergence of the augmented Lagrange method for solving optimization problems with equality constraints and the objective function expressed as the sum of a convex function and a twice continuously differentiable function. The presence of the non-smoothness of the convex function in the objective requires extensive tools … Read more