Fast Calculation of Spectral Bounds for Hessian Matrices on Hyperrectangles
Fast Calculation of Spectral Bounds for Hessian Matrices on Hyperrectangles
复制标题
超矩形上 Hessian 矩阵谱界的快速计算
DOI：
--
复制
发表时间：
2011
影响因子：
1.5
通讯作者：
M. Mönnigmann
中科院分区：
文献类型：
--
作者：
M. Mönnigmann
给出了一种快速计算海森矩阵集{cal H}{谱的界的方法
超矩形$Ssubset U$上的非线性函数$varphi：子集Mathbb{R}^n omathbb{R}$的Abla^2 varphi(X)|x in S}$。新方法与现有方法的不同之处在于，它故意不使用任何区间矩阵。由于从不使用区间矩阵，因此产生了两个有趣的特征：(I)新方法只需要${cal O}(N)N(Varphi)$运算(其中$N(Varphi)$表示在其域中的一点计算$varphi$所需的运算次数)，以及(Ii)对于某些(但不是所有)函数$varphi$，新方法产生的特征值界比区间Hessian矩阵的紧界更紧。这是令人惊讶的，因为计算区间Hessian的紧特征值界的最快方法需要${cal O}(2^n)$运算。然而，要强调的是，构造例子$varphi$是很容易的，对于这些例子，所提出的方法产生的界比区间Hessian的紧界更宽松。
This paper presents a fast method for the calculation of bounds on the spectra of Hessian matrix sets ${cal H} {
abla^2 varphi(x)|x in S}$ of nonlinear functions $varphi : Usubset mathbb{R}^n omathbb{R}$ on hyperrectangles $Ssubset U$. The new method differs from existing ones in that it deliberately does not use any interval matrices. Because interval matrices are never used, two interesting features result: (i) The new method requires only ${cal O}(n) N(varphi)$ operations (where $N(varphi)$ denotes the number of operations necessary to evaluate $varphi$ at a point in its domain), and (ii) for some (but not all) functions $varphi$, the new method results in tighter eigenvalue bounds than the tight bounds for the interval Hessian matrix. This is surprising, since the fastest method for calculating the tight eigenvalue bounds for the interval Hessian requires ${cal O}(2^n)$ operations. It is stressed, however, that it is easy to construct examples $varphi$ for which the proposed method results in looser bounds than the tight bounds for the interval Hessian.