半定规划问题的两种数值解法

青岛大学

硕士学位论文

半定规划问题的两种数值解法

姓名：薛丹

申请学位级别：硕士

专业：计算数学

指导教师：田志远

20100530

摘要

本文研究非线性半定规划问题的最优性条件和数值解法。全文包括三个部分。

第一章介绍了半定规划有关的基本知识和最优性理论，对于含等式约束的一类非光滑半定规划问题证明了其一阶必要性条件和二阶的充分和必要性条件。

第二章针对一般非凸半定规划问题，给出了一个非线性Ｌａｇｒａｎｇｅ函数，讨论了函数在ＫＫＴ点的性质，推广了Ｌａｇｒａｎｇｅ乘子法。分析了算法的收敛性，并给出了与罚参数相关的解的误差估计，在适当的条件下，当罚参数大于某一阈值时，算法产生的点列收敛到ＫＫＴ点。数值算例也说明了算法的可行性和有效性。

第三章将标准形式的半定规划进行转化，给出了求解较大规模半定规划问题的解析中心割平面算法，证明了算法的收敛性定理，并用实际算例验证了算法的有效性。算法的执行或者有限步终止，或者产生一个收敛到解的点列。

关键词：半定规划；最优性条件；非线性Ｌａｇｒａｎｇｅ算法；解析中心；割平面

Ａｂｓｔｒａｃｔ

ａｎｄｎｕｍｅｒｉｃａｌｍｅｔｈｏｄｓｏｆｎｏｎｌｉｎｅａｒｓｅｍｉｄｅｆｉｎｉｔｅＯｐｔｉｍａｌｉｔｖｃｏｎｄｉｔｉｏｎｓ

ｔｈｅｆｏｌｌｏｗｉｎｇｔｈｒｅｅｐａｎｓ・ｐｒｏｇｒａｍｍｉｎｇｗｅｒｅｓｔｕｄｉｅｄｉｎｔｈｉｓｐａｐｅｒｗｈｉｃｈｉｎｃｌｕｄｅｄ

Ｔｈｅｆｉｒｓｔｃｈａｒｔｅｒｄｅｓｃｒｉｂｅｄｔｈｅｂａｓｉｃｋｎｏｗｌｅｄｇｅｏｆｓｅｍｉｄｅｆｉｎｉｔｅｐｒｏｇｒａｍｍｉｎｇ，

ｎｅｘｔｏｕｔｌｉｎｅｄｏｐｔｉｍａｌｉｔｙｃｏｎｄｉｔｉｏｎｓ，ｗｈｉｃｈｗｅｒｅｐｒｅｐａｒｅｄｆｏｒｔｈｅＬａｇｒａｎｇｅｍｅｔｈｏｄｉｎｔｈｅ

ｃｈａｐｔｅｒ，ａｎｄｏｎｔｈｉｓｂａｓｉｓ，ｗｅｄｅｒｉｖｅｄｏｐｔｉｍａｌｉｔｙｃｏｎｄｉｔｉｏｎｓｆｏｒａｃｌａｓｓｏｆｎｏｎ－ｓｍｏｏｔｈｓｅｍｉｄｅｆｉｎｉｔｅｐｒｏｇｒａｍｍｉｎｇｐｒｏｂｌｅｍｗｉｔｈｅｑｕａｌｃｏｎｓｔｒａｉｎｔｓ・

Ｉｎｔｈｅｓｅｃｏｎｄｃｈａｐｔｅｒ，ａｎｏｎｌｉｎｅａｒＬａｇｒａｎｇｅｆｕｎｃｔｉｏｎｆｏｒｇｅｎｅｒａｌｎｏｎｃｏｎｖｅｘ

ｓｅｍｉｄｅｆｉｎｉｔｅｐｒｏｇｒａｍｍｉｎｇｗａｓ

ｆｕｎｃｔｉｏｎ

ｂａｓｅｄｏｎｏｎｇｉｖｅｎ．ＷｅａｎａｌｙｚｅｄｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｏｆｔｈｉｓＬａｇｒａｎｇｅｔｈｅＫＫＴｐｏｉｎｔ．Ｕｎｄｅｒｓｏｍｅｃｏｎｄｉｔｉｏｎｓ，ｔｈｅｌｏｃａｌｃｏｎｖｅｒｇｅｎｃｅｏｆｔｈｅｍｅｔｈｏｄａｔｈｉｓｆｕｎｃｔｉｏｎＷａｓｐｒｏｖｅｄｔｈａｔｔｈｅｒｅｅｘｉｓｔｓｔｈｒｅｓｈｏｌｄｏｆｔｈｅｐｅｎａｌｔｙｐａｒａｍｅｔｅｒ

ｗｈｅｎｓｕｃｈｔｈａｔｔｈｅｓｅｑｕｅｎｃｅｐｒｏｄｕｃｔｓｏｆｔｈｅａｌｇｏｒｉｔｈｍｌｏｃａｌｌｙｃｏｎｖｅｒｇｅｔｏｔｈｅＫＫＴｐｏｉｎｔ

ｔｈｅｐｅｎａｌｔｙｐａｒ锄ｅｔｅｒｉｓｍｏｒｅｔｈａｎｔｈｅｔｈｒｅｓｈｏｌｄ．Ｂｅｓｉｄｅｓ，ｔｈｅｅｒｒｏｒｂｏｕｎｄｏｆｔｈｅｓｏｌｕｔｉｏｎｓｗｉｔｈｔｈｅｐｅｎａｌｔｙｐａｒａｍｅｔｅｒｗａｓｅｓｔｉｍａｔｅｄ．Ｎｕｍｅｒｉｃａｌｅｘａｍｐｌｅｓａｌｓｏｄｅｍｏｎｓｔｒａｔｅｄｔｈｅｅｘｅｃｕｔｉｏｎａｎｄｅｆｆｅｃｔｉｖｅｎｅｓｓ．

Ｉｎｔｈｅｔｈｉｒｄｃｈａｐｔｅｒ’ａｎｆｏｒｓｏｌｖｉｎｇａｎａｌｙｔｉｃｃｅｎｔｅｒｃｕｔｔｉｎｇｐｌａｎｅｍｅｔｈｏｄｗａｓｇｉｖｅｎ

ｔｈｅｌａｒｇｅ．ｓｃａｌｅｓｅｍｉｄｅｆｉｎｉｔｅｐｒｏｇｒａｍｍｉｎｇ．Ｔｈｅｃｏｎｖｅｒｇｅｎｃｅｏｆｔｈｉｓｍｅｔｈｏｄｗａｓｐｒｏｖｅｄ，ａｎｄｅｖｅｎｔｕａｌｌｙｔｈｅｐｒａｃｔｉｃａｌｅｘａｍｐｌｅＷａｓｒｅｐｏｒｔｅｄ．

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

学位论文独创性和知识产权权属声明

学位论文独创性声明

本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成果。

本人如违反上述声明，愿意承担由此引发的一切责任和后果。

论文作者签名：≮军骨日期：Ｈｐ年ｌ｜［月巾

学位论文知识产权权属声明

本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为青岛大学。

本学位论文属于：

保密口，在

不保密叼。

（请在以上方框内打“√’’）

论文作者签名：年解密后适用于本声明。脊再Ｉ日期：ｗＪＤ年叶月）７日

日期：年月日导师签名：

（本声明的版权归青岛大学所有，未经许可，任何单位及任何个人不得擅自使用）

引言

己Ｉ吉Ｊ口Ｊ

半定规划是半正定矩阵上的线性规划。近二十年来半定规划的理论和算法取得了很大的进展，广泛应用于组合优化，系统工程和电子工程等领域，它已逐渐成为数学规划领域中一个非常活跃的研究方向。

２０世纪６０年代，由Ｒ．Ｂｅｌｌｍａｎ和ｉ．Ｆａｎ［２９１构造了一个半定规划问题，他们考虑将线性规划中的向量变量用矩阵变量代替，并且给出了对偶理论以及强对偶理论成立的一个Ｊ下则条件。２０世纪７０年代初，Ｄｏｎａｔｈ和Ｈｏｆｆｍａｎ，Ｃｕｌｌｕｍ和ｗ０１ｆｅ把一些难的图分割问题转化为一个特征值优化问题求解，而这个问题的求解又可以转化为半定规划问题。二十多年里半定规划问题一直没有受到关注，主要是由于半定规划的可行集不再是多面体，并且没有适用的单纯形法。内点法问世以后，对半定规划领域的研究才逐渐火爆起来，使得半定规划获得了飞速的发展。１９９２年，Ｎｅｓｔｅｒｏｖ，Ｎｅｍｉｒｏｖｓｋｙ，Ａ１ｉｚａｄｅｈ与Ｋａｍａｔｈ，Ｋａｒｍａｒｋａｒ独立的把ＬＰ的内点法推广到半定规划，使内点法成为求解半定规划问题的主要算法。

半定规划问题的标准形式是

ｒａｉｎＣ・ｘ

Ｓ１．越＝ｂ

Ｘ≥０．

其中∥表示玎×刀对称矩阵集合。鄙表示以×，ｚ半正定矩阵集合。Ｘ≥０表示Ｘ∈掣。Ｃ・ｘ表示ｔｒ（ＣｒＸ）。月是Ｓ”一尺‘的线性映射，可以认为月是由后个线性函数构成的，约束魁＝ｂ等价于后个线性约束乃－Ｘ＝６ｆ，ｆ＝１，…Ｊｊ｝．

近些年来国内外对于半定规划的研究主要集中在线性半定规划的研究上，上个世纪末本世纪初，半定规划问题的研究又被推广到非线性半定规划问题上，即线性或非线性目标函数受到（非线性）矩阵不等式和（或）向量不等式约束的优化问题

ｍｉｎｆ（ｘ）

Ｊ．，．日（力≥０且办（ｚ）＝０（１）其中ｆ：Ｒ”ｊＲ，日：Ｒ”专畔（群是由聊×肌的半定矩阵组成的空间）和ｈ：Ｒ”一Ｒｐ．

青岛人学硕十学位论文

这种半定规划问题主要来自最优结构设计、最优鲁棒控制、鲁棒反馈控制设计等领域，由于线性半定规划不能给出满意模型的优化问题而且非线性半定规划才刚刚起步，它的发展还很不成熟，因此研究求解非线性半定规划的算法无疑是有重要意义的。Ｓｈａｐｉｒｏ１４Ｉ通过锥的性质给出了非线性半定规划一阶和二阶最优性条件，

ＦｏｒｓｇｒｅｎＩ’１采用非线性规划的最优性条件分析的技巧也讨论了非线性半定规划的最优性条件。无论在线性规划中还是在非线性规划中，罚函数法和对数函数法对算法的研究起着重要的作用。Ｍｏｓｈｅｙｅｖ，Ｚｉｂｕｌｅｖｓｋｙ提出了一类惩罚／障碍乘子方法用于求解约束为线性矩阵不等式的非线性半定规划问题。Ｂｕｒｅｒ，Ｍｏｎｔｅｉｒｏ，ｚｈａｎｇ考虑将一类特殊的半定规划转化为非线性规划进行求解。Ｊａｒｒｅ，Ｒｉｎｇｅｒｔｚ采用障碍方法求解非线性半定规划。然而，障碍方法要求迭代初始点是严格可行的内点，这一要求在实际中往往很难满足。为克服上述方法的不足，Ｈｅｓｔｅｎｓ与Ｐｏｗｅｕ各自独立提出了近似增广Ｌａｇｒａｎｇｅ函数，来求解具有等式约束的非线性优化问题，最初的乘子法是基于二次增广Ｌａｇｒａｎｇｅ函数建立的，这一方法的优点在于克服了早期罚函数的病态问题以及收敛速度慢等弱点。后来Ｇｌａｄ研究了对增广Ｌａｇｒａｎｇｅ函数中的Ｌａｇｒａｎｇｅ乘子的不同的更新方法的收敛性质。Ｂｏｇｇｓ＆Ｔｏｎｅ（１９８０）引入了一类新的乘子法，发展了对偶理论，构造了一类新的惩罚函数并建立了精确罚函数和乘子法的联系。随着将增广Ｌａｇｒａｎｇｅ法和非线性Ｌａｇｒａｎｇｅ乘子法从非线性规划推广到半定规划中去，Ｌａｇｒａｎｇｅ算法成为解非线性半定规划的最有效的方法之一。

Ｌａｇｒａｎｇｅ算法主要研究由标准半定规划问题转化而来的半定规划问题（１），非线性Ｌａｇｒａｎｇｅ函数是经典Ｌａｇｒａｎｇｅ函数的变形，半定规划问题的经典的Ｌａｇｒａｎｇｅ函数是

三（ｘ，Ｕ，矿）＝ｆ（ｘ）－＜Ｕ，日（ｘ）＞＋＜Ｖ，办（ｘ）＞．

此Ｌａｇｒａｎｇｅ函数提供了一种从约束优化问题到无约束问题求稳定点的转换，它是刻画最优化特征以及构造最优化算法的基本工具。

半定规划的一个增广Ｌａｇｒａｎｇｅ函数为

驰姗ｆ）＿胁冲√ｕ一半）ｈ２圳２】＋＜ｍ∽＞＋譬．

实际生活中遇到的半定规划问题大多数是非线性的，包括非光滑半定规划，非

引言

凸半定规划等，本文研究非线性半定规划的一些数值方法。在第一章，我们探讨了一类非光滑半定规划的最优性条件。第二章，在满足非凸半定规划最优性条件的基础上，我们给出了一般形式的非线性Ｌａｇｒａｎｇｅ函数，讨论了函数在ＫＫＴ点的性质，给出了非线性Ｌａｇｒａｎｇｅ算法，在适当的条件下，证明了当罚参数大于某一阈值时，算法具有局部收敛性，并给出了与罚参数相关的解的误差估计。数值算例验证了算法的可行性和有效性。第三章将标准形式的半定规划问题进行转化，给出了可以用于求解较大规模半定规划问题的解析中心割平面算法，证明了算法的收敛性，实际算例表明了算法的有效性。

本文中常用到的符号如下：

矩阵Ａ≥０表示Ａ是一个半正定矩阵。令Ｒ眠”表示ｍｘ以的矩阵构成的空间。对于向量口，ｂ∈Ｒ”，我们定义内积＜口，ｂ＞＝ａｒｂ，对于矩阵么，Ｂ∈ＲＭ，内积为＜Ａ，Ｂ＞＝Ａ・Ｂ＝ｖｅｃ（Ｂ）７’ｖｅｃ（Ａ）＝ｔｒ（Ｂ７’么），（其中ｖｅｃ（Ａ）表示由Ａ的列向量组成的行２×１的向量，护（么）代表矩阵彳的迹），本文中相应的向量范数取２．范数，矩阵范数

ｑｌＢａ１２Ｂ…ａＩ＂Ｂ

取Ｆ．范数。符号圆表示矩阵的克罗内克积Ａ圆Ｂ＝嘭１Ｂ呸２Ｂ…ａ２。Ｂ，它是一

％ｌＢ％２Ｂ…％。Ｂ

个刀２×疗２矩阵。符号Ｖ，厂（ｘ）表示／（ｘ）在ｘ处的梯度，而Ｖ２，ｆ（ｘ）＝Ｖ，（Ｖ，厂（ｘ））．Ｖ，乃（ｘ）表示办（ｘ）在ｘ处的梯度，Ｖ。曩（ｘ）表示其第ｉ行。其中Ｅ（ｘ）＝胡（ｘ）／屯是ｍ×ｍ的偏微分矩阵。我们由此定义ｍ２×刀的矩阵讲（ｘ）／锄：＝［ｖｅｔ（Ｈｉ（ｘ）），…，ｖｅｃ（乜（ｘ））】．

第一章最优性条件

弟一早取饥。ｌ土氽’Ｉ十第一章最优性条件

１．１基础知识

目前许多专家和学者正致力于非线性半定规划（ＮＬＳＤＰ）的研究，尤其是对于大规模（ＮＬＳＤＰ）的研究，讨论了其最优性条件。相关学者对非凸半定规划【１１和非光滑半定规划１３１的最优性条件作出了突出贡献，本章对已有理论进行推广，证明了带有等式约束和不等式约束的一类非光滑半定规划问题的最优性条件。

我们考虑下面的半定规划问题

ｍｉｎｆ（ｘ）

ｓ２．日（ｘ）≥０且办（ｘ）＝０（２）

其中Ｈ：Ｒ”一算（算是由ｍｘｍ的半定矩阵组成的空间）和ｈ：Ｒ”一只尸，且它们是二次可微的。ｆ：Ｒ”专Ｒ，是连续可微的，并且Ｖ，ｆ（ｘ）是局部Ｌｉｐｓｃｈｉｔｚ的。定义１．１［３１设ｆ（ｘ）是连续可微函数，如果存在三使得

ｌｉｍ。２ｆ（ｘ＋ｔｄ）－ｆ（ｘ），－ｔ＜Ｖｆ（ｘ），ｄ＞．：Ｌ，

则称三为ｆ（ｘ）在ｚ关于方向ｄ的二阶Ｐｅａｎｏ导数，记为刀（ｘ；ｄ）．

上下Ｐｅａｎｏ导数分别定义为

抛炉ｌｉ嚷渺２坐盟丛半盥业，

硝Ｉｘ；ｄ）－ｌｉｍｍｓｕｐｆ‘Ｏ２—ｆ（ｘ—＋ｔｄ—）－—ｆ（ｘｒ）－ｔ—＜Ｖ—ｆ（ｘ），ｄ＞．Ｚ

设问题（２）的可行点为Ｘ‘，即Ｈ（ｘ‘）≥ＯＨｈ（ｘ‘）＝０，定义ｍ×ｍ阶正交矩阵Ｑ，Ｏ＝（ｇ，Ｑ）其中ｇ的列向量形成Ｈ（ｘ＋）列生成空间的一组基，Ｑ的列向量构成Ｈ（ｘ＋）零空间的一组基。矩阵Ｑ依赖于点ｘ‘，Ｑ不一定唯一。

设％，％分别是矩阵Ｑ与０２的列向量的维数，Ｓｍ为ｍｘｍ阶对称矩阵空间。定义集合１１１

Ｓ（Ａ，ｘ’）＝｛Ｍ：Ｍ∈Ｓ”，ｍ，，＝Ｏ如果３占＞０，对于使％（ｘ）＝０的任意ｘ，有

青岛人学硕十学位论文

ＩＸ－－Ｘ＋１１＜，／；其中么是从Ｒ”到ｓ”的二次连续函数。

Ｂ（Ａ，ｘ。）＝｛Ｍ：Ｍ∈Ｓ”，ｍｑ＝０如果ｆ，／属于与Ｓ（Ａ，ｘ。）相关的连通图的不同连通分支）。

则有

Ｓ（Ａ，ｘ’）∈８（Ａ，ｘ‘）．

令ｘ充分接近ｘ＋，使得研１Ｈ（ｘ）Ｑｉ＞０。对称矩阵疗（ｘ）定义为

疗（工）＝日（ｘ）一Ｈ（ｘ）ＱＩ（Ｑ［Ｈ（ｘ）Ｑｉ）一ＱｆＨ（ｘ），

则Ｆｌ（ｘ）为局部可行矩阵。下面给出疗（ｘ）的相关性质。

引理１．１如果彳和Ｂ是半正定对称矩阵，则爿Ｂ有实的非负特征值。特别地，有ｔｒ（ＡＢ）≥０．

引理１．２【１１设Ｈ（ｘ‘）≥０成立，则ｆｌ（ｘ‘）＝０，对于充分接近ｘ’且满足骈’Ｈ（ｘ）Ｑ＞０的点ｘ，有讲疗（ｘ）＝ｏ；疗（ｘ）≥ｏ当且仅当日（ｘ）≥ｏ．

引理１．３【１１设Ｈ（ｘ’）≥Ｏ成立，则下面关系式成立

疗（ｘ・）Ｑ１：ｏ；醒掣盟鲮：醇翌盟Ｑ，㈦，２，…，刀．

引理１．４Ⅲ设日（ｘ・）≥ｏ成立，则矩阵鹾掣Ｑ，ｆ：ｌ，２，…，刀．生成空间｛Ｑ；ＭＱｚ：Ｍ斛肌．）｝，当且仅当矩阵掣小１，２，…以生成｛９－．２Ｑ乒ＭＱ２醇：Ｍ∈ｓ（Ｂ，ｘ’））．

由上面疗（ｘ）的性质可知，在ｘ＋的某个邻域内，问题（２）等价于下面问题

ｍｉｎ厂（ｘ）

ｓＪ．疗（ｘ）≥０

办（ｘ）＝０．Ｏｘ，Ｏｘ，

设ｘ‘是问题（２）的可行点，对于充分接近ｘ＋且满足ＱｒＨ（ｘ）Ｑ，＞０的点Ｘ定义局部半定Ｌａｇｒａｎｇｅ函数：

Ｌ（ｘ，Ｕ，ｙ）＝ｆ（ｘ）－＜Ｕ，Ⅳ（ｘ）＞＋＜Ｖ，办（ｘ）＞．

第一章最优性条件

１．２一类非光滑半定规划问题的最优性条件

为引出最优性条件，先给出以下定义和定理：

定义１．２１３１满足Ｈ（ｘ’）≥０的点ｘ＋被称为一个正则点，如果

（ａ）

（ｂ）矩阵醇型婺垒Ｑ，江１，２，…，门，生成空问｛醇ＭＱ：Ｍ∈ｓ（疗，ｘ’）｝姒ｊ｛醒’朋鲮：Ｍ∈ｓ（疗，ｘ‘））中存在一个正定矩阵。

定义１．３ｔ３１问题（２）的一个可行点ｘ’∈Ｒ”称为稳定点或ＫＫＴ点，如果存在Ｕ＋∈ｓ７，Ｖ＋∈Ｒｐ使得在点（ｘ‘，ｕ＋，矿＋）处满足下面条件：

（ａ）掣圳．掣巾州ｘ＋矿Ｖ’，川，…儿ＣⅨｆＬⅨ，

（ｂ）Ｕ’Ｈ（ｘ’、）＝０，Ｕ‘≥０．

定理１．１Ｉｌｌ设ｘ’是问题（２）的一个正则点和局部极小点，则存在矩阵

Ｕ‘∈｛Ｑ醴嵫醇：Ｕ∈Ｂ（ｆ－１，ｚ’）），Ｖ‘∈Ｒ尸使得

掣－ｔｒ（－ＯＨ，（ｘ＇）Ｕ＋）叩烈ｘ’矿Ｖ’，Ｈ，…儿吼ＪＣⅨ，

Ｕ‘Ｈ（ｘ‘）＝０，Ｕ＋≥０．

下面给出此类非光滑半定规划的一阶最优性条件：

定理１．２假设ｘ‘∈Ｒ”是问题（２）的一个可行点，存在矩阵ｕ＋∈｛Ｑ２醒’嗡ｇ：Ｕ∈Ｂ（ｆＪ，Ｘ‘）），Ｖ’∈ＲＰ满足

掣－ｔｒ（掣ｕ・）巾鲰ｘ．））～Ｖ，川，…，咒；Ｌ珥ｆＣ珥，

Ｕ‘Ｈ（ｘ‘、）＝０，Ｕ‘≥０．

而且声，』（ｘ）是凹函数，ｉ＝１，…，刀，ｊ＝ｌ，…，刀（Ｅ，Ｊ（ｘ）代表矩阵疗（ｘ）的元素），ｈ（ｘ）是凸函数，那么ｘ＋是问题（２）的一个局部极小点。

证明由条件知局部半定Ｌａｇｒａｎｇｅ函数

三（ｘ，Ｕ，Ｖ）＝／（ｘ）一＜Ｕ，ｆｔ（ｘ）＞＋＜Ｖ，厅（ｘ）＞是凸函数，由次微分的定义知

０∈比（ｘ’，Ｕ‘，Ｖ’），零向量是函数三（ｘ，Ｕ，Ｖ）在点（ｘ‘，Ｕ＋，ｙ’）处的次梯度，因此任给可行点Ｙ，有

青岛人学硕十学位论文

Ｌ（ｙ，Ｕ＋，Ｖ’）２三（ｘ＋，Ｕ’，Ｖ＋）＋＜Ｏ，ｙ—ｘ＋＞，即

厂（Ｊ，）一＜Ｕ’，ｆｆＩ（ｙ）＞十＜ｙ‘，办（ｙ）＞

≥ｆ（ｘ＋）一＜Ｕ’，ｇ（ｘ’）＞＋＜ｙ’，ｈ（ｘ’）＞＋＜０，ｙ－ｘ’＞

因为ｘ＋满足Ｈ（ｘ’）≥０，ｈ（ｘ’）＝０，由引理１．２知ｇ（ｘ’）＝０．由Ｙ的可行性知疗（ｙ）≥０，办（Ｊ，）＝０，由引理１．１知＜Ｕ’，ｆＩ（ｙ）＞≥０．因此对于任意可行点Ｙ，下面不等式成立

厂（ｙ）≥ｆ（ｘ’）．

从而可知ｘ’是问题（２）的一个局部极小点。

为引出二阶最优性条件先给出一个引理：

引理１．５¨１设ｄ∈Ｒ”，ｇ是从Ｒ”到Ｓ肿的二次连续函数。Ｑ是ｍ×ｍ阶Ｊ下交矩阵，分块形式为Ｏ＝（Ｑ口，Ｑ）。如果点ｘ＋的某邻域中的点满足，ｇ（ｘ）Ｑｏ＝０，并且如果ｍ×ｍ阶矩阵诒（ｘ‘）／缸，ｉ＝ｌ，…，胛生成空间｛ＱｇＴ』Ⅵ场场１’：Ｍ∈Ｓ（ｇ，ｘ＋）），则存在占＞０以及一个二次可微连续函数ｘ（，），Ｖｔ∈（一占，ｓ）满足

石（ｏ）＝ｚ’，石’（ｏ）＝ｄ且ｇ（ｚ（啪＝ｇ（石‘）＋∑ｄ。（ａｇ（ｘ’）／Ｏｘ，）ｔ．

引理１．６…设ｇ是从尺”到Ｓ”的二次连续函数，假设ｘ’，ｄ。和ｆ‘满足ｇ（ｘ’）＝Ｏ，ｇ（ｘ’＋ｆ㈨ｄ）≥ｏ，ｆ‘≥ｏ，ｌＩｄｋ｜Ｉ＝１，！觋ｆ‘＝ｏ，！ｉ—ｍｄ。＝ｄ＋，则有

兰笺墨狐乞瓠ｉｊ

定理１．３设ｘ’是问题（２）的一个正则点和局部极小点，则存在矩阵Ｕ’∈｛０２讲ｖ０２醇：Ｕ∈Ｂ（ｇ，ｘ‘）），Ｖ’∈Ｒ尸，满足下列关系式：

吼ｆ掣叫掣∽巾胤ｘ＋））７’‘Ｖ，㈦，…，丹；Ｌ珥ｊ

Ｕ‘Ｈ（ｘ’）＝０，Ｕ‘≥０．

Ｊｊ．Ｖｄ叭肌喜埘掣Ｑ２＿ｏ，（Ｖ姒ｘ．））‰帅有

互：（ｘ＋，ｕ＋，Ｖ’；ｄ）≥０．

证明定理１．１知存在矩阵ｕ＋∈｛０２谚崛讲：Ｕ∈Ｂ（／－Ｉ，ｘ’）），Ｖ‘∈ＲＰ，满７

———————————————————————————————————一一足弟～覃最优性条什

警卸（掣∽书朋ｘ．））ｙ小】，．一…

Ｕ‘Ｈ（ｘ’）＝０，Ｕ‘≥０．

现假设ｄ∈Ｒ”满足：

喜醇掣Ｑ删巾崩ｘ．）），删．

根据引理１．３有，疗（ｘ＋）Ｑｌ＝ｏ；型娶立：瑶望挚立鲮，江，，…，厅．ｘ，。０ｘ二—。。。。

矿警纠删警ｃ嘲蚓’警喇警Ｑ．毗拭等价于髟掣鳓一ｏ，又由于Ｑ为正贿则喜警删．因为ｘ’是个Ｊ下则点，由引理１．５知，存在ｓ＞Ｏ以及一个二次可微连续函数ｘ（ｆ），舯《啦ｚ‘一，（ｏ）卸柚籽吲唱晡眦））－肌ｗ喜警如。，厅（ｚ（嘞＝办（ｘ‘）＋喜Ｖ，曩（ｘ’）谚ｆ＝（Ｖｘｈ（ｘ‘））７’衍＝。．设Ｇ（，）：厂（ｘ（泖，因为ｘ＋是局部极小点，所以有

Ｇ’（Ｏ）＝Ｖｆ（ｘ‘）７’ｄ＝０，

ｇ（ｏ；ｄ）：ｌｉｍ．ｉｎｆ２Ｇ（Ｏ＋ｔｄ）－Ｇ（Ｏ），－ｔ＜ＶＧ（０），ｄ＞．，４，０ｆｚ

＝易（ｘ‘；ｄ）＋夥（ｘ’）７’，（０）

由Ｐｅａｎｏ导数

鲜（ｏ；１）：ｌｉｍ．ｉ．ｎｆ２Ｇ（０＋ｔ）－Ｇ（０），－ｔ＜ＶＧ（０），１＞．‘，山Ｏ—ｚ

：ｌｉｍｉｎｆ２

ｔ‘Ｏｆ（ｘ（ｔ））－ｆ（ｘ＊）－ｔＶｆ（ｘ＇）ｒｘ＇（Ｏ）．●２

：ｌｉｍ．ｉｎｆ２

，山０ｆ（ｘ＋＋ｘ（ｔ）－ｘ’）－ｆ（ｘ’）－ｔ＜Ｖｆ（ｘ’—），ｘ＇（—０）＞・２８

青岛人学硕十学位论文

也ｍｉ。ｎｆ（２巡业型丝孚型巡型坠＋

２丝！旦！丛生型坚丝堕竺燮）ｔ‘

删咄ｘ＇（Ｏ））＋ｌｉｍ川ｉｎｆ（２竺竺生竽竺竺，川—————ＬＦ———一）删ｏ）．“ｏ）“嘧ｆ２掣ｔ２≥鬈（ｘ（ｏ）；

兵甲

ｆ、ｌ０时，孝山０，ｘ（７７）—争ｘ（０）．＝职＾～ｕＪ，ｏｘ’（ｏ））＋Ｗ（ｘ（ｏ））ｒ，（ｏ），ｘ（刁）∈（ｘ（。）＋反，（ｏ），ｘ（。）＋∥（。）＋ｉｔ２，（跏孝∈（。，，）．

同理，鲜（ｏ；一１）≥墨（ｘ（ｏ）；一一（ｏ））＋夥（ｘ（ｏ））ｒ，（ｏ），因此有

＿Ｇｐ一（ｏ；ｄ）＝Ｚ又ｘ’；ｄ）＋Ｖ厂（ｘ‘）７’ｘ’（ｏ）≥ｏ．

又由于，对于ｒ∈（－ｃ，ｓ）有疗（ｘ（ｆ））＝０，因此

塑盟Ｑ！：ｏ，一ｄ２／４（ｘ（Ｏ）：ｏ．即一ｄ２ｆｌ（ｘ（Ｏ））＝势掣＋芸警㈣＝。

带入ｕ’得，护（ｄ２／－Ｉ讲（ｘ。（Ｏ））－ｕ＋）

＝窆１＝１蜘．／＝１

由乃（ｘ（ｆ））＝ｏ，ｃ鬻∽哆＋嘉护ｃ警∽邶瑚得掣＝ｏ，了ｄ２ｈ（ｘ（Ｏ）＝ｏ．带入ｙ’得，ｄｔａｃｔ‘（１．２）ｄ７’（Ｊ。＠Ｖ‘ｒ）Ｖ，（ｖｅｃＶ，厅（ｘ））ｄ＋Ｖ‘７１Ｖ。ｈ（ｘ）ｘ”（Ｏ）＝０．（１．３）

９

’第一章最优性条什

由（１．１），（１．２）和（１．３）式得：

舭ｍ耵Ｆｎ仰）一窆ｉ＝１赫ｊ＝ｌ（鬻∽吒一骞护（警∽羽）

一ｄ７’（ＬｏＶ．ｒ）Ｖ，（ｖｅｃＶ，厅（ｘ））ｄ—Ｖ”Ｖ，ｈ（ｘ）ｘ”（Ｏ）≥０．

由Ｐｅａｎｏ导数定义可得

跏’删’娜啊Ⅳ＾即）一喜驴（警∽羽）＋ｖ＊ｒｖｘｈ（ｘ矿（０））瑚ｘ‘ｗ’娜芬等却（警∽＋Ｖ＇ｒＶｘ删们）＞０因为秒（ｘ‘）／叙，：护（型垒垒ｕ‘）一（ｖ，厅，（ｘ’））ｒｙ’，歹：ｌ，…，刀，故锻一。。

髟（ｘ’，ｕ’，Ｖ’；ｄ）≥ｏ．

定理１．４设Ｘ＋是问题（２）的一个正则点和ＫＫＴ点，即存在矩阵Ｕ。∈｛ＱＱ；’吆鳞：Ｕ∈Ｂ（疗，ｘ＋）｝，Ｖ‘∈Ｒｐ，使得

ｕ＋Ｈ（ｘ＋）：０，ｕ＋≥Ｏ和可（ｘ‘）／ａＩ：ｕ＋・—ｃｇ—Ｈ＝（一ｘ＇）一（ｖ。矗（ｘ＋））７’矿‘，ｆ：１，…，刀．且对于任意的｛ｄ∈彤，ｄ≠０．喜ｚＱｒ望墓竽Ｑ２＝。且（Ｖ。办（ｘ．））７’ｄ＝。），有２（ｘ＋，ｕ＋，Ｖ’；ｄ）＞０，则ｘ‘是问题（２）的严格局部极小点。

证明假设定理条件成立，但ｘ‘并不是局部极小点，则存在一点列｛∥），对于Ｖｋ有矿≠ｘ’，！ｉｍ，。ｘ。＝ｘ’，且满足日（∥）≥ｏ，ｈ（ｘ‘）＝ｏ但厂（∥）≤厂（ｘ’），令扩２网Ｘｋ－－Ｘ＊，记矿＝ｚ‘删，则对于每个七都蚓矿ｌＩ＝１，，★≠。一…ｌｉｍ，★＝。・由于每个ｄ‘都包含于一个紧集，不失一般性，可以假设对于ｄ。∈Ｒ”，有ｌｉｍｄ。＝ｄ＋．

正—’∞

由Ｈ（ｘ‘）≥０，根据引理１．２，当ｋ充分大时，有疗（≯）≥０。由Ｕ‘存在性，表明ｔｒ（／３（ｘ‘）Ｕ‘）≥０．１０

青岛人学硕十学位论文

微分得：科（，）＝喜驴（学【，‘）衫啪）＝喜喜咖（掣∽《．

当，＝０时，因为Ｕ’Ｈ（ｘ‘）＝０所以Ｕ‘为Ｈ（ｘ。）的零空问中的矩阵。又因为Ｑ为Ｈ（ｘ＋）的列生成空间中的基，因此讲ｕ‘＝０，则

椰）＝喜护（掣∽矽＝喜护（掣∽棚，

当ｔ＝ｔ‘时，

啪兮能（０）＋譬硝（ｏｋｔｋ）＞ｏ∥∈（０，１）．

ｆ（ｘ‘＋ｔｋｄｋ）川ｘ‘）＝ｔｋＶ，弛ｙｄ‘＋譬墨（ｚ＋＋孝ｋｔｋｄｋ；ｄｋ）＜０，艮（ｏ，１）．因为ｈ（ｘ。）＝０，有ｈ（ｘ‘＋，‘ｄ‘）＝ｈ（ｘ‘＋，‘ｄ。）一ｈ（ｘ‘）

纠Ｖ以ｚＶ。＋譬（办ｌ＂Ｖｘ２ｈ（ｚ＋∥砌ｗ‘＝。，尹∈（０，１）．结合以上式子得，当ｋ充分大时：

ｒ奢警叫警∽讽驰ｙｎ露

由Ｕ‘，Ｖ＋的性质，上式右边第一个式子为０，则可得一窆ｉ＝ｌ窆Ｊ＝ｌ取学∽徊

～窆ｔ＝ｌ兰ｊ＝ｌ啊学∽删

￡：（ｘ＋，Ｕ－，Ｖ‘；ｄ）≤０．＋牛职ｘ・＋ｆｋｔｋｄｋ；ｄｋ）＋华（们ｒＶ２ｈ（ｘ‘∥心Ｗｔ华ｇ（ｘ・＋孝ｋｔｋｄｋ；ｄｋ）一华（内ｒＶ２ｈ（ｘ‘∥心ｗｔ令ｋ－９＇ｏｏ，则（１．４）

第一章最优性条件

当ｆ。一ｏ，纯（，‘）≥０，贝，ｌｊ☆ｌｉ．ｍ。ｉｎｆ僦（Ｏ）≥ｏ．ＮＮｙ‘一ｙ＋所以有，

…ｌｉｍ（ｐ；（ｏ）＝新警∽蛐

因为ｈ（ｘ‘＋，‘ｄ‘）＝０，（１．５）Ｙ‘专Ｙ’得

ｄ．ｒＶ慨耐）７’ｄ＋（１ｚｋ）２２ｈ（ｘ‘∥灯）ｄ‘＝。，所以Ｖｘｈ（ｘ‘）７‘ｄ＋＝。．

此外，已知ｘ＋是ＫＫＴ点，贝ＩＪ

棚）＝和挚Ｍ叱ｍ＋）ｒｄｋ＿Ｖｘｈ（ｘ＊）７以

所以，我们有ｊｉｍ科（０）≤０，

片—，ｖｏ

结合（１．５）式有

由引理１．３，剿㈣＝势挚×一ｏ．

ｂ．州窆ｊ＝ｌｃ驰ｖ．．ｊ∥ｍｃ喜挚×＝窆ｊ＝ｌ驴ｃ挚×一ｏ．

业％由引理１．６得因为Ｕ‘≥０，则再由引理１．３得，警终，狐桦群铷从而有，矿１／２喜型墓≯１胆巧≥０．因为此矩阵是对称半正定矩阵，且因此有桫胆喜掣∽叫（喜（掣阶。，

耖啦挚即巧一ｏ．，：ｌＣⅨ，

Ｑ的列构成Ｈ（ｘ’）零空间的一组基，且Ｕ’和Ｕ讹ｌ／的生成空间相同，因此ａ的

１２

青岛人学硕十学位论文

列的生成空问与ｕ．１／２的列的生成空间相同。因此窆蜴’型癸；运彳：ｏ，由（１．４）ｌ＝ｌｕ‘’

式可知与题设矛盾，则ｘ’是问题（２）的严格局部极小点。

本章讨论了一类含有有等式约束和不等式约束的非光滑半定规化问题．把现存的结果扩展到约束是结构稀疏矩阵的情况，证明了一类含等式约束的非光滑半划问题的一阶必要性条件和二阶的充分性和必要性条件。１３

第二二章一个１卜线性Ｌａｇｒａｎｇｅ乘子法

第二章一个非线性Ｌａｇｒａｎｇｅ乘子法

２．１非凸半定规划问题

本章讨论一般非凸半定规划问题

（ＮＣＳＤＰ）ｍｉｎ厂（ｘ）

ｓ．ｔ日（ｘ）≥０且向（ｘ）＝０（３）

Ｒ，，其中ｆ：Ｒ”ＨＲ，Ｈ：Ｒ”Ｉ－－－）ｓ７（ｓ７是由ｍｘｍ的半定矩阵组成的空间），ｈ：Ｒ”Ｈ

且它们是二次可微的，这罩不要求ｆ（ｘ）是凸函数。

本章将求解非线性规划问题的非线性Ｌａｇｒａｎｇｅ方法推广到解决非凸半定规划中去，给出一个非线性Ｌａｇｒａｎｇｅ函数来求解非凸半定规划。

设非凸半定规划问题（３）的Ｌａｇｒａｎｇｅ函数为

Ｌ（ｘ，Ｕ，矿）＝ｆ（ｘ）－＜Ｕ，Ｈ（ｘ）＞＋＜Ｖ，办（ｘ）＞，

（ｘ‘，矿，ｙ‘）为问题（３）的ＫＫＴ点，即满足

掣圳・（掣）巾烈ｘ‘））７一Ｖ，㈦，…，咒ＣⅨｊＣⅨ，

Ｕ＋Ｈ（ｘ’）＝０，Ｕ‘≥０．

在下面的讨论中要用到下列假设条件１２０ｌ

（ａ）严格互补条件成立：即ｒａｎｋ（Ｈ（ｘ＋））＝，．，ｒａｎｋ（Ｕ’）＝ｍ—ｒ．

（ｂ）二阶充分条件成立：

对删础附．）＿悱驯喜ｚＥｒ警Ｅ＝咀（Ｖ崩ｘ．））饥０），

有下面不等式成立

ａ７’Ｖ２Ｌ（ｘ＂，Ｕ‘，Ｖ‘）ｄ＋ｄ７’Ｊ（ｘ’，Ｕ’）ｄ＞０．

其中Ｅ∈Ｒ”‘””，其ｍ一，．个列向量构成Ｈ（ｘ‘）零空问的一组标准正交基，

Ｊ（ｘ，Ｕ）＝（Ｊｏ）＝２（ａｎ（ｘ）／Ｏｘ）７’（Ｕｏ【日（ｘ）】一）（ａＨ（ｘ）／Ｏｘ），

厶：２ｕ・掣【日（ｊｃ）】－－＿ＯＨ（ｘ），屯ｊｆ：１，…，玎．。

ＯＸ，０％：（ｃ）ｎ（ｘ‘）在ｘ＋处是Ｌｉｐｓｃｈｉｔｚ的，即存在占＞０及盯＞０，对于任意

青岛人学硕十学位论文

ｚ∈Ｂ（ｘ’，占）＝｛＝Ｉｌｌｘ—ｚ’８＜占，ｘ∈Ｒ”），都有１］Ｈ（ｘ）－Ｈ（ｘ’）８ｓ盯忙一ｘ‘ｌ，若ｒａｎｋ（Ｈ（ｘ’））＝，．，当占充分小时，对任意ｘ∈Ｂ（ｘ＋，￡），有ｒａｎｋ（Ｈ（ｘ））＝，且Ｈ（ｘ）≥０．２．２非线性Ｌａｇｒａｎｇｅ函数及其性质

对于非凸半定规划（３），我们给出了一个非线性Ｌａｇｒａｎｇｅ函数

Ｆ（ｘ，ｕ，ｙ，ｆ）＝厂（ｘ）＋寻驴（ｕ（Ｊ『一Ｐ一一洲“’））＋＜ｙ，办（ｘ）＞＋吾。厅（ｘ）１１２，ｆ＞ｏ．

下面讨论Ｆ（ｘ，Ｕ，Ｖ，，）的一些性质。

引理２．１１３０ｌ设（ｘ’，Ｕ＋，Ｖ’）为问题（３）的ＫＫＴ点，则存在ｍｘｍ标准讵交阵Ｑ＝ｃＥＦ，，满足日ｃｘ‘，＝Ｑ（三三）ＱＴ且ｕ‘＝Ｑ（言３）９７’，

其中Ａ＝ｄｉａｇ（ａ，）∈Ｒｒ，ｒ，ｑ＞０，ｉ＝ｌ，…，厂；Ｂ＝ｄｉａｇ（Ｏｊ）∈Ｒｔｎｉｒｔｍ－ｆ，ｂｊ＞０，／＝１，…，ｍ－ｒ．由Ｑ一＝Ｑ７１得ＥＥ７’＋阿７‘＝厶，且日（ｘ＋）＝ＦＡＦ７’，Ｕ‘＝ＥＢＥ７’．

引埋２．２１７１令Ｄ∈Ｒ＂，是对称矩阵，Ｗ∈Ｒ切，Ｔ＝ｄｉａｇ（ｔ，）∈Ｒ“，其中‘＞０，ｉ＝１…．，Ｚ，若由Ｗｙ＝０可得Ｙ７’Ｄｙ≥０，则存在岛＞０，使得对于即＞‰，Ｄ＋ｐＷ７’研是Ｊ下定矩阵。

定理２．１设Ｍ（ｘ，Ｕ，Ｖ，ｆ）＝Ｕｅ一删硼７圩‘。’（，＋，２日（ｘ）２）～，Ｎ（ｘ，Ｕ，Ｖ，ｆ）＝Ｖ＋ｔｈ（ｘ），若（ｘ‘，Ｕ‘，Ｖ＋）为问题（３）的ＫＫＴ点，则有

Ｍ（ｘ＋，Ｕ’，ｙ＋，ｔ）＝Ｕ‘

证明Ⅳ（ｘ。，Ｕ’，矿‘，，）＝Ｖ’Ｖｔ＞０．由引理２．１可得

Ｍ（ｘ’，Ｕ‘，ｙ’，ｆ）＝Ｕ—ｅ棚胛∽（，＋ｆ２Ｈ（ｘ’）２）一１

《Ｂ

钮ＩｏＱ丁Ｑ（名７罟］Ｑ７’ｃＱ（名７兰）Ｑ７１，。１

《Ｂ

钮Ｌｏ旧驮≮７跏ｒ圳

１５这罩召＝ｄｉａｇ（ｅ一棚嘲‘，’）∈Ｓ７，０＝ｄｉａｇ（１＋ｔ２Ｅ（ｘ＋）２）∈Ｓ７，Ｆｈ亍：ｈ（ｘ‘）＝０，从而有Ⅳ（ｘ＋，Ｕ’，矿，，）＝Ｖ＋＋ｔｈ（ｘ’）＝矿．

第二章一个１ｒ线性Ｌａｇｒａｎｇｅ乘子法

定理２．２若（ｘ＋，Ｕ‘，Ｖ’）为问题（３）的ＫＫＴ点，则

Ｆ（ｘ’，Ｕ＋，ｙ‘，，）＝￡（ｘ＋，Ｕ’，Ｖ＋）＝ｆ（ｘ’）．

证明瞰‘，旷吒，）＿ｍ．）＋÷删。巧～ｗⅣ）））＋＜旷№．）＞＋扣ｘ．）Ｊ１２冈为Ｕ’Ｈ（ｘ‘）＝０，所以Ｕ‘（，一ｅ一删卸州。’’）＝０，再由ｈ（ｘ。）＝０可知

，（ｘ‘，Ｕ＋，ｙ‘，，）＝￡（工＋，Ｕ’，Ｖ’）＝／（ｘ’）．

定理２．３若（ｚ‘，Ｕ‘，Ｖ’）为问题（３）的ＫＫＴ点，，则

Ｖ，Ｆ（ｘ＋，Ｕ＋，矿‘，ｆ）＝０，Ｖｔ＞０．

证明Ｖ。Ｆ（ｘ，Ｕ，Ｖ，ｔ）

＝Ｖｘｆ（Ｘ）一÷肛（Ｖ，（Ｕｅ一咖脚“’））＋ｆ（Ｖ，办（ｘ））７’办（ｘ）＋（Ｖ，办（ｘ））７’Ｖ

＝Ｖ，ｆ（ｘ）－（ＯＨ（ｘ）／Ｏｘ）７’ｖｅｃ（Ｍ（ｘ，Ｕ，Ｖ，，））＋（Ｖ，办（ｘ））７１Ｎ（ｘ，Ｕ，Ｖ，ｆ）

由Ｌ（ｘ，Ｕ，ｙ）的定义得，Ｖ，Ｌ（ｘ，Ｕ，ｙ）＝Ｖ。厂（ｘ）一（汨（ｘ）／锄）７’ｖｅｃ（Ｕ）＋（Ｖ，乃（ｘ））ｒＶ．因此，Ｖ，Ｆ（ｘ＋，Ｕ’，Ｖｉｉ９ｆ）

＝Ｖ，ｆ（ｘ＋）－（ＯＨ（ｘ＋）／Ｏｘ）７’ｖｅｃ（Ｍ（ｘ＊，【，’，矿。，，））＋（Ｖ。ｈ（ｘ’））７’Ⅳ＠’，Ｕ。，ｙ＋，，）＝Ｖ，ｆ（ｘ’）－（ＯＨ（ｘ’）／Ｏｘ）７’ｖｅｃ（Ｕ’）＋（Ｖ，ｈ（ｘ‘））７’Ｖ’

＝Ｖ，三（．）ｒ＋，Ｕ＋，Ｖ’）＝０．

定理２．４如果条件（ａ）一（ｃ）成立，则存在，ｏ＞０，当ｆ＞＞－ｔｏ时，Ｖ２Ｆ（ｘ＂，Ｕ’，旷，ｆ）是严格正定的。

证明０２Ｆ（ｘ，Ｕ，Ｖ，ｆ）／融叙，

：职小Ｍ（删∥咖（掣）＋，ｆｒ（掣脚ｎ％）掣）锻ｉＯＸｉ０％Ｏ＇ｘｊ

＋（Ｖ，（Ｖ，忽（ｘ）））ｒＮ（ｘ，Ｕ，Ｖ，ｆ）＋ｆ（Ｖ，红（ｘ）），Ｖ。办，（ｘ），ｆ，Ｊ＝ｌ，…，胛．

贝０Ｖ：Ｆ（ｘ，Ｕ，Ｖ，ｆ）＝Ｖ２ｘｆ（ｘ）一（厶ｏ（ｖｅｃＭ（ｘ，Ｕ，Ｖ，ｆ））ｒ）Ｖ，ｖｅｃ（ＯＨ（ｘ）／Ｏｘ）

＋（厶＠Ｎ（ｘ，Ｕ，Ｖ，ｆ）７’）Ｖ，ｖｅｃ（Ｖ，办（ｘ））＋ｆ（Ｖ，办（ｘ））７’Ｖ，办（ｘ）

＋ｔ（ＯＨ（ｘ）／Ｏｘ），（（Ｍ（ｘ，Ｕ，Ｖ，ｆ）（，＋，２何（ｘ）２）一。（，＋２日（石））７’ｏＬ）（ａ日（ｘ）／ａ力由Ｌ（ｘ，Ｕ，ｙ）的定义得１６

青岛人学硕一卜学位论文

Ｖ：Ｌ（ｘ，Ｕ，ｙ）＝Ｖ：／（ｘ）一（厶圆（ｖｅｃＵ）７）Ｖ，ｖｅｃ（ａＨ（ｘ）／Ｏｘ）＋（Ｉ．圆Ｖｒ）Ｖ，ｖｅｃ（Ｖ，办（ｘ））贝｜ＪＶ，２，Ｌｘ，Ｕ’，ｙ‘，ｆ）＝Ｖ，２厂（ｘ’）一（Ｌ圆（ｖＰｃＭ（ｘ’，Ｕ‘，ｙ’，ｆ））７）Ｖ，ｖｅｃ（ＯＨ（ｘ’）／Ｏｘ）＋（厶ｏⅣ（ｘ＋，ｕ＋，ｙ’，ｆ）７）Ｖ，ｖｅｃ（Ｖ，ｈ（ｘ’））＋，（Ｖ，ｈ（ｘ＋））７Ｖ，ｈ（ｘ‘）

＋ｔ（ＯＨ（ｘ’）／Ｏｘ）７’（（Ｍ（ｘ’，Ｕ‘，ｙ＋，，）（，＋，２Ｈ（ｘ’）２）－’（，＋２Ｈ（ｘ’））ｐＬ）（ａＨ（ｘ‘）ｌａｘ）

＝Ｖ２Ｌ（ｘ＂，Ｕ‘，Ｖ‘）＋ｆ（ａ阿（ｘ’）／Ｏｘ）ｒ（（Ｕ＋（，＋，２Ｈ（ｘ‘）２）一１（，＋２Ｈ（ｘ’）））７’ｏＬ）（ａＨ（ｘ＋）／ａｘ）＋，（Ｖ。ｈ（ｘ＋））７’Ｖ，ｈ（ｘ’）

＝Ｖ，２从ｘ，Ｕ‘，Ｖ‘）＋，（御（ｘ’）／Ｏｘ）７’（ＥＢＥ７、ｏ厶）（御（ｘ＋）／ａｘ）

＋ｔ（ＯＨ（ｘ＋）／Ｏｘ）７’（（，＋ｆ２Ｈ（ｘ’）２）一（１＋２Ｈ（ｘ’”圆Ｌ）（柳（ｘ‘）／Ｏｘ）＋ｔ（ｖ，ｈ（ｘ’））７１Ｖ，ｈ（ｘ‘）＝Ｖ２Ｌ（ｘ＂，Ｕ’，Ｖ＋）＋，（阳（ｘ’）／Ｏｘ）７’（ＥＢＥｒｏ（皿７’＋肝７’））（拊（ｘ’）／Ｏｘ）

＋ｔ（ＯＨ（ｘ‘）／Ｏｘ）７’（（，＋，２Ｈ（ｘ’）２）‘１（Ｉ＋２Ｈ（ｘ’））＠乇）（胡（石＋）／Ｏｘ）＋ｔ（ｖ，ｈ（ｘ‘））７１Ｖ，ｈ（ｘ’）＝Ｖ：三（ｘ’，ｕ＋，Ｖ’）＋ｆ（ａ日（ｘ‘）／ａｘ）７’（ＥＢＥｒｏ髓７’）（ａ日（ｘ＋）／ａｘ）

＋ｔ（ＯＨ（ｘ‘）／Ｏｘ）ｒ（ＥＢＥｒ＠ＦＦ，）（阴（ｘ’）／反）

＋ｔ（ＯＨ（ｘ‘）／Ｏｘ）ｒ（（，＋ｆ２Ｈ（ｘ＋）２）一（１＋２Ｈ（ｘ’））圆Ｌ）（拊（ｘ‘）／ａｘ）＋，（Ｖ，ｈ（ｘ＋））７’Ｖ，ｈ（ｘ’）＝Ｖ：￡（ｘ‘，ｕ＋，Ｖ‘）＋ｆ（汨（ｘ＋）／ａｘ）７’（ＥｏＥ）（曰＠Ｌ一，）（Ｅ７圆Ｅ７１）（ａＨ（工＋）／Ｏｘ）

＋（ａ日（ｘ‘）／Ｏｘ）７’（Ｕ’＠（ｔＦＦ７’一２ＦＡ一１Ｆ７’））（ａＨ（ｘ‘）／觑）＋Ｊ（ｚ‘，Ｕ＋）

＋ｔ（ＯＨ（ｘ‘）／舐）７’（（，＋，２Ｈ（ｘ’）２）叫（Ｉ＋２Ｈ（ｘ’））ｏＬ）（谢（ｘ’）／ａｘ）“（Ｖ，ｈ（ｘ‘））７１Ｖ，ｈ（ｘ’）由于Ｈ（ｘ＋）≥０，（Ｖ，ｈ（ｘ‘））７’Ｖ，ｈ（ｘ＋）≥０，且ｆ＞０所以

ｔ（ＯＨ（ｘ‘）／Ｏｘ）７１（（，＋ｆ２Ｈ（ｘ＋）２）。１（Ｉ＋２Ｈ（ｘ。））ｏＬ）（掰（ｚ＋）／Ｏｘ）

＋，（Ｖ。ｈ（ｘ‘））７’Ｖ，ｈ（ｘ＋）≥０

由引理２．１得，Ｊ（＿）ｆ‘，Ｕ‘）＝２（ＯＨ（ｘ‘）／ａｘ）７’（Ｕ‘０ＦＡ。１Ｆ７’）（阳（ｚ’）／０ｘ）．

因此ｊｆ’＞０，当ｔ＞ｔ’时有，

ＶＺＦ（ｘ＂，ｕ’，ｙ＋，ｆ）＞－Ｖ：三（ｘ’，ｕ’，Ｖ’）＋，（ｘ‘，Ｕ‘）

＋ｔ（ＯＨ（ｘ‘）／Ｏｘ）ｒ（ＥＱＥ）（Ｂ圆Ｌ一，）（Ｅ７’圆Ｅ７’）（ａ日（ｘ＋）／ａｘ）

由引理２．２知存在ｔｏ＞九当ｔ＞ｆｏ时，Ｖ２ｘＦ（Ｘ＂，Ｕ‘，ｙ’，，）是严格正定的。

２．３基于非线性Ｌａｇｒａｎｇｅ函数的乘子法及其收敛性

基于第２．２节给出的非线性Ｌａｇｒａｎｇｅ函数

第二二章一个１卜线性Ｌａｇｒａｎｇｅ乘子法

，（ｘ，ｕ，ｙ，，）：／（ｘ）＋ｌｔｒ（Ｕ（１＿＿ｅ－”ｃｌａｎ，／４（ｘ）））＋＜矿，向（ｘ）＞＋委ｌＩ向（ｘ）０２”

ｔＺ”

可以得到如下求解半定规划问题（３）的乘子法。

算法

第１步．给定占＞０，ｔｏ＞０，Ｕｏ∈贮，Ｖｏ∈Ｒ，，ｋ：＝０．

第２步・求ｘｋ２ａｒｇｍ，。∥ｉｎＦ（ｘ，“，Ｋ，气）・

第３步．若０以Ⅳ（坼）０≤ｓ，ｅｉｇ（Ｈ（ｘｋ））≥一ｓ，肛（碗）ｌＩ≤ｓ则停止，ｘｋ是问题（３）的一个局部极小点；否则，转第４步。

第４步．更新Ｌａｇｒａｎｇｅ乘子

％＋ｌ＝以Ｐ一枷’ＩⅣ‘以’（，＋气２Ｈ（ｘｋ）２）～，圪＋ｌ＝圪＋气办（坼），ｔｋ＋ｌ＝１０ｔｋ．

第５步．后：＝ｋ＋ｌ，返第２步。

下面研究算法的收敛性。在证明收敛性定理之前，先给出引理。

引理２．３（Ｂｅｒｔｓｅｋａｓ第二隐函数定理）［７１：设Ｓ是尺卅”的一个开子集，ｊ是Ｒ”的一个紧致子集，ｇ：Ｓ—Ｒ”是Ｓ上的Ｐ次连续函数，Ｐ≥０．假设Ｖ。ｇ（ｘ，Ｙ）存在且在Ｓ上连续，歹满足（ｉ，力∈Ｓ，ｇ（ｉ，歹）＝０，且对所有的ｉ∈ｊ，Ｖ，ｇ（ｉ，歹）是非奇异的，那么存在占＞Ｏ，万＞０，和函数矽：Ｓ（ｉ；ｓ）寸ｓ（ｙ，万）使得矽在Ｓ（２；ｓ）上Ｐ次连续，且对所有舅∈ｊ，歹＝矽（ｉ），对所有ｘ∈Ｓ（牙；ｓ），ｇ（ｘ，痧（ｘ））＝０。如果ｘ∈Ｓ（ｉ；ｇ），Ｙ∈（夕，万）且ｇ（ｘ，Ｙ）＝０，那么Ｙ＝矽（ｘ）是唯一的。而且如果Ｐ≥ｌ，那么对于所有ｘ∈Ｓ（２；ｔｒ），有Ｖ矽（ｘ）＝一Ｖ，ｇ（ｘ，矽（ｘ））【Ｖ。ｇ（ｘ，≯（ｘ）】～．

定理２．５设（ｘ＋，ｕ‘，ｙ’）为问题（３）的ＫＫＴ点，且假设条件（ａ），（ｂ）和（Ｃ）成立，则存在ｓ＞０，万＞０，仃＞０，ｔｏ＞Ｏ使得对于Ｖｔ＞ｔｏ，

ＶＵ∈Ｂ（ｕ’，万）＝｛ｕＩＩＩｕ－ｕ‘８＜万，ｕ∈ｓ”），

ＶＶ∈曰（ｙ‘，仃）＝｛ｖＩＩＩｖ—Ｖ’０＜仃，Ｖ∈Ｒｐ），下列结论成立：

青岛人学硕十学位论文

（１）存在向量羹＝圣（ｕ，Ｖ，，）＝ａｒｇｍｉｎ｛Ｆ（ｘ，Ｕ，Ｖ，ｆ）ｌｘ∈Ｂ（ｘ＋，ｓ））

使得Ｖ，（叠，Ｕ，Ｖ，ｆ）＝０；

（２）对于（１）中的曼以及矩阵肪＝Ｍ（曼，Ｕ，Ｖ，，），力＝Ｊ７Ｖ（量，Ｕ，Ｖ，ｆ），有估计式

ｍａｘ｛卜ｘ．｜Ｊ，ｌｌ肪一Ｕ．ＪＩ’Ｉ卜ｙ’蚣叫阻矿）一（ｕ‘，旷）｜Ｉ，

其中ｃ＞０于，无关。

证明ｔ殳函数Ｑ：Ｒｎ×Ｒｍ一，，ｍ一，×尼ｐ×Ｒｍ，ｍ×尼ｐ×Ｒ＋—》Ｒｎ＋（ｍ一，）２＋ｐ

、咿（ｚ）＋（￡滴（ｚ）／￡玟）７‘ｖｅｆ（月）一（阴（石）／￡次）７’ｖｅｃ（＾夕（ｚ，Ｕ，Ｖ，，））

一（ａ厅（ｘ）／Ｏｘ）ｒｖｅｃ（厨ｌ（ｘ，Ｕ，ｙ，ｆ））＋（Ｖ向（ｘ”７’丁

Ｑ（ｘ，Ｒ，Ｔ，Ｕ，Ｖ，ｆ）＝

ｖｅｃ（Ｒ）一ｖｅｃ（Ｍ（ｘ，Ｕ，Ｖ，，））

三丁一！Ⅳ（ｘ，ｕ，Ｍｔｔ

其中露（ｘ，Ｕ，Ｖ，，）＝ＥｒＭ（ｘ，Ｕ，Ｖ，ｔ）Ｅ，霄（ｘ）＝ＥｒＨ（ｘ）Ｅ．

则Ｑ（ｘ＋，Ｂ，ｙ＋，Ｕ＋，ｙ＋，，）＝０，其中Ｂ如前面定义。

令Ｑ，，Ｑ２，Ｑ３分别表示Ｑ的第一行，第二行和第三行。

则Ｖ，Ｑ。（ｘ，Ｕ，Ｖ，，）

＝Ｖ：厂（ｘ）＋（厶＠（ｗｃ（尺））７１）Ｖ，ｖｅｃ（ＯＨ（ｘ）／Ｏｘ）一（ＯＨ（ｘ）／Ｏｘ）７１Ｖ，ｖｅｃ（Ｍ（ｘ，Ｕ，Ｖ，ｆ））一（厶圆（ｖｅｃＭ（ｘ，Ｕ，Ｖ，，））７’）Ｖ，ｖｅｃ（ＯＨ（ｘ）／Ｏｘ）一（ＯＢ（ｘ）／Ｏｘ）７’Ｖ，ｖｅｃ（Ｍ（ｘ，Ｕ，Ｖ，ｆ））一（厶ｏ（ｖｅｃ－Ｑ（ｘ，Ｕ，矿，ｆ））７’）Ｖ，ｖｅｃ（ＯＨ（ｘ）／Ｏｘ）＋（Ｉ．ｏｒ，）Ｖ，ｖｅｃ（Ｖ，厅（ｘ）），

Ｖ。（Ｒ）Ｑｌ（ｘ，Ｕ，Ｖ，ｆ）＝（ａ日（ｘ）／苏）７，Ｖ７＇Ｑ１（ｘ，Ｕ，Ｖ，ｔ）＝（Ｖ，办（ｘ））ｒ，ＶｘＱ２（ｘ，Ｕ，Ｖ，ｆ）一Ｖｘｖｅｃ（Ｍ（ｘ，Ｕ，ｙ，咖

Ｖ７’Ｑ２（ｘ，Ｕ，Ｖ，ｆ）＝Ｏ，Ｖ，Ｑ３（ｘ，Ｕ，Ｖ，，）＝一（Ｖ芹办（ｘ”ｒ，Ｖ州）Ｑ２（ｘ，Ｕ，Ｖ，ｆ）＝‘…）ｚ，Ｖ雠（尺）Ｑ３（ｘ，Ｕ，Ｖ，，）＝０，ＶｒＱ３（ｘ，ｕ，Ｍ＝１ｆＩ，．

因此，当ｆ＞０时，可得

第二章一个１卜线性Ｌａｇｒａｎｇｅ乘子法

Ｖ舭（ｎ７’Ｑ（ｘ，月，丁，ｕ，ｙ，，）ｌⅣ∥咖．’，）＝

。，二≯＠’’■；ｔ矗）－ｔ（Ｖ（ａｔＴ（ｘ）／Ｏｘ）ｖｅｃ（Ｍ坝（ｘｘ。＇，≯黑（鳓㈣７１限№．））７’＋

一Ｕ‘，ｙ’，，））、～７¨～’

一Ｖ，ｗｃ（露（ｘ’，Ｕ‘，ｙ’，，））‘…，ｚＯ

一Ｖ，ｈ（ｘ‘）０≮Ｉｐ

假设（口，∥，ｙ）∈Ｒ”×Ｒ‘ｍ一，’２×Ｒ，，使得（Ｖ，，眦（月），７．ｆ２（ｘ，Ｒ，Ｔ，Ｕ，ｙ，ｆ））（口，∥，７）７１＝０，即｛Ｖ；Ｆ（ｘ‘，ｕ’，ｙ‘，ｆ）一ｔ（Ｖ，办（ｘ’））７１Ｖ，办ｏ‘）一（捐（ｘ‘）／氖）ｒＶ，ｖｅｃ（厨（ｚ‘，ｕ‘，Ｖ‘，，）））口

＋ｆ折（ｘ‘）ｌＯｘ）７∥＋（Ｖ，ｈ（ｘ‘））７’７＝０，

・咧厨（ｘ‘，ｕ‘，矿力）口＋ｋ）：∥＝ｏ，吧ｍ’）口＋詈‘ｙ－ｏ．

从而得到Ｖ，２¨ｘ，Ｕ＋，ｙ＋，ｔ）ａ＝０．由定理２．５可知存在ｔｏ＞０，当ｆ≥，ｏ时，Ｖ：，（ｘ’，ｕ‘，ｙ＋，，）＞０，所以口＝０，于是（口，∥，ｙ）＝０．因此当ｆ－－－ｔｏ时

Ｖ，．眦（Ｒ”Ｑ（ｘ。，Ｂ，ｙ‘，Ｕ’，矿‘，，）是非奇异的。

令‘＞气，ｆｌ是足够大的数，由第二隐函数定理，存在正数占，万，盯，和定义在ｓ＝｛（ｕ，矿，，）ＩＩ｜ｕ—Ｕ＋８＜万，陟一矿’Ｉｌ＜盯，岛≤ｆｓ‘）上的唯一连续可微函数量（ｕ，ｙ，ｔ）ｆＨｄＲ（Ｕ，Ｖ，ｆ），Ｔ（Ｕ，Ｖ，ｆ）使得对所有的（Ｕ，Ｖ，，）∈Ｓ满足

ｍａ）（｛Ｉｌ圣（ｕ，矿，ｔ）－ｘ‘０，ＩＩＲ（Ｕ，ｙ，ｆ）一ＢｌＩ，｜Ｉ丁（ｕ，ｙ，ｔ）－Ｖ‘ｌＩ）≤占，

而且Ｑ（ｊ（Ｕ，Ｖ，ｆ），Ｒ（Ｕ，Ｖ，ｆ），Ｔ（Ｕ，Ｖ，ｆ），Ｕ，ｙ，ｆ）＝０，

由Ｑ的定义可知，对于ｖ（ｕ，Ｖ，，）∈Ｓ，有Ｖ，Ｆ（圣，Ｕ，Ｖ，，）＝Ｏ其中曼＝曼（Ｕ，Ｖ，ｆ）．

ＩＮＮＮｔ≥ｔｏ时，Ｖ：Ｆ（ｘ＋，Ｕ＊９Ｖ＊９，）是正定的，则由Ｂａｎａｃｈ扰动定理‘７１，存在正数占，万，仃对任意ｘ∈Ｂ（ｘ＋，占）＝｛ｘ∈Ｒ”，１１ｘ—ｘ．ＩＩ＜ｓ），

青岛人学硕十学位论文

ＵｅＢ（ｕ＋，万）＝｛ｕ∈Ｓ”ｔｌｌＵ—Ｕ＋０＜万）以及ｙ∈Ｂ（ｙ’，０９＝｛ｖ∈ＲＰ）１１ｖ—ｙ’ｌｌ＜ｏ－｝，Ｖ，２Ｆ（ｘ，Ｕ，Ｖ，ｆ）是正定的。选择充分小的Ｊ下数ｓ，艿，盯，使得曼∈Ｂ（ｘ＋，￡），则量是Ｆ（ｘ，Ｕ，Ｖ，，）在Ｓ（ｘ’，占）上的唯一局部极小点，结论（１）得证。

下面证明（２）：

令ＩＱ＝Ｍ（孟ｃ，Ｕ，Ｖ，，），力＝Ⅳ（叠，Ｕ，Ｖ，ｆ）．由Ｖ，Ｆ（圣，Ｕ，Ｖ，ｆ）：０及Ｍ（圣，Ｕ，Ｖ，，）和Ⅳ（曼，Ｕ，Ｖ，ｆ）的定义可得：

Ｖ，ｆ（Ｙｃ（Ｕ，Ｖ，，））一（ａ日（量（ｕ，Ｖ，ｆ））／苏）厂ｗｃ衍＋（Ｖ，办（曼））７’前

ｚ（ｕ，Ｖ，ｆ）＝！衍一！Ｕｅ一删锄删（ｊ’（，＋ｆ：Ｈ（圣）ｚ）一－’。＝０．

ｔｔ

昙力一Ｉ．ｖ一办（曼（ｕ，ｙ，ｆ））ｌｔ

分别对Ｚ（Ｕ，Ｖ，ｔ）的各行关于ｘ，ｖｅｃ（Ｕ），Ｖ求导得

Ｘ

Ｖｊ，。（厨汹Ｚ（Ｕ，Ｖ，ｔ）ｖ聊（ｕ沙ｖｅｃ（Ｍ）＋Ｖ。（￡，沙ｚ（ｕ，Ｖ，ｆ）＝０．

Ｎ

即ｅ（ｕ，Ｖ，ｔ）ｗ（Ｕ，Ｖ，，）７１＋缈（Ｕ，Ｖ，，）＝０．

００

其中缈（【，，Ｖ，ｔ）＝一詈Ｖ州，Ｍ（ｘ，ｕ，％）Ｉ扁ｏ

Ｏ

Ｖｖｅｃ（Ｕ）舅（Ｕ，Ｖ，，）Ｖ矿戈（Ｕ，Ｖ，，）

ｗ（Ｕ，Ｖ，ｆ）＝Ｖｍ（ｕ）ｖｅｃＭ

～。ｃ∞、ＮＶ矿ｖｅｃＭ～ｙＮ

沙（Ｕ，Ｖ，ｆ）

第二章一个非线性Ｌａｇｒａｎｇｅ乘子法

Ｖ：三（圣（ｕ，Ｖ，，），力，力）一（ａ日（圣（ｕ，Ｖ，，））／ａ譬）７（Ｖ，ｈ（Ｄ（Ｕ，Ｖ，，）））７１

。（尬。州拊（戈（叫，，））／反）７’

一Ｖ，悄ｕ，㈨）

量（Ｕ，Ｖ，ｆ）一ｘ。

由于詈Ｌ：０ｌ。ｉｐ化ｃ（力一Ｕ’）

力一矿‘叠（Ｕ，Ｖ，，）一叠（ｕ＋，ｙ‘，，）ｆ１＝Ｉｖｅｃ｛Ｍ（Ｊ（Ｕ，Ｖ，ｒ），Ｕ，Ｖ，，）一Ｍ（叠（ｕ‘，矿’，，），Ⅳ‘，Ｖ＊９，））Ｉ【Ⅳ（曼（ｕ，Ｖ，ｆ），Ｕ，Ｖ，，）一Ⅳ（曼（ｕ‘，ｙ‘，，），ｕ‘，ｙ‘，，）Ｊ

＝ｆｗｃｕ‘＋ｐｃｕ—ｕ‘，，ｙ‘＋ｐｃｙ—ｙ‘，，，，Ｕ－Ｕ＊）ｄｐ

＝一ｆ矽ｃｕ’＋Ｊｃｕ—ｕ。，，矿’＋Ｊｃ矿一ｙ＋，，，，一缈ｃｕ’＋ｐｃｕ—ｕ＋，，矿‘＋ｐｃｙ—ｙ‘，，，，Ｕ－Ｕ＊］ｄｐ根据≯（Ｕ，Ｖ，ｆ）的定义，可以证明：当ｔ＞ｔｏ时，≯（Ｕ‘，矿，，）是非奇异的。根据Ｂａｎａｃｈ扰动定理‘７１，Ｖｔ≥ｔｏ和ＶＵ∈Ｂ（Ｕ’，万）以及Ｖ矿∈Ｂ（ｙ’，仃），矽（Ｕ，Ｖ，，）一１存在且存在Ⅳｌ＞ｏ，使得眵（ｕ，ｙ，，）一０≤Ｍ

一由假设条件（ｃ）知存在Ⅳ２＞ｏ，对所有（Ｕ，Ｖ，，）∈Ｂ（Ｕ＋，万）×Ｂ（矿，盯）×（气，‘），有

ｐ”锄胛‘ｊ’（，＋ｆ２日（曼）２）。’８≤Ⅳ２．又因为ｌｆＶ。（ｕ）ｖｅｃ（ｕ）０为一个常数，则存在Ⅳ３＞ｏ，使劁Ｖｖｅｃ（Ｕ）Ｍ（ｘ，Ｕ，ｙ，，）叫｜＜Ⅳ３．

令Ｕ（ｐ）＝Ｕ＋＋ｐ（Ｕ—Ｕ‘），矿（ｐ）：Ｖ＋＋ｐ（Ｖ—Ｖ‘），则由上面所述得：

柳嚣０

ｋ．Ｍ，一＝ｌｌ—ｆ矽ｃ【，ｃｐ，，矿ｃｐ，，，，。１妒ｃｕｃｐ，，ｙｃｐ，，，，（影二笋］ｄｐ０

≤Ⅳ－８ｆ妒ｃｕｃｐ，，ｙｃ户，，，，（孑二≯）ｄｐ０

青岛人学硕十学位论文

≤Ⅳ。４ｆ（。。１ＶｍⅢ）Ｍ。’：≥二乒；√）ＬＪ（ｕ—ｕ。］ｄｐ０

ｓⅣ１ｆ－１（吲Ｉｕ—Ｕ‘ｌ｜２＋ＩＩＶ—Ｖ’１１２）１７２（令ｃ＝ｍａｘ（Ｎ。Ｎ３，Ⅳ１））

≤“一１（６ｕ—Ｕ‘０２＋０ｙ—ｙ＋０２）¨２≤订。１ｌＩ（ｕ，矿）一（ｕ’，矿’）４，

Ｃ与ｆ的选取尢夭。

由以上定理可得当ｓ≥ｏ时，假设ｆ≥ｆ。，Ｕ∈Ｂ（Ｕ’，万）＝｛ｕＩＩＩｕ—Ｕ＋０＜万，Ｕ∈Ｓ”），ｙ∈召（ｙ＋，盯）＝｛ｖｌｌｌｖ—ｙ‘ｌｌ＜盯，ｙ∈尺ｐ），黾，玑，圪，ｆ。分别是算法产生的点列，当Ｊｊ｝专ｏ。ｔｋ－－＞ｏｏ，则有（黾，Ｕｋ，圪）一（ｘ＋，Ｕ＋，ｙ’），０％Ⅳ（Ｋ）０专ｐ＋－（ｘ＇）ｌｌ－－ｏ，ｅｉｇ（Ｈ（ｘ，））－－－＞Ｐ辔（日（ｘ＋））≥ｏ，忙（吒）０专肛（ｘ‘）０＝ｏ；ｓ＞ｏ且有限步终止则由算法知得到问题的近似最优解。当ｇ＝Ｏ且算法在有限步终止，则％为问题的最优解。２．４数值计算实例

考虑非凸半定规划问题

ｍｉｎ＃＋Ｚ＋２《＋《一５五一５％一２１ｘ３＋７ｘ４

而＋恐

０

ｓｄ．Ｏ０ＯＨ（ｘ）＝一２昀而０

而

０五００Ｘ２＋ｘ３≥ＯＯ０

ｆｘｔ＋霹＋＃＋《＋五一而＋而一黾一８１

办（ｘ）＝ｌ彳＋２ｘ２２＋《＋２《一而一确一９Ｉ＝０

【彳＋《＋《＋２＿一ｔ一昀一５Ｊ

此算例的精确解为（ｏ１２一１）ｒ．

第二二章一个非线性Ｌａｇｒａｎｇｅ乘子法

在本章的算法中取ｓ＝１０。６，‰＝／４，％＝（１

表２．１

而ＩＩ）ｒ得计算结果如下恐

１．１３７１２２４７８５２７１０屯毛ｔ＝】００．２１５２７２８８２４８０４０１．９５５２３３７９６９１３８６—０．９０７３６６７１７０６１６９

ｔ＝１０２—０．０１４９２３４１０８４３０４０．９８７２２４４５７４０３８９２．００２２８４６７３３７６４６

２．００９９８２０７８０７７１４—１．００７４５６５５６８７２０９—０．９８７６６０２１１５３１６９ｔ＝１０３—０．０１４７８５７４２５３７００

—０．０００１０６１５９３５４９４１．００１５９３３５７２２４５５ｔ＝１０４１．００００１７３８２７６９１７２．００００７２８０８０９１２２—０．９９９９０６０９２８５８６０

取ｓ＝１０巧，Ｕｏ＝／４，ｖｏ＝（ｏ０ｏ）７’得计算结果如下

表２．２

而恐恐兄

ｔ＝１００．０６５３１８７６７９０２８３１．０５４２９７１８７４０３００２．０２７７４１１５９９６２７４—０．９３９４２００７２３６５４２ｔ＝１０２０．０５８８３３２７２９４５８４

—０．０００５１１０６３７５００５０．９９１８６５６６４４９４５３１．９５８３４４５８３４０９７５—１．０４９９６４４８５３６０８４ｔ＝１０３

ｔ＝１０４０．９９９８６００１５３８８８４１．００００４０２９５７４３２６２．０００２８１１７１２９２９７２．０００３３９８１４５２６８０—０．９９９７８５２８８０４０９５—０．０００５１４０２４５２３６０—０．９９９５８９３ｌ３３３３３８通过计算得到问题的近似解，且计算结果是满意的，这体现了算法是可行和有效的。

第三章半定规划ｌ＇ｕＪ题的解析中心割甲面法

第三章半定规划问题的解析中心割平面法

３．１半定规划问题的转化

本章研究半定规划的解析中心割平面算法，此算法可以求解较大规模的半定规划问题。

考虑标准形式的半定规划问题

ｒａｉｎＣ・Ｘ

（４）ｓ．ｆ．丑Ⅳ＝ｂ

Ｘ≥０．

它的对偶问题为

ｍａｘｂｒｙ

（５）ｓ．ｆ．月ｒｙ＋Ｓ＝Ｃ

Ｓ≥０．

其中Ｓ”表示刀×即对称矩阵集合。霹表示疗ｘ刀半正定矩阵集合。Ｘ≥０表示ｘ∈＆，Ｃ・ｘ表示ｔｒ（ｃ７’ｘ）．月是Ｓ”一月。的线性映射，可以认为月是由ｋ个线性函数构成一的，约束魁＝６等价于七个线性约束月・ｘ＝６，，ｉ＝１，…，ｋ．月ｒｙ等价于∑：。只月．

由于凸约束Ｘ≥０等价于

秽ｘ，ａ＝Ｂ分・ｘ２０。＼６∈Ｂ。

其中召为｛∥：８∥０：≤１｝．

所以问题（４）和（５）可以转化为半无限线性规划

ｒａｉｎＣ・Ｘ

（６）ｓ７．月Ｘ＝ｂ

ｐＴＸｊ｜Ｂｊ之０，Ⅵｐ∈Ｂ

青岛人学硕＋学位论文

ｍａｘｂｒｙ

（７）ｓ．ｔ．月ｒｙ＋８＝Ｃ

９ｉｓｐ≥０，、ｐ∈Ｂ．

为了研究上述问题我们首先考虑下面的有限线性规划（ＬＤＲ）和（ＬＰＲ）．

给定有限集合｛屈，汪１，２，…ｍ），（ＬＤＲ）是下面问题

ｍａｘｂｒｙ

量

ｓ１．１二ｙｊ８７Ａｊｐｉｓｐ？Ｃｐｉ（ＬＤＲ）

Ｊ＝ｌ

，＝１，２，…，ｍ．

ｍｉｎＣ・（∑一屈屈７１）

ｆ＝ｌ

ｓ１．Ａ匹ｘｌｏｌ戳、）＝ｂ（ＬＰＲ）

，＝ｌ

‘≥０，ｆ＝１，２，…，朋，

在本章中需要以下假设［１２１：

假设１矩阵月，ｆ＿１，２…七在Ｓ”中线性无关。

假设２存在常数ａ＞０，使得栅，若满足胚＝ｂ，则有ｔｒ（Ｘ）＝口．

若半定规划的原始可行集有界则可以满足此假设。

引理３．１存在唯一的向量夕，满足月７’夕＝Ｉ．

证明由假设２知，由七个线性约束月ｅＸ＝匆，汪ｌ，２，…，七．可得ｔｒ（Ｘ）＝，ｏＸ＝ｇｌ，故必定存在向量夕＝（Ｙｌ，Ｙ２，…虬）７’，使得∑竺。只月＝，，即月ｒ夕＝，，由假设１知夕是唯一的。

任给问题（５）的可行解Ｙ，由于Ｖ２＞Ｏ，在Ｊ，一砂点其对偶松弛矩阵

Ｓ＝Ｃ一月７’（），一五夕）＝Ｃ一月ｒｙ＋２Ｉ＞０，因此点Ｙ一砂是问题（５）的严格可行解，所以假设２保证了问题（５）有严格可行解，从而保证在最优解处的强对偶性，对偶间隙等于零，问题（４）和（５）的最优值相等。

定理３．１［１２１令ｙ‘和Ｘ＋，分别是（ＬＤＲ）和（ＬＰＲ）的最优解，

第三章半定规划问题的解析中心割平面法

则（１）矩阵ｘ‘＝∑ｔ＋屈屈７’是问题（４）的可行解。

ｌ＝ｌ

（２）令Ｓ‘＝Ｃ一月丁Ｙ‘，我们有ｘ＋・Ｓ‘＝０而且如果Ｓ’≥０，则有Ｘ＋Ｓ‘＝０且Ｘ’是

问题（４）的最优解。

３．２解析中心割平面法及其收敛性

割平面算法的思想是对于歹∈Ｒ‘，或者有歹∈Ｙ，或者由它可生成分离超平面，

由此确定半空间

｛ｙ∈Ｒ‘ｌ屈ｒ（月ｒＹ）ｆｌ，≤屈ｒｃ屈，０屈０：＝１），ｉ＝ｌ，２，…，ｍ．

其中】，＝｛ｙ∈Ｒ‘Ｉｓ＝Ｃ一月ｒｙ≥０）＝｛ＹｅＲ２Ｉ九瓤（月７’ｙ－Ｃ）＜０）是问题（５）可行集，

它是凸集。其中届，屐…成是矩阵月丁罗一Ｃ正的特征值对应的特征向量。

以上朋个割平面中最有效的割平面确定秒∈Ｒ‘Ｉ∥７１（月ｒＹ）ｆｌ≤∥ｒｃ∥，忪０：＝１），

其中∥是丸戤（月７’ｙ－ｃ）对应的特征向量。

解析中心割平面算法是选择解析中心作为下一个迭代点，

令ｗ，＝｛ｙ∈Ｒ。ｌ∥ｃ屈一∥’（月丁Ｙ）ｆｌ，≥ｏ，０屈０：＝ｌ，，＝ｌ，２，…，－，），＿的解析中心是下面

问题的解

ｍａｘ∑（∥ｃ屈一∥（夕ｒ），）屈）

ｆ＝ｌ

ｓＪ・Ｙ∈■・

解析中心割平面算法算法如下：

第０步给定ｍ个初始向量｛届，屈…，尾），ｇ＞０，Ｂ，，Ｂ。．

ｋ

第１步

计算令ｊｆ＝１，ｗｏ＝｛少∈Ｒ‘Ｉ∑屈，只月，届≤屈７’ｃ屈，ｔ＝ｌ，２…，埘，．，－ｌｍａｘｂｒｙ

七

ｓ１．∑ｐ？ｙｉＡｐｔ§ｐ？Ｃ线ｔ＝、，２’．．‘，ｍ．

得最优解Ｊ，Ｊ，Ｂ。＝ｍｉｎ｛ｂ７’ｙＪ，Ｂ。｝．２７

青岛人学硕＋学位论文

第２步计算乃＝以。（月ｒＹ７－ｃ），若乃≤ｏ，则Ｂ，＝ｍａｘ｛ｂ７’ｙＪＢ，），转第５步，否

则转第３步。

第３步令ｙｊ＝ｙｊ一九Ｊ５），Ｂ｜＝ｍａｘ｛ｂＴｙＪＢ｜、．

第４步计算乃对应的单位特征向量玩＋，，令

Ｑ』：｛ｙ∈彤Ｉｆｌｍ＋ｊｒＣｆｌｍ＋厂圭成＋，７’∥月尾＋，≥ｏ，０成＋川：＝１），＿＝＿一。ｕＱＪ，

ｚ‘＝ｍａｘ

ｓ．ｔ・解线性规划问题ｂｒｙＹ∈■・

最优解为ｙ７，令战＝ｍｉｎ｛ｚ＊，Ｂ。）．

第５步若ｌＢ。－Ｂ，Ｉ≤ｓ，停止，ＹＪ为近似最优解，否贝ＪＪｊ＝ｊ＋ｌ，令Ｙ。＝一一ｔ的解

析中心，转第２步。

在本章给出的假设下，构造的算法有如下收敛性结果：

定理３．２（收敛性定理）若算法有限步终止得到Ｙ‘，则Ｙ。即为问题（５）的最

优解；若不有限步终止，则由算法可得到无穷点列｛Ｙ，），其任意极限点歹都为问题

（５）的最优解。

证明若算法有限步终止得到Ｙ‘，根据算法知Ｙ‘即为问题（５）的最优解。

若ｚ。，１０无穷点列｛ｙ’），由假设知｛ｙ７）有界，故存在收敛子列｛ｙｔ），使得觑ｌｉ＋ｍ。ｙ岛＝歹，

这个子列不妨设为｛ｙ‘），对于少对应的对偶松弛矩阵为Ｓ。，相应使得！鳃∥＝Ｓ，

九；。（ｓ‘）对应的单位特征向量为展，同理使得！骢展．＝万，由算法知Ｍ满足

孱一ｌ７’ｃ孱一ｌ一展＿ｌＴ（月７’Ｙ‘）孱一１≥０，即屈～ｌｒｓ‘展一ｌ＝展一ｌ厦一ｌ７’・Ｓ。≥０，因为

厦一ｌ展一ｌ７’ｏＳ‘＝展一１展一Ｉ７’ｏＳ扣１＋屈一Ｉ反一Ｉｏ（Ｓ‘－Ｓ七一１）≥０，令ｋ—００得７１

历７’・ｉ＋历７’ｏ（Ｓ一一百）≥０，所以ｋ（箩）＝历７’・ｉ≥０，歹为问题（５）的可行解。

设问题（５）的最优值为∥＋，则６ｒ儿≥∥‘，取极限有ｂｒ罗≥∥＋，又因为歹为问题（５）２８

第三章半定规划问题的解析中心割平面法

的可行解故６７’歹≤∥’，所以６丁歹＝∥’，即歹为问题（５）的最优解，得证。

由定理可得，当占＝０时，ＩＢ。－Ｂ，Ｉ＝ｏ，算法有限步终止，Ｂ。＝Ｂ，，得剑最优解；

占＞０时，算法可得到无穷点列｛虮），其任意极限点歹都为问题的近似最优解。

３．３数值结果

我们将本算法用于求解最大割问题的过程中。在解决最大割问题中一般求解下

列半定规划问题，得到最大割问题的上界。设图Ｇ（Ｖ，Ｐ）的顶点集为矿（１，２…胛），（ｆ，力

表示顶点为，，Ｊ的边，割集为Ｓ，ｑ，表示边ｆ，Ｊ，的权。

ｍａｘ

ｓＪ．Ｃ・ＸＡ・ｘ＝１，ｉ＝１，２…，刀．

Ｘ≥０．

其中４表示Ａ（ｉ，ｉ）＝１，其余位置皆为０的方阵，

ｚ＝｛二１ｆ三；专ｓ，令国＝（％）…，ｘ∈Ｒｎ，。诹（ｘ）∈Ｒ“”表示由ｘ中元素为对角

元素的矩阵，旃昭是Ｄｉａｇ的逆运算，ｅ表示元素全是１的列向量。令

三＝Ｄｉａｇ（ｃｏｅ）一∞，则ｃ＝百Ｌ，ｘ＝砌７’．

上述半定规划的对偶问题是

ｍｉｎ已７’甜

盯．∑％４一Ｓ＝ｃ』ＪＪＪ

，二１

Ｓ≥０．

令Ｙ＝一“，得ｍａｘｅｒｙ

姒∑ｙ，Ａ＋ｓ＝一Ｃ

Ｓ≥０．

从而可以将上述半定规划问题转化成本文研究的半定规划问题，运用上述割平面算

法来求解最大割问题的上界。２９

青岛大学硕十学位论文

取占＝１０“对于无权图上述半定规划的计算结果如下表：

表３．１

迭代次数

ｎ＝２

ｎ＝５

ｎ＝ｌＯＵ一上９．６４６２６１７２１６１８６４３ｅ－００７８．３９６４２１３８０３９６６４６ｅ一００８２．７６８７９５３２１９０５７７０ｅ—００７最优值Ｏ．５０００００００２５６０５０１．２５００００００００００６９２．５０００００００００１６９３ｊ＝５ｊ＝１１ｊ＝２５

上述数值结果表明本文的算法是有效的。３０

结论

结论

本文研究了两类非线性半定规划问题一非光滑半定规划和非凸半定规划。第一章推广了一类含等式约束的非光滑半定规划的最优性条件，第二章给出求解非凸半定规划的新的非线性Ｌａｇｒａｎｇｅ函数，研究了函数的性质，并给出相应的算法，证明了算法的局部收敛性，给出了与罚参数相关的解的误差估计。第三章给出了可以用于求解较大规模半定规划问题的解析中心割平面算法，并证明了算法的收敛性，实际算例表明了算法的有效性。

本文给出了求解非凸半定规划的新的Ｌａｇｒａｎｇｅ乘子算法，在数值算例中得到了较好的结果，但算法在收敛性条件等方面还需进一步改进。

实际中往往是大规模半定规化问题，由于内点算法在求解大规模问题时的局限性，本文给出了解析中，Ｏ害Ｊｌ平面算法，达到求解大规模半定规划问题的目的，可还有许多不足之处，提高求解大规模半定规划问题算法的收敛速率和精度应做进一步讨论。３１

参考文献

参考文献

１ＦｏｒｓｇｒｅｎＡ．ＣｏｎｄｉｔｉｏｎｓｆｏｒＮｏｎｃｏｎｖｅｘＳｅｍｉｄｅｆｉｎｉｔｅＯｐｔｉｍａｌｉｔｙＰｒｏｇｒａｍｍｉｎｇ．

Ｍａｔｈｅｍａｔｉｃａｌ

２Ｐｒｏｇｒａｍｍｉｎｇ．２０００（８８）：１０５—１２８．ＯｐｔｉｍａｌｉｔｙＣｏｎｄｉｔｉｏｎｓｆｏｒＮｏｎｓｍｏｏｔｈＺｈａｏＷＨ，ＧａｏＹ．Ｆｉｒｓｔ—ＯｒｄｅｒＳｅｍｉｄｅｆｉｎｉｔｅ

Ｐｒｏｇｒａｍｍｉｎｇ．ＯＲＴｒａｎｓａｃｔｉｏｎｓ．２００６（３）：１—９．

３赵文会，高岩．Ｃ１，１半定规划的二阶最优性条件．数学物理学报．２００８（２８）：１５５—１６３．

４ＳｈａｐｉｒｏＡ．ＦｉｒｓｔａｎｄＳｅｃｏｎｄｏｒｄｅｒａｎａｌｙｓｉｓｏｆＮｏｎｌｉｎｅａｒＳｅｍｉｄｅｆｉｎｉｔｅＰｒｏｇｒａｍｍｉｎｇ．

ＭａｔｈｅｍａｔｉｃａｌＰｒｏｇｒａｍｍｉｎｇ．１９９７（７７）：３０１—３２０．

５李成进，孙文瑜．非凸半定规规划的Ｊ１．义Ｆａｋａｒｓ弓Ｉ理及最优性条件．高等学校计算数学学

报．２００８（３０）：１８４—１９２．

６王炜，朱琳琳，任咏红．求解约束规划的一个非线性Ｌａｇｒａｎｇｅ函数．辽宁师范大学学报（自然

科学版）．２００９（９）：２６５—２６９．

７ＢｅｒｔｓｅｋａｓＤＰ．ＣｏｎｓｔｒａｉｎｅｄＯｐｔｉｍｉｚａｔｉｏｎａｎｄＬａｇｒａｎｇｅＭｕｌｔｉｐｌｉｅｒＭｅｔｈｏｄｓ．ＮｅｗＹｏｒｋ：

ＡｃａｄｅｍｉｃＰｒｅｓｓ．１９８２．

８ＰｏｌｙａｋＲ．Ｌｏｇ—ＳｉｇｍｏｉｄＭｕｌｔｉｐｌｉｅｒｓＭｅｔｈｏｄｉｎＣｏｎｓｔｒａｉｎｅｄＯｐｔｉｍｉｚａｔｉｏｎ．Ａｎｎａｌｓｏｆ

Ｏｐｅｒａｔｉｏｎｓ

９Ｒｅｓｅａｒｃｈ．２００１（１０１）：４２７—４６０．Ｃ．ＳｅｍｉｄｅｆｉｎｉｔｅＰｒｏｇｒａｍｓ：ＮｅｗＳｅａｒｃｈＤｉｒｅｃｔｉｏｎｓ，Ｓｍｏｏｔｈｉｎｇ—Ｔｙｐｅ

ｏｎＫａｎｚｏｗＣ，ＮａｇｅｌＭｅｔｈｏｄｓ，ａｎｄＮｕｍｅｒｉｃａｌＲｅｓｕｌｔｓ．ＳＩＡＭＪｏｕｒｎａｌ

１０ＲｕｃｋｍａｎｎＪＪ，ＳｈａｐｉｒｏＡ．ＡｕｇｍｅｎｔｅｄＯｐｔｉｍｉｚａｔｉｏｎ．２００２（１３）：１—２３．ｐｒｏｇｒａｍｍｉｎｇ．ＮｅｗＬａｇｒａｎｇｉａｎｓｉｎｓｅｍｉ—ｉｎｆｉｎｉｔｅ

Ｙｏｒｋ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ．２００７．

１１ＨｅｌｍｂｅｒｇＣ．ＩｎｖｉｔｅｄＲｅｖｉｅｗＳｅｍｉｄｅｆｉｎｉｔｅＰｒｏｇｒａｍｍｉｎｇ．ＪｏｕｒｎａｌｏｆＯｐｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈ．

２００２（１３７）：１４６—４８２．

１２Ｓｉｖａｒａｍａｋｒｉｓｈｎａｎ

ＳｅｍｉｄｅｆｉｎｉｔｅＫＫ，ＭｉｔｃｈｅｌｌＪＥ．ＰｒｏｐｅｒｔｉｅｓｏｆａＣｕｔｔｉｎｇＰｌａｎｅＭｅｔｈｏｄｆｏｒＰｒｏｇｒａｍｍｉｎｇ．２００７．

ＣｅｎｔｅｒＣｕｔｔｉｎｇＰｌａｎｅＭｅｔｈｏｄｆｏｒ１３ＦａｎｇＳＣ．ＡｎＡｎａｌｙｔｉｃ

ＶａｒｉａｔｉｏｎａｌＳｏｌｖｉｎｇＳｅｍｉ—ＩｎｆｉｎｉｔｅＩｎｅｑｕａｌｉｔｙＰｒｏｂｌｅｍｓ．ＪｏｕｒｎａｌｏｆＧｌｏｂａｌＯｐｔｉｍｉｚａｔｉｏｎ．２００４（２８）：１４１—

１５２．３２

青岛人学硕十学位论文

１４ＳｈｅｒａｌｉＨ，ＢａｅａｒａｍＰＦ．ＥｎｈａｎｃｉｎｇＲＬＴｒｅｌａｘａｔｉｏｎｓｖｉａａｎｅｗｃｌａｓｓｏｆｓｅｍｉｄｅｆｉｎｉｔｅ

ｃｕｔｓ．ＪｏｕｒｎａｌｏｆＧｌｏｂａｌＯｐｔｉｍｉｚａｔｉｏｎ．２００２（２２）：２３３—２６１．

１５王新辉，刘三阳，刘红卫．半定规划的割平面算法及其应用．西安电子科技大学学报（自然科

学版）．２００４（３１）：１４０—１４３．

１６ＥｌｈｅｄｈｌｉＳ，ＧｏｆｆｉｎＪＬ．Ｔｈｅｉｎｔｅｇｒａｔｉｏｎｏｆ

ｗｉｔｈｉｎａａｎｉｎｔｅｒｉｏｒ—ｐｏｉｎｔｃｕｔｔｉｎｇｐｌａｎｅｍｅｔｈｏｄｂｒａｎｃｈ—ａｎｄ—ｐｒｉｃｅａｌｇｏｒｉｔｈｍ．ＮｅｗＹｏｒｋ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ．２００３．

１７贺素香，张立卫．非线性约束优化问题的一个修正Ｌａｇｒａｎｇｅ算法．数学物理学报．２００６，

２６（１）：４９—６２．

１８ＺｈａｎｇＬＷ．ＬｉｕＹＪ．ＣｏｎｖｅｒｇｅｎｃｅａｎａｌｙｓｉｓｏｆａｎｏｎｌｉｎｅａｒＬａｇｒａｎｇｅａｌｇｏｒｉｔｈｍｆｏｒ

ｎｏｎｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇｗｉｔｈｉｎｅｑｕａｌｉｔｙｃｏｎｓｔｒａｉｎｔｓ。ＪｏｕｒｎａｌｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ

＆Ｃｏｍｐｕｔｉｎｇ．２００３（１３）：１—１０．

１９蒋耀伟．半定规划及其应用研究［学位论文］．两安电子科技人学．２００９．

２０田嫒．半定规划问题的Ｌａｇｒａｎｇｉａｎ算法的研究．青岛人学．２００９．

２１ＳｕｎＯＦ，ＳｕｎＪ，ＺｈａｎｇＬＷ．ＴｈｅｒａｔｅｏｆｃｏｎｖｅｒｇｅｎｃｅｏｆｔｈｅａｕｇｍｅｎｔｅｄＬａｇｒａｎｇｉａｎｍｅｔｈｏｄ

ｆｏｒｓｅｍｉｄｅｆｉｎｉｔｅｐｒｏｇｒａｍｍｉｎｇ．ＪｏｕｒｎａｌｏｆＭａｔｈｅｍａｔｉｃａｌＰｒｏｇｒａｍｍｉｎｇ．２００８

（１１４）：３４９—３９１．

２２ＬｉｕＹＪ，ＺｈａｎｇＬＷ，ＬｉｕＭＪ．Ｃｏｎｖｅｒｇｅｎｃｅａｎａｌｙｓｉｓｏｆ

ｆｏｒｓｅｍｉｄｅｆｉｎｉｔｅｐｒｏｇｒａｍｍｉｎｇ．ＯＲ

ｔｈｅａｎｏｎｌｉｎｅａｒＬａｇｒａｎｇｅａｌｇｏｒｉｔｈｍｎｏｎｃｏｎｖｅｘＴｒａｎｓａｃｔｉｏｎｓ．２００７，１１（４）：５—１４．ＡｕｇｍｅｎｔｅｄＬａｇｒａｎｇｉａｎｉｎＮｏｎｌｉｎｅａｒ２３ＳｕｎＪ，ＺｈａｎｇＬＷ，ＷｕＹ．Ｐｒｏｐｅｒｔｉｅｓｏｆ

ＳｅｍｉｄｅｆｉｎｉｔｅＯｐｔｉｍｉｚａｔｉｏｎ．ＪｏｕｒｎａｌｏｆＯｐｔｉｍｉｚａｔｉｏｎＴｈｅｏｒｙａｎｄＡｐｐｌｉｃａｔｉｏｎｓ．

２００６（１２９）：４３７—４５６．

２４ＨｕａｎｇＸＸ，ＹａｎｇＸＱ．ＡＮｏｎｌｉｎｅａｒＬａｇｒａｎｇｉａｎＡｐｐｒｏａｃｈｔｏＣｏｎｓｔｒａｉｎｅｄ

Ｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｇｒａｍｓ．ＳＩＡＭＪｏｕｒｎａｌｏｎＯｐｔｉｍｉｚａｔｉｏｎ．２００１（１１）：１１１９—１１４４．

２５薛丹，田志远，于贻丹．半定规划的解析中心割平面法．青岛大学学报（自然科学版）．

２００９（２２）：３７—４０．

２６ＦｌｅｔｃｈｅｒＦ．Ｓｅｍｉｄｅｆｉｎｉｔｅｍａｔｒｉｘｃｏｎｓｔｒａｉｎｔｓｉｎｏｐｔｉｍｉｚａｔｉｏｎ．ＳＩＡＭＪＣｏｎｔｒｏｌＯｐｔｉｍ．

１９８５（２３）：４９３—５１３．

２７ＨｕａｎｇＸＸ，ＹａｎｇＸＱ，ＴｅｏＫＬ．Ｌｏｗｅｒ—ＯｒｄｅｒＰｅｎａｌｉｚａｔｉｏｎＡｐｐｒｏａｃｈ

３３ｔｏＮｏｎｌｉｎｅａｒ

．参考文献

ＳｅｍｉｄｅｆｉｎｉｔｅＰｒｏｇｒａｍｍｉｎｇ．ＪｏｕｒｎａｌｏｆＯｐｔｉｍｉｚａｔｉｏｎＴｈｅｏｒｙａｎｄＡｐｐｌｉｃａｔｉｏｎｓ．

２００７（１３２）．

２８ＢｅｌｌｍａｎＲ，ａｎｄＦａｎＫ．Ｏｎｓｙｓｔｅｍｓｏｆ１ｉｎｅａｒｉｎｅｑｕａｌｉｔｉｅｓｉｎＨｅｒｍｉｔｉａｎｍａｔｒｉｘｖａｒｉａｂｌｅｓ．

Ｉｎ：Ｃｏｎｖｅｘｉｔｙ，ｐｒｏｃｅｅｄｉｎｇｓｏｆｓｙｍｐｏｓｉａｉｎＰｕｒｅＭａｔｈｅｍａｔｉｃｓ．ＡｍｅｒｉｃａｎＭａｔｈｅｍａｔｉｃａｌ

Ｓｏｃｉｅｔｙ．１９６３（７）卜１１．

２９ＢｏｎｎａｎｓＪＦ，ＳｈａｐｉｒｏＡ．ＰｅｒｔｕｒｂａｔｉｏｎＡｎａｌｙｓｉｓｏｆＯｐｔｉｍｉｚａｔｉｏｎＰｒｏｂｌｅｍｓ．ＮｅｗＹｏｒｋ：

Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ．２０００．

３０袁亚湘，孙文瑜．最优化理论与方法．科学出版社．１９９７．３ｌ张贤达．矩阵分析与应用．清华大学出版社．２００４．

攻读学位期问的研究成果

攻读学位期间的研究成果

研究生期间发表的文章：

１薛丹，田志远，于贻丹．半定规划的解析中心割平面法．青岛大学学报（自然科学版）．Ｖ０１．２２Ｎｏ．４２００９．１２．

２于贻丹，田志远，薛丹．一个新的填充函数算法．青岛大学学报（自然科学版），Ｖ０１．２３Ｎｏ．２２０１０．６．３５

致谢

致谢

本文是在导师田志远教授的悉心指导下由本人独立完成的，从论文的选题、设计到丌题报告乃至论文的最终完成，都倾注了导师的大量心血和劳动。导师严谨的学风，高度的责任感和奉献精神，深深地影响了我，为我树立了榜样！在论文完成之际，由衷的感谢ＦＦｌ老师您对我的教诲。

感谢青岛大学数学科学学院和我硕士研究生课程任课教师给予我的无私帮助和指导，谢谢您们对我的关怀和帮助，在这里请接受我诚挚的谢意。

感谢同学们对我的深厚友情和帮助。

衷心感谢在百忙之中抽出时间审阅本论文的专家教授，感谢答辩委员会的各位老师和专家们对我的论文提出的宝贵建议，为我今后的学习和研究开拓了思路。

最后，感谢我的家人对我的无私奉献，感谢所有关爱我的人们！

薛丹２０１０年４月２７日