Adrian Lewis

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. Citation Cornell University, School of Operations Research and Information Engineering, 206 Rhodes Hall Cornell University Ithaca, NY 14853. May … Read more

    Partial Smoothness,Tilt Stability, and Generalized Hessians

  • Adrian Lewis
  • Shanshan Zhang
    • Categories Nonsmooth Optimization Tags , , , , , , , ,

    We compare two recent variational-analytic approaches to second-order conditions and sensitivity analysis for nonsmooth optimization. We describe a broad setting where computing the generalized Hessian of Mordukhovich is easy. In this setting, the idea of tilt stability introduced by Poliquin and Rockafellar is equivalent to a classical smooth second-order condition. Article Download View Partial Smoothness,Tilt … Read more

    The dimension of semialgebraic subdifferential graphs.

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

    Examples exist of extended-real-valued closed functions on $\R^n$ whose subdifferentials (in the standard, limiting sense) have large graphs. By contrast, if such a function is semi-algebraic, then its subdifferential graph must have everywhere constant local dimension $n$. This result is related to a celebrated theorem of Minty, and surprisingly may fail for the Clarke subdifferential. … Read more

    Generic nondegeneracy in convex optimization

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

    We show that minimizers of convex functions subject to almost all linear perturbations are nondegenerate. An analogous result holds more generally, for lower-C^2 functions. Citation Cornell University, School of Operations Research and Information Engineering, 206 Rhodes Hall Cornell University Ithaca, NY 14853. May 2010. Article Download View Generic nondegeneracy in convex optimization

    Semi-algebraic functions have small subdifferentials

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

    We prove that the subdifferential of any semi-algebraic extended-real-valued function on $\R^n$ has $n$-dimensional graph. We discuss consequences for generic semi-algebraic optimization problems. Citation Cornell University, School of Operations Research and Information Engineering, 206 Rhodes Hall Cornell University Ithaca, NY 14853. April 2010. Article Download View Semi-algebraic functions have small subdifferentials

    Generic identifiability and second-order sufficiency in tame convex optimization

  • Jérôme Bolte
  • Aris Daniilidis
  • Adrian Lewis
    • Categories Convex Optimization Tags , , ,

    We consider linear optimization over a fixed compact convex feasible region that is semi-algebraic (or, more generally, “tame”). Generically, we prove that the optimal solution is unique and lies on a unique manifold, around which the feasible region is “partly smooth”, ensuring finite identification of the manifold by many optimization algorithms. Furthermore, second-order optimality conditions … Read more

    Identifying Activity

  • Adrian Lewis
  • Stephen Wright
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    Identification of active constraints in constrained optimization is of interest from both practical and theoretical viewpoints, as it holds the promise of reducing an inequality-constrained problem to an equality-constrained problem, in a neighborhood of a solution. We study this issue in the more general setting of composite nonsmooth minimization, in which the objective is a … Read more

    Nonsmooth Optimization via BFGS

  • Adrian Lewis
  • Michael L. Overton
    • Categories Nonsmooth Optimization Tags , , , , ,

    We investigate the BFGS algorithm with an inexact line search when applied to nonsmooth functions, not necessarily convex. We define a suitable line search and show that it generates a sequence of nested intervals containing points satisfying the Armijo and weak Wolfe conditions, assuming only absolute continuity. We also prove that the line search terminates … Read more

    Behavior of BFGS with an Exact Line Search on Nonsmooth Examples

  • Adrian Lewis
  • Michael L. Overton
    • Categories Nonsmooth Optimization Tags , , , , ,

    We investigate the behavior of the BFGS algorithm with an exact line search on nonsmooth functions. We show that it may fail on a simple polyhedral example, but that it apparently always succeeds on the Euclidean norm function, spiraling into the origin with a Q-linear rate of convergence; we prove this in the case of … Read more

    A proximal method for composite minimization

  • Adrian Lewis
  • Stephen Wright
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    We consider minimization of functions that are compositions of convex or prox-regular functions (possibly extended-valued) with smooth vector functions. A wide variety of important optimization problems fall into this framework. We describe an algorithmic framework based on a subproblem constructed from a linearized approximation to the objective and a regularization term. Properties of local solutions … Read more