Using parallel function evaluations to improve hessian approximation for unconstrained optimization

This paper presents a new class of methods for solving unconstrained optimization problems on parallel computers. The methods are intended to solve small to moderate dimensional problems where function and derivative evaluation is the dominant cost. They utilize multiple processors to evaluate the function, (finite difference) gradient, and a portion of the finite difference Hessian simultaneously at each iterate. We introduce three types of new methods, which all utilize the new finite difference Hessian information in forming the new Hessian approximation at each iteration; they differ in whether and how they utilize the standard secant information from the current step as well. We present theoretical analyses of the rate of convergence of several of these methods. We also present computational results which illustrate their performance on parallel computers when function evaluation is expensive.Research supported by AFOSR grant AFOSR-85-0251, ARO contract DAAG 29-84-K-0140, NSF grant DCR-8403483, and NFS cooperative agreement DCR -8420944.     

On multilevel iterative methods for optimization problems

This paper is concerned with multilevel iterative methods which combine a descent scheme with a hierarchy of auxiliary problems in lower dimensional subspaces. The construction of auxiliary problems as well as applications to elasto-plastic model and linear programming are described. The auxiliary problem for the dual of a perturbed linear program is interpreted as a dual of perturbed aggregated linear program. Coercivity of the objective function over the feasible set is sufficient for the boundedness of the iterates. Equivalents of this condition are presented in special cases.Supported by NSF under grant DMS-8704169, AFOSR under grant 86-0126, and ONR under Contract N00014-83-K-0104. Consulting for American Airlines Decision Technologies, MD 2C55, P.O. Box 619616, DFW, TX 75261-9616, USA.Supported by NSF under grant DMS-8704169 and AFOSR under grant 86-0126.     

Parallel quasi-Newton methods for unconstrained optimization

We discuss methods for solving the unconstrained optimization problem on parallel computers, when the number of variables is sufficiently small that quasi-Newton methods can be used. We concentrate mainly, but not exclusively, on problems where function evaluation is expensive. First we discuss ways to parallelize both the function evaluation costs and the linear algebra calculations in the standard sequential secant method, the BFGS method. Then we discuss new methods that are appropriate when there are enough processors to evaluate the function, gradient, and part but not all of the Hessian at each iteration. We develop new algorithms that utilize this information and analyze their convergence properties. We present computational experiments showing that they are superior to parallelization either the BFGS methods or Newton's method under our assumptions on the number of processors and cost of function evaluation. Finally we discuss ways to effectively utilize the gradient values at unsuccessful trial points that are available in our parallel methods and also in some sequential software packages.Research supported by AFOSR grant AFOSR-85-0251, ARO contract DAAG 29-84-K-0140, NSF grants DCR-8403483 and CCR-8702403, and NSF cooperative agreement DCR-8420944.     

Brownian motion in infinite dimensional manifolds

We discuss the extension to infinite dimensional Riemannian—Wiener manifolds of the transport approximation to Brownian motion, which was formulated by M. Pinsky for finite dimensional manifolds. A global representation is given for the Laplace—Beltrami operator in terms of the Riemannian spray and a homogenizing operator based upon the central hitting measure of the surface of the unit ball with respect to the Brownian motion on the model space.Research supported by NSF grant MCS8202319.     

Newton interpolation is efficient for approximation of linear functionals

Summary The Newton interpolation approach is developed for approximation of linear functionals. It is shown that in numerical interpolation and numerical differentiation, the Newton interpolation approach is more efficient than solving the Vandermonde systems.This work was supported in part by the United States Air Force under a grant AFOSR 76-3020     

Inverse parabolic problems and discrete orthogonality

Summary This paper considers a discrete sampling scheme for the approximate recovery of initial data for one dimensional parabolic initial boundary value problems on a bounded interval. To obtain a given approximate, data is sampled at a single time and at a finite number of spatial points. The significance of this inversion scheme is the ability to accurately predict the error in approximation subject to choice of sample time and spatial sensor locations. The method is based on a discrete analogy of the continuous orthogonality for Sturm-Liouville systems. This property, which is of independent mathematical interest, is the notion of discrete orthogonal systems, which loosely speaking provides an exact (or approximate) Gauss-type quadrature for the continuous biorthogonality conditions.Supported in part by NSF Grant #DMS8905-344. Texas Advanced Research Program Grant #0219-44-5195 and AFOSR Grant #88-0309Visiting at Texas Tech University, Fall 1989Supported in part by NSF Grant #DMS8905-344, NSA grant #MDA904-85-H009 and NASA Grant #NAQ2-89     

Ritz-Galerkin approximations in blending function spaces

Summary This paper considers the theoretical development of finite dimensional bivariate blending function spaces and the problem of implementing the Ritz-Galerkin method in these approximation spaces. More specifically, the approximation theoretic methods of polynomial blending function interpolation and approximation developed in [2, 11–13] are extended to the general setting of L-splines, and these methods are then contrasted with familiar tensor product techniques in application of the Ritz-Galerkin method for approximately solving elliptic boundary value problems. The key to the application of blending function spaces in the Ritz-Galerkin method is the development of criteria which enable one to judiciously select from a nondenumerably infinite dimensional linear space of functions, certain finite dimensional subspaces which do not degrade the asymptotically high order approximation precision of the entire space. With these criteria for the selection of subspaces, we are able to derive a virtually unlimited number of new Ritz spaces which offer viable alternatives to the conventional tensor product piecewise polynomial spaces often employed. In fact, we shall see that tensor product spaces themselves are subspaces of blending function spaces; but these subspaces do not preserve the high order precision of the infinite dimensional parent space.Considerable attention is devoted to the analysis of several specific finite dimensional blending function spaces, solution of the discretized problems, choice of bases, ordering of unknowns, and concrete numerical examples. In addition, we extend these notations to boundary value problems defined on planar regions with curved boundaries.     

The effect of perturbations on the convergence rates of optimization algorithms

The problem of minimizing a functionF over a set Ω is approximated by a sequence of problems whereF and Ω are replaced byF ⁽ⁿ⁾ and Ω⁽ⁿ⁾, respectively. We show in which manner the convergence rates of the conditional gradient and projected gradient methods are influenced by the approximation. In particular, it becomes evident how the convergence theory for infinite dimensional problems such as control problems explains the behavior of finite dimensional implementations.     

On efficiently combining limited-memory and trust-region techniques

Limited-memory quasi-Newton methods and trust-region methods represent two efficient approaches used for solving unconstrained optimization problems. A straightforward combination of them deteriorates the efficiency of the former approach, especially in the case of large-scale problems. For this reason, the limited-memory methods are usually combined with a line search. We show how to efficiently combine limited-memory and trust-region techniques. One of our approaches is based on the eigenvalue decomposition of the limited-memory quasi-Newton approximation of the Hessian matrix. The decomposition allows for finding a nearly-exact solution to the trust-region subproblem defined by the Euclidean norm with an insignificant computational overhead as compared with the cost of computing the quasi-Newton direction in line-search limited-memory methods. The other approach is based on two new eigenvalue-based norms. The advantage of the new norms is that the trust-region subproblem is separable and each of the smaller subproblems is easy to solve. We show that our eigenvalue-based limited-memory trust-region methods are globally convergent. Moreover, we propose improved versions of the existing limited-memory trust-region algorithms. The presented results of numerical experiments demonstrate the efficiency of our approach which is competitive with line-search versions of the L-BFGS method.     

Resolution and the integrality of satisfiability problems

A satisfiability problem can be regarded as a nondisjoint union of set covering problems. We show that if the resolution method of theorem proving is applied to the satisfiability problem, its constraint set defines an integral polytope if and only if the constraint sets of the set covering problems do. In this sense, resolution reduces the integrality question for the satisfiability problem to that for the set covering problem. Partially supported by ONR grant N00014-92-J-1028 and AFOSR grant 91-0287.     

AnO(h 6) quintic spline collocation method for fourth order two-point boundary value problems

AnO(h ⁶) collocation method based on quintic splines is developed and analyzed for general fourth-order linear two-point boundary value problems. The method determines a quintic spline approximation to the solution by forcing it to satisfy a high order perturbation of the original boundary value problem at the nodal points of the spline. A variation of this method is formulated as a deferred correction method. The error analysis of the new method and its numerical behavior is presented.This research was supported by AFOSR grant 84-0385.     

Local and superlinear convergence of quasi-Newton methods based on modified secant conditions

For solving unconstrained minimization problems, quasi-Newton methods are popular iterative methods. The secant condition which employs only the gradient information is imposed on these methods. Several researchers paid attention to other secant conditions to get a better approximation of the Hessian matrix of the objective function. Recently, Zhang et al. [New quasi-Newton equation and related methods for unconstrained optimization, J. Optim. Theory Appl. 102 (1999) 147–167] and Zhang and Xu [Properties and numerical performance of quasi-Newton methods with modified quasi-Newton equations, J. Comput. Appl. Math. 137 (2001) 269–278] proposed the modified secant condition which uses both gradient and function value information in order to get a higher order accuracy in approximating the second curvature of the objective function. They showed the local and q-superlinear convergence property of the BFGS-like and DFP-like updates based on their proposed secant condition. In this paper, we incorporate one parameter into this secant condition to smoothly switch the standard secant condition and the secant condition of Zhang et al. We consider a modified Broyden family which includes the BFGS-like and the DFP-like updates proposed by Zhang et al. We prove the local and q-superlinear convergence of our method.     

Analytic invariants and the Schwarz-Pick inequality

We find numerical analytic invariants distinguishing between the infinite dimensional analogues of the classical Cartan domains of different type. Further, we define an invariant Hermitian metric on the classical bounded symmetric domains and certain infinite dimensional analogues and show that of all such metrics this is the only one (up to a constant multiple) which yields the best constant in the Schwarz-Pick inequality. Research partially supported by N.S.F. grant MCS 76-06975 A01.     

A Structured Secant Method Based on a New Quasi-Newton Equation for Nonlinear Least Squares Problems

In this paper, a new quasi-Newton equation is applied to the structured secant methods for nonlinear least squares problems. We show that the new equation is better than the original quasi-Newton equation as it provides a more accurate approximation to the second order information. Furthermore, combining the new quasi-Newton equation with a product structure, a new algorithm is established. It is shown that the resulting algorithm is quadratically convergent for the zero-residual case and superlinearly convergent for the nonzero-residual case. In order to compare the new algorithm with some related methods, our preliminary numerical experiments are also reported.     

Spline approximation,Kronecker products and multilinear forms

Sums of Kronecker products occur naturally in high‐dimensional spline approximation problems, which arise, for example, in the numerical treatment of chemical reactions. In full matrix form, the resulting non‐sparse linear problems usually exceed the memory capacity of workstations. We present methods for the manipulation and numerical handling of Kronecker products in factorized form. Moreover, we analyze the problem of approximating a given matrix by sums of Kronecker products by making use of the equivalence to the problem of decomposing multilinear forms into sums of one‐forms. Greedy algorithms based on the maximization of multilinear forms over a torus are used to obtain such (finite and infinite) decompositions that can be used to solve the approximation problem. Moreover, we present numerical considerations for these algorithms. Copyright © 2016 John Wiley & Sons, Ltd.     

Computational experiments with scaled initial hessian approximation for the broyden family methods ∗

In this paper we consider two alternative choices for the factor used to scale the initial Hessian approximation, before updating by a member of the Broyden family of updates for quasi-Newton optimization methods. By extensive computational experiments carried out on a set of standard test problems from the CUTE collection, using efficient implemen-tations of the quasi-Newton method, we show that the proposed new scaling factors are better, in terms of efficiency achieved (number of iterations, number of function and gradient evaluations), than the standard choice proposed in the literature     

Truncated Trust Region Methods Based on Preconditioned Iterative Subalgorithms for Large Sparse Systems of Nonlinear Equations

This paper is devoted to globally convergent methods for solving large sparse systems of nonlinear equations with an inexact approximation of the Jacobian matrix. These methods include difference versions of the Newton method and various quasi-Newton methods. We propose a class of trust region methods together with a proof of their global convergence and describe an implementable globally convergent algorithm which can be used as a realization of these methods. Considerable attention is concentrated on the application of conjugate gradient-type iterative methods to the solution of linear subproblems. We prove that both the GMRES and the smoothed COS well-preconditioned methods can be used for the construction of globally convergent trust region methods. The efficiency of our algorithm is demonstrated computationally by using a large collection of sparse test problems.     

A GENERALIZED QUASI-NEWTON EQUATION AND COMPUTATIONAL EXPERIENCE

The quasi-Newton equation has played a central role in the quasi-Newton methods forsolving systems of nonlinear equations and/or unconstrained optimization problems.In-stead,Pan suggested a new equation,and showed that it is of the second order while thetraditional of the first order,in certain approximation sense[12].In this paper,we makea generalization of the two equations to include them as special cases.The generalizedequation is analyzed,and new updates are derived from it.A DFP-like new update out-performed the traditional DFP update in computational experiments on a set of standardtest problems.     

Contingent derivatives of set-valued maps and applications to vector optimization

In this paper we investigate contingent derivatives of set-valued maps and their lower and upper semidifferentiability properties. We provide also some calculus rules for these derivatives in infinite dimensional spaces. The concept of contingent derivatives is then applied to produce several necessary and sufficient conditions for vector optimization problems with set-valued objectives.This paper was written when the author was at the University of Erlangen-Nurnberg under a grant of the Alexander von Humboldt Foundation.On leave from the Institute of Mathematics, Hanoi, Vietnam.     

A likelihood ratio formula for random fields with application to physical geodesy

A formula for the likelihood ratio applicable to estimation and inference problems arising in random field data models in physical geodesy is derived based on multiparameter white noise theory.Research supported in part under grant no. 78-3550, Applied Mathematics Division, AFOSR, United States Air Force.