mtlab无约束最优化问题.docx
《mtlab无约束最优化问题.docx》由会员分享，可在线阅读，更多相关《mtlab无约束最优化问题.docx（17页珍藏版）》请在冰点文库上搜索。
mtlab无约束最优化问题
第16章无约束最优化问题
单变量最小化
基本数学原理
本节讨论只有一个变量时的最小化问题，即一维搜索问题。
该问题在某些情况下可以直接用于求解实际问题，但大多数情况下它是作为多变量最优化方法的基础，因为进行多变量最优化要用到一维搜索算法。
该问题的数学模型为：
该问题的搜索过程可用下式表达：
求解单变量最优化问题的方法有很多种。
根据目标函数是否需要求导，可以分为两类，即直接法和间接法。
直接法不需要目标函数的导数，而间接法则需要用到目标函数的导数。
1.直接法
常用的一维直接法主要有消去法和近似法两种。
（1）消去法。
该法利用单峰函数具有的消去性质进行反复迭代，逐渐消去不包含极小
点的区间，缩小搜索区间，直到搜索区间缩小到给定的允许精度为止。
一种典型的消去法为黄金分割搜索法（GoIdenSectionSearch）。
黄金分割搜索法的基本思想是在单峰区间内适当插入两点，将区间分为3段，然后通过比较这两点函数值的大小来确定是删去最左段还是删去最右段，或是同时删去左、右两段保留中间段。
重复该过程使区间无限缩小。
插入点的位置放在区间的黄金分割点及其对称点上，所以该法称为黄金分割搜索法。
该法的优点是算法简单，效率较高，稳定性好。
（2）多项式近似法。
该法用于目标函数比较复杂的情况。
此时寻找一个与它近似的函
数来代替目标函数，并用近似函数的极小点作为原函数极小点的近似。
常用的近似函数为二次和三次多项式。
二次内插涉及到形如下式的二次函数数据拟合问题：
其中步长极值为
然后只要利用3个梯度或函数方程组就可以确定系数a和b,从而可以确定*。
得到该
值以后，进行搜索区间的收索。
在缩短的新区间中，重新安排3点求出下一次的近似极小点*，如此迭代下去，直到满足终止准则为止。
其迭代公式为
式中
二次插值法的计算速度比黄金分割搜索法的快，但是对于一些强烈扭曲或可能多峰的
函数，该法的收敛速度会变得很慢，甚至失败。
2．间接法
间接法需要计算目标函数导数，优点是计算速度很快。
常见的间接法包括牛顿切线
法、对分法、割线法和三次插值多项式近似法等。
优化工具箱中用得较多的是三次插值法。
三次插值的基本思想与二次插值的一致，它是用4个已知点构造一个三次多项式
P3（x），用它逼近函数f（x），以P3（x）的极小点作为数f（x）的近似极小点。
一般地讲，三次插值法比二次插值法的收敛速度要快些，但每次迭代需要计算两个导数值。
三次插值法的迭代公式为
如果函数的导数容易求得，一般来说首先考虑使用三次插值法，因为它具有较高的效率。
对于只需要计算函数值的方法中，二次插值法是一个很好的方法，它的收敛速度较快，在极小点所在区间较小时尤其如此。
黄金分割法则是一种十分稳定的方法，并且计算简单。
由于以上原因，优化工具箱中用得较多的方法是二次插值法、三次插值法以及二次、三次混合插值法和黄金分割法。
有关函数介绍
1.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,fvaI]=fminbnd（…）返回解x处目标函数的值。
[x,fvaI,exitfIag]=fminbnd（…）返回exitfIag值描述fminbnd函数的退出条件。
[x,fvaI,exitfIag,output]=fminbnd（…）返回包含优化信息的结构输出。
与fminbnd函数相关的细节内容包含在fun,options,exitfIag和output等参数中，如表16-1所示。
表16-1参数描述表
参数
描述
fun
需要最小化的目标函数。
fun函数需要输入标量参数x，返回x处的目标函数标量值f。
可以将fun函数指定为命令行，如
x=fminbnd（inline（sin（x*x）’x0）
同样，fun参数可以是一个包含函数名的字符串。
对应的函数可以是M文件、内部函数或MEX文件。
若fun=’ymfun’，则M文件函数必须有下面的形式
functionf=myfun（x）
f=…%计算x处的函数值
options
优化参数选项。
可以用optimset函数设置或该变这些参数的值.options参数有以下几个选项:
DispIay显示的水平。
选择‘off’，不显示输出；选择‘iter’，显示每一步迭代过程的输出；选择‘final’，显示最终结果
MaxFunEvaIs函数评价的最大允许次数
MaxIter最大允许次数
ToIXx处的终止容限
exitfIag
描述退出条件：
>0表示目标函数收敛于解x处
0表示已经达到函数评价或迭代的最大次数
<0表示目标函数不收敛
output
该函数包含下列优化信息：
迭代次数
所采用的算法
函数评价次数
注意：
目标函数必须是连续的；
fminbnd函数可能只给出局部最优解；
当问题的解位于区间边界上时，fminbnd函数的收敛速度很慢。
此时,fmincon函数的计算速度更快，计算精度更高；
fminbnd函数只用于实数变量。
2．应用实例
【例16-1】对边长为3m正方形铁板，在4个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大
假设剪去的正方行的边长为x，则水槽的容积为
现在要求在区间（0,）上确定一个x，f（x）最大化。
因为优化工具箱中要求目标
函数最小化，所以需要对目标函数进行转换，即要求“f（x）”最小化。
首先编写M文件:
functionf=op16_1（x）
f=-（3-2*x）.^2*x;
然后调用fminbnd函数，得到问题的解：
>>x=fminbnd（@op16_1,0,
x=
即剪掉的正方形的边长为时水槽的容积最大。
水槽的最大容积计算：
>>y=op16_1（x）
y=
所以水槽的最大容积为.
无约束非线性规划问题
基本数学原理
无约束最优化问题在实际应用中也比较常见，如工程中常见的参数反演问题。
另外，许多有约束最优化问题可以转化为无约束最优化问题进行求解。
求解无约束最优化问题的方法主要有两类，即直接搜索法（Directsearchmethod）和梯度法（Gradientmethod）。
直接搜索法适用于目标函数高度非线性，没有导数或导数很难计算的情况。
由于实际工作中很多问题都是非线性的，故直接搜索法不失为一种有效的解决办法。
常用的直接搜索法为单纯形法，此外还有Hook-Jeeves搜索法、PaveII共轭方向法等，其缺点是收敛速度慢。
在函数的导数可求的情况下，梯度法是一种更优的方法。
该方法利用函数的梯度（一阶导数）和Hess矩阵（二阶导数）构造算法，可以获得更快的收敛速度。
函数f（x）的负梯度方向
即反映了函数的最大下降方向。
当搜索方向取为负梯度方向时称为最速下降法。
当需要最小化的函数有一狭长的谷形值域时，该法的效率很低，如Rosenbrock函数
它的最小值解为x=[1,1]，最小值为f（x）=0。
图16-1是该函数的等值线图，图中还显示了从初值[，2]出发向最小值前进的路径。
迭代1000次以后终止，此时距最小值仍有相当长的距离。
图中的黑色区域是该法在谷的两侧不断进行“之”字形搜索形成的。
这种类型的函数又称为香蕉函数。
图16-1香蕉函数的等值线图及最速下降法的搜索路径
常见的梯度法有最速下降法、Newton法、Marquart法、共轭梯度法和拟牛顿法（Quasi-Newtonmethod）等。
在所有这些方法中，用的最多的是拟牛顿法，这些方法在每次迭代过程中建立曲率信息，构成下式得二次模型问题：
式中，Hess矩阵H为一正定对称矩阵，C为常数向量，b为常数。
对x求偏导数可以获得问题的最优解
拟牛顿法包括两个阶段，即确定搜索方向和一维搜索阶段
1.Hess矩阵的更新
牛顿法由于需要多次计算Hess矩阵，故计算量很大。
而拟牛顿法则通过构建一个Hess矩阵的近似矩阵来避开这个问题。
在优化工具箱中，通过将options参数HessUpdate设置为BFGS或DFP来决定搜索方向。
当Hess矩阵H始终保持正定时，搜索方向就总是保持为下降方向。
构建Hess矩阵的方法很多。
对于求解一般问题，Broyden,Fletcher,GoIdfarb和Shanno的方法（简称BFGS法）是最有效的。
BFGS法的计算公式为
式中
作为初值，H0可以设为任意对称正定矩阵。
另一个有名的构造近似Hess矩阵的方法是DFP（Daridon-Fletcher-PoweII）法。
该法的计算公式与BFGS法的形式一样，只是
梯度信息可以用解析方法得到，也可以用有限差分方法通过求偏导数得到。
在每一个主要的迭代过程中，在下式所示的方向上进行一维搜索：
.
图16-2演示了用拟牛顿法时Rosenbrock函数的求解路径。
可见，利用该法，只需要140迭代就可以达到最小值解，比前面利用最速下降法要快得多。
图16-2拟牛顿法的搜索路径----P202
2．一维搜索
工具箱中有两套方案进行一维搜索。
当梯度值可以直接得到时，用三次插值的方法进行一维搜索，当梯度值不能直接得到时，采用二次、三次混合插值法。
有关函数介绍
1．fminunc函数
用该函数求多变量无约束函数的最小值。
多变量无约束函数的数学模型为：
式中，x为一向量，f（x）为一函数，返回标量。
fminunc函数的调用格式如下：
fminunc给定初值，求多变量标量函数的最小值。
常用于无约束非线性最优化问题
x=fminunc（fun,x0）给定初值x0，求fun函数的局部极小点x。
x0可以是标量、向量或矩阵。
x=fminunc（fun,x0,options）用options参数中指定的优化参数进行最小化。
x=fminunc（fun,x0,options,P1,P2,…）将问题参数P1、P2等直接输给目标函数fun，将options参数设置为空矩阵，作为options参数的默认值。
[x,fvaI]=fminunc（…）将解x处目标函数的值返回到fvaI参数中。
[x,fvaI,exitfIag]=fminunc（…）返回exitfIag值，描述函数的输出条件。
[x,fvaI,exitfIag,output]=fminunc（…）返回包含优化信息的结构输出。
[x,fvaI,exitfIag,output,grad]=fminunc（…）将解x处fun函数的梯度值返回到grad参数中。
[x,fvaI,exitfIag,output,grad,hessian]=fminunc（…）将解x处目标函数的Hessian矩阵信息返回到hessian参数中。
表16-2中包括各输入输出变量的描述。
表16-2输入/输出变量描述表
变量
描述
fun
为目标函数，即需要最小化的目标函数。
Fun函数需要输入标量参数x,返回x处的目标函数标量值f。
可以将fun函数指定为命令行，如
x=fminbnd（inline（‘sin（x*x）’,x0）
同样，fun参数可以是一个包含函数名的字符串。
对应的函数可以是M文件、内部函数或MEX文件。
若fun=myfun,则M文件函数必须有下面的形式：
functionf=myfun（x）
f=…%计算x处的函数值
若fun函数的梯度可以算得，且设位on（用下式设定）、
则fun函数必须返回解x处的梯度向量g到第2个输出变量中去。
注意，当被调用的函数fun函数只需要一个输出变量时（如算法只需要目标函数的值而不需要其梯度值时），可以通过核对nargout的值来避免计算梯度值
function[f,g]=myfun（x）
f=…%计算x处的函数值
ifnargout>1%调用fun函数并要求有两个输出变量
g=…%计算x处的梯度值
end
若Hess矩阵也可以求得，并且设为on，即，
options=optimset（Hessian,on）
则fun函数必须返回解x处的Hess对称矩阵H到第3个输出变量中去。
注意，当被调用的fun函数只需要一个或两个输出变量时（如算法只需要目标函数得值f和梯度值g而不需要Hess矩阵H时），可以通过核对nargout的值以避免计算Hess矩阵
function[f,g,H]=myfun（x）
f=…%计算x处的函数值
ifnargout>1%调用fun函数并要求有两个输出变量
g=…%计算x处的梯度值
ifnargout>2
H=…%计算x处的Hess矩阵
options
优化参数选项。
可以通过optimset函数设置或改变这些参数。
其中有的参数适用于所有的优化算法，有的则只适用于大型优化问题，另外一些则只适用于中型问题
首先描述适用于大型问题的选项。
这仅仅是一个参考，因为使用大型问题算法有一些条件。
对于fminunc函数来说，必须提供梯度信息
LargeSeaIe当设为on时使用大型算法，若设为off则使用中型问题的算法
适用于大型和中型算法的参数：
Diagnostics打印最小化函数的诊断信息
DispIay显示水平。
选择off,不显示输出：
选择iter,显示每一步迭代过程的书橱；选择finaI,显示最终结果。
打印最小化函数的诊断信息
GradObj用户定义的目标函数的梯度。
对于大型问题此参数是必选的，对于中型问题则是可选项
MaxFunEvaIs函数评价的最大次数
MaxIter最大允许迭代次数
ToIFun函数值的终止容限
ToIXx处的终止容限
只用于大型算法的参数：
Hesian用户定义的目标函数的Hess矩阵
HessPattem用于有限差分的Hess矩阵的稀疏形式。
若不方便求fun函数的稀疏Hess矩阵H,可以用梯度的有限差分获得的H的稀疏结构（如非零值的位置等）得到近似的Hess矩阵H。
若连矩阵的稀疏结构都不知道，则可以将HessPattem设为密集矩阵，在每一次迭代过程中，都将进行密集矩阵的有限差分近似（这是默认摄制）。
这将非常麻烦，所以花一些力气得到Hess矩阵的稀疏结构还是值得的
MaxPCGIterPCG迭代的最大次数
PrecondBandWidthPCG前处理得上带宽，默认时为零。
对于有些问题，增加带宽可以减少迭代次数
ToIPCGPCG迭代的终止容限
TypicaIX典型x值
只适用于中型算法的参数：
DerivativeCheck对用户提供的导数和有限差分求出的导数进行对比
DiffMaxChange变量有限差分梯度的最大变化
DiffMinChange变量有限差分梯度的最小变化
LinSearchType一维搜索算法的选择
exitfIag
描述退出条件
>0表示目标函数收敛于解x处
0表示已经达到函数评价或迭代的最大次数
<0目标函数不收敛
output
该函数包含下列优化信息：
迭代次数
所采用的算法
函数评价次数
PCG迭代次数（只适用于大型规划问题）
最终步长的大小（只适用于中型问题）
一阶优化的度量；解x处梯度的范数
对规模不同的优化问题，fminunc函数使用不同的优化算法。
（1）大型优化算法
若用户在fun函数中提供梯度信息，则默认时函数将选择大型优化算法。
该算法是基
于内部映射牛顿的子空间置信域法。
计算中的每一次迭代都涉及到用PCG法求解大型线性系统得到的近似解。
（2）中型优化算法
此时fminunc函数的参数设置为off。
该算法采用的是基于二次和三
次混合插值一维搜索法的BFGS拟牛顿法。
该法通过BFGS公式来更新Hess矩阵。
通过将HessUpdate参数设置为dfp，可以用DFP公式求得Hess矩阵逆的近似。
通过将HessUpdate参数设置为steepdesc，可以用最速下降法来更新Hess矩阵。
但一般不建议使用最速下降法。
当设置为quadcubic时，默认一维搜索法为二次和三次混合插
值法。
将设置为cubicpoIy时，将采用三次插值法。
第2种方法需要的目标函数计算次数更少，但梯度的计算次数更多。
这样，如果提供了梯度信息，或者能较容易地算到，则三次插值法是更佳的选择。
注意：
1对于求解平方和问题，fminunc函数不是最好的选择，用IsqnonIin函数效果更佳。
2使用大型方法时，必须通过将设置为on来提供梯度信息，否则将给警告消息。
3目标函数必须是连续的。
fminunc函数有时会给出局部最优解。
4fminunc函数只对实数进行优化，即x必须为实数，而且f（x）必须返回实数。
当x为复数时，必须将它分解为实部和虚部。
5在使用大型算法时，用户必须在fun函数中提供梯度（options参数中GradObj属性必须设置为on）。
目前，若在fun函数中提供了解析梯度，则options参数DerivativeCheck不能用于大
型算法以比较解析梯度和有限差分梯度。
通过将options参数的MaxIter属性设置为0以用中型方法核对导数。
然后重新用大型方法求解问题。
【例16-2】将下列函数最小化
f（x）=3*x1^2+2*x1*x2+x2^2
解首先创建M文件myfun2m:
functionf=myfun（x）
f=3*x
（1）^2+2*x
（1）*x
（2）+x
（2）^2;%目标函数
然后调用fminunc函数求[1，1]附近myfun函数的最小值。
>>x0=[1,1];
>>[x,fva1]=fminunc（@myfun,x0）
Warning:
Gradientmustbeprovidedfortrust-regionmethod;
usingline-searchmethodinstead.
>InC:
\MATLAB6p5\toolbox\optim\atline211
Optimizationterminatedsuccessfully:
Searchdirectionlessthan2*
x=
*
%书上的结果为：
fva1=
经过迭代以后，返回解x和x处的函数值fva1。
如果用fminsearch函数则有与上不同的结果：
>>x0=[1,1];
>>[x,fval2]=fminsearch（@myfun,X0）
x=
*
fval2=
下面用提供的梯度g使函数最小化，修改M文件如下：
function[f,g]=myfun2（x）
f=3*x
（1）^2+2*x
（1）*x
（2）+x
（2）^2;%目标函数
ifnargout>1
g
（1）=6*x
（1）+2*x
（2）;
g
（2）=2*x
（1）+2*x
（2）;
end
下面通过将优化选项结构设置为on来得到梯度值。
>>clear
>>options=optimset（'GradObj','on'）;
>>x0=[1,1];
>>[x,fva2]=fminunc（@myfun2,x0,options）
Optimizationterminatedsuccessfully:
First-orderoptimalitylessthan,andnonegative/zerocurvaturedetected
x=
*
%书上结果为：
0
fva2=
%书上结果为：
经过数次迭代以后，返回解x和x处的函数值fva12。
2．fminsearch函数
利用fminsearch函数求解多变量无约束函数的最小值，其调用格式如下：
fminsearch求解多变量无约束函数的最小值。
该函数常用于无约束非线性最优化问题。
x=fminsearch（fun,x0）初值为x0，求fun函数的局部极小点x。
x0可以是标量、向量或矩阵。
x=fminsearch（fun,x0,options）用options参数指定的优化参数进行最小化。
x=fminsearch（fun,x0,options,p1,p2…）将问题参数p1,p2等直接输给目标函数fun，将options参数设置为空矩阵，作为options参数的默认值。
[x,fvaI]=fminsearch（…）将x处的目标函数返回到fvaI参数中。
[x,fvaI,exitfIag]=fminsearch（…）返回exitfIag值，描述函数的退出条件。
[x,fvaI,exitfIag,output]=fminsearch（…）返回包含优化信息的输出参数output。
fminsearch函数使用单纯形法进行计算。
对于求解二次以上的问题，fminsearch函数比fminunc函数有效。
但是，当问题为高度
非线性时，fminsearch函数更具有稳健性。
注意：
应用fminsearch函数可能会得到局部最优解。
fminserarch函数只对实数进行最小化，
即x必须由实数组成，f（x）函数必须返回实数。
如果x为复数，则必须将它分为实数部和虚数部两部分。
另外，fminsearch函数不适合求解平方和问题，用IsqnonIin函数更好一些。
【例16-3】使一维函数f（x）=sin（x）+3最小化。
首先创建M文件myfun3m:
functionf=myfun3（x）
f=sin（x）+3;%目标函数
然后调用fminsearch函数求2附近函数的最小值。
>>x=fminsearch（@myfun3,2）
x=
下面使用命令行使该函数最小化：
>>f=inline（'sin（x）+3'）;
>>x=fminsearch（f,2）
x=
升级会员 