Andrew Conn, IBM
Optimization at Watson
Derivative Free Optimization and Not An Introduction and New Results

I will present current work at the IBM T.J. Watson Research Center in nonlinear optimization that are two significantly different approaches. One is derivative free optimization, for relatively small problems with expensive function evaluations and the other makes uses of derivatives and is designed for large problems. In both case I will give real applications in circuit tuning that are important for IBMs computer manufacturing and I will also try to give insights into the underlying algorithms.

Chandu Visweswariah, IBM
Mathematics and Engineering: A Clash of Cultures?

Integrated circuit design consists of a series of optimization steps. From high-level design all the way through floorplanning, logic synthesis, circuit design, transistor sizing, placement, routing and testing, each step is a unique type of optimization problem. The few places where formal mathematical optimization algorithms have worked well will be pointed out. In practice, however, most of these steps use heuristic methods. This presentation will examine the reasons for the relative lack of penetration of mathematical optimization into mainstream chip design methodology. Among others, one of the salient reasons is that mathematicians and engineers have deeply held biases and cultural traits. Some of the hurdles include speaking different languages, approaching problems differently and having different priorities. If these hurdles are overcome by both communities, mathematical techniques can have a much wider impact on chip design methodology. Open problems and opportunities for collaboration will be discussed.

April 5, 2005 -- 5:00 p.m.

Leon Lasdon
Information, Risk, and Operations Management Dept., McCombs School of Business, University of Texas
SLP Algorithms and Refinery Optimization

Successive Linear Programming (SLP) Algorithms were first developed by practitioners in the oil and chemical industry, e.g. Griffith and Stewart of Shell Development Company around 1960, and have been the most widely used NLP algorithms in that field since then. The major reasons are that they can solve large models, and work well for mostly linear and/or highly constrained problems. In the mid 1980's, Lasdon and Zhang et al wrote a series of papers in which trust region ideas were applied to yield improved SLP algorithms with provable convergence to a local solution. These have been implemented by Shell and others, and incorporated into both proprietary and commercially available refinery modeling systems.

David R. Heltne
Managing Consultant - SCM, Lakeside Technology Associates
Refinery Planning Using SLP Algorithms

Refinery planning is one of the very early major applications of optimization - linear programming at the start. As computers, modeling systems and optimization codes have improved, the size and complexity of the refinery planning models has increased to match these improvements. Current refinery models include many nonlinearities around pools, product blending, weight volume conversions and sometimes in the conversion unit yield vectors. In this presentation, I will present some background on refineries and refinery planning, illustrate the optimization problem and the nonlinearities and provide some results of large planning models which used an SLP code based on the trust region ideas of Lasdon and Zhang.

March 1, 2005 -- 5:00 p.m.

Andreas Waechter
IBM T.J. Watson Research Center
Interior Point Algorithms for Large-Scale Nonlinear Programming: Theory and Algorithmic Development

The field of nonlinear programming (NLP), which deals with the minimization of a smooth objective function subject to smooth constraints, originated over 50 years ago. Nevertheless, the development of new numerical algorithms, particularly for large-scale problems, remains a very active research area. The past 10-15 years have seen a lot of activity in interior point methods. Following on the success of these methods for linear programming, interior point NLP methods have been developed and shown to be able to effectively solve problems with millions of variables.

In this talk, we introduce this topic by considering some background on nonlinear optimization and the basic interior point framework. We
then discuss the question of global convergence (i.e. guaranteed convergence from any given starting point) in some detail. In particular, we will describe a filter line search procedure, which is able to overcome certain drawbacks of the basic method to obtain stronger convergence properties. We will further discuss some recent developments regarding adaptive update procedures for the barrier parameter, which aim to improve the efficiency of the method. Numerical results on a large test set for an open-source software implementation of the algorithm (IPOPT) will be presented.

Larry Biegler
Carnegie Mellon University
Interior Point Algorithms for Large-Scale Nonlinear Programming: Applications in Dynamic Systems

Optimization of dynamic systems covers a wide range of engineering applications. Moreover, many of these problem formulations lead to
large-scale NLPs that may exhibit severe nonlinearities and degeneracies. As a result, algorithms are needed that exploit structure, handle constraints efficiently, and also have desirable global and local convergence properties. This talk presents a number of applications that drive the development of large-scale NLP algorithms. Using IPOPT as the framework, we consider a number of dynamic optimization problems. These include inverse problems for municipal water networks and oil reservoirs, control problems for chemical plants and aircraft trajectories, and design problems for biological and chemical systems. We detail the formulation of these problems using a simultaneous (or direct transcription) approach. In each example we emphasize particular structural features that need to be considered for efficient solution. We then show how NLP algorithms like IPOPT can exploit these features. Finally, we describe future challenges that are driven by these large-scale applications. These problems include mathematical programs with equilibrium constraints, singular control problems and distributed systems represented by PDEs

February 1, 2005 -- 5:00 p.m.

John Dennis,
Research Professor and Noah Harding Professor Emeritus, Rice University
Optimization using surrogates for engineering design

This talk will outline the surrogate management framework, which is presently built on the filter MADS method for general nonlinear programming without derivatives. This line of research was motivated by industrial applications, indeed, by a question I was asked by Paul Frank of Boeing Phantom Works. His group was often asked for help in dealing with very expensive low dimensional design problems from all around the company. Everyone there was dissatisfied with the common practice of substituting inexpensive surrogates for the expensive ``true'' objective and constraint functions in the optimal design formulation. I hope to demonstrate in this talk just how simple the answer to Paul's question is.

The surrogate management framework has been implemented successfully by several different groups, and it is unreasonably effective in practice, where most of the application are extended valued and certainly nondifferentiable. This has forced my colleagues and me to begin to learn some nonsmooth analysis, which in turn has led to MADS, a replacement for the GPS infrastructure algorithm.

John Betts,
Math and Engineering Analysis, The Boeing Company
Is a Good NLP all you need to Solve Optimal Control Problems?

Most computational methods for solving optimal control problems utilize a nonlinear programming algorithm as the basis for an iterative process. Consequently it is tempting to ask, "Is a good NLP all you need to Solve Optimal Control Problems?" This presentation will address this question and also discuss what aspects of an NLP are most important for the optimal control
application.

December 7, 2004 -- 5:00 p.m.

George F. Corliss, Marquette University
Automatic Differentiation

Automatic differentiation is a technique for providing fast, accurate values of derivative objects (gradients, Hessians, Taylor series) required by modern tools for optimization, nonlinear systems, differential equations, or sensitivity analysis. We outline some needs and applications for derivatives, survey the functionality of AD in forward and reverse modes, and discuss some of the mathematical and computer science challenges of AD.

This talk should be accessible after first semester calculus and a programming course in data structures. It should be interesting to researchers in symbolic computation or in scientific or engineering applications requiring almost any numerical analysis technique requiring derivatives.

Joaquim Martins, University of Toronto
Aero-Structural Wing Design using Coupled Sensitivity Analysis

An overview of existing methods for computing the sensitivity of single and coupled systems is presented. The focus is on the application of two of the methods -- the complex-step derivative approximation and the coupled-adjoint method -- to an aero-structural solver. The resulting framework calculates the sensitivities of aerodynamic and structural cost functions with respect to both aerodynamic shape and structural variables. The aero-structural adjoint sensitivities are compared with those given by the complex-step derivative approximation and finite differences. The proposed method is shown to be both accurate and efficient, exhibiting a significant cost advantage when the gradient of a small number of functions with respect to a large number of design variables is needed. The optimization of a supersonic business jet configuration demonstrates the efficiency of the coupled-adjoint approach and the importance of computing the coupled sensitivities.

November 2, 2004 -- 5:00 p.m.

Henry Wolkowicz, COO Waterloo
Robust algorithms for large sparse semidefinite programming (SDP)

Semidefinite Programming, SDP, refers to optimization problems where the vector variable is a symmetric matrix which is required to be positive semidefinite. Though SDPs (under various names) have been studied as far back as the 1940s, the interest has grown tremendously during the last fifteen years. This is partly due to the many diverse applications in e.g. engineering, combinatorial optimization, and statistics. Part of the interest is due to the great advances in efficient solutions for these types of problems.

Current paradigms for search directions for primal-dual interior-point methods for SDP use: (i) symmetrize the linearization of the optimality conditions at the current estimate; (ii) form and solve the Schur complement equation for the dual variable dy; (iii) back solve to complete the search direction. These steps result in loss of sparsity and ill-conditioning/instability, in particular when one takes long steps and gets close to the boundary of the positive semidefinite cone. This has resulted in the exclusive use of direct, rather than iterative methods, for the linear system.
We look at alternative paradigms based on least squares, an inexact Gauss-Newton approach, and a matrix-free preconditioned conjugate gradient method. This avoids the ill-conditioning in the nondegenerate case. We emphasize exploiting structure in large sparse problems. In particular, we look at LP and SDP relaxations of the: Max-Cut; Quadratic Assignment; Theta function; Nearest Correlation Matrix; and Nearest Euclidean Distance Matrix problems.

Antony Vannelli, Department of Electrical and Computer Engineering
University of Waterloo

New Modelling Techniques for the Global Routing Problem
Modern integrated circuit design involves laying out circuits which consist of millions of switching elements or transistors. The circuit interconnection is the single most important factor in performance criteria such as signal delay, power dissipation, circuit size and cost. The wire-minimization is formulated as a sequence of discrete optimization problems that are known to be NP-hard. In this talk, we present new modelling techniques to solve one such problem - global routing. The main contribution of this work is that we incorporate wirelength minimization with congestion reduction in the formulation of an integer programming model. It turns out that by adding congestion modelling into the objective function, the optimal solution of the resulting "relaxed LP" has mostly 0-1 solutions. The structure of the constraint matrix have been exploited to obtain global routing solutions in vary fast time for benchmark circuits.

Back to top