Speaker: Don Aronson, Director of Postdoctoral Program in the IMA

Title: Transmission in Inhomogeneous Excitable Media

Abstract: In the first part of the talk, I will review some aspects of the transmission of signals in a homogeneous excitable medium such as a nerve axon. There is a hierarchy of mathematical models ranging from the ultra precise (and Nobel Prize worthy) Hodgkin-Huxley system to the McKean-FitzHugh-Nagumo caricature. I will be mostly concerned with the latter. The second part of the talk will be a highly speculative discussion of what happens to transmission when one introduces inhomogeneities in the form of passive gaps. The object here is to pose some potentially interesting problems.

Speaker: Beth Allen, Professor of Economics, University of Minnesota

Title: Some Theoretical Approaches to Product Development

Abstract: This talk will survey some recent research focusing on the early stages of the product life cycle: Design (choice of product or product line) and manufacturing (in contrast to the later stages in the supply chain of, for instance, scheduling, distribution, inventory strategy, post-purchase service/maintenance/repair, and end-of-life reuse/recycling/disposal). First, the mathematical structure of the design space (in particular, for homogeneous geometric objects or shapes, so that the set of potential product designs consists of equivalence classes of nonempty closed subsets of a Euclidean space), will be examined. Implications for constrained optimization will be analyzed. Relations to quality control and manufacturing will be considered.

Speaker: Luis Goddyn, Mathematics, Simon Fraser University

Title: The Worst-Case Euclidean Traveling Salesman Problem

Abstract: How should a finite set X of points be arranged within a finite region R in Euclidean d-space, so as to maximize the length L(X) of a TSP tour through X?

It turns out that, if the size n of X is large, then the shape of R becomes irrelevant, and if R has unit volume, then the assymptotic growth is

L(X)   _d n^{(d-1) /d}

(_d depends only on the dimension d).

We discuss methods and issues involved in estimating the value of the fundamental coefficient _d. This talk involves a mix of geometry, sphere packing, quantizers, heuristics and algorithm analysis.

Speaker: Douglas N. Arnold, IMA Director

Title: Talking Math to People Who Don't Know Any

Abstract: Mathematicians are often criticized--by themselves and others--for being incapable of describing their work to non-mathematicians. In this seminar I will discuss ways to communicate mathematics to the public using as a case study a talk I gave recently on optimization for the IT Quarterly, a "forum for friends of the Institute of Technology."

Speaker: Tamon Stephen, IMA Postdoctoral Associate

Title: The Lift-and-Project Approach to Integer Programs

Abstract: In this survey talk, we discuss the ``lift and project'' approach for solving 0-1 integer programs. Our main example is the method of semi-definite matrix relaxations proposed by Lovasz and Schrijver.

Speaker: C. Roos, Delft University of Technology, Netherlands and IMA visitor, March 2003

Title: What is special with the logarithmic barrier function in optimization?    Slides:   pdf

Abstract: After its introduction by Frisch in 1955, the logarithmic barrier function (LBF) has played a major role in the field optimization. The revolutionary developments of the past two decades in this field, which gave rise to the subfield of interior-points (IP) methods, has re-emphasized its importance. The search directions in all state-of-the-art IP-solvers for linear, and also for second-order cone and semidefinite optimization problems are explicitly or implicitly based on an LBF, and the analysis of these methods strongly depends on properties of such functions. Other barrier functions have been proposed, but both from a theoretical and computational viewpoint LBF's always were winning, at least surviving. It has often been asked what makes LBF so special. In this talk we deal with this question. We focus on primal-dual methods for linear optimization. It is probably for the first time that alternative barrier functions have been found that in some cases provide better theoretical complexity results than the LBF. The results can be extended to other conic optimization problems; it is an open question if the new barrier functions can be adapted to primal methods and dual methods, respectively.

This is joint work with Y. Bai (Shanghai University, China) and M. Elghami (Delft University of Technology, Netherlands).

Speaker: Toshio Yoshikawa, IMA Postdoctoral Associate

Title: Toda Lattice Type Model for Nonlinear Viscoelastic Material

Abstract: Viscoelastic materials are materials which behave like elastic body in short time scale and like liquid in long time scale. In this talk I will discuss a mathematical model of viscoelastic materials. The model I propose here is based on Toda lattice. Toda lattice is an one-dimensional chain of nonlinear springs with exponential type force function; it is one of few known integrable mechanical systems. A remarkable feature of Toda lattice is that it has a family of exact solutions called solitons; these are solitary waves traveling at constant velocity along the lattice. I will modify Toda lattice to include viscoelasticity and discuss solitons on this modified lattice. As part of this talk, I will give the introduction to the solitons on the original Toda lattice.

Speaker: Luis N. Vicente, Department of Mathematics, University of Coimbra, Portugal IBM T.J. Watson Research Center, Yorktown Heights, New York and IMA, University of Minnesota

Title: Space Mapping: Models, Algorithms and Applications

Abstract: A number of new techniques have been developed to deal with optimization problems which involve expensive function evaluations from simulation or experimentation.

One of the techniques that has been recently considered in the engineering community is the so-called space-mapping approach. Space mapping assumes the existence of two models for the same physical phenomenon: a fine model, accurate and expensive, and a coarse model, significantly cheaper and considerably less accurate. The idea behind space mapping is to "construct" a mapping between the fine-model space of parameters or variables and the coarse-model space that allows to defer the optimization process to the coarse model, where most function evaluations should take place. Space-mapping techniques are typically iterative as the mapping is unknown a priori and it is calculated for a sequence of points in the fine space.

One of the goals of this talk is to organize some of the model and algorithmic aspects of space mapping in a mathematical framework which allows us to look at the properties of the space mapping and to fit the convergence analysis of the algorithms into the existence convergence theory of nonlinear optimization. We will also introduce new ways of building the space mapping and deriving the algorithms.

We will report recent numerical testing with the application of the space-mapping methodology to optimal control problems governed by partial differential equations. We will show how the space mapping technique can be used in the context of this class of problems.

This is joint work with Michael Hintermuller.

Speaker: Moritz Diehl, University of Heidelberg, Germany & IMA visitor January-March 2003

Title: Nominal Stability for Nonlinear Model Predictive Control

Abstract: Nonlinear Model Predictive Control (NMPC) is a technique for the design of feedback controllers that works by online minimization of an objective depending on the predicted system behaviour. Typically, the system shall be kept in some desired steady state, and the objective penalizes deviations from it. A basic requirement for the resulting feedback controller is that it stabilizes the system at the given operating point at least in the case that the model is perfect - this property is called nominal stability.

In the talk, I will introduce the basic ideas underlying the standard stability proofs for NMPC. I will shortly discuss how the stability problem changes if numerical optimization errors are taken into account, and give a sketch of recent results to address this problem.

Speaker: Peh Ng, Dept of Mathematics, University of Minnesota - Morris & IMA Visitor 2002-2003

Title: A Commodity Family Extended Formulation Approach to Solving Uncapacitated Fixed Charge Network Flow Problems

Abstract: In general, uncapacitated fixed charge network flow problem, (UF), is NP-Hard. However, previous research on a few NP-Hard problems has shown that improved linear programming relaxations can be obtained by using extended reformulations. In this research, we develop a theory of extended formulations for (UF) by reformulating these problems in terms of an extended variable set corresponding to flow commodities defined by arbitrary demand subsets. In particular, we show how to produce an extended formulation for any suitable commodity family and isolate simple axioms characterizing the families that yield the most useful reformulations.

Speaker: Michael J.D. Powell, University of Cambridge

Title: Radial Basis Function Methods for Global Optimization

Abstract:    pdf    ps

Speaker: John Dennis, Rice University and the IMA

Title: Working With Industry or My Life as an Evangelist

Abstract: In this talk, I will discuss my work with various industrial groups, including my first real experience as a consultant to the National Bureau of Economic Research starting in the early `70s. I will try to explain the research each collaboration motivated and how it affected my work with graduate students. I will also try to draw some conclusions on how to collaborate successfully with industrial or semi-industrial groups - in case you might want to try it.

My hope is to convince you that you can do interesting work and help the rather dismal image of mathematicians by seeking such collaborations yourself. To this end, there will not be many technical details, and I hope for an interactive presentation rather than a lecture.

Speaker: Dacian N. Daescu, IMA Postdoctoral Associate

Title: Adjoint-based Techniques for the Analysis of Large-scale Uncertain Systems

Abstract: Despite the increased complexity in the model representations, it is often the case that comprehensive dynamical models show poor results when compared to observational data. To address this problem we need to consider various factors that may contribute to the uncertainties in the analysis of dynamical systems. Data assimilation techniques (e.g. Kalman filter, variational methods) combine observations of a dynamical system with a dynamical model of the system to provide an optimal estimate of the evolving state of the system.

In four-dimensional variational data assimilation (4D-Var) a minimization algorithm is used to find the set of control variables such that an optimal fit between the model forecast and observations, scattered in time, is achieved. For large-scale models, the minimization of the cost functional is a very intensive computational process. At the same time, the development and validation of dynamical models require a systematic sensitivity analysis to evaluate the effects of parameter variations on model prediction.

The adjoint modeling is presented as an efficient tool to evaluate the sensitivity of a scalar response function with respect to initial conditions and model parameters. Using the adjoint method, the necessary gradient may be computed at the expense of few function evaluations, making the optimization process very efficient. The sensitivity field obtained through a single backward integration of the adjoint model may be used to identify parameters that play an essential role in determining the model forecast.

The intimate connection between measurements and models can be illustrated through the example of large-scale field experiments. The difficulty in planning such experiments lies in the fact that the features of interest are usually transient in nature. Expensive field-deployed resources (facilities and people) can be employed/utilized more effectively and science success can be maximized by an optimal allocation of the observational resources. The problem of optimal deployment of additional observational resources is presented and adjoint-based adaptive observations strategies using the singular value decomposition and gradient sensitivity are discussed in detail.

Numerical illustrations are shown for nonlinear chemical reactions systems and atmospheric circulation models.

Speaker: Maurice Queyranne, Professor of Management Science, Faculty of Commerce and Business Administration, University of British Columbia, Vancouver, Canada

Title: On Optimum Size-Constrained Set Partitions with Submodular Costs
Slides:    pdf

Speaker: Lili Ju, IMA Industrial Postdoc

Title: Some Topics on Centroidal Voronoi Tessellations

Centroidal Voronoi tessellations (CVT) are Voronoi tessellations of a region such that the generating points of the tessellations arealso the centroids of the corresponding Voronoi regions. Such tessellations and their extension for general surfaces are of use in very diverse applications, including data compression, clustering analysis, cell biology, territorial behavior of animals, optimal allocation of resources, grid generations and optimization, meshless computing, and interpolation. Some detreminstic and probabilistic algorithms for computing CVTs will also be discussed.

Speaker: Marshall Hampton, NSF Postdoctoral Fellow, School of Mathematics, U of M

Title: Celestial Mechanics: Recent Progress and Open Problems

Abstract: In the last few years there have been some exciting developments in celestial mechanics. A new type of orbit (a "choreography") in the 3-body problem was discovered which leads to many open questions. The study of relative equilibria in the n-body problem has blossomed and led to applications in energy efficient orbits for interplanetary spacecraft. Several weeks ago a solution was announced for the simplest case of a long-standing conjecture ("Saari's Conjecture") in the 3-body problem. An attempt will be made to survey some of these results, applications, and open problems.

Speaker: Michael Ball, R H Smith School of Business and Institute for Systems Research University of Maryland

Title: Mathematical Models for Supporting Available-to-Promise (ATP)
Slides:    html    pdf

Abstract: The Available to Promise (ATP) business function is the set of capabilities that support responding to customer order requests. Traditionally ATP refers to a simple database lookup into the Master Production Schedule. With the advent of e-business, make-to-order production and high variety product offerings, ATP functionality has become a critical component of many business? strategies and also now requires much more complex model and IT support. In this talk, we provide an overview of ATP-related research and of ATP business practice. We classify ATP research into two categories: push-based models, which allocate resources and prepare information based on forecasted demand and pull-based models, which generate responses to actual customer orders. A variety of relevant research will be covered, including mixed integer programming models for resource allocation, stochastic models of uncertain customer demand, on-line scheduling algorithms for generating order delivery dates and strategies for searching for available inventory.

Speaker: Daniel Kern, IMA Postdoctoral Associate

Title: Multispecies Competition and Traveling Waves

Abstract: The consideration of spatial factors in ecological modeling has led to a variety of interesting problems in the current literature. Besides better explaining the development of biological phenomena, the resulting models can lead to interesting mathematics. Here, the spread of two invasive plant species and the corresponding replacement of a single native species is examined as a competition model with spatial considerations. The general model is a system of three nonlinear reaction-diffusion equations of the Lotka-Volterra type. A model is developed for a specific case involving cottonwoods and two invasive plants in New Mexico. The existence of a traveling wave solution is then examined, leading to possible restrictions on the propagation speed of the exotic species.

Speaker: Lisa Evans, IMA Postdoctoral Associate

Title: An Overview of Gomory's Group Approach to Solving Integer Programs

Abstract: This talk will give an overview of Gomory's group approach to solving integer programs, including some of the key theorems. It will also describe how facets of master cyclic group problems can be used to generate cutting planes for general IP's. A related method that generates cutting planes from piecewise-linear subadditive functions that approximate the facets of master cyclic group problems will also be presented. Some new classes of facets for the master cyclic group problem will be described, as well as preliminary computational results using subadditive functions to generate cutting planes.

Speaker: Igor Vasilév,Universite di Salerno, Italy/ Institute of System Dynamics and Control Theory, Russia

Title: Computational Experience with Large-Scale p-Median Problems

Abstract: Given a directed graph, the p-Median problem consist of determining p nodes (the median nodes) minimizing the total distance to the other nodes of the graph. We present a Branch-and-Cut algorithm yielding provably good solutions for instances up to 3795 nodes of complete graphs, proving in most the cases their optimality. The key ingredients of our approach are: lagrangian relaxation, a simple procedure to choose the "promising variables," preprocessing, a column-and-row generation strategy to solve LP-relaxation, cutting planes.

Speaker: Miao-jung Yvonne Ou, IMA

Title: Object Inverse Scattering in an Ocean with Sloping Seabed

Abstract: This talk considers an obstacle inverse scattering problem in a sloping seabed. The incident waves are sent from point sources along a straight line parallel to the sea surface, and the corresponding scattered fields are measured from a line above the unknown object. We prove a uniqueness theorem for the inverse problem, and describe a generalized dual space indicator method for numerical solution. Numerical results will be presented.

Speaker: Professor Mike Siddoway, Colorado College (Visiting scholar in School of Math., UMN)

Title: R-Modules with the Krull-Schmidt Property

Abstract: A fundamental question mathematicians ask is whether a given structure decomposes in a nice way. For instance, in the ring of integers we know that any number can be written uniquely as a product of primes. If we expand the integers in some simple way we sometimes lose uniqueness. We also know that any finite dimensional vector space is completely characterized by its dimension. That is, there is only one way to write a vector space (up to isomorphism) as a direct sum of indecomposable vector spaces. The indecomposable vector spaces are simply the one dimensional vector spaces. An R-module is just a vector space with the scalar field replaced by a commutative ring. An abelian group can be viewed as a Z-module, a module over the integers. In module theory, we say that a class of modules has the Krull-Schmidt Property if every module in the class is uniquely (up to isomorphism) the direct sum of indecomposable members of the class. By our earlier comments we see that finite dimensional vector spaces have the Krull-Schmidt Property. This idea was first formulated by Krull in the 20's for finite groups. In this talk I will explore decompositions of modules with some finiteness conditions over various rings, and say a few things about when these modules have the Krull-Schmidt Property.