A geometer’s view of the simplex algorithm for linear optimization

Speaker: 

Jesus de Loera

Institution: 

UC Davis

Time: 

Thursday, May 3, 2018 - 3:00pm to 4:00pm

Host: 

Location: 

RH 306

Linear programs (LPs) are, without any doubt, at the core of both the theory and the practice of mondern applied and computational Optimization (e.g., in discrete optimization LPs are used in practical computations using branch-and-bound, and in approximation algorithms, e.g., in rounding schemes). At the same time  Dantzig’s Simplex method is one of the most famous algorithms to solve LPs and SIAM elected it as one of the top 10 most influential algorithms of the 20th Century.

But despite its key importance, many simple easy-to-state mathematical properties of the Simplex method and its geometry remain unknown. The geometry of the simplex method is very much the convex-combinatorial geometry of polyhedra (e.g., cubes, simplices, etc). Perhaps the most famous geometric-combinatorial challenge is to determine a worst-case upper bound for the graph diameter of polyhedra.  Although a lot of progress has been made, today even for the most elementary textbook linear programs we remain ignorant as to what the exact diameter upper bounds are. In this talk, I will discuss this  geometric problem and present the key ideas for proving that the diameter of graphs of all network-flow polytopes satisfy the Hirsch linear bound. This is joint work with S. Borgwardt (Univ of Colorado) and E. Finhold (Fraunhofer Institut).

Joint UCI-UCR-UCSD Southern California Differential Geometry Seminar

Institution: 

SCDGS

Time: 

Tuesday, May 8, 2018 - 3:00pm to 5:00pm

Location: 

UC Riverside

Lecture 1

Speaker: Otis Chodosh

Time/place: Surge 284 3:40~4:30

Title:Properties of Allen--Cahn min-max constructions on 3-manifolds

Abstract:

I will describe recent joint work with C. Mantoulidis in which we study the properties of bounded Morse index solutions to the Allen--Cahn equation on 3-manifolds. One consequence of our work is that a generic Riemannian 3-manifold contains an embedded minimal surface with Morse index p, for each positive integer p.

 

Lecture 2

Speaker:  Ved Datar

Time/place: Surge 284 4:40~5:30

Title: Hermitian-Yang-Mills connections on collapsing K3 surfaces

Abstract:

Let $X$ be an elliptically fibered K3 surface with a fixed $SU(n)$ bundle $\mathcal{E}$. I will talk about degenerations of connections on $\mathcal{E}$ that are Hermitian-Yang-Mills with respect to a collapsing family of Ricci flat metrics. This can be thought of as a vector bundle analog of the degeneration of Ricci flat metrics studied by Gross-Wilson and Gross-Tosatti-Zhang. I will show that under some mild conditions on the bundle, the restriction of the connections to a generic elliptic fiber converges to a flat connection. I will also talk about some ongoing work on strengthening this result. This is based on joint work with Adam Jacob and Yuguang Zhang.

 

The Technology of Voting: Risks & Opportunities

Speaker: 

Josh Benaloh, Alex Halderman, Hovav Shacham

Institution: 

Microsoft Research, University of Michigan, UCSD

Time: 

Tuesday, March 13, 2018 - 3:30pm to 4:40pm

Host: 

Location: 

Crystal Cove Auditorium, UCI Student Center

Event on Elections and Voting, with Panels on the Technology, Law, & Policy of Election Hacking, 1:30 - 7:30 pm

The Technology of Voting: Risks & Opportunities
Josh Benaloh (Microsoft Research)
Alex Halderman (University of Michigan)
Hovav Shacham (UC San Diego)
Panel moderated by Alice Silverberg (UC Irvine), 3:30 pm - 4:40 pm

Keynote Speaker: James Carville 6:30 - 7:30 pm

More information: https://cpri.uci.edu/can-adversaries-hack-our-elections-can-we-stop-them...

FREE to UCI students, faculty, and staff.  Register at: https://scout.eee.uci.edu/s/CPRI-March13

The complexity of countable torsion-free Abelian groups

Speaker: 

Douglas Ulrich

Institution: 

University of Maryland

Time: 

Monday, May 7, 2018 - 4:00pm

Host: 

Location: 

RH 440R

How complicated are countable torsion-free abelian groups? In particular, are they as complicated as countable graphs? In recent joint work with Shelah, we show it is consistent with ZFC that countable torsion-free abelian groups are $a \Delta^1_2$ complete; in other words, countable graphs can be encoded into them via an absolutely $\Delta^1_2$-map. I discuss this, and the related result: assuming large cardinals, it is independent of ZFC if there is an absolutely $\Delta^1_2$ reduction from Graphs to Colored Trees, which takes non-isomorphic graphs to non-biembeddable colored trees.

Professor Tom Trogdon awarded NSF Career Award

Congratulations to Professor Tom Trogdon! He has been awarded an NSF CAREER Award. This is one of the most prestigious awards available to a junior faculty member. Recipients are "junior faculty who exemplify the role of teacher-scholars through outstanding research, excellent education and the integration of education and research within the context of the mission of their organizations. Such activities should build a firm foundation for a lifetime of leadership in integrating education and research."

Laplacian Smoothing Gradient Descent and Micro-encapsulation of Droplets

Speaker: 

Bao Wang

Institution: 

UCLA

Time: 

Monday, May 14, 2018 - 4:00pm to 5:00pm

Host: 

Location: 

RH 306

First, I will present the Laplacian smoothing gradient descent proposed recently by Prof. Stan Osher. We show that when applied to a variety of machine learning models including softmax regression, convolutional neural nets, generative adversarial nets, and deep reinforcement learning, this very simple surrogate of gradient descent can dramatically reduce the variance and improve the accuracy of the generalization. The new algorithm, (which depends on one nonnegative parameter) when applied to non-convex minimization, tends to avoid sharp local minima. Instead it seeks somewhat flatter local(and often global) minima. The method only involves preconditioning the gradient by the inverse of a tri-diagonal matrix that is positive definite. The motivation comes from the theory of Hamilton-Jacobi partial differential equations. This theory demonstrates that the new algorithm is almost the same as doing gradient descent on a new function which (a) has the same global minima as the original function and (b) is "more convex". Second, I will talk about modeling, simulation, and experiments of the micro-encapsulation of droplets. This is a work joint with Professors Andrea Bertozzi, Dino Di Carlo, and Stan Osher’s groups.

Algorithmic Development for Computing B-stationary Points of a Class of Nonsmooth DC Programs

Speaker: 

Zhaosong Lu

Institution: 

Simon Fraser University

Time: 

Friday, February 16, 2018 - 11:00am to 12:00pm

Host: 

Location: 

340P

In the first part of this talk, we study a convex-constrained nonsmooth DC program
in which the concave summand of the objective is an infimum of possibly infinitely many smooth
concave functions. We propose some algorithms by using nonmonotone linear search and extrapolation
techniques for possible acceleration for this problem, and analyze their global convergence, sequence
convergence and also iteration complexity. We also propose randomized counterparts for them
and discuss their convergence.

In the second part we consider a class of DC constrained nonsmooth DC programs. We propose penalty and
augmented Lagrangian methods for solving them and show that they converge to a B-stationary
point under much weaker assumptions than those imposed in the literature.

This is joint work with Zhe Sun and Zirui Zhou.

Pages

Subscribe to UCI Mathematics RSS