Approximate quasi-Newton methods

We consider the effect of approximation on performance of quasi-Newton methods for infinite dimensional problems. In particular we study methods in which the approximation is refined at each iterate. We show how the local convergence behavior of the quasi-Newton method in the infinite dimensional setting is affected by the refinement strategy. Applications to boundary value problems and integral equations are considered.The research of this author was supported by NSF grant DMS-8601139 and AFOSR grant AFOSR-ISSA-860074.     

Two regularization methods for a spherically symmetric inverse heat conduction problem

In this paper, we consider a spherically symmetric inverse heat conduction problem of determining the internal surface temperature of a hollow sphere from the measured data at a fixed location inside it. This is an ill-posed problem in the sense that the solution (if it exists) does not depend continuously on the data. A Tikhonov type’s regularization method and a Fourier regularization method are applied to formulate regularized solutions which are stably convergent to the exact ones with order optimal error estimates.     

Nonsmooth optimization via quasi-Newton methods

We investigate the behavior of quasi-Newton algorithms applied to minimize a nonsmooth function f, not necessarily convex. We introduce an inexact line search that generates a sequence of nested intervals containing a set of points of nonzero measure that satisfy the Armijo and Wolfe conditions if f is absolutely continuous along the line. Furthermore, the line search is guaranteed to terminate if f is semi-algebraic. It seems quite difficult to establish a convergence theorem for quasi-Newton methods applied to such general classes of functions, so we give a careful analysis of a special but illuminating case, the Euclidean norm, in one variable using the inexact line search and in two variables assuming that the line search is exact. In practice, we find that when f is locally Lipschitz and semi-algebraic with bounded sublevel sets, the BFGS (Broyden–Fletcher–Goldfarb–Shanno) method with the inexact line search almost always generates sequences whose cluster points are Clarke stationary and with function values converging R-linearly to a Clarke stationary value. We give references documenting the successful use of BFGS in a variety of nonsmooth applications, particularly the design of low-order controllers for linear dynamical systems. We conclude with a challenging open question.     

Bounded rank-1 transformations

We define the notion of canonical boundedness among rank-1 transformations and use it to characterize the class of bounded rank-1 transformations with trivial centralizer. We also explicitly characterize totally ergodic rank-1 transformations with bounded cutting parameter. Together with a recent result of Ryzhikov, our results provide a simple procedure for determining, purely in terms of the cutting and spacer parameters for the transformation, whether a bounded rank-1 transformation has minimal self-joinings of all orders.     

Structure of quasi-Newton minimization methods

A scheme for the design of quasi-Newton methods for unconstrained optimization problems is examined. A criterion for the positive definiteness of the quasi-Newton modification of the Hessian matrix is given. Quasi-Newton methods are described that cannot be placed within the classical scheme specified by the family of Broyden methods.     

New implicit multistep quasi-Newton methods

Multistep quasi-Newton optimization methods use data from more than one previous step to construct the current Hessian approximation. These methods were introduced in [3, 4] where it is shown how to construct such methods by means of interpolating curves. To obtain a better parametrization of the interpolation, Ford [2] developed the idea of “implicit” methods. In this paper, we describe a derivation of new implicit updates which are similar to methods I4 and I5 created in [17]. The experimental results presented here show that both of the new methods produce better performance than the existing methods, especially as the dimension of the test problem grows.     

Multi-step quasi-Newton methods for optimization

Quasi-Newton methods update, at each iteration, the existing Hessian approximation (or its inverse) by means of data deriving from the step just completed. We show how “multi-step” methods (employing, in addition, data from previous iterations) may be constructed by means of interpolating polynomials, leading to a generalization of the “secant” (or “quasi-Newton”) equation. The issue of positive-definiteness in the Hessian approximation is addressed and shown to depend on a generalized version of the condition which is required to hold in the original “single-step” methods. The results of extensive numerical experimentation indicate strongly that computational advantages can accrue from such an approach (by comparison with “single-step” methods), particularly as the dimension of the problem increases.     

Sharp upper bound for the first non-zero Neumann eigenvalue for bounded domains in rank-1 symmetric spaces

In this paper, we prove that for a bounded domain in a rank- symmetric space, the first non-zero Neumann eigenvalue where denotes the geodesic ball of radius such that

and equality holds iff . This result generalises the works of Szego, Weinberger and Ashbaugh-Benguria for bounded domains in the spaces of constant curvature.

     

Variational quasi-Newton methods for unconstrained optimization

In this paper, we propose new members of the Broyden family of quasi-Newton methods. We develop, on the basis of well-known least-change results for the BFGS and DFP updates, a measure for the Broyden family which seeks to take into account the change in both the Hessian approximation and its inverse. The proposal is then to choose the formula which gives the least value of this measure in terms of the two parameters available, and hence to produce an update which is optimal in the sense of the given measure. Several approaches to the problem of minimizing the measure are considered, from which new updates are obtained. In particular, one approach yields a new variational result for the Davidon optimally conditioned method and another yields a reasonable modification to this method. The paper is also concerned with the possibility of estimating, in a certain sense, the size of the eigenvalues of the Hessian approximation on the basis of two available scalars. This allows one to derive further modifications to the above-mentioned methods. Comparisons with the BFGS and Davidson methods are made on a set of standard test problems that show promising results for certain new methods.Part of this work was done during the author's visits at International Centre for Theoretical Physics, Trieste, Italy, at Systems Department, University of Calabria, Cosenza, Italy, and at Ajman University College of Science and Technology, Ajman, United Arab Emirates.The author expresses his gratitude to Professor L. Grandinetti for his encouragement and thanks the anonymous referees for their careful reading of an earlier draft of the paper and valuable comments, which led to a substantial improvement of the original paper.     

Nonsmooth multiobjective programming with quasi-Newton methods

This paper proposes a new algorithm to solve nonsmooth multiobjective programming. The algorithm is a descent direction method to obtain the critical point (a necessary condition for Pareto optimality). We analyze both global and local convergence results under some assumptions. Numerical tests are also given.     

Diagonalized multiplier methods and quasi-Newton methods for constrained optimization

Two approaches to quasi-Newton methods for constrained optimization problems inR ⁿ are presented. These approaches are based on a class of Lagrange multiplier approximation formulas used by the author in his previous work on Newton's method for constrained problems. The first approach is set in the framework of a diagonalized multiplier method. From this point of view, a new update rule for the Lagrange multipliers which depends on the particular quasi-Newton method employed is given. This update rule, in contrast to most other update rules, does not require exact minimization of the intermediate unconstrained problem. In fact, the optimal convergence rate is attained in the extreme case when only one step of a quasi-Newton method is taken on this intermediate problem. The second approach transforms the constrained optimization problem into an unconstrained problem of the same dimension.The author would like to thank J. Moré and M. J. D. Powell for comments related to the material in Section 13. He also thanks J. Nocedal for the computer results in Tables 1–3 and M. Wright for the results in Table 4, which were obtained via one of her general programs. Discussions with M. R. Hestenes and A. Miele regarding their contributions to this area were very helpful. Many individuals, including J. E. Dennis, made useful general comments at various stages of this paper. Finally, the author is particularly thankful to R. Byrd, M. Heath, and R. McCord for reading the paper in detail and suggesting many improvements.This work was supported by the Energy Research and Development Administration, Contract No. E-(40-1)-5046, and was performed in part while the author was visiting the Department of Operations Research, Stanford University, Stanford, California.     

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.     

Cubic and symmetric compositions over rings

We consider generalized symmetric compositions over a ring k on the one hand, and unital algebras with multiplicative cubic forms on the other. Given a primitive sixth root of unity in k, we construct functors between these categories which are equivalences if 3 is a unit in k. This extends to arbitrary base rings, and with new proofs, results of Elduque and Myung on non-degenerate symmetric compositions and separable alternative algebras of degree 3 over fields. It also answers a problem posed in “The Book of Involutions” [Knus et al.: American Mathematical Society Colloquium Publications, vol. 44. American Mathematical Society, Providence, RI (1998), 34.26].     

Methods of conjugate directions versus quasi-Newton methods

It is shown that algorithms for minimizing an unconstrained functionF(x), x E ⁿ , which are solely methods of conjugate directions can be expected to exhibit only ann or (n–1) step superlinear rate of convergence to an isolated local minimizer. This is contrasted with quasi-Newton methods which can be expected to exhibit every step superlinear convergence. Similar statements about a quadratic rate of convergence hold when a Lipschitz condition is placed on the second derivatives ofF(x). Research was supported in part by Army Research Office, Contract Number DAHC 19-69-C-0017 and the Office of Naval Research, Contract Number N00014-71-C-0116 (NR 047-99).     

Adjoint-based quasi-Newton methods for partially separable problems

In this paper the concepts of partitioned quasi-Newton methods are applied to adjoint Broyden updates. Consequently a corresponding partitioned adjoint Broyden update is presented and local convergence results are given. Numerical results compare the partitioned adjoint Broyden update methods to the corresponding unpartitioned quasi-Newton method and to Newton's method for nonlinear equations. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Secant relations versus positive definiteness in quasi-Newton methods

The effect of using a nonsymmetric and nonpositive-definite matrix for approximation of the Hessian inverse in unconstrained optimization is investigated. To this end, a new algorithm, which may be viewed as a member of the Huang family, is derived. The proposed algorithm possesses the quadratic termination property without exact line search. It seems from the numerical results that it is not essential to use a symmetric and positive-definite matrix.     

Phase portraits of the full symmetric Toda systems on rank-2 groups

We continue investigations begun in our previous works where we proved that the phase diagram of the Toda system on special linear groups can be identified with the Bruhat order on the symmetric group if all eigenvalues of the Lax matrix are distinct or with the Bruhat order on permutations of a multiset if there are multiple eigenvalues. We show that the phase portrait of the Toda system and the Hasse diagram of the Bruhat order coincide in the case of an arbitrary simple Lie group of rank 2. For this, we verify this property for the two remaining rank-2 groups, Sp(4,?) and the real form of G₂.     

A sharp upper bound for the first eigenvalue of the Laplacian of compact hypersurfaces in rank-1 symmetric spaces

Let M be a closed hypersurface in a simply connected rank-1 symmetric space . In this paper, we give an upper bound for the first eigenvalue of the Laplacian of M in terms of the Ricci curvature of and the square of the length of the second fundamental form of the geodesic spheres with center at the center-of-mass of M.     

Non-asymptotic superlinear convergence of standard quasi-Newton methods

Mathematical Programming - In this paper, we study and prove the non-asymptotic superlinear convergence rate of the Broyden class of quasi-Newton algorithms which includes the...