带分段线性增广乘子方法

《带分段线性增广乘子方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一类带分段线性NCP函数的新lagrangian乘子法王汝锋尚有林濮定国（河南科技大学数学与统计学院洛阳471003）摘要：本文提出一类带分段线性NCP函数的新的lagrangian乘子法，在一定条件下证明了原问题（NLP）的KKT点、局部极小解、整体极小解与增广lagrangian乘子函数的平稳点、局部极小点、整体极小点是对应的。这样原问题（NLP）就可以通过无约束问题求解。关键词：约束最优化；KKT点；非线性互补0引言考虑如下的约束非线性优化问题（NLP）（1）其中是二次连续可微函数。定义约束非线性优化问题（NLP）的可行域为（2

2、）约束非线性优化问题（NLP）的lagrangian乘子函数，（3）其中和是乘子向量，为方便起见，用表示列向量。KKT条件：,若点满足KKT条件，则称为问题（NLP）的KKT点。约束非线性优化问题（NLP）的增广lagrangian乘子函数，其中是正参数，当取某个值的时候，增广lagrangian乘子函数的最小值与NLP的解和相应的乘子是对应的。Dpillo和Grippo已经证明[1-4],然而，这些方法用到一个求最大值的函数，这个函数在无限多个点处并不是可微的。为了克服以上缺点，濮定国在2004年提出了一类带新NCP函数的乘子法，该

3、方法在增广lagrangian函数和原问题之间存在很好的等价性；本文定义了一个带线性NCP函数的增广lagrangian乘子函数，并在一定条件下证明了原问题（NLP）的KKT点、局部极小解、整体极小解与增广lagrangian乘子函数12的平稳点、局部极小点、整体极小点是对应的。这样原问题（NLP）就可以通过无约束问题求解。1预备知识严格互补条件：称为互补条件；若同时有，则称严格互补条件成立。强二阶充分条件：若点满足以下条件1.满足一阶KKT条件；2.对于任意，有。这里。则称满足强二阶充分条件。NCP函数NCP对如果，则称数对是一个N

4、CP对.NCP函数如果二元函数，当且仅当是一个NCP对,则称是一个NCP函数(非线性规划互补函数)线性NCP函数如下定义:为了研究方便令,我们得到（创新点）对于函数,以下结论成立:1.是个NCP函数，即；2.是连续可微的；3.除了在原点是强半光滑的，其他点处处连续可微，124.对于所有的，或者对所有的，有？！令，这里：当且仅当对于任意的，有及。记显然，KKT条件等价于，及。2新的增广lagrangian乘子函数本文构造的增广laganrian乘子函数如下:给出以下假设A1:和是二次Lipschitz连续可微的。A2任，当时，有线性无关

5、。A3在原问题(NLP)的KKT点处，严格互补条件成立。A4:和是三次Lipschitz连续可微的。A5在原问题(NLP)的KKT点处，强二阶充分条件成立。下面的定理表明原问题（NLP）的KKT点、局部极小解、整体极小解与的稳定点、局部极小点、整体极小点与在以上假设成立的条件下是对应的。首先给出(NLP)的KKT点和增广Lagrangian乘子函数的平稳点之间的关系定理2.1:若是原问题(NLP)的KKT点，则对于任意的，有；若对于充分大的，有，则是原问题(NLP)的KKT点。证：记；.12根据的定义，对任意的，有，及，结论显然成立；

6、对任意的，当是原问题(NLP)的KKT点，（2.1）又（2.2）将（2.2）代入（2.1）得（2.3）又根据严格互补条件（2.4）12（2.5）又（2.6）将（2.6）式带入（2.5）得（2.7）又根据严格互补条件（2.8）则的梯度为：（2.9）12（2.10）（2.11）若是原问题(NLP)的KKT点，则，，对于任意的，（2.9），（2.10），（2.11）显然为0，故当时，（2.12）将（2.2）式带入（2.12）式计算可得（2.13）当充分大时12根据（2.11）可以得到（2.14）又根据A2可知线性无关，可以得到（2.15）同

7、时可以推出，对于任意的，有（2.16）否则，不妨设，则对任意，都有
与矛盾。由（2.10）和（2.15）可以得到（2.17）将，代入（2.9）可得到（2.18）12又因为线性无关，，可以得到故可以得到是原（NLP）的KKT点。定理2.2:当C充分大时，若是的局部极小点，则是原问题(NLP)的一个局部极小解.证明：当C充分大时，若是的局部极小点，则存在，使得对任意的，有（2.19）由是的局部极小点可知，。根据定理2.1，是原问题（NLP）的KKT点。故，即（2.20）则又根据假设A2任，当时，有线性无关，则是非奇异的。又根据假设A1，存

8、在，，使得任意的，线性无关，则非奇异。因此可以通过下式求得：很显然，当且时，必有。即当充分小时，对任意的，存在满足。由是原问题（NLP）的KKT点可得。另一方面，任意的，存在使得，，12，？！（因为即），则有（2.21）