这一节课介绍无约束问题的PVT算法，PVT算法是PVD算法的扩展，或者说是一个框架，可以在其中设计算法某些位置的参数（下面的矩阵 $A_l^i$），然后得到不同的具体的并行算法。

PVT算法流程

步骤 $0$(初始化) 令 $p$ 是并行处理机的个数，$m_l(l=1,2,\ldots,p)$ 是使得 $\sum_{l=1}^{p} m_l \geq n$的一组正整数.给定初始点 $x^{(0)} \in \mathbb{R}^n$ 且令 $i=0$.

步骤 $1$(并行计算) 对每个处理机 $l \in \{1,2,\ldots,p\}$ ，选取一个 $n\times m_l$ 矩阵 $\boldsymbol{A}^i_l$，求下列极小化问题的一个近似解 $\boldsymbol{y}^i_l \in \mathbb{R}^{m_l}$:

\[\min_{y_l \in \mathbb{R}^{m_l}} \varphi_{l}^{i}(\boldsymbol{y}_l) = f(\boldsymbol{A}^i_l \boldsymbol{y}_l + \boldsymbol{x}^{(i)}), \tag{7.1.18}\]

如果对于所有的 $l\in \{1,2,\ldots,p\}$ 都有 $\nabla \varphi_l^i(\mathbf{0})=\mathbf{0}$，则停止（关于停止条件的理解下面会谈到）.否则，转步骤 $2$.

对比PVD步骤 1

步骤 $1$ （并行计算） 对每个处理机 $l\in \{1,2,\ldots,p\}$ ，计算下面问题的一个近似解 ${(\boldsymbol{y}_ {l}^{i},\boldsymbol{\lambda}_ {\bar{l}}^{i} ) \in \mathbb{R}^{n_{l}} \times \mathbb{R}^{p-1} }$ : $$ \begin{aligned} \min_{(\boldsymbol{x}_l,\boldsymbol{\lambda}_{\bar{l}})} \psi_{l}^{i} (\boldsymbol{x}_{l},\boldsymbol{\lambda}_{\bar{l}}) &= f(\boldsymbol{x}_{l},\boldsymbol{x}_{\bar{l}}^{(i)} + \boldsymbol{D}_{\bar{l}}^{i}\boldsymbol{\lambda}_{\bar{l}}), \\ \boldsymbol{x}^{i_{l}} &= (\boldsymbol{y}_{l}^{i},\boldsymbol{x}_{\bar{l}}^{(i)} + \boldsymbol{D}_{\bar{l}}^{i}\boldsymbol{\lambda}_{\bar{l}}^{i}). \end{aligned} \notag $$

步骤 $2$(同步计算) 令 $\boldsymbol{B}^i$ 是以 $x^{(i)}$ 和 $\boldsymbol{A}_l^i \boldsymbol{y}^i_l + \boldsymbol{x}^{(i)},l=1,2\ldots,p$ 为列的 $n\times (p+1)$矩阵，求下面极小化问题的近似解 $\boldsymbol{z}^i = (z_0^i,z_1^i,\cdots,z_p^i)\in \mathbb{R}^{(p+1)}$:

\[\min_{\boldsymbol{z}\in \mathbb{R}^{(p+1)}} \psi^i(\boldsymbol{z}) = f(\boldsymbol{B}^{i} \boldsymbol{z}). \tag{7.1.19}\]

令 $\boldsymbol{x}^{(i+1)} = \boldsymbol{B}^{i} \boldsymbol{z}^i$ 且 $i=i+1$， 转回步骤 $1$.

注意到，上面的PVT算法其实是一个框架，其中变换矩阵 $\boldsymbol{A}^i$是可以变换的，为了保证收敛性，只需矩阵 $\boldsymbol{A}^i = (\boldsymbol{A}^i_1,\boldsymbol{A}^i_2,\cdots,\boldsymbol{A}^i_p)\in \mathbb{R}^{n\times(m_1+m_2+\cdots,m_p)}$ 满足下面的条件: $\forall \boldsymbol{x} \in \mathbb{R}^n$，存在与 $i$ 无关的正常数 $\beta$，对所有的 $i$ 都有 $\Vert (\boldsymbol{A}^i)^T \boldsymbol{x}\Vert \geq \beta \Vert \boldsymbol{x} \Vert$.

我们选取 ${m_l = n_l + (p-1),}$，并令

$$ \boldsymbol{A}^i_l = \left[ \begin{smallmatrix} \boldsymbol{I}_l & \mathbb{0} \\ \mathbb{0} & \boldsymbol{D}_{\bar{l}}^i \end{smallmatrix} \right] \notag $$

其中${\boldsymbol{I}_l}$ 是 ${n_l\times n_l}$ 的单位阵. 那么我们就得到了PVD算法.（可能有人会说步骤 2并不相同，下面将会解释）

这里我们讨论一下，上面这个关于矩阵 $\boldsymbol{A}^i$ 的约束，是怎么对于上述的停止条件起作用

我们知道 $\varphi^i_l(\boldsymbol{y}_l) = f(\boldsymbol{A}^i_l \boldsymbol{y}_l + \boldsymbol{x}^{(i)})$ ，其实是一个复合函数，所以我们求其梯度 $$ \nabla \varphi^i_l(\boldsymbol{y}_l) = \nabla f^T(\boldsymbol{A}^i_l \boldsymbol{y}_l + \boldsymbol{x}^{(i)}) \bullet \boldsymbol{A}^i_l$$ 根据停止条件，$\forall l\in \{1,2,\ldots,p\}$ 满足 $\nabla \varphi_l^i(\mathbf{0})=\mathbf{0}$，也就是 $\Vert (\boldsymbol{A}^i)^T \nabla f(\boldsymbol{x}^{(i)}) \Vert = \mathbf{0} $，根据 $\boldsymbol{A}^i_l$的条件，$\forall \boldsymbol{x}\in \mathbb{R}^n , \Vert (\boldsymbol{A}^i)^T \boldsymbol{x} \Vert \geq \beta \Vert \boldsymbol{x} \Vert$.因为 $\Vert (\boldsymbol{A}^i)^T \nabla f(\boldsymbol{x}^{(i)}) \Vert = \mathbf{0} $ ，即 $\nabla f(\boldsymbol{x}^{(i)})=\mathbf{0}$.

PVT的实际应用和收敛性

在求解实际问题的时候并不要求严格求解(7.1.18)和(7.1.19)，对于并行计算，只需要求

$$ \varphi^i_l (\boldsymbol{y}^i_l) \leq \varphi^i_l (\mathbb{0}) -\sigma^i_l(\left\| \nabla \varphi^i_l (\mathbb{0}) \right\|) \tag{7.1.20} $$

其中是为了强迫收敛的函数，其满足，任意非负序列 ${{t_k} \subset [0,\infty)}$，

$$ \sigma_l(t_k) \rightarrow 0 \Rightarrow t_k \rightarrow 0. $$

对于同步运算，只需要最后求解值小于最小的备选点的值即可，即

$$ \psi^i(\boldsymbol{z}^i) \leq \min_{1\leq l \leq p} \varphi^i_l (\boldsymbol{y}^i_l).\tag{7.1.21} $$

满足上面的两个条件，就可以保证PVT算法收敛，定理7.1.13。

然后课本又给出了一种具体计算 ${\boldsymbol{y}^i_l}$ 的方法，根据引理7.1.3，在附加了对目标函数 ${\boldsymbol{y}^i_l}$ 和对矩阵${\boldsymbol{A}^i_l}$ 的要求下，其满足(7.1.20)的要求，PVT算法收敛（定理7.1.14）.