skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Conservative and Semismooth Derivatives are Equivalent for Semialgebraic Maps
Subgradient and Newton algorithms for nonsmooth optimization require generalized derivatives to satisfy subtle approximation properties: conservativity for the former and semismoothness for the latter. Though these two properties originate in entirely different contexts, we show that in the semi-algebraic setting they are equivalent. Both properties for a generalized derivative simply require it to coincide with the standard directional derivative on the tangent spaces of some partition of the domain into smooth manifolds. An appealing byproduct is a new short proof that semi-algebraic maps are semismooth relative to the Clarke Jacobian.  more » « less
Award ID(s):
2047637
PAR ID:
10312272
Author(s) / Creator(s):
;
Date Published:
Journal Name:
Set-Valued and Variational Analysis
ISSN:
1877-0533
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Discrete & Computational Geometry)
    Let $$\R$$ be a real closed field and $$\C$$ the algebraic closure of $$\R$$. We give an algorithm for computing a semi-algebraic basis for the first homology group, $$\HH_1(S,\mathbb{F})$$, with coefficients in a field $$\FF$$, of any given semi-algebraic set $$S \subset \R^k$$ defined by a closed formula. The complexity of the algorithm is bounded singly exponentially. More precisely, if the given quantifier-free formula involves $$s$$ polynomials whose degrees are bounded by $$d$$, the complexity of the algorithm is bounded by $$(s d)^{k^{O(1)}}$$. This algorithm generalizes well known algorithms having singly exponential complexity for computing a semi-algebraic basis of the zero-th homology group of semi-algebraic sets, which is equivalent to the problem of computing a set of points meeting every semi-algebraically connected component of the given semi-algebraic set at a unique point. It is not known how to compute such a basis for the higher homology groups with singly exponential complexity. As an intermediate step in our algorithm we construct a semi-algebraic subset $$\Gamma$$ of the given semi-algebraic set $$S$$, such that $$\HH_q(S,\Gamma) = 0$$ for $q=0,1$. We relate this construction to a basic theorem in complex algebraic geometry stating that for any affine variety $$X$$ of dimension $$n$$, there exists Zariski closed subsets \[ Z^{(n-1)} \supset \cdots \supset Z^{(1)} \supset Z^{(0)} \] with $$\dim_\C Z^{(i)} \leq i$, and $$\HH_q(X,Z^{(i)}) = 0$$ for $$0 \leq q \leq i$$. We conjecture a quantitative version of this result in the semi-algebraic category, with $$X$$ and $$Z^{(i)}$$ replaced by closed semi-algebraic sets. We make initial progress on this conjecture by proving the existence of $$Z^{(0)}$$ and $$Z^{(1)}$$ with complexity bounded singly exponentially (previously, such an algorithm was known only for constructing $$Z^{(0)}$$). 
    more » « less
  2. ; ; (, ACM Communications in Computer Algebra)
    Many algorithms for determining properties of semi-algebraic sets rely upon the ability to compute smooth points [1]. We present a simple procedure based on computing the critical points of some well-chosen function that guarantees the computation of smooth points in each connected bounded component of a real atomic semi-algebraic set. Our technique is intuitive in principal, performs well on previously difficult examples, and is straightforward to implement using existing numerical algebraic geometry software. The practical efficiency of our approach is demonstrated by solving a conjecture on the number of equilibria of the Kuramoto model for then= 4 case. We also apply our method to design an efficient algorithm to compute the real dimension of algebraic sets, the original motivation for this research. 
    more » « less
  3. ; ; ; ; (, Journal of the ACM)
    Recursive queries have been traditionally studied in the framework of datalog, a language that restricts recursion to monotone queries over sets, which is guaranteed to converge in polynomial time in the size of the input. But modern big data systems require recursive computations beyond the Boolean space. In this article, we study the convergence of datalog when it is interpreted over an arbitrary semiring. We consider an ordered semiring, define the semantics of a datalog program as a least fixpoint in this semiring, and study the number of steps required to reach that fixpoint, if ever. We identify algebraic properties of the semiring that correspond to certain convergence properties of datalog programs. Finally, we describe a class of ordered semirings on which one can use the semi-naïve evaluation algorithm on any datalog program. 
    more » « less
  4. ; ; ; (, Journal of High Energy Physics)
    A<sc>bstract</sc> Gauging is a powerful operation on symmetries in quantum field theory (QFT), as it connects distinct theories and also reveals hidden structures in a given theory. We initiate a systematic investigation of gauging discrete generalized symmetries in two-dimensional QFT. Such symmetries are described by topological defect lines (TDLs) which obey fusion rules that are non-invertible in general. Despite this seemingly exotic feature, all well-known properties in gauging invertible symmetries carry over to this general setting, which greatly enhances both the scope and the power of gauging. This is established by formulating generalized gauging in terms of topological interfaces between QFTs, which explains the physical picture for the mathematical concept of algebra objects and associated module categories over fusion categories that encapsulate the algebraic properties of generalized symmetries and their gaugings. This perspective also provides simple physical derivations of well-known mathematical theorems in category theory from basic axiomatic properties of QFT in the presence of such interfaces. We discuss a bootstrap-type analysis to classify such topological interfaces and thus the possible generalized gaugings and demonstrate the procedure in concrete examples of fusion categories. Moreover we present a number of examples to illustrate generalized gauging and its properties in concrete conformal field theories (CFTs). In particular, we identify the generalized orbifold groupoid that captures the structure of fusion between topological interfaces (equivalently sequential gaugings) as well as a plethora of new self-dualities in CFTs under generalized gaugings. 
    more » « less
  5. ; (, Communications in Mathematical Physics)
    Abstract We prove that all Galerkin truncations of the 2d stochastic Navier–Stokes equations in vorticity form on any rectangular torus subjected to hypoelliptic, additive stochastic forcing are chaotic at sufficiently small viscosity, provided the frequency truncation satisfies$$N\ge 392$$ N ≥ 392 . By “chaotic” we mean having a strictly positive Lyapunov exponent, i.e. almost-sure asymptotic exponential growth of the derivative with respect to generic initial conditions. A sufficient condition for such results was derived in previous joint work with Alex Blumenthal which reduces the question to the non-degeneracy of a matrix Lie algebra implying Hörmander’s condition for the Markov process lifted to the sphere bundle (projective hypoellipticity). The purpose of this work is to reformulate this condition to be more amenable for Galerkin truncations of PDEs and then to verify this condition using (a) a reduction to genericity properties of a diagonal sub-algebra inspired by the root space decomposition of semi-simple Lie algebras and (b) computational algebraic geometry executed by Maple in exact rational arithmetic. Note that even though we use a computer assisted proof, the result is valid for all aspect ratios and all sufficiently high dimensional truncations; in fact, certain steps simplify in the formal infinite dimensional limit. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email