非线形规划讲稿

一、基本概念二、一维搜索由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的最优解就是整个可行域上的全局最优解。非线性规划却不然，有时求出的某个解虽是一部分可行域上的极值点，但并不一定是整个可行域上的全局最优解。对于非线性规划模型(NP)，可以采用迭代方法求它的最优解。迭代方法的基本思想是：从一个选定的初始点出发，按照某一特定的迭代规则产生一个点列，使得当是有穷点列时，其最后一个点是(NP)的最优解；当是无穷点列时，它有极限点，并且其极限点是(NP)的最优解。0°选取初始点，令。1°构造搜索方向，依照一定规则，构造在点处关于的可行下降方向作为搜索方向。2°寻求搜索步长。以为起点沿搜索方向寻求适当的步长，使目标函数值有某种意义的下降。3°求出下一个迭代点。按迭代格式（1）求出。若已满足某种终止条件，停止迭代。4°以代替，回到1°步。无约束问题2.1一维搜索方法当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有：（1）试探法（“成功—失败”，斐波那契法，0.618法等）；插值法（抛物线插值法，三次插值法等）；（3）微积分中的求根法（切线法，二分法等）。考虑一维极小化问题（2）若是区间上的下单峰函数，我们介绍通过不断地缩短的长度，来搜索得（2）的近似最优解的两个方法。为了缩短区间，逐步搜索得（2）的最优解的近似值，我们可以采用以下途径：在中任取两个关于是对称的点和（不妨设，并把它们叫做搜索点），计算和并比较它们的大小。对于单峰函数，若，则必有，因而是缩短了的单峰区间；若，则有，故是缩短了的单峰区间；若，则和都是缩短了的单峰。因此通过两个搜索点处目标函数值大小的比较，总可以获得缩短了的单峰区间。对于新的单峰区间重复上述做法，显然又可获得更短的单峰区间。如此进行，在单峰区间缩短到充分小时，我们可以取最后的搜索点作为（2）最优解的近似值。三、无约束极值无约束极值问题可表述为（5）求解问题（5）的迭代法大体上分为两种：一是用到函数的一阶导数或二阶导数，称为解析法。另一是仅用到函数值，称为直接法。2.3.1解析法2.3.1.1梯度法（最速下降法）对基本迭代格式（6）我们总是考虑从点出发沿哪一个方向，使目标函数下降得最快。微积分的知识告诉我们，点的负梯度方向，是从点出发使下降最快的方向。为此，称负梯度方向为在点处的最速下降方向。按基本迭代格式（6），每一轮从点出发沿最速下降方向作一维搜索，来建立求解无约束极值问题的方法，称之为最速下降法。这个方法的特点是，每轮的搜索方向都是目标函数在当前点下降最快的方向。同时，用或作为停止条件。其具体步骤如下：1°选取初始数据。选取初始点，给定终止误差，令。2°求梯度向量。计算，若，停止迭代，输出。否则，进行3°。3°构造负梯度方向。取.4°进行一维搜索。求，使得令转2°。例4用最速下降法求解无约束非线性规划问题其中，要求选取初始点，终止误差。解：（=1\*romani）编写M文件detaf.m如下function[f,df]=detaf(x);f=x(1)^2+25*x(2)^2;df(1)=2*x(1);df(2)=50*x(2);（=2\*romanii）编写M文件zuisu.mclcx=[2;2];[f0,g]=detaf(x);whilenorm(g)>0.000001p=-g'/norm(g);t=1.0;f=detaf(x+t*p);whilef>f0t=t/2;f=detaf(x+t*p);endx=x+t*p[f0,g]=detaf(x)end2.3.1.2Newton法考虑目标函数在点处的二次逼近式假定Hesse阵正定。由于正定，函数的稳定点是的最小点。为求此最小点，令，即可解得.对照基本迭代格式（1），可知从点出发沿搜索方向。并取步长即可得的最小点。通常，把方向叫做从点出发的Newton方向。从一初始点开始，每一轮从当前迭代点出发，沿Newton方向并取步长为1的求解方法，称之为Newton法。其具体步骤如下：1°选取初始数据。选取初始点，给定终止误差，令。2°求梯度向量。计算，若，停止迭代，输出。否则，进行3°。3°构造Newton方向。计算，取.4°求下一迭代点。令，转2°。例5用Newton法求解，选取，。解：（=1\*romani）编写M文件nwfun.m如下：function[f,df,d2f]=nwfun(x);f=x(1)^4+25*x(2)^4+x(1)^2*x(2)^2;df(1)=4*x(1)^3+2*x(1)*x(2)^2;df(2)=100*x(2)^3+2*x(1)^2*x(2);d2f(1,1)=12*x(1)^2+2*x(2)^2;d2f(1,2)=4*x(1)*x(2);d2f(2,1)=d2f(1,2);d2f(2,2)=300*x(2)^2+4*x(1)*x(2);（=2\*romanii）编写M文件：clcx=[2;2];[f0,g1,g2]=nwfun(x)whilenorm(g1)>0.00001%deadloop,fori=1:3p=-inv(g2)*g1',p=p/norm(p)t=1.0,f=detaf(x+t*p)whilef>f0t=t/2,f=detaf(x+t*p),endx=x+t*p[f0,g1,g2]=nwfun(x)end如果目标函数是非二次函数，一般地说，用Newton法通过有限轮迭代并不能保证可求得其最优解。Newton法的优点是收敛速度快；缺点是有时不好用而需采取改进措施，此外，当维数较高时，计算的工作量很大。§3约束极值问题带有约束条件的极值问题称为约束极值问题，也叫约束规划问题。求解约束极值问题要比求解无约束极值问题困难得多。为了简化其优化工作，可采用以下方法：将约束问题化为无约束问题；将非线性规划问题化为线性规划问题，以及能将复杂问题变换为较简单问题的其它方法。二次规划若某非线性规划的目标函数为自变量的二次函数，约束条件又全是线性的，就称这种规划为二次规划。Matlab中二次规划的数学模型可表述如下：这里是实对称矩矩阵，是列列向量，是是相应维数数的矩阵。Matlab中中求解二次次规划的命命令是[X,FVALL]=QQUADPPROG((H,f,,A,b,,Aeq,,beq,,LB,UUB,X00,OPTTIONSS)X的返回值是向量量，FVALL的返回值值是目标函函数在X处的值。（具具体细节可可以参看在在Matllab指令令中运行hhelpquaddprogg后的帮助助）。例8求解二次规划解编写如下程序：：h=[4,-44;-4,,8];f=[-6;--3];a=[1,1;;4,1]];b=[3;9]];[x,valuue]=qquadpprog((h,f,,a,b,,[],[[],zeeros((2,1)))求得。罚函数法利用罚函数法，可可将非线性性规划问题题的求解，转转化为求解解一系列无无约束极值值问题，因因而也称这这种方法为为序列无约约束最小化化技术，简简记为SSUMT(SeqquenttialUncoonstrraineedMiinimiizatiionTTechnniquee)。罚函数法求解非非线性规划划问题的思思想是，利利用问题中中的约束函函数作出适适当的罚函函数，由此此构造出带带参数的增增广目标函函数，把问问题转化为为无约束非非线性规划划问题。主主要有两种种形式，一一种叫外罚罚函数法，另另一种叫内内罚函数法法，下面介介绍外罚函函数法。考虑如下问题：：s.t.取一个充分大的的数，构造函函数（或这里，，，为适当的行向量量，Mattlab中中可以直接接利用和函数。）则则以增广目目标函数为为目标函数数的无约束束极值问题题的最优解也是原原问题的最最优解。例9求下列非非线性规划划解(=1\*romani)编写写M文件testt.mfunctioong==testt(x);;M=500000;f=x(1)^^2+x((2)^22+8;g=f-M*mmin(xx(1),,0)-MM*minn(x(22),0))-M*mmin(xx(1)^^2-x((2),00)....+M*abbs(-xx(1)--x(2))^2+22);(=2\*romanii)在MMatlaab命令窗窗口输入[x,y]=fmiinuncc('tesst',rrand((2,1))即可求得问题的的解。§4飞行管管理问题在约10，000m高空的的某边长1160kmm的正方形形区域内，经经常有若干干架飞机作作水平飞行行。区域内内每架飞机机的位置和和速度向量量均由计算算机记录其其数据，以以便进行飞飞行管理。当当一架欲进进入该区域域的飞机到到达区域边边缘时，记记录其数据据后，要立立即计算并并判断是否否会与区域域内的飞机机发生碰撞撞。如果会会碰撞，则则应计算如如何调整各各架（包括括新进入的的）飞机飞飞行的方向向角，以避避免碰撞。现现假定条件件如下：1）不碰撞的标准准为任意两两架飞机的的距离大于于8km;2）飞机飞行方向向角调整的的幅度不应应超过300度；3）所有飞机飞行行速度均为为每小时8800kmm;4）进入该区域的的飞机在到到达区域边边缘时，与与区域内飞飞机的距离离应在600km以上上；5）最多需考虑66架飞机；；6）不必考虑飞机机离开此区区域后的状状况。请你对这个避免免碰撞的飞飞行管理问问题建立数数学模型，列列出计算步步骤，对以以下数据进进行计算（方方向角误差差不超过0.01度），要要求飞机飞飞行方向角角调整的幅幅度尽量小小。设该区域4个顶顶点的座标标为(0,0))，(160,,0)，(1600,1600)，(0,1660)。记记录数据为为：飞机编号横座标纵座标方向角（度度）1150014402432855885236315001555220..541455550159513001550230新进入000522注：方向角指飞飞行方向与与轴正向的的夹角。试根据实际应用用背景对你你的模型进进行评价与与推广。提示：，，其中为飞机的总总架数，为为时刻第架飞飞机的坐标标，分别表表示第架飞飞机飞出正正方形区域域边界的时时刻。这里里，，；，，；其中为飞机的速速度，分别别为第架飞飞机的初始始方向角和和调整后的的方向角。令其中，则两架飞机不碰碰撞的条件件是。习题：某工厂向用户提提供发动