Conventions for Using PIERS

(Abstract not available)

December 1991

On the Convergence of Fenchel Cutting Planes for Mixed Integer Programs

Fenchel cutting planes are based on the dual relationship between separation and optimization and can be applied in many instances where alternative cutting planes cannot. They are deep in the sense of providing the maximum separation between a point x and a polyhedron P as measured by an arbitrary norm which is specified in the process of generating a Fenchel cut. This paper demonstrates a number of fundamental convergence properties of Fenchel cuts and addresses the question of which norms lead to the most desirable Fenchel cuts. The strengths and weaknesses of the related class of 1-polar cuts are also examined.

December 1991

A Test Set of Real-World Mixed Integer Programming Problems

(Abstract not available)

November 1991 (revised January 1992)

Explicit/Implicit, Conservative Domain Decomposition Procedures for Parabolic Problems Based on Block-Centered Finite Differences

(Abstract not available)

November 1991

[SIAM J. Numer. Anal. 31 (1994), no. 4, 1045-1061.]

Analysis of Explicit/Implicit, Block Centered Finite Difference Domain Decomposition Procedures for Parabolic Problems

Domain decomposition procedures for solving parabolic equations are considered. The underlying discretization is block-centered finite differences. In this procedures, fluxes at subdomain interfaces are calculated from the solution at the previous time level. These fluxes serve as Neumann boundary data for implicit, block-centered discretizations in the subdomains. A priori error estimates are derived, and numerical results examining the stability, accuracy, and parallelism of the scheme are presented.

November 1991

Column-Secant Update Technique for Solving Systems of Nonlinear Equations

This paper presents a QR update implementation of the successive column correction (SCC) method and a column-secant modification of the SCC method, which is called the CSSCC method. The computational cost of the QR update technique for the SCC method is much less than that for Broyden's method. The CSSCC method uses function values more efficiently than the SCC method, and it shown that the CSSCC method has better local q-convergence and r-convergence rates than the SCC method. The numerical results show that the SCC method and the CSSCC method with the QR update technique are competitive with some well known methods for some standard test problems.

October 1991

[Numer. Math. J. Chinese Univ. (English Ser.) 4 (1995), no. 2, 193-206.]

Successive Element Correction Algorithms for Sparse Unconstrained Optimization

This paper presents a successive element correction algorithm and a secant modification of this algorithm. The new algorithms are designed to use the gradient evaluations as efficiently as possible in forming the approximate Hessian. The estimate of the q-convergence and r-convergence rates show that the new algorithms may have good local convergence properties. Some restricted numerical results and comparisons with some previously established algorithms suggest the new algorithms have some promise to be efficient in practice.

October 1991

[J. Optim. Theory Appl. 77 (1993), no. 3, 523-543.]

Steady State Couette Flow

An exact solution is found for a non-linear problem with thermomechanical coupling, the steady flow of a fluid with viscosity exponentially dependent on temperature, which is sheared between an adiabatic, fixed, inner cylinder and a thermostatted, rotating, outer cylinder. There is a maximum torque above which no steady flow is possible and below which two flows are possible, a high shear and a low shear steady flow for each value of torque.

October 1991

Recovering an Optimal LP Basis from an Interior Point Solution

An important issue in the implementation of interior point algorithms for linear programming is the recovery of an optimal basic solution from an optimal interior point solution. In this paper we describe a method for recovering such a solution. Our implementation links a high-performance interior point code (OB1) with a high-performance simplex code (CPLEX). Results for our computational tests indicate that basis recovery can be done quickly and efficiently.

October 1991

[Oper. Res. Lett. 15 (1994), no. 4, 169-178.]

Thermal Simulation of Pipeline Flow

A new numerical method for studying one dimensional fluid flow through pipelines is presented and analyzed. This work extends in a certain direction the collocation method described by Luskin ["An Approximation Procedure for Nonsymmetric, Nonlinear Hyperbolic Systems with Integral Boundary Conditions," SIAM J. Numer. Anal. 1976]. The pressure and velocity of an isothermal fluid in a pipeline can be described by a coupled pair of nonlinear first order hyperbolic partial differential equations. When thermal effects are important a third equation for temperature is added. While Luskin's method works well for the isothermal situation he discussed, it does not apply in certain common cases when thermal effects are modeled. The analysis of this new method shows how the difficulties that come from the application of standard collocation can be overcome. Experiments indicate that this method is a substantial improvement over standard collocation. It also describes an approach to analyzing nonlinear evolution equations with smooth solutions which produces convergence theorems about the nonlinear system from the corresponding linear theorems with relatively little extra work. This technique also yields an H¹ estimate in the isothermal case.

September 1991

[SIAM J. Numer. Anal. 32 (1995), no. 4, 1225-1262.]

On the Convergence of Interior-Point Methods to the Center of the Solution Set in Linear Programming

The notion of the central path plays an important role in the convergence analysis of interior-point methods. Many interior-point algorithms have been developed based on the principle of following the central path, either closely or otherwise. However, whether such algorithms actually converge to the center of the solution set has remained an open question. In this paper, we demonstrate that under mild conditions, when the iteration sequence generated by a primal-dual interior-point method converges, it converges to the center of the solution set.

September 1991

Time-Split Methods for Advective Flow Problems in Multidimensions Based on Combining Godunov-Type Procedures with a Mixed Finite Element Method

Time-split methods for multidimensional advection-diffusion equations are considered. In these methods, advection is approximated by a Godunov-type procedure, and diffusion is approximated by a low order mixed finite element method. This approach is currently being used by a number of researchers to model fluid flow. A general methodology is outlined and analyzed, then two particular schemes for calculating advective fluxes are discussed. The first approach is an unsplit, higher-order Godunov method. In this approach, a method of characteristics is used to calculate the advective flux, and time steps larger than a CFL time step are considered. In an appendix, a modification to the first approach that is second order in time is analyzed.

September 1991

Optimal Shapes for Kernel Density Estimations: An Historical Footnote

In the early years of kernel density estimation, Watson and Leadbetter (1963) attempted to optimize kernel shape for fixed sample sizes by minimizing the expected L² distance between the kernel density estimate and the true density. Perhaps out of technical necessity, they did not impose the constraint that the kernel be a probability density function. The present paper uses recent developments in the theory of infinite programming to successfully impose that constraint. Necessary and sufficient conditions for solution of the constrained problem are derived. These conditions are not trivial; however, they can be exploited to demonstrate that symmetric densities with sufficiently light tails have optimal kernels with compact support.

September 1991

[Comm. Statist. Theory Methods 22 (1993), no. 2, 375-391.]

Superlinear and Quadratic Convergence of Primal-Dual Interior-Point Methods for Linear Programming Revisited

Recently, Zhang, Tapia and Dennis produced a superlinear and quadratic convergence theory for the duality gap sequence in primal-dual interior-point methods for linear programming. In this theory, a basic assumption for superlinear convergence is the convergence of the iteration sequence; and a basic assumption for quadratic convergence is nondegeneracy. Several recent research projects have either used or built on this theory under one or both of the above mentioned assumptions. In this paper, we remove both assumptions from the Zhang-Tapia-Dennis theory.

August 1991

[J. Optim. Theory Appl. 73 (1992), no. 2, 229-242.]

A Quadratically Convergent O(sqrt{n}L)-Iteration Algorithm for Linear Programming

Recently, Ye et al. proposed a large step modification of the Mizuno-Todd-Ye predictor-corrector interior-point algorithm for linear programming. They demonstrated that the large-step algorithm maintains the O (sqrt{n}L)-iteration complexity while exhibiting superlinear convergence of the duality gap to zero under the assumption that the iteration sequence converges, and quadratic convergence of the duality gap to zero under the assumption of nondegeneracy. In this paper we establish the quadratic convergence result without any assumption concerning the convergence of the iteration sequence or nondegeneracy. This surprising result, to our knowledge, is the first instance of polynomiality and superlinear (or quadratic) convergence for an interior-point algorithm which does not assume the convergence of the iteration sequence or nondegeneracy.

August 1991

[Math. Programming 59 (1993), no. 2, Ser. A, 151-162.]

Extending the Farkas Lemma Approach to Necessity Conditions to Infinite Programming

Under mild assumptions, the classical Farkas lemma approach to Lagrange multiplier theory is extended to an infinite programming formulation. The main result generalizes the usual first-order necessity conditions to address problems in which the domain of the objective function is Hilbert space and the number of constraints is arbitrary. The result is used to obtain necessity conditions for a well-known problem from the statistical literature on probability density estimation.

July 1991 (revised May 1993)

[SIAM Review, 36 (1):1-17 (1994)]

On the Convergence of the Iteration Sequence in Primal-Dual Interior-Point Methods

This research is concerned with the convergence of the iteration sequence generated by a primal-dual interior-point method for linear programming. It is known that this sequence converges when both the primal and the dual problems have unique solutions. However, convergence for general problems has been an open question now for quite some time. In this work we demonstrate that for general problems, under mild conditions, the iteration sequence converges.

August 1991 (revised August 1993)

[Math. Programming 68 (1995), no. 2, Ser. A, 141-154.]

An Interior-Point Method with Polynomial Complexity and Superlinear Convergence for Linear Complementarity Problems

For linear programming, a primal-dual interior-point algorithm was recently constructed by Zhang and Tapia that achieves both polynomial complexity and Q-superlinear convergence (Q-quadratic in the nondegenerate case). In this paper, we extend their results to quadratic programming and linear complementarity problems.

July 1991

A Superlinearly Convergent O(sqrt{n}L)-Iteration Algorithm for Linear Programming

In this note we consider a large step modification of the Mizuno-Todd-Ye O (sqrt{n}L) predictor-corrector interior-point algorithm for linear programming. We demonstrate that the modified algorithm maintains its O (sqrt{n}L)-iteration complexity, while exhibiting superlinear convergence for general problems and quadratic convergence for nondegenerate problems. To our knowledge, this is the first construction of a superlinearly convergent algorithm with O (sqrt{n}L)-iteration complexity.

July 1991

Resolving Degeneracy in Linear Programs: Steepest Edge, Steepest Ascent, and Closest Ascent

While variants of the steepest edge pivoting rule are commonly used in linear programming codes they are not known to have the theoretically attractive property of avoiding an infinite sequence of pivots at points of degeneracy. A natural extension of the steepest edge pivoting rule based on steepest ascent is developed and shown to be provably finite. An alternative finite pivoting procedure that is computationally more attractive than steepest ascent is then introduced and it is argued that with probability 1 the procedure has the same computational requirements as steepest edge independent of the linear program being solved. Both procedures have the unique advantage that they choose the pivot element without explicit knowledge of the set of all active constraints at a point of degeneracy, thus making them attractive in combinatorial settings where the linear program is never explicitly written out.

July 1991

The Dikin-Karmarkar Principle for Steepest Descent: Avoiding Short Steps

(Abstract not available)

July 1991

Sizing the BFGS and DFP Updates: A Numerical Study

In this study we develop and test a strategy for selectively sizing (multiplying by an appropriate scalar) the approximate Hessian matrix before it is updated in the BFGS and DFP trust-region methods for unconstrained optimization. Our numerical results imply that for use with the DFP update the Oren-Luenberger sizing factor is completely satisfactory and selective sizing is vastly superior to the alternatives of never sizing, or first-iteration sizing, and is slightly better than the alternative of always sizing. Numerical experimentation showed that the Oren-Luenberger sizing factor is not a satisfactory sizing factor for use with the BFGS update. Therefore, based on our newly acquired understanding of the situation, we propose a damped Oren-Luenberger sizing factor to be used with the BFGS update. Our numerical experimentation implies that selectively sizing the BFGS update with the damped Oren-Luenberger sizing factor is superior to the alternatives. These results contradict the folk-axiom that sizing should be done only at the first iteration. They also show that without sufficient sizing, DFP is vastly inferior to BFGS; however, when selectively sized, DFP is competitive with BFGS.

July 1991

[J. Optim. Theory Appl. 78 (1993), no. 1, 93-108.]

Numerical Comparisons of Local Convergence Strategies for Interior-Point Methods in Linear Programming

(Abstract not available)

July 1991

Convergence Properties of the Barzilai and Borwein Gradient Method

In a recent paper, Barzilai and Borwein presented a new choice of steplength for the gradient method. Their choice does not guarantee descent in the objective function and greatly speeds up the convergence of the method. We derive an interesting relationship between any gradient method and the shifted power method. This relationship allows us to establish the convergence of the Barzilai and Borwein method when applied to the problem of minimizing any strictly convex quadratic function (Barzilai and Borwein considered only 2-dimensional problems). Our point of view also allows us to explain the remarkable improvement obtained by using this new choice of steplength.

For the two eigenvalues case we present some very interesting convergence rate results. We show that our Q and R-rate of convergence analysis is sharp and we compare it with the Barzilai and Borwein analysis.

We derive the preconditioned Barzilai and Borwein method and present preliminary numerical results indicating that it is an effective method, as compared to the preconditioned Conjugate Gradient method, for the numerical solution of some special symmetric positive definite linear systems that arise in the numerical solution of Partial Differential Equations.

June 1991

Additive Lower Bounding as a Cutting Plane Technique

It is demonstrated how the additive bounding procedure of Fischetti and Toth can be strengthened by interpreting it as a cutting plane technique.

June 1991

A Study of Indicators for Identifying Zero Variables in Interior-Point Methods

The ability to identify zero variables early on in an iterative method is of considerable value and can be used to computational advantage. In this work we first give a formal presentation of the notion of indicators for identifying zero variables, and then study various indicators proposed in the literature for use with interior-point methods for linear programming. We present both theory and experimentation that speaks strongly against the use of the variables as indicators; perhaps the most frequently used indicator in the literature. Our study implies that an indicator proposed by Tapia in 1980 is particularly effective in the context of primal-dual interior-point methods.

June 1991 (revised June 1993)

[SIAM Rev. 36 (1994), no. 1, 45-72.]

Simulation of Flow in Root-Soil Systems

In this paper we develop a mathematical model of a root-soil system, and also accurate and efficient finite element and finite difference algorithms for approximating this model. The goal of our work is to develop an understanding of the properties of root systems, which can be modified by using genetic engineering techniques, in order to improve the performance of plants when water availability is limited. The results of some numerical simulations are presented, which demonstrate the effectiveness of genetic and physical changes to the root-soil system.

May 1991

[SIAM J. Numer. Anal. 30 (1993), no. 6, 1677-1702.]

Structural Bounds for Eigenvalue Perturbation

A matrix perturbation B-A in the space of symmetric matrices should be related to the structure of that space. We try to take advantage of this fact to decompose the matrix perturbation in such a way that we get a more precise description of the eigenvalue perturbation. We obtain a lower bound for the eigenvalue perturbation that improves the known bound | |B|F - |A|F | given by the norm. Also we construct an upper bound that is related to the structure and sometimes is smaller than the known estimate |B - A|F. This bound gives us the maximal eigenvalue perturbation of two matrices with the same eigenvectors, keeping the same eigenvalue order.

May 1991

Segmented Data Files: An I/O Standard

(Abstract not available)

May 1991

Very Large-Scale Linear Programming: A Case Study in Combining Interior Point and Simplex Methods

Experience with solving a 12,753,313 variable linear program is described. This problem is the linear programming relaxation of a set partitioning problem arising from an airline crew scheduling application. A scheme is described that requires successive solutions of small subproblems, yielding a procedure that has little growth in solution time in terms of the number of variables. Experience using the simplex method as implemented in CPLEX, an interior point method as implemented in OB1, and hybrid interior point/simplex approach is reported. The resulting procedure illustrates the power of an interior point/simplex combination for solving very large-scale linear programs.

May 1991

[Oper. Res. 40 (1992), no. 5, 885-897.]

A New Formulation of Mixed Finite Element Methods for Second Order Elliptic Problems

In this paper we show that mixed finite element methods for a fairly general second order elliptic problem with variable coefficients can be given a nonmixed formulation. We define an approximation method by incorporating some projection operators within a standard Galerkin method, which we call a projection finite element method. It is shown that for a given mixed method, if the projection method's finite element space Mh satisfies two conditions, then the two approximation methods are equivalent. These two conditions can be simplified for a single element in the case of mixed spaces possessing the usual vector projection operator. For any such mixed spaces defined on a geometrically regular partition of the domain, we can then easily construct appropriate conforming spaces Mh. We also present for several mixed methods alternative nonconforming spaces Mh that also satisfy the two conditions for equivalence.

May 1991

A Subgradient Algorithm for Nonlinear Integer Programming and Its Parallel Implementation

This work concerns efficiently solving a class of nonlinear integer programming problems: min f (x): x in {0,1}^{n} where f (x) is a general nonlinear function. The notion of subgradient for the objective function is introduced. A necessary and sufficient condition for the optimal solution is constructed. And a new algorithm, called the subgradient algorithm, is developed. The algorithm is an iterative procedure, searching for the solution iteratively among feasible points, and in each iteration, generating the next iterative point by solving the problem for a local piecewise linear model of the original problem which is constructed with supporting planes for the objective function at a set of feasible points. Special continuous optimization techniques are used to compute the supporting planes. The problem for each local piecewise linear model is solved by solving an equivalent linear integer program. The fundamental theory for the new approach is built and all related mathematical proofs and derivations such as proofs for convergence properties, the finiteness of the algorithm, as well as the correct formulation of the subproblems are presented. The algorithm is parallelized and implemented on parallel distributed-memory machines. The preliminary numerical results show that the algorithm can solve test problems effectively.

To implement the subgradient algorithm, a parallel software system written in EXPRESS C is developed. The system contains a group of parallel subroutines that can be used for either continuous or discrete optimization such as subroutines for QR, LU and Cholesky factorizations, triangular system solvers and so on. A sequential implementation of the simplex algorithm for linear programming also is included. Especially, a parallel branch-and-bound procedure is developed. Different from directly parallelizing the sequential binary branch-and-bound algorithm, a parallel strategy with multiple branching is used for good processor scheduling. Performance results of the system on NCUBE are given.

May 1991

The Performance of an Explicit/Implicit, Domain Decomposition Procedure for Parabolic Equations on an Intel Hypercube

A domain decomposition procedure for parabolic equations is described. In this procedure, the computational domain is divided into nonoverlapping subdomains. The equation is discretized by finite differences in time, and in space, a Galerkin finite element method is used on each subdomain. Subdomain solutions are related by an explicit flux calculation on the interfaces between subdomains. The interface fluxes are calculated in a stable and accurate manner, thus no iterations between the interface and subdomains are required. The method has been implemented on an Intel iPSC/860 Hypercube, and comparisons between domain decomposition solutions and a fully implicit Galerkin solution are presented for a set of test problems.

May 1991

[In Fifth International Symposium on Domain Decomposition Methods for Partial Differential Equations (Norfolk, VA, 1991), 386-393, SIAM, Philadelphia, PA, 1992.]

Numerical Methods for the Simulation of Flow in Root-Soil Systems

We consider the numerical properties of approximation schemes for a model that simulates water transport in root-soil systems. The model given in this paper is a reformulation of a previously proposed model now defined completely in terms of the water potential. The system of equations consists of a parabolic partial differential equation which contains a nonlinear capacity term coupled to two linear ordinary differential equations. A closed form solution is obtained for one of the latter equations. Finite element and finite difference schemes are defined to approximate the solution of the coupled system, and optimal order error estimates are derived. A postprocessed water mass flux computation is also presented and shown to be superconvergent to the true flux. Computational results which verify the theoretical convergence rates are given.

April 1991

[SIAM J. Numer. Anal. 30 (1993), no. 6, 1677-1702.]

Simulation of Nonlinear Contaminant Transport in Groundwater by a Higher Order Godunov-Mixed Finite Element Method

We consider the numerical simulation of contaminant transport in groundwater where the mathematical model includes a nonlinear adsorption term. The method we describe combines a higher order Godunov scheme for advection with a mixed finite element method for diffusion. The method is formulated in one space dimension, and numerical results for equilibrium and nonequilibrium adsorption are presented.

April 1991

Godunov-Mixed Methods for Advective Flow Problems in One Space Dimension

A time-splitting method for solving advection-dominated, parabolic, partial differential equations is presented. In this method, a higher-order Godunov procedure approximates advection and a mixed finite element procedure approximates diffusion. Several variations on the basic scheme are formulated for solving one-dimensional, quasilinear, parabolic problems with Dirichlet boundary conditions. A maximum principle for one variant of the scheme is demonstrated, and L^{infinity}(L²) and L²(L²) error estimates for the approximate solution and the diffusive flux, respectively, are derived. These estimates indicate that one variant of the scheme is L^{infinity}-stable in certain situations, but possibly sub-optimal in error, while another variant is optimal and L²-stable.

March 1991

[SIAM J. Numer. Anal. 28 (1991), no. 5, 1282-1309.]

A Pseudopolynomial Problem Formulation for Exact Knapsack Separation

The NP-complete separation problem for the knapsack polyhedron P is formulated as a side-constrained network flow problem with a pseudopolynomial number of vertices and edges. It is demonstrated that the primal polyhedron associated with this formulation can be projected onto an appropriate subspace to yield P and that the dual polyhedron can be projected onto an appropriate subspace to yield the polar of P. Practical consequences of the formulation are discussed.

March 1991

Gravitational Forces in Dual-Porosity Models of Single Phase Flow

A dual porosity model is derived by the normal theory of homogenization. The model properly incorporates gravity in that it respects the equilibrium states of the medium.

March 1991

An Upper Bound for the Linearized Map of an Inverse Problem for the Wave Equation

(Abstract not available)

January 1991

Trace Regularity for a Second Order Hyperbolic Equation with Nonsmooth Coefficients

In this research, a trace regularity theorem on a time like surface is proved for the solution of a multidimensional linear acoustic wave equation with nonsmooth coefficients. Our theorem indicates that with microlocal restrictions against tangential oscillations in the coefficient, the boundary value is just as regular as the solution, in particular as regular as the coefficients allow to be.

January 1991

[J. Math. Anal. Appl. 174 (1993), no. 2, 370-389.]

Go to 1990 reports

Go to 1992 reports