TECHNICAL REPORTS: (2007)
A MADS Algorithm with a Progressive Barrier for Derivative-Free Nonlinear Programming
Charles Audet & J.E. Dennis Jr.
We propose a new algorithm for general constrained derivative-free optimization. As in most methods, constraint violations are aggregated into a single constraint violation function. As in filter methods, a threshold, or barrier, is imposed on the constraint violation function, and any trial point whose constraint violation function value exceeds this threshold is discarded from consideration. In the new algorithm, unlike the filter method, the amount of constraint violation subject to the barrier is progressively decreased as the algorithm evolves.
Using the Clarke nonsmooth calculus, we prove Clarke stationarity of the sequences of feasible and infeasible trial points. The new method is effective on two academic test problems with up to 50 variables, which were problematic for our GPS filter method. We also test on a chemical engineering problem. The proposed method generally outperforms our LTMADS in the case where no feasible initial points are known, and it does as well when feasible points are known.
Key Words: Mesh adaptive direct search algorithm, filter algorithm, barrier approach, constrained optimization, nonlinear programming.
December 2007
Best Symmetric Low Rank Approximation Via the Symmetry Preserving Singular Value Decomposition
Mili I. Shah & Danny C. Sorensen
The symmetry preserving singular value decomposition (SPSVD) produces the best symmetric (low rank) approximation to a set of data. These symmetric approximations are characterized via an invariance under the action of a symmetry group on the set of data. The symmetry groups of interest consist of all the non-spherical symmetry groups in three dimensions. This set includes the rotational, reflectional, dihedral, and inversion symmetry groups. In order to calculate the best symmetric (low rank) approximation, the symmetry of the data set must be determined. Therefore, matrix representations for each of the non-spherical symmetry groups have been formulated. These new matrix representations lead directly to a novel reweighting iterative method to determine the symmetry of a given data set by solving a series of minimization problems. Once the symmetry of the data set is found, the best symmetric (low rank) approximation in the Frobenius norm and matrix 2-norm can be established by using the SPSVD.
Index Terms: Singular value decomposition, symmetry, symmetry operation, symmetry constraints, rotation, reflection, dihedral, inversion, large scale, protein dynamics.
December 2007
Comparing Problem Formulation for Coupled Sets of Component
S.F. Arroyo, E.J. Cramer, P.D. Frank, & J.E. Dennis, Jr.
In this paper several formulations and comparative test results are presented for problems involving the general paradigm of coupled sets of components. This paradigm is general enough to include systems of systems (SoS) and multidisciplinary design optimization (MDO). It is assumed that these systems involve a (potentially inactive) coordinating component, or "Central Authority" and one or more, potentially interacting, subordinate components. The formulations differ in the amount of control given to the central authority versus the autonomy granted to the subordinate components. Comparative test results are given for several of the formulations on a NASA-generated, public domain, aircraft conceptual design problem.
Key Words: System of systems, multidisciplinary design optimization, distributed optimization, optimization formulations.
November 2007
Parallel Space Decomposition of the Mesh Adaptive Direct Search Algorithm
Charles Audet, J.E. Dennis Jr., & Sebastien Le Digabel
This paper describes a Parallel Space Decomposition (PSD) technique for the Mesh Adaptive Direct Search (MADS) algorithm. MADS extends Generalized Pattern Search for constrained nonsmooth optimization problems. The objective here is to solve larger problems more efficiently. The new method (PSD-MADS) is an asynchronous parallel algorithm in which the processes solve problems over subsets of variables. The convergence analysis based on the Clarke calculus is essentially the same as for the MADS algorithm. A practical implementation is described and some numerical results on problems with up to 500 variables illustrate advantages and limitations of PSD-MADS.
Key Words: Parallel Space Decomposition, Mesh Adaptive Direct Search, Asynchronous parallel algorithm, Nonsmooth optimization, Convergence analysis.
November 2007
Domain Decomposition and Model Reduction of Systems with Local Nonlinearities
K. Sun, R. Glowinski, M. Heinkenschloss, & D. C. Sorensen
The goal of this paper is to combine balanced truncation model reduction and domain decomposition to derive reduced order models with guaranteed error bounds for systems of discretized partial differential equations (PDEs) with a spatially localized nonlinearities. Domain decomposition techniques are used to divide the problem into linear subproblems and small nonlinear subproblems. Balanced truncation is applied to the linear subproblems with inputs and outputs determined by the original in- and outputs as well as the interface conditions between the subproblems. The potential of this approach is demonstrated for a model problem.
Key Words: Model reduction, domain decomposition, Burgers equations
November 2007
Bregman Iterative Algorithms for l1-Minimization with Applications to Compressed Sensing
Wotao Yin, Stanley Osher, Donald Goldfarb, & Jerome Darbon
We propose simple and extremely efficient methods for solving the Basis Pursuit problem
September 2007
A Study on Conditions for Sparse Solution Recovery in Compressive Sensing
Anatoly Eydelzon
It is well-known by now that under suitable conditions L1 minimization can recover sparse solutions to under-determined linear systems of equations. More precisely, by solving the convex optimization problem min{||x||1 : Αx = b}, where A is an m by n measurement matrix with m < n, one can obtain the sparsest solution x* to Ax = b provided that the measurement matrix A has certain properties and the sparsity level k of x is suffciently small. This fact has led to active research in the area of compressive sensing and other applications.
The central question for this problem is the following. Given a type of measurements, a signal's length n and sparsity level k, what is the minimum measurement size m that ensures recovery? Or equivalently, given a type of measurements, a signal length n and a measurement size m, what is the maximum recoverable sparsity level k?
The above fundamental question has been answered, with varying degrees of precision, by a number of researchers for a number of different random or semi-random measurement matrices. However, all the existing results still involve unknown constants of some kind and thus are unable to provide precise answers to specific situations. For example, let A be an m by n partial DCT matrix with n = 107 and m = 5 x 105 (n/m = 20). Can we provide a reasonably good estimate on the maximum recoverable sparsity k?
In this research, we attempt to provide a more precise answer to the central question raised above. By studying new suffcient conditions for exact recovery of sparse solutions, we propose a new technique to estimate recoverable sparsity for different kinds of deterministic, random and semi-random matrices. We will present empirical evidence to show the practical success of our approach, though further research is still needed to formally establish its effectiveness.
August 2007 (Updated on May 2008)
Passivity Preserving Model Reduction via Interpolation of Spectral Zeros: Selection Criteria and Implementation
Hung Dinh Nong
This thesis presents spectral zero selection criteria for a rigorous theory on passivity preserving model reduction via interpolation of spectral zeros. For linear time invariant systems in circuit simulation, passivity implies stability, and hence need be preserved during model reduction. Sorensen [19] presents an algorithm that constructs passive reduced models which are much less expensive to simulate than the originals. The algorithm transforms the model reduction problem into a highly-structured generalized eigenvalue problem whose generalized eigenvalues are the spectral zeros of the original model. The reduced models constructed by interpolating the spectral zeros are passive and hence stable. This thesis first introduces spectral zero selection criteria for which the reduced model resulting from interpolation is a good approximation to the original. The physical interpretation for the criteria is presented. Second, by modifying the selection criteria, an algorithm of two-stage reduction is formulated to handle large-scale systems.
September 2007
A New Alternating Minimization Algorithm for Total Variation Image Reconstruction
Yilun Wang, Junfeng Yang, Wotao Yin, & Yin Zhang
We propose, analyze and test an alternating minimization algorithm for recovering images from blurry and noisy observa- tions with total variation (TV) regularization. This algorithm arises from a new half-quadratic model applicable to not only the anisotropic but also isotropic forms of total variation discretizations. The per-iteration computational complexity of the algorithm is three Fast Fourier Transforms (FFTs). We establish strong convergence properties for the algorithm including finite convergence for some variables and relatively fast exponential (or q-linear in optimization terminology) convergence for the others. Furthermore, we propose a continuation scheme to accelerate the practical convergence of the algorithm. Extensive numerical results show that our algorithm performs favorably in comparison to several state-of-the-art algorithms. In particular, it runs orders of magnitude faster than the Lagged Diffusivity algorithm for total-variation-based deblurring. Some extensions of our algorithm are also discussed.
June 2007 (Revised on May 2008)
Parametric Maximum Flow Algorithms for Fast Total Variation Minimization
Donald Goldfarb & Wotao Yin
This report studies the global minimization of discretized total variation (TV) energies with an L1 or L2 fidelity term using parametric maximum flow algorithms. The TV-L2 model, also known as the Rudin-Osher-Fatemi (ROF) model is suitable for restoring images contaminated by Gaussian noise, while the TV-L1 model is able to remove impulsive noise from grey-scale images, and perform multi scale decompositions of them. For large-scale applications such as those in medical image (pre)processing, we propose here fast and memory-efficient algorithms, based on a parametric maximum flow algorithm and the minimum s-t cut representation of TV-based energy functions. Preliminary numerical results on large-scale two-dimensional CT and three-dimensional Brain MRI images that illustrate the effectiveness of our approaches are presented.
Key words: Maximum flow, minimum cut, graph cut, parametric maximum flow, total variation, MRI.
May 2007
Optimal Reorientation of Spacecraft Using Only Control Moment Gyroscopes
Sagar A. Bhatt
Spacecraft reorientation can require propellant even when using gyroscopes since these have momentum saturation limits at which control is lost until thrusters are fired to desaturate them. To eliminate this need and thereby reduce cost, this work seeks trajectories that avoid saturation altogether by taking advantage of known disturbance torques. This concept is formulated as an optimal control problem and a direct transcription method is applied to obtain numerical solutions. Unlike recent related work on attitude maneuvers and momentum desaturation using only gyroscopes, this thesis allows the full rotational state (attitude, rate, and momentum) at the start and end of the maneuver to be specified. This thesis establishes the viability of this technique, which can potentially extend the operational lifetime of any gyroscope-equipped spacecraft, by successfully demonstrating it in a flight test in which the International Space Station was rotated 90 deg without propellant.
May 2007
A Fixed-Point Continuation Method for L_1-Regularization with Application to Compressed Sensing
Elaine T. Hale, Wotao Yin, and Yin Zhang
We consider solving minimization problems with L_1-regularization:
min ||x||_1 + μ f(x)
particularly for f(x) = (1/2)||Ax-b||^2, where A is m by n and m < n.
Our goal is to construct efficient and robust algorithms for solving
large-scale problems with dense data, and our approach is based on
two powerful algorithmic ideas: operator-splitting and continuation.
This paper establishes q-linear convergence rates for our algorithm
applied to problems with f(x) convex, but not necessarily strictly
convex. We present numerical results for several types of compressed
sensing problems, and show that our algorithm compares favorably with
three state-of-the-art algorithms when applied to large-scale problems
with noisy data.
May 2007
A Symmetry Preserving Singular Value Decomposition
Mili Shah
This thesis concentrates on the development, analysis, implementation, and application of a symmetry preserving singular value decomposition (SPSVD). This new factorization enhances the singular value decomposition (SVD) — a powerful method for calculating a low rank approximation to a large data set — by producing the best symmetric low rank approximation to a matrix with respect to the Frobenius norm and matrix 2-norm.
Calculating an SPSVD is a two-step process. In the first step, a matrix representation for the symmetry of a given data set must be determined. This process is presented as a novel iterative reweighting method: a scheme which is rapidly convergent in practice and seems to be extremely effective in ignoring outliers of the data. In the second step, the best approximation that maintains the symmetry calculated from the first step is computed. This approximation is designated the SPSVD of the data set.
In many situations, the SPSVD needs efficient updating. For instance, if new data is given, then the symmetry of the set may change and an alternative matrix representation has to be formed. A modification in the matrix representation also alters the SPSVD. Therefore, proficient methods to address each of these issues are developed in this thesis.
This thesis applies the SPSVD to molecular dynamic (MD) simulations of proteins and to face analysis. Symmetric motions of a molecule may be lost when the SVD is applied to MD trajectories of proteins. This loss is corrected by implementing the SPSVD to create major modes of motion that best describe the symmetric movements of the protein. Moreover, the SPSVD may reduce the noise that often occurs on the side chains of molecules. In face analysis, the SVD is regularly used for compression. Because faces are nearly symmetric, applying the SPSVD to faces creates a more efficient compression. This efficiency is a result of having to store only half the picture for the SPSVD. Therefore, it is apparent that the SPSVD is an effective method for calculating a symmetric low rank approximation for a set of data.
April 2007
Migration Velocity Analysis and Waveform Inversion
William W. Symes
Waveform (output least squares) inversion of seismic reflection data can reconstruct remarkably detailed models of subsurface structure, and take into account essentially any physics of seismic wave propagation that can be modeled. However the waveform inversion objective has many spurious local minima, hence convergence of descent methods (mandatory because of problem size) to useful Earth models requires accurate initial estimates of long-scale velocity structure. Migration velocity analysis, on the other hand, is based on the Born approximation but is capable of correcting substantially erroneous in itial velocities. Appropriate choice of objective (differential semblance) turns migrat ion velocity analysis into an optimization problem, for which Newton-like methods exhib it little tendency to stagnate at nonglobal minima. The extended modeling concept links these two apparently unrelated approaches to estimation of Earth structure: from this point of view, migration velocity analysis is a solution method for the linearized (single scattering, Born) waveform inversion problem. Extended modeling also provides a basis for a nonlinear generalization of migration velocity analysis. Preliminary numerical evidence suggests that this new approach to nonlinear waveform inversion may combine the global convergence of velocity analysis with the physical fidelity of least squares.
March 2007
A Time-Stepping Library For Simulation-Driven Optimization
William W. Symes
The Timestepping Simulation for Optimization ("TSOpt") library provides an interface for time-stepping simulation. It packages a simulator togehter with its derivatives ("sensitivities") and adjoint derivaties with respect to simulation parameters, and uses the aggregate to define a Rice Vector Library Operator subclass.
March 2007
Quantitative Object Reconstruction using Abel Transform X-Ray Tomography and Mixed Variable Optimization
Mark A. Abramson, Thomas J. Asaki, J. E. Dennis, Jr., Kevin R. O'Reilly, & Rachael L. Pingel
This paper introduces a new approach to the problem of quantitatively reconstructing cylindrically symmetric objects from radiograph data obtained via x-ray tomography. Specifically, a mixed variable programming (MVP) problem is formulated, in which the variables of interest are the number and types of materials and the thickness of each concentric layer. The objective function is a measure of distance between one-dimensional radiograph data and a material property vector operated on by a forward projection based on the Abel transform. The mixed variable pattern search (MVPS) algorithm for linearly constrained MVP problems is applied to the problem by means of the NOMADm MATLAB® software package. Numerical results are presented for several test configurations and show that, while there are difficulties yet to be overcome, the method appears to be very promising for solving this class of problems in practice.
Key words: Mixed variable optimization, derivative-free optimization, mesh adaptive direct search (MADS) algorithms, x-ray tomography, Abel transforms
February 2007 (Revised on June 2008)
Balanced Truncation Model Reduction for a Class of Descriptor Systems with Application to the Oseen Equations
Matthias Heinkenschloss, Danny C. Sorensen, & Kai Sun
We discuss the computation of balanced truncation model reduction for a class of descriptor systems which includes the semidiscrete Oseen equations with time independent advection. The purpose of this paper is twofold. First, we show how to apply standard balanced truncation model reduction techniques, which apply to dynamical systems given by ordinary differential equations, to this class of descriptor systems. This is accomplished by eliminating the algebraic equation using a projection. The second objective of this paper is to demonstrate how the important class of ADI/Smith-type methods for the approximate computation of reduced order models using balanced truncation can be applied without explicitly computing the afore mentioned projection. Instead, we utilize the solution of saddle point problems. We demonstrate the effectiveness of the technique in the computation of reduced order models for semidiscrete Oseen equations.
Key words: Model reduction, control, descriptor systems, differential algebraic equations, Oseen equations.
January 2007
A Comparison of Three Total Variation Based Texture Extraction Models
Wotao Yin, Donald Goldfarb, & Stanley Osher
This paper qualitatively compares three recently proposed models for signal/image texture extraction based on total variation minimization:the Meyer, Vese-Osher, and TV-L1 models. We formulate discrete versions of these models as second-order cone programs (SOCPs) which can be solved efficiently by interior-point methods. Our experiments with these models on 1D oscillating signals and 2D images reveal their differences: the Meyer model tends to extract oscillation patterns in the input, the TV-L1 model performs a strict multiscale decomposition, and the Vese-Osher model has properties falling in between the other two models.
Key words: Image decomposition, texture extraction, feature selection, total variation, variational imaging, second-order cone programming, interior-point method.
January 2007