基于延迟离散时间测量的无梯度优化

《Nonlinear Analysis: Hybrid Systems》：Gradient-free optimization using delayed discrete-time measurements

　　摘要
本文研究了一种无梯度优化算法——无偏极值搜索算法（uES），用于处理具有时变延迟的离散时间测量下的广义强凸映射问题。文中提出了两种算法：经典uES方案和有界uES方案。为适应系统的离散时间测量特性，采用方波扰动信号，并引入可调指数函数以消除稳态振荡误差，从而确保收敛到精确最优解。采样过程被建模为时变延迟，进而发展出基于时延的平均方法用于稳定性分析。该方法将原始极值搜索系统转化为扰动项呈指数衰减的扰动梯度下降系统。通过基于李雅普诺夫的分析，证明了这两种算法对于广义强凸代价函数具有指数稳定性，并严格证明了它们对时变测量延迟的鲁棒性。文中还给出了数值示例以验证所提方案的有效性。

引言
优化理论在工程实践中有着广泛的应用[1][2]。在许多情况下，梯度信息难以获取或获取成本高昂，这就使得无梯度（或零阶）优化方法变得至关重要[3][4]。极值搜索是一种自适应的、无需模型的优化技术，可用于实时定位未知输入输出映射的极值点。该方法可追溯至1922年[5]。基于平均法和奇异扰动理论，首次为极值搜索提供了严格的稳定性证明，见于文献[6]。此后，该技术得到了诸多扩展和应用，包括半全局稳定性结果[7]、基于牛顿法的极值搜索[8]、基于李括号的极值搜索[9]、有界极值搜索[10][11][12]、用于博弈的极值搜索[13]、带延迟的极值搜索[14]以及用于多智能体系统的极值搜索[15]。

在实际应用中，极值搜索通常基于离散时间测量来实现，这更适用于数字平台。最早考虑离散数据极值搜索的是文献[16]，其中利用离散时间测量来估计梯度，再结合传统的非线性规划算法进行优化。这一思路后来被进一步拓展到全局离散数据极值搜索[17]、受限离散数据极值搜索[18]以及基于核函数近似的离散数据极值搜索[19]。另一种方法是，Zhu等人[20]将采样操作建模为时变延迟，并采用基于时延的平均方法来分析稳定性。

上述所有极值搜索方法都存在稳态误差，只能收敛到最优解的附近区域，即仅具备实际稳定性。为克服这一限制，Yilmaz等人[21][22]提出了无偏极值搜索算法。这类算法利用呈指数衰减的扰动幅度以及呈指数增长的解调信号，从而消除了稳态偏差，并确保收敛到精确最优解。这些算法的稳定性分别通过经典平均法和李括号平均法进行了分析。然而，这些平均方法在存在延迟的情况下难以应用。最近，在文献[23]中，我们通过一种新的构造性平均方法，成功将uES框架扩展到存在时变测量延迟的不确定二次静态映射问题。这种方法无需近似，因为转化后系统的稳定性可直接推导出原系统的稳定性。不过，文献[23]的结果仅限于二次目标函数，未涵盖有界uES算法。

基于以上分析，据我们所知，本文是首个针对具有时变延迟的离散时间测量下的广义强凸映射，开发出两种uES算法的论文。与仅考虑不确定二次静态映射且未涉及有界uES的文献[23]不同，本文研究了广义强凸目标函数，并涵盖了经典uES方案和有界uES方案。具体而言，我们提出了适用于离散时间测量的经典uES方案实现方式以及有界uES方案的离散时间实现方式。这两种算法均采用方波扰动来适应离散时间测量环境，并通过可调指数函数消除稳态振荡误差，从而实现向精确最优解的收敛。受Zhu和Fridman[24]以及Fridman和Zhang[25]的启发，我们将离散时间测量过程建模为时变延迟，并建立了基于时延的平均方法用于稳定性分析。该方法将原始极值搜索系统转化为扰动项呈指数衰减的扰动梯度下降系统，随后通过基于李雅普诺夫的分析证明其指数稳定性。与文献[23]中的构造性平均方法不同，我们的分析不依赖于目标函数的二次假设，因此可应用于更广泛的强凸代价函数类别。此外，据我们所知，这也是首次将时延平均方法扩展到具有广义强凸目标函数的有界ES算法上。

本文的其余结构如下：第2节介绍相关预备知识，包括符号说明、问题表述及基本假设；第3节阐述经典uES算法并证明其指数稳定性；第4节将分析扩展到有界uES方案；第5节给出用于说明两种算法的数值示例；第6节对全文进行总结。

符号说明
在本文中，Rn表示n维欧几里得空间。对于实数a，?a?表示小于或等于a的最大整数。对于向量x∈Rn，‖x‖表示欧几里得范数。对于矩阵A，‖A‖表示其诱导的2-n范数。给定向量v1,…,vn，运算符col{v1,…,vn}表示列向量[v1T,…,vnT]T。向量ei表示Rn的第i个标准基向量。适当维数的单位矩阵记为I，而对角矩阵则用diag{?}表示。

具有离散时间测量和时变延迟的经典uES算法
首先回顾一下文献[31]中提出的连续时间uES算法（为简化起见，仅考虑一维情况）：
x(t)=x?(t)+ζ?1(t)sin(ωt),
x??(t)=?kζ(t)sin(ωt)f(x(t))?η(t),
η?(t)=?ωhη(t)+ωhf(x(t))，
其中ω为抖动频率，ωh为高通滤波器的截止频率，η为高通滤波器状态，而指数调节函数定义为ζ(t)=eλt。
x(t)的动态方程可表示为：
x?(t)=ζ?1(t)?λsin(ωt)+ωcos(ωt)?kζ2(t)sin(ωt)f(x)?η(t)。

具有离散时间测量和时变延迟的有界uES算法
在本节中，我们提出一种有界uES算法。首先简要回顾文献[22]中的方法（为简化起见，仍考虑一维情况）：
x?(t)=ζ?1(t)ωαcosωt+kζ2(t)f(x(t))?η(t)=ζ?1(t)ωα[cosωtcoskζ2(t)f(x)?η(t)?sinωtsinkζ2(t)f(x)?η(t)]，
η?(t)=?ωhη(t)+ωhf(x(t))，
其中ζ(t)的定义如式(4)所示，ω、η、ωh、k的定义同第3节，α>0为可调参数。在此基础上，我们结合图2所示的离散时间测量情况设计算法：
x?(t)=ζ?1(t)∑i=1n

数值示例
本节通过数值模拟，展示所提出的uES算法在存在测量延迟的离散时间测量条件下的性能。经典uES方案和有界uES方案均在相同的二维代价函数f(x)=12‖x?x?‖2+12ln(1+‖x?x?‖2)上进行测试，该函数在x?=[3,3]T处存在唯一的全局最小值。在所有模拟中，测量值都受到形如D(t)=0.01?0.5+0.5sin(2t)的时变测量延迟的影响，因此0≤D(t)

结论
本文提出了两种能够处理测量延迟并实现向最优解精确收敛的uES算法。通过基于时延的平均方法，我们将原始极值搜索系统转化为扰动项呈指数衰减的梯度下降系统。基于这种转化后的动态系统，通过严格的李雅普诺夫分析证明：只要控制参数合适，系统状态就会以指数速率收敛到未知的极值点。

作者贡献声明
Xuebin Li：撰写——初稿、方法论、研究工作。
Xuefei Yang：撰写——审稿与编辑、监督、资源协调、项目管理、概念构思。
Kai Zhang：研究工作、形式化分析、数据整理。
Jiebao Sun：可视化处理、结果验证、资金筹集。

利益冲突声明
作者声明不存在任何可能影响本文研究的已知财务利益或个人关系。

致谢
作者衷心感谢特拉维夫大学的Emilia Fridman教授，她向我们介绍了极值搜索领域，开发了用于极值搜索的时延平均方法，还为本文中的时延平均分析提供了指导。

Xuebin Li | Xuefei Yang | Kai Zhang | Jiebao Sun
哈尔滨工业大学数学学院，中国哈尔滨，150001