运筹学12非线性规划

无约束条件下单变量函数寻优一、消去法原理：逐步缩小搜索区间，直至极值点存在的区间达到允许的误差范围为止。设要寻求f(X)的极小值点为X*，起始搜索区间为a0,b0。x1、x2a0,b0，且x2x1，计算f(x1)和f(x2)，并且比较结果：,x1,x2均在x*的右侧，f(x2)f(x1)，去掉x1,b0，此时x*a0,x1x1,x2均在x*的左侧，f(x2)f(x1)，去掉a0,x2，此时x*x2,b0x1,x2均在x*的两侧，f(x2)f(x1)：a.去掉x1,b0，此时x*a0,x1b.去掉a0,x2，此时x*x2,b0,二、黄金分割法(0.618法)：是一种常用的消去法与对分法、Fibonacci法比较，具有计算次数少，过程简单的特点。,1、原理：,2、取点法则：,f(x2)f(x1)，取a1=a0,b1=x1x1=x2x2=b1-(b1-a1),f(x2)f(x1)，取a1=x2,b1=b0x1=a1+(b1-a1)x2=x1,计算n个点后，总缩短率为En=n-1，可得试点数n。,3、计算步骤：求函数f(x)的极值点,第一步：取初始区间a0,b0,若求f(x)的极小值点，则f(x2)f(x1)，取a1=a0,b1=x1x1=x2x2=b1-(b1-a1)f(x2)f(x1)，取a1=x2,b1=b0x1=a1+(b1-a1)x2=x1,若求f(x)的极大值点，则f(x2)f(x1)，取a1=a0,b1=x1x1=x2x2=b1-(b1-a1)f(x2)f(x1)，取a1=x2,b1=b0x1=a1+(b1-a1)x2=x1,第二步：求区间的缩短率,例求解f(x)=-18x2+72x+28的极大值点，0.1，起始搜索区间为0,3,解：用间接法：令f(x)=-36x+72=0，得驻点x=2又因为f(x)=-360，故x=2为f(x)的极大值点，fmax=100,用直接法中的黄金分割法：令n-1=，得n=1+(lg)/(lg)5.78442约6步即可，计算结果见下表：,2、算法步骤：设S=f(X)=f(x1,x2)，极值点存在的区间为x1*a1,b1，x2*a2,b2第一步：从X(0)=(x1(0),x2(0)T出发先固定x1=x1(0):求以x2为单变量的目标函数的极值点，得X(1)=(x1(0),x2(1)T，S(1)=f(X(1)再固定x2=x2(1):求以x1为单变量的目标函数的极值点，得X(2)=(x1(2),x2(1)T，S(2)=f(X(2)此时S(2)优于S(1)，且搜索区间缩短为x1*x1(2),b1，x2*x2(1),b2第二步：如此交替搜索，直至满足给定精度为止|f(X(k)-f(X(k-1)|或|S(k)-S(k-1)|,例求S=f(x)=x12+x22-x1x2-10 x1-4x2+60的极小值点，=0.01,解：设起始点X(0)=(0,0)T，用变量轮换法计算：先固定x1=x1(0)=0:则f(0,x2)=x22-4x2+60，寻优得x2(1)=2于是X(1)=(x1(0),x2(1)T=(0,2)T，S(1)=f(X(1)=56再固定x2=x2(1)=2:则f(x1,2)=x12-12x1+56，寻优得x1(2)=6于是X(2)=(x1(2),x2(1)T=(6,2)T，S(2)=f(X(2)=20如此交替搜索，直至满足给定精度=0.01为止|f(X(k)-f(X(k-1)|0.01或|S(k)-S(k-1)|0.01最后得极小点X*=(8,6)T，f(X*)=8,计算结果见下表：,缺点：很大程度上取决于目标函数性质。目标函数等高线的性质很重要。道路迂回曲折，多次变换方向，在极点附近，目标值改进更小，收敛速度慢。故不是一个有利方向。,三、梯度法(最速下降法):选择负梯度方向为搜索方向设求S=f(X)=f(x1,x2,xn)的极值点。1、原理：从起点X(0)出发，沿某个有利方向P(0)进行一维搜索，求得f(X)在P(0)方向近似极小点X(1)；从点X(1)出发，沿某个新有利方向P(1)进行一维搜索，求得f(X)在P(1)方向近似极小点X(2)；从点X(2)出发，照此进行下去，直至满足给定的精度为止|f(X(k)-f(X(k-1)|或|S(k)-S(k-1)|2、算法步骤：设求S=f(X)=f(x1,x2)的极值点。第一步：从给定起点X(0)出发,第二步：从点X(1)出发，照此进行下去，直至满足给定的精度为止|f(X(k+1)-f(X(k)|或|G(k)|,例求S=f(x)=x12+x22-x1x2-10 x1-4x2+60的极小值点，=0.1,解:,从点X(1)出发，照此进行下去，直至满足给定的精度=0.1为止|f(X(k+1)-f(X(k)|0.1或|G(k)|0.1,计算结果见下表：,缺点：搜索效果比变量轮换法快，但愈接近极值点，步长愈小，目标值改进愈小。当遇到强交互作用时，不是有效的方法;当遇到山脊时，会慢慢爬行。在远离极点时，收敛速度较快;在极点附近，收敛速度不快。,四、共轭梯度法:选择共轭方向为搜索方向问题的提出：在极值点附近，如何加快收敛速度，须对函数在极值点附近的性质进行研究。设有n维目标函数S=f(X)=f(x1,x2,xn),在极值点X*附近展开成泰勒级数：,特别：对二元正定二次函数，可证明：在极值点附近，其等高线可近似视为同心椭园族，而同心椭园族的任意两根平行切线的切点连线必通过椭园中心。,故：在极值点附近，沿搜索方向P(0)上巳得到一个切点X(1)，则只要得出通过极值点的连线方向P(1),在此方向上寻优,可一步直达极值点。而这个连线方向P(1)是上一次搜索方向P(0)的共轭方向。,共轭方向的定义：1、定义：设X,Y是n维向量空间En中两个向量，A为nn对称正定矩阵，若XTAY=0，则称向量X与Y对于矩阵A共轭。特例：若A=I，得XTY=0，则称向量X与Y正交。2、几何意义：共轭方向是通过极值点的方向。,寻优原理：设n元函数S=f(X)=f(x1,x2,xn),在极值点X*附近可用一个二次函数逼近,其中H为nn对称正定矩阵,特别：对二元二次函数S=f(X)=f(x1，x2)从某点X(0)出发,以P(0)方向搜索,使f(X)达到极小值点X(1),则:X(1)必为该点处等高线的切点,P(0)为切线方向，且点X(1)的梯度方向f(X(1)为该等高线的法线方向，这两个方向正交。,从另一点X(0)出发,仍以P(0)方向搜索,使f(X)达到另一个极小值点X(2),则:X(2)也必为该点处等高线的切点,P(0)为切线方向，且点X(2)的梯度方向f(X(2)为该等高线的法线方向，这两个方向正交。,故:对二元二次函数,只须搜索两个方向P(0)和P(1)就可达到极值点X*。一般:对n元二次函数,可用不超过n次搜索就可达到极值点X*。而n元非二次函数在极值点附近可用二次函数逼近。,寻优步骤：例求S=f(x)=x12+x22-x1x2-10 x1-4x2+60的极小值点。,解,对二元二次函数,只须两次搜索就可达到极值点X*,一般:对n元二次函数,可用不超过n次搜索就可达到极值点X*。而n元非二次函数在极值点附近可用二次函数逼近。,适用于一般目标函数的共轭梯度法：1、共轭方向的计算问题：须用到目标函数的海赛矩阵H(二阶偏导数矩阵)，若目标函数为二次函数时，H容易求出；若目标函数为高次或高维函数时，H难以求出，此时共轭方向难以求出。2、共轭方向的计算方法：F-R法，由Fletcher和Reeves提出，可避免海赛矩阵H的计算，方便地确定共轭方向，简单有效。,3、搜索过程：,从X(0)出发：,从X(1)出发：,从X(2)出发：,4、搜索方法:若目标函数为n元二次函数，则理论上最多经n次迭代可达极小点，实际由于舍入误差，须n次以上的迭代。若目标函数为n元非二次函数，但共轭方向只有n个，迭代n次以后应重新开始迭代，减少误差积累。一般，在开始阶段(二次型较弱)用一阶梯度法，接近极点(二次型较强)用共轭梯度法。,一般有：,例求S=f(x)=x12+x22-x1x2-10 x1-4x2+60的极小值点。,解:,有约束条件下多变量函数寻优一、具有等式约束的极值问题：1、消元法：n元非线性规划S=f(X)=f(x1,x2,xn)s.t.gk(X)=0,k=1,2,m,mn若可从m个s.t.中解出m个变量xi=h(xm+1,xm+2,xm),i=1,2,m,代入目标函数中消去m个变量，则问题变为一个求n-m个变量函数的无约束条件的极值问题。,2、拉格朗日(Lagrangian)乘子法：n元非线性规划S=f(X)=f(x1,x2,xn)s.t.gk(X)=0,k=1,2,m,则L(X,)有极值的必要条件为：,求出的解就是f(X)的驻点。,其中，拉格朗日乘子k的经济意义：影子价格-单位资源的目标增量S=f(X)=f(x1,x2,xn)s.t.gk(X)=bk,k=1,2,m,知k是约束式gk每变化一个单位,引起目标f值的变化率。,若目标f为效用函数极大化，b为预算约束，则*表示增加一元预算收入，可使最大效用增加的值。若目标f为费用函数极小化，b为产出水平，则*表示降低一元产出，可使最大费用减少的值-影子费用。,3、罚函数(代价函数)法：对n元非线性规划问题S=f(X)=f(x1,x2,xn)s.t.gk(X)=0,k=1,2,m,R(X,pk)有极值的必要条件为：,求出的解就是f(X)的驻点。,当s.t.不满足时,pk越大，则R值越大，此时罚项是一种惩罚。当s.t.满足时,不论pk多大(一般取),R(X,pk)=f(X),此时罚项无效。,二、具有不等式约束的极值问题：1、拉格朗日乘子法：引入松弛变量，将不等式约束化为等式约束。,2、库恩塔克(KuhnTuckers)条件法：适用范围：含有等式和不等式约束及变量非负的一般非线性规划。库塔条件：非线性规划,注：库塔条件是确定X*为极值点的必要条件，但不是充分条件。若为凸规划，则为充分必要条件。,由库塔条件有：,1.求出驻点：,则由得x1=1，x2=2，这与矛盾，舍去；,则由得x1=9/5，x2=4/5，代入得1=22/25，2=-24/250,矛盾,舍去；,则由,得x1=13/17，x2=18/17，1=0，2=4/17，用校验正确，得驻点X*=(13/17，18/17)T；,则由,得x1=9/13，x2=20/13，1=2/13，2=0，用校验不正确,舍去。,2.验证规划的凸性：,所以原规划为凸规划，从而X*=(13/17，18/17)T为最小值点，此时Z*=-1173/578。,3、罚函数法：把有s.t.问题化为无s.t.问题，依罚项形式不同有:外点法：从可行解域外部逐渐逼近极值点，初始点可任选。适用于含等式和不等式s.t.、非凸问题。,对T求无约束条