非线性规划的论文.doc

无约束非线性规划的算法与研究摘要本文旨在对非线性规划的算法和应用进行研究。非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年库恩和塔克发表的关于最优性条件(后来称为库恩塔克条件，又称为K-T条件)的论文是非线性规划正式诞生的一个重要标志。非线性规划在管理、工程、科研、军事、经济等方面都有广泛的应用，并且为最优设计提供了有力的工具。在第一章我们主要介绍了非线性规划的基础知如非线性规划的数学模型，凸函数和凹函数，极值问题以及下降迭代算法等。在第二章我们主要对约束条件的线性规划进行了具体介绍。在无约束非线性规划中主要讨论了一维搜索法和多变量函数极值的下降方法。第三章介绍了求解非线性规划的计算机软件并通过一些基本的例子，从而进一步加深对非线性规划进行理解。关键词：非线性规划；约束非线性规划；最优解无约束非线性规划的算法与研究第一章 绪论1.1非线性规划综述非线性规划是具有非线性目标函数或约束条件的数学规划，是运筹学的一个重要分支1。非线性规划属于最优化方法的一种，是线性规划的延伸。早在17世纪，Newton和Leibniz发明微积分的时代，已经提出函数的极值问题，后来又出现了Lagrange乘子法，Cauchy的最速下降法。但直到20世纪30年代，最优化的理论和方法才得以迅速发展，并不断完善，逐步成为一门系统的学科2。1939年，Kantorovich和Hitchcock等人在生产组织管理和制定交通运输方案方面首先研究和应用了线性规划。1947年，Dantzig提出了求解线性规划的单纯形法，为线性规划的理论和算法奠定了基础，单纯形法被誉为“20世纪最伟大的创造之一”。1951年，由Kuhn和Tucker完成了非线性规划的基础性工作 3。19591963年，由三位数学家共同研究成功求解无约束问题的DFP变尺度法(该算法是由英国数学家WCDavidon提出，由法国数学家RFletcher和美国数学家MJD.Powell加以简化)，该算法的研究成功是无约束优化算法的一个大飞跃，引起了一系列的理论工作，并陆续出现了多种新的算法4。1965年，德国数学家CG Broyden提出了求解非线性方程组的拟牛顿算法，并且该算法还包含了DFP算法。1970年，四位数学家以不同角度对变尺度算法进行了深入研究，提出了BFGS公式 (CG Broyden，R Fletcher，DGoldfarb，DE Shanno) 。实践表明该算法较之DFP算法和拟Newton法具有更好的数值稳定性。1970年，无约束优化方法的研究出现了引入注目的成果，英国数学家LCW Dixon和美籍华人HYHuang提出了关于“二阶收敛算法的统一研究”的研究成果，提出了一个令三个自由参数的公式族Huang族和拟牛顿公式，它可包容前面所介绍的所有无约束优化算法。20世纪70年代，最优化无论在理论和算法上，还是在应用的深度和广度上都有了进一步的发展。随着电子计算机的飞速发展，最优化的应用能力越来越强，从而成为一门十分活跃的学科5。近代最优化方法的形成和发展过程中最重要的事件有：1、 以苏联康托罗维奇和美国丹齐克为代表的线性规划； 2、 以美国库恩和塔克尔为代表的非线性规划； 3、 以美国贝尔曼为代表的动态规划； 4、 以苏联庞特里亚金为代表的极大值原理等。 这些方法后来都形成体系，成为近代很活跃的学科，对促进运筹学、管理科学、控制论和系统工程等学科的发展起了重要作用 非线性规划在经营管理、工程设计、科学研究、军事指挥等方面普遍地存在着最优化问题。例如：如何在现有人力、物力、财力条件下合理安排产品生产，以取得最高的利润；如何设计某种产品，在满足规格、性能要求的前提下，达到最低的成本；如何确定一个自动控制系统的某些参数，使系统的工作状态最佳；如何分配一个动力系统中各电站的负荷，在保证一定指标要求的前提下，使总耗费最小；如何安排库存储量，既能保证供应，又使储存费用最低；如何组织货源，既能满足顾客需要，又使资金周转最快等。对于静态的最优化问题，当目标函数或约束条件出现未知量的非线性函数，且不便于线性化，或勉强线性化后会招致较大误差时，就可应用非线性规划的方法去处理。1.2非线性规划的基础知识对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点： （1）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。 （2）提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。 （3）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它。 （4）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示。1.2.1非线性规划问题的数学模型非线性规划是具有非线性目标函数或约束条件的数学规划。它的数学模型常表示成以下形式： （1.1）其中自变量是维欧氏空间中的向量；是目标函数和是约束条件。也可以将非线性规划的数学模型写成以下形式 （1.2）对于求目标函数的最大值问题，我们可以转换成求其负函数的最小值问题，从而转换成非线性规划的标准形式。1.2.2极值问题1、局部极值和全局极值设是n维欧氏空间En中某一区域D的函数，这一区域D叫做可行域。对于，如果存在，对D且|X-X*|0，对XD且|X-X*|，都有f(X*)f(X),则称X*为在D上的严格局部极小点，f(X*)为严格局部极小值。如果对于一切XD，都有f(X*)，则称X*为f(X)在D上的全局极小点，f(X*)为全局极小值。如果对于一切XD，都有f(X*)0，则X*为f(X)的局部极小点。、1.2.3 凸函数和凹函数1、凸凹函数的定义设f(X)是n维欧氏空间En中某一凸集D上的函数，若对于任何实数(01)以及D中的任意两点X(1)和X(2)，恒有f(X(1)+(1-) X(2) f(X(1) +(1-)f(X(2)则称f(X)为定义在D上的凸函数。如果f(X(1)+(1-) X(2)0，则称约束条件 gjX0(1jl)是X0点的无效约束（或不起作用约束）。（2） 如果使 gjX0=0，则称约束条件 gjX0(1jl)是X0点的有效约束（或起作用约束）。如果 gjX0(1jl) 是X0点的无效约束，则说明X0位于可行域的内部，不在边界上，即当X0有微小变化时，此约束条件不会有什么影响。而对于有效约束则说明X0位于可行域的边界上，即当X0有微小变化时，此约束条件起着限制作用。定义3.2 设X0是非线性规划问题的一个可行解，即可行域R内的一点，d是过此点的某一个方向，如果：（1）存在实数00，使对任意0, 0均有X0+d R，则称此方向d是X0点的一个可行方向； (2) 存在实数00，使对任意0, 0均有f(X0+d )f(X0)，则称此方向d是X0点的一个下降方向； (3) 方向d既是X0点的可行方向，又是下降方向，则称它是X0点可行下降方向。3.2.2最优性的条件定理3.1 （Kuhn-Tucker）如果X*是问题（3.2）的极小点，且与点X*的有效约束的梯度线性无关，则必存在向量*=(1*,2,*l*)T使下述条件成立： fX*-j=1lj*gjX*=0j* gjX*=0 (j=1,2,l)j*0 (j=1,2,l) （3.3）此条件称为库恩-塔克（Kuhn-Tucker）条件，简称为K-T条件。满足K-T条件的点称为K-T点14。类似地，如果X*是问题（3.1）的极小点，且与点X*的所有有效约束的梯度hiX*(i=1,2,m)和gjX*(j=1,2,l)线性无关，则必存在向量*=(1*,2,*m*)T和*=(1*,2,*l*)T使下面的K-T条件成立： fX*-i=1mi*hiX*-j=1lj*gjX*=0j* gjX*=0 (j=1,2,l)j*0 (j=1,2,l) （3.4）将满足K-T条件的点也称为K-T点。其中1*,2,*m*和1*,2,*l*称为广义Lagrange乘子。3.3二次规划若某非线性规划的目标函数为自变量X的二次函数，约束条件又全是线性的，就称这种规划为二次规划。二次规划的数学模型可表述为： minfX=j=1ncjxj+12j=1nk=1ncjkxjxk （3.5）cjk=ckj , k=1,2,n （3.6）k=1naijxj+bi0 , i=1,2,m （3.7）xj0 , j=1,2,n （3.8）（3.6）式右端的第二项为二次型。如果该二次型正定（或半正定），则目标函数为严格凸函数（或凸函数）；此外，二次规划的可行域为凸集，因而，上述规划属于凸规划。前面已指出，凸规划的局部极值即为全局极值。对于这种问题来说，库恩-塔克条件不但是极值点存在的必要条件，而且也是充分条件。二次规划的求解：将K-T条件中的第一个条件应用于二次规划（3.6）（3.8），y代替K-T条件中的，即可得到： -k=1ncjkxk+i=1maijyn+i+yj=cj（j=1,2,n） (3.9)在式（3.8）中引入松弛变量xn+1，式（3.8）即变为（假定bi0）： i=1naijxj-xn+i+bi=0 （i=1,2,m） (3.10)再将K-T条件中的第二个条件应用于上述二次规划，并考虑到式（3.10），就得到 xjyj=0 （j=1,2,n+m） (3.11)此外，还有 xj0，yj0 （j=1,2,n+m） (3.12) 联立求解式（3.9）和（3.10），如果得到的解也满足式（3.11）和式（3.12），则这个解就是原二次规划问题的解。但是，在式（3.9）中，cj可能为正，也可能为负，为了便于求解，先引入人工变量zj（zj0，其前面的符号可以取正或负，以便得出可行解）。这样，式（3.9）就变成 i=1maijyn+i+yj-k=1ncjk+sgn（cj）zj=cj（j=1,2,n） (3.13)其中：sgn（cj）为符号函数：sgncj=1，当cj0时sgncj=-1,当cj0时这样一来，可得到初始基本可行解如下：zj=sgncj (j=1,2,n)xn+1=bi (i=1,2,m)xj=0 (j=1,2,n)yj=0 (j=1,2,n+m)但是，只有当zj=0时，才能够得到原来问题的解，故必须对上述问题进行修正，从而得到如下的线性规划问题： minZ=j=1nzj i=1maijyn+i+yj-k=1ncjkxk+sgn（cj）zj=cj（j=1,2,n）j=1naijxj-xn+i+bi=0 i=1,2,m xj0 , j=1,2,n+m yj0 , j=1,2,n+m zj0 , j=1,2,n (3.14)该线性规划问题还应满足式（3.10）。也就是说，不能使xj和yj（对每一个j）同时为基变量。解线性规划问题（3.14），若得到最优解（x1*,x2,*xn+m*,y1*,y2*,yn+m*, z1=0,z2=0,zn=0）,则（x1*,x2,*xn*）就是原二次规划问题的最优解。3.4约束非线性规划的求解方法3.4.1可行方向法考虑非线性规划问题（3.2），假设Xk是该问题的可行解，但不是最优解。为了进一步寻找最优解，在它的可行下降方向中选取其一个方向dk,并确定最佳步长k使得 Xk+1=Xk+kdkfXk+1f(Xk) （3.15）反复进行这一过程，直到得到满足精度要求的可行解为止，这种方法称为可行方向法。 可行方向法的主要特点是：因为迭代过程中所采用的搜索方向总为可行方向，所以产生的迭代点列Xk始终在可行域R内，且目标函数值不断的单调下降。可行方向法实际上是一类方法，最典型的是Zoutendijk可行方向法。定理3.2 设X*是问题（3.2）的一个局部极小点，函数f(X)和 gjX在X*处均可微，则在X*点不存在可行下降方向，从而不存在向量d同时满足 f(X*)Td0 (j=1,2,m) （3.16）Zoutendijk可行方向法 设Xk点的有效约束集非空，则Xk点的可行下降方向d=(d1,d2,dn)T必须满足f(X*)Td 0 ( jJ)又等价于f(X*)Td-gj(X*)Td0，jJ其中J是有效约束的下标集。此问题可以转化为求下面的线性规划问题：s.t.min f(Xk)Td -gj(Xk)Td -1di1 (i=1,2,n) ( jJ) （3.17）其中最后一个约束是为了求问题的有限解，即只需要确定d的方向，这只要确定其单位向量即可。如果求得=0，则在Xk点不存在可行下降方向，Xk就是K-T点。如果求得0，20，选初始近似点X0R,并令k=0。（2） 确定起作用约束指标集J(Xk)=j| gjXk=0,1jl 若J(Xk)