Scaled memoryless symmetric rank one method for large-scale optimization

This paper concerns the memoryless quasi-Newton method, that is precisely the quasi-Newton method for which the approximation to the inverse of Hessian, at each step, is updated from the identity matrix. Hence its search direction can be computed without the storage of matrices. In this paper, a scaled memoryless symmetric rank one (SR1) method for solving large-scale unconstrained optimization problems is developed. The basic idea is to incorporate the SR1 update within the framework of the memoryless quasi-Newton method. However, it is well-known that the SR1 update may not preserve positive definiteness even when updated from a positive definite matrix. Therefore we propose the memoryless SR1 method, which is updated from a positive scaled of the identity, where the scaling factor is derived in such a way that positive definiteness of the updating matrices are preserved and at the same time improves the condition of the scaled memoryless SR1 update. Under very mild conditions it is shown that, for strictly convex objective functions, the method is globally convergent with a linear rate of convergence. Numerical results show that the optimally scaled memoryless SR1 method is very encouraging.     

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.     

Cubic regularization in symmetric rank-1 quasi-Newton methods

Quasi-Newton methods based on the symmetric rank-one (SR1) update have been known to be fast and provide better approximations of the true Hessian than popular rank-two approaches, but these properties are guaranteed under certain conditions which frequently do not hold. Additionally, SR1 is plagued by the lack of guarantee of positive definiteness for the Hessian estimate. In this paper, we propose cubic regularization as a remedy to relax the conditions on the proofs of convergence for both speed and accuracy and to provide a positive definite approximation at each step. We show that the n-step convergence property for strictly convex quadratic programs is retained by the proposed approach. Extensive numerical results on unconstrained problems from the CUTEr test set are provided to demonstrate the computational efficiency and robustness of the approach.     

A Kantorovich Theorem for the Structured PSB Update in Hilbert Space

The convergence behavior of quasi-Newton methods has been well investigated for many update rules. One exception that has to be examined is the PSB update in Hilbert space. Analogous to the SR1 update, the PSB update takes advantage of the symmetry property of the operator, but it does not require the positive definiteness of the operator to work with. These properties are of great practical importance, for example, to solve minimization problems where the starting operator is not positive definite, which is necessary for other updates to ensure local convergence. In this paper, a Kantorovich theorem is presented for a structured PSB update in Hilbert space, where the structure is exploited in the sense of Dennis and Walker. Finally, numerical implications are illustrated by various results on an optimal shape design problem.     

Verification of Positive Definiteness

We present a computational, simple and fast sufficient criterion to verify positive definiteness of a symmetric or Hermitian matrix. The criterion uses only standard floating-point operations in rounding to nearest, it is rigorous, it takes into account all possible computational and rounding errors, and is also valid in the presence of underflow. It is based on a floating-point Cholesky decomposition and improves a known result. Using the criterion an efficient algorithm to compute rigorous error bounds for the solution of linear systems with symmetric positive definite matrix follows. A computational criterion to verify that a given symmetric or Hermitian matrix is not positive definite is given as well. Computational examples demonstrate the effectiveness of our criteria. AMS subject classification (2000) 65G20, 15A18     

Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identity

Summary The number of multiplications required for matrix multiplication, for the triangular decomposition of a matrix with partial pivoting, and for the Cholesky decomposition of a positive definite symmetric matrix, can be roughly halved if Winograd's identity is used to compute the inner products involved. Floating-point error bounds for these algorithms are shown to be comparable to those for the normal methods provided that care is taken with scaling.     

Real valued iterative methods for solving complex symmetric linear systems

Complex valued systems of equations with a matrix R + 1S where R and S are real valued arise in many applications. A preconditioned iterative solution method is presented when R and S are symmetric positive semi‐definite and at least one of R, S is positive definite. The condition number of the preconditioned matrix is bounded above by 2, so only very few iterations are required. Applications when solving matrix polynomial equation systems, linear systems of ordinary differential equations, and using time‐stepping integration schemes based on Padé approximation for parabolic and hyperbolic problems are also discussed. Numerical comparisons show that the proposed real valued method is much faster than the iterative complex symmetric QMR method. Copyright © 2000 John Wiley & Sons, Ltd.     

An SR1/BFGS SQP algorithm for nonconvex nonlinear programs with block-diagonal Hessian matrix

We present a quasi-Newton sequential quadratic programming (SQP) algorithm for nonlinear programs in which the Hessian of the Lagrangian function is block-diagonal. Problems with this characteristic frequently arise in the context of optimal control; for example, when a direct multiple shooting parametrization is used. In this article, we describe an implementation of a filter line-search SQP method that computes search directions using an active-set quadratic programming (QP) solver. To take advantage of the block-diagonal structure of the Hessian matrix, each block is approximated separately by quasi-Newton updates. For nonconvex instances, that arise, for example, in optimum experimental design control problems, these blocks are often found to be indefinite. In that case, the block-BFGS quasi-Newton update can lead to poor convergence. The novel aspect in this work is the use of SR1 updates in place of BFGS approximations whenever possible. The resulting indefinite QPs necessitate an inertia control mechanism within the sparse Schur-complement factorization that is carried out by the active-set QP solver. This permits an adaptive selection of the Hessian approximation that guarantees sufficient progress towards a stationary point of the problem. Numerical results demonstrate that the proposed approach reduces the number of SQP iterations and CPU time required for the solution of a set of optimal control problems.     

Bi-block positive semidefiniteness of bi-block symmetric tensors

The positive definiteness of elasticity tensors plays an important role in the elasticity theory.In this paper,we consider the bi-block symmetric tensors,which contain elasticity tensors as a subclass.First,we define the bi-block M-eigenvalue of a bi-block symmetric tensor,and show that a bi-block symmetric tensor is bi-block positive(semi)definite if and only if its smallest bi-block M-eigenvalue is(nonnegative)positive.Then,we discuss the distribution of bi-block M-eigenvalues,by which we get a sufficient condition for judging bi-block positive(semi)definiteness of the bi-block symmetric tensor involved.Particularly,we show that several classes of bi-block symmetric tensors are bi-block positive definite or bi-block positive semidefinite,including bi-block(strictly)diagonally dominant symmetric tensors and bi-block symmetric(B)B0-tensors.These give easily checkable sufficient conditions for judging bi-block positive(semi)definiteness of a bi-block symmetric tensor.As a byproduct,we also obtain two easily checkable sufficient conditions for the strong ellipticity of elasticity tensors.     

Hermite正定对称矩阵迹的一些结果(英文)

本文研究了一类Hermite正定矩阵迹的不等式问题.利用文献[2-6]中的结果以及放缩法,获得了Hermite正定矩阵迹的极值定理、杨氏不等式和贝努利不等式,并且将许多初等不等式推广到Hermite正定矩阵迹的情形.     

A sufficient condition for a non-negative matrix to have non-negative determinant

It is shown that a matrix with non-negative entries has non-negative determinant if in each row the elements decrease, by steadily smaller amounts, as one proceeds (in either direction) away from the main diagonal. This condition suffices to establish non- negativity of the determinant for certain matrices to which the familiar Minkowski- Hadamard-Ostrowski dominance conditions do not apply. In the symmetric case it provides a sufficient condition for non-negative definiteness. This may be applied to establish the positive definiteness of certain real symmetric Toeplitz matrices.     

Algebraic multilevel iteration method for Stieltjes matrices

The numerical solution of elliptic selfadjoint second-order boundary value problems leads to a class of linear systems of equations with symmetric, positive definite, large and sparse matrices which can be solved iteratively using a preconditioned version of some algorithm. Such differential equations originate from various applications such as heat conducting and electromagnetics. Systems of equations of similar type can also arise in the finite element analysis of structures. We discuss a recursive method constructing preconditioners to a symmetric, positive definite matrix. An algebraic multilevel technique based on partitioning of the matrix in two by two matrix block form, approximating some of these by other matrices with more simple sparsity structure and using the corresponding Schur complement as a matrix on the lower level, is considered. The quality of the preconditioners is improved by special matrix polynomials which recursively connect the preconditioners on every two adjoining levels. Upper and lower bounds for the degree of the polynomials are derived as conditions for a computational complexity of optimal order for each level and for an optimal rate of convergence, respectively. The method is an extended and more accurate algebraic formulation of a method for nine-point and mixed five- and nine-point difference matrices, presented in some previous papers.     

一种新的修正SR1更新公式及其算法收敛性

SR1更新公式对比其他的拟牛顿更新公式,会更加简单且每次迭代需要更少的计算量。但是一般SR1更新公式的收敛性质是在一致线性无关这一很强的条件下证明的。基于前人的研究成果,提出了一种新的修正SR1公式,并分别证明了其在一致线性无关和没有一致线性无关这两个条件下的局部收敛性,最后通过数值实验验证了提出的更新公式的有效性,以及所作出假设的合理性。根据实验数据显示,在某些条件下基于所提出更新公式的拟牛顿算法会比基于传统的SR1更新公式的算法收敛效果更好一些。     

Retaining positive definiteness in thresholded matrices

Positive definite (p.d.) matrices arise naturally in many areas within mathematics and also feature extensively in scientific applications. In modern high-dimensional applications, a common approach to finding sparse positive definite matrices is to threshold their small off-diagonal elements. This thresholding, sometimes referred to as hard-thresholding, sets small elements to zero. Thresholding has the attractive property that the resulting matrices are sparse, and are thus easier to interpret and work with. In many applications, it is often required, and thus implicitly assumed, that thresholded matrices retain positive definiteness. In this paper we formally investigate the algebraic properties of p.d. matrices which are thresholded. We demonstrate that for positive definiteness to be preserved, the pattern of elements to be set to zero has to necessarily correspond to a graph which is a union of complete components. This result rigorously demonstrates that, except in special cases, positive definiteness can be easily lost. We then proceed to demonstrate that the class of diagonally dominant matrices is not maximal in terms of retaining positive definiteness when thresholded. Consequently, we derive characterizations of matrices which retain positive definiteness when thresholded with respect to important classes of graphs. In particular, we demonstrate that retaining positive definiteness upon thresholding is governed by complex algebraic conditions.     

Theoretical investigations of the new Cokriging method for variable-fidelity surrogate modeling

Cokriging is a variable-fidelity surrogate modeling technique which emulates a target process based on the spatial correlation of sampled data of different levels of fidelity. In this work, we address two theoretical questions associated with the so-called new Cokriging method for variable-fidelity modeling:

1. (1)
   A mandatory requirement for the well-posedness of the Cokriging emulator is the positive definiteness of the associated Cokriging correlation matrix. Spatial correlations are usually modeled by positive definite correlation kernels, which are guaranteed to yield positive definite correlation matrices for mutually distinct sample points. However, in applications, low-fidelity information is often available at high-fidelity sample points and the Cokriging predictor may benefit from the additional information provided by such an inclusive sampling. We investigate the positive definiteness of the Cokriging covariance matrix in both of the aforementioned cases and derive sufficient conditions for the well-posedness of the Cokriging predictor.
    
2. (2)
   The approximation quality of the Cokriging predictor is highly dependent on a number of model- and hyper-parameters. These parameters are determined by the method of maximum likelihood estimation. For standard Kriging, closed-form optima of the model parameters along hyper-parameter profile lines are known. Yet, these do not readily transfer to the setting of Cokriging, since additional parameters arise, which exhibit a mutual dependence. In previous work, this obstacle was tackled via a numerical optimization. Here, we derive closed-form optima for all Cokriging model parameters along hyper-parameter profile lines. The findings are illustrated by numerical experiments.
    

     

A RESTARTING DIRECTION FOR THE CONJUGATE GRADIENT METHOD

The main purpose of this paper is to provide a restarting direction for improving on the standard conjugate gradient method.If a drastic non-quadratic behaviour of the objective function is observed in the neighbour of xk,then a restart should be done.The scaling symmetric rank-one update with Davidon's optimal criterion is applied to generate the restarting direction.It is proved that the conjugate gradient method with this strategy retains the quadratic termination.Numerical experiments show that it is successful.     

A class of compactly supported orthogonal symmetric complex wavelets with dilation factor 3

When approximation order is an odd positive integer a simple method is given to construct compactly supported orthogonal symmetric complex scaling function with dilation factor 3. Two corresponding orthogonal wavelets, one is symmetric and the other is antisymmetric about origin, are constructed explicitly. Additionally, when approximation order is an even integer 2, we also give a method to construct compactly supported orthogonal symmetric complex wavelets. In the end, there are several examples that illustrate the corresponding results.     

ORTHOGONAL MATRIX POLYNOMIALS WITH RESPECT TO A CONJUGATE BILINEAR MATRIX MOMENT FUNCTIONAL: BASIC THEORY

In this paper basic results for a theory of orthogonal matrix polynomials with respect to a conjugate bilinear matrix moment functional are proposed. Properties of orthogonal matrix polynomial sequences including a three term matrix relationship are given. Positive definite conjugate bilinear matrix moment functionals are introduced and a characterization of positive definiteness in terms of a block Haenkel moment matrix is established. For each positive definite conjugate bilinear matrix moment functional an associated matrix inner product is defined.     

The inverse eigenvalue problem for a weighted helmholtz equation

Given the m lowest eigenvalues, we seek to recover an approximation to the density function ρ in the weighted Helmholtz equation -Δ=λρu on a rectangle with Dirchlet boundary conditions. The density ρ is assumed to be symmetric with respect to the midlines of the rectangle. Projection of the boundary value problem and the unknown density function onto appropriate vector spaces leads to a matrix inverse problem. Solutions of the matrix inverse problem exist provided that the reciprocals of the prescribed eigenvalues are close to the reciprocals of the simple eigenvalues of the base problem with ρ = 1. The matrix inverse problem is solved by a fixed—point iterative method and a density function ρ^* is constructed which has the same m lowest eigenvalues as the unknown ρ. The algorithm can be modified when multiple base eigenvalues arise, although the success of the modification depends on the symmetry properties of the base eigenfunctions.     

A non-conforming domain decomposition for Raviart-Thomas vector fields in three dimensions

In this paper we are concerned with a domain decomposition method with nonmatching grids for Raviart-Thomas finite elements. In this method, the normal complement of the resulting approximation is not continuous across the interface. To handle such non-conformity, a new matching condition will be introduced. Such matching condition still