1. 引言
求解约束最优化问题的增广拉格朗日法又叫乘子法,是罚函数法和拉格朗日乘子法的有机结合,最开始是由Powell [1] 和Hestenes [2] 在1969年针对等式约束优化问题提出的一种优化算法,在1973年Rockfellar对其进行了推广,从而应用于求解不等式约束优化问题。虽然过去了很多年,但增广拉格朗日法及其衍生的方法仍然是求解约束优化问题的核心工具。在二十世纪七十到八十年代,增广拉格朗日法和它衍生的一些方法得到了很好的研究 [3] 。Nocedal J和Wright S J在Numerical Optimization一书中对求解约束优化问题的方法进行了详细的阐述,如:对数障碍法、二次罚函数法等 [4] 。相关学者也撰写了关于最优化理论的书籍,为我们的研究奠定坚实的基础 [5] [6] 。
近年来,随着计算机的快速发展,增广拉格朗日法对于求解变分不等式问题在构造数值算法时能起到很重要的作用 [7] 。陈亮研究了一些基于增广拉格朗日函数方法求解约束最优化问题的算法设计,做出理论分析并进行了数值试验 [8] 。申倩影等人在增广拉格朗日乘子法的基础上,提出修正的增广拉格朗日乘子法,并对其收敛性进行分析 [9] 。相关学者对非凸约束问题的非精确增广拉格朗日法的最坏情况复杂度进行了研究,证明了迭代复杂度的界 [10] 。在几何约束优化问题的增广拉格朗日方法的理论和数值研究中,利用问题定制的非单调投影梯度法求解得到的子问题 [11] 。但近年来具体阐述求解约束最优化问题的增广拉格朗日法却不多见,可见这是一个重要的研究课题,其在很多领域具有广阔的应用前景。另外,增广拉格朗日法可以用于许多实际问题中的优化设计,通过编写程序构造乘子函数,求解精度较高,是一种非常切实可行的设计优化方法,是值得我们继续研究的课题。
本文我们所讨论增广拉格朗日法实际上是从原问题的拉格朗日函数出发,再加上适当的罚函数,其实,可以理解为在拉格朗日函数的基础上加了一个二次惩罚项,从而将原约束优化问题转化为求解一系列的无约束优化子问题。本文主要针对用增广拉格朗日法对等式约束及不等式约束问题的求解方法进行介绍,使读者更加清晰地认识增广拉格朗日法在求解约束最优化问题中的应用。本文的结构安排如下:第2节主要讨论增广拉格朗日法求解等式约束和不等式约束问题的方法;第3节主要对其相关定理进行简单介绍;第4节主要用一个例子用解析法探究其有效性;第5节将对本文内容进行小结及展望。
2. 基于增广拉格朗日法求解约束最优化问题
本节我们主要详细的阐述用增广拉格朗日法对等式约束问题和不等式约束问题进行求解的具体过程,增强我们对增广拉格朗日法求解约束最优化问题的进一步认识与了解。
2.1. 等式约束问题
我们首先考虑等式约束问题
(1)
2.1.1. 等式约束问题求解
在二次罚函数
中,通过平方不可行性并按
缩放它们来惩罚违反约束的行为,并且
不完全满足可行性条件
,相反,它们受到轻微的扰动
并且近似满足
可以肯定的是,这种扰动会随着时间的推移而消失
,但我们是否可以改变函数
为了避免这种系统扰动,即使近似极小值更接近满足等式约束
,通过这样做,我们可以避免减少
归零。
而对于等式约束问题,采用增广拉格朗日法,可以将难以求解的问题转化为更容易求解的问题,首先需引入增广拉格朗日函数
(2)
我们看到,增广拉格朗日函数通过包含拉格朗日乘子的显示估计来实现这些目标
与拉格朗日函数
的不同之处是平方项的存在,而与二次罚函数
的不同之处在于
的存在,所以从这个意义上说,它是拉格朗日函数和二次罚函数的结合。
对拉格朗日函数
中的x求偏导(即为L的梯度)
(3)
从而在第k步迭代过程中,固定惩罚项参数
和
,此时优化x,根据优化条件有
(4)
对比最优性条件有,应该有
,从而很自然的通过
更新乘数估计
从一个迭代到另一个迭代。
2.1.2. 等式约束问题算法
等式约束问题的基本算法步骤:
步骤1:定义
,
,初始点
、
和
;
步骤2:以
为起始点,求解
的最优解;
步骤3:若
,算法停止;
步骤4:通过
更新
,否则,转步骤2。
2.2. 不等式约束问题
不等式约束问题主要考虑
(5)
不等式约束问题求解
当问题属于不等式约束问题时,我们引入松弛变量
并替换不等式
,将其转化为具有等式约束和有界约束的问题,即
根据约束条件
定义增广拉格朗日并且应用边界约束条件
,我们得到了在等式约束问题的基本算法的迭代k中要解决的子问题:
(6a)
(6b)
每个
只出现在(6a)的两项中,这实际上是关于每个松弛变量
的凸二次函数,所以,我们可以在(6)
中分别对每个
执行显示最小化。子问题(6a)对
的偏导数为
,(6a)关于
的无约束
极小值出现在偏导数等于零时,即
(7)
如果这个无约束极小值小于0的下界,那么由于(6a)在
中是凸的,
在(6)中的最优解为0。综上所述,我们发现
在(6)中的最优解为
(8)
我们可以用这个公式来代替s,得到仅在x中的子问题(6)的等价形式。通过分离涉及
的项,我们得到
(9)
通过定义函数
在标量参数
在上式中有以下形式
(10)
我们得到以下转化子问题:
(11)
的这个定义代表了增广拉格朗日到不等式约束情形的自然扩展。通过这个扩展。我们也可以将等式约束问题的基本算法应用到不等式约束的情况,并进行进一步的修改,只要获得近似解
,我们将通过以下这个公式来更新拉格朗日乘子
(12)
这个公式是由
关于x在(11)的近似解
处应接近于0,通过使用(9),我们得到
更新公式(12)通过将此公式与第一个KKT条件进行比较得出
,我们可以说
它有直观的意义,以保持非负性的组成部分
,因为我们从KKT条件
知道不等式约束的最优拉格朗日乘子是非负的。
3. 基于增广拉格朗日法的相关定理
为了简单起见,我们仅讨论等式约束问题,即给定增广拉格朗日的问题。第一个结果验证了等式约束问题的基本算法的方法,当我们了解到精确的拉格朗日乘子向量
,并且
是
的极小值,
对所有的
足够小。我们可以得到一个很好地
估计,通过最小化
即使在什么时候
不是特别接近于0,前提是
是对的合理估计
。
定理1:设
是(1)的局部解,满足LICQ (即梯度
是线性无关向量),并满足二阶充分条件中规定的
,然后有一个,使得对所有的
,
是
的严格局部极小值。
证明:
满足
是严格局部极小值的二阶充分条件,即
(13)
是正定的。
通过使用KKT条件和(2),我们有
(14)
上述验证(13)的第一部分。
我们现在证明第二部分
,对所有的
并且
足够小,由
,我们有
注意,根据LICQ,A具有全行秩。请注意
(15)
根据代数的基本定理,令
,则有
(16)
我们在这个表达式的右边寻找三项的界限。由于
,则
;令
,在
给出第二项的下限。
对于第三项,我们定义
,我们有
最后,如果d是
的最小的特征值,我们有
通过这些下界代入(16),我们得到
(17)
这个表达式右侧的第一项显然是非负的。因为
,如果我们选择A的满秩,第二项也是非负的
成为任何值,以至于
然后选择
,事实上,(17)的右边是严格正的,除非
和
,这意味着
是正定的,即证。
定理2:假设定理1的假设在
和
,
是一个阈值,存在正标量
,使得以下成立:
a) 对所有的
和
满足
问题
(18)
有独特的
解决方案,此外,我们有
b) 对所有的
和
满足(18),我们有
其中
由
给出。
c) 对所有的
和
满足(18),矩阵
是正定的,并且约束梯度
是线性独立的。
4. 基于增广拉格朗日法的有效性
为了充分说明拉格朗日法的有效性,从以下例子具体说明:
例:用增广拉格朗日法求解等式约束问题
(19)
解:构造增广拉格朗日函数
则由
(20)
由解析法求解无约束优化问题
的最优解
由迭代公式
,得
令
,上式两边
取极限,得
解得
,代入
的表达式得原问题的最优解为
对于罚函数法求得的最优解为
,而增广拉格朗日法求得的最优解为
。从这两种方法求出的最优解,我们可以清楚的看到增广拉格朗日法求解的最优解更有效,逼近效果更好,更加稳定。
5. 小结与展望
在本文中,我们主要对求解等式约束和不等式约束最优化问题的增广拉格朗日法进行详细介绍,进一步增强我们对增广拉格朗日法的认识,同时对其所涉及的相关定理进行证明并做一些简要的概述,最后通过一个例子验证该方法的有效性。
针对本文所介绍的求解约束最优化问题的增广拉格朗日法,在今后的研究中我们还可以考虑用计算机进行求解,通过MATLAB语言对其进行编程得到有效的数值结果,对其有效性做进一步的验证,在此之上我们还可以考虑针对等式约束和不等式约束同时存在的最优化问题的增广拉格朗日法等。相信在未来,这一求解约束最优化问题的增广拉格朗日法将在各领域有更好的发展和更广泛的应用。
参考文献