文摘
我们提供一个光滑的增广拉格朗日算法为半无限的编程(SIP)。对于该算法,我们建立一个扰动定理在温和的条件下。摄动定理的推论,我们获得了全局收敛性结果,也就是说,任何聚点的序列算法生成的SIP的解决方案。我们得到了这个全局收敛性结果没有任何强制性的或有界性条件。另一个扰动定理的推论表明,扰动函数在零点低半连续当且仅当目标函数的算法部队序列收敛到最优值的SIP。最后,给出了数值结果。
1。介绍
我们考虑半无限规划(SIP): 在哪里,功能和是连续可微的。是一个非空的有界和封闭域。在本文中,我们假设 这种假设是非常温和的,因为目标函数可以更换的如果假设是不满意的。
半无限规划具有广阔的应用,如工程技术、最优控制、特征值计算,统计设计。提出了很多方法来解决半无限规划(见[1- - - - - -4])。正如我们所知,解决SIP面临的主要困难是无限的约束。如果将无限约束转换为一个积分函数,SIP (1.1相当于一个与有限的约束非线性规划。
对于任何给定的和,让 定义通过 在哪里是一个给定的概率测度,也就是说,。因此SIP (1.1)可以新配方如下非线性规划(NP)和一个等式约束: 然后非线性规划(1.5)具有相同的最优解和最优值与SIP (1.1)。
有限的等式约束的非线性规划,Hestenes [5和鲍威尔6)独立地提出了一个增广拉格朗日函数,通过融合一个二次惩罚项传统拉格朗日函数。这个增广拉格朗日函数避免了传统拉格朗日函数的缺点是只适用于凸函数。因此,增广拉格朗日函数可以应用于非凸优化问题。后,增广拉格朗日函数扩展为不等式约束优化问题和彻底调查Rockafellar [7]。最近,杨和Teo [8)和Ruckmann夏皮罗(9]介绍了SIP的增广拉格朗日函数(1.1)。在[9),存在的必要和充分条件提出了相应的增广拉格朗日乘数法。(8)提出了一个非线性拉格朗日方法,建立了非线性处罚问题的最佳值序列收敛于SIP (1.1),假设目标函数的水平集是有界的。本文利用半无限规划的等价关系(1.1)和非线性规划(1.5),没有任何有界性条件,我们提出一个增广拉格朗日算法SIP (1.1)。
我们注意到,尽管NP的约束(1.5)是有限的,但非光滑约束函数。因此,基于现有的梯度优化方法不能用于解决NP (1.5直接)。为了克服这种不便,我们必须光滑约束函数。SIP (1.1),(10- - - - - -13]介绍了半光滑牛顿方法和平滑牛顿方法。他们证明了每个SIP的聚点是一个广义平稳点(1.1)。然而,在这些方法每次迭代,海赛矩阵需要计算。当问题的规模很大,海赛矩阵计算非常昂贵。基于精确的罚函数近似的平滑函数的一个家庭,一个smoothed-penalty算法求解NP (1.5)提出了14]。他们证明,如果约束集有界或目标函数是强制性的,积累点的算法生成一个序列的SIP解决方案(1.1)。
本文对SIP (1.1),我们提供一个光滑的增广拉格朗日算法平滑(经典的增广拉格朗日函数7]。在该算法中,我们不需要得到一个精确的全球自愿子问题的最优解在每一个迭代。它足够的搜索是一个不精确的解决方案。不难获得一个不精确的解决方案,只要积分函数的评价不是很贵。对于该算法,我们建立一个扰动定理在温和的条件下。摄动定理的推论,我们获得了全局收敛性结果,也就是说,任何聚点的序列算法生成的SIP解决方案(1.1)。我们得到了这个全局收敛性结果没有任何强制性的或有界性条件。值得注意的是乘数序列是一个有界性的充分条件在许多文献对拉格朗日方法(见[15- - - - - -17])。然而,在我们的算法中,乘数可以无限序列。另一个扰动定理的推论表明,扰动函数在零点低半连续当且仅当目标函数的算法部队序列收敛到最优值的SIP (1.1)。
本文组织如下。在下一节中,我们提出一个平滑的增广拉格朗日算法。节3,我们建立的扰动定理算法。通过这个定理,我们获得一个全局收敛性属性和一个充分必要条件,目标函数的算法部队序列收敛到最优值的SIP (1.1)。最后,我们给出一些数值结果4。
2。光滑的增广拉格朗日算法
在介绍算法之前,一些定义和符号需要。为,我们定义放松可行的SIP (1.1)如下: 然后是可行的SIP (1.1)。让SIP是一组最优解(1.1)。我们假设在这篇文章中。
摄动函数定义如下: 因此SIP的最优值(1.1)是 很容易证明上半连续点吗。
对于问题(1.5(),相应的经典增广拉格朗日函数7)是 在哪里拉格朗日乘数和吗是惩罚参数。基础上,我们引入了一种光滑的增广拉格朗日函数: 在这里是近似的参数。
在下面,我们假设连续可微的函数满足(一) 非负和单调递增;(b)对于任何,;(c) 。
很容易检查有许多连续可微的函数满足条件(a)、(b)和(c)。 使用条件(a)和(c),为任何,我们有 从上面的方程,(一)——(c)条件下,光滑函数接近古典增广拉格朗日函数作为接近为零,也就是说,
基于光滑的增广拉格朗日函数,我们提出以下平滑增广拉格朗日算法。
算法2.1。集,,,,,。
步骤1。计算
否则,寻求在不精确的全局最优解令人满意的
步骤2。集,,
步骤3。集,回到步骤1。
自下面是有界的,负的,是一个不精确的解决方案满意(2.10)总是存在。因此算法2.1是可行的。
3所示。收敛性质
在本节中,通过使用摄动定理算法2.1,我们将获得一个全局收敛性的属性,一个算法的充分必要条件2.1部队的目标函数序列收敛到最优值的SIP (1.1)。证明了摄动定理,我们首先给以下两个前题。
让,,。
引理3.1。假设点序列由算法生成2.1。然后对任何,存在一个正整数这样,尽管。
证明。
案例1。当,往往有限。从算法2.1,存在一个正整数这样对所有。请注意,,所以任何,存在一个正整数这样对所有。因此,当,我们有。
案例2。当,。我们假设结论不成立。然后,存在无限子序列这样对所有,也就是说,
自,上面的,存在一个正整数这样对所有。然后使用(2.10)算法2.1,我们有
因此,(3.1),(3.2),令人满意的(a) (b),为任何,,我们得出,
请注意,下面是有界的,,我们就能获得
也就是说,。然而,另一方面,因为,我们可以选择;的选择,,在算法2.1的属性,我们获得
这表明有一个上限。它是在矛盾。
引理3.2。假设点序列由算法生成2.1。然后每一个聚点的,一个。
定理3.3。假设序列由算法生成2.1,然后(我) ;(2) ;(3) 。
证明。自是单调递减的对吗我们知道,下面已经绑定存在,是有限的。由算法2.1,我们有。然后
采取和下确界的定义,存在这样
自,也就是说,。
另一方面,由引理3.1,对于任何,当是足够大,我们有吗
自满足条件(a)和(c),我们获得
因此,存在这样
对于任何。如前所述,选择,,,在算法2.1,(3.7),(3.8)和(3.10)获得任何,
从上面的不平等和(3.6),注意到,对于任何,我们有
然后。所以结论(1)- (3)。
现在,我们证明了算法的全局收敛性2.1。
推论3.4。假设点序列由算法生成2.1。然后每一个聚点是问题的最优解(1.1)。
证明。让的聚点;从引理3.2,我们有 定理的结论(i)3.3和(3.13),我们得到 然后我们得到,因为(3.14),上半连续点吗。
推论3.5。 当且仅当低半连续点。
4所示。数值结果
给一些见解的行为算法提出了。它是在Matlab中实现7.0.4和运行在AMD Athlon (tm)双核心处理器4800 + 2.50 GHz CPU和1.87 GB的内存。表1和2显示相应的问题的计算结果与下列事项: :迭代次数; :起点; :平滑函数; :最后的迭代点; :最后的拉格朗日乘数; 的函数值在最后。
中使用的参数的算法2.1指定如下:
示例4.1(见[18])。考虑以下: 我们选择的起点。这个例子中有最优解。
示例4.2(见[18])。考虑以下: 为、6和。我们选择零向量作为起点。
整个计算实验中,我们使用信赖域方法求解无约束优化子问题的每一步。对于相应的信赖域子问题,我们直接使用Matlab工具箱中的信任函数。测试结果的例子4.1总结在表1。我们测试的三种情况,和,分别用作平滑近似函数。表示迭代的数量,表示近似拉格朗日乘数在最后的迭代,和和是近似解和最终的目标函数迭代。例如4.2时,我们测试结果,,在表2。数值结果表明,增广拉格朗日算法建立在本文中是一个实用和有效的方法求解半无限规划问题。
确认
这项工作得到了国家自然科学基金资助下10971118,10901096,和11271226,优秀的科研基金的中年和青年科学家的山东省格兰特BS2012SF027,和山东省自然科学基金授予ZR2009AL019。