对罚函数的研究.docVIP

对罚函数的探讨 （一）背景 最优化既是一个古老的课题，又是一门年轻的学科，它讨论决策问题的最佳选择之特性，构造寻求最佳解的计算方法，研究这些计算方法的理论性质及实际计算表现。最优化方法和理论来源于军事、管理、经济和工程技术领域的各个方面，早在17世纪，Newton和Leibniz发明微积分的时代，已经提出函数的极值问题，后来又出现了Lagrange乘子法，Cauchy的最速下降法。但直到20世纪30年代，最优化的理论和方法才得以迅速 发展，并不断完善，逐步成为一门系统的学科。 1930年，苏联数学家康托诺维奇首创图上作业法解决小规模的线性规划问题，如物资调运方案、合理下料方案等，而大规模的线性规划则是在电子计算机问世以后才得以发展。1939年，Hitchcock等人在生产组织管理和制定交通运输方案方面首先研究和应用了线性规划；1947年， Dantzig提出了求解线性规划的单纯形法，为线性规划的理论和算法奠定了基础，单纯形法被誉为“20世纪最伟大的创造之一”；1950-1965年，匈牙利数学家库恩和塔克建立了线性规划的对偶理论，为求解鞍点问题提供了数学工具，两位年轻的数学家建立约束极值的最优性条件被称为K-T条件，为求解非线性规划奠定了理论基础；1958年，美国数学家R.E.Gomery提出整数规划的割平面法；1960年，丹茨和英国数学家维尔夫研究成功线性规划的分解算法，该算法为求解大规模线性规划提供了有力的工具； 1970-1984年，前苏联数学家卡钦杨和美国数学家卡马尔卡先后提出并完成了线性规划的多项式算法[11,12]，轰动了整个数学界。 随着电子计算机的普遍使用，非线性规划的理论和方法有了很大的发展，其应用的领域也越来越广泛，特别是在军事、经济、管理、生产过程自动化、工程设计和产品优化设计等方面都有着重要的应用。非线性规划是20世纪50年代才开始形成的一门新兴学科，其理论是在线性规划2的基础上发展起来的。1959-1963年，由三位数学家共同研究成功求解无约束问题的DFP变尺度方法，该算法的研究成功是无约束优化算法的一个大飞跃，引起了一系列的理论工作，并陆续出现了多种新的算法；1965年德国数学家C.G.Broydenb提出了求解非线性方程组的拟Newton法，并且该算法还包容了DFP算法；1970年，四位数学家从不同角度对变尺度算法进行深入研究，提出了BFGS公式，实践表明该算法较之DFP算法和拟Newton法具有更好的数值稳定性；1970年，无约束优化方法的研究出现了引人注目的成果。Powell法是一种改进后的共轭方向法，是迄今为止求解无约束优化问题最有效的方法。其基本思路是：利用共轭方向的概念，逐次构造共轭方向，作为算法迭代的有哪些信誉好的足球投注网站方向，采用一维优化方法确定沿有哪些信誉好的足球投注网站方向上的最优迭代步长，它既避免在每次有哪些信誉好的足球投注网站中有哪些信誉好的足球投注网站方向的线 性相关性所产生的有哪些信誉好的足球投注网站方向又趋向相互共轭。这种方法不需要对目标函数作求导计算，由于变量n10?20，当遇到目标函数的一阶导数不连续的最优化问题时，也能得到很好的计算结果。求解约束极值问题的基本算法有：惩罚函数法、可行方向法、投影梯度法。20世纪70年代以来，非线性规划算法有较大的进展，非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。 二次规划问题是最简单也是最早被人们研究的一类非线性规划问题，有着广泛的实际背景。人们对于求解二次规划问题已做了很多探索，特别是近20年来二次规划的解法已取得很大进展，有了比较有效的算法，如文献，中的拉格朗日乘子法和有效集方法等。由于二次规划问题比较容易解决，特别是序列二次规划方法的发展使得研究二次规划的求解更为重要。 非线性(混合)整数规划是当今国际上最优决策与应用领域里一个极为重要的分支，因此通过构造一种惩罚函数将这类问题连续化，转化成相应的非线性规划，并利用非线性规划的相关算法解决，是有意义的尝试。文献对非线性整数规划问题提出了惩罚函数解法，文献给出了一类可分离非线性混合整数规划的填充函数解法，文献给出了非线性整数规划的一个近似算法，文献对一类非线性两层混合整数规划问题，选取一种混沌性较强的自映射，设计了一种新型的混沌遗传算法，文献中给出了非线性整数规划的连续化解法，文献对有界闭箱中的非线性混合整数规划进行了探讨，通过惩罚函数法把有约束问题化为等价无约束问题，再利用求解无约束非线性规划问题的解法得到原问题的最优解。 二 惩罚函数算法简介 在工程实践中，绝大多数的优化问题都包含有约束条件，都属于多维有约束优化问题，约束非线性规划问题广泛见于工程、国防、经济等许多重要领域。若在需要解决的优化问题中，存在非线性函数，那么这类优化设计问题就称为非线性规划问题。求解这类问题的思路有两种：一种是直接在约束可行域内寻求约束最优点，另一种是将约