英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料
关于一个函数Lipschitz常数的估计
G.R.WOOD
数学与计算机学院，中央昆士兰大学，罗克汉普顿，昆士兰4702，澳大利亚
B.P.ZHANG
数学与统计学院，坎特伯雷大学，克莱斯特彻奇，新西兰
（投稿于1994年6月1日，公开于1995年4月10日）
摘要：一些全局优化算法都基于目标函数的Lipschitz常数值。本文提出一个预测Lipschitz常数的随机方法。我们可以指出，在给定样本斜率中的最大斜率近似符合逆威布尔分布。这个分布通过最大斜率来拟合，并且位置参数作为Lipschitz常数的评估指标。数值结果如文中所示。
关键词:全局优化，Lipschitz常数，逆威布尔分布，Gnedenko条件，渐进分布，单边Lipschitz条件
1.简介
许多全局优化算法是基于目标函数的Lipschitz连续性。对于这些算法而言，预估Lipschitz常数是很重要的。正如[6]中描述的，良好的预估也是必要的，因为估计得越好，这些算法就收敛得越快。求解函数的Lipschitz常数于它自身而言是一个全局优化难题，因为Lipschitz常数是函数方向导数量的上界。
现有的研究中处理估计Lipschitz常数问题的方法分为两类。首先第一类是目标函数的表达式及其导数是明确已知的，其次第二类形式是未知的，只有函数值是可以被估计的。我们分别将这些目标函数分为白盒函数和黑盒函数。
对于白盒问题，Shubert[13]给出了一个利用导数上界估计单变量Lipschitz常数的例子。Mladineo[9]讨论了二维变量的情况并选择作为估计值。值域包含区间分析方法应归功于曾被Gourdin使用的Moore[10]的方法。文献[5]是估算符合威布尔分布的极大似然估计的三变量函数的Lipschitz常数问题。显而易见，任何合适的全局优化算法都可以用来寻找白盒目标函数的Lipschitz常数。
另一方面，对于黑盒问题，我们不得不通过仅有的函数值来寻找函数梯度量的上界。Strongin在文献[14]中提供了一个用于单变量函数的方法。在k值后，有序值和对应的函数值是已知的，而且给出了Lipschitz常数的一个保守估计。Strongin估计需要乘上一个大于1的因子r。然而，无法保证这个估计值等价于或优于真实的Lipschitz常数。文献[7]中，Hansen揭示了对于一类已构Lipschitz函数，无论选择多大的因子r， Strongin估计都是一个对于真实Lipschitz常数的保守估计，因此Strongin的伴随算法可能终止于局部最优。在文献[2]中，de Haan提出了一个方法，用来估计使用顺序统计量的函数的最小值，并且讨论了目标函数的必要条件。虽然这个方法在原则上和我们的方法类似，但是我们的方法仅要求目标函数值来估计Lipschitz常数，并不需要他们的导数。
我们的方法建立在Strongin和de Haan的思想上，并且源自于估计单变量函数的Lipschitz常数问题。改进之处在接下来简单描述。回忆我们的目标，我们要寻找对于在g的范围内各自对应的x和y值所有的斜率的上界。如果我们从范围g中均匀地取出X值和Y值，那么随机变量自身拥有累计分布函数F，我们把F称为g的斜率分布。它的支集的上界就是我们需要的Lipschitz常数。令人遗憾的是我们仍然不知道一个任意的目标函数g的F函数的形式。
假设现在我们得到一个叫做n的完全斜率的随机样本，然后考虑最大值的分部。已知F满足Gnedenko条件，在下一节中给出，它的最大完全斜率的分布可以近似地认为是符合逆威布尔分布。我们将它的位置参数（支集的上界）用来估计Lipschitz常数。
我们在第2节严格证明这些想法，并在第3节用数值结果说明。在第4节我们要说明对于一大类函数，它们的斜率分布确实符合Gnedenko条件。在第5节我们讨论了未来研究的方向。
2.方法
对于一个在实数集R上的区间[a,b]，对于所有的函数定义，这样对于所有的都有。这些是具有Lipschitz常数M，区间为R的子集[a,b]的Lipschitz连续函数。
我们从通过一个简单例子来说明这个方法开始。在图1我们指出了定义域为[-1,1]的函数。Lipschitz常数M值为1，因为我们在之间均匀独立地选择x和y。在例子中，易得斜率估计值为
图1 目标函数g，斜率取值为0.67
假设我们多次重复这个过程。那么如图2所示，这类斜率的绝对值的累积分布就会收敛到累积斜率分布。注意到相应的概率密度函数将具有上限支持。
图2 斜率绝对值的累积分布函数
现在从这个分布中做一个大小为的随机抽样。令为斜率绝对值的最大值。那么的累积分布函数应为.图3显示了这个累积分布函数斜率的最大值。注意到的概率密度函数有同样的上界。
图3五个绝对斜率样本中最大的累积分布函数
一般来说，的分布形式是什么？如果我们知道分布趋向于增加，那么位置参数的估计就可以被用作常数的估计。
极值分布理论告诉我们极值的分布类型只有三种。因为的支集是有上界的，那么假如原始的分布函数满足条件，其中任何都大于，常数大于，标准理论表明是逆威布尔分布的。这个结果首次出现在文献[4]中。
三参数逆威布尔分布的累积分布函数形式如下：
为位置参数，为尺度参数，为形状参数。在第节中给出了收敛到逆威布尔分布的方式的精确描述。我们将反向威布尔分布拟合到最大绝对斜率的样本，并使用位置参数的估计作为的估计。
我们现在正式地给出这个随机过程来估计的Lipschitz常数。我们的方法假设函数值是可以被计算出的。当对选择靠近时，可以得到较大的斜率绝对值。为此，我们在步骤1中设置了采样方案，该方案允许根据对角线周围的条带上的均匀分布来选择对。
第一步，对斜率取样。已知，在均匀取对并求值。
第二步，计算斜率最大值。令，重复次第一步和第二步，得到。
第三步，拟合逆威布尔分布。将三参数逆威布尔分布拟合于。
输出。我们对于的估计量，是拟合逆威布尔分布的位置参数。
由此，我们将Lipschitz常数估计问题转化为一个常规的曲线拟合问题。
3.数值结果
这个方法给出良好的结果了吗？我们现在继续研究这个问题。我们首先观察到，如果随机变量具有反向威布尔分布，则其负值具有威布尔分布。因此，我们可以采用标准威布尔拟合法。
Zanakis和Kyparisis在文献[16]、Panchang和Gupta在文献[11]中，详细讨论了三参数威布尔分布的极大似然估计方法。我们使用轮廓似然和矩量法相结合来拟合威布尔分布。对于固定量，我们可以直接使用第一步和第二步来找到和。然后我们选择组合，从而最大程度的观察到的最大斜率的可能性。我们注意到Gourdin等人，在文献[5]中提出了一种新的全局算法来解决这一问题。我们用Gourdin的方法来检查结果。
我们描述了三个测试函数的结果。第一个测试函数是简单函数，定义域为，它的Lipschitz常数为。另外两个测试函数从文献[15]中第177页得来，分别为，定义域为，Lipschitz常数为；，定义域为[-10,10]，Lipschitz常数为67.表Ⅰ、Ⅱ、Ⅲ给出了当取样按均匀分布时，和的不同取值和的估计值。表Ⅳ给出了当，不同取值下这三个函数的估计值。在下一节中，我们表明，这些测试函数的斜率分布满足Gnedenko条件。所有的估计值以的形式给出，其中是平均值，为对于给定的和，标准偏差超过的值。
注意，估计值随着和的增加而提高。还要注意，微小的的使用加剧了这些结果，特别是当域间隔较大时。这是由于当间隔很大时，从中取样，很少在最大绝对斜率值达到的区域产生一对。
表Ⅰ 在上的Lipschitz常数估计，在上均匀取样。这里
表Ⅱ 在上的Lipschitz常数估计，在上均匀取样，这里
表Ⅲ 在上的Lipschitz常数估计，在上均匀取样，这里
下面的例子可以让我们比较我们的数值结果与Strongin的方法得出的数值结果。测试函数是汉森等人在文献[7]中提出的改良。
表Ⅳ 当时，三个测试函数的Lipschitz常数估计值
令,
其中，且 是Strongin算法的乘数。这里是大于或等于的最小整数。图4给出了当时的图像。
图4 的汉森检验函数
对于任何大于1的乘数，可以证明的的是Lipschitz常数的Strongin估计永远是，但是Lipschitz常数的真值是，等价于。因此，Strongin估计是欠估计的，于是他的算法收敛到非全局局部最优。表Ⅴ比较了对于两个同样的在上的汉森检验函数，分别使用Strongin方法和逆威布尔分布方法求解的Lipschitz常数估计值。
表Ⅴ Lipschitz常数估计值比较：对于较大值和较小值的Strongin估计和逆威布尔估计
4.Gnedenko条件
为了使逆威布尔分布近似最大绝对斜率的分布，初始累积分布函数必须满足一个条件。下面的命题证明了这个结果。
命题1 令有限，为从中随机取样范围为的最大值。然后有序列，使得收敛于标准逆威布尔分布，当且仅当对于任意时。
有Gnedenko条件，。这里的是逆威布尔分布，且。
文献3中的53-57页和87-91页给出这个命题的证明。
以上结果表明，最大绝对斜率的仿射变换近似于逆威布尔分布。很容易证明，如果一个随机变量的分布是逆威布尔分布，那么的分布也是逆威布尔分布。因此，最大绝对斜率本身具有近似逆威布尔分布。形式上，近似于。
我们将在第二节使用这个结论。需要证明的是，Gnedenko条件确实适用于一类广泛的目标函数的斜率分布。这是我们现在提出的主要定理的内容。
定理2 假设，取自然数。那么就存在一个特殊的使得，且。已知，令为均匀抽取的一点，则有
表示的累积分布函数。当的时，Gnedenko条件成立。
为了证明定理2，我们需要下面的预备定理和引理。令，对于固定的令。典型的和）如图5所示，。
图5目标函数的斜率函数的水平集和
Archetti等人在文献1中提出了利用目标函数随机抽样的全局优化框架。他们将极值分布理论应用于全局最大化问题，利用目标函数水平集的测度来研究Gnedenko条件。他们在目标函数上得到一个条件，保证水平集的测度具有一定的极限性质。这又确保随机抽样下目标函数值的分布满足Gnedenko条件。
我们的方法类似于Archetti等人的步骤，但是这里要最大化的函数是原始目标函数的绝对斜率函数，而不是。我们的目的是找到上的一般条件，确保斜率分布满足Gnedenko条件。下一个引理，这里用定理2中给出的绝对斜率函数来表示，归功于Archetti等人，见于文献1中的第一章、定理6和定理7，给出了绝对斜率函数的条件，保证绝对值的累积分布满足Gnedenko条件。然后我们就可以通过那个定理的条件确保引理3成立来证明定理2。
引理3 （1）假设，这里是在任意达到其唯一的全局最大值的内点，是阶的负齐次多项式，其中，为自然数且当。那么极限存在且当时为有限的及正的。这里表示上的勒贝格测度。
（2）如果满足，那么当时，Gnedenko条件成立。证明引理3（1）的关键是水平集的结构，例如。那么这就表明了和都存在且等价。现在我们使用引理3来证明定理2
定理2的证明。为了不失一般性，我们假设。（这是因为我们可以令，并根据需要证明的结果）。我们接着可以将写为
根据假设，。因为假设是的唯一最大值，我们必须令。当然随着直径的唯一假设是矛盾的。
因为，接近零，于是对于任何足够接近零的数对我们有。我们证明了满足引理3（1）的条件。
对于任何包含于的且z足够小，当时直径。考虑上一点，那么当在之间，在域上的重新排列的泰勒展开式即为。写出关于在0上的泰勒展开式，我们有：
这里等价于
且在和之间。那么现在就有：
利用文献11中第8页所述的广义范德蒙德卷积公式可得对于，
则有：
现在很容易检查是引理3（1）中描述的函数形式。引理3（1）不仅表明了存在而且当时该极限有限而且为正。这个限制的结果取决于我们从的对角线的带上均匀采样的事实，而且在对角线上假定其最大值。随后引理3（2）给出在时，Gnedenko条件成立。在的邻域中，这与的累积分布函数一致，因此定理2如下。
要求在中出现第一个非零导数的奇数阶保证了与的假设没有矛盾。可以肯定的是在第3节中讨论的三个测试函数满足定理2的条件。我们要指出的是，仅包含线性和三次项的目标函数的证明要容易得多，因为在这种情况下，水平集和是椭圆的。
基于定理2的下列命题表明，关于在唯一点或内点其最大绝对值的假设可以被去除。这两个命题都可以用一种简单的方式来证明。
命题4 假设上的有限多点，那么而且但是。已知，从中均匀选择，，表示的累积分布函数。那么Gnedenko条件成立于。
命题5 假设，。当表示左k阶导数时，且在上。已知，从中均匀选择，，表示的累积分布函数。那么Gnedenko条件成立于。
5.总结与展望
本文提出了一种估计单变量函数的Lipschitz常数的随机方法。该方法显然是成功的，但计算复杂。进一步研究的三个方向是改善它们自己。首先，这里使用的思想是如何针对多个变量的函数的？作者有一些部分的结果，将在另一篇论文中提出和深入研究。其次，如何选择斜率样本的大小和最大绝对斜率的样本大小？
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[21628]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
