TR0218
PDF
file (265 kB)
Mixed Variable Optimization of a LoadBearing Thermal
Insulation System Using a Filter Pattern Search Algorithm
Mark A. Abramson
This paper describes the optimization of a loadbearing
thermal insulation system characterized by hot and cold
surfaces with a series of heat intercepts and insulators
between them. The optimization problem is represented as a
mixed variable programming (MVP) problem with nonlinear
constraints, in which the objective is to minimize the
power required to maintain the heat intercepts at fixed
temperatures so that one surface is kept sufficiently cold.
MVP problems are more general than mixed integer nonlinear
programming (MINLP) problems in that the discrete variables
are categorical; i.e., they must always take on
values from a predefined enumerable set or list. Thus,
traditional approaches that use branch and bound techniques
cannot be applied.
In a previous paper, a linearly contrained version of this
problem was solved numerically using the AudetDennis
generalized pattern search (GPS) method for MVP problems.
However, this algorithm may not work for problems with
general nonlinear constraints. A new algorithm that extends
that of Audet and Dennis by incorporating a filter to handle
nonlinear constraints makes it possible to solve the more
general problem. Additional nonlinear constraints on stress,
mass, and thermal contraction are added to that of the
previous work in an effort to find a more realistic feasible
design. Several computational experiments show a substantial
improvement in power required to maintain the system, as
compared to the previous literature. The addition of the new
constraints leads to a very different design without
significantly changing the power required. The results
demonstrate that the new algorithm can be applied to a very
broad class of optimization problems, for which no previous
algorithm with provable convergence results could be
applied.
Key words: Optimization, nonsmooth
optimization, thermal insulation, heat intercepts,
categorical variables, mixed variable programming,
pattern search algortihm, filter algorithm, nonlinear constraints.
December 2002 (revised May 2003)
TR0217
PDF
file (2.7 MB)
Solving the Inverse Problem of Electrocardiography Using a Duncan and
Horn Formulation of the Kalman Filter
Keith L. Berrier, Danny C. Sorensen and Dirar S. Khoury
Numeric regularization methods most often used to solve
the illposed inverse problem of electrocardiography are
spatial and ignore the temporal nature of the problem. In
this study, a reformulation of the Kalman filter was used to
incorporate temporal information in regularizing the inverse
problem. The inverse problem was solved in the left
ventricle by reconstructing endocardial surface electrograms
based on cavitary electrograms measured by a noncontact,
multielectrode probe. The results were validated based on
electrograms measured in situ at the same endocardial
locations using an integrated, multielectrode
basketcatheter. A threedimensional, probeendocardium
model was determined from multiplane fluoroscopic images.
The boundary element method was applied to solve the
boundary value problem and determine a linear relationship
between endocardial and probe potentials. The Duncan and
Horn formulation of the Kalman filter was employed and was
compared to the commonly used zero and firstorder Tikhonov
regularization as well as Twomey regularization. Endocardial
electrograms were reconstructed during both sinus and paced
rhythms. The Paige and Saunders solution of the Duncan and
Horn formulation reconstructed endocardial electrograms at
an amplitude relative error of 13% (potential amplitude)
which was superior to solutions obtained with zeroorder
Tikhonov (relative error, 31%), firstorder Tikhonov
(relative error, 19%), and Twomey regularization (relative
error, 44%). Likewise, activation error in the inverse
solution using the Duncan and Horn formulation (2.9 ms) was
smaller than that of zeroorder Tikhonov (4.8 ms),
firstorder Tikhonov (5.4 ms), and Twomey regularization
(5.8 ms). Therefore, temporal regularization based on the
Duncan and Horn formulation of the Kalman filter improves
the solution of the inverse problem of
electrocardiography.
Key words: Inverse problem, noncontact
mapping, regularization, Kalman filter.
December 2002 (revised March 2003)
TR0216
PS
file (901 kB)
A Successive Linear Programming Approach to IMRT
Optimization Problem
Michael Merritt, Yin Zhang, Helen Liu and Radhe Mohan
We propose to solve the IMRT optimization problem
through a successive linear programming approach. Taking
advantage of the sensitivity information in linear
programming and the reoptimization ability of simplex
methods, the proposed approach provides an affordable
methodology to efficiently solve problems with dosevolume
constraints. Preliminary computational results indicate
that, compared to the standard weighted least squares
approach, the new approach leads to higher tumor dosage
escalation and better conformation.
December 2002
TR0215
PS
file (321 kB)
Passivity Preserving Model Reduction via Interpolation of
Spectral Zeros
D. C. Sorensen
An algorithm is developed for passivity preserving model
reduction of LTI systems. The derivation is justified
analytically and implementation schemes are developed for
both medium scale (dense) and large scale (sparse)
applications. The algorithm is based upon interpolation of
specified spectral zeros of the original transfer function
to produce a reduced transfer function that has the
specified roots as its spectral zeros. These interpolation
conditions are satisfied through the computation of a basis
for a selected invariant subspace of a certain blocked
matrix which has the spectral zeros as its spectrum. It is
shown that this procedure indirectly solves the associated
controllability and observability Riccati equations and how
to select the interpolation points to give maximal or
minimal solutions of these equations. From these, a
balancing transformation may be constructed to give a
reduced model that is balanced as well as passive and
stable.
November 2002
TR0214
Approximate Implicit Subspace Iteration with Alternating
Directions for LTI system Model Reduction
Yunkai Zhou and D. C. Sorensen
We propose an Approximate Implicit Subspace Iteration with
Alternating Directions (AISIAD) framework for Linear Time
Invariant (LTI) system model reduction. The framework
approximates the dominant eigensubspaces of the product of
the system Gramians directly. This has advantage over the
many approaches that consider the system Gramians
separately. Two approaches within this framework are
constructed, one uses the QR updates, the other uses the SVD
updates. The efficiency of our approaches are shown by
extensive numerical results.
Key words: Implicit subspace iteration;
dominant eigensubspace; Lyapunov equations; projected matrix
equation; balanced model reduction.
November 2002
TR0213
PS
file (11 MB)
Variationally Constrained Numerical Solution of
Electrical Impedance Tomography
Liliana Borcea, Genetha Anne Gray and Yin Zhang
We propose a novel, variational inversion methodology
for the electrical impedance tomography problem, where we
seek electrical conductivity σ inside a bounded,
simply connected domain Ω, given simultaneous
measurements of electric currents I and potentials
V at the boundary. Explicitly, we make use of
natural, variational constraints on the space of admissible
functions σ, to obtain efficient reconstruction
methods which make best use of the data. We give a detailed
analysis of the variational constraints, we propose a
variety of reconstruction algorithms and we discuss their
advantages and disadvantages. We also assess the
performance of our algorithms through numerical simulations
and comparisons with other, well established, numerical
reconstruction methods.
October 2002
TR0212
PS
file (1458 kB)
Computational Experience with Lenstra's Algorithm
Liyan Gao and Yin Zhang
Integer programming is an important mathematical approach
for many decisionmaking problems. In this field, a major
theoretical breakthrough came in 1983 when H. W. Lenstra,
Jr. proposed a polynomialtime algorithm for a general
integer programming feasibility problem where the number of
variables is fixed. Two key ingredients of Lenstra's
algorithm are ellipsoidal approximation of polytopes and
lattice basis reduction. However, the lack of practically
efficient algorithms and software for the ellipsoidal
approximation of polytopes had made it difficult to study
the computational properties of Lenstra's algorithm. In
this paper, using a newly developed ellipsoidal
approximation algorithm as a subroutine, we have implemented
a version of Lenstra's algorithm for the general integer
programming feasibility problem. Our numerical results on
small to mediumsized test instances indicate that
Lenstra's algorithm often examines far fewer nodes than
the traditional branchandbound approach. Currently, the
main bottleneck in the performance of the algorithm lies in
the step of lattice basis reduction.
August 2002
TR0211
PDF
file (960 kB)
Pattern Search Algorithms for Mixed Variable General
Constrained Optimization Problems
Mark Aaron Abramson
A new class of algorithms for solving nonlinearly
constrained mixed variable optimization problems is
presented. The AudetDennis Generalized Pattern Search (GPS)
algorithm for bound constrained mixed variable optimization
problems is extended to problems with general nonlinear
constraints by incorporating a filter, in which new iterates
are accepted whenever they decrease the incumbent objective
function value or constraint violation function value.
Additionally, the algorithm can exploit any available
derivative information (or rough approximation thereof) to
speed convergence without sacrificing the flexibility often
employed by GPS methods to find better local optima. In
generalizing existing GPS algorithms, the new theoretical
convergence results presented here reduce seamlessly to
existing results for more specific classes of problems.
While no local continuity or smoothness assumptions are
made, a hierarchy of theoretical convergence results is
given, in which the assumptions dictate what can be proved
about certain limit points of the algorithm. A new
Matlab^{®} software package was developed to
implement these algorithms. Numerical results are provided
for several nonlinear optimization problems from the CUTE
test set, as well as a difficult nonlinearly constrained
mixed variable optimization problem in the design of a
loadbearing thermal insulation system used in cryogenic
applications.
August 2002
TR0210
PDF
file (198 kB)
Generalized Pattern Searches with Derivative
Information
Mark A. Abramson, Charles Audet and J. E. Dennis, Jr.
A common question asked by users of direct search algorithms is how to use derivative information at iterates where it is available. This paper addresses that question with respect to Generalized Pattern Search (GPS) methods for unconstrained and linearly constrained optimization. Specifically this paper concentrates on the GPS POLL step. Polling is done to certify the need to refine the current mesh, and it requires O(n) function evaluations in the worst case. We show that the use of derivative information significantly reduces the maximum number of function evaluations necessary for POLL steps, even to a worst case of a single function evaluation with certain algorithmic choices given here. Furthermore, we show that rather rough approximations to the gradient are sufficient to reduce the POLL step to a single function evaluation. We prove that using these less expensive POLL steps does not weaken the known convergence properties of the method, all of which depend only on the POLL step.
Key words: Pattern search algorithm, linearly
constrained optimization, surrogatebased optimization,
nonsmooth optimization, gradientbased optimization.
June 2002 (revised October 2003)
TR0209
PS
file (1120 kB)
A Global Optimization Method for the Molecular
Replacement Problem in Xray Crystallography
Diane C. Jamrog, George N. Phillips, Jr., Richard A.
Tapia and Yin Zhang
The primary technique for determining the threedimensional
structure of a protein molecule is Xray crystallography,
from which the molecular replacement (MR) problem often
arises as a critical step. The MR problem is a global
optimization problem to locate an optimal position of a
model protein, whose structure is similar to the unknown
protein structure that is to be determined, so that at this
position the model protein will produce calculated
intensities closest to those observed from an Xray
crystallography experiment. Improving the applicability and
robustness of MR methods is an important research topic
because commonly used traditional MR methods, though often
successful, have their limitations in solving difficult
problems.
We introduce a new global optimization strategy that
combines a coarsegrid search, using a surrogate function,
with extensive multistart local optimization. A new MR
code, called SOMoRe, based on this strategy is developed and
tested on four realistic problems, including two difficult
problems that traditional MR codes failed to solve directly.
SOMoRe was able to solve each test problem without any
complication, and SOMoRe solved a MR problem using a less
complete model than the models required by three other
programs. These results indicate that the new method is
promising and should enhance the applicability and
robustness of the MR methodology.
Key words: Molecular replacement problem,
Xray crystallography, global optimization, surrogate
function, global search, multistart local
optimization.
June 2002
TR0208
PS
file (4 MB)
PS
gzipped file (722 kB)
A New Global Optimization Strategy for the Molecular
Replacement Problem
Diane C. Jamrog
The primary technique for determining the threedimensional
structure of a protein is Xray crystallography, in which
the molecular replacement (MR) problem arises as a critical
step. Knowledge of protein structures is extremely useful
for medical research, including discovering the molecular
basis of disease and designing pharmaceutical drugs. This
thesis proposes a new strategy to solve the MR problem,
which is a global optimization problem to find the optimal
orientation and position of a structurally similar model
protein that will produce calculated intensities closest to
those observed from an Xray crystallography experiment.
Improving the applicability and the robustness of MR methods
is an important research goal because commonly used
traditional MR methods, though often successful, have
difficulty solving certain classes of MR problems.
Moreover, the use of MR methods is only expected to increase
as more structures are deposited into the Protein Data
Bank.
The new strategy has two major components: a sixdimensional
global search and multistart local optimization. The
global search uses a lowfrequency surrogate objective
function and samples a coarse grid to identify good starting
points for multistart local optimization, which uses a more
accurate objective function. As a result, the global search
is relatively quick and the local optimization efforts are
focused on promising regions of the MR variable space where
solutions are likely to exist, in contrast to the
traditional search strategy that exhaustively samples a
uniformly fine grid of the variable space. In addition, the
new strategy is deterministic, in contrast to stochastic
search methods that randomly sample the variable space.
This dissertation introduces a new MR program called SOMoRe
that implements the new global optimization strategy. When
tested on seven problems, SOMoRe was able to
straightforwardly solve every test problem, including three
problems that could not be directly solved by traditional MR
programs. Moreover, SOMoRe also solved a MR problem using a
less complete model than those required by two traditional
programs and a stochastic sixdimensional program. Based on
these results, this new strategy promises to extend the
applicability and robustness of MR.
June 2002
TR0207
PS
file (665 kB)
PDF
file (300 kB)
Bounds on eigenvalue decay rates and sensitivity of
solutions to Lyapunov equations
D. C. Sorensen and Y. Zhou
Balanced model reduction is a technique for producing a low
dimensional approximation to a linear time invariant system.
An important feature of balanced reduction is the existence
of an error bound that is closely related to the decay rate
of the eigenvalues of certain system Gramians. Rapidly
decaying eigenvalues imply low dimensional reduced systems.
New bounds are developed for the eigendecay rate of the
solution of Lyapunov equation
AP + PA^{T}
= BB^{T}.
These bounds take into account the low rank right hand side
structure of the Lyapunov equation. They are valid for any
diagonalizable matrix A. Numerical results are
presented to illustrate the effectiveness of these bounds
when the eigensystem of A is moderately
conditioned.
We also present a bound on the norm of the solution
P when A is diagonalizable and derive bounds
on the conditioning of the Lyapunov operator for general
A.
Key words: Lyapunov equation; Lyapunov
operator; Low rank; Conditioning; Eigenvalue decay
rate.
June 2002
TR0206
PS
file (1151 kB)
PDF
file (386 kB)
Hundred Digit Challenge Solutions
Eric Dussaud, Chris Husband, Hoang Nguyen, Daniel
Reynolds and Christiaan Stolk
This paper details our solutions to the
"Hundreddollar,
Hundreddigit Challenge", which appeared in Volume 35,
Number 1 of SIAM News.
May 2002
TR0205
PDF
file (548 kB)
Optimal Control of Aeroacoustic Noise Generated by
Cylinder Vortex Interaction
S. Scott Collis, Kaveh Ghayour and Matthias Heinkenschloss
This paper presents an optimal control formulation and
solution for an idealized Blade Vortex Interaction (BVI)
problem. This problem consists of the interaction of an
inviscid vortex pair with a circular cylinder in a steady
Mach 0.3 uniform flow with wallnormal velocity used as
control on the cylinder surface. This model problem captures
the fundamental noise generation process of the BVI
phenomena while mitigating many of the complexities of the
full rotorcraft problem. As such, it serves as a stepping
stone towards optimal control of realistic BVI flows. The
optimal control problem is solved using a gradient based
method where gradient information is computed from a
continuous adjoint analysis of the governing unsteady Euler
equations. The BVI wave packet is targeted by defining an
objective function that measures the square amplitude of
pressure fluctuations in an observation region over a time
interval of interest. The computed control actuation
reduces BVI noise to 6% of its uncontrolled value which is a
reduction in sound pressure level of 12db. The optimal
control, unlike most common mitigation methods, does not
target the interaction directly  instead, the computed
boundary control, when processed by the potential flow about
the cylinder, produces a wave packet of the correct
amplitude and phase to approximately cancel the BVI noise in
the observation region.
May 2002
TR0204
PDF
file (1439 kB)
Programming the Nanocell, a Random Array of Molecules
Summer M. Husband
The emerging field of molecular electronics seeks to create
computational function from individual molecules or arrays
of molecules. These nanoscale devices would then enable the
production of faster, denser, cheaper computers. Clearly,
there are many obstacles to building such devices, one of
which is to develop methods for using lithographic wires to
address molecules that are many orders of magnitude smaller
in size. In this thesis, a moletronics design is presented
that offers a method for connecting nanometer molecules to
the worldatlarge. This architecture involves the
production of nanocells, or random arrays of molecules and
metallic nanoparticles. The molecules have two discrete
states and exhibit electrical behavior that enables complex
logic in a nanocell. Methods are presented to take a random
array of such switch states and alter them to program a
nanocell as a useful logical device. Simulations of this
programming process are presented and show that it is
theoretically possible to obtain very high level function
from these cells. Observations made during simulations are
then used to formulate theorems about the programmability of
nanocells. These theorems demonstrate that there is a dense
solution space of molecular switch states that give rise to
certain computation within a nanocell. Future directions of
research, such as methods for wiring multiple nanocells
together, are included as well.
May 2002
TR0203
PS
gzipped file (939 kB)
PS
file (for PC users) (939 kB)
Numerical Methods for Large Scale Matrix Equations with
Applications in LTI System Model Reduction
Yunkai Zhou
LTI (Linear Time Invariant) systems arise frequently in
different branches of engineering. This thesis mainly
concerns the properties and numerical methods for large
scale matrix equations related to LTI systems, the final
goal is model reduction.
Due to the importance of small to medium scale matrix
equations, we firstly made formulation improvements to the
two standard direct methods (the BartelsStewart's method
and the Hammarling's method) for Sylvester and Lyapunov
equations. Numerical evidence and flop counts show the
better performance of our modified formulations.
The low rank solution property of large scale Lyapunov
equations is the basis for any algorithm that computes low
rank approximate solutions. We study the eigendecay rate of
the solution since eigendecay rate is closely related to
the low rank solution property. New eigendecay rate bounds
and estimated rates are established for general nonsymmetric
Lyapunov equation. Connections between the solution of
Lyapunov equation and some special matrices are discussed,
which further reveal different properties of the solution.
We also present new bounds on the conditioning of Lyapunov
operator.
Finally, we develop an AISIAD (Approximate Implicit Subspace
Iteration with Alternating Directions) framework for model
reduction. Two new approaches within this framework are
constructed. The efficiency of these approaches are
demonstrated by numerical results.
May 2002
TR0202
PS
file (34 MB)
PS
(textonly) file (644 kB)
A Variational Study of the Electrical Impedance
Tomography Problem
Genetha Anne Gray
This research is focused on the numerical solution of the
inverse conductivity problem, widely known as electrical
impedance tomography (EIT). The EIT problem is concerned
with imaging electrical properties, such as conductivity
(sigma) and permittivity (epsilon), in the
interior of a body given measurements of d.c. or a.c.
voltages and currents at the boundary. Given complete and
perfect knowledge of the boundary data, the EIT problem is
known to have a unique solution. In practice however, the
data is noisy and incomplete. Hence, satisfactory solutions
of the nonlinear illposed EIT problem are difficult to
obtain.
In this thesis, we introduce a family of variational
formulations for the EIT problem which we show to have
advantages over the popular output least squares approach.
Output least squares seeks sigma and/or
epsilon by minimizing the voltage misfit at the
boundary measured in the L^{2} norm. In
contrast, the variational methods ensure that the measured
data is being fit in a more natural norm, which is not the
L^{2} norm. These
methods also introduce some
natural regularization. Through extensive numerical
experimentation, we compare the performance of our
variational formulations with one another and with the
standard least squares algorithm. Using the same data, we
demonstrate that our variational algorithms produce better
images without significantly increasing computational
cost.
April 2002
TR0201
PDF
file (242 kB)
Analysis of the SUPG Method for the Solution of Optimal
Control Problems
S. S. Collis and M. Heinkenschloss
We study the effect of the streamline upwind/Petrov
Galerkin (SUPG) stabilized finite element method on the
discretization of optimal control problems governed by
linear advectiondiffusion equations. We compare two
approaches for the numerical solution of such optimal
control problems. In the discretizethenoptimize approach
the optimal control problem is first discretized, using the
SUPG method for the discretization of the
advectiondiffusion equation, and then the resulting finite
dimensional optimization problem is solved. In the
optimizethendiscretize approach one first computes the
infinite dimensional optimality system, involving the
advectiondiffusion equation as well as the adjoint
advectiondiffusion equation, and then discretizes this
optimality system using the SUPG method for both the
original and the adjoint equations. These approaches lead to
different results. The main result of this paper is an
estimates for the error between the solution of the infinite
dimensional optimal control problem and their approximations
computed using the previous approaches. For a class of
problems prove that the optimizethendiscretize approach
has better asymptotic convergence properties if finite
elements of order greater than one are used. For linear
finite elements our theoretical convergence results for both
approaches are comparable, except in the zero diffusion
limit where again the optimizethendiscretize approach
seems favorable. Numerical examples are presented to
illustrate some of the theoretical results.
March 2002
Go to 2001 reports
Go to 2003 reports
