| Speaker: |
Leo Jung
|
| Location: |
MC 5029 |
Abstract:
Difficulties in solving large-scale optimization problems often arise from structural pathologies such as ill-conditioning, Hadamard ill-posedness, and degeneracy, particularly due to the failure of constraint qualifications. While standard algorithms often struggle to address these issues, preprocessing based on structural analysis offers an effective strategy for overcoming such challenges. This thesis investigates several preprocessing methods targeting various sources of these difficulties.
In Part I, we study a nonclassical, average condition number of linear systems, the $\omega$-condition number. Our results demonstrate several advantages of the $\omega$-condition number over the classical $\kappa$-condition number. First, $\omega$ provides a more accurate measure of the conditioning of linear systems by more faithfully capturing the effects of perturbations observed in practice. Second, $\omega$ exhibits superior numerical stability compared to $\kappa$. Third, when used in preconditioner design, $\omega$ more effectively promotes eigenvalue clustering, which is crucial for the efficiency of iterative solvers. Finally, the analytical simplicity of $\omega$ enables the derivation of explicit optimality conditions, allowing for closed-form expressions of optimal preconditioners under various frameworks, including low rank updates of the generalized Jacobian for semismooth Newton methods and diagonal or block-diagonal scaling. For diagonal preconditioning, we further include a comparison between two distinct notions of conditioning.
In Part II, we first answer in the affirmative a long-standing open question of whether the smooth stress function admits local nonglobal minimizers. This quartic nonconvex objective function arises in the exact recovery of a Euclidean distance matrix (EDM) of a given embedding dimension. By eliminating the Hadamard ill-posedness caused by translation and rotation invariance, we stabilize Newton's method and avoid singular Hessians. \\
We then consider the single-element error correction problem as a case study. We first show that the standard nearest EDM formulation based on minimizing the smooth stress function fails to recover the correct EDM in this setting. We then introduce divide-and-conquer strategies based on facial reduction. Our approach efficiently recovers the correct EDM with high accuracy, and we further provide criteria characterizing the existence of multiple solutions.
In Part III, we relate FR to the analysis of the convergence behaviour of a semismooth Newton method for projection onto a spectrahedron, i.e., the intersection of a linear manifold and the semidefinite cone. In this process, we derive an explicit formula for the projection onto a face of the semidefinite cone obtained via regularization and analyze pathologies that arise in the absence of strict feasibility. We further show that ill-conditioning of the Jacobian near optimality characterizes the degeneracy of the projection point. \\
As an application, we consider a simplified Wasserstein barycenter problem, a well-known NP-hard problem. We compute the Wasserstein barycenter by exploiting the structure of the linear constraints to obtain a facially reduced doubly nonnegative (DNN) relaxation. This reduction provides a natural splitting for applying the symmetric alternating direction method of multipliers (sADMM). The resulting algorithm exploits structure in the subproblems to compute strong upper and lower bounds. In most of the instances, we achieve the small gap between these bounds, which means that the original problem is solved.