Wednesdays at 4:15 PM in 380C.
A natural optimization model that formulates many online resource allocation and revenue management problems is the online linear program (LP) where the constraint matrix, along with the objective coefficients, are revealed column by column. We discuss optimal algorithms for solving this surprisingly general class of online problems under the assumption of random order of arrival and some conditions on the data and size of the problem. These algorithms have a feature of "learning while doing" by dynamically updating a threshold price vector at certain time intervals, where the dual prices learned from revealed columns in the previous period are used to determine the sequential decisions in the current period. In particular, the algorithms don't assume any distribution information on the input itself, thus it is robust to data uncertainty and variations due to its dynamic learning capability. Applications include many online multi-resource allocation and multi-product revenue management problems such as online routing and packing, online combinatorial auctions, display advertizing, etc.
Understanding the coupling of physical models at different scales is important and quite challenging. In this talk, we focus on the issue of kinetic-fluid coupling, in particular, the half-space problems for kinetic equations coming from the boundary layer. We will present some recent progress in algorithm development and analysis for the linear half-space kinetic equations, and its application in coupling of neutron transport equations with diffusion equations. (joint work with Qin Li and Weiran Sun)
We will consider systems of stochastic delay differential equations driven by colored noise. The two important time scales characterizing such system are the delay time and the correlation time of the noise. We will study perturbatively the limiting behavior of the solutions as these two time scales become small, showing the emergence of a noise-induced drift in the effective equation describing the limit. The results are confirmed by a noisy electrical circuit experiment. This is a joint work with experimental physicists Giuseppe Pesce and Giovanni Volpe and with graduate students Scott Hottovy and Austin McDaniel.
The ability of animals to self-organize into remarkable patterns of movement is seen throughout nature from herds of large mammals, to flocks of birds, schools of fish, and swarms of insects. Remarkably, patterns of collective movement can be seen even in the simplest forms of life such as bacteria. M. xanthus are common soil bacteria that are among the most "social" bacteria in nature. In this talk clustering mechanism of swarming M. xanthus will be described using combination of experimental movies and stochastic model simulations. Continuous limits of discrete stochastic dynamical systems simulating cell aggregation will be described in the form of reaction-diffusion and nonlinear diffusion equations. Surface motility such as swarming is thought to precede biofilm formation during infection. Population of bacteria P. aeruginosa, major infection in hospitals, will be shown to efficiently propagate as high density waves that move symmetrically as rings within swarms towards the extending tendrils. Multi-scale model simulations suggest a mechanism of wave propagation as well as branched tendril formation at the edge of the population that depend upon competition between the changing viscosity of the bacterial liquid suspension and the liquid film boundary expansion caused by Marangoni forces. This collective mechanism of cell- cell coordination was recently shown to moderate swarming direction of individual bacteria to avoid a toxic environment.
Abstract: This talk compares local and global conditions for polynomial optimization problems. First, we review the classical local optimality conditions: constraint qualification, strict complementarity and second order sufficiency conditions. We show that they are always satisfied, except a zero measure set of input data. Second, we review global optimality conditions that are expressed by sum-of-squares type representations. We show that if the above classical local optimality conditions hold, then the sum-of-squares type global optimality conditions must be satisfied. Third, we review Lasserre's hierarchy for solving polynomial optimization, and show that it always has finite convergence, except a zero measure set of input data.
Hierarchically low-rank ("H-") matrices are well-known to provide quasi-optimal solution techniques for the inversion of large classes of second-order elliptic equations with L-infinity coefficients, but, as of yet, no algorithms are known which allow for the inversion of N x N H-matrices in polylogarithmic time using O(N) processes (indeed, current approaches require Omega(N) time). The prospect of executing Newton's algorithm in approximate H-matrix arithmetic has been repeatedly studied as a scalable alternative, but with the unfortunate consensus is that convergence is only obtained if the initial guess is relatively close to the true inverse. This talk introduces the gambit of constructing the initial guess via a ULV factorization from an algebraically friendly low-rank scheme (so-called weakly-admissible H^2 matrices, or HSS matrices) which forfeits quasi-optimal rank growth in exchange for a highly parallel means of constructing a rough guess for the inverse.
Linear response eigenvalue problems (LREPs) arise from the study of collective motion of many particle systems, such as excited states of electronic structures. In this talk, we will present recent theoretical results on variational principles of LREPs and discuss conjugate gradient-like algorithms. Numerical results of large-scale LREPs for computing multiple low-lying excitation energies of molecules by the time-dependent density functional theory will be presented. This is a joint work with Ren-cang Li, Dario Rocca and Giulia Galli.
I discuss "simple" dynamical systems on networks and examine how network structure affects dynamics of processes running on top of networks. I'll give an introduction to the idea of social ("complex") contagions, and I'll present a model for multi-stage complex contagions--in which fanatics produce greater influence than mere followers. I'll also briefly discuss the use of ideas from topics like persistent homology to examine wavefront propagation versus the appearance of new contagion clusters, and I'll present a model (without network structure) for the adoption of applications on Facebook. The last family of models illustrates how very different time-dependent dynamics can produce quantitatively similar long-time behavior, which poses both very serious challenges and exciting opportunities for the modeling of complex systems.
Experiments and numerical simulations provide plenty of data describing entangled systems arising from dynamics or otherwise. For example, there are recent experiments studying entangled hair, and magnetic fields are often modelled as entangled lines. But what is a good measure of entanglement, and how much entanglement should we expect? We look at modeling the entanglement of purely random orbits such as Brownian motion. This is joint work with Marko Budisic and Huanyu Wen.
I will discuss a number of examples where the addition of noise leads to a qualitative change in the dynamics of the system. My main emphasis will be on a simple planner ODE possessing solutions which explode in finite time. Yet when noise is added the system is stabilized and develops a number of interesting "out of equilibrium" behaviors. This is an instructive example of "stabilization by noise". The lessons learned in this example could be informative when consider more complicated settings such as PDEs in which people hope are stabilized by noise. In this simple example, the interaction of the noise and the instability leads to a system which at once equilibrates quickly but also has heavy tails and "intermittent" behavior. I will provide a general framework to think about such problems providing both heuristic calculations and glimpses of the proofs which involve constructing OPTIMAL Lyapunov functions. If time permits I will also talk about a simple examle which deterministically possess many invariant measure, yet the zero noise limit of the stochastically forced system limit possesses only one invariant measure. The problems possesses some serious mathematical challenges including a limiting problem which does not have unique solutions. Uniqueness is only obtained when it is views as the limit of a noisy system.
For questions, contact