semi-algebraic

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

    The structure of conservative gradient fields

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

    The classical Clarke subdifferential alone is inadequate for understanding automatic differentiation in nonsmooth contexts. Instead, we can sometimes rely on enlarged generalized gradients called “conservative fields”, defined through the natural path-wise chain rule: one application is the convergence analysis of gradient-based deep learning algorithms. In the semi-algebraic case, we show that all conservative fields are … Read more

    Tangencies and Polynomial Optimization

  • Tiên-So'n Pham
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory Tags , , , , , , , , ,

    Given a polynomial function $f \colon \mathbb{R}^n \rightarrow \mathbb{R}$ and a unbounded basic closed semi-algebraic set $S \subset \mathbb{R}^n,$ in this paper we show that the conditions listed below are characterized exactly in terms of the so-called {\em tangency variety} of $f$ on $S$: (i) The $f$ is bounded from below on $S;$ (ii) The … Read more

    Local minimizers of semi-algebraic functions

  • Tiên-So'n Pham
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , , , ,

    Consider a semi-algebraic function $f\colon\mathbb{R}^n \to {\mathbb{R}},$ which is continuous around a point $\bar{x} \in \mathbb{R}^n.$ Using the so–called {\em tangency variety} of $f$ at $\bar{x},$ we first provide necessary and sufficient conditions for $\bar{x}$ to be a local minimizer of $f,$ and then in the case where $\bar{x}$ is an isolated local minimizer of … Read more

    On the Existence of Pareto Solutions for Polynomial Vector Optimization Problems

  • Do Sang Kim
  • Tiên-So'n Pham
  • Nguyen Van Tuyen
    • Categories Multi-Criteria Optimization, Unconstrained Optimization Tags , , , , ,

    We are interested in the existence of Pareto solutions to the vector optimization problem $$\text{\rm Min}_{\,\mathbb{R}^m_+} \{f(x) \,|\, x\in \mathbb{R}^n\},$$ where $f\colon\mathbb{R}^n\to \mathbb{R}^m$ is a polynomial map. By using the {\em tangency variety} of $f$ we first construct a semi-algebraic set of dimension at most $m – 1$ containing the set of Pareto values of … 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. Citation 13 pages, September, 2013 Article Download View Quadratic growth and critical point stability of semi-algebraic … 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

    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

    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

    Lipschitz behavior of the robust regularization

  • Adrian Lewis
  • C.H. Jeffrey Pang
    • Categories Control Applications, Nonsmooth Optimization, Robust Optimization Tags , , , , , , , ,

    To minimize or upper-bound the value of a function “robustly”, we might instead minimize or upper-bound the “epsilon-robust regularization”, defined as the map from a point to the maximum value of the function within an epsilon-radius. This regularization may be easy to compute: convex quadratics lead to semidefinite-representable regularizations, for example, and the spectral radius … Read more