Events

Title:Generalizing the problem of packing disjoint cycles

Speaker:	Paul Wollan
Affiliation:	University of Rome "La Sapienza"
Room:	MC 5479

Abstract: A classic result of Erdos and Posa states that there exists a function f such that for all k,

Tuesday, November 27, 2018 5:30 pm - 5:30 pm EST (GMT -05:00)

CryptoWorks21 Distinguished Lecture - Marc Morin

The "blood, sweat, tears, toil and triumphs" of commercializing technology

Marc Morin is the co-founder and CEO of Auvik Networks, creators of cloud-based software that makes it dramatically easier for IT managed service providers to monitor and manage their clients' IT networks. A serial entrepreneur, Marc has previously co-founded several successful companies, including PixStream (acquired by Cisco for USD$369 million) and Sandvine (Sold to Francisco Partners for CAD$582 million), and is a seed investor in a number of local tech companies.

Title: In Memoriam: Tom Coleman’s Contributions to Applied Mathematics and Optimization

Speakers:	Yuying Li, Stephen Wright, Alex Pothen, Bruce Hendrickson, Peter Forsyth, and Somayeh Moazeni
Affiliation:	SIAM Annual Meeting (AN21)
Registration:	https://www.siam.org/conferences/cm/conference/an21

Description:

Thomas F. Coleman—a leader in optimization and scientific computing, professor at the University of Waterloo, and a SIAM Fellow—passed away on April 20, 2021. Tom served as the Director of the Theory Center at Cornell and then as Dean of the Faculty of Mathematics at the University of Waterloo. His research spanned continuous optimization, combinatorial scientific computing, automatic differentiation, financial optimization, mathematical software, etc. In this session, his wife and collaborator, Yuying Li, and five of his students and colleagues will describe the pioneering contributions that Tom made to these fields in his research.

Friday, October 28, 2022 9:00 am - Saturday, October 29, 2022 5:00 pm EDT (GMT -04:00)

Workshop on Large Scale Optimization and Applications

Optimization is an important area of applied mathematics that bridges mathematical theory with applications in diverse fields. This Twenty Fourth Annual Midwest Optimization Meeting provides opportunities for researchers in this region with different backgrounds to come together to share their research and teaching experiences, forge collaborations with colleagues from different institutions, and to expose students to applications of mathematical theory. This workshop will focus on bringing together several of the diverse communities working on large scale optimization models that arise from variational problems.

Registration information, schedule, and abstracts click here

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.

Speaker:	ZiWen Wang
Supervisor:	Levent Tuncel
Location:	MC 5479

Abstract:

Given an LP with tall and skinny constraint matrix, we will exploit this property and study an algorithm invented by Clarkson [8]. Although this algorithm has
been around for over 30 years, there were no software or implementation that could be found online, nor there be any benchmarks for these special tall and skinny LP s. We will describe some variants and changes to the algorithm aiming for practical performancesto close this gap.

We also study a first order algorithm aimed for large scale LP s proposed by a group of researchers from Google [2], [3] called PDLP. And compare it with Clarkson’s algorithm.

Speaker:	Amaan Khan
Supervisor:	Levent Tuncel
Location:	MC 5479

Abstract:

Second-order Interior Point Methods (IPM) have been studied extensively over the past 80 years, proving effective for conic optimization. They can produce high-precision approximate solutions in few iterations. Each iteration is computationally expensive: The core of each iteration is a large matrix inversion that scales poorly with the number of variables.

In large-scale applications, we cannot bear the per-iteration cost (perhaps due to lack of memory), so we instead turn to first-order methods. We study a first-order IPM that uses a low-rank update scheme to replace the matrix inversion with significantly lower per-iteration cost, and compare this to other first-order methods for solving LP at scale.

Filter by:

Grad Social

Graphs and Matroids Seminar

CryptoWorks21 Distinguished Lecture - Marc Morin

The "blood, sweat, tears, toil and triumphs" of commercializing technology

Special SIAM Session - In Memoriam: Tom Coleman’s Contributions to Applied Mathematics and Optimization

Workshop on Large Scale Optimization and Applications

PhD Defense - Leo Jung - Preprocessing for Hard Optimization Problems Across Structurally Diverse Models

Master's Thesis Presentation - ZiWen Wang - Solving Linear Programs with very Tall Constraint Matrices

Master's Thesis Presentation - Amaan Khan - A Study of First-Order Primal-Dual Algorithms for Linear Optimization

Contact Info