非线性最优化问题一族新罚函数方法研究.doc

摘要对于非线性最优化问题寻找快速有效的算法一直是优化专家们研究的热门方向之一．菲线性约束优化问题是和实际问题最接近的抽象模型，随着计算效学理论的发展，计算机性能的提高，寻求高效可靠而易于计算机实现的大规模非线性约束优化算法成为当代研究的热点．罚函数法是解决这一问题的有效的方法之罚函数的梅建直接影响着算法的有效性．本文在传统形式的罚函数基础上引入双曲余弦函数做罚项，构造了新的对于一般约束优化问题的双曲余弦罚函效和求解迭代公式；进一步地，又提出了求解具有等式约束优化问题的双曲罚函数乘子法，在第一章中，我们首先简要地介绍了非线性最优化问题的提出；判断最优解常用的最优性条件及常用的几类解决方法；回顾了早期的罚函数，并介绍了增广拉格朗日函数和乘子法的演变过程及现状．在第二章中，我们利用函数Ｑ（ｔ）＝ｃｈ（ｔ）一１良好的性质，提出一种用双曲余弦函数作罚项的双曲余弦罚函数及算法，证明了该罚函数和算法的合理性及迭代点列的收敛性．把它与传统的罚函数方法进行分析比较，说明新算法在一定程度上能减弱因罚因子过大衙引起的病态性质，从而易于计算机的编程实现．我们做了数值实验，计算结果表明本文中所提出的方法有望提高算法收敛的速度．在第三章中，我们把传统的增广Ｌａｇｒａｎｇｅ函数和双曲余弦函数结合，构造了一类新的在等式约束下的双曲罚函数乘子法，推导出了双益乘子迭代公式．在一定条件下证明了算法的收敛性，并做数值实验检验了该方法的有效性．关键词：罚函数，乘子法，约束最优化，增广拉格朗日函数，收敛性Ｓｅｅｋｉｎｇ ｆａｓｔ ａｎｄ ｅｆｆｅｃｔｉｖｅ ｄｇｏｎｔｈｍｓ ｉｎ ｎｏｎｌｉｎｅａｒ ｏｐｔｉｍｉｚａｔｉｏｎ ｈａｓ ｂｅｅｎａｖｅｒｙ ｉｎｔｅｒｅｓｔｅｄ ｒｅｓｅａｒｃｈ ｔｏｐｉｃ ｆｏｒ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎｒｅｓｅａｒｃｈｅｒｓ．Ｎｏｎｌｉｎｅａｒｃｏｎ－ｓｔｒａｉｎｅｄ ｏｐｔｌｍ｛ｚａｔｉｏｎａｒｅｔｈｅ ａｂｓｔｒａｃｔ ｍｏｄｅｌｓ ｍｏｓｔ ｐｒｏｘｉｍａｌ ｔｏ ｔｈｅ ｐｒａｃｔｉｃａｌｔｈｅ ｃａｌｃｕｌａｔｉｖｅ ｍａｔｈｅｍａｔｉｃｓ ａｎｄ ｔｈｅ ａｄ－ｙａ２１ｃ８ ｏｆ ｔｈｅ ｃａｐａｂｉｌｉｔｙ ｏｆ ｔｈｅ ｃｏｍｐｕｔｅｒｓ，ｆｉｎｄｉｎｇ ｄｅｐｅｎｄａｂｌｅ ｍｇｈ ｅｆｆｅｃｔｉｖｅ蜘ｒｉｔｈｍｓ ｔｈａｔ ａｒｅ ｅａｓｙ ｔｏ ｃａｒｒｙ ｏｕｔ ｆｏｒ ｃｏｍｐｕｔｅｒｓ ｂｅｃｏｍｅｓ ｆｏｃｕｓ ｏｆ ｔｈｅ ｅｒａ．Ｐｅｎａｌｔｙｆｕｎｃｔｉｏｎ ｍｅｔｈｏｄ ｉｓｏｎｅｏｆ ｔｈｅ ｅｆｆｅｃｔｉｖｅ ｍｅｔｈｏｄｓ ｔｏ ｓｏｌｖｅ ｔｈｉｓ ｋｉｎｄ ｏｆｐｒｏｂｌｅｍｓ．Ｔｈｅ ｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ ｔｈｅ ｐｅｎａｌｔｙ ｆｕｎｃｔｉｏｎ ｅｆｆｅｃｔｓ ｔｈｅ ｅｆｆｉｃｉｅｎｃｅ ｏｆ ｔｈｅ ａｌｇｏ－ｒｉｔｈｍｓ。

Ｉｎ ｔｈｉｓ ｐａｐｅｒ ｗｅ ｉｎｔｒｏｄｕｃｅ ｔｈｅ ｈｙｐｅｒｂｏｌｉｃ ｃｏｓｉｎｅ ｆｕｎｃｔｉｏｎ ａｎｄ ｃｏｎｓｔｒｕｃｔｔｈｅ ｎｅｗｃｏｎｓｔｒｕｃｔｈｙｐｅｒｂｏｌｉｃ ｃｏｓｉｎｅ ｐｅｎａｌｔｙ ｆｕｎｃｔｉｏｎ ａｎｄ ａｌｇｏｒｉｔｈｍｓ．ｆｕｒｔｈｅｒｔｈｅ ｎｅｗ ｈｙｐｅｒｂｏｌｉｃ ｃｏｓｉｎｅ ｍｕｌｔｉｐｉｅｒ ｐｅｎａｌｔｙ ｆｕｎｃｔｉｏｎ．ｍｏｒｅ，ｗｅＩｎ ｃｈａｐｔｅｒ ｌ，ｗｅ ｆｉｒｓｔ ｉｎｔｒｏｄｕｃｅ ｔｈｅｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ｏｐｔｉｍｉｚａｔｉｏｎ；Ｓｏｍｅｃｏｎ－ｄｉｔｉｏｎｓ ｔｏ ｄｅｃｉｄｅ ｔｈｅ ｏｐｔｉｍｕｍ ｓｏｌｕｔｉｏｎ ａｎｄ ｓｅｖｅｒａｌ ｄｅｓｃｅｎｔ ｍｅｔｈｏｄｓ ｏｆ ｕｎｃｏｎ－ｓｔｒａｉｎｅｄ ｏｐｔｉｍｉｚａｔｉｏｎ；Ｌｏｏｋ ｂａｃｋ ｔｏ ｔｈｅ ｐｅｎａｌｔｙ ｆｕｎｃｔｉｏｎ ａｎｄ ｉｎｔｒｏｄｕｃｅ ｔｈｅ ｄｅ－ｖｅｌｏｐｍｅｎｔ ａｎｄ ｔｈｅ ｐｒｅｓｅｎｔ ｃｏｎｄｉｔｉｏｎｓ ｏｆ ｔｈｅ ａｕｇｍｅｎｔｅｄＬａｇｒａｎｇｅｆｕｎｃｔｉｏｎａｎｄｍｕｌｔｉｐｌｉｅｒ ｍｅｔｈｏｄｓ．Ｉｎ ｃｈａｐｔｅｒ ２，ｕｓｉｎｇ ｔｈｅ ｆａｖｏｒａｂｌｅ ｃｈａｒａｃｔｅｒｓ ｏｆ ｔｈｅｆｕｎｃｔｉｏｎ Ｑ扫）＝ｃｈ（ｚ）一１，ｗｅｃｏｎｓｔｒｕｃｔ ｔｈｅ ｈｙｐｅｒｂｏｌｉｃｃｏｓｉｎｅ ｐｅｎａｌｔｙ ｆｕｎｃｔｉｏｎ ａｎｄ ａｌｇｏｒｉｔｈｍｓ ａｎｄｐｒｏｖｅｄｉｔｓ ｃｏｎｖｅｒｇｅｎｃｅ．ＩｔＣａｎｗｅａｋｅｎ ｔｈｅ ｃｈａｒａｃｔｅｒｓ ｗｈｅｎ ｔｈｅ ｐｅｎａｌｔｙ ｇｅｎｅｓ ｇｅｔｓ ｔｏｏｌａｒｇｅ ｗｈｅｎ ｃｏｍｐａｒｅｄⅥｄｔｈ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ｐｅｎａｌｔｙｆｕｎｃｔｉｏｎ．Ｗｅｐｒｏｐｏｓｅ ｔｈｅｎｕｍｅｒｉｃａｌ ｅｘｐｅｒｉｍｅｎｔｓ ｗｈｉｃｈ ｓｈｏｗ ｔｈｅｙａｒｅｍｏｒｅ ｅｆｆｉｃｉｅｎｔ．Ｉｎ ｃｈａｐｔｅｒ ３，ｃｏｍｂｉｎｉｎｇ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ａｕｇｍｅｎｔｅｄ Ｌａｇｒａｎｇｅ ｆｕｎｃｔｉｏｎａｎｄｔｈｅ ｈｙｐｅｒｂｏｌｉｃ ｃｏｓｉｎｅｆｕｎｃｔｉｏｎｔ ｗｅｃｏｎｓｔｒｕｃｔａｎｅｗ ｈｙｐｅｒｂｏｌｉｃ ｐｅｎａｌｔｙ ｆｕｎｃｔｉｏｎｍｕｌｔｉｐｌｉｅｒ ｍｅｔｈｏｄ ｆｏｒ ｔｈｅ ｅｑｕａｌｉｔｙ ｃｏｎｓｔｒａｉｎｅｄ ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ ｄｅｄｕｃｅｄ ｔｈｅ ｉｔ．ｅｒａｔｉｖｅｆｏｒｍｕｌａｓ，ａｎｄ ｐｒｏｖｅｄ ｔｈｅｃｏｎｖｅｒｇｅｎｃｅ ｕｎｄｅｒ ｓｏｍｅｃｏｎｄｉｔｉｏｎｓ．Ｗｅｐｒｏｐｏｓｅｔｈｅｎｕｍｅｒｉｃａｌｅｘｐｅｒｉｍｅｎｔｓ ｔｈａｔ ＳＨＯＷＳ ｔｈｅ ｅｆｆｉｃｉｅｎｃｅ．Ｋｅｙｗｏｒｄｓ：Ｐｅｎａｌｔｙｆｕｎｃｔｉｏｎ，Ｍｕｌｔｉｐｉｅｒｍｅｔｈｏｄ，Ｃｏｎｓｔｒａｉｎｅｄ ｏｐｔｉｍｉｚａ－ｔｉｏｎ，ＡｕｇｍｅｎｔｅｄＬａｇｒａｎｇｅｆｕｎｃｔｉｏｎ，Ｃｏｎｖｅｒｇｅｎｃｅ．ｔｈｅ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆｐｒｏｂｌｅｍｓ．Ｗｉｔｈ丫８｛；８９８９首都师范大学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。

除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明本人完全意识到本声明的法律结果由本人承担学位论文作者签名：稚肃看日期：年月Ｅｌ首都师范大学位论文授权使用声明本人完全了勰首都师范大学有关保留、使用学位论文的规定，学校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅有权将学位论文的内容编入有关数据库进行检索有权将学位论文的标题和摘要汇编出版保密的学位论文在解密后适用本规定学位论文作者签名：程木活日期：年月日１非线性最优化问题简介这一章里，我们简要介绍最优化问题的提出以及判断最优解常用的最优性条件；介绍了无约束和约束优化问题常用的几类主要算法Ｉ总结了罚函数的基本思想，详细介绍了几种罚函数算法；在最后一节，介绍了我们提出新罚函数算法的主要思想．１．１最优化问题的提出及最优性条件最优化理论与方法是一门应用性很强的年轻学科．它讨论决策问题的最佳之特性，构造寻求最佳解的计算方法，研究这些方法的理论性质及实际计算效果．随着现代科技的发展和计算机的广泛应用，进一步推动了最优化理论和算法的研究，新的方法不断出现，实际应用日益广泛．现在，最优化理论与方法在经济规划、工程设计、政府决策、生产管理、交通运输和军事国防等方面得到了广泛的应用，从而发展成为一门十分活跃的学科．一般来说，最优化问题可归结为求解如下的极小值问题ｔ骝ｍ）（１－１・１）其中，ｇ∈Ｄ是决策变量，，（ｚ）为目标函数，Ｄ∈ｊｐ为可行域．根据变量的类型，最优化问题可分为连续型最优化和离散型最优化ｆ也称组合优化）．连续型最优化问题又可分为目标函数和约束函数均为线性时的线性规划问题，以及目标函数和约束函数中至少有一个为非线性时的非线性优化问题．又根据可行域Ｄ的类型，菲线性优化问题可分为约束优化和无约束优化问题．一般无约束优化同题通常可描述为：磐ｍ）１（１．１．２）首都师范大学硬士学位论文・非线性最优化问题的—族新的罚函数方法研究本文主要研究约束最优化问题ｔ。

ｍｉ卵ｎ，（∞ｓ．ｔ．ｃ‘＠）＝０，ｉ＝１，２，・．，，ｍ；（１．１．３）（１．ｉ．４）ｑ＠）≥０，ｔ＝ｍ ｑ－１，ｍ－ｂ其中／：印一Ｒ为非线性连续函数．下面我们给出全局最优解和局部最优解的定义．２，ｒ一，ｎ．（１．１．５）定义１．１若矿∈舒具有性质ｔＶｘ∈舻，均有，０）≥ｆ（ｘ’），则称矿为问题（１．１＿Ｉ）的全局最优解．定义１．２若矿∈舻具有性质ｔ存在矿的莱个邻域坼（矿）＝扣Ｊ ｌｌｘ一矿０＜田，其中Ｊ＞０为某个正数，使得妇∈肌（矿），均有，０）２，（矿），则称∥为问题（１．１．１）的一个局部最优解，当目标函数，（ｚ）是凸函数时，局部最优解就是全局最优解．但在一般情形下找出全局最优解非常困难，通常在非线性优化中我们认为局部最优解即为所求的解．在实际的算法中，我们通常是找出满足局部最优解的必要条件的点．为行文方便，记ｇ（ｘ）＝ｖ，（ｚ）表示，（茹）的梯度，ｃ（ｘ）＝ｖ２，（￡）表示，（的Ｈｅｓｓｅ矩阵．下面我们给出这些必要条件引理１．１㈦（无约束优化一阶必要条件）若矿为问题（１．１．２）的—个局部最优解，且在矿的某个邻域内，（ｚ）∈Ｇ・则ｇ（矿）＝０．（Ｉ．Ｉ．６）引理１．２【１２）（无约束优化二阶必要条件）若矿为问题（１．１．２）的—个局部最优解，且在矿的某个邻域内，（ｚ）∈Ｇ２，则ｇ（矿）＝０，Ｇ（ｘ＋）≥０（１．Ｉ ７）第１章非线性最优化同题简介引理１．３［１２］（Ｋｕｌｍ－Ｔｕｃｋｅｒ必要条件）若矿为问题（１．１．３）一（１．１．５）的—个局部最优解，又正规性假定成立，则必存在向量”＝（埘，砖，…，Ａ：）７，使得ｎ、Ｔｆ（ｘ’）＋∑ｗｖ。