We consider the problem of solving nonconvex quadratic optimization problems, potentially with additional integrality constraints on the variables.  Gurobi takes a branch-and-bound approach to solve such problems to global optimality, and in this talk we will review the three main algorithmic components that Gurobi uses:  Convex relaxations based on local linearization, globally valid cutting planes, and nonlinear local optimization heuristics.  We will explain how these parts play together, and discuss some of the implementation details.

The numerical solution of elliptic PDEs is often the most computationally intensive task in large-scale continuum mechanics simulations.  High-order finite element methods can efficiently exploit modern parallel hardware while offering very rapid convergence properties.  As the polynomial degree is increased, the efficient solution of such PDEs becomes difficult. In this talk we introduce preconditioners for high-order discretizations. We build upon the pioneering work of Pavarino, who proved in 1993 that the additive Schwarz method with vertex patches and a low-order coarse space gives a  solver for symmetric and coercive problems that is robust to the polynomial degree. 

However, for very high polynomial degrees it is not feasible to assemble or factorize the matrices for each vertex patch, as the patch matrices contain dense blocks, which couple together all degrees of freedom within a cell. The central novelty of the preconditioners we develop is that they have the same time and space complexity as sum-factorized operator application on unstructured meshes of tensor-product cells, i.e., we can solve $A x=b$ with the same complexity as evaluating $b-A x$. Our solver relies on new finite elements for the de Rham complex that enable the blocks in the stiffness matrix corresponding to the cell interiors to become diagonal for scalar PDEs or block diagonal for vector-valued PDEs.  With these new elements, the patch problems are as sparse as a low-order finite difference discretization, while having a sparser Cholesky factorization. In the non-separable case, themethod can be applied as a preconditioner by approximating the problem with a separable surrogate.  Through the careful use of incomplete factorizations and choice of space decomposition we achieve optimal fill-in in the patch factors, ultimately allowing for optimal-complexity storage and computational cost across the setup and solution stages.

We demonstrate the approach by solving the Riesz maps of $H^1$, $H(\mathrm{curl})$, and $H(\mathrm{div})$ in three dimensions at $p = 15$.

We investigate the theoretical properties of subsampling and hashing as tools for approximate Euclidean norm-preserving embeddings for vectors with (unknown) additive Gaussian noises. Such embeddings are called Johnson-Lindenstrauss embeddings due to their celebrated lemma. Previous work shows that as sparse embeddings, if a comparable embedding dimension to the Gaussian matrices is required, the success of subsampling and hashing closely depends on the $l_\infty$ to $l_2$ ratios of the vectors to be mapped. This paper shows that the presence of noise removes such constrain in high-dimensions; in other words, sparse embeddings such as subsampling and hashing with comparable embedding dimensions to dense embeddings have similar norm-preserving dimensionality-reduction properties, regardless of the $l_\infty$ to $l_2$ ratios of the vectors to be mapped. The key idea in our result is that the noise should be treated as information to be exploited, not simply a nuisance to be removed. Numerical illustrations show better performances of sparse embeddings in the presence of noise.