A short proof of the Dennis-Schnabel theorem

It is shown on the basis of simple orthogonality relations that all least change secant updates under additional linear constraints can be represented as projected rank one or rank two corrections.     

Improved Hessian approximation with modified secant equations for symmetric rank-one method

Symmetric rank-one (SR1) is one of the competitive formulas among the quasi-Newton (QN) methods. In this paper, we propose some modified SR1 updates based on the modified secant equations, which use both gradient and function information. Furthermore, to avoid the loss of positive definiteness and zero denominators of the new SR1 updates, we apply a restart procedure to this update. Three new algorithms are given to improve the Hessian approximation with modified secant equations for the SR1 method. Numerical results show that the proposed algorithms are very encouraging and the advantage of the proposed algorithms over the standard SR1 and BFGS updates is clearly observed.     

Separation process optimization calculations

A modified Newton-like method for nonlinearly constrained optimization calculations is presented and applied to a variety of separation process optimization problems.The nonlinear programming algorithm in this paper is similar to those of Wilson, Han and Powell. It differs only in the way in which approximations to the Hessian matrix of the Lagrangian function are built. For separation process applications, a large amount of reliable second-derivative information is available in analytical form. Much of the remaining second-derivative information is subject to certain thermodynamic constraints. Our algorithm exploits these two facts by building Hessian matrix approximations in two parts, a computed part which is built analytically, and an approximated part which is built by iterated projections and the Powell-symmetric-Broyden formula. Iterated projections are required so that the quasi-Newton matrix approximations satisfy the thermodynamic constraints at each iteration and a limiting secant condition. Further advantage is taken of the complete separability of the thermodynamic functions. This modified successive quadratic programming algorithm has been compared to various Newton-like methods on a number of separation process optimization problems. These include cost minimization calculations for one- and two-stage flash units and the optimization of the operating conditions of a distillation column. The numerical results show that our modified algorithm can compete favorably with existing methods, in terms of reliability and efficiency, on these applications.     

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.     

On the generation of updates for quasi-Newton methods

We present a unified technique for updating approximations to Jacobian or Hessian matrices when any linear structure can be imposed. The updates are derived by variational means, where an operator-weighted Frobenius norm is used, and are finally expressed as solutions of linear equations and/or unconstrained extrema. A certain behavior of the solutions is discussed for certain perturbations of the operator and the constraints. Multiple secant relations are then considered. For the nonsparse case, an explicit family of updates is obtained including Broyden, DFP, and BFGS. For the case where some of the matrix elements are prescribed, explicit solutions are obtained if certain conditions are satisfied. When symmetry is assumed, we show, in addition, the connection with the DFP and BFGS updates.This work was partially supported by a grant from Control Data     

Symmetric minimum-norm updates for use in gibbs free energy calculations

This paper examines a type of symmetric quasi-Newton update for use in nonlinear optimization algorithms. The updates presented here impose additional properties on the Hessian approximations that do not result if the usual quasi-Newton updating schemes are applied to certain Gibbs free energy minimization problems. The updates derived in this paper are symmetric matrices that satisfy a given matrix equation and are least squares solutions to the secant equation. A general representation for this class of updates is given. The update in this class that has the minimum weighted Frobenius norm is also presented. This work was done at Sandia National Laboratories and supported by the US Dept. of Energy under contract no. DE-AC04-76DP00789.     

A NEW SECANT METHOD FOR NONLINEAR LEAST SQUARES PROBLEMS

This paper is concerned with the solution of the nonlinear least squares problems. A new secant method is suggested in this paper, which is based on an affine model of the objective function and updates the first-order approximation each step when the iterations proceed. We present an algorithm which combines the new secant method with Gauss-Newton method for general nonlinear least squares problems. Furthermore, we prove that this algorithm is Q-superlinearly convergent for large residual problems under mild conditions.     

Inertia-preserving secant updates

A class of rank-two, inertia-preserving updates for symmetric matricesH _c is studied. To ensure that inertia is preserved, the updates are chosen to be of the formH ₊=FH _c F ^t, whereF=I+qr ^t, withq andr selected so that the secant equation is satisfied. A characterization is given for all such updates. Using a parameterization of this family of updates, the connection between them and the Broyden class of updates is established. Also, parameter selection criteria that can be used to choose the optimally conditioned update or the update closest to the SR1 update are discussed.The work of the first author was partially supported by AFOSR Grant 84-0326. The work of the second author was partially supported by NSF Grant EAR-82-18743.     

On the superlinear convergence of the variable metric proximal point algorithm using Broyden and BFGS matrix secant updating

In previous work, the authors provided a foundation for the theory of variable metric proximal point algorithms in Hilbert space. In that work conditions are developed for global, linear, and super–linear convergence. This paper focuses attention on two matrix secant updating strategies for the finite dimensional case. These are the Broyden and BFGS updates. The BFGS update is considered for application in the symmetric case, e.g., convex programming applications, while the Broyden update can be applied to general monotone operators. Subject to the linear convergence of the iterates and a quadratic growth condition on the inverse of the operator at the solution, super–linear convergence of the iterates is established for both updates. These results are applied to show that the Chen–Fukushima variable metric proximal point algorithm is super–linearly convergent when implemented with the BFGS update. Received: September 12, 1996 / Accepted: January 7, 2000?Published online March 15, 2000     

Moment equations and Hermite expansion for nonlinear stochastic differential equations with application to stock price models

Exact moment equations for nonlinear Itô processes are derived. Taylor expansion of the drift and diffusion coefficients around the first conditional moment gives a hierarchy of coupled moment equations which can be closed by truncation or a Gaussian assumption. The state transition density is expanded into a Hermite orthogonal series with leading Gaussian term and the Fourier coefficients are expressed in terms of the moments. The resulting approximate likelihood is maximized by using a quasi Newton algorithm with BFGS secant updates. A simulation study for the CEV stock price model compares the several approximate likelihood estimators with the Euler approximation and the exact ML estimator (Feller, in Ann Math 54: 173–182, 1951).     

An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem

The irregular strip packing problem is a combinatorial optimization problem that requires to place a given set of two-dimensional polygons within a rectangular container so that no polygon overlaps with other polygons or protrudes from the container, where each polygon is not necessarily convex. The container has a fixed width, while its length can change so that all polygons are placed in it. The objective is to find a layout of the set of polygons that minimizes the length of the container.We propose an algorithm that separates overlapping polygons based on nonlinear programming, and an algorithm that swaps two polygons in a layout so as to find their new positions in the layout with the least overlap. We incorporate these algorithms as components into an iterated local search algorithm for the overlap minimization problem and then develop an algorithm for the irregular strip packing problem using the iterated local search algorithm. Computational comparisons on representative instances disclose that our algorithm is competitive with other existing algorithms. Moreover, our algorithm updates several best known results.     

Updating approximate principal components with applications to template tracking

Adaptive principal component analysis is prohibitively expensive when a large‐scale data matrix must be updated frequently. Therefore, we consider the truncated URV decomposition that allows faster updates to its approximation to the singular value decomposition while still producing a good enough approximation to recover principal components. Specifically, we suggest an efficient algorithm for the truncated URV decomposition when a rank 1 matrix updates the data matrix. After the algorithm development, the truncated URV decomposition is successfully applied to the template tracking problem in a video sequence proposed by Matthews et al. [IEEE Trans. Pattern Anal. Mach. Intell., 26:810‐815 2004], which requires computation of the principal components of the augmented image matrix at every iteration. From the template tracking experiments, we show that, in adaptive applications, the truncated URV decomposition maintains a good approximation to the principal component subspace more efficiently than other procedures.     

ESTIMATING A DISTRIBUTION FUNCTION WITH TRUNCATED DATA

ＥＳＴＩＭＡＴＩＮＧＡＤＩＳＴＲＩＢＵＴＩＯＮＦＵＮＣＴＩＯＮＷＩＴＨＴＲＵＮＣＡＴＥＤＤＡＴＡＨＥＳＨＵＹＵＡＮ（何书元）（ＤｅｐａｒｔｍｅｎｔｏｆＰｒｏｂａｂｉｌｉｔｙａｎｄＳｔａｔｉｓｔｉｃｓ，ＰｅｋｉｎｇＵｎｉｖｅｒｓｉｔｙＢｅｉｊｉｎｇ１０...     

KERNEL ESTIMATION OF HIGHER DERIVATIVES OF DENSITY AND HAZARD RATE FUNCTION FOR TRUNCATED AND CENSORED DEPENDENT DATA

Based on left truncated and right censored dependent data, the estimators of higher derivatives of density function and hazard rate function are given by kernel smoothing method. When observed data exhibit α-mixing dependence, local properties including strong consistency and law of iterated logarithm are presented. Moreover, when the mode estimator is defined as the random variable that maximizes the kernel density estimator, the asymptotic normality of the mode estimator is established.     

左截断右删失下一类泛函估计的渐近性质

在左截断右删失下,本文讨论了一类广义Von－Mises泛函估计的渐近性质．在一定条件下,得到了此类泛函估计的强逼近和U-统计量表示,并由此得出它的强相合性、渐近正态性及重对数律．     

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 andq-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.This research was sponsored by SDIO/IST/ARO, AFOSR-85-0243, and DOE-DEFG05-86 ER-25017.A portion of this work is contained in the second author's doctoral thesis under the supervision of the other two authors in the Department of Mathematical Sciences, Rice University. The second author would like to thank Universidad del Valle, Cali, Columbia, for support during his graduate studies.An early draft of this work was presented at the SIAM 35th Anniversary Meeting, October 12–15, 1987, Denver, Colorado.     

Safety preserving control synthesis for sampled data systems

In sampled data systems the controller receives periodically sampled state feedback about the evolution of a continuous time plant, and must choose a constant control signal to apply between these updates; however, unlike purely discrete time models the evolution of the plant between updates is important. In this paper we describe an abstract algorithm for approximating the discriminating kernel (also known as the maximal robust control invariant set) for a sampled data system with continuous state space, and then use this operator to construct a switched, set-valued feedback control policy which ensures safety. We show that the approximation is conservative for sampled data systems. We then demonstrate that the key operations–the tensor products of two sets, invariance kernels, and a pair of projections–can be implemented in two formulations: one based on the Hamilton–Jacobi partial differential equation which can handle nonlinear dynamics but which scales poorly with state space dimension, and one based on ellipsoids which scales well with state space dimension but which is restricted to linear dynamics. Each version of the algorithm is demonstrated numerically on a simple example.     

Use of extrapolation for improving the order of convergence of eigenelement approximations

We consider the approximation of the eigenelements of a compactintegral operator defined on C[0, 1] with a smooth kernel. Weuse the iterated collocation method based on r Gauss pointsand piecewise polynomials of degree r – 1 on each subintervalof a nonuniform partition of [0, 1]. We obtain asymptotic expansionsfor the arithmetic means of m eigenvalues and also for the associatedspectral projections. Using Richardson extrapolation, we showthat the order of convergence O(h^2r) in the iterated collocationmethod can be improved to O(h^2r+2). Similar results hold forthe Nyström method and for the iterated Galerkin method.We illustrate the improvement in the order of convergence bynumerical experiments.     

Efficient implementation of ‘Optimal’ algorithms in computerized tomography

We describe three optimal algorithms for the reconstruction of a function in R ² from a finite number of line or strip integrals: Optimal recovery, Bayes estimate, Tikhonov-Phillips method. In the case of a rotationally invariant scanning geometry we show that the resulting linear system is a block-cyclic convolution. This observation leads to algorithms which are roughly as efficient as filtered backprojection which is one of the standard methods. The algorithms can be applied to the case of hollow and truncated projections. Numerical examples are given.