Seminar Abstracts (Spring 2012)
Ed Scheinerman (Johns Hopkins University)
Abstract:
Amitabh Basu (University of California, Davis)
Corner Polyhedra and Maximal Lattice-free Convex Bodies: A Fresh Geometic Approach to Cutting Plane Theory
Abstract: I will present my work on techniques which have the potential to create the next methodological breakthrough in solving general discrete optimization problems. The talk will focus on my work in cutting plane theory for Mixed-Integer Linear Programming. I will present a framework which unifies previous methods in cutting planes and provides new, and potentially much stronger, cutting plane ideas. This line of work combines the insights behind Gomory's Corner Polyhedron and Balas' Intersection Cuts, using tools from convex analysis, polyhedral geometry and the geometry of numbers. This line of work has initiated intense research activity in the integer programming community. The ultimate hope is to achieve the next leap in improving Integer Programming algorithms.
Anke van Zuylen (Max Plank Institute for Informatics, Germany)
The Subtour LP for the Traveling Salesman Problem
Abstract: The traveling salesman problem (TSP) is perhaps the most famous problem in combinatorial optimization: given a set of cities and the distances fortraveling between each pair of cities, the goal of the problem is to find the shortest tour that visits each city exactly once and returns to its starting point. We consider TSP instances in which the distances are symmetric and obey the triangle inequality. Finding the optimal tour is known to be NP-hard; nevertheless, the past decades have seen great progress in solving real-world instances of the TSP. A starting point for solving real-world TSP instances is a linear programming relaxation called the subtour LP. The subtour LP is known to give excellent lower bounds on TSP instances in practice, coming within a percent or two of the length of theoptimal tour. However, its theoretical worst-case is not well understood. Examples are known that show that the worst-case ratio is at least 4/3, and the famous Christofides' algorithm always finds a tour of length at most 3/2 times the value of the subtour LP. A long-standing conjecture states that the worst-case ratio, taken over all instances of the problem, of the value of the optimal tour to the value of the subtour LP is at most 4/3.
In the past two years, there has been a lot of exciting progress in this area. In this talk, we review some of the known results, and present somenew results that refine our understanding of the subtour LP. In particular, we resolve a conjecture of Boyd and Carr about the ratio of an optimal 2-matching to the subtour LP bound in the worst case. We also begin a study of the subtour LP bound for the case in which all distances between cities are either 1 or 2. For these instances we show that the worst-caseratio of the value of the optimal tour to the value of the subtour LP is always strictly better than 4/3.
This is based on joint work with Jiawei Qian, Frans Schalekamp and David P. Williamson.
Gwen Spencer (Cornell University)
Optimally Fragmenting Graphs Against Stochastically-located Threats: Containing Wildfire, Invasive Species, and Epidemics
Abstract: Aggressive wildfire-suppression policies have proved highly unsustainable due to excessive build up of flammable materials on the landscape. Increasing frequency of catastrophically-damaging wildfire events has stimulated interest among foresters in the effective use of preventative fuel reductions like dead-brush removal and small-scale controlled burns. How can data produced by forest scientists be used to determine the right level of investment in these preventative measures? How can we optimally place these treatments on the landscape to best complement real-time firefighting capabilities? Exploring these questions motivates a natural new family of budgeted stochastic combinatorial-optimization problems that fragment (or cut) a landscape graph to isolate a stochastically-occurring ignition point. These models represent novel extensions of well-studied ideas in the theoretical computer science literature and capture crucial features of other contemporary environmental applications (e.g., containing the spread of invasive species). I will explain a hierarchy of efficient and provably-good algorithmic results for these models, discuss some successful extensions related to the social-networks literature, and mention some future research directions.
Rico Zenklusen (MIT)
Tackling Hard Combinatorial Optimization Problems via Negatively Correlated Rounding
Abstract: A promising approach to deal with hard combinatorial optimization problems is to first compute an optimal solution of an efficiently solvable relaxation, which is then rounded to a feasible solution of the initial problem. However, finding suitable rounding procedures is a major challenge. One of the most prominent randomized rounding approaches, known as negatively correlated rounding, has led to the currently best known results for a variety of fundamental combinatorial optimization problems by exploiting Chernoff-type concentration bounds.
I will present some of my work on negatively correlated rounding procedures and related topics. These results include a polyhedral characterization of all problem settings that admit negatively correlated rounding algorithms, and more importantly, an efficient rounding algorithm working on all such instances. This considerably widens the applicability of negatively correlated rounding and also improves on the efficiency of previous approaches for known settings.
02/28/2012
Sergey Nadtochiy (Oxford-Man Institute, University of Oxford)
Quantitative Methods for Derivatives Markets Consistent with Historical Observations
03/1/2012
James Primbs (Stanford University)
Portfolio Optimization under Transaction Costs via Linear-Quadratic and Receding Horizon Methods
Abstract: In this talk we explore the use of Linear Quadratic (LQ) control and receding horizon methods in dynamic portfolio optimization. In particular, we consider the problem of a trader who wishes to maximize a power utility function of final wealth but faces a proportional transaction cost when trading. While the structure of the optimal solution is known, efficient algorithms for computing it are not available. We approach this problem by first recognizing that when transaction costs are not present, the portfolio optimization problem and a standard LQ control problem share the same solution. This allows us to propose an altered LQ problem that accounts for the transaction costs. While this new problem is still difficult to solve, the LQ structure lends itself well to efficient sub-optimal receding horizon approaches (also known as model predictive control) that have been successfully applied for years in other domains. Finally, we test the potential of these LQ based receding horizon schemes on numerical examples.
03/6/2012
Stephan Sturm (Princeton University)
From Smile Wings to Market Risk Measures
Abstract: The left tail of the implied volatility skew, coming from quotes on out-of-the-money put options, can be thought to reflect the market's assessment of the risk of a huge drop in stock prices. We analyze how this market information can be integrated into the theoretical framework of convex monetary measures of risk. In particular, we make use of indifference pricing by dynamic convex risk measures, which are given as solutions of backward stochastic differential equations (BSDEs), to establish a link between these two approaches to risk measurement. We derive a characterization of the implied volatility in terms of the solution of a nonlinear PDE and provide a small time-to-maturity expansion. This procedure allows to choose convex risk measures in a conveniently parametrized class, distorted entropic dynamic risk measures, such that the asymptotic volatility skew under indifference pricing can be matched with the market skew. This is joint work with Ronnie Sircar.
James R. Wilson (NC STATE) is a professor of the Edward P. Fitts Department of Industrial and Systems Engineering at North Carolina State University. He is a Senior Member of the Association for Computing Machinery and a member of the American Statistical Association. He is a Fellow of the Institute of Industrial Engineers and of the Institute for Operations Research and the Management Sciences. His e-mail address is jwilson@ncsu.edu and his Web page is http://www.ise.ncsu.edu/jwilson/
SKART: A SKEWNESS- AND AUTOREGRESSION-ADJUSTED BATCH-MEANS PROCEDURE FOR SIMULATION ANALYSIS
Abstract: Skart is an automated sequential batch-means procedure for constructing a skewness- and autoregression-adjusted confidence interval (CI) for the steady-state mean of a simulation output process either in discrete time (i.e., using observation-based statistics), or in continuous time (i.e., using time-averaged statistics). Skart delivers a CI designed to satisfy user-specified requirements concerning both the CI’s coverage probability and its absolute or relative precision. Skart exploits separate adjustments to the classical batch-means CI to account for the effects on the distribution of the underlying Student’s t-statistic arising from skewness and autocorrelation of the batch means. Skart also delivers a point estimator for the steady-state mean that is approximately free of initialization bias. In extensive experimentation, Skart compared favorably with its competitors. Some results are also presented for N-Skart, a nonsequential version of the procedure that has been adapted to handle time series of fixed length.
Casey Richardson (Johns Hopkins University)
Measure Matching Using Metamorphosis
Abstract: Metamorphosis is a mathematical framework for pattern matching in which one defines a distance on a space of images or shapes. In the case of images, this distance is found by computing the energetically optimal way in which one image can be morphed into the other, combining both smooth deformations and smooth changes in image intensity. In this talk, I will discuss an extension of this approach to the case of measure matching, which was proposed by Holm, Trouv\'{e}, and Younes (2009).
The particular case of matching combinations of Dirac measures has applications in shape analysis using landmark points. Then I will describe on-going work (joint with Laurent Younes) on the analysis and computation of measure metamorphosis. We show that, when matching two measures, minimizers can become more singular than the measures themselves, which complicates the computation of solutions. I will discuss the nature of these singularities and present some early computational results for simple examples of Dirac measure matching.
Sridevi Sarma (Johns Hopkins University)
Quickest Detection of Drug-Resistant Seizures Using Network-Based Analysis
Abstract: Epilepsy affects over 50 million people worldwide, and 30% remain drug-resistant. This has increased interest in both chronic and responsive neurostimulation, which is most effective when administered at or near the foci and immediately prior to or at the seizure (ictal) onset. Precise automatic online seizure detection (AOSD) from intracranial EEG (iEEG) recordings are therefore critical for closed-loop intervention, but remains a challenging problem. Several AOSD algorithms has been proposed thus far and though they are highly sensitive (large number of true positives), these algorithms generally have low specificity (large number of false positives), which limits their clinical use. The lack of specificity presumably occurs because (i) they compute statistics from a few channels at a time which may not capture network dynamics of the brain, (ii) and/or the detection thresholds are not explicitly optimized to maximize AOSD performance.
In this talk, we propose a novel computational framework for AOSD that involves (i) constructing multivariate statistics from all electrodes to distinguish between non-ictal and ictal states; (ii) modeling the evolution of these statistics in each state and the state-transition probabilities; and, (iii) developing an optimal model-based strategy to detect transitions to ictal states from sequential neural measurements. This strategy is formulated as the Bayesian “Quickest Detection” (QD) of the seizure onset, and is solved via control optimization tools, and explicitly minimizes both the distance between detected and unequivocal onset times and the probability of false positives. We demonstrate our approach with intracranial EEG recordings from patients with drug-resistant epilepsy and our preliminary results indicate that QD achieves high sensitivity with high specificity (low number of false positives).
Frank E. Curtis (Lehigh University) is a P.C. Rossin Assistant Professor in the Industrial and Systems Engineering Department at Lehigh University. He received his Ph.D. from Northwestern University in 2007 and then spent two years as a Postdoctoral Researcher in the Courant Institute for Mathematical Sciences at New York University before joining Lehigh in 2009. His research, currently funded by the NSF, has been published in journals such as SIAM Journal on Optimization, Mathematical Programming, IMA Journal of Numerical Analysis, and SIAM Journal on Scientific Computing. Frank is the current Vice Chair for Nonlinear Programming for the INFORMS Optimization Society.
Nonconvex, Nonsmooth Optimization by Gradient Sampling
Abstract: Optimization algorithms are often distinguished by lines separating those that solve smooth problems and those that solve nonsmooth problems. They are also often separated into those for convex, as opposed to nonconvex, problems. This talk, however, describes an algorithmic framework that straddles the lines between smooth and nonsmooth, convex and nonconvex. The framework generalizes gradient-based methods for unconstrained optimization and sequential quadratic methods for constrained optimization so that nonconvex, nonsmooth functions can be minimized, subject to any number of nonconvex, nonsmooth constraints.
Our algorithmic framework has features in common with novel methods
for a variety of problem classes. For example, the framework is
stochastic in nature, and in certain ways resembles
stochastic-gradient approaches (and its extensions) that are the
subject of much contemporary research. It also has commonalities with
derivative-free methods due to the manner in which (sub)derivatives
are approximated by partial information. The real strength of our
framework, however, is not in these similarities, but is in the way
that our framework opens the door for the best methods for smooth
optimization to be extended readily for solving nonsmooth problems.
Thus, it represents a potential cornerstone for a great deal of
further developments and extensions.
Alan F. Karr (National Institute of Statistical Sciences)
Combining Cohorts in Longitudinal Surveys, with Application to the Survey of Doctorate Recipients
Abstract:
We present a methodology, utilizing generalized estimating equations (GEEs), for modeling temporal phenomena in longitudinal surveys with multiple cohorts. The method is based on joint randomization, taking the superpopulation model into account, but empirical studies show that it also performs well for estimation of finite population quantities. The method requires only (valid) cross-sectional weights for each wave, and therefore makes full use of the data. Variance estimation is also discussed.
The method is applied to the Survey of Doctorate Recipients (SDR), a long-term data collection conducted by the National Center for Science and Engineering Statistics (NCSES) of the NSF. In the SDR, there occur new cohorts representing additional target populations, attrition, and deliberate reduction of the existing sample in order to accommodate the new cohorts. In addition, some subjects respond irregularly over time. We describe a model for estimation of individual salary histories as a function of temporal, demographic and institutional parameters. Detailed attention is paid to interpretation of the results as characteristics of the US scientific workforce.
This is joint work with Ivan Carillo-Garcia, postdoctoral fellow at NISS.
04/12/2012 & 04/13/2012
Gérard Ben Arous (New York University)
A specialist of probability theory and its applications, Gérard Ben Arous arrived to NYU's Courant Institute as a Professor of Mathematics in 2002. He was appointed Director of the Courant Institute and Vice-Provost for Science and Engineering Development in September 2011. A native of France, Professor Ben Arous studied Mathematics at École Normale Supérieure and earned his PhD from the University of Paris VII (1981). He has been a Professor at the University of Paris-Sud (Orsay), at École Normale Supérieure, and more recently at the Swiss Federal Institute of Technology in Lausanne, where he held the Chair of Stochastic Modeling. He headed the department of Mathematics at Orsay and the departments of Mathematics and Computer Science at École Normale Supérieure. He also founded a Mathematics research institute in Lausanne, the Bernoulli Center. He is the managing editor (with Amir Dembo, Stanford) of one of the main journals in his field, Probability Theory and Related Fields.
Professor Ben Arous works on probability theory (stochastic analysis, large deviations, random media and random matrices) and its connections with other domains of mathematics (partial differential equations, dynamical systems), physics (statistical mechanics of disordered media), or industrial applications. He is mainly interested in the time evolution of complex systems, and the universal aspects of their long time behavior and of their slow relaxation to equilibrium, in particular how complexity and disorder imply aging. He is a Fellow of the Institute of Mathematical Statistics (as of August 2011) and an elected member of the International Statistical Institute. He was a plenary speaker at the European Congress of Mathematics, an invited speaker at the International Congress of Mathematics, received a senior Lady Davis Fellowship (Israel), the Rollo Davison Prize (Imperial College, London) and the Montyon Prize (French Academy of Sciences).
Counting critical points of random functions of many variables
RMT^2: Random Morse Theory meets Random Matrix Theory
Abstract:
Thursday, April 12
Morse theory gives bounds on the number of critical points for all smooth (Morse) functions on a manifold. The questions I will be surveying here are the following:
Can one count the number of critical points for random smooth functions of many variables?
How complex is a typical random function?
How complex is the topology of its level sets?
We will study here the simplest case of smooth Gaussian random functions defined on the sphere in high dimensions. We will see that such a randomly chosen smooth function is very complex, i.e. that its number of critical points of given index is exponentially large. We also study the topology of the level sets of these functions, and give sharp estimates of their Euler characteristic.
This study, which is a joint work with Tuca Auffinger (Chicago) and partly with Jiri Cerny (Vienna), relies rather surprisingly on Random Matrix Theory, through the use of the classical Kac-Rice formula.
The main motivation for this study comes from one of the hard questions of statistical physics of disordered media.
Friday April 13
In the second talk I will go deeper in this direction and indicate how these random smooth functions on the sphere correspond to Hamiltonians of well-known models of statistical physics, i.e general spherical spin glasses. I will detail the interesting picture we get for the complexity of these random Hamiltonians, for the bottom of the energy landscape, and in particular a strong correlation between the index and and the critical value. I will relate our findings to the results in the physics literature, for instance to the so-called TAP (Thouless-Anderson-Palmer) complexity at low temperature. I will show how the positive complexity threshold is (or is not) related to the ground state of those models, and relate this to the Parisi formula. I will also propose a new invariant for the possible transition between the so-called -step replica symmetry breaking and a Full Replica symmetry breaking scheme. Many questions remain open, I will detail a few.
Daniel Ullman (George Washington University)
A Whirlwind Tour of Combinatorial Game Theory
Abstract:
I will introduce the beautiful theory of combinatorial games due to John Horton Conway. These are games like Nim, Tic-Tac-Toe, and Chess in which two players move alternately until they can't and there is no randomness or hidden information. The object of an analysis of such games is to determine which player will win or to classify the associated decision problem according to its computational complexity. Of special interest are games one can play on graphs, and I will focus primarily on so-called impartial games in which the rules afford the two players the same legal moves. We'll describe one such game, which we call Take-one-or-two (TOOT), and present some recent results.
Rafael Irizarry (Johns Hopkins University)
Bump Hunting in the Cancer Epigenome
Abstract: Epigenetics is the study of nonsequence-based changes, such as DNA methylation, heritable during cell division. I will start the talk with a short tutorial on epigenetics and DNA methylation. I will describe new challenges for statisticians related to the existing field of bump hunting. I will describe the important role modern statistical techniques play in finding regions of the genome that are consistently different between disease and normal groups using both microarray and next-generation sequencing data. I will also describe the batch effect and how we deal with it.
Finally, I will present some interesting Biological results related to development and cancer.
Sergio Focardi (EDHEC Business School)
Comparing Dynamic Factor Models of Prices and Returns
Abstract: Slides for talk
Jim Fill (Johns Hopkins University) - Slides
Comparison Inequalities and Fastest-Mixing Markov Chains
