quadratic growth

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

    General Convergence Rates Follow From Specialized Rates Assuming Growth Bounds

  • Benjamin Grimmer
    • Categories Convex Optimization Tags , ,

    Often in the analysis of first-order methods, assuming the existence of a quadratic growth bound (a generalization of strong convexity) facilitates much stronger convergence analysis. Hence the analysis is done twice, once for the general case and once for the growth bounded case. We give a meta-theorem for deriving general convergence rates from those assuming … Read more

    Error bounds, quadratic growth, and linear convergence of proximal methods

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
    • Categories Nonsmooth Optimization Tags , , , ,

    We show that the the error bound property, postulating that the step lengths of the proximal gradient method linearly bound the distance to the solution set, is equivalent to a standard quadratic growth condition. We exploit this equivalence in an analysis of asymptotic linear convergence of the proximal gradient algorithm for structured problems, which lack … Read more

    Stability and genericity for semi-algebraic compact programs

  • Gue Myung Lee
  • Tiên-So'n Pham
    • Categories Constrained Nonlinear Optimization, Global Optimization Tags , , , , , , ,

    In this paper we consider the class of polynomial optimization problems with inequality and equality constraints, in which every problem of the class is obtained by perturbations of the objective function, while the constraint functions are kept fixed. Under certain assumptions, we establish some stability properties (e.g., strong H\”older stability with explicitly determined exponents, semicontinuity, … Read more

    Quadratic growth and critical point stability of semi-algebraic functions

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

    We show that quadratic growth of a semi-algebraic function is equivalent to strong metric subregularity of the subdifferential — a kind of stability of generalized critical points. In contrast, this equivalence can easily fail outside of the semi-algebraic setting. Citation13 pages, September, 2013ArticleDownload View PDF

    Full stability of locally optimal solutions in second-order cone programming

  • Boris S. Mordukhovich
  • Jiri V. Outrata
  • Ebrahim Sarabi
    • Categories Nonsmooth Optimization Tags , , , , , ,

    The paper presents complete characterizations of Lipschitzian full stability of locally optimal solutions to problems of second-order cone programming (SOCP) expressed entirely in terms of their initial data. These characterizations are obtained via appropriate versions of the quadratic growth and strong second-order sucient conditions under the corresponding constraint quali cations. We also establish close relationships between … Read more

    Second-order growth, tilt stability, and metric regularity of the subdifferential

  • Dmitriy Drusvyatskiy
  • Boris S. Mordukhovich
  • Nghia Tran
    • Categories Nonsmooth Optimization Tags , , , , ,

    This paper sheds new light on several interrelated topics of second-order variational analysis, both in finite and infinite-dimensional settings. We establish new relationships between second-order growth conditions on functions, the basic properties of metric regularity and subregularity of the limiting subdifferential, tilt-stability of local minimizers, and positive definiteness/semidefiniteness properties of the second-order subdifferential (or generalized … Read more

    Tilt stability, uniform quadratic growth, and strong metric regularity of the subdifferential.

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , ,

    We prove that uniform second order growth, tilt stability, and strong metric regularity of the subdifferential — three notions that have appeared in entirely different settings — are all essentially equivalent for any lower-semicontinuous, extended-real-valued function. CitationCornell University, School of Operations Research and Information Engineering, 206 Rhodes Hall Cornell University Ithaca, NY 14853. May 2012.ArticleDownload … Read more

    Optimal control of a parabolic equation with time-dependent state constraints

  • Joseph Frédéric Bonnans
  • Pascal Jaisson
    • Categories Distributed Control Tags , , , , , , ,

    In this paper we study the optimal control problem of the heat equation by a distributed control over a subset of the domain, in the presence of a state constraint. The latter is integral over the space and has to be satisfied at each time. Using for the first time the technique of alternative optimality … Read more