上海悉尼工商学院

第３６卷第５期

２００８年５月

同济大学学报（自然科学版）

ＪＯＵＲＮＡＬ ＯＦ删ＧＪＩ ＵＮＩＶＥＲＳＩＴＹ（ＮＡＨ眼ＡＩ，ＳｃｍＮＣＥ）

ＶｏＩ．３６ Ｎｏ．５

Ｍａｙ ２００８

一类带ＮＣＰ函数的新Ｌａｇｒａｎｇｉａｎ乘子法

姜爱萍 ，一，濮定国 ，段希波３

（１．同济大学数学系，上海２０００９２；２．上海大学悉尼工商学院，上海２０１８００；

３．山东水利职业学院数学教研室，山东１３照２７６８２６）

摘要：提出一类带非线性互补问题（ＮＣＰ）函数的新Ｌａｇｒａｎｇｉａｎ乘子法，用来解满足等式约束和不等式约束的最优

化问题．此方法以连续可微的罚函数为基础，通过求解一个新的无约束Ｌａｇｒａｎｇｉａｎ函数得到原问题的解，并且在一

定的条件下还可得到此方法的全局收敛性．

关键词：约束优化问题；非线性互补函数；收敛性

中图分类号：０ ２２１．２ 文献标识码：Ａ 文章编号：０２５３—３７４Ｘ（２００８）０５—０６９５—０４

Ａ Ｃｌａｓｓ ｏｆ Ｎｅｗ Ｌａｇｒａｎｇｉａｎ Ｍｕｌｔｉｐｌｉｅｒ Ｍｅｔｈｏｄ ｗｉｔｈ ＮＣＰ Ｆｕｎｃｔｉｏｎ

ＪＩＡＮＧＡｉｐｉｎｇ ，一，ＰＵＤｉｎｇｇｕｏ ＤＵＡＮＸｉｂｏ。

（１．Ｄｅｐａｎｎｅｎｔ ｏｆ Ｍａｔｈｅｎａａｔｉｅｓ，Ｙｏｎｇｊｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ ２０００９２，Ｃｈｉｎａ；２．Ｓｙｄｎｅｙ ｌｎｓｔｉｍｔｅ ｏｆ Ｌａｎｇｕａｇｅ ａｎｄ Ｃｏｍｍｅｒｃｅ，Ｓｈａｎｇｈａｉ Ｕｎｉｖｅｒｓｉｔｙ，

ｈａｎｇＩ１ａｉ ２０１８００，Ｃ【ｌｉｍ；３．Ｔｅａｃｈｉｎｇ ａｎｄＲｅｓｅａｒｃｈＳｅｃｔｉｏｎｏｆＭａｔｈｍａａｔｉｃｓ，ＩｎｓｔｉｔｕｔｅｏｆＳ￣ｍ＆ｎｇＷａｔｅｒＰｏｌｙｔｅｃｈｎｉｃ，Ｒｉｚｌ＇￣ｍ ２７６８２６，Ｏａｔｎａ）

Ａｂｓｔｒａｃｔ．Ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｓ ａ ｎｅｗ Ｌａｇｒａｎｇｉａｎ Ｍｕｌｔｉｐｌｉｅｒ ｍｅｔｈｏｄ ｗｉｔｈ ｎｏｎｌｉｎｅａｒ ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ

ｐｒｏｂｌｅｍ（ＮＣＰ）ｆｕｎｃｔｉｏｎ ｆｏｒ ｎｏｎｌｉｎｅａｒ ｃｏｎｓｔｒａｉｎｅｄ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ．Ｔｈｅ ｍｅｔｈｏｄ ｉｓ ｂａｓｅｄ ｏｎ ａ ｃｏｎ—

ｔｉｎｕｏｕｓｌｙ ｄｉｆｆｅｒｅｎｔｉａｂｌｅ ｐｅｎａｌｔｙ ｆｕｎｃｔｉｏｎ ａｎｄ ｉｔ Ｃａｎ ｏｂｔａｉｎ ｔｈｅ ｓｏｌｕｔｉｏｎ ｏｆ ｔｈｅ ｃｏｎｓｔｒａｉｎｅｄ ｐｒｏｂｌｅｍｓ ｂｙ ａ

ｓｉｎｇｌｅ ｕｎｃｏｎｓｔｒａｉｎｅｄ ｍｉｎｉｍｉｚａｔｉｏｎ ｏｆ ａ ｎｅｗ ｌａｇｒａｎｇｉａｎ ｆｕｎｃｔｉｏｎ．Ｍｏｒｅｏｖｅｒ，ｔｈｅ ｇｌｏｂａｌ ｃｏｎｖｅｒｇｅｎｃｅ ｃａｎ

ａｌｓｏ ｂｅ ａｂｔａｉｎｅｄ ｕｎｄｅｒ ｍｉｌｄ ｃｏｎｄｉｔｉｏｎｓ．

Ｋｅｙ ｗｏｒｄｓ：ｃｏｎｓｔｒａｉｎｅｄ ｏｐｔｉｍｉｚａｔｉｏｎ；ｎｏｎｌｉｎｅａｒ ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ ｆｕｎｃｔｉｏｎ；ｃｏｎｖｅｒｇｅｎｃｅ

考虑如下的约束非线性优化问题（ＮＬＰ）：

ｍｉｎ ｆ（ｘ） ∈Ｒ”

Ｓ．ｔ．Ｈ（ｘ）＝０

Ｇ（ ）≤０ （１）

其中厂：Ｒ 一Ｒ，Ｈ（Ｘ）：（ｈｌ（ ），ｈ２（ ），…，ｈ

（ ））Ｔ：Ｒ 一Ｒｐ和Ｇ（ ）＝（ｇｌ（ ），ｇ２（ ），…，ｇ７，

（ ））Ｔ：Ｒ”一Ｒ 是二次连续可微函数．

定义约束非线性优化问题（ＮＬＰ）的可行域为

Ｄ＝｛ ∈Ｒ”｛Ｇ（ ）≤０，ｎ（ｘ）＝０｝（２）

约束问题ＮＬＰ的Ｌａｇｒａｎｇｉａｎ乘子函数为

Ｌ（ｘ，∞， ）＝ｆ（ｘ）＋∞ＴＨ（ｘ）＋ ＴＣ（ｘ） （３）

其中∞：（ｃＯ１， ２，…， ）Ｔ∈Ｒｐ和 ＝（ ｌ， ２，

…

，

）Ｔ∈Ｒ 是乘子向量，为方便起见，用（ ，

∞Ｔ

， Ｔ）Ｔ表示列向量．

Ｋａｒｕｓｈ—Ｋｕｈｎ—Ｔｕｃｋｅｒ（Ｋ～Ｋ—Ｔ）点（ ， ， ）∈

Ｒ ×Ｒｐ×Ｒｍ是满足ＮＬＰ问题的一阶最优必要条

件的点

（ ， ， ）＝０，Ｇ（ ）≤０，

Ｈ（ ）＝０，．ｒＴＧ（ ）：０， ≥０ （４）

收稿１３期：２００６～１０—１６

基金项目：国家自然科学基金资助项目（１０７７１１６２）

作者简介：姜爱萍（１９７９一），女，博士生，主要研究方向为最优化理论与方法．Ｅ－ｍａｉｌ：ａｐ７２４＠１２６．ｃｏｒｎ；

濮定国（１９４８一），男，教授，博士生导师，主要研究方向为非线性规划．Ｅ－ｍａｉｌ：ｍａｄｐｕ＠ｍａｉｌ．ｔｏｎｇｊｉ．ｅｄｕ．ｃｎ

维普资讯

６９６ 同济大学学报（自然科学版） 第３６卷

ＮＬＰ问题的增广Ｌａｇｒａｎｇｉａｎ函数为Ｓ（ ，∞，

，Ｃ），其中Ｃ为正的参数，当Ｃ取某个值的时候，

增广Ｌａｇｒａｎｇｉａｎ函数的最小值与ＮＬＰ的解和相应

的乘子为一一对应的．Ｐｉｌｌｏ和Ｇｒｉｐｐｏ已经证明（见

文献［１—４］），在一定条件下有约束问题的ＫＫＴ

点、局部极小点、整体极小点和增广的乘子函数Ｓ

（ ，∞， ．Ｃ）的平稳点、局部极小点、整体极小点

之间有一一对应的关系，并给出了相关算法的收敛

性．这样有约束问题ＮＬＰ可以转化为无约束问题来

求解．然而，这些方法用到一个求最大值的函数，这

个函数在无限多个点处可能并不是可微的．

为了克服以上缺点，本文提出一类带线性ＮＣＰ

函数的增广Ｌａｇｒａｎｇｉａｎ函数方法来求解带光滑等式

约束和不等式约束的光滑目标函数的最小值，此方

法把原约束问题化为无约束的最优化问题来求解，

且证明原约束问题与转化后的无约束问题之间具有

等价性．这个方法具有全局收敛性，特别地，还构造

出一个函数来调整增广Ｌａｇｒａｎｇｉａｎ函数中的参数．

１预备知识

给出有关非线性互补问题（ＮＣＰ）和严格非线性

互补问题（ＳＮＣＰ）的两个定义．

定义１ ＮＣＰ对和ＳＮＣＰ对

如果满足ａ＞ｆｏ，ｂ＞ｆＯ且ａｂ＝０，称（盘，ｂ）∈Ｒ２

为ＮＣＰ对；如果满足（盘，ｂ）为ＮＣＰ对且ａ ＋ｂｚ≠

０，称（盘，ｂ）∈Ｒ 为ＳＮＣＰ对．

定义２ ＮＣＰ函数

如果满足 （ａ，ｂ）＝０当且仅当（ａ，ｂ）是ＮＣＰ

对，函数 ：Ｒ２一Ｒ称为ＮＣＰ函数．

线性ＮＣＰ函数如下定义：

ｆ３盘一盘

Ｊ （盘，ｂ）＝ ３ｂ—ｂＺ／ａ

【９盘＋９６

如果ｂ≥ａ＞０，或３６＞一ａ≥０，

如果ａ＞ｂ＞０或３盘＞一ｂ≥０， （５）

如果０≥ａ且～ａ≥３ｂ，或ｂ≤一３ａ≤０．

在除原点以外的地方均为连续可微的，但它在原

点为强半光滑的．Ｉ，ｆｌ（盘，ｂ）＝０当且仅当

ｆａ＝０ ｂ＞０

Ｊ

＿《口＞０ ｂ：０ （６）

【口＝０ ｂ：０

也就是说， （盘，ｂ）＝０当且仅当ａ≥０，ｂ≥０，

ａｂ＝０。

令

（ ， ，Ｃ）＝ （（一ｃｇ （ ））， ）１≤ｉ≤

其中Ｃ＞０为参数，因而 （ ， ，Ｃ）：０当且仅当

ｆｇｉ（ ）：０ ＞０

ｇ （ ）＜０ ｆ＝０ （７）

ｌｇ （ ）＝０ ＝０

也就是说， （ ， ，Ｃ）：０，当且仅当对任意的ｃ＞

０，有ｇｊ（ ）≤０，Ａｉ≥０， （ ）＝０．

定义 （ ， ，Ｃ）＝（ １（ ， ，Ｃ），…， （ ， ，

Ｃ））Ｔ．显然，式（３）的ＫＫＴ条件等价于

（ ， ，Ｃ）＝０，ｆＩ Ｈ（ ）ｆＩ＝０， 上（ ，∞， ）：０

定义带线性ＮＣＰ函数的增广Ｌａｇｒａｎｇｉａｎ乘子函数

Ｓ：Ｒ” ｌ—Ｒ为

Ｓ（ ，∞， ，Ｃ）：ｆ（ ）＋∞ＴＨ（ ）＋

ｃ ＩＩ Ｈ（ ）ｌＪ ／２＋［１Ｊ （ ， ，Ｃ）一 ／３ ｌＪ ～

ｆＩ ／３ ｆＩ ／（２ｃ）＋ｆＩ 正（ ，∞， ）ｆＩ ／２ （８）

其中，∞＝（∞ｌ，…，ＣＯｐ）Ｔ，且 ＝（ １， ２，…， ）Ｔ是

Ｌａｇｒａｎｇｉａｎ乘子，Ｃ＞０是参数．

给出以下假设：

Ａｌ：厂，ｈ （ ），ｉ＝１，２，…，Ｐ，和ｇ （ ），ｉ：１，

２，…， 是二次Ｌｉｐｓｃｈｉｔｚ连续可微的．

Ａ２：对任意的Ｃ＞０，｛Ｖ＾ （ ）， ｇ （ ）ｌ ｉ：１，

２，…，Ｐ，Ｊ＝１，２，…， ｝在满足 Ｓ（ ，∞， ，Ｃ）＝０

的点处是线性无关的．

引理１ 如果（ ，∞， ）是问题ＮＬＰ的一个

ＫＫＴ点，那么对任意的Ｃ＞０均有ｖＳ（ ，∞， ，Ｃ）

＝０；如果对某个Ｃ＞０有 Ｓ（ ，∞， ，Ｃ）＝０，

（ ， ，Ｃ）＝０， 正（ ，∞， ）：０成立，贝ｑ（ ，∞， ）

满足问题ＮＬＰ的ＫＫＴ条件；如果对充分大的Ｃ，

有 Ｓ（ ，∞， ，Ｃ）＝０成立，则（ ，∞， ）满足问题

ＮＬＰ的ＫＫＴ条件．

引理２如果对充分大的Ｃ，（ ，面， ）是Ｓ（ｘ，

∞， ，Ｃ）的局部极小值，那么 是问题ＮＬＰ的局部解．

证明如果对充分大的Ｃ，（ ， ， ）是Ｓ（ ，

∞， ，Ｃ）的局部极小值，那么存在８＞０使得对于任

意（ ，∞， ）∈Ｂ （ ， ， ）＝｛（ ，∞， ）ｌ｛ｌ（ ，

∞， ）一（ ， ， ）ＩＩ≤ ｝，

Ｓ（ ， ， ，Ｃ）≤Ｓ（ｘ，∞， ，Ｃ） （９）

上（ ， ， ）＝０意味着

（ＶＨ（ ）， Ｇ（ ）） （ Ｈ（ ）， Ｇ（ ））（ ， ）＝

一（ Ｈ（ ）， Ｇ（ ）） ｆ（ ）．

对于任意的 ∈Ｄ，假设Ａ２意味着存在一个（∞， ），

维普资讯

第５期 姜爱萍，等：一类带ＮＣＰ函数的新Ｌ￣４ｇｒａｎｇｉａｎ乘子法

（∞， ）＝～［（ Ｈ（ ）， Ｇ（ ））Ｔ（ｖｒ１（ｘ），

Ｇ（ ））ｒ （￣ＴＨ（ｘ），

Ｇ（ ）） ｖｆ（ ）．

显然， （ ，∞， ）＝０且当 — 时（∞， ）一（ ，

）．存在一个 ｌ，０＜ １≤ ，使得对于任意的 Ｅ

（ ）都有一个（ ，∞， ）∈ （ ， ， ）且 正（ ，∞，

）＝０．由引理２，（ ， ， ）满足问题ＮＬＰ的ＫＫＴ条

件．有 （ ）＝Ｓ（ ， ， ）．另一方面，对于任意的；

∈

．（ ）ｎ Ｄ，存在一个（；， ， ）∈ （ ，岙， ）使

得 正（；， ， ）＝０．Ｇ（呈）≤０，Ｉｌ （；， ，Ｃ）一Ｉ．／３

【１ ０一【Ｉ互／３【Ｉ ≤０和Ｈ（王）＝０意味着

厂（ ）＝Ｓ（ ， ， ）≤Ｓ（；， ， ，Ｃ）≤，（主）

（１０）

在假设Ａ１和假设Ａ２成立的条件下，给出以下假

设：

Ａ３：在每个ＫＫＴ点（ ， ， ）处严格互补条件

成立．

Ａ４：ｆ，ｈ 和ｇ 是三次Ｌｉｐｓｃｈｉｔｚ连续可微的．

定义３如果点（ ，Ａ， ）满足问题ＮＬＰ的～

阶ＫＫＴ条件且对任意的

ｄ∈Ｐ（ ）＝｛ｄ ｌ ｄ Ｈｉ（ ）＝０，

ｉ：１，…，Ｐ，ｄＴ ｇ （ ）≤０，ｉ Ｅ Ｉ（ｘ）｝，

Ｉ（ ）＝｛ Ｊ ＝１，…， ，ｇ （ ）＝０｝

和ｄ≠０均有

ｄＴ Ｌ（ ，∞， ）ｄ＞０

成立，则点（ ，Ａ， ）满足问题ＮＬＰ的强二阶充分

条件．

Ａ５：在问题ＮＬＰ的任意ＫＫＴ点处强二阶充分

条件成立．

引理３假设Ａ２～Ａ５成立，如果（ ， ， ）∈

Ｘ×Ｐ×Ｍ是问题ＮＬＰ的一个ＫＫＴ点，则对充分

大的Ｃ，Ｓ（ ，∞， ，Ｃ）在（ ， ， ）处是强凸的．

假设Ａ２￣Ａ５成立，则下面的引理４～７成立．

引理４设Ｘ×Ｐ×Ｍ Ｒ Ｐ 为紧集，假

设（ ， ， ）Ｅ ｉｎｔ（Ｘ×Ｐ×Ｍ）是问题ＮＬＰ的

ＫＫＴ点，如果 是问题ＮＬＰ在紧集ｘ上的唯一全

局最小点，那么对充分大的Ｃ，（ ， ， ）是Ｓ（ 。

∞， ，Ｃ）在ｉｎｔ（ ×Ｐ×Ｍ）上的唯一全局最小点．

证明 因为（ ， ， ）Ｅ ｉｎｔ（Ｘ×Ｐ×Ｍ），假设

Ａ２￣Ａ５在它的邻域Ｂ （ ，岙， ）（＝＝ｘ×Ｐ×Ｍ成

立，由引理１和引理４的条件可知对充分大的Ｃ，存

在 ＞０，（ ，面， ）是Ｓ（ ，∞， ，Ｃ）在Ｂ （ ，面，

）上的唯一最小值点．如果（ ，面， ）不是Ｓ（ ，

∞， ，Ｃ）在ｉｎｔ（Ｘ×Ｐ×Ｍ）上的唯一全局最小点，

则存在另外一个最小点（呈， ， ）∈ｉｎｔ（Ｘ×Ｐ×

Ｍ）满足Ｓ（呈， ， ，Ｃ）≤Ｓ（ ， ， ，Ｃ）．通过引

理１可知，（呈， ， ）是问题ＮＬＰ的ＫＫＴ点，所以

（ ）≤ （ ）；因而 ＝ 且（ ， ）≠（面， ）．令

１ １ （∞女， ＾）＝÷（面，ｊ【）＋（１一÷）（ ， ）

那么对充分大的 ，有（ ，∞女， ）∈Ｂ６（ ， ， ）且

（ ， ， ）是问题ＮＬＰ的ＫＫＴ点．所以

Ｓ（ ，∞女， 女，Ｃ）＝ｆ（ ）＝Ｓ（ ， ， ，Ｃ）

则对任意的 ＞０，（ ，面， ）不是 上的唯一最小

点，这与上面的结论矛盾，引理４可证．

定义

ｒ（ ，∞， ，Ｃ）＝一Ｃ【Ｉ ｓ（ ，∞， ，Ｃ）【１ ＋

【Ｉ Ｌ（ ，∞， ）【Ｉ ＋【Ｉ西（ ， ，Ｃ）／Ｃ【Ｉ

引理５令Ｘ×Ｐ×ＭＣＲ Ｐ 为一紧集，假

设问题ＮＬＰ没有ＫＫＴ点（ ，∞， ）∈Ｘ×Ｐ×

Ｍ，那么存在一个Ｃ ＞０，使得对任意的Ｃ≥Ｃ 和

（ ，∞， ）∈Ｘ×Ｐ×Ｍ，

ｒ（ ，∞， ，Ｃ）≤０．

引理６令Ｘ×Ｐ×ＭＣＲ Ｐ 是紧集，假设

（ ， ， ）∈ｉｎｔ（Ｘ×Ｐ×Ｍ）是问题ＮＬＰ的ＫＫＴ

点，则存在Ｃ ＞０和 ＞０使得对任意的Ｃ≥Ｃ

和任意的（ ，∞， ）∈Ｂ （ ， ， ），其中（ ， ，

）∈Ｘ×Ｐ×Ｍ

ｒ（ ，∞， ，Ｃ）≤０

引理７令Ｘ×Ｐ×ＭＣＲ Ｐ 是个紧集，那

么存在一个Ｃ ＞０使得对任意的Ｃ≥Ｃ 和所有

的（ ，∞， ）∈Ｘ×Ｐ×Ｍ，

ｒ（ ，∞， ，Ｃ）≤０

２算法和收敛，陛

算法１

步骤０选择参数Ｃ０＞０，ｃ＞ｌ，０＜ ＜１，０

＜ ＜１和０＜０１≤０２＜１．给出一个初始点 ０ＥＲ ，

ｆＯ０＝（ｏ￣ｏｉ， ０２，…， ０ｐ）Ｅ Ｒ 和 ０＝（ ０１， ０２，…，

０

）∈Ｒ ．设置 ：０，Ｊ＝０．

维普资讯

同济大学学报（自然科学版） 第３６卷

步骤１如果 Ｓ（Ｘｋ，ｆ．Ｏｋ， ，Ｃ ）＝０且ｚ．（ ，

，∞ ，Ｃ ）≤０，停止．

步骤２如果ｚ．（Ｘｋ， ，∞ ， ）≥０，那么Ｃ １

：ｃｃ ，（ＸＯ，２ｔｏ， ｏ， ）＝（Ｘｋ， ，ｆ．Ｏｋ，ｃ ）， ＝Ｊ＋

１，转步骤１；否则转步骤３．

步骤３ 由牛顿迭代（见子算法１．１）获得

（ ＋ｌ，∞ ＋１， ＋１）＝（ ， ， ）＋ａ ，ｋ＝ｋ＋１，

转步骤１．

子算法１．１牛顿迭代

步骤１．１．１ 由牛顿迭代获得 使得

而ｖＳ ≤ ，（１２） ＩＩ （

，∞ ， ，ｃ Ｉ ’

其中 ∈ａ２ Ｓ（Ｘｋ，ｆ．Ｏｋ， ，ｃ 如果

一（ｖＳ（ ，国 ， ，Ｃ，）） ｄ ≥

ｒａｉｎ｛０，ｌＩ ｖＳ（ｘ ，∞ ， ，Ｃ，）ｌＩ｝

ｌＩ ｄ ｌＩ ｌＩ ｖＳ（ ，∞ ， ，ｃ ）ｌＩ

那么令ｄ ＝ｄ ，否则令

ｄ ＝ｄｔ一 ＶＳ（Ｘｋ，∞ ， ，Ｇ）， （１３）

其中 是个正的参数使得

一（ｖＳ（ｘ，， ， ，ｃ１））Ｔｄ ≥

ｒａｉｎ｛０，ＩＩ ｖＳ（ｘ ，∞ ， ，ｃ ）ｌＩ｝

ｌＩ ｄ ｌＩ ｌＩ Ｓ（ ，∞ ， ，Ｃ ）ｌＩ （１４）

步骤１．１．２现在 ＞０使得

Ｓ（ ， ， ，ｃ ）～Ｓ（（ ，∞ ， ）＋ａ ｄ ，ｃ，）≥

一ｍｉｎ｛ ｌ，ｌＩ ＶＳ（Ｘｋ，（Ｏｋ， ，ｃ ）ｌＩ｝

ａ （ Ｓ（ｘ ，（Ｄｋ， ，Ｃ ））Ｔｄ （１５）

｝ｖＳ（（Ｘｋ，∞ ， ）＋ａ ，Ｃ ）ＴＳ ｝≤

一 ２（ Ｓ（Ｘｋ，∞ ， ，Ｃ ））Ｔ （１６）

一直取ａ６：１

步骤１．１．３令（ ＋１，∞ ＋１， ＋１）＝（ ，∞ ，

）＋ａ ，转步骤１．

可以在适当的条件下证明算法１的全局收敛性

（见文献［５—８］）．

定理３如果假设Ａ１和假设Ａ２成立，算法１

或者在满足 Ｓ（ ，∞ ， ，Ｃ ）＝０和ｚ．（Ｘｋ， ，

∞ ，Ｃ ）≤０的点（ ，（Ｄｋ， ，Ｃ，）处停止；或者当Ｃｆ

达到一定数值时获得一个无穷数列（ ，∞ ， ，

ｃ 如果（ ，∞ ， ）是（Ｘｋ，∞ ， ，ｃ ）的一个

聚点，那么（ ，∞ ， ）是问题ＮＬＰ的ＫＫＴ点．

参考文献：

［１］Ｐｉｌｌｏ Ｇ Ｄ，Ｇｒｉｐｐｏ Ｌ．Ａ ｎｅｗ ｃｌａｓｓ ｏｆ ａｕｇｍｅｎｔｅｄ Ｌａｇｒａｎｇｉａｎｓ ｉｎ

ｎｏｎｌｉｎｅａｒ［Ｊ］．ＳＩＡＭ Ｊ ＣｏｎｔｒａｌＯｐｔ，１９７９，１７：６１６．

［２］ＰｉｌｌｏＧＤ，ＧｒｉｐｐｏＬ．Ａｎ ａｕｇｍｅｎｔｅｄＬａｇｒａｎｇｉａｎｆｏｒｉｎｅｑｕａｌｉｔｙ ｃｏｎ．

ｓｔｒａｉｎｔｓ ｉｎ ｎｏｎｌｉｎｅａｒ ｐｒｏｇｒａｍｍｉｎｇ ｐｒｏｂｌｅｍｓ［Ｊ］。Ｊ ｏｐｔｉｍ．啪ｔ；∞

Ｔｈｅｏｒｅｍ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ，１９８２，３６：４９５．

［３］ＰｉｌｌｏＧＤ．Ｅｘａｃｔ ｐｅｎａｌｔｙｍｅｔｈｏｄ［Ｍ］∥ＩｎＡｌｇｏｒｉｔｈｍｓｆｏｒＣｏｎｔｉｎｕ．

ＯＵＳ Ｏｐｔｉｍｉｚａｔｉｏｎ：ｔｈｅ ｓｔａｔｅ ｏｆ ｔｈｅ ａｒｔ．Ｂｏｓｔｏｎ：Ｋｌｕｗｅｒ Ａｅ Ｐｒｅｓｓ．

１９９４：１—４５．

［４］Ｐｉｌｌｏ Ｇ Ｄ，Ｌｕｃｉｄｉ Ｓ．Ｏｎ ｅｘａｃｔ ａｕｇｍｅｎｔｅｄ Ｌａｇｒａｎｇｉａｎ ｆｕｎｃｔｉｏｎｓ ｉｎ

ｎｏｎｌｉｎｅａｒ ｐｒｃ￣ｒｒａｍｍｉｎｇ ｐｒｏｂｌｅｍｓ［Ｍ］∥Ｉｎ Ｎｏｎｌｉｎｅａｒ Ｏｐｔｉｍｉｚａ．

ｔｉｏｎ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ．Ｎｅｗ Ｙｏｒｋ：Ｐｌｅｎｕｍ Ｐｒｅｓｓ，１９９６：８５—１００．

［５］Ｐｕ Ｄ．Ａ ｃｌａｓｓ ｏｆ ａｕｇｍｅｎｔｅｄ Ｌａｇｒａｎｇｉａｎ ｍｕｌｔｉｐｌｉｅｒ ｆｕｎｃｔｉｏｎ［Ｊ］．

Ｊｏｕｒｎａｌ ｏｆ Ｓｈａｎｇｈａｉ Ｉｎｓｔｉｔｕｔｅ ｏｆＲａｉｌｗａｙＴｅｃｈｎｏｌｏｇｙ，１９８４，（５）：

４５。

［６］ＰｕＤ，ＴｉａｎＷ．Ｃ￣ｌｏｂａｌｌｙ ｉｎｅｘａｃｔ ｇｅｎｅｒａｌｉｚｅｄＮｅｗｔｏｎｍｅｔｈｏｄｓ ｆｏｒ

ｎｏｎｓｍｏｏｔｈ ｅｑｕａｔｉｏｎ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎａｌ ａｎｄ Ａｐｐｌｉｅｄ

Ｍａｔｈｅｍａｔｉｃｓ，２００２，２０：２８９．

［７ｊ Ｐｕ Ｄ，Ｇｕｉ Ｓ，Ｔｉａｎ Ｗ．Ａ ｃｌａｓｓ ｏｆ ｒｅｖｉｓｅｄ Ｂｍｙｄｅｎ ａｌｇｏｒｉｔｈｍｓ ｗｉｔｈ—

Ｏｕｔ ｅｘａｃｔ ｌｉｎｅａｒ ｓｅａｒｃｈ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｍａｔｈｅｍａｔ—

ｉｃｓ，２００４，２２：１１．

［８］Ｐｕ Ｄ，Ｚｈｏｎ Ｙ，Ｚｈａｎｇ Ｚ．Ａ ＱＰ ｆｒｅｅ ｆｅａｓｉｂｌｅ ｍｅｔｌｘｘｔ［Ｊ］．Ｊｏｕｒｎａｌｏｆ

Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｍａｔｈｅｍａｔｉｃｓ，２００４，２２：６５１．

Ｓ

十

一

ＩＪ

足

满

维普资讯