Matlab最优化计算方法ppt课件

《Matlab最优化计算方法ppt课件》由会员分享，可在线阅读，更多相关《Matlab最优化计算方法ppt课件（138页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,‹#›,为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益,,线性规划,最优化方法专题,无约束规划,非线性规划,课程目的,课程内容,2,、掌握用数学软件包求解线性规划问题。,1,、了解线性规划的基本内容。,3,、,实验作业。,2,、用数学软件包求解线性规划问题。,1,、两个引例。,问题一,：,任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为,800,和,900,，三种工件的数量分别为,400,、,60

2、0,和,500,，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,,,两个引例,解,,设在甲车床上加工工件,1,、,2,、,3,的数量分别为,x,1,、,x,2,、,x,3,，在乙车床上加工工件,1,、,2,、,3,的数量分别为,x,4,、,x,5,、,x,6,。可建立以下线性规划模型：,,解答,问题二：,,某厂生产甲、乙两种产品，已知制成一吨产品甲需用资源,A 3,吨资源,B 4m,3,；制成一吨产品乙需用资源,A 2,吨，资源,B 6m,3,，资源,C 7,个单位。若一吨产品甲和乙的经济价值分别为

3、,7,万元和,5,万元，三种资源的限制量分别为,90,吨、,200m,3,和,210,个单位。试应生产这两种产品各多少吨才能使创造的总经济价值最高？,解：,这是个最优化问题，其,目标,为经济价值最高，,约束条件,为三种资源的数量有限，,决策,为生产甲、乙产品的数量。令生产产品甲的数量为,x,1,，生产产品乙的数量为,x,2,。由题意可以建立如下的线性规划模型。,故目标函数为：,约束条件为：,问题,2,线性规划模型：,,解答,返 回,设置决策变量，它们体现解决问题的方案,。,小结,1,：建模的基本步骤,确定目标函数，它是决策变量的函数。,确定决策变量的取值范围，给出优化方向。,确定约束条件，它

4、们是含有决策变量的不等式或等式。,小结,2,：数学模型的共同结构,,1.,存在一组决策变量，称为决策变量，对它们可有非负要求；,,2.,存在一个以决策变量为自变量的目标函数，且它为线性函数；,,3.,存在一组约束条件，且每个条件都是由决策变量构成的线性不等式或等式；,,4.,结构要求出这样的变量组，或者说决策向量,X,，在满足约束条件和非负约束的同时，使相应的目标函数值达到最大或者最小。简言之，在一定条件下使目标函数优化。,,具有上述结构的数学模型为线性规划模型,线性规划数学模型,三要素：,决策变量、目标函数、约束条件,10,20,30,40,10,20,30,40,,,,,,,例,,,通过图

5、解法求下列线性规划问题的最优解。,,,,,,,,,,,,,max z=x,1,+3x,2,s.t. x,1,+ x,2,≤6,-x,1,+2x,2,≤8,x,1,≥0, x,2,≥0,,,,,,,,,,,可行域,目标函数等值线,最优解,6,4,-8,6,0,x,1,x,2,例 通过图解法求下列线性规划问题的最优解。,-x,1,+2x,2,=2,,x,1,-x,2,=2,,x,1,+x,2,=4,0 1 2 3 4,x,1,x,2,,G,4,3,2,1,F,E,H,A,B,C,D,I,,,,,,,,,,,,,,,,,,,,,,,,,,,,多重最优解,,,

6、,例 通过图解法求下列线性规划问题的最优解。,,,,,,,,,,,,,,,,,,,,,,,x,1,+2x,2,=4,x,1,+2x,2,=6,0 1 2 3 4 x,1,,x,1,=3,,X,2,,,3,,2,,1,,,,,-x,1,+2x,2,=0,,无界解,,,,,例 通过图解法求下列线性规划问题的最优解。,0 1 2 3 4 x,1,,x,1,=3,,X,2,,,3,,2,,1,,,,,-x,1,+2x,2,=0,,,,,,,,,,,,,,,,,,,,,,,,,

7、无界解,,,,例 通过图解法求下列线性规划问题的最优。,x,1,+x,2,=1,0 1 2 3 4 x,1,,X,2,,,3,,2,,1,,,,,-x,1,+2x,2,=4,,,,,,,,,,,,,,,,,,,无可行解,,,例 通过图解法求下列线性规划问题的最优。,总结：线性规划问题解的状况,,,,,,,,,唯一最优解,无穷多最优解,,,,,,,,无界解,无可行解,我们通常把无界解或无可行解统称为无最优解,c,1,x,1,0,c,2,x,2,0,C,t,= …… ..….,0=,……,c,

8、n,x,n,0,,并且,r(A)=m

9、 (,P,1,,,P,2,, … ,,P,n,),A,中线性独立的,m,列，构成该标准型的一个,基,，即基矩阵,,B,= (,P,1,,,P,2,, … ,,P,m,),，,|,B,|, 0,,P,1,,,,P,2,,,, … ,,P,m,,称为,基向量,与,基向量,对应的变量称为,基变量,，记为,,X,B,= (,x,1,,,x,2,, … ,,x,m,),T,，其余的变量称,非基变量,，记为,X,N,= (,x,m,+1,,,x,m,+2,, … ,,x,n,),T,,，,故有,,X,= (,X,B,,,X,N,),T,,,基,解、基可行解,线性规划的基矩阵、基变量、非基变量,,,

10、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,=,,,,,,,,,,,,,目标函数,约束条件,行列式≠,0,基矩阵,右边常数,例,:,0,0,0,0,3,2,0,2,0,0,0,1,0,1,0,x1,x2,x4,x3,0,0,1,3,0,0,3,2,1,=,目标函数,约束条件,行列式≠,0,基矩阵,X1,x2,x3,为基变量,,x4,为非基变量,可行解,满足约束条件和非负条件的解,X,称为可行解,.,基解,(,基本解,),令非基变量,X,N,=,0,，求得基变量,X,B,的值称为基本解,即,X,B,=,B,,1,,b,AX=b,令,A=(B,N),

11、 X=(,X,B ,,X,N,),,T,B,X,B,+,N,X,N,=b,令,,X,N,=,0,得,X,B,=,B,,1,b,,因此基解为,X=,（,B,,1,b,，,0,）,T,基本可行解,符合非负性要求的基解,，,称为,基本可行解，否则为基本非可行解,基本可行解,的非零分量个数,<,,m,,时,（,基本可行解中存在取零值的基变量），,称为退化基本可行,解,例,:,写出下列线性规划问题的基解，并判断是否为基可行解。,,,,基变量,x,1,、,x,2,、,x,3,，非基变量,x,4,、,x,5,、,x,6,基解,为（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）,

12、=,（,5,，,3,，,1,，,0,，,0,，,0,）,是基础可行解,，表示可行域的一个顶点。,目标函数值为：,z=20,,,,基变量,x,1,、,x,2,、,x,5,，非基变量,x,3,、,x,4,、,x,6,但不是基可行解,，不是一个顶点。,基解为（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）,=,（,6,，,3,，,0,，,0,，,-3,，,0,）,,,,基变量,x,1,、,x,2,、,x,6,，非基变量,x,3,、,x,4,、,x,5,基础解为（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）,=,（,3,，,4,，,0,，,0,，,

13、0,，,4,）,是基础可行解，表示可行域的一个顶点。,,目标函数值为：,z=18,,,,基变量,x,2,、,x,3,、,x,4,，非基变量,x,1,、,x,5,、,x,6,基础解为,（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）,=,（,0,，,21/2,，,27/2,，,-30,，,0,，,0,）,是基础解，但不是可行解。,约束方程的,解空间,,,基解,可行解,非可行解,基可,行解,,退化解,,1.3.2,线性规划标准型问题解的关系,1,、线性规划的标准型有特点（ ）。,,A,、右端项非零；,B,、目标求最大；,,C,、有等式或不等式约束；,D,、变量

14、均非负。,2,下面命题不正确的是（ ）。,,A,、线性规划的最优解是基本可行解；,,B,、基本可行解一定是基本解；,,C,、线性规划一定有可行解；,,D,、线性规划的最优值至多有一个。,,3,若某线性规划问题中，变量个数为,n,，基变量个数为,m,（,m < n,），则该问题基本可行解的最大数目为（ ）,① ② ③ ④,,,,,,4,若线性规划问题的最优解同时在可行域的两个顶点上达到，则最优解有,( ),①,无穷多个 ② 过这两点的整条直线 ③ 不可能发生 ④ 两个,5,当

15、线性规划问题的可行集非空时一定（）,A,包含原点,X=(0,0,,…,,0) B,有界,C,无界,D,是凸集,2.1,单纯形算法,,,基本思想：,从可行域的一个基本可行解,(,顶点,),出发，判别它是否已是最优解，如果不是，寻找下一个基本可行解，并使目标函数得到改进，如此迭代下去，直到找到最优解或判定问题无界为止。,2.1,单纯形思想举例,,max Z=1500x,1,+2500x,2,s.t. 3x,1,+2x,2,,65,2x,1,+ x,2,,40,,3x,2,75,x,1,,x,2,,0,,化成标准形：,max Z=1500x,1,+2500x,2,s.t.

16、 3x,1,+2x,2,+x,3,=65,2x,1,+ x,2,+,,x,4,=40,,3x,2,+,,x,5,=,,75,x,1,,x,2,,0,,2,1 0 0,1,0 1 0,0 3,0 0 1,A=,（,P,1,，,P,2,，,P,3,，,P,4,,，,P,5,）,例,P,3,，,P,4,，,P,5,线性无关，,x,3,, x,4,, x,5,是基变量，,x,1,, x,2,是非基变量。,,1 0 0,0 1 0,0 0 1,B=,（,P,3,，,P,4,,，

17、,P,5,）,用非基变量表示的方程,：,,Z= 1500x,1,+2500x,2,x,3,= 65 - 3x,1,- 2x,2,x,4,= 40 - 2x,1,- x,2,(I),x,5,= 75 - 3x,2,,令非基变量 （,x,1,,,,x,2,）,t,=,（,0,，,0,）,t,,得初始基可行解：,,x,(1),=(0,0,65,40,75),t,Z=0,,经济含义：不生产产品甲和乙，利润为零。,（,x,3,，,x,4,,，,x,5,）,分析：,,Z= 1500x,1,+2500x,2,分别增加单位产品甲、乙，目标函数分别增加,1500,、,2500,，即利润分别增加,1500,元、,

18、2500,元。,同时由目标函数可以看出增加单位产品乙（,x,2,）比甲（,x,1,,）对目标函数的贡献大,（最大检验数原则），,把非基变量,x,2,换成基变量，称,x,2,为,进基变量。同时为保证基变量的个数必须确定一个出基变量。,（,在选择出基变量时，只考虑,a,ij,是正的方程,）（最小比值原则）,,用非基变量表示的方程：,,,x,3,= 65,,- 2x,2,≥0,x,4,= 40,,- x,2,≥0,,(II),,x,2,＝,min,x,5,= 75 - 3x,2,≥0,,当,x,2,＝,25,时，,x,5,＝,0,，即,x,5,由原来的基变量变为现在的非基变量。,65/2, 40

19、/1 75/3,,确定了,进基变量,x,2,,，出基变量,x,5,,以后，用非基变量表示基变量得到新的方程组：,,Z= 62500+1500x,1,-(2500/3)x,5,x,3,= 15 - 3x,1,+,（,2/3,）,x,5,x,4,= 15 - 2x,1,+,（,1/3,）,x,5,(II),x,2,=,,25 -,（,-1/3,）,x,5,令新的非基变量（,,x,1,，,x,5,）,=,（,0,，,0,）,t,得到新的基本可行解：,x,(2),=(0,25,15,15, 0),t,Z=62500,经济含义：生产乙产品,25,个，获得利润,62500,元。,

20、,这个方案比前方案好，但是否是最优？,,分析：,Z= 62500+1500x,1,-(2500/3)x,5,非基变量,x,1,系数仍为正数，确定,x,1,为,进基变量。,在保证所有的变量非负的情况下，,确定,x,3,为出基变量。,得到新的基本可行解：,,x,(3),=(5,25,0,5, 0),t,Z= 70000-500x,3,-500x,5,由,Z,的表达式可以看出，该解已是最优解。,经济含义：生产甲产品生产,5,个乙产品,25,个，获得利润,70000,元。,c,1,x,1,0,c,2,x,2,0,C,t,= …… ..….,0=,……,c,n,x

21、,n,0,,并且,r(A)=m

22、 = [C,B,,C,N,],,s.t. [B , N] = b,,X,B,, X,N,,≥0,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,=,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,=,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,=,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,=,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,=,,,,,,,,,,,,,检验数

23、与最优检验,：,目标函数中,x,N,的系为 ，由于,x,N,= 0,，它对目标函数值没有直接影响，但却影响目标值的潜在变化。,检验向量为：,检验分量为：,,,,j,被称为,检验数,,,根据检验数取值情况可做如下讨论：,,,单纯形方法计算步骤,,,第一步：转换线性规划问题为标准型,,,构造初始单纯形表,第二步：根据换入规则决定进基变量,第三步：根据换出规则决定出基变量,第四步：构造新的单纯形表,第五步：返回第二步,例：用单纯形法求解线性规划问题,,,3,4,-1,2,0,0,b,θ,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,,,0,X,5,1,1

24、,1,1,1,0,25,,0,x,6,1,2,1,2,0,1,36,,σ ,Z,B,,3,4,-1,2,0,0,0,,,x,6,离基，,x,2,进基，,,,写出单纯形表,,,3,4,-1,2,0,0,b,θ,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,,,0,x,5,1,1,1,1,1,0,25,,0,x,6,1,2,1,2,0,1,36,,σ ,Z,B,,3,4,-1,2,0,0,0,,1,1/2,1/2,1,1/2,18,x,2,4,0,1/2,1/2,0,-1/2,7,0,1,-3,-2,-2,72,,,,x,5,离基，,x,1,进基,，,25/1=25,36/2=1

25、8,7/(1/2)=14,18/(1/2)=36,,,3,4,-1,2,0,0,b,θ,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,,,0,x,5,1/2,0,1/2,0,1,-1/2,7,,4,x,2,1/2,1,½,1,0,½,18,,σ ,Z,B,,1,0,-3,-2,0,-2,72,,1,1,2,-1,14,x,1,3,0,-1/2,-1,0,11,0,-4,-2,-1,86,得到最优解，最优解为：,X=(14,，,11,，,0,，,0,，,0,，,0),T,, max z=86,1.,线性规划的标准形式：,用单纯法求解时，常将标准形式化为：,2.,线性规划的基本算

26、法,——,单纯形法,线性规划的基本算法,——,单纯形法,引入松弛变量,x,3,, x,4,, x,5,,,将不等式化为等式, 即单纯形标准形:,用,MATLAB,优化工具箱解线性规划,min,z=cX,,,1,、模型：,命令：,x=linprog,（,c,，,A,，,b,）,,2,、模型,：,min,z=cX,,,,,,命令：,x=linprog,（,c,，,A,，,b,，,Aeq,beq,）,,注意：若没有不等式： 存在，则令,A=[ ],，,b=[ ].,3,、模型,：,min,z=cX,,,,,,VLB≤X≤VUB,,命令：,[1],x=linprog,（,c,，,

27、A,，,b,，,Aeq,beq, VLB,，,VUB,）,,[2],x=linprog,（,c,，,A,，,b,，,Aeq,beq, VLB,，,VUB, X,0,）,,注意：,[1],若没有等式约束,: ,,则令,Aeq=[ ], beq=[ ].,[2],其中,X,0,表示初始点,,4,、命令：,[x,fval]=linprog(…),返回最优解ｘ及ｘ处的目标函数值,fval.,,解 编写,M,文件如下：,c=[-0.4 -0.28 -0.32 -0.72 -0.64 -0.6];,A=[0.01 0.01 0.01 0.03 0.03 0

28、.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08];,b=[850;700;100;900];,Aeq=[]; beq=[];,vlb=[0;0;0;0;0;0]; vub=[];,[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub),,,解,:,编写,M,文件如下：,,c=[-7 -5];,A=[3 2; 4 6; 0 7];,b=[90;200;210];,Aeq=[];,beq=[];,vlb=[0,0];,vub=[inf,inf];,[x,fval]=linprog(c,A,b,Aeq,beq

29、,vlb,vub),,,问题,2,解答,例,3,问题一的解答,任务分配,问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为,800,和,900,，三种工件的数量分别为,400,、,600,和,500,，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,解,,设在甲车床上加工工件,1,、,2,、,3,的数量分别为,x1,、,x2,、,x3,，在乙车床上加工工件,1,、,2,、,3,的数量分别为,x4,、,x5,、,x6,。可建立以下线性规划模型：,S.t.,改写为：,例,3

30、,问题一的解答,,,问题,编写,M,文件如下,:,,f = [13 9 10 11 12 8];,A = [0.4 1.1 1 0 0 0,0 0 0 0.5 1.2 1.3];,b = [800; 900];,Aeq=[1 0 0 1 0 0,0 1 0 0 1 0,0 0 1 0 0 1];,beq=[400 600 500];,vlb = zeros(6,1);,vub=[];,[x,fval] = linprog(f,A,b,Aeq,beq,vlb,vub),,结果,:,x =,0.0000,600.0000,0.0000,400.0000,0.0000,500.0000,fval

31、=1.3800e+004,,,即在甲机床上加工,600,个工件,2,,在乙机床上加工,400,个工件,1,、,500,个工件,3,，可在满足条件的情况下使总加工费最小为,13800,。,结果为：,x =,14.0000,24.0000,fval =,,-218.0000,,,注：,有些实际问题可能会有一个,约束条件,：决策变量只能取整数，如,x,1,、,x,2,取整数。这类问题实际上是,整数线性规划,问题。如果把它当成一个线性规划来解，求得其最优解刚好是整数时，故它就是该整数规划的最优解。若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法

32、求解（如割平面法、分支定界法）。,实验作业,,某厂生产甲乙两种口味的饮料,,,每百箱甲饮料需用原料,6,千克,,,工人,10,名,,,可获利,10,万元,;,每百箱乙饮料需用原料,5,千克,,,工人,20,名,,,可获利,9,万元,.,今工厂共有原料,60,千克,,,工人,150,名,,,又由于其他条件所限甲饮料产量不超过,8,百箱,.,问如何安排生产计划,,,即两种饮料各生产多少使获利最大,.,进一步讨论,:,1),若投资,0.8,万元可增加原料,1,千克,,,问应否作这项投资,.,2),若每百箱甲饮料获利可增加,1,万元,,,问应否改变生产计划,.,返 回,无约,束非线性最,优化,课程目

33、的,课程内容,2,、掌握用数学软件包求解无约束最优化问题。,1,、了解无约,束非线性最,优化基本算法。,1,、无约,束非线性优,化基本思想及基本算法,。,4,、实验作业。,3,、用,MATLAB,求解无约,束非线性优,化问题。,2,、,MATLAB,优化工具箱简介,,无约,束非线性最,优化问题,求解无约,束非线性最,优化问题的的基本思想,*,无约,束非线性最,优化问题的基本算法,返回,标准形式：,求解无约,束非线性最,优化问题的基本思想,求解的基本思想,,(,以二元函数为例,),,,,,,,,,,,,,,,,,,,,,5,3,1,,,,,,,连续可微,多局部极小,,,,,唯一极小,(,全局极小

34、,),,,,,搜索过程,,,最优点,(1 1),初始点,(-1 1),,,,,,,,,,,,,,,,-1,1,4.00,,,-0.79,0.58,3.39,,,-0.53,0.23,2.60,,,-0.18,0.00,1.50,,,0.09,-0.03,0.98,,,0.37,0.11,0.47,,,0.59,0.33,0.20,,,0.80,0.63,0.05,,,0.95,0.90,0.003,,,0.99,0.99,1E-4,,,0.999,0.998,1E-5,,0.9997,0.9998,1E-8,返回,无约束优化问题,,,,,最优解类型,,全局最优解（,Global opti

35、mum,）,,局部最优解（,Local optimum,）,,现有基于导数的求解方法通常只能得到局部最优,解,。,,,无约束优化问题,,,最优化条件（,Optimality,Condition,）,,必要条件（,Necessary condition,）,充分条件（,,Sufficient condition,）,,,无约束优化问题,,步骤,1:,寻找稳定点,（,S,tationary,points,）：,步骤,2,： 检查稳定点是否满足充分条件：,基本思路,,,基本流程,,Example 1——,,Yanni Yang,2013,-2014 Spring,Semester,Slide 7,

36、基本思路,稳定点满足以下条件：,求解得到两个稳定点：,Hessian,矩阵：,,,Yanni Yang,2013,-2014 Spring,Semester,Slide 8,Example 2——,基本思路,,Yanni Yang,2013 -2014 Spring Semester,Slide 11,凸规划,无论初值取值，最优解唯一：,这样的函数被称为凸函数，求解凸函数最优解问题被称为凸规划,,Yanni Yang,2013 -2014 Spring Semester,Slide 12,,The slope of the function is increasing,！,多维函数判断准

37、则：,The Hessian matrix is positive semi-definite,！,凸规划,,,判别方法,,,Yanni Yang,2013 -2014 Spring Semester,Slide 13,,凸规划,,,性质定理,,求解,算法,思,路：,,基于局部搜索的原理求解,NLP,问题的方法很多，其原因是没有哪一种方法比别的方法更好。而且要想找到一个通用的求解,NLP,的局部搜索算法来处理所有的非线性模型是不现实的。它势必转换成穷举法。,常用的方法有二分法、线截法、不动点法和梯度法等。,求解,算法,1,.,二分法,,求解,算法,1,.,二分法,选择,a,、,b,，使得,f

38、(a)f(b)<0,且,x*∈[a, b],；,产生中点,m(m←(a+b)/2),；,如果,f(m)≠0,，则有,f(a)f(m)<0,或者,f(m)f(b)<0,，如果前者为,真,,,令,b=m,；否则令,a=m,；,如果,b-a<ε,则程序终止；否则执行步骤,2,。,求解,算法,2,.,弦截法,,,弦截法的算法过程如下：,过两点,(a,f(a)),(b,f(b)),作一直线，它与,x,轴有一个交点，记为,x1,.,如果,f(a)f(x1)<0,,过两点,(a,f(a)),(x1,f(x1)),作一直线，它与,x,轴的交点记为,x2,，否则过两点,(b,f(b)),(x1,f(x1)),作

39、一直线，它与,x,轴的交点记为,x2,；,如此下去，直到,|x,n,-x,n-1,|<,就,可以认为,x,n,为,f(x)=0,在区间,[a,b],上的一个根。,,,弦截法的算法过程如下：,X,k,的递推公式为：,,,,且,,在,MATLAB,中编程实现的弦截法的函数为：,Secant.,功能：用弦截法求函数在某个区间的一个零点。,调用格式：,root=Secant(f,a,b,eps).,,求解,算法,3.,不动点法,,求解,算法,3.,不动点法,给定,f(x)=0,的一个初始猜测点,s1；,作点,f(s1),处,的切线并找到切线与,x,轴的交点,s2,，然后将该点作为下一个猜测点；,以此类

40、推，,直到两个猜测点之间的距离充分小。,求解,算法,,练习：,,求解方程,f,(,x,)=,0,的解。,,,4,．最速下降法（共轭梯度法）算法步骤：,,最速下降法是一种最基本的算法，它在最优化方法中占有重要地位,.,最速下降法的优点是工作量小，存储变量较少,,,初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法,.,5,．,牛顿法算法步骤：,,如果,f,是对称正定矩阵,A,的二次函数，则用牛顿法经过,一次迭,代,就,可达到最优点,,,如不是二次函数，则牛顿法不能一步达到极值点,，但,由于这种函数在极值点附近和二次函数很近似,,

41、,因此牛顿法的,收敛,速度还是很快的,.,,牛顿法的收敛速度虽然较快，但要求,Hessian,矩阵要可逆,，,要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量,.,,Yanni Yang,2013,-2014 Spring,Semester,Slide 9,,,牛顿法（一维）,,,Yanni Yang,2013,-2014 Spring,Semester,Slide 10,初值不同，所得到的解可能,不同，无法保证所得解为全局最优解。,,,牛顿法（多维）,,,3,．拟牛顿法,,返回,分别,用,最速下降法、,牛顿法求解二次函数,,的极小值。初始点,。,用,Matlab,解无约束优化问题,,

42、其中（,3,）、（,4,）、（,5,）的等式右边可选用（,1,）或（,2,）的等式右边。,函数,fminbnd,的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。,常用格式如下：,（,1,）,x= fminbnd (,fun,x,1,,x,2,),（,2,）,x= fminbnd (,fun,x,1,,x,2,,，,options),（,3,）,[x,，,fval]= fminbnd,（,...,）,（,4,）,[x,，,fval,，,exitflag]= fminbnd,（,...,）,（,5,）,[x,，,fval,，,exitflag,，,outpu

43、t]= fminbnd,（,...,）,,主程序为,:,f=,'2*exp(-x).*sin(x)',;,fplot(f,[0,8]);,%,作图语句,,[xmin,ymin]=fminbnd (f, 0,8),f1=,'-2*exp(-x).*sin(x)',;,[xmax,ymax]=fminbnd (f1, 0,8),例,2,对边长为,3,米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大,？,解,先编写,M,文件,fminbndtest.m,如下,:,function f=myfun(x),f=,-,(3-2*x).^2*x;,主程序调用,fminb

44、nd:,[x,fval]=fminbnd(,',fminbndtest,',,0,1.5);,xmax=x,fmax=-fval,运算结果为,:,xmax = 0.5000,fmax =2.0000.,即剪掉的正方形的边长为,0.5,米时水槽的容积最大,,,最大容积为,2,立方米,.,,命令格式为,:,（,1,）,x= fminunc,（,fun,X,0,,）；或,x=fminsearch,（,fun,X,0,,）,（,2,）,x= fminunc,（,fun,X,0,,，,options,）；,或,x=fminsearch,（,fun,X,0,,，,options,）,（,3,）,[x,，,

45、fval]= fminunc,（,...,）；,或,[x,，,fval]= fminsearch,（,...,）,（,4,）,[x,，,fval,，,exitflag]= fminunc,（,...,）；,或,[x,，,fval,，,exitflag]= fminsearch,（,5,）,[x,，,fval,，,exitflag,，,output]= fminunc,（,...,）；,或,[x,，,fval,，,exitflag,，,output]= fminsearch,（,...,）,2,、多元函数无约束优化问题,标准型为,：,min F(X),[3] fminunc,为中型优化算法的步长

46、一维搜索提供了两种算法，,由,options,中参数,LineSearchType,控制：,LineSearchType=,’,quadcubic,’,(,缺省值,),，混合的二次和三,次多项式插值；,LineSearchType=,’,cubicpoly,’,，三次多项式插,使用,fminunc,和,fminsearch,可能会得到局部最优解,.,说明,:,fminsearch,是用单纯形法寻优,. fminunc,的算法见以下几点说明：,[1] fminunc,为无约束优化提供了大型优化和中型优化算法。由,options,中的参数,LargeScale,控制：,LargeScale=,’,

47、on,’,(,默认值,),,使用大型算法,LargeScale=,’,off,’,(,默认值,),,使用中型算法,[2] fminunc,为中型优化算法的搜索方向提供了,4,种算法，由,,options,中的参数,HessUpdate,控制：,HessUpdate=,’,bfgs,’,（默认值），拟牛顿法的,BFGS,公式；,HessUpdate=,’,dfp,’,，拟牛顿法的,DFP,公式；,HessUpdate=,’,steepdesc,’,，最速下降法,例,3,min f(x)=(4x,1,2,+2x,2,2,+4x,1,x,2,+2x,2,+1)*exp(x,1,),1,、编写,M-,

48、文件,fun1.m:,function f = fun1 (x),f = exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);,,2,、输入,M,文件,myprg3.m,如下,:,x,0,= [-1, 1];,x=fminunc(,',fun1,',,x,0,);,y=fun1(x),,3,、运行结果,:,x= 0.5000 -1.0000,y = 1.3029e-10,,,2.,画出,Rosenbrock,函数的等高线图,,,输入命令：,,contour(x,y,z,20),hold on,plot(-1.2,2,' o ')

49、;,text(-1.2,2,'start point'),plot(1,1,'o'),text(1,1,'solution'),3.,用,fminsearch,函数求解,输入命令,:,f='100*(x(2)-x(1)^2)^2+(1-x(1))^2';,[x,fval,exitflag,output]=fminsearch(f, [-1.2 2]),运行结果,:,x =1.0000 1.0000,fval =1.9151e-010,exitflag = 1,output =,iterations: 108,funcCount: 202,algorithm: 'Nelder-Mead s

50、implex direct search',4.,,用,fminunc,函数,(1),建立,M-,文件,fun1.m,,function,f=fun1(x),f=100*(x(2)-x(1)^2)^2+(1-x(1))^2,(2),求解主程序,oldoptions=optimset('fminunc'),options=optimset(oldoptions,'LargeScale','off'),,options11=optimset(options,'HessUpdate','dfp'),[x11,fval11,exitflag11,output11]=fminunc(',fun1,',

51、[-1.2 2],options11),Rosenbrock,函数不同算法的计算结果,可以看出，最速下降法的结果最差,.,因为最速下降法特别不适合于从一狭长通道到达最优解的情况,.,实验作业,有约束非,线性规划,,课程目的,课程内容,2,、掌握用数学软件求解优化问题。,1,、直观了解非线性规划的基本内容。,1,、非线性规划的基本理论。,3,、实验作业。,2,、用数学软件求解非线性规划。,有约束非,线性规划,,定义,,如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做,非线性规划问题,．,非线性,规划的基本概念,,一般形式,:,,,,,（,1,）,其中

52、 ， 是定义在,E,n,上的实值函数，简记,:,,其它情况,:,,求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式．,,,,定义,1,,把满足问题（,1,）中条件的解 称为,可行解,（或可行,点,），,所有可行点的集合称为,可行集,（或,可行域,）,．记为,D,．即,问题,(1),可简记为 ．,,,定义,2,,对于问题,(1),，设 ，若存在,,,使得对一切,，且 ，都有 ，则称,X,*,是,f(X),在,D,上的,局部极小值点,（,局部最优解,）,．特别地当

53、 时，若,，，则,称,X,*,是,f(X),在,D,上的,严格局部极小值,点,（,严格局部最优解,）,．,定义,3,对于问题,(1),,设,,,对任意的,,,都有 则称,X,*,是,f(X),在,D,上的,全局极小值点,（,全局最优解,）,．特别地当,时，若 ，则称,X,*,是,f(X),在,D,上的,严格全局极小值点,（,严格全局最优解,）,．,,罚函数法,,罚函数法,基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解．这类方法称为,序列无约束最小化方法,．简称为,SUMT,法,．,其一为,SUMT,外点法,，其二为

54、,SUMT,内点法,．,,其中,T(X,M),称为,罚函数,，,M,称为,罚因子,，,带,M,的项称为,罚项,，,这里的罚函数只对不满足约束条件的点实行惩罚,:,当 时，满足各 ，故罚项,=0,，不受惩罚．当 时，必有 的约束条件，故罚项,>0,，要受惩罚．,SUTM,外点法,,罚函数法的,缺点,是：每个近似最优解,X,k,往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着,M,k,的增大，可能导致错误．,,1,、,任意给定初始点,X,0,

55、，取,M,1,>1,，给定允许误差 ，令,k=1,；,2,、,求无约束极值问题 的最优解，设为,X,k,=X(M,k,),，即,；,3,、,若存在 ，使 ，则取,M,k,>M( ),令,k=k+1,返回（,2,），否则，停止迭代．得最优解,.,计算时也可将收敛性判别准则 改为,.,SUTM,外点法,(,罚函数法,),的,迭代步骤,SUTM,内点法（,障碍函数法,）,,内点法的迭代步骤,用,MATLAB,软件求解,,,其,输入格式,如下,:,,1. x=quadprog(H,C,A,b);,2. x=

56、quadprog(H,C,A,b,Aeq,beq);,3. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB);,4. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X,0,);,5. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X,0,,options);,6. [x,fval]=quaprog(...);,7. [x,fval,exitflag]=quaprog(...);,8. [x,fval,exitflag,output]=quaprog(...);,1,、二次规划,例,1,,min f(x,1,,x,2,

57、)=-2x,1,-6x,2,+x,1,2,-2x,1,x,2,+2x,2,2,s.t. x,1,+x,2,≤2,-x,1,+2x,2,≤2,x,1,≥0, x,2,≥0,1,、,写成标准形式,：,2,、,输入命令,：,,H=[1 -1; -1 2];,c=[-2 ;-6];A=[1 1; -1 2];b=[2;2];,Aeq=[];beq=[]; VLB=[0;0];VUB=[];,[x,z]=quadprog(H,c,A,b,Aeq,beq,VLB,VUB),3,、,运算结果,为：,,x =0.6667 1.3333 z = -8.2222,s.t.,,1.,首先建立,M,文件,f

58、un.m,,定义目标函数,F,（,X,）,:,function f=fun(X);,f=F(X);,2,、一般非线性规划,,其中,X,为,n,维变元向量，,G(X),与,Ceq(X),均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同,.,用,Matlab,求解上述问题，基本步骤分三步：,3.,建立主程序,.,非线性规划求解的函数是,fmincon,,,命令的基本格式如下：,,(1),x=,fmincon,(‘fun’,X,0,,A,b),,(2),x=,fmincon,(‘fun’,X,0,,A,b,Aeq,beq),,(3),x=,fmincon,(‘fun’,X,0,,A

59、,b, Aeq,beq,VLB,VUB),,(4),x=,fmincon,(‘fun’,X,0,,A,b,Aeq,beq,VLB,VUB,’nonlcon’),(5),x=,fmincon,(‘fun’,X,0,,A,b,Aeq,beq,VLB,VUB,’nonlcon’,options),,,,,,,(6),[x,fval]=,fmincon(...),,(7),[x,fval,exitflag]=,fmincon(...),(8)[x,fval,exitflag,output]=,fmincon(...),输出极值点,,M,文件,,迭代的初值,,参数说明,,变量上下限,,,注意：,,[1]

60、 fmincon,函数提供了大型优化算法和中型优化算法。默认时，若在,fun,函数中提供了梯度（,options,参数的,GradObj,设置为’,on’,），并且只有上下界存在或只有等式约束，,fmincon,函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。,,[2] fmincon,函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用,BFGS,法更新拉格朗日,Hessian,矩阵。,,[3] fmincon,函数可能会给出局部最优解，这与初值,X,0,的选取有关。,,,1,、,写成标准形式,：,,,,,,,,s.t.,,,,,2x,1,+3x,2,

61、6,s.t x,1,+4x,2,5,x,1,,x,2,0,例,2,,2,、,先建立,M-,文件,fun3.m:,,function f=fun3(x);,f=-x(1)-2*x(2)+(1/2)*x(1)^2+(1/2)*x(2)^2,3,、再建立主程序,youh2.m,：,,x0=[1;1];,A=[2 3 ;1 4]; b=[6;5];,Aeq=[];beq=[];,VLB=[0;0]; VUB=[];,[x,fval]=fmincon('fun3',x0,A,b,Aeq,beq,VLB,VUB),4,、,运算结果为：,,x = 0.7647 1.0588,fval =

62、 -2.0294,,1,．,先建立,M,文件,fun4.m,,定义目标函数,:,,function f=fun4(x);,f=exp(x(1)),*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);,x,1,+x,2,=0,s.t. 1.5+x,1,x,2,- x,1,- x,2,0,-x,1,x,2,–10,,0,,例,3,2,．再建立,M,文件,mycon.m,定义非线性约束：,,function [g,ceq]=mycon(x),g=[x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10];,,3,．主程序

63、为,:,x0=[-1;1];,A=[];b=[];,Aeq=[1 1];beq=[0];,vlb=[];vub=[];,[x,fval]=fmincon('fun4',x0,A,b,Aeq,beq,vlb,vub,'mycon'),3.,运算结果为,：,,,x = -1.2250 1.2250,fval = 1.8951,,,例,4,,,,,,,1,．先建立,M-,文件,fun.m,定义目标函数,:,function f=fun(x);,f=-2*x(1)-x(2);,,2,．再建立,M,文件,mycon2.m,定义非线性约束：,,function [g,ceq]=mycon2(x),g

64、=[x(1)^2+x(2)^2-25;x(1)^2-x(2)^2-7];,,3.,主程序,fxx.m,为,:,x0=[3;2.5];,VLB=[0 0];VUB=[5 10];,[x,fval,exitflag,output],=fmincon('fun',x0,[],[],[],[],VLB,VUB,'mycon2'),,4.,运算结果为,:,x =,4.0000,3.0000,fval =-11.0000,exitflag = 1,output =,iterations: 4,funcCount: 17,stepsize: 1,algorithm: [1x44 char],firstord

65、eropt: [],cgiterations: [],,Matlab,优化工具箱简介,1.MATLAB,求解优化问题的主要函数,2.,优化函数的输入变量,,使用优化函数或优化工具箱中其它优化函数时,,,输入变量见下表,:,3.,优化函数的输出变量下表,:,4,．控制参数,options,的设置,,(3),MaxIter,:,允许进行迭代的最大次数,,,取值为正整数,.,Options,中常用的几个参数的名称、含义、取值如下,:,(1),Display,:,显示水平,.,取值为,’,off,’,时,,,不显示输出,;,取值为,’,iter,’,时,,,显示每次迭代的信息,;,取值为,’,fina

66、l,’,时,,,显示最终结果,.,默认值为,’,final,’,.,(2),MaxFunEvals,:,允许进行函数评价的最大次数,,,取值为正整数,.,例：,opts=optimset(,‘,Display,’,,,’,iter,’,,,’,TolFun,’,,1e-8),,该语句创建一个称为,opts,的优化选项结构,,,其中显示参数设为,’,iter,’,, TolFun,参数设为,1e-8.,,控制参数,options,可以通过函数,optimset,创建或修改。命令的格式如下：,(1),options=optimset(,‘,optimfun,’,),,创建一个含有所有参数名,,,并与优化函数,optimfun,相关的默认值的选项结构,options.,（,2,）,options=optimset(,‘,param1,’,,value1,,’,param2,’,,value2,...),,创建一个名称为,options,的优化选项参数,,,其中指定的参数具有指定值,,,所有未指定的参数取默认值,.,(3),options=optimset(oldops,,‘,param1,’