More Like this

1. On the stationarity for nonlinear optimization problems with polyhedral constraints

   https://doi.org/10.1007/s10107-023-01979-9  

   di Serafino, Daniela; Hager, William W.; Toraldo, Gerardo; Viola, Marco (May 2023, Mathematical Programming)

   Abstract For polyhedral constrained optimization problems and a feasible point$$\textbf{x}$$ $x$, it is shown that the projection of the negative gradient on the tangent cone, denoted$$\nabla _\varOmega f(\textbf{x})$$ ${\nabla }_{\Omega }f\left(x\right)$, has an orthogonal decomposition of the form$$\varvec{\beta }(\textbf{x}) + \varvec{\varphi }(\textbf{x})$$ $\beta \left(x\right)+\phi \left(x\right)$. At a stationary point,$$\nabla _\varOmega f(\textbf{x}) = \textbf{0}$$ ${\nabla }_{\Omega }f\left(x\right)=0$so$$\Vert \nabla _\varOmega f(\textbf{x})\Vert $$ $\Vert {\nabla }_{\Omega }f\left(x\right)\Vert$reflects the distance to a stationary point. Away from a stationary point,$$\Vert \varvec{\beta }(\textbf{x})\Vert $$ $\Vert \beta \left(x\right)\Vert$and$$\Vert \varvec{\varphi }(\textbf{x})\Vert $$ $\Vert \phi \left(x\right)\Vert$measure different aspects of optimality since$$\varvec{\beta }(\textbf{x})$$ $\beta \left(x\right)$only vanishes when the KKT multipliers at$$\textbf{x}$$ $x$have the correct sign, while$$\varvec{\varphi }(\textbf{x})$$ $\phi \left(x\right)$only vanishes when$$\textbf{x}$$ $x$is a stationary point in the active manifold. As an application of the theory, an active set algorithm is developed for convex quadratic programs which adapts the flow of the algorithm based on a comparison between$$\Vert \varvec{\beta }(\textbf{x})\Vert $$ $\Vert \beta \left(x\right)\Vert$and$$\Vert \varvec{\varphi }(\textbf{x})\Vert $$ $\Vert \phi \left(x\right)\Vert$. 

   more » « less
2. Block mapping class groups and their finiteness properties

   https://doi.org/10.1007/s10711-025-00985-9  

   Aramayona, J; Aroca, J; Cumplido, M; Skipper, R; Wu, X (April 2025, Geometriae Dedicata)

   Abstract Given$$g \in \mathbb N \cup \{0, \infty \}$$ $g\in N\cup \{0,\infty \}$, let$$\Sigma _g$$ ${\Sigma }_g$denote the closed surface of genusgwith a Cantor set removed, if$$g<\infty $$ $g<\infty$; or the blooming Cantor tree, when$$g= \infty $$ $g=\infty$. We construct a family$$\mathfrak B(H)$$ $B\left(H\right)$of subgroups of$${{\,\textrm{Map}\,}}(\Sigma _g)$$ $\text{Map}\left({\Sigma }_g\right)$whose elements preserve ablock decompositionof$$\Sigma _g$$ ${\Sigma }_g$, andeventually like actlike an element ofH, whereHis a prescribed subgroup of the mapping class group of the block. The group$$\mathfrak B(H)$$ $B\left(H\right)$surjects onto an appropriate symmetric Thompson group of Farley–Hughes; in particular, it answers positively. Our main result asserts that$$\mathfrak B(H)$$ $B\left(H\right)$is of type$$F_n$$ $F_n$if and only ifHis. As a consequence, for every$$g\in \mathbb N \cup \{0, \infty \}$$ $g\in N\cup \{0,\infty \}$and every$$n\ge 1$$ $n\ge 1$, we construct a subgroup$$G <{{\,\textrm{Map}\,}}(\Sigma _g)$$ $G<\text{Map}\left({\Sigma }_g\right)$that is of type$$F_n$$ $F_n$but not of type$$F_{n+1}$$ $F_{n+1}$, and which contains the mapping class group of every compact surface of genus$$\le g$$ $\le g$and with non-empty boundary. 

   more » « less
3. Hardness and approximation of submodular minimum linear ordering problems

   https://doi.org/10.1007/s10107-023-02038-z  

   Farhadi, Majid; Gupta, Swati; Sun, Shengding; Tetali, Prasad; Wigal, Michael C (December 2023, Mathematical Programming)

   Abstract The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost$$f(\cdot )$$ $f(·)$due to an ordering$$\sigma $$ $\sigma$of the items (say [n]), i.e.,$$\min _{\sigma } \sum _{i\in [n]} f(E_{i,\sigma })$$ ${min}_{\sigma }{\sum }_{i\in \left[n\right]}f\left(E_{i,\sigma }\right)$, where$$E_{i,\sigma }$$ $E_{i,\sigma }$is the set of items mapped by$$\sigma $$ $\sigma$to indices [i]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NP-hard. We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata et al. (in: APPROX, 2012), using Lovász extension of submodular functions. We show a$$(2-\frac{1+\ell _{f}}{1+|E|})$$ $(2-\frac{1+{\ell }_f}{1+\left|E\right|})$-approximation for monotone submodular MLOP where$$\ell _{f}=\frac{f(E)}{\max _{x\in E}f(\{x\})}$$ ${\ell }_f=\frac{f\left(E\right)}{{max}_{x\in E}f\left(\left\{x\right\}\right)}$satisfies$$1 \le \ell _f \le |E|$$ $1\le {\ell }_f\le \left|E\right|$. Our theory provides new approximation bounds for special cases of the problem, in particular a$$(2-\frac{1+r(E)}{1+|E|})$$ $(2-\frac{1+r\left(E\right)}{1+\left|E\right|})$-approximation for the matroid MLOP, where$$f = r$$ $f=r$is the rank function of a matroid. We further show that minimum latency vertex cover is$$\frac{4}{3}$$ $\frac{4}{3}$-approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest. 

   more » « less
4. The Brown measure of the free multiplicative Brownian motion

   https://doi.org/10.1007/s00440-022-01142-z  

   Driver, Bruce K.; Hall, Brian; Kemp, Todd (October 2022, Probability Theory and Related Fields)

   Abstract The free multiplicative Brownian motion$$b_{t}$$ $b_t$is the large-Nlimit of the Brownian motion on$$\mathsf {GL}(N;\mathbb {C}),$$ $\mathrm{GL}(N;C),$in the sense of$$*$$ $\ast$-distributions. The natural candidate for the large-Nlimit of the empirical distribution of eigenvalues is thus the Brown measure of$$b_{t}$$ $b_t$. In previous work, the second and third authors showed that this Brown measure is supported in the closure of a region$$\Sigma _{t}$$ ${\Sigma }_t$that appeared in the work of Biane. In the present paper, we compute the Brown measure completely. It has a continuous density$$W_{t}$$ $W_t$on$$\overline{\Sigma }_{t},$$ ${\overline{\Sigma }}_t,$which is strictly positive and real analytic on$$\Sigma _{t}$$ ${\Sigma }_t$. This density has a simple form in polar coordinates:$$\begin{aligned} W_{t}(r,\theta )=\frac{1}{r^{2}}w_{t}(\theta ), \end{aligned}$$ $\begin{array}{c}{W}_t(r,\theta )=\frac{1}{r^2}{w}_t\left(\theta \right),\end{array}$where$$w_{t}$$ $w_t$is an analytic function determined by the geometry of the region$$\Sigma _{t}$$ ${\Sigma }_t$. We show also that the spectral measure of free unitary Brownian motion$$u_{t}$$ $u_t$is a “shadow” of the Brown measure of$$b_{t}$$ $b_t$, precisely mirroring the relationship between the circular and semicircular laws. We develop several new methods, based on stochastic differential equations and PDE, to prove these results. 

   more » « less
5. Generalized Parking Function Polytopes

   https://doi.org/10.1007/s00026-023-00671-1  

   Hanada, Mitsuki; Lentfer, John; Vindas-Meléndez, Andrés_R (November 2023, Annals of Combinatorics)

   Abstract A classical parking function of lengthnis a list of positive integers$$(a_1, a_2, \ldots , a_n)$$ $(a_1,a_2,\dots ,a_n)$whose nondecreasing rearrangement$$b_1 \le b_2 \le \cdots \le b_n$$ $b_1\le b_2\le \cdots \le b_n$satisfies$$b_i \le i$$ $b_i\le i$. The convex hull of all parking functions of lengthnis ann-dimensional polytope in$${\mathbb {R}}^n$$ $R^n$, which we refer to as the classical parking function polytope. Its geometric properties have been explored in Amanbayeva and Wang (Enumer Combin Appl 2(2):Paper No. S2R10, 10, 2022) in response to a question posed by Stanley (Amer Math Mon 127(6):563–571, 2020). We generalize this family of polytopes by studying the geometric properties of the convex hull of$${\textbf{x}}$$ $x$-parking functions for$${\textbf{x}}=(a,b,\dots ,b)$$ $x=(a,b,\cdots ,b)$, which we refer to as$${\textbf{x}}$$ $x$-parking function polytopes. We explore connections between these$${\textbf{x}}$$ $x$-parking function polytopes, the Pitman–Stanley polytope, and the partial permutahedra of Heuer and Striker (SIAM J Discrete Math 36(4):2863–2888, 2022). In particular, we establish a closed-form expression for the volume of$${\textbf{x}}$$ $x$-parking function polytopes. This allows us to answer a conjecture of Behrend et al. (2022) and also obtain a new closed-form expression for the volume of the convex hull of classical parking functions as a corollary. 

   more » « less