Woosuk Leo Jung

Preconditioning is essential in iterative methods for solving linear systems. It is also the implicit objective in updating approximations of Jacobians in optimization methods, e.g., in quasi-Newton methods. We study a nonclassic matrix condition number, the $\omega$-condition number, $\omega$ for short. $\omega$ is the ratio of: the arithmetic and geometric means of the singular values, rather than the largest and smallest for the classical $\kappa$-condition number. The simple functions in $\omega$ allow one to exploit first order optimality conditions. We use this fact to derive explicit formulae for (i) $\omega$-optimal low rank updating of generalized Jacobians arising in the context of nonsmooth Newton methods; and (ii) $\omega$-optimal preconditioners of special structure for iterative methods for linear systems. In the latter context, we analyze the benefits of $\omega$ for (a) improving the clustering of eigenvalues; (b) reducing the number of iterations; and (c) estimating the actual condition of a linear system. Moreover we show strong theoretical connections between the $\omega$-optimal preconditioners and incomplete Cholesky factorizations, and highlight the misleading effects arising from the inverse invariance of $\kappa$. Our results confirm the efficacy of using the $\omega$-condition number compared to the $\kappa$-condition number.

Understanding the role that subgradients play in various second-order variational analysis constructions can help us uncover new properties of important classes of functions in variational analysis. Focusing mainly on the behavior of the second subderivative and subgradient proto-derivative of polyhedral functions, i.e., functions with polyhedral convex epigraphs, we demonstrate that choosing the underlying subgradient, utilized in the definitions of these concepts, from the relative interior of the subdifferential of polyhedral functions ensures stronger second-order variational properties such as strict twice epi-differentiability and strict subgradient proto-differentiability. This allows us to characterize continuous differentiability of the proximal mapping and twice continuous differentiability of the Moreau envelope of polyhedral functions. We close the paper with proving the equivalence of metric regularity and strong metric regularity of a class of generalized equations at their nondegenerate solutions.

The so-called simplified Wasserstein barycenter problem, also known as the cheapest hub problem, consists in selecting one point from each of $k$ given sets, each set consisting of $n$ points, with the aim of minimizing the sum of distances to the barycenter of the $k$ chosen points. This problem is known to be NP-hard. We compute the Wasserstein barycenter by exploiting the Euclidean distance matrix structure to obtain a facially reduced doubly nonnegative, $\DNNp$, relaxation. The facial reduction provides a natural splitting for applying the symmetric alternating directions method of multipliers ($\sADMM$) to the $\DNN$ relaxation. The $\sADMM$ method exploits structure in the subproblems to find strong upper and lower bounds. In addition, we extend the problem to allow varying $n_j$ points for the $j$-th set.
The purpose of this paper is twofold. First we want to illustrate the strength of this $\DNN$ relaxation with a splitting approach mentioned above. Our numerical tests then illustrate the surprising success on random problems, as we generally, efficiently, find the provable exact solution of this NP-hard problem. Comparisons with current commercial software illustrate this surprising efficiency. However, we demonstrate and prove that there is a duality gap for problems with enough multiple optimal solutions, and that this arises from problems with highly symmetrized structure.

We consider the exact error correction of a noisy Euclidean distance matrix, $\EDMp$, where the elements are the squared distances between $n$ points in $\R^d$. For our problem we are given two facts: (i) the embedding dimension, $d=\mathrm{edim}(D)$, (ii) exactly one distance in the data is corrupted by nonzero noise. But we do not know the magnitude nor position of the noise. Thus there is a combinatorial element to the problem. We present three solution techniques. These use three divide and conquer strategies in combination with three versions of facial reduction that use: exposing vectors, facial vectors, and Gale transforms. This sheds light on the connections between the various forms of facial reduction related to Gale transforms. Our highly successful empirics confirm the success of these approaches as we can solve huge problems of the order of $100,000$ nodes in approximately one minute to machine precision.
Our algorithm depends on identifying whether a principal submatrix of the $\EDM$ contains the corrupted element. We provide a theorem for doing this that is related to the existing results for identifying yielding elements, i.e., we provide a characterization for guaranteeing the perturbed $\EDM$ remains an $\EDM$ with embedding dimension $d$. The characterization is particularly simple in the $d=2$ case.
In addition, we characterize when the intuitive approach of the nearest $\EDM$ problem, $\NEDMp$, solves our problem. In fact, we show that this happens if, and only if, the original distance element is $0$, degenerate, and the perturbation is negative.

Facial reduction, $\FRp$, is a regularization technique for convex programs where the strict feasibility constraint qualification, CQ, fails. Though this CQ holds generically, failure is pervasive in applications such as semidefinite relaxations of hard discrete optimization problems. In this paper we relate $\FR$ to the analysis of the convergence behaviour of a semi-smooth Newton root finding method for the projection onto a spectrahedron, i.e., onto the intersection of a linear manifold and the semidefinite cone. In the process, we derive and use an elegant formula for the projection onto a face of the semidefinite cone. We show further that the ill-conditioning of the Jacobian of the Newton method near optimality characterizes the degeneracy of the nearest point in the spectrahedron. We apply the results, both theoretically and empirically, to the problem of finding nearest points to the sets of: (i) correlation matrices or the elliptope; and (ii) semidefinite relaxations of permutation matrices or the vontope, i.e., the feasible sets for the semidefinite relaxations of the max-cut and quadratic assignment problems, respectively.