A Generalized Trust Region Algorithm for Equality Constrained Optimization
Zhen Wang

We introduce and analyze a class of generalized trust region sequential quadratic programming (GTRSQP) algorithms for equality constrained optimization. Unlike in standard trust region SQP (TRSQP) algorithms, the optimization subproblems arising in our GTRSQP algorithm can be generated from models of the objective and constraint functions that are not necessarily based on Taylor approximations. The need for such generalizations is motivated by optimal control problems for which model problems can be generated using, e.g., different discretizations.

Several existing TRSQP algorithms are special cases of our GTRSQP algorithm. Our first order global convergence result for the GTRSQP algorithm applied to TRSQP allows one to relax the condition that the so-called tangential step lies in the null-space of the linearized constraints.

The application of the GTRSQP algorithm to an optimal control problem governed by Burgers equation is discussed.

Key words: Elliptic optimal control problems, domain decomposition, Neumann-Neumann methods, iterative solution

December 2003 (Submitted Nov. 03)

Balancing Neumann-Neumann Methods for Elliptic Optimal Control Problems
Matthias Heinkenschloss and Hoang Nguyen

We present Neumann-Neumann domain decomposition (DD) preconditioners for the solution of elliptic linear quadratic optimal control problems. The preconditioner is applied to the optimality system. A Schur complement formulation is derived that reformulates the original optimality system as a system in the state and adjoint variables restricted to the subdomain boundaries. The application of the Schur complement matrix requires the solution of subdomain optimal control problems with Dirichlet boundary conditions on the subdomain interfaces. The application of the inverses of the subdomain Schur complement matrices require the solution of subdomain optimal control problems with Neumann boundary conditions on the subdomain interfaces. Numerical tests show that the dependence of this preconditioner on mesh size and subdomain size is comparable to its counterpart applied to elliptic equations only.

Key words: Elliptic optimal control problems, domain decomposition, Neumann-Neumann methods, iterative solution

December 2003

Design and Implementation of whirl2xaif and xaif2whirl
Nathan Tallent and Mike Fagan

In order to connect the Open64 Fortran front end to the xaifbooster differentiation engine, we needed to develop bridging tools to translate between Open64 intermediate representation language whirl and xaifbooster intermediate representation XAIF. This report describes the design and implementation of these translation tools: whirl2xaif and xaif2whirl.

Key words:

November 2003

Porting Open64 to the Cygwin Environment
Nathan Tallent and Mike Fagan

Cygwin is a Linux-like environment for Windows. It is sufficiently complete and stable that porting even very large codes to the environment is relatively straightforward. Cygwin is easy enough to download and install that it provides a convenient platform for traveling with code and giving conference demonstrations (via laptop) -- even potentially expanding a code's audience and user base (via desktop). However, for various reasons, Cygwin is not 100\% compatible with Linux. We describe the major problems we encountered porting Rice University's Open64/SL code base to Cygwin and present our solutions.

Key words:

November 2003

Generalized Newton Methods for Crack Problems with Non-Penetration Condition
M. Hintermüller, V.A. Kovtunenko, and K. Kunisch

A class of semismooth Newton methods for unilaterally constrained variational problems modelling cracks under a non-penetration condition are introduced and investigated. On the continuous level, a penalization technique is applied which allows to argue generalized differentiability of the nonlinear mapping associated to its first order optimality characterization. It is shown that the corresponding semismooth Newton method converges locally superlinearly. For the discrete version of the problem, fast local as well as global and monotonous convergence of a discrete semismooth Newton method are proved. A comprehensive report on numerical tests for the two-dimensional Lamé problem with three collinear cracks under the non-penetration condition ends the paper.

Key words: Variational inequality, complementarity problem, cracks with non-penetration, linear elasticity, semismooth Newton method.

November 2003

Verifying A Runge-Kutta Solver Using ADOL-C
C. Edwards and M. Fagan

This report describes our effort to verify differential equation solvers using automatic differentiation (AD). In particular, the report describes the AD verification technique in general, as well as the application of the technique to a 4th order Runge-Kutta solver using the ADOL-C tool.

Key words:

November 2003

Automatic Differentiation of Polymorphic Fortran 77 Programs Using Adifor 3.0
M. Fagan and C. Rankin

Adifor 3.0 is a source-to-source transformation tool used to augment programs that compute derivatives. As part of the transformation process, Adifor analyzes certain aspects of program behaviour. Furthermore, that analysis depends on the original program being type correct. Since standard Fortran is officially monomorphic, the assumption of type correctness is not normally a difficult constraint to satisfy. There is a class of (non-standard) Fortran programs, however, that take advantage of the pass-by-reference semantics to be, in effect, polymorphic. This report details some techniques for differentiating these polymorphic programs using monomorphic Adifor 3.0. In particular, we report on our efforts to compute derivatives for the structural analysis code STAGS.

Key words:

November 2003

A SQP-Semi-Smooth Newton-Type Algorithm Applied to Control of the Instationary Navier-Stokes System Subject to Control Constraints
M. Hintermüller and M. Hinze

Sequential quadratic programming (SQP) methods for the optimal control of the instationary Navier-Stokes equations with pointwise constraints on the control are considered. Due to the presence of the constraints the quadratic subproblems (QP) of SQP require a more sophisticated solver compared to the unconstrained case. In this paper, a semismooth Newton method is proposed for efficiently solving the QPs. The convergence analysis, which is performed in an appropriate function space setting, relies on the concept of the slant differentiability for proving locally superlinear convergence of the QP-solver. For the analysis of the outer SQP-iteration a generalized equations approach is utilized. Sufficient conditions for guaranteeing strong regularity of the generalized equation are established which, in turn, allows to argue a quadratic rate of convergence of the SQP-method. The paper ends with a report on numerical results supporting the theoretical findings.

Key words: Box constraints, generalized equations, Navier-Stokes, optimal control, semismooth Newton, squential quadratic programming

October 2003

Pseudospectral Collocation Methods for the Direct Transcription of Optimal Control Problems
Jesse A. Pietz

This thesis is concerned with the study of pseudospectral discretizations of optimal control problems governed by ordinary differential equations and with their application to the solution of the International Space Station (ISS) momentum dumping problem.

Pseudospectral methods are used to transcribe a given optimal control problem into a nonlinear programming problem. Adjoint estimates are presented and analyzed that provide approximations of the original adjoint variables using Lagrange multipliers corresponding to the discretized optimal control problem. These adjoint estimations are derived for a broad class of pseudospectral discretizations and generalize the previously known adjoint estimation procedure for the Legendre pseudospectral discretization. The error between the desired solution to the infinite dimensional optimal control problem and the solution computed using pseudospectral collocation and nonlinear programming is estimated for linear-quadratic optimal control problems. Numerical results are given for both linear-quadratic and nonlinear optimal control problems.

The Legendre pseudospectral method is applied to formulations of the ISS momentum dumping problem. Computed solutions are verified through simulations using adaptive higher order integration of the system dynamics.

Key words: Optimal control, pseudospectral methods, collocation, adjoint estimation, International Space Station

September 2003

Pattern Search Methods for Linearly Constrained Minimization in the Presence of Degeneracy
Olga A. Brezhneva and J.E. Dennis Jr.

This paper deals with generalized pattern search (GPS) algorithms for linearly constrained optimization. At each iteration, the GPS algorithm generates a set of directions that conforms to the geometry of any nearby linear constraints, and this set is used to define the poll set for that iteration. The contribution of this paper is to provide a detailed algorithm for constructing the set of directions at a current iterate whether or not the constraints are degenerate. The main difficulty in the degenerate case is in classifying constraints as redundant and nonredundant. We give a short survey of the main definitions and methods concerning redundancy and propose an approach, which may be useful for other active set algorithms, to identify the nonredundant constraints.

Key words: Pattern search, linearly constrained optimization, derivative-free optimization, degeneracy, redundancy, constraint classification

August 2003

Convergence of Polynomial Restart Krylov Methods for Eigenvalue Computation
Christopher A. Beattie, Mark Embree, and D. C. Sorensen

The convergence of Krylov subspace eigenvalue algorithms can be robustly measured by the angle the approximating Krylov space makes with a desired invariant subspace. This paper describes a new bound on this angle that handles the complexities introduced by non-Hermitian matrices, yet has a simpler derivation than similar previous bounds. The new bound reveals that ill-conditioning of the desired eigenvalues has little impact on convergence, while instability of unwanted eigenvalues plays an essential role. Practical computations usually require the approximating Krylov space to be restarted for efficiency, whereby the starting vector that generates the subspace is improved via a polynomial filter. Such filters dynamically steer a low-dimensional Krylov space toward a desired invariant subspace. We address the design of these filters, and illustrate with examples the subtleties involved in restarting non-Hermitian iterations.

Key words: Krylov subspace methods, invariant subspaces, Arnoldi convergence, Lanczos convergence, pseudospectra

August 2003

Client-Server Component Architecture for Scientific Computing
Hala N. Dajani

In a Distributed Computing Environment software components dispersed on a variety of computer platforms communicate transparently with each other to emulate a single computer platform. One distributed component framework model consists of two autonomous processes: the client and the server. The client-server model implemented in an object-oriented language shields low level platform complexities from the user and allows coupling of prefabricated components. These components must have a means of interfacing with each other in a distributed environment. To accommodate this need, while maintaining high performance, we propose a low level socket communication core. We employ the proxy design pattern and introduce new C++ classes to dynamically extend object behavior to a distributed environment. These classes also serve as component interfaces. Here, we describe general guidelines for partitioning objects into client and server components.

June 2003

Fixed-Polynomial Approximate Spectral Transformations for Preconditioning the Eigenvalue Problem
Heidi Krista Thornquist

Arnoldi's method is often used to compute a few eigenvalues and eigenvectors of large, sparse matrices. When the eigenvalues of interest are not dominant or well-separated, this method may suffer from slow convergence. Spectral transformations are a common acceleration technique that address this issue by introducing a modified eigenvalue problem that is easier to solve than the original. This modified problem accentuates the eigenvalues of interest, but requires solving a linear system, which is computationally expensive for large-scale eigenvalue problems.

This thesis shows how this expense can be reduced through a preconditioning scheme that uses a fixed-polynomial operator to approximate the spectral transformation. Implementation details and accuracy heuristics for employing a fixed-polynomial operator with Arnoldi's method are discussed. The computational results presented indicate that this preconditioning scheme is a promising approach for solving large-scale eigenvalue problems. Furthermore, this approach extends the domain of applications for current Arnoldi-based software. Future research directions include development of convergence theory, accuracy bounds for computed eigenpairs, and alternative constructions of the fixed-polynomial operator.

This work was supported in whole or in part by the Los Alamos National Laboratory Computer Science Institute (LACSI) through LANL contract number 03891-001-99-49, as part of the prime contract (W-7405-ENG-36) between the Department of Energy and the Regents of the University of California.

Key words: Large eigenvalue problems, Arnoldi's method, spectral transformations, eigenvalue preconditioning

June 2003

Computational Modeling of Internal Surfaces in Austenite-Martensite System
Luis A. Melara

In this work, we present a new computational method based on a nonconforming domain decomposition technique for modeling of phase transitions. Phase transitions are the result of thermal or mechanical loading in ferromagnetic materials or shape memory materials. Modeling of phase transitions is important because it can help to predict or control the behavior of these materials. This thesis will focus on phase transitions characterized by two directions of magnetization in the case of ferromagnets and two variants of Martensite in the case of shape memory materials. In both types of materials, branching occurs near an internal surface which is characterized by complex microstructures. These microstructures occur at a minimum energy state. The new computational method simulates the branching behavior of these microstructures near an internal surface. We approximate the microstructures via energy minimization. We minimize the total stored energy stored in vicinity of internal surface with the minimizing function representing the microstructures. We compare the numerical results obtained by the new technique with those obtained by a more standard technique, one not incorporating nonconforming domain decomposition. Furthermore, we verify the various energy scaling laws used to predict the total stored energy near an internal surface. Among these laws, we verify the local-in-y scaling property which has been conjectured but not proven.

Key words: Shape Memory Alloys, Phase Transitions, Finite Element Methods, Domain Decomposition Methods

June 2003

The Effect of Stabilization in Finite Element Methods for the Optimal Boundary Control of the Oseen Equations
Feby Abraham, Marek Behr, and Matthias Heinkenschloss

We study the effect of the Galerkin/Least-Squares (GLS) stabilization on the finite element discretization of optimal control problems governed by the linear Oseen equations. Control is applied in the form of suction or blowing on part of the boundary. Two ways of including the GLS stabilization into the discretization of the optimal control problem are discussed. In one case the optimal control problem is first discretized and the resulting finite dimensional problem is then solved. In the other case, the optimality contitions are first formulated on the differential equation level and are then discretized. Both approaches lead to different discrete adjoint equations and, depending on the choice of the stabilization parameters and grid size, may significantly affect the computed control. The effect of the order in which the discretization is applied and the choice of the stabilization parameters are illustrated using two test problems. The cause of the differences in the computed controls are explored numerically. Diagnostics are introduced that may guide the selection of sensible stabilization parameters.

Key words: optimal boundary control, stabilized finite element methods, Oseen equations, solution accuracy

May 2003

A Nonlinear Thermodynamic Model for Phase Transitions in Shape Memory Alloy Wires
Daniel R. Reynolds

Through a mathematical and computational model of the physical behavior of shape memory alloy wires, this study shows that localized heating and cooling of such materials provides an effective means of damping vibrational energy. The thermally induced pseudo-elastic behavior of a shape memory wire is modeled using a continuum thermodynamic description based on an improved Landau-Devonshire potential. Our construction of the potential function allows the model to account for particular alloys as well as the general solid-state phase transformation, improving over traditional potentials that idealize many of the material properties or focus only on individual processes. The material's thermodynamic response is modeled using a nonlinear conservation of momentum and a nonlinear heat equation. The heat equation introduces an inhomogeneous version of the Fourier heat flux, thereby describing the discontinuous heat flow associated with shape memory materials more thoroughly than standard, continuous heat dissipation mechanisms do. This continuum thermodynamic model is then solved computationally to determine the resulting state of the wire in time. Continuous time Galerkin methods and affine finite elements treat the temporal and spatial discretizations of the model, respectively. Traditional methods for solution of the resulting finite-dimensional, nonlinear, nonconvex system of equations must introduce a significant artificial dissipation to achieve existence of solutions. The solution of the discrete system here uses a novel combination of the damped Newton method and a homotopy method for minimizing the artificial dissipation. This combination, inspired by the well-known Method of Vanishing Viscosity for the solution of scalar hyperbolic conservation laws, reduces the artificial dissipation errors introduced by traditional approaches for such nonlinear, nonconvex thermomechanical models. Computational tests show that the proposed model successfully describes the relevant physical processes inherent in shape memory alloy behavior. Further computational experiments then confirm that up to 80% of an initial shock of vibrational energy can be eliminated at the onset of a thermally-induced phase transformation.

Key words: nonlinear partial differential equations, phase transitions, shape memory alloys, thermodynamics modeling

May 2003

On the Equivalence Between a Commonly Used Correlation Coefficient and a Least Squares Function
D.C. Jamrog, G.N. Philips, Jr., and Y. Zhang

Many objective functions have been proposed in X-ray crystallography to solve the molecular replacement (MR) problem and other optimization problems. In this paper, we establish the equivalence between optimizing two target functions: a commonly used correlation coefficient and a least squares function. This equivalence may be in neighborhoods about the global optima or the entire MR variable space depending on whether the average values of the observed and calculated data are subtracted from observed and calculated data. In addition, we also present an argument that the correlation coefficient between structure factor magnitudes is likely to perform better than the correlation coefficient between intensities. This was confirmed by the MR program SOMoRe, especially when low-resolution data were used.

Key words: molecular replacement problem, X-ray crystallography, global optimization, nonlinear optimization, least squares function, correlation coefficient

January 2003 (revised October 2003)

Graceful Graphs and Graceful Labelings: Two Mathematical Programming Formulations and Some Other New Results
Timothy A. Redl

Given a graph G consisting of vertices and edges, a vertex labeling of G is an assignment f of labels to the vertices of G that produces for each edge xy a label depending on the vertex labels f(x) and f(y). A vertex labeling f is called a graceful labeling of a graph G with e edges if f is an injection from the vertices of G to the set {0, 1, ..., e} such that when each edge xy is assigned the label |f(x) - f(y)| the resulting edge labels are distinct. A graph G is called graceful if there exists a graceful labeling of G. In this paper we present two mathematical programming formulations of the graceful labeling problem (first as an integer programming problem, second as a constraint programming problem), along with some new results on the gracefulness of three classes of graphs: generalized graphs, double cones, and a particular class of product graphs.

Key words: graceful labeling; graceful graph; generalized Petersen graph; double cone; integer programming; constraint programming

January 2003

Go to 2002 reports