带分段线性增广乘子方法.doc

一类带分段线性NCP函数的新lagrangian乘子法王汝锋 尚有林 濮定国（河南科技大学 数学与统计学院 洛阳 471003）摘要：本文提出一类带分段线性NCP函数的新的lagrangian乘子法，在一定条件下证明了原问题（NLP）的KKT点、局部极小解、整体极小解与增广lagrangian乘子函数的平稳点、局部极小点、整体极小点是对应的。这样原问题（NLP）就可以通过无约束问题求解。关键词：约束最优化；KKT点；非线性互补0 引言考虑如下的约束非线性优化问题（NLP） （1）其中是二次连续可微函数。定义约束非线性优化问题（NLP）的可行域为 （2）约束非线性优化问题（NLP）的lagrangian乘子函数， （3）其中和是乘子向量，为方便起见，用表示列向量。 KKT条件：,若点满足KKT条件，则称为问题（NLP）的KKT点。约束非线性优化问题（NLP）的增广lagrangian乘子函数，其中是正参数，当取某个值的时候，增广lagrangian乘子函数的最小值与NLP的解和相应的乘子是对应的。Dpillo和Grippo已经证明1-4,然而，这些方法用到一个求最大值的函数，这个函数在无限多个点处并不是可微的。为了克服以上缺点，濮定国在2004年提出了一类带新NCP函数的乘子法，该方法在增广lagrangian函数和原问题之间存在很好的等价性；本文定义了一个带线性NCP函数的增广lagrangian乘子函数，并在一定条件下证明了原问题（NLP）的KKT点、局部极小解、整体极小解与增广lagrangian乘子函数的平稳点、局部极小点、整体极小点是对应的。这样原问题（NLP）就可以通过无约束问题求解。1 预备知识严格互补条件：称为互补条件；若同时有，则称严格互补条件成立。强二阶充分条件：若点满足以下条件1. 满足一阶KKT条件；2. 对于任意，有。这里。则称满足强二阶充分条件。NCP函数NCP对 如果，则称数对是一个 NCP对.NCP函数 如果二元函数，当且仅当是一个NCP对,则称是一个NCP 函数(非线性规划互补函数)线性NCP函数如下定义:为了研究方便令,我们得到（创新点）对于函数,以下结论成立:1.是个NCP函数，即；2. 是连续可微的； 3. 除了在原点是强半光滑的，其他点处处连续可微，4. 对于所有的，或者对所有的，有？！令 ，这里：当且仅当对于任意的，有及。记 显然，KKT条件等价于，及。2 新的增广lagrangian乘子函数本文构造的增广laganrian乘子函数如下:给出以下假设A1: 和是二次Lipschitz连续可微的。A2 任，当时，有线性无关。A3 在原问题(NLP)的KKT点处，严格互补条件成立。A4: 和是三次Lipschitz连续可微的。A5 在原问题(NLP)的KKT点处，强二阶充分条件成立。下面的定理表明原问题（NLP）的KKT点、局部极小解、整体极小解与的稳定点、局部极小点、整体极小点与在以上假设成立的条件下是对应的。首先给出(NLP)的KKT点和增广Lagrangian乘子函数的平稳点之间的关系定理2.1:若是原问题(NLP)的KKT点，则对于任意的，有；若对于充分大的，有，则是原问题(NLP)的KKT点。证：记 ；.根据的定义，对任意的，有，及，结论显然成立；对任意的，当是原问题(NLP)的KKT点， （2.1）又 （2.2）将（2.2）代入（2.1）得 （2.3）又根据严格互补条件 （2.4） （2.5）又 （2.6）将（2.6）式带入（2.5）得 （2.7）又根据严格互补条件 （2.8）则的梯度为： （2.9） （2.10） （2.11）若是原问题(NLP)的KKT点，则，对于任意的，（2.9），（2.10），（2.11）显然为0，故当时，（2.12）将（2.2）式带入（2.12）式计算可得 （2.13）当充分大时根据（2.11）可以得到 （2.14）又根据A2可知线性无关，可以得到 （2.15）同时可以推出，对于任意的，有 （2.16）否则，不妨设，则对任意，都有与矛盾。由（2.10）和（2.15）可以得到 （2.17）将，代入（2.9）可得到（2.18）又因为线性无关，可以得到故可以得到是原（NLP）的KKT点。定理2.2 :当C充分大时，若是 的局部极小点，则是原问题(NLP)的一个局部极小解.证明：当C充分大时，若是 的局部极小点，则存在，使得对任意的，有 （2.19）由是的局部极小点可知，。根据定理2.1，是原问题（NLP）的KKT点。故，即 （2.20）则又根据假设A2任，当时，有线性无关，则是非奇异的。又根据假设A1，存在，使得任意的，线性无关，则非奇异。因此可以通过下式求得：很显然，当且时，必有。即当充分小时，对任意的，存在满足。由是原问题（NLP）的KKT点可得。另一方面，任意的，存在使得，？！（因为即），则有 （2.21）得证。以下引理均在假设A2-A5下得出。下面证明原问题(NLP)的整体极小解和增广Lagrangian乘子函数 的整体极小点之间的关系定理2.3 :若 是原问题(NLP)的KKT点，则当C充分大时，在处强凸。定理2.4:设 是一个紧集。若是原问题(NLP)的KKT点，且是(NLP)在紧集X上唯一的整体极小解，则当C充分大时，是在整体极小点。证：由可知，存在，使则假设A2-A5在成立。根据定理2.1，；根据定理2.3，当充分大时，在处强凸。则存在，是在上的唯一极小点。假设结论不成立，则在上存在另外一个极小点且根据定理2.1，是原问题(NCP)的KKT点。则有又是（NLP）在紧集X上唯一的全局极小点，故，。令则当充分大时，且是原问题(NLP)的KKT点。则由此可知，不是在上的唯一极小点。故得出矛盾，得证。3 结束语本文证明了函数的稳定点，局部极小点及整体极小点与原问题（NLP）的KKT点，局部极小解及整体极小解是对应的1 Pillo G D, Grippo L. A new class of augmented Lagrangians in nonlinear J . S IAM J Cont ralOpt, 1979, 17: 616.2 Pillo G D, Grippo L. An augmented Lagrangian for inequality constraints in nonlinear programming problems J . J Optimizat ionT heorem and Applicat ions, 1982, 36: 495.3 Pillo G D. Exact penalty method M /In Algorithms for Continuous Optimization: the state of the art . Boston: Kluw er Ac Press,1994: 1- 45.4 Pillo G D, Lucidi S . On exact augment ed Lagrangian functions in nonlinear programming probl