Optimization of unconstrained functions with sparse Hessian matrices—Quasi-Newton methods

Newton-type methods and quasi-Newton methods have proven to be very successful in solving dense unconstrained optimization problems. Recently there has been considerable interest in extending these methods to solving large problems when the Hessian matrix has a known a priori sparsity pattern. This paper treats sparse quasi-Newton methods in a uniform fashion and shows the effect of loss of positive-definiteness in generating updates. These sparse quasi-Newton methods coupled with a modified Cholesky factorization to take into account the loss of positive-definiteness when solving the linear systems associated with these methods were tested on a large set of problems. The overall conclusions are that these methods perform poorly in general—the Hessian matrix becomes indefinite even close to the solution and superlinear convergence is not observed in practice. Research for this paper was performed at the Department of Operations Research, Stanford, CA 94305. The research was partially supported by the Department of Energy Contract AM03-76SF00326. PA# DE-AT03-76ER72018: Office of Naval Research Contract N00014-75-C-0267; National Science Foundation Grants MCS-7681259, MCS-7926009 and ECS-8012974.     

Estimation of sparse hessian matrices and graph coloring problems

Large scale optimization problems often require an approximation to the Hessian matrix. If the Hessian matrix is sparse then estimation by differences of gradients is attractive because the number of required differences is usually small compared to the dimension of the problem. The problem of estimating Hessian matrices by differences can be phrased as follows: Given the sparsity structure of a symmetric matrixA, obtain vectorsd ₁,d ₂, …d _p such thatAd ₁,Ad ₂, …Ad _p determineA uniquely withp as small as possible. We approach this problem from a graph theoretic point of view and show that both direct and indirect approaches to this problem have a natural graph coloring interpretation. The complexity of the problem is analyzed and efficient practical heuristic procedures are developed. Numerical results illustrate the differences between the various approaches. Work supported in part by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38.     

Exact Finite Difference Scheme for an Advection-Reaction Equation

We construct an exact finite difference scheme for a non-linear PDE having linear advection and an odd-cubic reaction term. This construction is based on the fact that the general initial-value problem for the equation can be completely solved. We also give a detailed discussion of the mathematical structure of the exact finite difference equation.     

Object-oriented modelling and simulation of heat exchangers with finite element methods

The paper describes the derivation of finite-element models of one-dimensional fluid flows with heat transfer in pipes, using the Galerkin/least-squares approach. The models are first derived for one-phase flows, and then extended to homogeneous two-phase flows. The resulting equations have then been embedded in the context of object-oriented system modelling; this allows one to combine the fluid flow model with a model for other phenomena such as heat transfer, as well as with models of other discrete components such as pumps or valves, to obtain complex models of heat exchangers. The models are then validated by simulating a typical heat exchanger plant.     

Non-linear analysis of the consolidation of an elastic saturated soil with incompressible fluid and variable permeability by FEM

Research interest in the mechanical behaviour of soils is growing as a result of an increasing number of geomechanical problems involving consolidation effects. The main aim of this paper is to validate and to solve a model for consolidation of an elastic saturated soil with incompressible fluid and variable permeability. Firstly, we prove the existence and uniqueness of the solution of the variational problem corresponding to an initial and boundary value problem (IBVP): a special case of the Biot’s ‘consolidation of clay’ model (where the applied forces depend on time). Secondly, we prove the convergence of the method using a technique based on the proof of solution’s existence. Finally, we then solved this constitutive model by the finite element method (FEM) employing repeated fixed point techniques in order to obtain the results for displacement and pore water pressure. The pore fluid is considered incompressible. The results of the numerical experiments are compared with analytical solutions and, in cases where such solutions do not exist, with experimental data. Therefore, the model can be used for quantitative predictions of consolidation behaviour of soils with permeability dependent on the settlement.     

Quasi-Monte Carlo methods for integration of functions with dominating mixed smoothness in arbitrary dimension

In a celebrated construction, Chen and Skriganov gave explicit examples of point sets achieving the best possible _L2$L_2$-norm of the discrepancy function. We consider the discrepancy function of the Chen–Skriganov point sets in Besov spaces with dominating mixed smoothness and show that they also achieve the best possible rate in this setting. The proof uses a b$b$-adic generalization of the Haar system and corresponding characterizations of the Besov space norm. Results for further function spaces and integration errors are concluded.