关于线性系统解的对称性算法的强稳定性的探索

关于线性方程解的算法方面,本文在对称非奇异矩阵类和对称正定矩阵类上给出了强稳定性算法.     

最速下降法的一次迭代收敛性的一点注记

推广了最速下降法经过一次迭代到达严格凸二次规划问题的最优解的充分必要条件：初始点可以表示为最优解和Hesse矩阵的一个特征向量之和.证明此条件也是最速下降法经过有限次迭代后到达最优解的充要条件.丰富了最速下降法的理论,有助于更好地认识和理解最速下降法,对相关算法的教学有一定的启发意义.     

无约束优化问题的精细修正牛顿算法

针对牛顿法在求解一般非凸函数极小值过程中,迭代点处Hessian矩阵不一定正定的情况,提出了一种精细修正的牛顿法.该方法充分利用迭代点处目标函数的一阶、二阶信息,合适选取搜索方向,是最速下降法、牛顿法和已有修正牛顿法相混合的一种方法.在较弱的条件下建立了算法的全局收敛性.进一步的数值实验验证了提出的算法比以往同类算法计...     

实对称五对角矩阵的两类广义特征值反问题

讨论了如下两类广义特征值反问题:(i)由给定的三个互异的特征对和给定的实对称正定五对角矩阵构造一个实对称五对角矩阵;(ii)由给定的三个互异特征对和给定的全对称正定五对角矩阵构造一个全对称五对角矩阵.利用线性方程组理论、对称向量和反对称向量的性质,分别得到了两类反问题存在唯一解的充要条件,并给出了解的表达式和数值算法;最后通过数值例子说明了算法的有效性.     

正定矩阵标准型的复合矩阵的一般形式

实对称正定矩阵的复合矩阵正定性的研究已有结论,但对于一般意义下的正定矩阵的复合矩阵是否仍然是正定的研究需要利用一般的正定矩阵的标准形的复合矩阵进行讨论,给出了一般公式及具体算法,为讨论其复合矩阵的正定性提供了基础条件.     

正定矩阵的子式阵仍是正定矩阵的一个充要条件

文[2]证明了实对称正定矩阵的子式阵仍然是实对称正定矩阵,文[3]给出了一般的正定矩阵的的概念,本文利用标准型给出了一般正定矩阵的子式阵仍然是正定矩阵的充要条件.     

Oppenheim不等式的一种类似

证明了实对称正定矩阵或实对称半正定矩阵与 M-矩阵的 Hadamard乘积满足实对称正定矩阵 Hadamard乘积的 Oppenheim不等式 .     

Szasz不等式在亚正定矩阵和拟广义正定矩阵上的推广

实对称正定矩阵的Szasz不等式是Hadamard不等式的加细;本文将Szasz不等式推广到一类亚正定矩阵和拟广义正定矩阵上去,从而推广了关于实对称正定矩阵的Szasz不等式和Hadamard不等式.     

半监督距离度量学习内蕴加速投影梯度算法

考虑求解一类半监督距离度量学习问题. 由于样本集(数据库)的规模与复杂性的激增, 在考虑距离度量学习问题时, 必须考虑学习来的距离度量矩阵具有稀疏性的特点. 因此, 在现有的距离度量学习模型中, 增加了学习矩阵的稀疏约束. 为了便于模型求解, 稀疏约束应用了Frobenius 范数约束. 进一步, 通过罚函数方法将Frobenius范数约束罚到目标函数, 使得具有稀疏约束的模型转化成无约束优化问题. 为了求解问题, 提出了正定矩阵群上加速投影梯度算法, 克服了矩阵群上不能直接进行线性组合的困难, 并分析了算法的收敛性. 最后通过UCI数据库的分类问题的例子, 进行了数值实验, 数值实验的结果说明了学习矩阵的稀疏性以及加速投影梯度算法的有效性.     

参量连续代数Riccati方程对称解的两种迭代算法

基于求线性矩阵方程约束解的修正共轭梯度法,针对源于低增益反馈设计中的一类参量连续代数Riccati方程,建立求其非零对称解的两种互为补充的迭代算法,称之为变换-MCG算法和牛顿-MCG算法.在一定条件下,当Riccati方程存在可逆对称解或唯一对称正定解时,由变换-MCG算法所得对称解具备可逆性或正定性.牛顿-MCG算法仅要求Riccati方程存在非零对称解,对系数矩阵等没有附加限定,但所得对称解不能保证可逆性或正定性.数值算例表明,两种迭代算法是有效的.     

A Riemannian submersion-based approach to the Wasserstein barycenter of positive definite matrices

In this paper, we introduce a novel geometrization on the space of positive definite matrices, derived from the Riemannian submersion from the general linear group to the space of positive definite matrices, resulting in easier computation of its geometric structure. The related metric is found to be the same as a particular Wasserstein metric. Based on this metric, the Wasserstein barycenter problem is studied. To solve this problem, some schemes of the numerical computation based on gradient descent algorithms are proposed and compared. As an application, we test the k-means clustering of positive definite matrices with different choices of matrix mean.     

Computing the matrix geometric mean: Riemannian versus Euclidean conditioning,implementation techniques,and a Riemannian BFGS method

This paper addresses the problem of computing the Riemannian center of mass of a collection of symmetric positive definite matrices. We show in detail that the condition number of the Riemannian Hessian of the underlying optimization problem is never very ill conditioned in practice, which explains why the Riemannian steepest descent approach has been observed to perform well. We also show theoretically and empirically that this property is not shared by the Euclidean Hessian. We then present a limited‐memory Riemannian BFGS method to handle this computational task. We also provide methods to produce efficient numerical representations of geometric objects that are required for Riemannian optimization methods on the manifold of symmetric positive definite matrices. Through empirical results and a computational complexity analysis, we demonstrate the robust behavior of the limited‐memory Riemannian BFGS method and the efficiency of our implementation when compared to state‐of‐the‐art algorithms.     

Steepest descent preconditioning for nonlinear GMRES optimization

Steepest descent preconditioning is considered for the recently proposed nonlinear generalized minimal residual (N‐GMRES) optimization algorithm for unconstrained nonlinear optimization. Two steepest descent preconditioning variants are proposed. The first employs a line search, whereas the second employs a predefined small step. A simple global convergence proof is provided for the N‐GMRES optimization algorithm with the first steepest descent preconditioner (with line search), under mild standard conditions on the objective function and the line search processes. Steepest descent preconditioning for N‐GMRES optimization is also motivated by relating it to standard non‐preconditioned GMRES for linear systems in the case of a standard quadratic optimization problem with symmetric positive definite operator. Numerical tests on a variety of model problems show that the N‐GMRES optimization algorithm is able to very significantly accelerate convergence of stand‐alone steepest descent optimization. Moreover, performance of steepest‐descent preconditioned N‐GMRES is shown to be competitive with standard nonlinear conjugate gradient and limited‐memory Broyden–Fletcher–Goldfarb–Shanno methods for the model problems considered. These results serve to theoretically and numerically establish steepest‐descent preconditioned N‐GMRES as a general optimization method for unconstrained nonlinear optimization, with performance that appears promising compared with established techniques. In addition, it is argued that the real potential of the N‐GMRES optimization framework lies in the fact that it can make use of problem‐dependent nonlinear preconditioners that are more powerful than steepest descent (or, equivalently, N‐GMRES can be used as a simple wrapper around any other iterative optimization process to seek acceleration of that process), and this potential is illustrated with a further application example. Copyright © 2012 John Wiley & Sons, Ltd.     

Proximal point algorithm with Schur decomposition on the cone of symmetric semidefinite positive matrices

In this work, we propose a proximal algorithm for unconstrained optimization on the cone of symmetric semidefinite positive matrices. It appears to be the first in the proximal class on the set of methods that convert a Symmetric Definite Positive Optimization in Nonlinear Optimization. It replaces the main iteration of the conceptual proximal point algorithm by a sequence of nonlinear programming problems on the cone of diagonal definite positive matrices that has the structure of the positive orthant of the Euclidian vector space. We are motivated by results of the classical proximal algorithm extended to Riemannian manifolds with nonpositive sectional curvature. An important example of such a manifold is the space of symmetric definite positive matrices, where the metrics is given by the Hessian of the standard barrier function −lndet(X). Observing the obvious fact that proximal algorithms do not depend on the geodesics, we apply those ideas to develop a proximal point algorithm for convex functions in this Riemannian metric.     

Intrinsic Data Depth for Hermitian Positive Definite Matrices

Nondegenerate covariance, correlation, and spectral density matrices are necessarily symmetric or Hermitian and positive definite. This article develops statistical data depths for collections of Hermitian positive definite matrices by exploiting the geometric structure of the space as a Riemannian manifold. The depth functions allow one to naturally characterize most central or outlying matrices, but also provide a practical framework for inference in the context of samples of positive definite matrices. First, the desired properties of an intrinsic data depth function acting on the space of Hermitian positive definite matrices are presented. Second, we propose two pointwise and integrated data depth functions that satisfy each of these requirements and investigate several robustness and efficiency aspects. As an application, we construct depth-based confidence regions for the intrinsic mean of a sample of positive definite matrices, which is applied to the exploratory analysis of a collection of covariance matrices in a multicenter clinical trial. Supplementary materials and an accompanying R-package are available online.     

多步最速下降法

A_1=B_1~TAB_1是对称正定n-1阶阵,b_1是常矢量,r是常数.因而问题(1’)和问题(1)是相同的,但其空间维数较原来低了一维.反复使用这种办法,重复上述手续,可以把问题(1)化成一个一维问题。 又注意到     

An efficient algorithm for maximum entropy extension of block-circulant covariance matrices

This paper deals with maximum entropy completion of partially specified block-circulant matrices. Since positive definite symmetric circulants happen to be covariance matrices of stationary periodic processes, in particular of stationary reciprocal processes, this problem has applications in signal processing, in particular to image modeling. In fact it is strictly related to maximum likelihood estimation of bilateral AR-type representations of acausal signals subject to certain conditional independence constraints. The maximum entropy completion problem for block-circulant matrices has recently been solved by the authors, although leaving open the problem of an efficient computation of the solution. In this paper, we provide an efficient algorithm for computing its solution which compares very favorably with existing algorithms designed for positive definite matrix extension problems. The proposed algorithm benefits from the analysis of the relationship between our problem and the band-extension problem for block-Toeplitz matrices also developed in this paper.     

On the convergence of the block principal pivotal algorithm for the LCP

We show that the block principal pivot algorithm (BPPA) for the linear complementarity problem (LCP) solves the problem for a special class of matrices in at most n block principal pivot steps. We provide cycling examples for the BPPA in which the matrix is positive definite or symmetric positive definite. For LCP of order three, we prove that strict column (row) diagonal dominance is a sufficient condition to avoid cycling.     

A smoothing Newton's method for the construction of a damped vibrating system from noisy test eigendata

In this paper we consider an inverse problem for a damped vibration system from the noisy measured eigendata, where the mass, damping, and stiffness matrices are all symmetric positive‐definite matrices with the mass matrix being diagonal and the damping and stiffness matrices being tridiagonal. To take into consideration the noise in the data, the problem is formulated as a convex optimization problem involving quadratic constraints on the unknown mass, damping, and stiffness parameters. Then we propose a smoothing Newton‐type algorithm for the optimization problem, which improves a pre‐existing estimate of a solution to the inverse problem. We show that the proposed method converges both globally and quadratically. Numerical examples are also given to demonstrate the efficiency of our method. Copyright © 2008 John Wiley & Sons, Ltd.