基于数值实验的邻近点算法收敛速度研究

王从徐

（滁州城市职业学院 教育系，安徽 滁州 239000）

0 引言

在数值计算中，往往需要考虑求解无约束优化问题[1]：.如果使用迭代法求解此类问题，基本思想是先给定一个初始点，通过某种迭代规则产生一个迭代序列{xk}，使得如果该序列是收敛的，那么这个极限点就是问题的最小值[2].邻近点算法是求解最优化问题的迭代算法之一，特别适合求解具有特殊结构的优化问题[3].例如，在图像处理中，问题规模（变量个数）往往在百万以上，传统算法基本无法处理，但如果使用邻近点算法或与其紧密相关的迭代收缩阈值算法，可以快速有效地处理此类问题，而且输出的结果精度较高[4，5]；在传统压缩感知问题中算法重构质量较差，时间复杂度大，通过引入阈值和正则化参数的邻近点算法，逐步迭代恢复图像信号，具有加快收敛速度和改善重构质量的效果[6].在实际应用中表明，邻近点算法及其改进算法可以减少运算时间，加快收敛速度[7].本研究通过数值实验研究和分析该算法在不同的参数设置、不同的实验问题下收敛速度和计算时间的变化，获得初步结论.

1 相关方法与原理概述

1.1 最优化模型

最优化问题，常见的数学规划的数学模型为：

式中：f（x），hi（x）（i=1，…，l）以及gi（x）（i=1，…，m）都是定义在Rn上连续可微的多元实值函数.记E={i：hi（x）=0}，I={i：gi（x）≥0}，若E∪I=Ø，称之为无约束优化问题，否则称为约束优化问题.其中f（x）称为目标函数，hi（x），gi（x）称为约束函数.目标函数为二次函数而约束函数都是线性函数的优化问题称为二次规划；而目标函数和约束函数都是线性函数的优化问题称为线性规划.

1.2 邻近点算法

其主要设计思路是在原目标函数上添加一个二次项[2]，邻近点算法中添加的项叫做邻近点（PPA）项，PPA 项可以取一般的范数，不一定要取欧式范数，在一定程度上可以降低难度.

1.3 邻近点算法的收敛性分析

算法的收敛性是设计一个迭代算法的最起码要求，关于收敛性，有局部收敛性和全局收敛性的概念[9，10].

定义1若算法只有当初始点x0充分接近极小点x*时，由算法产生的点列{xk}才收敛于x*，则称该算法具有局部收敛性.若对于任意的初始点x0，由算法产生的点列{xk}都收敛于x*，则称该算法具有全局收敛性.

算法的局部收敛速度是衡量一个算法好坏的重要指标，给出有关收敛速度的概念：设算法产生的点列{xk}收敛于极小点x*，且

若p=1 且0＜θ＜1，则称该算法具有线性的收敛速度；若p=1 且θ=0，则称该算法具有超线性收敛速度；若p=2且0＜θ＜∞，则称该算法具有平方收敛速度；若p＞2 且0＜θ＜∞，则称该算法具有p 阶收敛速度.

2 数值实验分析

2.1 邻近点算法求解无约束二次规划

二次规划是指这种形式的优化问题：

式中：H∈Rn×n为实对称矩阵；x 为列向量.如果H 为半正定矩阵，则称此规划为凸二次规划，否则为非凸二次规划.对于非凸二次规划，全局最优解较难计算，所以只考虑凸二次规划.

例1通过添加一个二次项，求解第k 个子问题.

在实际的计算中，xk+1可以通过求解线性方程组得到，根据已有的条件，其中r 的取值可能影响邻近点算法的效率，分析r 的取值对整个算法的收敛性的影响.主要考虑在r 不同的取值情况下，算法的收敛速度的改变以及对收敛精度的影响.通过编制符合算法结构的MATLAB 程序，然后对r 分别取0.1，0.5，1，1.5，2，分析r 的取值对算法的收敛速度以及误差大小的影响.在维度为500，条件数随机生成的情况下，MATLAB 计算的结果如表1 所示.

表1 维度为500 时计算结果

图1 直观地展示了r 取不同值时算法的收敛速度.从图1 可以看出，当r=0.1 时算法的收敛速度最快，当r≤1 时，算法的收敛速度明显下降，说明r 较大时会降低算法的收敛速度.另一方面，从计算的数据结果来看，当r=0.1 时，计算时间有着明显的优势.综上所述，当r 取值较小时，在目标函数为好条件时，即使r 取值较小，不能有效改善条件数，但是依然保证了较高的计算效率，可以以较快的运算速度得出结果；而当r 增加到1 时，运算的时间大大增加，而且收敛精度较低；当r 增加到2 时，运算时间和r=1 时基本相当，在相同步骤中收敛精度继续下降.所以，在一定数量级之内当r 增加时，虽然可以改善坏条件，但是不一定能改善算法的计算效率.

图1 r 取值对收敛速度的影响

为了进一步研究r 取值的影响，设置不同的条件数以研究r 的取值与计算时间的关系.在维度为100 时，计算时间t 的结果与条件数、r 的关系见表2.在条件数不变的情况下，r 的变化会对计算时间造成较大的改变.比如当条件数＜107时，r 的增加会造成计算时间的增加，说明收敛速度变慢；但当条件数＞107时，r 的增加反而可以一定程度上减少计算时间，说明r 可能改善了条件数，从而提升了计算效率.

表2 条件数与r 的关系

在维度为100，条件数为108的情况下，r 分别取1，0.1，0.01，0.001，0.000 1，利用MATLAB进行计算，结果见图2.

如图2 所示，在有限的步数下，当条件数比较大的时候，对比不同的r 取值，r=0.001 的收敛速度超过了r=0.000 1 的收敛速度，说明r 的增加一定程度上可以改善条件数，提高计算效率，节约计算时间.另一个直观的变化就是当r=0.1时，整个算法的收敛精度大幅下滑，最终的误差大大高于r 取值较小时的结果，而且图像趋于平滑，不再继续收敛.在数值实验中，常见的误差主要有两种，一种是观测误差和模型误差，但是他们不属于数值计算带来的误差，所以一般不做研究.另一种是数值计算中产生的误差，主要有截断误差和舍入误差.截断误差是指在计算机计算迭代算法的过程中，迭代计算不可能无限进行下去，当计算需要终止时，计算结果数值与理论值的差异.舍入误差是指计算机在反复的计算过程中，因为存储空间的限制，不得不放弃一部分精度，并且不断地在计算过程中累积的误差.根据之前的分析，当r 取值较大时，改善了目标函数的条件数，但是也会造成计算步骤增加，所以在计算迭代算法过程中截断误差和舍入误差反复出现，并且在大量的计算步骤中逐渐累积，最终导致较大的误差.而且当r 的取值与原来矩阵中的数不是处在同一数量级时，在矩阵的计算中可能出现大数吃小数的现象，而这是需要在算法的设计中尽量避免的.所以，在数值计算实验的模型设计中，要考虑到相关的控制措施，避免误差过大，才能使模型的应用范围更广，精度更高.

图2 r 取值对算法收敛精度的影响

2.2 邻近点算法求解基追踪问题

考虑基追踪降噪（BPDN）问题：

应用邻近点算法的基本思路，添加一个邻近点项，使得算法可以通过迭代法的方式，简化原问题的难度，加快原问题的解决速度.例如求解0∈T（x）=∂‖x‖1+β（x-xk），做相应变换得x，其解相当于对左端的xk做软收缩，长度为，即

为了验证步长对于算法收敛性的影响，所以利用MATLAB 来编制相关算法，来分析不同的步长在实际运算中的表现，将步长分别设置为2，1.5，1，0.5，0.1，其中步长与r 为倒数关系，在MATLAB 运算得到的结果如图3 所示.

图3 不同步长下算法收敛速度

从图3 可以看到，当步长较小时，算法的收敛速度较慢，随着步长的增加，算法的收敛速度不断提高，这说明算法的收敛速度是与步长相关的.其中r 为步长的倒数，所以当r 减小时，算法的收敛速度提升.但是当将r 减小到一定值的时候，运算无法进行，说明r 的取值是有特定的取值范围的，所以在理论分析中的想法得到了印证，即r＞βρ（A＇A）.但是在实际的应用中，已经证明时，上述结论依然是成立的，这样一来就大大放松了收敛条件，在实际运用中变得更加有效.

3 结论

通过对最优模型定义与邻近点算法的最优化规则和收敛特性进行概述，利用MATLAB 软件对求解无约束二次规划优化问题与使用迭代收缩阈值算法求解基追踪问题进行收敛性能分析，得到结论如下：

1）在求解无约束二次规划优化问题中，在一定数量级之内当r 增加时，虽然可以改善坏条件，但是不一定能改善算法的计算效率；

2）在求解无约束二次规划优化问题中，r 改善了目标函数的条件数，但是也会造成计算步骤的增加，所以在计算迭代算法过程中截断误差和舍入误差反复出现；

3）在求解基追踪问题中，步长较小时，算法的收敛速度较慢，随着步长的增加，算法的收敛速度不断提高，收敛速度与步长相关.