Monday May 12, 2003, 11:00 am - 12:00 noon
Luis Goddyn, IMA VIV Simon Fraser University

Modernizing the Million Dollar Permutation

Abstract:   Frank Gray's 1958 patent, "Pulse Code Communication" (pat. no. 2,632,058), earned him $1 million. His idea was a simple, recursively defined permutation of the n-bit binary words, with the property that adjacent words differ in exactly one bit position. Such a permutation is a Hamilton path in a hypercube, and is usually called a Binary Gray Code.

In recent years, applications in Engineering, Computer Science, and Statistics have demanded Gray codes with specialized properties. For example, certain applications demand contol of the number of times each bit position changes, while others demand that no bit changes twice in rapid succession. I present a survey regarding such Specialized Gray Codes, with a view to their construction, generation and application.

Monday April 21, 2003, 11:00 am - 12:00 noon
Saif Benjaafar (Graduate Program in Industrial Engineering, Dept of Mechanical Engineering, University of Minnesota  saif@ie.umn.edu)

Demand Allocation in Multiple-Product, Multiple-Facility Make-To-Stock Systems

Abstract:  We consider the problem of allocating demand arising from N products to M production facilities with finite capacity and load-dependent lead-times. Production facilities can choose to manufacture items either to-stock or to-order. If items are stocked, demand is satisfied immediately if there is on-hand inventory. Otherwise, demand is backlogged with the production facility to which it is assigned. Products vary in their demand rates, holding and backordering costs, and service level requirements. We develop models and solution procedures to determine the optimal allocation of demand to facilities and the optimal inventory level for products at each facility. We consider two types of demand allocation, one in which we allow the demand for a product to be split among multiple facilities and the other in which demand from each product must be entirely satisfied by a single facility. We refer to the former as the demand allocation problem and to the latter as the demand partitioning problem. For each case, we offer a solution procedure to obtain optimal demand allocations and optimal inventory base-stock levels. We use the models to characterize analytically several properties of the optimal solution. In particular, we highlight seven principles that relate the effects of cost, congestion, inventory pooling, customer segmentation, multiple sourcing, and process and demand variability.

Monday March 24, 2003, 11:00 am - 12:00 noon
Vera Kovacevic-Vujcic (University of Belgrade)

Stabilization of Interior-Point Methods for Linear and Semidefinite Programming

Abstract: In the first part of the lecture we study numerical stability problems arising in application of interior-point methods to degenerate linear programs. A general stabilization procedure (which can be used in primal, dual and primal-dual methods) is proposed and it is shown that it guarantees stable Cholesky decomposition of systems of normal equations. Results of numerical experiments with a set of highly degenerate test problems are also presented. In the second part of the talk we analyze behavior of a particular semidefinite programming method (proposed by Helmberg, Rendl, Vanderbei and Wolkowicz) on a special class of semidefinite programs obtained as relaxations of the traveling salesman problem. Optimal choice of parameters regarding numerical stability is proposed. Some numerical experience is presented.

Monday March 10, 2003, 11:00 am - 12:00 noon
Mituhiro Fukuda (Courant Institute of Mathematical Sciences, New York University & IMA Visitor)

The Conversion Method for Sparse Semidefinite Programs

Abstract: We start presenting the basic definitions on semidefinite programs (SDP) with a brief overview of some methods to solve these kind of problems. The "conversion method" which we propose here converts a given sparse SDP into an equivalent SDP with small block matrices which can be solved more efficiently by any primal-dual interior-point method code. The method is based on the matrix completion theory, and it manipulates the aggregate sparsity pattern (structure) represented by a graph of a given SDP. The conversion of the problem is performed entirely on this graph exploring basic properties of chordal graphs and clique trees. Heuristic procedures to estimate the computational cost of the converted problem is employed in this method. In particular, the method works efficiently when combined with the SDPA 6.0 (a C/C++ code to solve SDPs).

This is joint work with Katsuki Fujisawa (Dept. Mathematical Sciences, Tokyo Denki University) & Kazuhide Nakata (Dept. of Industrial Engineering and Management, Tokyo Institute of Technology).

Note: Luís N. Vicente's 3/10/2003 talk has been moved to the Brown Bag Seminar on 3/5/2003.

Monday March 3, 2003, 11:00 am - 12:00 noon
M.J.D. Powell (University of Cambridge)

On Least Frobenius Norm Updating of Quadratic Models

Abstract: In the UMN Mathematics Colloquium on February 13th, the speaker described an algorithm for unconstrained optimization, that calculates a change to the variables by minimizing a quadratic approximation Q to the objective function F within a trust region. Further, each Q interpolates some values of F, and the remaining freedom in Q is taken up by minimizing the Frobenius norm of the change to the second derivative matrix of Q from the previous model. Thus only 2n+1 interpolation conditions is typical, where n is the number of variables, and the resultant algorithm performs well in some experiments with between 10 and 160 variables. Occasionally, however, severe inefficiencies arise from computer rounding errors when the model is updated. On the other hand, the updating method has a useful stability property that removes automatically some of the errors that have accumulated from previous iterations. Examples of loss of accuracy will be given, the stability property will be explained, and some recent research of the author will be addressed, because its purpose is to provide a robust algorithm for unconstrained optimization without derivatives, by taking advantage of the stability property.

Monday February 10, 2003, 11:00 am - 12:00 noon, Lind Hall 409
John Dennis (Rice University and IMA)

Optimization Tech Transfer is a Two-Way Street

Abstract: This talk will present arguments, backed by examples from my industrial experience, that optimization is a particularly valuable tool for providing more robust solutions to industrial problems. My three main points will be:

* Optimization can only solve the problem you give it. Involving optimization expertise early in the problem formulation process will help users/clients refine their thinking by exploiting any weakness in their problem formulation.

* Academic Optimization technology provides a toolbox, but tools do not build a product. Inhouse optimization expertise is a key to success.

* Industrial optimization problems are becoming more difficult as the need for more reliable solutions in engineering design increases. Collaboration between academic and industrial optimization researchers is critical in developing robust and fit-for-purpose solutions to industrial problems.

Monday January 27, 2003, 11:00 am - 12:00 noon
Luis N. Vicente (Department of Mathematics, University of Coimbra, Portugal/IBM T.J. Watson Research Center, Yorktown Heights, New York, USA IMA, University of Minnesota, USA)

Error estimates and poisedness in multivariate polynomial optimization and derivative-free optimization

Abstract: We show how to derive error estimates between a function and its interpolating polynomial and between their corresponding derivatives. The derivation is based on a new concept of well-poisedness for the interpolation set, directly connecting the accuracy of the error estimates with the geometry of the points in the set. Our approach extracts the error bounds for all the derivatives using the same derivation; the error bound for the function values is then derived a posteriori. We design algorithms to build sets of well-poised interpolation points or to modify existing interpolation sets to ensure well-poisedness.

If time permits, we will also talk about derivative-free optimization techniques, relating geometrical concepts like well-poisedness and positive bases and pointing out the key ingredients for global convergence.

This is joint work with A.R. Conn and K. Scheinberg.

Monday December 9, 2002, 11:00 am - 12 noon
Montaz Ali (IMA Visitor 2002-2003 from Centre for Control Theory and Optimization, School of Computational and Applied Mathematics, University of the Witwatersrand)

A review of the stochastic global optimization methods

Abstract: The talk will cover the past and the recent developments, and the new frontiers of global optimization methods. Population set based methods, clustering methods, and the single point based methods will be discussed.