贵州大学数学与统计学院，贵州 贵阳

收稿日期：2021年5月21日；录用日期：2021年6月9日；发布日期：2021年6月25日

摘要

本文主要研究对称随机矩阵的逆特征值问题。通过将该问题转化为求两个集合交点的可行性问题，提出用交替投影法进行求解。因为其中一个集合不是凸集，关于凸可行性问题的收敛性结果不能用来分析算法的收敛性。对于算法的收敛性，本文在已有关于两个黎曼流形的交替投影算法收敛性的研究结果上，建立了交替投影算法在一定条件下的线性收敛性。最后数值例子也表明了算法的有效性。

关键词

对称随机逆特征值问题，可行性问题，交替投影算法，黎曼流形，线性收敛

Alternating Method for Symmetric Stochastic Inverse Eigenvalue Problems

Chanjuan Dang, Xiangmei Wang^*

School of Mathematics and Statistics, Guizhou University, Guiyang Guizhou

Received: May 21^st, 2021; accepted: Jun. 9^th, 2021; published: Jun. 25^th, 2021

ABSTRACT

The symmetric stochastic inverse eigenvalue problem (StIEP) is considered. By reformulating it into a feasibility problem of two sets, the alternating method is proposed for solving it. Since one of the sets is not convex, the convergence analysis technique for the convex cases does not work. For the convergence of the algorithm, this paper establishes the linear convergence of the alternating projection algorithm under certain conditions on the existing results on the convergence of the alternating projection algorithms for two Riemannian manifolds. At last, some numerical experiments are provided to illustrate the efficiency of the method.

Keywords:Symmetric Stochastic Inverse Eigenvalue Problem, Feasibility Problem, Alternating Method, Riemannian Manifold, Linear Convergence

Copyright © 2021 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

求一个 $n$ 阶非负矩阵(所有元素都是非负数)，使得它的特征值是给定的 $n$ 个常数 ${\lambda }_i\left(i=1,\cdots ,n\right)$ 的问题称为非负逆特征值问题(简称 $NIEP$ )。 $NIEP$ 在很多领域有广泛的应用，例如在博弈论，数值分析，数据分析，群论和经济学等领域中，详见( [1] - [20] )及其参考文献。1937年Kolmogorov [1] 提出逆特征值问题：一个复数 $z$ 何时为某个非负矩阵的特征值的问题？后来，Suleimanova ( [2] )在1949年提出了更一般的非负逆特征值问题，并证明了当 $\left\{{\lambda }_i\right\}$ 中只有一个数大于0 (其他数小于等于0)时， $NIEP$ 有解的充分必要条件是这些数的和大于0。此后， $NIEP$ 有解的充分和必要条件一直是学者们研究的热点问题之一。一些学者研究了 $NIEP$ 有解的必要条件，取得了一些重要的研究成果。例如，Loewy和Johnson ( [3] )、Johnson ( [4] )建立了 $NIEP$ 有解的四个必要条件。1998年，Laffey和Meehan给出了奇数阶非负矩阵迹为零的必要条件。此外，一些学者对低阶的情形进行研究，1978年Loewy和Londow给出了 $n=3$ 时， $NIEP$ 有解的四个充分必要条件。此外，1996年Reams解决了 $n=4$ 时非负矩阵迹为零的问题，1999年Laffey和Meehan解决了 $n=5$ 时同样的问题(详见 [5] )。其他研究成果参考( [6] - [20] )及其参考文献。

本文主要关注求解 $NIEP$ 的有效算法。据我们所知，目前关于 $NIEP$ 的算法并不多，主要有梯度流下降算法，交替投影算法，非光滑牛顿法以及共轭梯度法。在 [21] 中，Chu和Guo将 $NIEP$ 转化为以下优化问题：

$\underset{P,R\in R^{n\times n}}{\min }F\left(P,R\right)=\frac{1}{2}{\Vert P\Lambda P^{-1}-R\circ R\Vert }^2$, (1.1)

其中 $\Lambda$ 是以给定的 $n$ 个常数为主对角元的 $n$ 阶对角矩阵，“ $\circ$ ”表示Hadamard积(详见 [21] )。他们提出了求解问题(1.1)的基于微分方程的梯度流下降算法，并通过一些应用说明了算法的有效性。文献 [22] 中，Orsi将 $NIEP$ 转化为含两个集合的可行性问题：

求 $X\in E\cap N$ (1.2)

其中 $E$ 是以给定的 $n$ 个常数为特征值的 $n$ 阶实对称矩阵集合， $N$ 是 $n$ 阶非负矩阵的集合。在 [22] 中，Orsi给出了集合 $E$ 上的投影算子的计算式，并提出了求解 $NIEP$ (即问题(1.2))的交替投影算法(交替地在集合 $E$ 和 $N$ 上进行投影)。因为集合 $E$ 不是凸集，所以问题(1.2)不是凸可行问题。关于非凸的可行性问题的交替投影算法的收敛性分析非常困难，收敛性结果也非常少。在 [22] 中，作者证明了当 $E\cap \mathrm{int}N\ne \varphi$，且迭代点充分接近 $x\in E\cap \mathrm{int}N$ 时，算法再经过一次迭代得到的 $NIEP$ 解，其中 $\mathrm{int}N$ 是集合 $N$ 的内点集。类似地假设条件也被用在 [23] 算法的分析中。此外，参考文献 [24] 和 [25] 研究了已知部分特征对的 $NIEP$ 问题的算法，即已知矩阵的部分特征值及其特征向量，求一个非负矩阵。这两篇文献分别通过将这类问题转化为欧氏空间和黎曼流形上的优化问题进行求解。 [24] 提出了求解该问题的非光滑牛顿法，并证明了算法的二阶收敛性； [25] 中提出求解该问题的黎曼流形上的共轭梯度法，并证明了算法的收敛性。

本文主要研究一类特殊的 $NIEP$ 问题的数值算法——对称随机逆特征值问题(简称 $StIEP$ )，即求解一个对称随机矩阵(行/列和为1的非负实对称矩阵)，使得它的特征值是给定的 $n$ 个常数。受 [22] 启发，我们将问题转化为含两个集合的可行性问题：

$求X\in E\cap F$ (1.3)

其中集合 $E$ 的定义同问题(1.2)，集合 $F$ 是双随机矩阵集合(即行和、列和均为1的非负矩阵)，并提出交替投影算法进行求解。在算法运行中，我们采用 [22] 中计算式计算集合 $E$ 上投影 $P_E(\cdot )$，而集合 $F$ 上的投影 $P_F(\cdot )$，我们采用同时投影的子迭代计算，详见算法3.2。正如我们在上面提到集合 $E$ 不是凸集，所以问题(1.3)也是非凸可行性问题，凸可行问题的交替投影算法的收敛性分析方法不能用来分析算法的收敛性。注意到集合 $F$ 没有内点，不满足 [22] 中的假设条件： $E\cap \mathrm{int}N\ne \varphi$。所以这一假设条件不能用来分析求解问题(1.3) (即 $StIEP$ )的交替投影算法的收敛性。注意到Lewis在( [26], Theorem 13)中研究了当两个集合在解的附近是光滑黎曼流形时(不一定是凸集)，交替投影算法的收敛性，并建立了算法线性收敛性条件。结合集合 $E$ 和 $F$ 的特性以及对算法产生的迭代点列的分析(注意集合 $F$ 并不是黎曼流形)，用 [26] 中的结论建立了交替投影算法线性收敛的条件。

本文结构如下。第一节是预备知识，包括一些记号，概念和一些重要引理。论文的主要结果在第二节，我们提出求解 $StIEP$ 的交替投影算法，给出了一些集合上投影的计算式，并建立了算法线性收敛的条件。第三节的数值实验结果表明交替投影算法是有效的算法。最后是对本文的总结以及展望。

2. 预备知识

这一节介绍本文用到的一些记号，概念和重要引理。设 $R^n$，$R^{n\times n}$ 分别表示实数域上的 $n$ 维向量， $n$ 阶方阵构成的欧氏空间。设 $E\subset R^{n\times n}$ 是 $R^{n\times n}$ 中子集，点 $X\in R^{n\times n}$ 到集合 $E$ 的距离和投影分别记为 $d_E(\cdot )$ 和 $P_E(\cdot )$，即 $d_E\left(X\right)=\underset{Y\in E}{\inf }\Vert X-Y\Vert$，

$P_E\left(X\right)=\underset{Y\in E}{Arg\min }\Vert X-Y\Vert =\left\{Y\in E|d_E\left(X\right)=\Vert X-Y\Vert \right\}$,

其中 $\Vert \Vert$ 表示 $R^{n\times n}$ 中的 $F-$ 范数。

下面介绍黎曼流形上一些概念和结论，关于黎曼流形更多的结果可以参考( [27] [28] [29] [30] )。设 $f:R^{n\times n}\to R^d$ 为定义在 $R^{n\times n}$ 上的光滑函数，其中 $d$ 是正整数。设 $X\in R^{n\times n}$，函数 $f$ 在点 $X$ 处的Jacobi矩阵记为 $Jf\left(X\right)$。

定义2.1 设 $M\subset R^{n\times n}$ 是 $R^{n\times n}$ 中子集， $X\in M$。我们称 $M$ 在点 $X$ 附近是光滑黎曼流形，如果存在光滑函数 $f:R^{n\times n}\to R^d$ 和 $X$ 的邻域 $U$，使得 $Jf$ 在 $U$ 上是满射且以下式子成立：

$M\cap U:=\left\{Y\in U:f\left(Y\right)=0\right\}$.

设 $M$ 在点 $X$ 附近是光滑黎曼流形， $M$ 在点 $X\in M$ 处的切空间记为 $T_{X}M$。则有

$T_{X}M=\ker Jf\left(X\right):=\left\{Z\in R^{n\times n},\langle Z,Jf\left(X\right)\rangle =0\right\}$,

其中 $\langle \cdot ,\cdot \rangle$ 是 $R^{n\times n}$ 中内积，即

$\langle A,B\rangle =trace\left(A^{\text{T}}B\right),\forall A,B\in R^{n\times n}$.

当 $M$ 和 $N$ 都是 $R^{n\times n}$ 中光滑子流形时，Lewis在 [26] 中证明了以下求这两个集合交点的交替投影算法的线性收敛性，它在我们后面算法收敛性分析中非常重要。需要指出的是，以下引理将( [26]，Theorem 13)中的假设条件：

$T_M\left(\bar{X}\right)+T_N\left(\bar{X}\right)=R^{n\times n}.$ (2.1)

减弱为

$T_{M\cap N}\left(\bar{X}\right)=T_M\left(\bar{X}\right)\cap T_N\left(\bar{X}\right).$ (2.2)

(注意(2.1) $\Rightarrow$ (2.2), 见 [30] )，这是仔细检查( [26]，Theorem 13)的证明得到的(也见 [30] )。同时，由( [26]，Theorem 13)的证明也有下面(2.3)成立。

引理2.1 ( [26]，Theorem 13)设 $M,N\in R^{n\times n}$，点 $\bar{X}\in M\cap N$。设 $M$ 和 $N$ 在点 $\bar{X}$ 附近都是光滑黎曼流形，且满足(2.2)。设 $\left\{X_k\right\}$ 是由以下交替投影法产生的点列，即

$X_{k+1}:=P_N{P}_M\left(X_k\right),\forall k=0,1,\cdots$.

则存在 $\delta >\delta \text{'}>0$，使得当初始点 $X_0\in U\left(\bar{X},{\delta }^{\prime }\right)$ 时，点列 $\left\{X_k\right\}$ 满足

$\left\{X_k\right\}\subset U\left(\bar{X},\delta \right)$, (2.3)

且线性收敛到 $M\cap N$ 中一点 $X^{\ast }$，即存在 $\alpha \in R$，$c\in \left(0,1\right)$，使得 $\Vert X_k-X^{*}\Vert \le \alpha c^k,k=1,2,\cdots$。

3. 交替投影算法及收敛性分

3.1. StIEP及投影的计算

设 $\lambda :=\left\{{\lambda }_1,{\lambda }_2，\cdots ,{\lambda }_n\right\}$ 是给定的 $n$ 个实数。考虑对称随机逆特征值问题( $StIEP$ )，即求一个 $n$ 阶对称随机矩阵 $X\in R^{n\times n}$，使得它的特征值是 $\lambda$。不失一般性，设 ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$，并记对角阵 $\Lambda$ 为

$\Lambda =diag\left({\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n\right)$，即

$diag\left(\lambda \right)=\left[\begin{array}{cccc}{\lambda }_1& 0& \cdots & 0\\ 0& {\lambda }_2& \cdots & 0\\ ⋮& ⋮& ⋮& ⋮\\ 0& 0& \cdots & {\lambda }_n\end{array}\right].$

在 $R^{n\times n}$ 中定义以下集合 $E$，$F$ 和 $F_1$ 如下：

$E:=\left\{A\in R^{n\times n}|A=V\Lambda V^{\text{T}},V\in {\text{R}}^{n\times n}是正交矩阵\right\}$,

$F:=\left\{A\in R^{n\times n}|A^{\text{T}}=A,{\displaystyle \underset{j=1}{\overset{n}{\sum }}{A}_{ij}}=1,A_{ij}\ge 0,i,j=1,2,\cdots ,n\right\}$

$F_1:=\left\{A\in R^{n\times n}|{\displaystyle \underset{j=1}{\overset{n}{\sum }}{A}_{ij}}=1,A_{ij}\ge 0,i,j=1,2,\cdots ,n\right\},$

其中 $B^{\text{T}}$ 表示矩阵 $B\in R^{n\times n}$ 的转置， $A_{ij}$ 表示矩阵 $A$ 的第 $i$ 行第 $j$ 列元素。下面我们先讨论集合 $E$ 和 $F_1$ 上投影算子 $P_E(\cdot )$ 和 $P_{F_1}(\cdot )$ 的计算。首先，我们有以下关于 $P_E(\cdot )$ 的计算式。

引理3.1 ( [22],Theorem 3.2) 设实对称矩阵 $Y\in R^{n\times n}$ 的正交分解为 $Y=Vdiag\left({\mu }_1,\cdots ,{\mu }_n\right)V^{{\rm T}}$，其中 ${\mu }_1\ge \cdots \ge {\mu }_n$。则 $P_E\left(Y\right)=V\Lambda V^{{\rm T}}$。

下面讨论 $P_{F_1}(\cdot )$，为此设向量 $a={\left(a_1,\cdots ,a_n\right)}^{{\rm T}}$。考虑以下严格凸优化问题：

$\begin{array}{l}\underset{x\in R^n}{\min }\frac{1}{2}{\Vert x-a\Vert }_2^2\\ \mathrm{s}.t{.}_{}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{x}_i}=1,\\ -x_i\le 0,i=1,\cdots ,n,\end{array}$ (3.1)

其中 ${\Vert \Vert }_{\text{2}}$ 表示 $R^n$ 中的 $\text{2}-$ 范数。设 $x_a^{*}=\left({\left(x_a^{*}\right)}_i\right)\in R^n$ 为问题(3.1)的唯一全局最优解，同时也是它的唯一KKT点。所以存在 ${\lambda }^{*}=\left({\lambda }_i^{*}\right)\in R^n,{\mu }^{*}\in R$，满足以下KKT条件：

$\{\begin{array}{l}{x}_a^{*}-a-{\mu }^{*}e-{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i^{*}{e}_i=0,(3.2)}\\ {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\left(x_a^{*}\right)}_i=1,(3.3)}\\ {\left(x_a^{*}\right)}_i\ge 0,{\lambda }_i^{*}\ge 0,{\left(x_a^{*}\right)}_i{\lambda }_i^{*}=0,i=1,\cdots ,n,(\; 3.4\; )\end{array}$

其中 $e=\left(1,\cdots ,1\right)$，$e_i=\left(0,\cdots 0,1,0,\cdots ,0\right)\in R^n,\left(第i个分量为1,其他为0\right)$。为了方便运算，我们设向量的 $a$ 分量满足 $a_1\le a_2\le \cdots \le a_n$。

引理3.2 设向量 $a$ 的分量满足 $a_1\le a_2\le \cdots \le a_n$，则问题(3.1)的唯一最优解为：

$x_a^{*}=\left(\text{0,}\cdots ,\text{0},b_{l+1}+\frac{1}{n-l}{\displaystyle \underset{j=1}{\overset{l}{\sum }}{b}_j},\cdots ,b_n+\frac{1}{n-l}{\displaystyle \underset{j=1}{\overset{l}{\sum }}{b}_j}\right),$ (3.5)

其中对任意 $i=1,\cdots ,n$，$b_i=a_i+\frac{1}{n}-\frac{1}{n}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{a}_i}$，$c_i=b_i+\frac{1}{n-i+1}{\displaystyle \underset{j=1}{\overset{i-1}{\sum }}{b}_j}$，$l\in \left\{0,1,\cdots ,n-1\right\}$ 使得 $c_i\le 0_{}^{}\left(\forall i\le l\right)$ 且 $c_{l+1}>0$。

证明由 $\left\{b_i\right\}$ 和 $\left\{c_i\right\}$ 的定义，容易证明

$b_1\le \cdots \le b_n,$ (3.6)

且存在 $l\in \left\{0,1,\cdots ,n-1\right\}$，使得 $c_i\le 0_{}^{}\left(\forall i\le l\right)$，且 $c_{l+1}>0$，令

${\left(x_a^{*}\right)}_i=\{\begin{array}{l}0,\begin{array}{c}\end{array}\begin{array}{c}\end{array}\begin{array}{c}\end{array}\begin{array}{c}\end{array}\begin{array}{c}\end{array}\begin{array}{c}\end{array}\begin{array}{c}\end{array}\begin{array}{c}\end{array}\begin{array}{c}\end{array}\begin{array}{c}\end{array}i\le l,\\ b_i+\frac{1}{n-l}{\displaystyle \underset{j=1}{\overset{l}{\sum }}{b}_j},\begin{array}{c}\end{array}i\ge l+1.\end{array}$ (3.7)

${\lambda }_i^{*}=\{\begin{array}{l}-b_i-\frac{1}{n-l}{\displaystyle \underset{j=1}{\overset{l}{\sum }}{b}_j},\begin{array}{c}\end{array}i\le l,\\ 0,\begin{array}{c}\end{array}\begin{array}{c}\end{array}\begin{array}{c}\end{array}\begin{array}{c}\end{array}\begin{array}{c}\end{array}\begin{array}{c}\end{array}\begin{array}{c}\end{array}\begin{array}{c}\end{array}\begin{array}{c}\end{array}\begin{array}{c}\end{array}\begin{array}{c}\end{array}i\ge l+1.\end{array}$ (3.8)

下面验证 $x_a^{*},{\lambda }^{*}$ 满足KKT条件(3.2)~(3.4)。首先，我们有

${\lambda }_i^{*}\cdot {\left(x_a^{*}\right)}_i=0,\forall i=1,\cdots ,n.$

另外，由(3.6)，显然有 ${\lambda }_1^{*}\ge {\lambda }_2^{*}\ge \cdots \ge {\lambda }_l^{*}$。要证 ${\lambda }_i^{*}\ge 0\left(i=1,2,\cdots ,n\right)$，只需证明 ${\lambda }_l\ge 0$。根据 $l$ 的定义，有 $c_i\le 0$。于是由(3.8)有：

$\begin{array}{l}{\lambda }_{{}_l}^{*}=-b_l-\frac{1}{n-l}{\displaystyle \underset{j=1}{\overset{l}{\sum }}{b}_j}\\ {{\displaystyle }}_{}^{}=-b_l-\frac{1}{n-l+1}{\displaystyle \underset{j=1}{\overset{l-1}{\sum }}{b}_j}+\frac{1}{n-l+1}{\displaystyle \underset{j=1}{\overset{l-1}{\sum }}{b}_j}-\frac{1}{n-l}{\displaystyle \underset{j=1}{\overset{l}{\sum }}{b}_j}\\ {{\displaystyle }}_{}^{}=-c_l-\frac{1}{n-l}{c}_l\ge 0.\end{array}$

下面证明 ${\left(x_a^{*}\right)}_i\ge 0\left(i=1,2,\cdots ,n\right)$。类似地，由(3.6)和(3.7)，显然有 ${\left(x_a^{*}\right)}_{l+1}\le {\left(x_a^{*}\right)}_{l+2}\le \cdots \le {\left(x_a^{*}\right)}_n$，所以只需证明 ${\left(x_a^{*}\right)}_{l+1}\ge 0$。根据 $l$ 的定义，有 $c_{l+1}>0$。又 $\left\{b_i\right\}$ 单调不减，我们有

${\left(x_a^{*}\right)}_{l+1}=b_{l+1}+\frac{1}{n-l}{\displaystyle \underset{j=1}{\overset{l}{\sum }}{b}_j}=c_{l+1}>0.$

所以 $x_a^{*},{\lambda }_a^{*}$ 满足KKT条件(3.4)。又

${\displaystyle \underset{i=1}{\overset{n}{\sum }}{\left(x_a^{*}\right)}_i}={\displaystyle \underset{i=1}{\overset{l}{\sum }}{\left(x_a^{*}\right)}_i}+{\displaystyle \underset{i=l+1}{\overset{n}{\sum }}{\left(x_a^{*}\right)}_i}={\displaystyle \underset{i=l+1}{\overset{n}{\sum }}{b}_i}=1.$

所以(3.3)成立。令

${\mu }^{*}=\{\begin{array}{l}-a_i-{\displaystyle \underset{i=1}{\overset{n}{\sum }}\left(-b_i-\frac{1}{n-l}{\displaystyle \underset{j=1}{\overset{l}{\sum }}{b}_j}\right)},i\le l,\\ b_i+\frac{1}{n-l}{\displaystyle \underset{j=1}{\overset{l}{\sum }}{b}_j-a_i,{{\displaystyle }}_{}^{}{{\displaystyle }}_{}^{}{{\displaystyle }}_{}^{}{{\displaystyle }}_{}^{}i\ge l+1.}\end{array}$

则有

${\left(x_a^{*}\right)}_i-a_i-{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i^{*}}-{\mu }^{*}=\{\begin{array}{l}{b}_i+\frac{1}{n-l}{\displaystyle \underset{j=1}{\overset{l}{\sum }}{b}_j}-a_i-\left(b_i+\frac{1}{n-l}{\displaystyle \underset{j=1}{\overset{l}{\sum }}{b}_j-a_i}\right)=0,i\ge l+1,\\ 0-a_i+a_i+{\displaystyle \underset{i=1}{\overset{n}{\sum }}\left(-b_i-\frac{1}{n-l}{\displaystyle \underset{j=1}{\overset{l}{\sum }}{b}_j}\right)-{\displaystyle \underset{i=1}{\overset{n}{\sum }}\left(-b_i-\frac{1}{n-l}{\displaystyle \underset{j=1}{\overset{l}{\sum }}{b}_j}\right)}=0,i\le l+1}.\end{array}$

即

$x_a^{*}-a-{\mu }^{\text{*}}e-{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i^{*}{e}_i}=0.$

所以 $x_a^{*},{\lambda }^{*}$ 满足KKT条件(3.2)。综上， $x_a^{*}$ 是问题(3.1)的KKT点，从而是问题(3.1)最优解。

注 3.1 如果向量 $a$ 的分量不满足 $a_1\le a_2\le \cdots \le a_n$，可以先将 $a$ 的分量按从小到大顺序排列，记为向量 $\bar{a}$。设 $x_{\bar{a}}^{\ast }$ 是由(3.5)定义的向量， $x_a^{\ast }$ 是 $x_{\bar{a}}^{\ast }$ 按照分量所在位置还原后得到的向量。则 $x_a^{\ast }$ 是问题(3.1)的唯一最优解。

结合引理3.2和注3.1，将矩阵 $X\in R^{n\times n}$ 按行分块，即 $X=\left(\begin{array}{l}{X}_1^{{\rm T}}\\ X_2^{{\rm T}}\\ ⋮\\ X_n^{{\rm T}}\end{array}\right)$，则 $X$ 在集合 $F_1$ 上的投影 $P_{F_1}(\cdot )$ 有以下表达式，其中 $x_{X_i^{\text{T}}}^{\ast }$ 是按注3.1中计算，即先将 $X_i^{\text{T}}$ 的分量按从小到大排序得到 $\overline{X_i^{\text{T}}}$，再令 $a:=\overline{X_i^{\text{T}}}$ 按(3.5)计算后，排回原来的位置得到。

引理 3.3 设 $X\in R^{n\times n}$，且 $X$ 按行分块为 $X=\left(\begin{array}{l}{X}_1^{{\rm T}}\\ X_2^{{\rm T}}\\ ⋮\\ X_n^{{\rm T}}\end{array}\right)$，则 $X$ 在集合 $F_1$ 上的投影为 $P_{F1}\left(X\right)=\left(\begin{array}{l}{\left(x_{X_1^{\text{T}}}^{\ast }\right)}^{\text{T}}\\ {\left(x_{X_2^{\text{T}}}^{\ast }\right)}^{\text{T}}\\ ⋮\\ {\left(x_{X_n^{\text{T}}}^{\ast }\right)}^{\text{T}}\end{array}\right)$。

3.2. 交替投影算法及收敛性分析

显然 $StIEP$ 等价于可行性问题(1.3)，即求 $X\in E\cap F$。我们提出以下求解 $StIEP$ 的交替投影算法。

交替投影算法3.1

交替投影算法1要计算两个集合 $E$ 和 $F$ 上的投影，其中 $P_E(\cdot )$ 按引理3.1计算，而 $P_F(\cdot )$ 用同时投影算法计算，具体见以下交替投影算法3.2和注3.2。

交替投影算法3.2

注 3.2 交替投影算法3.2给出了投影的计算式。由引理3.1，Step 4计算了 $P_E\left(W_k\right)$，即 $P_E\left(W_k\right):=X_{k+1}$。而算法的Steps 2-3用同时投影算法计算 $P_F\left(X_k\right)$。事实上，记

$F_2:=\left\{A\in R^{n\times n}|{\displaystyle \underset{i=1}{\overset{n}{\sum }}{A}_{ij}}=1,A_{ij}\ge 0,i,j=1,2,\cdots ,n\right\}.$

则 $P_F\left(X\right)=P_{F_1\cap F_2}\left(X\right)$，且容易验证 $P_{F_2}(X)={\left(P_{F_1}(X)\right)}^{\text{T}}$。所以交替投影算法3.2的Steps 3-4实际上是子迭代：

$Y_{k,l+1}:=\frac{P_{F_1}\left(Y_{k,l}\right)+P_{F_2}\left(Y_{k,l}\right)}{2}\forall l\in 0,1,\cdots ,$ (3.9)

直到满足精度要求 $\Vert Y_{k,l}-Y_{k,l+1}\Vert <{\epsilon }_2$。因为集合 $F_1$ 和 $F_2$ 都是多面体，求解凸可行问题：求 $X\in F_1\cap F_2$ 的同时投影算法(3.9)是线性收敛的(见 [30]，Corollary 3.14)，所以交替投影算法2的Steps 2-3迭代的次数不多。

下面我们分析交替投影算法3.1的收敛性。因为集合 $E$ 不是凸集，所以凸可行性问题的研究方法不能用来分析交替投影算法3.1的收敛性。我们将用 [22] 中的求两个黎曼子流形交点的交替投影算法的收敛性研究结果进行研究。因为集合 $F$ 不是 $R^{n\times n}$ 的子流形。为此，我们定义集合 $F^{\circ }$ 如下：

$F^{\circ }:=\left\{A\in R^{n\times n}|A=A^{\text{T}},{\displaystyle \underset{j=1}{\overset{n}{\sum }}{A}_{ij}}=1,A_{ij}>0,i,j=1,2,\cdots ,n\right\}.$

由集合 $F^{\circ }$ 的定义，对任意 $X\in F^{\circ }$，存在点 $X$ 的邻域 $U\left(X\right)$ 使得

$F^{\circ }\cap U\left(X\right):=\left\{A\in U\left(X\right)|A_{ij}=A_{ji},{\displaystyle \underset{j=1}{\overset{n}{\sum }}{A}_{ij}}=1,i,j=1,2,\cdots ,n\right\}$.

由定义2.1容易验证以下结论。

引理 3.4 $F^{\circ }$ 在任意点 $X\in F^{\circ }$ 附近是光滑黎曼流形。

关于集合 $E$，由定义知对任意 $X\in E$，$\lambda :=\left\{{\lambda }_1,{\lambda }_2，\cdots ,{\lambda }_n\right\}$ 是它的 $n$ 个特征值，即 ${\lambda }_1,{\lambda }_2，\cdots ,{\lambda }_n$ 是关于 $\lambda$ 的 $n$ 次方程 $\left|\lambda I-X\right|=0$ 的 $n$ 个根，其中 $I$ 是 $n$ 阶单位阵。由根与系数的关系以及集合 $E$ 的定义有

$E:=\left\{A\in R^{n\times n}|A_{ij}=A_{ji},f\left(A\right)=0{\text{,}}_{}^{}i,j=1,2,\cdots ,n\right\}$,

其中 $f:R^{n\times n}\to R^n$ 是定义在 $R^{n\times n}$ 上的多项式函数。设 $\bar{X}\in E\cap F^{\circ }$，下面的讨论需要用到以下假设：

$E$ 在点 $\bar{X}$ 附近是光滑黎曼流形，且满足

$T_{E\cap F^{\circ }}\left(\bar{X}\right)=T_E\left(\bar{X}\right)\cap T_{F^{\circ }}\left(\bar{X}\right)$.(3.10)

下面仅对当 $n=2$ 时，说明 $E$ 在任意点 $\bar{X}\in E\cap F^{\circ }$ 附近是光滑黎曼流形，而当 $n>2$ 时，类似地可以知道很多情形下相同的结论也成立。事实上容易验证， $n=2$ 时 $StIEP$ 有解(即 $E\cap F\ne \varnothing$ )的充分必要条件是 $\lambda =\left\{1,t\right\}$，其中 $t\in [-1,1]$，且解为 $X^{*}:=\left[\begin{array}{cc}\frac{1}{2}+\frac{t}{2}& \frac{1}{2}-\frac{t}{2}\\ \frac{1}{2}-\frac{t}{2}& \frac{1}{2}+\frac{t}{2}\end{array}\right]$。而当 $t\in \left(-1,1\right)$ 时， $E\cap F^o\ne \varnothing$。设 $t\in \left(-1,1\right)$，$\bar{X}=\left[\begin{array}{cc}\frac{1}{2}+\frac{t}{2}& \frac{1}{2}-\frac{t}{2}\\ \frac{1}{2}-\frac{t}{2}& \frac{1}{2}+\frac{t}{2}\end{array}\right]\in E\cap F^{\circ }$，并记

$E:=\left\{A\in R^{n\times n}|A_{12}=A_{21},A_{11}+A_{22}=1+t,A_{11}{A}_{22}-A_{12}{A}_{21}=t\right\}=\left\{A\in R^{n\times n}|g\left(A\right)=0\right\}$.

直接计算知 $Jg\left(\bar{X}\right)$ 满秩，所以由定义2.1， $E$ 在点 $\bar{X}$ 附近是光滑黎曼流形。

考虑以下可行性问题：

$求X\in E\cap F^{\circ }$. (3.11)

由引理2.1和引理3.4，有以下结论(其中 $M:=F^0,N:=E$ )。

引理 3.5 设 $\bar{x}\in E\cap F^{\circ }$ 满足假设(3.10)。设 $\left\{X_k\right\}$ 是由以下交替投影法产生的点列，即

$X_{k+1}:=P_E{P}_{F^0}\left(X_k\right)\forall k=0,1,\cdots$. (3.12)

则存在 $\delta >{\delta }^{\prime }>0$，使得当初始点 $X_0\in U\left(\bar{X},{\delta }^{\prime }\right)$ 时，点列 $\left\{X_k\right\}$ 满足 $\left\{X_k\right\}\subset U\left(\bar{X},\delta \right)$，且线性收敛到 $E\cap F^{\circ }$ 中一点 $X^{\ast }$。

关于交替投影算法3.1，我们有以下线性收敛的结论。

定理 3.1设 $\bar{X}\in E\cap F^{\circ }$ 满足假设(3.10)。则当初始点 $X_0$ 充分接近 $\bar{X}$ 时，交替投影算法3.1产生的点列 $\left\{X_k\right\}$ 线性收敛到 $E\cap F$ 中一点。

证明 设 $\left\{{\tilde{X}}_k\right\}$ 是以 $X_0$ 为初始点(即 ${\tilde{X}}_0=X_0$ )，用交替投影算法(3.12)产生的点列。由引理3.5，存在 $\delta >{\delta }^{\prime }>0$，使得当初始点 $X_0\in U\left(\bar{X},{\delta }^{\prime }\right)$ 时，点列 $\left\{{\tilde{X}}_k\right\}$ 满足 $\left\{{\tilde{X}}_k\right\}\subset U\left(\bar{X},\delta \right)$，且线性收敛到 $E\cap F^{\circ }\left(\subset E\cap F\right)$ 中一点。所以，要证明定理的结论，只需证明当初始点 $X_0$ 充分接近 $\bar{X}$ 时，算法3.1和算法(3.12)产生相同的点列，即 $\left\{X_k\right\}$ 和 $\left\{{\tilde{X}}_k\right\}$ 相同。设 $\bar{X}$ 到集合 $F$ 的边界 $\partial F:=F\backslash F^{\circ }$ 的距离为 $d_0$，则由 $F^{\circ }$ 的定义知 $d_0>0$。不妨设 $\delta <\frac{d_0}{2}$ (否则取更小的 $\delta$ 即可)。因为 $\bar{X}\in E\cap F^{\circ }\subset E\cap F$，所以对任意 $X\in U\left(\bar{X},\delta \right)$，我们有 $P_F\left(X\right)=P_{F^{\circ }}\left(X\right)$。注意到 ${\tilde{X}}_0=X_0$ 和 $\left\{{\tilde{X}}_k\right\}\subset U\left(\bar{X},\delta \right)$，容易得到算法3.1和算法(3.12)产生相同的点列。证毕。

4. 数值实验

本节我们用交替投影算法3.2求解StIEP问题。在数值实验中，初始值 $X_0\in R^{n\times n}$ 为随机产生的 $n$ 阶矩阵，iter和time(s)分别表示算法的迭代次数和CPU运行时间(单位为秒)。在每次实验时，我们先随机生成 $n$ 阶对称随机矩阵 $A$，并求出矩阵 $A$ 的 $n$ 个特征值作为 $\lambda$。然后用交替投影算法3.2进行求解。算法采用 $\text{Matlab}\text{R2018b}$ 实现，实验结果如下。

例给定 $5\times 5$ 阶矩阵的特征值为

$\lambda =\left\{\text{1}\text{.0000},\text{0}\text{.0021,0}\text{.0051,0}\text{.0954,0}\text{.1004}\right\}$.

用算法3.2求一个 $5\times 5$ 阶对称双随机矩阵 $X$，使其特征值为 $\lambda$。算法中的 ${\epsilon }_1$ 和 ${\epsilon }_2$ 分别取作 ${10}^{-}{}^{14}$ 和 ${10}^{-5}$，实验结果为：

$X=\left[\begin{array}{l}0.94350.00660.00580.02360.0205\hfill \\ 0.00660.95010.01650.01230.0145\hfill \\ 0.00580.01650.95240.00350.0218\hfill \\ 0.02360.01230.00350.95100.0096\hfill \\ 0.02050.01450.02180.00960.9336\hfill \end{array}\right]$.

更高阶的数值实验结果见表1，其中 $n$ 是矩阵的阶数，iter和time(s)是实验10次的平均迭代次数和时间。

表1. 不同阶数的实验结果

5. 结论

对称随机逆特征值问题( $StIEP$ )是非负逆特征值问题( $NIEP$ )的一种特殊情形，通过将问题转化为可行性问题，本文提出的交替投影算法。因为该问题不是凸可行性问题，其收敛性分析非常困难。我们运用黎曼流形上可行性问题的线性收敛分析结果，在一定条件下建立算法的线性收敛性。未来我们将继续研究交替投影法求解其他 $NIEP$ 问题，同时进一步研究非凸可行性问题的交替投影算法的收敛性条件。

基金项目

本研究受国家自然科学基金项目(11661019)资助，在此表示感谢。

文章引用

党婵娟,王湘美. 交替投影法求解对称随机逆特征值问题
Alternating Method for Symmetric Stochastic Inverse Eigenvalue Problems[J]. 应用数学进展, 2021, 10(06): 2206-2216. https://doi.org/10.12677/AAM.2021.106230

参考文献