More Like this

1. On the convex hull of convex quadratic optimization problems with indicators

   https://doi.org/10.1007/s10107-023-01982-0  

   Wei, Linchuan; Atamtürk, Alper; Gómez, Andrés; Küçükyavuz, Simge (June 2023, Mathematical Programming)

   Abstract We consider the convex quadratic optimization problem in$$\mathbb {R}^{n}$$ $R^n$with indicator variables and arbitrary constraints on the indicators. We show that a convex hull description of the associated mixed-integer set in an extended space with a quadratic number of additional variables consists of an$$(n+1) \times (n+1)$$ $(n+1)\times (n+1)$positive semidefinite constraint (explicitly stated) and linear constraints. In particular, convexification of this class of problems reduces to describing a polyhedral set in an extended formulation. While the vertex representation of this polyhedral set is exponential and an explicit linear inequality description may not be readily available in general, we derive a compact mixed-integer linear formulation whose solutions coincide with the vertices of the polyhedral set. We also give descriptions in the original space of variables: we provide a description based on an infinite number of conic-quadratic inequalities, which are “finitely generated.” In particular, it is possible to characterize whether a given inequality is necessary to describe the convex hull. The new theory presented here unifies several previously established results, and paves the way toward utilizing polyhedral methods to analyze the convex hull of mixed-integer nonlinear sets. 

   more » « less
2. Numerical Fuzz: A Type System for Rounding Error Analysis

   https://doi.org/10.1145/3656456  

   Kellison, Ariel_E; Hsu, Justin (June 2024, Proceedings of the ACM on Programming Languages)

   Algorithms operating on real numbers are implemented as floating-point computations in practice, but floatingpoint operations introduceroundoff errorsthat can degrade the accuracy of the result. We propose ${\mathrm{\Lambda }}_{\mathbf{num}}$, a functional programming language with a type system that can express quantitative bounds on roundoff error. Our type system combines a sensitivity analysis, enforced through a linear typing discipline, with a novel graded monad to track the accumulation of roundoff errors. We prove that our type system is sound by relating the denotational semantics of our language to the exact and floating-point operational semantics. To demonstrate our system, we instantiate ${\mathrm{\Lambda }}_{\mathbf{num}}$with error metrics proposed in the numerical analysis literature and we show how to incorporate rounding operations that faithfully model aspects of the IEEE 754 floating-point standard. To show that ${\mathrm{\Lambda }}_{\mathbf{num}}$can be a useful tool for automated error analysis, we develop a prototype implementation for ${\mathrm{\Lambda }}_{\mathbf{num}}$that infers error bounds that are competitive with existing tools, while often running significantly faster. Finally, we consider semantic extensions of our graded monad to bound error under more complex rounding behaviors, such as non-deterministic and randomized rounding. 

   more » « less
3. On the Size of the Singular Set of Minimizing Harmonic Maps

   https://doi.org/10.1090/memo/1519  

   Mazowiecka, Katarzyna; Miśkiewicz, Michał; Schikorra, Armin (October 2024, Memoirs of the American Mathematical Society)

   We consider minimizing harmonic maps $u$from $\mathrm{\Omega <\#comment/>}\subset <\#comment/>{\mathbb{R}}^n$into a closed Riemannian manifold $\mathcal{N}$and prove: 1. an extension to $n\ge <\#comment/>4$of Almgren and Lieb’s linear law. That is, if the fundamental group of the target manifold $\mathcal{N}$is finite, we have\[ ${\mathcal{H}}^{n-<\#comment/>3}(\mathrm{sing}<\#comment/>u)\le <\#comment/>C{\int <\#comment/>}_{\mathrm{\partial <\#comment/>}\mathrm{\Omega <\#comment/>}}|{\mathrm{\nabla <\#comment/>}}_{T}u{|}^{n-<\#comment/>1}\mathrm{d}{\mathcal{H}}^{n-<\#comment/>1};$\]2. an extension of Hardt and Lin’s stability theorem. Namely, assuming that the target manifold is $\mathcal{N}={\mathbb{S}}^2$we obtain that the singular set of $u$is stable under small $W^{1,n-<\#comment/>1}$-perturbations of the boundary data. In dimension $n=3$both results are shown to hold with weaker hypotheses, i.e., only assuming that the trace of our map lies in the fractional space $W^{s,p}$with $s\in <\#comment/>(\frac{1}{2},1]$and $p\in <\#comment/>[2,\mathrm{\infty <\#comment/>})$satisfying $sp\ge <\#comment/>2$. We also discuss sharpness. 

   more » « less
4. Intersections of dual 𝑆𝐿₃-webs

   https://doi.org/10.1090/tran/9349  

   Shen, Linhui; Sun, Zhe; Weng, Daping (August 2025, Transactions of the American Mathematical Society)

   We introduce a topological intersection number for an ordered pair of ${\mathrm{SL}}_3$-webs on a decorated surface. Using this intersection pairing between reduced $({\mathrm{SL}}_3,\mathcal{A})$-webs and a collection of $({\mathrm{SL}}_3,\mathcal{X})$-webs associated with the Fock–Goncharov cluster coordinates, we provide a natural combinatorial interpretation of the bijection from the set of reduced $({\mathrm{SL}}_3,\mathcal{A})$-webs to the tropical set ${\mathcal{A}}_{{\mathrm{PGL}}_3,\stackrel{^<\#comment/>}{S}}^{+}\left({\mathbb{Z}}^t\right)$, as established by Douglas and Sun in [Forum Math. Sigma 12 (2024), p. e5, 55]. We provide a new proof of the flip equivariance of the above bijection, which is crucial for proving the Fock–Goncharov duality conjecture of higher Teichmüller spaces for ${\mathrm{SL}}_3$. 

   more » « less
5. Mapping class groups of exotic tori and actions by 𝑆𝐿_{𝑑}(𝐙)

   https://doi.org/10.1090/btran/207  

   Bustamante, Mauricio; Krannich, Manuel; Kupers, Alexander; Tshishiku, Bena (November 2024, Transactions of the American Mathematical Society, Series B)

   We determine for which exotic tori $\mathcal{T}$of dimension $d\ne <\#comment/>4$the homomorphism from the group of isotopy classes of orientation-preserving diffeomorphisms of $\mathcal{T}$to ${\mathrm{S}\mathrm{L}}_d\left(\mathbf{Z}\right)$given by the action on the first homology group is split surjective. As part of the proof we compute the mapping class group of all exotic tori $\mathcal{T}$that are obtained from the standard torus by a connected sum with an exotic sphere. Moreover, we show that any nontrivial ${\mathrm{S}\mathrm{L}}_d\left(\mathbf{Z}\right)$-action on $\mathcal{T}$agrees on homology with the standard action, up to an automorphism of ${\mathrm{S}\mathrm{L}}_d\left(\mathbf{Z}\right)$. When combined, these results in particular show that many exotic tori do not admit any nontrivial differentiable action by ${\mathrm{S}\mathrm{L}}_d\left(\mathbf{Z}\right)$. 

   more » « less