非线性规划的论文

无约束非线性规划的算法与研究摘要本文旨在对非线性规划的算法和应用进行研究。非线性规划是20世纪50年代才开始形成的一门新兴学科。1931年库恩和塔克发表的关于最优性条件（后来称为库恩一塔克条件，乂称为K-T条件）的论文是非线性规划正式诞生的一个重要标志。非线性规划在管理、工程、科研、军事、经济等方面都有广泛的应用，并且为最优设计提供了有力的工具。在第一章我们主要介绍了非线性规划的基础知如非线性规划的数学模型，凸函数和凹函数，极值问题以及下降迭代算法等。在第二章我们主要对约束条件的线性规划进行了具体介绍。在无约束非线性规划中主要讨论了一维搜索法和多变量函数极值的下降方法。第三章介绍了求解非线性规划的计算机软件并通过一些基本的例子，从而进一步加深对非线性规划进行理解。关键词：非线性规划；约束非线性规划；最优解无约束非线性规划的算法与研究第一章绪论1非线性规划综述非线性规划是具有非线性LI标函数或约束条件的数学规划，是运筹学的一个重要分支用。非线性规划属于最优化方法的一种，是线性规划的延伸。早在17世纪，Newton和Leibniz发明微积分的时代，已经提出函数的极值问题，后来乂出现了Lagrange乘子法，Cauchy的最速下降法。但直到20世纪30年代，最优化的理论和方法才得以迅速发展，并不断完善，逐步成为一门系统的学科巨。1939年，Kantorovich和Hitchcock等人在生产组织管理和制定交通运输方案方面首先研究和应用了线性规划。1947年，Dantzig提出了求解线性规划的单纯形法，为线性规划的理论和算法奠定了基础，单纯形法被誉为“2世纪最伟大的创造之一”。1951年，由Kuhn和Tucker完成了非线性规划的基础性工作⑶。1959-1963年，山三位数学家共同研究成功求解无约束问题的DFP变尺度法(该算法是由英国数学家W.C.Davidon提出，由法国数学家R.Fletcher和美国数学家M.J.D.Powel1加以简化)，该算法的研究成功是无约束优化算法的一个大飞跃，引起了一系列的理论工作，并陆续出现了多种新的算法⑷。1965年，德国数学家C.GBroyden提出了求解非线性方程组的拟牛顿算法，并且该算法还包含了DFP算法。1970年，四位数学家以不同角度对变尺度算法进行了深入研究，提出了BFGS公式(C.GBroyden,RFletcher,D.Goldfarb,D.EShanno)。实践表明该算法较之DFP算法和拟Newton法具有更好的数值稳定性。1970年，无约束优化方法的研究出现了引入注目的成果，英国数学家L.C.WDixon和美籍华人H.Y.Huang提出了关于“二阶收敛算法的统一研究”的研究成果，提出了一个令三个自由参数的公式族・Huang族和拟牛顿公式，它可包容前面所介绍的所有无约束优化算法。20世纪70年代，最优化无论在理论和算法上，还是在应用的深度和广度上都有了进一步的发展。随着电子计算机的飞速发展，最优化的应用能力越来越强，从而成为一门十分活跃的学科⑸。近代最优化方法的形成和发展过程中最重要的事件有：1、以苏联康托罗维奇和美国丹齐克为代表的线性规划：2、以美国库恩和塔克尔为代表的非线性规划；3、以美国贝尔曼为代表的动态规划：4、以苏联庞特里亚金为代表的极大值原理等。这些方法后来都形成体系，成为近代很活跃的学科，对促进运筹学、管理科学、控制论和系统工程等学科的发展起了重要作用非线性规划在经营管理、上程设计、科学研究、军事指挥等方面普遍地存在着最优化问题。例如：如何在现有人力、物力、财力条件下合理安排产品生产，以取得最高的利润；如何设计某种产品，在满足规格、性能要求的前提下，达到最低的成本；如何确定一个自动控制系统的某些参数，使系统的工作状态最佳；如何分配一个动力系统中各电站的负荷，在保证一定指标要求的前提下，使总耗费最小；如何安排库存储量，既能保证供应，乂使储存费用最低；如何组织货源，既能满足顾客需要，乂使资金周转最快等。对于静态的最优化问题，当□标函数或约束条件出现未知量的非线性函数，且不便于线性化，或勉强线性化后会招致较大误差时，就可应用非线性规划的方法去处理。1.2非线性规划的基础知识对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下儿点：（1）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。（2）提出追求H标：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。（3）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它。（4）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示。1.2.1非线性规划问题的数学模型非线性规划是具有非线性LI标函数或约束条件的数学规划。它的数学模型常表示成以下形式：min/(X)</*(X)=0J=12…，加(1.1)gj(X)N0,j=l,2,..・,f其中自变量X=(xi9x29...9xn)r是〃维欧氏空间中的向量；/(X)是目标函数/zf.(x)=0和gj(x)no是约束条件。也可以将非线性规划的数学模型写成以下形式minf(X)(1.2)对于求LI标函数的最大值问题，我们可以转换成求其负函数的最小值问题，从而转换成非线性规划的标准形式。1.2.2极值问题1、局部极值和全局极值设/(X)是力维欧氏空间夕中某一区域0的函数，这一区域0叫做可行域。对于X*eL,如果存在>6,对xFv/且HX-X*//<r,都有f(x*)w/(X),则称x*为/(X)在。上的局部极小点，fcr*J为局部极小值。对于X*e：0,如果存在e>6,对XWD且X-X*〈&，都有f(X*)<f(X),则称尤*为/0)在0上的严格局部极小点，ftXV为严格局部极小值。如果对于一切〉VJ都有f(X*)W/(X),则称X*^/XV在D上的全局极小点，f(X")为全局极小值。如果对于一切力V/,都有f(X*)<f(X)，则称X*为f如在0上的严格全局极小点，f(X")为严格全局极小值。2、极值点存在的判定首先引入梯度和海赛(Hessian)矩阵的定义。设力元函数f如的一阶偏导数存在，则称

为函数fd?的梯度函数。设力元函数^▼的二阶偏导数存在，称山f(X)的所有二阶偏导数构成的矩阵a-Xz)d2Mdxfdxjdx2沪心dxjdxndx''dxj■dxjdXr■■■■■■a'AzO*a-7(z0dXfJd%为函数/7X?的海赛(Hessian)矩阵。它是对称矩阵。山线性代数知道，二次型懑为正定的充要条件是它的矩阵〃的左上角各阶主子式都大于零；而它为负定的充要条件是它的矩阵〃的左上角各阶主子式依次正负相间。二次型为正定、负定或不定时，对称矩阵〃分别为成为正定的、负定的或不定的。定理11：(一阶必要条件)设f如是刀维欧氏空间夕中某一区域。的函数也*)f，初，定理1.2:(二阶必要条件)设f①是n维欧氏空间F中某一区域。的函数,f如的一阶连续偏导数存在。若X左为f(x)的局部极小点，则迎广)\的二阶连续偏导数存在。若〃为f如的局部极小点，则〃&*)二SM厂)$6O定理1.3:(二阶充分条件)设f如是力维欧氏空间F中某一区域。的函数，ie8(D)。若勺(才*)二Bxf>S则尤*为如的局部极小点。、1-2.3凸函数和凹函数1、凸凹函数的定义设f也*)f，初，定理1.2:(二阶必要条件)设f①是n维欧氏空间F中某一区域。的函数,a(0<a〈〃以及。中的任意两点尤⑵和X仞，恒有f(aX(i"(l-a)X2))Waf(Xi))十(1-a)f(X2))则称f如为定义在0上的凸函数。如果f{aX（i）+（l-a）X2））<af（Xi））+（1-a）fiX⑵）则称f如为定义在0上的严格凸函数。将上面两式的不等号反向，即可得凹函数和严格凹函数的定义。显然，如果为凸函数（严格凸函数），则-/YV一定是凹函数（严格凹函数）。凸函数的性质设，△都是D上的凸函数，SS则f》f是。上的凸函数。设f如是定义在凸集。上的凸函数，则对任一实数0,集合=VD,f（X）W刃是凸集。函数凸性的判定定理1・4:（一阶条件））设是刀维欧氏空间夕中某一开凸集0的函数，f如的一阶连续偏导数存在。则f如为0上的凸函数的充要条件是，对任意两个不同的点X⑵和〃匕恒有f（x⑵）nfJ一wJ定理1.5:（二阶条件）设f如是门维欧氏空间夕中某一开凸集0的函数，f①的二阶连续偏导数存在。则f①为0上的凸函数的充要条件是：/ZV的海赛（Hessian^阵〃如在0上处处半正定。凸函数的极值定理1.6:若/ZV是定义在凸集0上的凸函数，则它的任一极小点就是它在刀上最小点（全局极小点），而且它的极小点形成一个凸集。定理1・7:设f仞是定义在凸集0上的可微凸函数，若存在点尤欷e乙使得对于所有的尤&殖-X*）鼻侧厂是f如在。上的最小点（全局极小点）。当X*是。得内点时，式子磔厂儿尤-厂JMC对于任意尤-广都成立，这就意味着可将式子-XV$c改为勺（厂）二屋1.2.4凸规划对一个非线性规划问题，如果：1、目标是求凸函数的最小值。2、每个等式约束函数都是一个线性函数。3、每个小于或等于的约束函数都是凸函数。4、每个大于或等于约束函数都是凹函数。则称该非线性规划问题是凸规划问题。定理1・8：凸规划问题的可行域是凸集。定理1・9：凸规划问题局部最优解就是总体最优解。1.2.5下降迭代算法迭代法的基本思想是：为了求函数的最优解，首先给定一个初始估计然后按某种算法找出比X仞更好的解尤⑵，再按照此种规划找出比X®更好的解X仞，…。即可得到一个解的序列｛X〃｝。若这个序列有极限即Jjrn!/Y(k)-V*//k_8—‘丸，则称它收敛于厂。若山某算法所产生的解的序列｛*〃｝使忖标函数心〉)逐渐减少，就称这算法为下降算法。我们把x(k+i)-x(k"kfFU做基本迭代模式。严称为搜索方向，，仃称为步长或步长因子。所以下降迭代算法的步骤可总结如下：选定某一初始点尤仞，并令&=0；确定搜索方向严；从/俐出发，沿方向严求步长J仃，以产生下一个迭代点X(k'检查得到的新点X(k!)是否为极小点或近似极小点。若是，则停止迭代。否则，令2k+l,转回(2)继续进行迭代。第二章约束条件的非线性规划3.1约束非线性规划的数学模型带有约束条件的极值问题称为约束极值问题，也叫规划问题。其一般形式为222'姒的。J（3.1））minf（X）I呼力$o,j=1,2,・・・，1（3.2）3.2最优性问题3.21最优性的基本概念定义3.1设”是非线性规划问题的一个可行解，它使某个的（处NglWjW力，具有下面两种情况：（1）如果gJ（W）>G则称约束条件胡力WjW刀是〃点的无效约束（或不起作用约束）。（2）如果使阳（0）二、则称约束条件胡力三gWjW■力是点的有效约束（或起作用约束）。如果殆（力鼻MlWjWI）是”点的无效约束，则说明”位于可行域的内部，不在边界上，即当”有微小变化时，此约束条件不会有什么影响。而对于有效约束则说明”位于可行域的边界上，即当”有微小变化时，此约束条件起着限制作用。定义3.2设”是非线性规划问题的一个可行解，即可行域斤内的一点，〃是过此点的某一个方向，如果：（1）存在实数DG使对任意以G[0,心均有M八三日，则称此方向〃是F点的一个可行方向；（2）存在实数一■>6,使对任意以&[0,人刀均有/'必如以a则称此方向〃是〃点的一个下降方向;方向孑既是F点的可行方向，乂是下降方向，则称它是”点可行下降方向。3.2.2最优性的条件定理3.1(Kuhn-Tucker)如果是问题(3.2)的极小点，且与点尤*的有效约束的梯度线性无关，则必存在向量厂*=(ryJ：・Y使下述条件成立：总人尤*)-岁切(厂)二0j/(护)=0(j=1,2,・・・，1)'门鼻0(j二1,2,...,1)(3.3)此条件称为库恩-塔克(Kuhn-Tucker)条件，简称为K-T条件。满足K-T条件的点称为K-T点严。类似地，如果工*・是问题(3.1)的极小点，且与点X*・的所有有效约束的梯度弘CY订(i二1,2，…,勿和切(才(j二1,2,…,D线性无关，则必存在向量A*=r.iL入2二/I:广和Y*=(rL丫2二r〃使下面的K-T条件成立：总人厂)一工：二川*%Cr*)-Jy*切(厂)二6j/厂)=0(j=1,2,...,1)丫1鼻。(j=1,2,...,1)(3.4)将满足K-T条件的点也称为K-T点。其中A,4昇.，以：和yy2ry:称为广义Lagrange乘子。3.3二次规划若某非线性规划的□标函数为自变量*的二次函数，约束条件乂全是线性的，就称这种规划为二次规划。二次规划的数学模型可表述为：minfix)=E：=+:二声,=卢以为必5=Qy/(k=1,2t…,n):12,…，m)勺20,j二L2*•匕n(3.6)式右端的笫二项为二次型。如果该二次型正定(或半正定)，则口标函数为严格凸函数(或凸函数)；此外，二次规划的可行域为凸集，因而，上述规划属于凸规划。前面已指出，凸规划的局部极值即为全局极值。对于这种问题来说库恩-塔克条件不但是极值点存在的必要条件，而且也是充分条件。二次规划的求解：将K-T条件中的第一个条件应用于二次规划(3.6)——(3.8),y代替K-T条件中的Y,即可得到：二gjkxRi二jajjVjj+i+yj二Cj(J-1,2,…,n)(3.9)在式(3.8)中引入松弛变量xn.i,式(3.8)即变为(假定％步0)：二flijXj-xn+心=0(2-1,2…・,m}(3.10)再将K-T条件中的第二个条件应用于上述二次规划，并考虑到式(3.10)，就得到XjVj=O(j=l,2,••->n+m}(3.11)此外，还有

X仝6,Vj事G(〉=1,2,,n+m)(3.12)联立求解式(3.9)和(3.10),如果得到的解也满足式(3.11)和式(3.12),则这个解就是原二次规划问题的解。但是，在式(3.9)中，。可能为正，也可能为负，为了便于求解，先引入人工变量旬(右仝6,其前面的符号可以取正或负，以便得出可行解)。这样，式(3.9)就变成乙(二fiijVn+i+yj一乙点二］Cjk+sgn(CC)zg(j-1,2,・,n)(3.13)其中：sgn(Cj)为符号函数：sgn(cj)=七当。P加寸■sgn(勺)二一1,当Cj〈01寸这样一来，可得到初始基本可行解如下：Zj=sgn(Cj)(j=1,2，…,n)Xn丰1=bi(i=1,2，…,ill)□二0(j=1,2，…,n)Yj=0(j=1,2…,n+m)但是，只有当习=0时，才能够得到原来问题的解，故必须对上述问题进行修正，从而得到如下的线性规划问题：minG(力七-乙’二iajyn+iiyn5二3ksgn(cj)zj=cj(JminG(力七-乙’二iajyn+iiyn5二3ksgn(cj)zj=cj(J二A2:n)^2OVTJ?/-/刃方刀刀〃(X：,x2r:召：鼬y:,y2,・.《Gz、zi=O,彳=0,«=0)，则(才；，比匚J；)就是原二次规划问题的最优解。3.4约束非线性规划的求解方法3.4.1可行方向法考虑非线性规划问题(3.2),假设H是该问题的可行解，但不是最优解。为了进一步寻找最优解，在它的可行下降方向中选取其一个方向/并确定最佳步长人&使得FH十人址.A/+7)<f(jf)(3.15)反复进行这一过程，直到得到满足精度要求的可行解为止，这种方法称为可行方向法。可行方向法的主要特点是：因为迭代过程中所采用的搜索方向总为可行方向，所以产生的迭代点列｛F｝始终在可行域斤内，且LI标函数值不断的单调下降。可行方向法实际上是一类方法，最典型的是Zoutend