Mixed Variable Optimization of a Load-Bearing Thermal Insulation System Using a Filter Pattern Search Algorithm
Mark A. Abramson

This paper describes the optimization of a load-bearing 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 Audet-Dennis 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)

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 ill-posed 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 basket-catheter. A three-dimensional, probe-endocardium 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 first-order 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 zero-order Tikhonov (relative error, 31%), first-order 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 zero-order Tikhonov (4.8 ms), first-order 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)

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 re-optimization ability of simplex methods, the proposed approach provides an affordable methodology to efficiently solve problems with dose-volume 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

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

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

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

Computational Experience with Lenstra's Algorithm
Liyan Gao and Yin Zhang

Integer programming is an important mathematical approach for many decision-making problems. In this field, a major theoretical breakthrough came in 1983 when H. W. Lenstra, Jr. proposed a polynomial-time 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 medium-sized test instances indicate that Lenstra's algorithm often examines far fewer nodes than the traditional branch-and-bound approach. Currently, the main bottle-neck in the performance of the algorithm lies in the step of lattice basis reduction.

August 2002

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 Audet-Dennis 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 load-bearing thermal insulation system used in cryogenic applications.

August 2002

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) meth-ods 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, surrogate-based optimization, nonsmooth optimization, gradient-based optimization.

June 2002 (revised October 2003)

A Global Optimization Method for the Molecular Replacement Problem in X-ray Crystallography
Diane C. Jamrog, George N. Phillips, Jr., Richard A. Tapia and Yin Zhang

The primary technique for determining the three-dimensional structure of a protein molecule is X-ray 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 X-ray 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 coarse-grid search, using a surrogate function, with extensive multi-start 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, X-ray crystallography, global optimization, surrogate function, global search, multi-start local optimization.

June 2002

A New Global Optimization Strategy for the Molecular Replacement Problem
Diane C. Jamrog

The primary technique for determining the three-dimensional structure of a protein is X-ray 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 X-ray 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 six-dimensional global search and multi-start local optimization. The global search uses a low-frequency surrogate objective function and samples a coarse grid to identify good starting points for multi-start 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 six-dimensional program. Based on these results, this new strategy promises to extend the applicability and robustness of MR.

June 2002

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 eigen-decay 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

Hundred Digit Challenge Solutions
Eric Dussaud, Chris Husband, Hoang Nguyen, Daniel Reynolds and Christiaan Stolk

This paper details our solutions to the "Hundred-dollar, Hundred-digit Challenge", which appeared in Volume 35, Number 1 of SIAM News.

May 2002

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 wall-normal 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

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 world-at-large. 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

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 Bartels-Stewart'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 eigen-decay rate of the solution since eigen-decay rate is closely related to the low rank solution property. New eigen-decay 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

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 ill-posed 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² norm. In contrast, the variational methods ensure that the measured data is being fit in a more natural norm, which is not the L² 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

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 advection-diffusion equations. We compare two approaches for the numerical solution of such optimal control problems. In the discretize-then-optimize approach the optimal control problem is first discretized, using the SUPG method for the discretization of the advection-diffusion equation, and then the resulting finite dimensional optimization problem is solved. In the optimize-then-discretize approach one first computes the infinite dimensional optimality system, involving the advection-diffusion equation as well as the adjoint advection-diffusion 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 optimize-then-discretize 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 optimize-then-discretize approach seems favorable. Numerical examples are presented to illustrate some of the theoretical results.

March 2002

Go to 2001 reports

Go to 2003 reports