May 3, 2005 -- 5:00 pm.
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
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.
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
March 1, 2005 -- 5:00 p.m.
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
In this talk, we introduce this topic by considering some background
on nonlinear optimization and the basic interior point framework.
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.
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
February 1, 2005 -- 5:00 p.m.
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
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
December 7, 2004 -- 5:00 p.m.
George F. Corliss, Marquette University
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
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
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