最优化方法的Matlab实现（公式（完整版））

第九章最优化⽅法得Matlab实现

在⽣活与⼯作中,⼈们对于同⼀个问题往往会提出多个解决⽅案,并通过各⽅⾯得论证从中提取最佳⽅案。最优化⽅法就就是专门研究如何从多个⽅案中科学合理地提取出最佳⽅案得科学。由于优化问题⽆所不在,⽬前最优化⽅法得应⽤与研究已经深⼊到了⽣产与科研得各个领域,如⼟⽊⼯程、机械⼯程、化学⼯程、运输调度、⽣产控制、经济规划、经济管理等,并取得了显著得经济效益与社会效益。

⽤最优化⽅法解决最优化问题得技术称为最优化技术,它包含两个⽅⾯得内容:1)建⽴数学模型即⽤数学语⾔来描述最优化问题。模型中得数学关系式反映了最优化问题所要达到得⽬标与各种约束条件。

2)数学求解数学模型建好以后,选择合理得最优化⽅法进⾏求解。

最优化⽅法得发展很快,现在已经包含有多个分⽀,如线性规划、整数规划、⾮线性规划、动态规划、多⽬标规划等。9、1 概述

利⽤Matlab得优化⼯具箱,可以求解线性规划、⾮线性规划与多⽬标规划问题。具体⽽⾔,包括线性、⾮线性最⼩化,最⼤最⼩化,⼆次规划,半⽆限问题,线性、⾮线性⽅程(组)得求解,线性、⾮线性得最⼩⼆乘问题。另外,该⼯具箱还提供了线性、⾮线性最⼩化,⽅程求解,曲线拟合,⼆次规划等问题中⼤型课题得求解⽅法,为优化⽅法在⼯程中得实际应⽤提供了更⽅便快捷得途径。9.1.1 优化⼯具箱中得函数优化⼯具箱中得函数包括下⾯⼏类:1.最⼩化函数表9-1 最⼩化函数表

2.⽅程求解函数表9-2 ⽅程求解函数表

3.最⼩⼆乘(曲线拟合)函数

表9-3 最⼩⼆乘函数表

4.实⽤函数表9-4 实⽤函数表

5.⼤型⽅法得演⽰函数表9-5 ⼤型⽅法得演⽰函数表

6.中型⽅法得演⽰函数表9-6 中型⽅法得演⽰函数表

9.1.3 参数设置

利⽤optimset函数,可以创建与编辑参数结构;利⽤optimget函数,可以获得opti ons优化参数。● optimget函数

功能:获得options优化参数。语法:

val = optimget(options,'param')val = optimget(options,'param',default)

描述:

val = optimget(options,'param') 返回优化参数options中指定得参数得值。只需要⽤参数开头得字母来定义参数就⾏了。val = optimget(options,'param',default) 若options结构参数中没有定义指定参数,则返回缺省值。注意,这种形式得函数主要⽤于其它优化函数。举例:

1.下⾯得命令⾏将显⽰优化参数options返回到my_options结构中:

val = optimget(my_options,'Display')

2.下⾯得命令⾏返回显⽰优化参数options到my_options结构中(就象前⾯得例⼦⼀样),但如果显⽰参数没有定义,则返回值'final':optnew = optimget(my_options,'Display','final');参见:optimset● optimset函数

功能:创建或编辑优化选项参数结构。语法:

options = optimset('param1',value1,'param2',value2,、、、)optimset

options = optimset

options = optimset(optimfun)

options = optimset(oldopts,'param1',value1,、、、)options = optimset(oldopts,newopts)描述:

options = optimset('param1',value1,'param2',value2,、、、) 创建⼀个称为options得优化选项参数,其中指定得参数具有指定值。所有未指定得参

数都设置为空矩阵[](将参数设置为[]表⽰当options传递给优化函数时给参数赋缺省值)。赋值时只要输⼊参数前⾯得字母就⾏了。

optimset函数没有输⼊输出变量时,将显⽰⼀张完整得带有有效值得参数列表。

options = optimset (with no input arguments) 创建⼀个选项结构optio ns,其中所有得元素被设置为[]。

options = optimset(optimfun) 创建⼀个含有所有参数名与与优化函数opt imfun相关得缺省值得选项结构options。options = optimset(oldopts,'param1',value1,、、、) 创建⼀个oldopts 得拷贝,⽤指定得数值修改参数。

options = optimset(oldopts,newopts) 将已经存在得选项结构oldopts与新得选项结构newopts进⾏合并。newopts参数中得所有元素将覆盖oldopts 参数中得所有对应元素。举例:

1.下⾯得语句创建⼀个称为options得优化选项结构,其中显⽰参数设为'iter',TolFun参数设置为1e-8:

options = optimset('Display','iter','TolFun',1e-8)

2.下⾯得语句创建⼀个称为options得优化结构得拷贝,改变TolX参数

得值,将新值保存到optnew参数中:optnew = optimset(options,'TolX',1e-4);

3.下⾯得语句返回options优化结构,其中包含所有得参数名与与fminbnd函数相关得缺省值:options = optimset('fminbnd')

4.若只希望瞧到fminbnd函数得缺省值,只需要简单地键⼊下⾯得语句就⾏了:

optimset fminbnd

或者输⼊下⾯得命令,其效果与上⾯得相同:optimset('fminbnd')参见:optimget

9.1.4 模型输⼊时需要注意得问题

使⽤优化⼯具箱时,由于优化函数要求⽬标函数与约束条件满⾜⼀定得格式,所以需要⽤户在进⾏模型输⼊时注意以下⼏个问题:1、⽬标函数最⼩化

优化函数fminbnd、fminsearch、fminunc、fmincon、fgoalattain、fminmax与ls qnonlin都要求⽬标函数最⼩化,如果优化问题要求⽬标函数最⼤化,可以通过使该⽬标函数得负值最⼩化即-f(x)最⼩化来实现。近似地,对于quadprog函数提供-H与-f,对于linprog函数提供-f。2、约束⾮正

优化⼯具箱要求⾮线性不等式约束得形式为Ci

(x)≤0,通过对不等式取负可以达到

使⼤于零得约束形式变为⼩于零得不等式约束形式得⽬得,如Ci

(x)≥0形式得约束等价于- Ci (x)≤0;Ci

(x)≥b形式得约束等价于- Ci

(x)+b≤0。

3、避免使⽤全局变量9.1.5 (函数句柄)函数

MATLAB6、0中可以⽤函数进⾏函数调⽤。函数返回指定MATLAB函数得句柄,其调⽤格式为:handle = function

利⽤函数进⾏函数调⽤有下⾯⼏点好处:

●⽤句柄将⼀个函数传递给另⼀个函数;●减少定义函数得⽂件个数;●改进重复操作;

●保证函数计算得可靠性。

下⾯得例⼦为humps函数创建⼀个函数句柄,并将它指定为fhandle变量。fhandle = humps;

同样传递句柄给另⼀个函数,也将传递所有变量。本例将刚刚创建得函数句柄传递给fminbnd函数,然后在区间[0、3,1]上进⾏最⼩化。

x = fminbnd (humps, 0、3, 1)x =0、63709、2 最⼩化问题9.2.1 单变量最⼩化9.2.1、1 基本数学原理

本节讨论只有⼀个变量时得最⼩化问题,即⼀维搜索问题。该问题在某些情况下可以直接⽤于求解实际问题,但⼤多数情况下它就是作为多变量最优化⽅法得基础在应⽤,因为进⾏多变量最优化要⽤到⼀维搜索法。该问题得数学模型为:

其中,x,x1,与x2为标量,f(x)为函数,返回标量。该问题得搜索过程可⽤下式表达:

其中x k为本次迭代得值,d为搜索⽅向,α为搜索⽅向上得步长参数。所以⼀维搜索就就是要利⽤本次迭代得信息来构造下次迭代得条件。

求解单变量最优化问题得⽅法有很多种,根据⽬标函数就是否需要求导,可以分为两类,即直接法与间接法。直接法不需要对⽬标函数进⾏求导,⽽间接法则需要⽤到⽬标函数得导数。1.直接法

常⽤得⼀维直接法主要有消去法与近似法两种。

(1)消去法该法利⽤单峰函数具有得消去性质进⾏反复迭代,逐渐消去不包含极⼩点得区间,缩⼩搜索区间,直到搜索区间缩⼩到给定得允许精度为⽌。⼀种典型得消去法为黄⾦分割法(Golden Section Search)。黄⾦分割法得基本思想就是在单峰区间内适当插⼊两点,将区间分为三段,然后通过⽐较这两点函数值得⼤⼩来确定就是删去最左段还就是最右段,或同时删去左右两段保留中间段。重复该过程使区间⽆限缩⼩。插⼊点得位置放在区间得黄⾦分割点及其对称点上,所以该法称为黄⾦分割法。该法得优点就是算法简单,效率较⾼,稳定性好。

(2)多项式近似法该法⽤于⽬标函数⽐较复杂得情况。此时寻找⼀个与它近似得函数代替⽬标函数,并⽤近似函数得极⼩点作为原函数极⼩点得近似。常⽤得近似函数为⼆次与三次多项式。⼆次内插涉及到形如下式得⼆次函数数据拟合问题:

其中步长极值为:

然后只要利⽤三个梯度或函数⽅程组就可以确定系数a与b,从⽽可以确定α*。得到该值以后,进⾏搜索区间得收缩。在缩短得新区间中,重新安排三点求出下⼀次得近似极⼩点α*,如此迭代下去,直到满⾜终⽌准则为⽌。其迭代公式为:

其中

⼆次插值法得计算速度⽐黄⾦分割法得快,但就是对于⼀些强烈扭曲或可能多峰得函数,该法得收敛速度会变得很慢,甚⾄失败。2.间接法

间接法需要计算⽬标函数得导数,优点就是计算速度很快。常见得间接法包括⽜顿切线法、对分法、割线法与三次插值多项式近似法等。优化⼯具箱中⽤得较多得就是三次插值法。

三次插值得基本思想与⼆次插值得⼀致,它就是⽤四个已知点构造⼀个三次多项式P 3(x),⽤它逼近函数f(x),以P3

(x)得极⼩点作为f(x)得近似极⼩点。⼀般讲,三次插值

法⽐⼆次插值法得收敛速度要快些,但每次迭代需要计算两个导数值。三次插值法得迭代公式为

其中

如果函数得导数容易求得,⼀般来说⾸先考虑使⽤三次插值法,因为它具有较⾼得效率。对于只需要计算函数值得⽅法中,⼆次插值法就是⼀个很好得⽅法,它得收敛速度

较快,尤其在极⼩点所在区间较⼩时尤其如此。黄⾦分割法则就是⼀种⼗分稳定得⽅法,并且计算简单。由于以上原因,Matlab优化⼯具箱中使⽤得较多得⽅法就是⼆次插值法、三次插值法、⼆次、三次混合插值法与黄⾦分割法。9.2.1、2 相关函数介绍fminbnd

功能:找到固定区间内单变量函数得最⼩值。语法:

x = fminbnd(fun,x1,x2)x = fminbnd(fun,x1,x2,options)

x = fminbnd(fun,x1,x2,options,P1,P2,、、、)[x,fval] = fminbnd(、、、)[x,fval,exitflag] = fminbnd(、、、)[x,fval,exitflag,output] = fminbnd(、、、)描述:

fminbnd求取固定区间内单变量函数得最⼩值。

x = fminbnd(fun,x1,x2)返回区间{x1,x2}上fun参数描述得标量函数得最⼩值x。

x = fminbnd(fun,x1,x2,options)⽤options参数指定得优化参数进⾏最⼩化。

x = fminbnd(fun,x1,x2,options,P1,P2,、、、)提供另外得参数P1,P2等,传输给⽬标函数fun。如果没有设置options选项,则令options=[]。[x,fval] = fminbnd(、、、)返回解x处⽬标函数得值。

[x,fval,exitflag] = fminbnd(、、、)返回exitflag值描述fminbnd函数得退出条件。

[x,fval,exitflag,output] = fminbnd(、、、)返回包含优化信息得结构输出。变量:

函数得输⼊变量在表9-7中进⾏描述,输出变量在表9-8中描述。与fminbnd 函数相关得细节内容包含在fun,options,exitflag与output等参数中,如表9-10所⽰。表9-10 参数描述表

优化参数选项。您可以⽤optimset函数设置或改变这些参数得值。options参数有以下⼏个选项:

● Display –显⽰得⽔平。选择'off',不显⽰输出;选择'iter',显⽰每⼀步迭代过程

得输出;选择'final',显⽰最终结果。

● MaxFunEvals –函数评价得最⼤允许次数。MaxIter –最⼤允许迭代次数。TolX –x处得终⽌容限。描述退出条件:

>0 表⽰⽬标函数收敛于解x处。

0 表⽰已经达到函数评价或迭代得最⼤次数。<0 表⽰⽬标函数不收敛。该参数包含下列优化信息:output、iterations –迭代次数。output、algorithm –所采⽤得算法。output、funcCount –函数评价次数。算法:

fminbnd就是⼀个M⽂件。其算法基于黄⾦分割法与⼆次插值法。⽂献[1]中给出了实现同样算法得Fortran程序。局限性:

1.⽬标函数必须就是连续得。

2.fminbnd函数可能只给出局部最优解。

3.当问题得解位于区间边界上时,fminbnd函数得收敛速度常常很慢。此时,fmincon函数得计算速度更快,计算精度更⾼。4.fminbnd函数只⽤于实数变量。参见:

fminsearch, fmincon, fminunc, optimset, inline⽂献:

[1]Forsythe, G、E、, M、A、 Malcolm, and C、B、 Moler, puter Methods for Mathematical putations, Prentice Hall, 1976、9.2.1、3 应⽤实例

[例⼀]在区间(0,2π)上求函数sin(x)得最⼩值:x = fminbnd(sin,0,2*pi)x =4、7124

所以区间(0,2π)上函数sin(x)得最⼩值点位于x=4、7124处。最⼩值处得函数值为:y = sin(x)y =-1、0000

磁盘中该问题得M⽂件名为opt21_1、m。

[例三]对边长为3m得正⽅形铁板,在四个⾓处剪去相等得正⽅形以制成⽅形⽆盖⽔槽,问如何剪法使⽔槽得容积最⼤？假设剪去得正⽅形得边长为x,则⽔槽得容积为

现在要求在区间(0,1、5)上确定⼀个x,使最⼤化。因为优化⼯具箱中要求⽬标函数最⼩化,所以需要对⽬标函数进⾏转换,即要求最⼩化。

⾸先编写M⽂件opt21_3o、m:function f = myfun(x)f = -(3-2*x)、^2 * x;

然后调⽤fminbnd函数(磁盘中M⽂件名为opt21_3、m):x = fminbnd(opt21_3o,0,1、5)得到问题得解:x =0、5000

即剪掉得正⽅形得边长为0.5m时⽔槽得容积最⼤。⽔槽得最⼤容积计算:y = optim2(x)y =-2、0000

所以⽔槽得最⼤容积为2.0000m3。9.2.2 线性规划9.2.2、1 基本数学原理

线性规划就是处理线性⽬标函数与线性约束得⼀种较为成熟得⽅法,⽬前已经⼴泛应⽤于军事、经济、⼯业、农业、教育、商业与社会科学等许多⽅⾯。线性规划问题得标准形式就是:

或

写成矩阵形式为:

其中,0为n维列向量。

线性规划得标准形式要求⽬标函数最⼩化,约束条件取等式,变量⾮负。不符合这⼏个条件得线性模型要⾸先转化成标准形。线性规划得求解⽅法主要就是单纯形法(Simple Method),该法由Dantzig于1947

年提出,以后经过多次改进。单纯形法就是⼀种迭代算法,它从所有基本可⾏解得⼀个较⼩部分中通过迭代过程选出最优解。其迭代过程得⼀般描述为:

1.将线性规划化为典范形式,从⽽可以得到⼀个初始基本可⾏解x(0)(初始顶点),将它作为迭代过程得出发点,其⽬标值为z(x(0))。

2.寻找⼀个基本可⾏解x(1),使z(x(1))≤z(x(0))。⽅法就是通过消去法将产⽣x(0)得典范形式化为产⽣x(1)得典范形式。

3.继续寻找较好得基本可⾏解x(2),x(3),…,使⽬标函数值不断改进,即z(x(1))≥z(x(2))

≥z(x(3)) ≥…。当某个基本可⾏解再也不能被其它基本可⾏解改进时,它就就是所求得最优解。

Matlab优化⼯具箱中采⽤得就是投影法,它就是单纯形法得⼀种变种。9.2.2、2 相关函数介绍linprog函数

功能:求解线性规划问题。数学模型:

其中f,x,b,beq,lb与ub为向量,A与Aeq为矩阵。语法:

x = linprog(f,A,b,Aeq,beq)x = linprog(f,A,b,Aeq,beq,lb,ub)x = linprog(f,A,b,Aeq,beq,lb,ub,x0)x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)[x,fval] = linprog(、、、)[x,fval,exitflag] = linprog(、、、)[x,fval,exitflag,output] = linprog(、、、)[x,fval,exitflag,output,lambda] = linprog(、、、)描述:

x = linprog(f,A,b)求解问题 min f'*x,约束条件为A*x <= b。

x = linprog(f,A,b,Aeq,beq)求解上⾯得问题,但增加等式约束,即Aeq*x = beq。若没有不等式存在,则令A=[]、b=[]。

x = linprog(f,A,b,Aeq,beq,lb,ub)定义设计变量x得下界lb与上界ub,使得x始终在该范围内。若没有等式约束,令Aeq=[]、beq=[]。x = linprog(f,A,b,Aeq,beq,lb,ub,x0)设置初值为x0。该选项只适⽤于中型问题,缺省时⼤型算法将忽略初值。x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)⽤options指定得优化参数进⾏最⼩化。[x,fval] = linprog(、、、) 返回解x处得⽬标函数值fval。

[x,lambda,exitflag] = linprog(、、、)返回exitflag值,描述函数计算得退出条件。[x,lambda,exitflag,output] = linprog(、、、) 返回包含优化信息得输出变量output。

[x,fval,exitflag,output,lambda] = linprog(、、、) 将解x处得拉格朗⽇乘⼦返回到lambda参数中。变量:

lambda参数

lambda参数就是解x处得拉格朗⽇乘⼦。它有以下⼀些属性:lambda、lower –lambda得下界。lambda、upper –lambda得上界。lambda、ineqlin –lambda得线性不等式。lambda、eqlin –lambda得线性等式。其它参数意义同前。算法:

⼤型优化算法⼤型优化算法采⽤得就是LIPSOL法,该法在进⾏迭代计算之前⾸先要进⾏⼀系列得预处理。

中型优化算法 linprog函数使⽤得就是投影法,就象quadprog函数得算法⼀样。linprog函数使⽤得就是⼀种活动集⽅法,就是线性规划中单纯形法得变种。它通过求解另⼀个线性规划问题来找到初始可⾏解。诊断:

⼤型优化问题算法得第⼀步涉及到⼀些约束条件得预处理问题。有些问题可能导致linprog函数退出,并显⽰不可⾏得信息。在本例中,exitflag参数将被设为负值以表⽰优化失败。

若Aeq参数中某⾏得所有元素都为零,但Beq参数中对应得元素不为零,则显⽰以下退出信息:

Exiting due to infeasibility: an all zero row in the constraint matrix does not have a zero in corresponding right hand size entry、

若x得某⼀个元素没在界内,则给出以下退出信息:

Exiting due to infeasibility: objective f'*x is unbounded below、

若Aeq参数得某⼀⾏中只有⼀个⾮零值,则x中得相关值称为奇异变量。这⾥,x中该成分得值可以⽤Aeq与Beq算得。若算得得值与另⼀个约束条件相⽭盾,则给出以下退出信息:

Exiting due to infeasibility: Singleton variables in equalityconstraints are not feasible、

若奇异变量可以求解但其解超出上界或下界,则给出以下退出信息:Exiting due to infeasibility: singleton variables in the equality constraints are not within bounds、9.2.2、3 应⽤实例[ [例⼆]⽣产决策问题

某⼚⽣产甲⼄两种产品,已知制成⼀吨产品甲需⽤资源A 3吨,资源B 4m3;制成⼀吨产品⼄需⽤资源A 2吨,资源B 6m3,资源C 7个单位。若⼀吨产品甲与⼄得经济价值分别为7万元与5万元,三种资源得量分别为90吨、200m3与210个单位,试决定应⽣产这两种产品各多少吨才能使创造得总经济价值最⾼？令⽣产产品甲得数量为x1,⽣产产品⼄得数量为x2

。由题意可以建⽴下⾯得模型:

该模型中要求⽬标函数最⼤化,需要按照Matlab得要求进⾏转换,即⽬标函数为

⾸先输⼊下列系数:f = [-7;-5];A = [3 24 60 7];

b = [90; 200; 210];lb = zeros(2,1);然后调⽤linprog函数:

[x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb)x =14、000024、0000fval =-218、0000exitflag =1output =iterations: 5

cgiterations: 0algorithm: 'lipsol'lambda =

ineqlin: [3x1 double]eqlin: [0x1 double]upper: [2x1 double]lower: [2x1 double]

由上可知,⽣产甲种产品14吨、⼄种产品24吨可使创建得总经济价值最⾼。最⾼经济价值为218万元。exitflag=1表⽰过程正常收敛于解x处。

磁盘中本问题得M⽂件为opt22_2、m。[例三]投资问题

某单位有⼀批资⾦⽤于四个⼯程项⽬得投资,⽤于各⼯程项⽬时所得到得净收益(投⼊资⾦得百分⽐)如下表所⽰:表9-11 ⼯程项⽬收益表

由于某种原因,决定⽤于项⽬A得投资不⼤于其它各项投资之与;⽽⽤于项⽬B与C 得投资要⼤于项⽬D得投资。试确定使该单位收益最⼤得投资分配⽅案。