An Algorithmic Characterization of Antimatroids

In an article entitled "Optimal sequencing of a single machine subject to precedence constraints," E.L. Lawler presented a now classical minmax result for job scheduling. In essence, Lawler's proof demonstrated that the properties of partially ordered sets were sufficient to solve the posed scheduling problem. These properties are, in fact, common to a more general class of combinatorial structures known as antimatroids, which have recently received considerable attention in the literature. It is demonstrated that the properties of antimatroids are not only sufficient but necessary to solve the scheduling problem posed by Lawler, thus yielding an algorithmic characterization of antimatroids. Examples of problems solvable by the general result are provided.

December 1987

Eigenvalue Estimates for Symmetric Matrices

Symmetric and symmetric positive definite matrices have been extensively studied, and there are good characterizations of these sets. We wish to use the setting that in R^{n × n}, the set of symmetric positive semidefinite matrices forms a cone with a very special structure; the identity matrix is the central direction and there exist certain kinds of symmetries around it. The position of each matrix in the cone depends strongly on its eigenvalues and consequently on its rank. We exploit this special structure.

December 1987

[Linear Algebra Appl. 135 (1990), 171-179.]

A Global Convergence Theory for Arbitrary Norm Trust Region Methods for Nonlinear Equations

(Replaced by TR93-41.)

November 1987 (Revised July 1989)

Time-Splitting for Advection-Dominated Parabolic Problems in One Space Variable

(Abstract not available)

November 1987

[Comm. Appl. Numer. Methods 4 (1988), no. 3, 413-423.]

A View of Unconstrained Optimization

Finding the unconstrained minimizer of a function of more than one variable is an important problem with many practical applications, including data fitting, engineering design, and process control. In addition, techniques for solving unconstrained optimization problems form the basis for most methods for solving constrained optimization problems. This paper surveys the state of the art for solving unconstrained optimization problems and the closely related problem of solving systems of nonlinear equations. First we briefly give some mathematical background. Then we discuss Newton's method, the fundamental method underlying most approaches to these problems, as well as the inexact Newton method. The two main practical deficiencies of Newton's method, the need for analytic derivatives and the possible failure to converge to the solution from poor starting points, are the key issues in unconstrained optimization and are addressed next. We discuss a variety of techniques for approximating derivatives, including finite difference approximations, secant methods for nonlinear equations and unconstrained optimization, and the extension of these techniques to solving large, sparse problems. Then we discuss the main methods used to ensure convergence from poor starting points, line search methods and trust region methods. Next we briefly discuss two rather different approaches to unconstrained optimization, the Nelder-Mead simplex method and conjugate direction methods. Finally we comment on some current research directions in the field, in the solution of large problems, the solution of data fitting problems, new secant methods, the solution of singular problems,

October 1987

[In Optimization, 1-72, North-Holland, Amsterdam, 1989.]

A Short Proof of the Truemper-Tseng Theorem on Max-Flow Min-Cut Matroids

Seymour has characterized the matroids satisfying the integral max-flow min-cut property with respect to a fixed element. Truemper and Tseng subsequently proved a decomposition theorem for this class, similar in spirit to Wagner's characterization of the regular (totally unimodular) matroids. The purpose of this paper is to give a short, self-contained exposition of the Truemper-Tseng result.

October 1987

[Linear Algebra Appl. 114/115 (1989), 277-29.]

Notes on Combinatorial Optimization

October 1987

Domain Decomposition Algorithms for Linear Hyperbolic Equations

The use of parallel computers for solving partial differential equations is important in areas such as fluid dynamics, reservoir simulation, and structural analysis, where many of the problems of interest cannot be solved without the use of supercomputers. One technique for applying parallel computers to the solution of these problems is known as domain decomposition where the domain of interest is subdivided into several smaller subdomains and the task of solving the partial differential equation on each subdomain problem is assigned to a different processor. The global solution is then synthesized from the solutions computed on the individual subdomains. Much of the current work in the application of domain decomposition techniques has been in the area of elliptic partial differential equations, with very little attention being given to hyperbolic equations. We propose to use the methods of domain decomposition for the solution of linear hyperbolic equations. The idea of using overlapping domains is introduced in the context of linear hyperbolic equations to develop a domain decomposition algorithm which is shown to be well suited for parallel processors. The issues of communication costs and load balancing are addressed and a simple strategy for assigning jobs to processors to achieve load balancing is presented.

August 1987

A Computational Note on Markov Decision Processes Without Discounting

The Markov decision process is treated in a variety of forms or cases: finite or infinite horizon, with or without discounting. The finite horizon cases and the case of infinite horizon with discounting have received considerable attention. In the infinite horizon case, with discounting, the problem either receives a linear programming treatment or is treated by the elegant and effective policy-iteration procedure by Ronald Howard. In the undiscounted case, however, a special form of this procedure is required, which detracts from the directness and elegance of the method. The difficulty comes in the step generally called the value-determination procedure. The equations used in this step are linearly dependent, so that the solution of the system of linear equations requires some adjustment. We propose a new computational procedure which avoids this difficulty and works directly with the average next-period gains and powers of the transition probability matrix. The fundamental computational tools are matrix multiplication and addition.

July 1987

A Parametric Study of Viscous Fingering in Miscible Displacement by Numerical Simulation

Numerical simulation is used to study the effects of several parameters on miscible viscous fingering. A miscible flood of a rectangular slab is simulated in two spatial dimensions. The parameters, obtained by the dedimensionalization of the governing equations, are the viscosity ratio, Peclet numbers associated with molecular diffusion, longitudinal dispersion and transverse dispersion and the aspect ratio of the slab. The effects of local permeability variations and the overall heterogeneity of the porous medium are also considered. A finite element modified method of characteristics is used for the solution of the concentration equation, combined with a mixed finite element method for the solution of the pressure equation. This scheme is essentially free of numerical dispersion.

The results suggest that the local permeability distribution near the entrance of the porous medium plays an important role in finger generation, while the permeability distribution downstream does not significantly affect fingering. The number of developing fingers and their growth rates depend strongly on the mobility ratio. The aspect ratio of the slab also influences significantly the number of fingers.

June 1987

[In Numerical Simulation in Oil Recovery (Minneapolis, Minn., 1986), 227-247, Springer, New York, 1988.]

Simultaneous Determination of Source Wavelet and Velocity Profile Using Impulsive Point-Source Reflections from a Layered Fluid

The determination of source signature is a major calibration problem in reflection seismology. This "deconvolution" problem is conventionally approached by way of statistical methods, by direct measurement, or by the location of a clean reflection in an otherwise quiet part of a reflection section. We show that a quasi-impulsive, isotropic point source may be recovered simultaneously with the velocity profile from reflection data over a layered fluid, in linear (perturbation) approximation. Our approach is completely deterministic, and does not depend on the presence of an isolated reflection in a quiet part of the section, as we illustrate with a numerical example. After describing the algorithm and a numerical implementation, we give a complete mathematical treatment, which shows that our estimates of source wavelet and velocity profile are stable in a certain sense. Because of this stability property we conjecture that our approach to simultaneous estimation of source and medium parameters actually applies to a much broader class of models than that treated here.

June, 1987

A Convergence Theory for the Structured BFGS Secant Method with an Application to Nonlinear Least Squares

In 1981, Dennis and Walker developed a convergence theory for structured secant methods which included the PSB and the DFP secant methods, but not the straightforward structured version of the BFGS secant method. Here we fill this gap in the theory by establishing a convergence theory for the structured BFGS secant method. A direct application of our new theory gives the first proof of local and q-superlinear convergence of the important structured BFGS secant method for the nonlinear least-squares problem which is used by Dennis, Gay and Welsh in the current version of the popular and successful NL2SOL code.

May 1987 (revised July 1988)

[J. Optim. Theory Appl. 61 (1989), no. 2, 161-178.]

Projected Newton for the Symmetric Eigenvalue Problem has Order 1+sqrt(2)

In their study of the classical inverse iteration algorithm, Peters and Wilkinson considered the closely related algorithm that consists of applying Newton's method, followed by a 2-norm normalization, to the nonlinear system of equations consisting of the eigenvalue-eigenvector equation and an equation requiring the eigenvector have the square of its 2-norm equal to one. They argue that in practice the infinity-norm is easier to work with, and they therefore replace the 2-norm normalization equation with a linear equation requiring that a particular component of the eigenvector be equal to one (effectively an infinity-norm normalization). Next, they observe that, because of the linearity of the normalization equation, the normalization step is automatically satisfied; the algorithm thus reduces to Newton's method and quadratic convergence follows from standard theory. Peters and Wilkinson choose to dismiss the 2-norm formulation in favor of the infinity-norm formulation; one factor in their choice seems to be that quadratic convergence is not so immediate for the 2-norm formulation. In this work we establish the surprising result that the 2-norm formulation gives a convergence rate of 1+sqrt(2), significantly superior to that given by the Peters and Wilkinson formulation.

May 1987 (revised Novemeber 1987)

A Variable-Metric Variant of the Karmarkar Algorithm for Linear Programming

The most time-consuming part of the Karmarkar algorithm for linear programming is computation of the step direction, which requires the projection of a vector onto the nullspace of a matrix that changes at each iteration. We present a variant of the Karmarkar algorithm that uses standard variable-metric techniques in an innovative way to approximate this projection. We prove that the modified algorithm that we construct using a step direction obtained from this approximation retains the polynomial-time complexity of the Karmarkar algorithm. We extend applicability of the modified algorithm to the solution of linear programming problems with unknown optimal value, using a construction of monotonic lower bounds on the optimal objective value that approximates the lower bound construction of Todd and Burrell. We show that our modified algorithm for solving problems with unknown optimal value also retains the polynomial-time complexity ofthe Karmarkar algorithm. Computational testing has verified that our modification substantially reduces the number of matrix factorizations needed for the solution of linear programming problems, compared to the number of matrix factorizations required by the Karmarkar algorithm.

May 1987

Safeguarding Hessian Approximations in Trust Region Algorithms

In establishing global convergence results for trust region algorithms applied to unconstrained optimization, it is customary to assume either a uniform upper bound on the sequence of Hessian approximations or an upper bound linear in the iteration count. The former property has not been established for most commonly used secant updates, and the latter has only been established for some updates under the highly restrictive assumption of convexity.

One purpose of the uniform upper bound assumption is to establish a technical condition we refer to as the uniform predicted decrease condition. We show that this condition can also be obtained by milder assumptions, the simplest of which is a uniform upper bound on the sequence of Rayleigh quotients of the Hessian approximations in the gradient directions. This in turn suggests both a simple procedure for detecting questionable Hessian approximations, and several natural procedures for correcting them when detected.

In numerical testing, one of these procedures increased the reliability of the popular BFGS method by a factor of two (i.e., the procedure halved the number of test cases to fail to converge to a critical point in a reasonable number of iterations). Further, for those problems where both methods were successful, this safeguarding procedure actually improved the average efficiency of the BFGS by ten to twenty percent.

May, 1987

Domain Decomposition and Mixed Finite Element Methods for Elliptic Problems

In this paper we describe the numerical solution of elliptic problems with nonconstant coefficients by domain decomposition methods based on a mixed formulation and mixed finite element approximations. Two families of conjugate gradient algorithms taking advantage of domain decomposition will be discussed and their performance will be evaluated through numerical experiments, some of them concerning practical situations arising from flow in porous media.

May, 1987

[In First International Symposium on Domain Decomposition Methods for Partial Differential Equations (Paris, 1987), 144-172, SIAM, Philadelphia, PA, 1988.]

Domain Decomposition for Elliptic Partial Differential Equations with Neumann Boundary Conditions

Discretization of a self-adjoint elliptic partial differential equation by finite differences or finite elements yields a large, sparse, symmetric system of equations, Ax=b. We use the preconditioned conjugate gradient method with domain decomposition to develop an effective, vectorizable preconditioner which is suitable for solving large two-dimensional problems on vector and parallel machines.

May, 1987

[Parallel Comput. 5 (1987), no. 1-2, 257-263.]

An Operator-Splitting Method for Advection-Diffusion-Reaction Problems

Abstract not available

May, 1987

[In The Mathematics of Finite Elements and Applications, VI (Uxbridge, 1987), 463-482, Academic Press, London, 1988.]

Inference for Time Series with Mixed Spectrum

The old and important problem of estimating the discontinuous (mixed) spectrum of a series containing periodic components was considered in this paper. Most nonparametric spectral estimation procedures were developed for estimating smooth spectra and did not provide satisfactory results in estimating mixed spectra. A nonparametric estimation procedure was proposed for estimating discontinuous spectra. The procedure first finds a robust filter, which is insensitive to the presence of periodic components, to prewhiten the noise series and then uses a feature preserving smoother on the residual periodograms to estimate the discontinuous spectrum of the filtered series. The procedure was applied to some simulated data, and the results were compared with the classical kernel estimates and the autoregressive spectral estimates. The proposed procedure performs much better than the classical methods in estimating mixed spectra. The proposed procedure was also applied to three real data sets, including the famous Canadian lynx data. The proposed procedure was extended to estimate high-dimensional spectra. The problem of testing the significance of periodic components was discussed, and a testing procedure was also suggested.

May 1987

Karmarkar as a Classical Method

In this work we demonstrate that the Karmarkar algorithm for linear programs results from the classical approach of first transforming nonnegativity constraints into equality constraints by adding squared-slack variables and then applying the method of successive linear programming (SLP) to the resulting nonlinear program. Three specific formulations of the SLP method immediately present themselves. One gives the Karmarkar algorithm, one gives the algorithm commonly referred to as the affine scaling variant of the Karmarkar algorithm, and one gives the Karmarkar variant suggested independently by Barnes (1986), Cavalier and Soyster (1985), and Vanderbei, Meketon and Freedman (1985). Employing the understanding gained from these equivalences, we make several observations. By replacing the SLP component with an SQP (successive quadratic programming) component we present a new algorithm and demonstrate that it is locally quadratically convergent, and the problem variables that converge to zero do so q-superlinearly. Finally, we give some general comments on the use of squared-slack variables and a historical overview of the use of square-slack variables in linear programming.

March 1987 (revised August 1987)

On the Global Convergence of Trust Region Algorithms Using Inexact Gradient Information

Trust region algorithms are an important class of methods that can be used to solve unconstrained optimization problems. Moré [10] has proven a global convergence result for a class of trust region methods where the gradient values are approximated rather than computed exactly, provided the approximations are consistent. We show that the assumption of consistency can be replaced by a simple condition on the relative error in the gradient approximation. This new condition has both practical and theoretical advantages. First, it provides a practical test for judging the adequacy of a given gradient approximation, and does not require new approximations to be computed for unsuccessful iterations. Second, it leads to stronger convergence results than obtained in [10].

May 1987

[SIAM J. Numer. Anal. 28 (1991), no. 1, 251-265.]

A Global Convergence Theory for Arbitrary Norm Trust Region Methods for Nonlinear Equations

In this research we extend the Levenberg-Marquardt algorithm for approximating zeros of the nonlinear system F(x) = 0, where F is continuously differentiable from R^n to R^n. Instead of the l2-norm, arbitrary norms can be used in the objective function and in the trust region constraint. The algorithm is shown to be globally convergent. This research was motivated by the recent work of Duff, Nocedal and Reid. A key point in our analysis is that the tools from nonsmooth analysis, namely locally Lipschitz analysis, allow us to establish essentially the same properties for our algorithm that have been established for the Levenberg-Marquardt algorithm using the tools from smooth optimization. In our analysis, the sequence generated by the algorithm is the couple (xk, deltak) where xk is the iterate and deltak the trust region radius. Since the successor (x{k+1}, delta{k+1}) of (xk, deltak) is not unique we model our algorithm by a point-to-set map and then apply Zangwill's theorem of convergence to our case. It is shown that our algorithm reduces locally to Newton's method.

March 1987

The Local Convergence of Sequential Quadratic Programming Methods

Sequential quadratic programming methods for solving constrained nonlinear optimization problems (P) generate iterates xk, x{k+1}: = Phi(xk), by means of a certain iteration function Phi(xk), which has any Kuhn-Tucker point x* of (P) as fixed point. By studying the differentiability properties of Phi(xk) close to x*, we obtain easy and straightforward proofs for some fundamental results on the convergence speed of the iterates xk, e.g. the Boggs-Tolle-Wang characterization of their Q-superlinear convergence, and Powell's criterion for their 2-step Q-superlinear convergence.

March 1987

Deflated Krylov Subspace Methods for Nearly Singular Linear Systems

This paper concerns the use of Krylov subspace methods for the solution of nearly singular nonsymmetric linear systems. We show that the Incomplete Orthogonalization Methods (IOM) in conjunction with certain deflation techniques of Stewart and Chan can be used to solve large nonsymmetric linear systems which are nearly singular.

February 1987

[J. Optim. Theory Appl. 72 (1992), no. 3, 441-457.]

Biased and Unbiased Cross-Validation in Density Estimation

Non parametric density estimation requires the specification of smoothing parameters. The demand of statistical objectivity make it highly desirable to base the choice on properties of the data set. In this paper we introduce some biased cross-validation criteria for selection of smoothing parameters for kernel and histogram density estimators, closely related to one investigated in Scott and Factor (1981). These criteria are obtained by estimating L2-norms of derivatives of the unknown density and provide slightly biased estimates of the average squared-L2 error or mean integrated squared error. These criteria are roughly the analog of Wahba's (1981) generalized cross-validation procedure for orthogonal series density estimators. We present the relationship of the biased cross-validation procedure to the least squares cross-validation procedure, which provides unbiased estimates of the mean integrated squared error. Both methods are shown to be based on U-statistics. We compare the two methods by theoretical calculation of the noise in the cross-validation functions and corresponding cross-validated smoothing parameters, by Monte Carlo simulation, and by example. Surprisingly large gains in asymptotic efficiency are observed when biased cross-validation is compared to unbiased cross-validation if the underlying density is sufficiently smooth. The theoretical results explain some of the small sample behavior of cross-validation functions: we show that cross-validation algorithms can be unreliable for samples sizes which are "too small." In order to aid the practitioner in the use of these appealing automatic cross-validation algorithms and to help facilitate evaluation of future algorithms, we must address some ofttimes controversial issues in density estimation: squared loss, the integrate squared error and mean integrated squared error criteria, adaptive density estimates, sample size requirements, and assumptions about the underlying density's smoothness. We conclude that the two cross-validation procedures behave quite differently so that one might well use both in practice.

February 1987

[J. Amer. Statist. Assoc. 82 (1987), no. 400, 1131-1146.]

A Feature Preserving Smoother with Application to the Coal-Mining Disaster Data of Britain

The problem of estimating a discontinuous mean function was studied. A feature preserving smoothing procedure was proposed. The procedure can preserve the discontinuities of the function and detect outliers in the observations. The procedure was applied to analyze the famous data set of the coal-mining disasters of Britain.

January 1987

Go to 1986 reports

Go to 1988 reports