slope

The complexity of first-order optimization methods from a metric perspective

  • Adrian Lewis
  • Tonghua Tian
    • Categories Nonsmooth Optimization, Other Topics Tags , , , , ,

    A central tool for understanding first-order optimization algorithms is the Kurdyka-Lojasiewicz inequality. Standard approaches to such methods rely crucially on this inequality to leverage sufficient decrease conditions involving gradients or subgradients. However, the KL property fundamentally concerns not subgradients but rather “slope”, a purely metric notion. By highlighting this view, and avoiding any use of … Read more

    Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
  • Alexander D. Ioffe
    • Categories Nonsmooth Optimization Tags , , , ,

    We consider optimization algorithms that successively minimize simple Taylor-like models of the objective function. Methods of Gauss-Newton type for minimizing the composition of a convex function and a smooth map are common examples. Our main result is an explicit relationship between the step-size of any such algorithm and the slope of the function at a … Read more

    Nonlinear local error bounds via a change of metric

  • Dominique Azé
  • Jean-Noël Corvellec
    • Categories Convex and Nonsmooth Optimization, Infinite Dimensional Optimization, Nonlinear Optimization Tags , ,

    In this work, we improve the approach of Corvellec-Motreanu to nonlinear error bounds for lowersemicontinuous functions on complete metric spaces, an approach consisting in reducing the nonlinear case to the linear one through a change of metric. This improvement is basically a technical one, and allows dealing with local error bounds in an appropriate way. … Read more

    Alternating projections and coupling slope

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
  • Alexander D. Ioffe
    • Categories Nonsmooth Optimization, Other Topics Tags , , , ,

    We consider the method of alternating projections for finding a point in the intersection of two possibly nonconvex closed sets. We present a local linear convergence result that makes no regularity assumptions on either set (unlike previous results), while at the same time weakening standard transversal intersection assumptions. The proof grows out of a study … Read more

    Trajectories of Descent

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
  • Alexander D. Ioffe
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    Steepest descent drives both theory and practice of nonsmooth optimization. We study slight relaxations of two influential notions of steepest descent curves — curves of maximal slope and solutions to evolution equations. In particular, we provide a simple proof showing that lower-semicontinuous functions that are locally Lipschitz continuous on their domains — functions playing a … Read more

    Slopes of multifunctions and extensions of metric regularity

  • Van Ngai Huynh
  • Alexander Y. Kruger
  • Michel Thera
    • Categories Nonsmooth Optimization Tags , , , ,

    This article aims to demonstrate how the definitions of slopes can be extended to multi-valued mappings between metric spaces and applied for characterizing metric regularity. Several kinds of local and nonlocal slopes are defined and several metric regularity properties for set-valued mappings between metric spaces are investigated. CitationPublished in Vietnam Journal of Mathematics 40:2&3(2012) 355-369. … Read more

    Error bounds for vector-valued functions on metric spaces

  • Ewa M. Bednarczuk
  • Alexander Y. Kruger
    • Categories Multi-Criteria Optimization, Nonsmooth Optimization Tags , , ,

    In this paper, we attempt to extend the definition and existing local error bound criteria to vector-valued functions, or more generally, to functions taking values in a normed linear space. Some new primal space derivative-like objects — slopes — are introduced and a classification scheme of error bound criteria is presented. CitationPublished in Vietnam Journal … Read more

    Stationarity and regularity of infinite collections of sets. Applications to infinitely constrained optimization

  • Alexander Y. Kruger
  • Marco A. López
    • Categories Nonsmooth Optimization, Semi-infinite Programming Tags , , , , , , , ,

    This article continues the investigation of stationarity and regularity properties of infinite collections of sets in a Banach space started in Kruger & L�pez (2012) and is mainly focused on the application of the criteria from Kruger & L�pez (2012) to infinitely constrained optimization problems. We consider several settings of optimization problems which involve (explicitly … Read more

    Error bounds for vector-valued functions: necessary and sufficient conditions

  • Ewa M. Bednarczuk
  • Alexander Y. Kruger
    • Categories Nonsmooth Optimization Tags , , ,

    In this paper, we attempt to extend the definition and existing local error bound criteria to vector-valued functions, or more generally, to functions taking values in a normed linear space. Some new derivative-like objects (slopes and subdifferentials) are introduced and a general classification scheme of error bound criteria is presented. CitationPublished in Nonlinear Analysis. Theory, … Read more

    About Stationarity and Regularity in Variational Analysis

  • Alexander Y. Kruger
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , , ,

    Stationarity and regularity concepts for the three typical for variational analysis classes of objects — real-valued functions, collections of sets, and multifunctions — are investigated. An attempt is maid to present a classification scheme for such concepts and to show that properties introduced for objects from different classes can be treated in a similar way. … Read more