A Cubically Convergent Method for Locating a Nearby Vertex in Linear Programming

Given an approximate solution sufficiently close to a nondegenerate basic feasible solution x* of a linear program, we show how to generate a sequence {p^k} that converges to the 0-1 vector sign (x*) at a Q-cubic rate. This extremely fast convergence enables us to determine, with a high degree of certainty, which variables will be zero and which will be nonzero at optimality and then construct x* from this information.

December 1989

[J. Optim. Theory Appl. 67 (1990), no. 2, 217-225.]

Solving Linear Programs with Two Processors

A linear programming problem can be solved in parallel using two processors. One processor performs iterations of the main algorithm, while the other processor continuously refactorizes the basis matrix. Using this method we have been able to solve linear programs in as little as 73% of the time needed with one processor.

November 1989

A Trace Theorem for Solutions of Linear Partial Differential Equations

The main goal of this work is to determine circumstances under which the trace of the solution of a linear partial differential equation is as smooth as the solution itself. Clearly, if the linear partial differential equation is strictly hyperbolic with smooth coefficients, standard energy estimates will yield the fact that the solution along any spacelike trace is as smooth as itself locally, provided a sufficiently smooth right-hand side. Unfortunately, for more general equations or even a strictly hyperbolic differential equation but this time along a nonspacelike trace, the same idea will not work, essentially because one does not know how to apply energy estimates to a nonhyperbolic problem directly. In this paper, we shall investigate the trace regularities of solutions to linear P.D.E. Our result shows that the difficulties discussed above may be cured by imposing some additional microlocal smoothness.

October 1989

[Math. Methods Appl. Sci. 14 (1991), no. 8, 553-562.]

Plane-Wave Detection: A Nonlinearly Ill-Posed Inverse Problem

One inverse problem exhibiting a severe case of nonlinear ill-posedness is the velocity estimation problem of reflection seismology. For an extensive discussion of this rather specialized problem, with many references, we direct the reader to the monograph by Santosa and the author (Santosa and Symes, 1989). In this paper we will mostly discuss instead a much simpler problem, the plane wave detection problem, which shares the essential mathematical features of the velocity estimation problem without carrying the conceptual baggage of reflection seismology. In the final section we will describe briefly a version of velocity estimation, to make plausible this sharing of features.

A deep understanding of nonlinear ill-posedness and related matters is to be had through G. Chavent's theory of quasiconvex sets in Hilbert space (Chavent, 1980). The plane-wave detection problem is treated from the point of view of Chavent's theory in Symes (1989). In the present paper we describe just the basic properties of a simple best-fit formulation of the detection problem (Section 2), and then indicate how the cost function can be convexified and smoothed (Section 3). The fourth section begins by describing the acoustic model of reflection seismology, then presents several simplifications and approximations leading to a problem recognizably similar to plane wave detection. We give a brief discussion of this problem, referring the interested reader to other papers for more information.

September 1989

[In Inverse Problems and Imaging (Glasgow, 1988), 200-220, Longman Sci. Tech., Harlow, 1991.]

Propagation of Singularities and Some Inverse Problems in Wave Propagation

We review a number of results relating the propagation of singularities for hyperbolic partial differential equations - i.e. the persistence, or nonlocalization, of wave motion - with well-posedness for some inverse problems of reflection type, such as arise for instance in seismology and ultrasonics. By far the most complete information is available for layered problems. We show how a simple but refined propagation-of-singularities theorem, with estimates, yields important functional properties of the model-data relationship for such problems, including regularity in various useful coefficient classes, separation of scales, .... We explain the essential role of travel time in the study of these problems, and show how its function may be generalized to multidimensional (i.e. non-layered) problems.

September 1989

[In Random Media and Composites (Leesburg, VA, 1988), 67-88, SIAM, Philadelphia, PA, 1989.]

Mixed Finite Element Methods for Time Dependent Problems: Application to Control

The main goal of this paper is to discuss mixed variational formulations for time dependent problems such as initial and boundary value problems for the heat and wave equations in a bounded domain Omega of R^N(N>=1). Then we shall use these formulations to derive mixed finite element approximations of the heat and wave equations. Finally, an application to an exact boundary controllability problem for the wave equation will be presented together with some numerical results. The techniques and application briefly considered here will be discussed with more details in a forthcoming paper.

September 1989

[In Finite Elements in Fluids, Vol. 8 (Huntsville, AL, 1989), 119-136, Hemisphere, Washington, DC, 1992.]

Using General Separation Algorithms to Solve Linear Integer Programming Problems

Cutting plane methods have recently reemerged as an important technique for solving integer programs. Fundamental to the implementation of these methods is the ability to solve the separation problem - the problem of finding a hyperplane that separates a given point from the convex hull of feasible integer points. This paper outlines a practical algorithm for solving the separation problem that uses the solution of optimization problems rather than explicit information about the convex hull of feasible integer points. Computational results are presented for an application of the algorithm.

August 1989

Velocity Inversion by Coherency Optimization

We introduce an approach to velocity and reflectivity estimation based on optimizing the coherence of multiple shot-gather inversions of reflection seismograms. The resulting algorithm appears to avoid the severe convergence difficulties reported for output (nonlinear) least-squares inversion. We describe in detail an algorithm appropriate for the layered acoustic model, using the convolutional model of the plane-wave (p-tau) seismogram. We give theoretical and numerical evidence with both synthetic and field data sets that coherency optimization, as defined here, yields stable and reasonably accurate estimates of both velocity trend and reflectivity, by exploiting reflection phase moveout and amplitudes in a computationally efficient way. The approach may be modified to apply to determination of elastic models and source parameters as well as to determination of laterally heterogeneous acoustic models.

August 1989

A Quadratic Minimization Problem on Subsets of Symmetric Positive Semidefinite Matrices

In this paper we deal with a family of constrained optimization problems in which the objective function, which is the same for each problem in the family, is quadratic and strictly convex and is defined for any matrix of order n. The difference among problems in this family is in the feasible sets. These feasible sets are the sets of symmetric positive semidefinite matrices with rank less than or equal to k, so k is the parameter of the family. The first observation is that these feasible sets are closed but not convex, except for k-n which satisfies both properties.

The central idea contained in our approach is to transform each problem of the family into an unconstrained optimization problem using a function that takes R^{n × k} onto the feasible sets. This function allows us to consider an equivalent objective function on R^{n × k}.

August 1989

More Estimates for Eigenvalues and Singular Values

In this paper we follow the ideas given in Tarazaga, Estimates Eigenvalue for Symmetric Matrices, and we obtain new results for symmetric matrices using as information only the trace and the Frobenius norm which we will denote by tr ( ) and | |F respectively. Second, we generalize some properties for non-symmetric matrices. In both cases the identity matrix plays a very important role and the angle between any matrix and the identity is a relevant parameter.

August 1989

[Linear Algebra Appl. 149 (1991), 97-110.]

A Unified Approach to Global Convergence of Trust Region Methods for Nonsmooth Optimization

This paper investigates the global convergence of trust region (TR) methods for solving nonsmooth minimization problems. For a class of nonsmooth objective functions called regular functions, conditions are found on the TR local models that imply three fundamental convergence properties. These conditions are shown to be satisfied by Fletcher's TR method for solving constrained optimization problems, Powell for solving nonlinear fitting problems, Zhang, Kim & Lasdon's successive linear programming method for solving constrained problems, Duff, Nocedal & Reid's TR method for solving systems of nonlinear equations, and El Hallabi & Tapia's TR method for solving systems of nonlinear equations. Thus our results can be viewed as a unified convergence theory for TR methods for nonsmooth problems.

July 1989 (revised April 1990 and July 1993)

[Math. Programming 68 (1995), no. 3, Ser. A, 319-346.]

An SQP Augmented Lagrangian BFGS Algorithm for Constrained Optimization

In this research we present an effective algorithm for nonlinearly constrained optimization using the structured augmented Lagrangian secant update recently proposed by Tapia. The algorithm is globally defined, and uses a new and reliable method for choosing the Lagrangian augmentation parameter that does not require prior knowledge of the true Hessian. We present considerable numerical experimentation with this algorithm, both embedded in a merit-function line search SQP framework, and without line search. We compare the algorithm to the widely-used damped BFGS secant update of Powell, which, like ours, was designed to circumvent the lack of positive definiteness in the Hessian of the Lagrangian. We also establish the powerful and surprising convergence rate result, that when our algorithm converges it converges R-superlinearly. An immediate corollary is a new result in unconstrained optimization: whenever the unconstrained BFGS secant method converges, it does so Q-superlinearly. Our study has led us to the conclusion that when properly implemented Tapia's structured augmented Lagrangian BFGS secant update offers significant theoretical and tangible numerical advantages over Powell's damped BFGS update.

May 1989 (revised November 1990)

[SIAM J. Optim. 2 (1992), no. 2, 210-241.]

The Effect of Caustics in Acoustic Inverse Scattering Experiments

Most inversion techniques described in the literature rely on the validity of ray tracing, which breaks down in the presence of caustics. The linearized acoustic inverse problem with constant reference velocity is analyzed in order to quantify the effects of a caustic in a probing wavefront on the scattered signal.

When the sound velocity is perturbed by a localized, unidirectional, high frequency inhomogeneity, the surprising result obtained is that the energy in the scattered field is spread out if the perturbation is located on the caustic. This spreading of energy allows the construction of an oscillatory integral representation of the scattered field, which has the same form, whether or not an incident caustic is present. On the other hand, a sequence of localized high frequency sound velocity perturbations is constructed such that the size of the scattered signal relative to the size of the inhomogeneity becomes arbitrarily large as the support of the perturbation approaches the caustic.

In regions where there are no caustics, a general inverse operator is found for smoothly varying reference velocities. This operator is shown to be equivalent to an inverse operator constructed by Beylkin (1985).

May 1989

Convergence Rates for the Variable, the Multiplier, and the Pair in SQP Methods

In this work we consider relationships among the convergence rates for the variable x, for the multiplier lambda and for the pair (x,lambda) in SQP methods for equality constrained optimization. We show that if the convergence in (x,lambda) is q-superlinear, then the convergence in x is at least two-step q-superlinear. Moreover, if the convergence in (x,lambda) and also in x is q-superlinear, then the convergence in lambda is either q-superlinear or q-sublinear with unbounded q1 factor. We extend the Boggs-Tolle-Wang characterization of q-superlinear convergence in x to the case where it is known that the convergence in (x,lambda) is q-superlinear. Finally we present a condition that guarantees q-superlinear convergence in x, lambda and (x,lambda) for an SQP method.

January 1989 (revised June 1989)

An Optimal Basis Identification Technique for Interior-Point Linear Programming Algorithms

This work concerns a method for identifying an optimal basis for linear programming problems in the setting of interior point methods. To each iterate x^k generated by a primal interior point algorithm, say, we associate an indicator vector q^k with the property that if x^k converges to a nondegenerate vertex x*, then q^k converges to the 0-1 vector sign (x*). More interestingly, we show that the convergence of q^k is quadratically faster than that of x^k in the sense that q^k-q* = O (x^k-x*²). This clear-cut separation and rapid convergence allow one to infer at an intermediate stage of the iterative process which variables will be zero at optimality and which will not. We also show that under suitable assumptions this method is applicable to dual as well as primal-dual algorithms and can be extended to handle certain types of degeneracy. Numerical examples are included to corroborate the convergence properties of the indicators. The practical limitations of the indicator technique are also discussed.

April 1989 (revised September 1990)

Go to 1988 reports

Go to 1990 reports