Source author record

Juan C. Vera

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.OC math.PR Discrete Mathematics math.CO math-ph math.MP

Catalog footprint

Research overview

8works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Duality of Hoffman constants

We show that a suitable Slater condition implies a duality inequality between the Hoffman constants of the following feasibility problems: $\begin{array}{r} Ax-b \in S\\ x \in R \end{array} \qquad\text{ and }\qquad \begin{array}{r} c-A^T y \in R^*\\ y \in S^*. \end{array}$ where $A\in \mathbb{R}^{m\times n}$ , and $R\subseteq \mathbb{R}^n$ and $S\subseteq \mathbb{R}^m$ are reference polyhedral cones, with respective dual cones $R^*\subseteq \mathbb{R}^n$ and $S^*\subseteq \mathbb{R}^m$ . Our approach relies on an exact characterization of Hoffman constants and introduces a novel Hoffman duality inequality for polyhedral set-valued mappings. These two fundamental results also yield a striking identity between the Hoffman constants of box-constrained feasibility problems, which feature a similar primal-dual structure with a box and a linear subspace as reference sets. Additionally, we establish a surprising identity between the Hoffman constants of box-constrained feasibility problems and the chi condition measures for weighted least-squares problems

preprint2026arXiv

Lagrangian Reformulation for Nonconvex Optimization: Tailoring Problems to Specialized Solvers

In recent years, there has been a surge of interest in studying different ways to reformulate nonconvex optimization problems, especially those that involve binary variables. This interest surge is due to advancements in computing technologies, such as quantum and Ising devices, as well as improvements in quantum and classical optimization solvers that take advantage of particular formulations of nonconvex problems to tackle their solutions. Our research characterizes the equivalence between equality-constrained nonconvex optimization problems and their Lagrangian relaxation, enabling the aforementioned new technologies to solve these problems. In addition to filling a crucial gap in the literature, our results are readily applicable to many important situations in practice. To obtain these results, we bridge between specific optimization problem characteristics and broader, classical results on Lagrangian duality for general nonconvex problems. Further, our approach takes a comprehensive approach to the question of equivalence between problem formulations. We consider this question not only from the perspective of the problem's objective but also from the viewpoint of its solution. This perspective, often overlooked in existing literature, is particularly relevant for problems featuring continuous and binary variables.

preprint2020arXiv

Equivalence and invariance of the chi and Hoffman constants of a matrix

We show that the following two condition measures of a full column rank matrix $A \in \mathbb{R}^{m\times n}$ are identical: the chi constant and a signed Hoffman constant. This identity is naturally suggested by the evident invariance of the chi constant under sign changes of the rows of $A$ . We also show that similar equivalence and invariance properties extend to variants of the chi and Hoffman constants that depend only on the linear subspace $A(\mathbb{R}^n):=\{Ax: x\in\mathbb{R}^n\} \subseteq \mathbb{R}^m$ . Finally, we show similar identities between the chi constants and signed versions of Renegar's and Grassmannian condition measures.

preprint2016arXiv

On the convergence rate of grid search for polynomial optimization over the simplex

We consider the approximate minimization of a given polynomial on the standard simplex, obtained by taking the minimum value over all rational grid points with given denominator ${r} \in \mathbb{N}$ . It was shown in [De Klerk, E., Laurent, M., Sun, Z.: An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution. {\em SIAM J. Optim.} 25(3) 1498--1514 (2015)] that the relative accuracy of this approximation depends on $r$ as $O(1/r^2)$ if there exists a rational global minimizer. In this note we show that the rational minimizer condition is not necessary to obtain the $O(1/r^2)$ bound.

preprint2014arXiv

Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions

For the hard-core lattice gas model defined on independent sets weighted by an activity $λ$ , we study the critical activity $λ_c(\mathbb{Z}^2)$ for the uniqueness/non-uniqueness threshold on the 2-dimensional integer lattice $\mathbb{Z}^2$ . The conjectured value of the critical activity is approximately $3.796$ . Until recently, the best lower bound followed from algorithmic results of Weitz (2006). Weitz presented an FPTAS for approximating the partition function for graphs of constant maximum degree $Δ$ when $λ<λ_c(\mathbb{T}_Δ)$ where $\mathbb{T}_Δ$ is the infinite, regular tree of degree $Δ$ . His result established a certain decay of correlations property called strong spatial mixing (SSM) on $\mathbb{Z}^2$ by proving that SSM holds on its self-avoiding walk tree $T_{\mathrm{saw}}^σ(\mathbb{Z}^2)$ where $σ=(σ_v)_{v\in \mathbb{Z}^2}$ and $σ_v$ is an ordering on the neighbors of vertex $v$ . As a consequence he obtained that $λ_c(\mathbb{Z}^2)\geqλ_c( \mathbb{T}_4) = 1.675$ . Restrepo et al. (2011) improved Weitz's approach for the particular case of $\mathbb{Z}^2$ and obtained that $λ_c(\mathbb{Z}^2)>2.388$ . In this paper, we establish an upper bound for this approach, by showing that, for all $σ$ , SSM does not hold on $T_{\mathrm{saw}}^σ(\mathbb{Z}^2)$ when $λ>3.4$ . We also present a refinement of the approach of Restrepo et al. which improves the lower bound to $λ_c(\mathbb{Z}^2)>2.48$ .

preprint2012arXiv

Phase transition for the mixing time of the Glauber dynamics for coloring regular trees

We prove that the mixing time of the Glauber dynamics for random k-colorings of the complete tree with branching factor b undergoes a phase transition at $k=b(1+o_b(1))/\ln{b}$ . Our main result shows nearly sharp bounds on the mixing time of the dynamics on the complete tree with n vertices for $k=Cb/\ln{b}$ colors with constant C. For $C\geq1$ we prove the mixing time is $O(n^{1+o_b(1)}\ln{n})$ . On the other side, for $C<1$ the mixing time experiences a slowing down; in particular, we prove it is $O(n^{1/C+o_b(1)}\ln{n})$ and $Ω(n^{1/C-o_b(1)})$ . The critical point C=1 is interesting since it coincides (at least up to first order) with the so-called reconstruction threshold which was recently established by Sly. The reconstruction threshold has been of considerable interest recently since it appears to have close connections to the efficiency of certain local algorithms, and this work was inspired by our attempt to understand these connections in this particular setting.

preprint2011arXiv

Randomly coloring planar graphs with fewer colors than the maximum degree

We study Markov chains for randomly sampling $k$ -colorings of a graph with maximum degree $Δ$ . Our main result is a polynomial upper bound on the mixing time of the single-site update chain known as the Glauber dynamics for planar graphs when $k=Ω(Δ/\logΔ)$ . Our results can be partially extended to the more general case where the maximum eigenvalue of the adjacency matrix of the graph is at most $Δ^{1-\eps}$, for fixed $\eps > 0$. The main challenge when $k \le Δ+ 1$ is the possibility of "frozen" vertices, that is, vertices for which only one color is possible, conditioned on the colors of its neighbors. Indeed, when $Δ= O(1)$ , even a typical coloring can have a constant fraction of the vertices frozen. Our proofs rely on recent advances in techniques for bounding mixing time using "local uniformity" properties.

preprint2010arXiv

Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees

We study the effect of boundary conditions on the relaxation time of the Glauber dynamics for the hard-core model on the tree. The hard-core model is defined on the set of independent sets weighted by a parameter $λ$ , called the activity. The Glauber dynamics is the Markov chain that updates a randomly chosen vertex in each step. On the infinite tree with branching factor $b$ , the hard-core model can be equivalently defined as a broadcasting process with a parameter $ω$ which is the positive solution to $λ=ω(1+ω)^b$ , and vertices are occupied with probability $ω/(1+ω)$ when their parent is unoccupied. This broadcasting process undergoes a phase transition between the so-called reconstruction and non-reconstruction regions at $ω_r\approx \ln{b}/b$ . Reconstruction has been of considerable interest recently since it appears to be intimately connected to the efficiency of local algorithms on locally tree-like graphs, such as sparse random graphs. In this paper we show that the relaxation time of the Glauber dynamics on regular $b$ -ary trees $T_h$ of height $h$ and $n$ vertices, undergoes a phase transition around the reconstruction threshold. In particular, we construct a boundary condition for which the relaxation time slows down at the reconstruction threshold. More precisely, for any $ω\le \ln{b}/b$ , for $T_h$ with any boundary condition, the relaxation time is $Ω(n)$ and $O(n^{1+o_b(1)})$ . In contrast, above the reconstruction threshold we show that for every $δ>0$ , for $ω=(1+δ)\ln{b}/b$ , the relaxation time on $T_h$ with any boundary condition is $O(n^{1+δ+ o_b(1)})$ , and we construct a boundary condition where the relaxation time is $Ω(n^{1+δ/2 - o_b(1)})$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.