无约束优化算法

无约束优化算法无约束优化算法问题，是指优化问题的可行集为Rn，无约束的标准形式为：minf(x)f:RnTR最优性条件极小值点的一阶必要条件设f(x):RntR为连续可微函数，如果x*为局部极小值点，则X*为驻点，即梯度W(x*)=0。极小值的二阶必要条件设f(x):RntR为二阶连续可微函数，如果x*为局部极小值点，则x*为驻点，即梯度Vf(x*)=0，二阶膈sseV2f(x*)半正定。极小值点的二阶充分条件设f(x):RntR为二阶连续可微函数，如果梯度Vf(x*)=0，二阶hesseV2f(x*)正定，则x*为f的局部极小值点，x*GRn。以上三个定理为搜索最优点以及判断一个点是否为最优点的基本依据。经典的优化算法的停止条件为Vf(x*)=0，例如在程序中□Vf(x*)玉1x10-8，即在导数范数小于某特定误差限时停止。误差限较大，则算法迭代次数减少，计算时间缩短，但解得质量降低；误差限较小，则算法迭代次数增加，计算时间增加，但解的质量提高；误差限一般为1x10-8，可以根据实际情况设定合适的误差限。当然，还有极小值点的二阶必要条件与极小值点的二阶充分条件，对V2f(x*)的判断，由于目标函数比较复杂，二阶导数矩阵的计算量极大，所以一般算法都在迭代过程中对V2f(x(k))进行修正，得到V2f(x(k+d)，在修正的过程中始终保持V2f(x*)的正定性，以此方法解决极小值点的二阶条件问题。最速下降法2.1算法原理最速下降法是早期的优化算法，其理论根据函数的一阶泰勒展开：由f(x+ad)=f(x)+"(x)Td+o(a||d||)得到f(x+ad)-f(x)=aVf(x)Td+o(a||d||)根据下降要求f3+ad)-f3)<0故aVf(x)Td+o(a||d||)<0实际中要求aVf(x)Td<0根据上式选取合适的d，得aVf(x)Td<0。最速下降法取d=-Vf(x)。由于近似的有：f(x+ad)-f(x)=aVf(x)Td取d=-Vf(x)，则f(x+ad)-f(x)=-aVf(x)tVf(x)由Vf(x)tVf(x)>0知：-aVf(x)TVf(x)<0最速下降法有全局收敛性，并且是线性收敛的，算法比较简单。一般来说，在实际计算中，最速下降法在开始迭代时效果较好，有时能很快地找到最优解得附近，但是当局继续迭代时，常常发生扭摆现象，以致不能达到最优解。2.2算法步骤给定控制误差e>0。步骤1：取初始点x(0)，令k=0步骤2：计算g(k)=Vf(x(k))。步骤3：若||g(k)||<£，则x*=x(k)，停止计算；否则，令p(k)=-g(k)，由一维搜索步长匕，使得f(x(k)+ap(k))=minf(x(k)+ap(k))ka>0步骤4：令x(k+i)=x(k)+ap(k)，k=k+1，转步骤2。MATLAB中实现最速下降法的函数为fminunc，fminunc函数是求解无约束优化问题的主要函数，最速下降法仅仅是fminunc函数所使用的算法之一。语法：x=fminunc(fun,x0)x=fminunc(fun,x0,options)[x,fval]=fminunc(...)[x,fval,exitflag]=fminunc(...)[x,fval,exitflag,output]=fminunc(...)[x,fval,exitflag,output,grad]=fminunc(...)[x,fval,exitflag,output,grad,hessian]=fminunc(...)输入参数：fun：目标函数，一般用M文件形式给出x0:优化算法初始迭代点options:参数设置函数输出：x:最优点输出fval:最优点对应的函数值exitflag:函数结束信息output:函数基本信息，包括迭代次数、目标函数最大计算次数、使用的算法名称、计算规模。grad:最优点的导数hessian:最优点的二阶导数2.3程序示例MATLAB函数使用方法：目标函数程序BanaFun.m与BanaFunWithGrad.mfunctionf=BanaFun(x)(不含导数解析式)f=100*(x(2)-x(1)人2)人2+(1-x(1))A2function^f,g]=BanaFunWithGrad(x)(含导数解析式)f=100*(x(2)-x(1)a2)a2+(1-x(1))A2g=[100*(4*x(1)A3-4*x(1)*x(2))+2*x(1)-2;100*(2*x(2)-2*x(1)人2)]参数设置(steepdesc.m)options=optimset('LargeScale','off；HessUpdate；steepdesc','gradobj','on；'MaxFunEvals',250,'display','iter')'LargeScale','off':大规模计算模式 关闭'HessUpdate','steepdesc':Hess阵修正方式，采用最速下降法(不需要修正)'gradobj','on'：目标函数导数解析式，on使用，off不使用'MaxFunEvals',250:最大目标函数计算次数，250次'display','iter':显示迭代过程函数计算x=[—1.9,2]:初始迭代点[x,fval,exitflag,output]=fminunc(@BanaFunWithGrad,x,options)计算结果First-orderIterationFunc-countf(x)Step-sizeoptimality01267.621.23e+00312214.4160.000813405519295.836390.0009849313.43155.782920.0005673051.584185.731270.038797912.95245.680230.0005837361.596275.630810.036759912.57335.58190.0006002911.68365.534440.034948212.19425.487430.0006170091.6110455.441730.033324511.711515.396410.0006339251.6212545.352280.031858711.313605.308490.0006510741.6314635.265790.03052711115695.223380.0006684871.6416725.181970.029310610.717785.140820.0006861941.6418815.100590.028193710.419875.060580.0007042251.65First-orderIterationFunc-countf(x)Step-sizeoptimality20905.021440.027163510.121964.982490.0007226091.6622994.944330.02620959.89231054.906350.0007413761.67241084.869120.02532289.65

251144.832040.0007605541.68261174.795660.02449589.42271234.75940.0007801741.69281264.723810.0237229.2291324.688330.0008002671.7301354.653470.0229968.99311414.618710.0008208661.7321444.584530.0223138.79331504.550430.0008420021.71341534.51690.02166898.6351594.483430.0008637111.72361624.450490.02106018.42371684.41760.0008860291.73381714.385220.02048348.24391774.352890.0009089951.74First-orderIterationFunc-countf(x)Step-sizeoptimality401804.321030.0199368.07411864.28920.0009326491.75421894.257840.01941547.91431954.22650.0009570331.76441984.195590.01891947.75452044.16470.0009821941.77462074.134230.01844627.6472134.103770.001008181.78482164.073710.01799397.45492224.043640.001035051.79502254.013960.01756097.3512313.984270.001062841.8522343.954950.01714587.16532403.925610.001088861.8542433.894410.01810857.29552493.863210.001117641.82Solverstoppedprematurely.fminuncstoppedbecauseitexceededthefunctionevaluationlimit,options.MaxFunEvals=250(theselectedvalue).-0.96340.9372-0.96340.9372fval=3.8632exitflag=0output=iterations:56funcCount:250stepsize:0.0011firstorderopt:1.8155algorithm:'medium-scale:Quasi-Newtonlinesearch'message:[1x146char]从结果可见，在250次最大的目标函数计算次数内，算法没有到最优点[1,1]。将最大目标函数计算次数调高到2500次，则，计算结果：fminuncstoppedbecauseitexceededtheiterationlimit,options.MaxIter=400(thedefaultvalue).x=0.9770 0.9542fval=5.3808e-004exitflag=0output=iterations:401funcCount:1462stepsize:0.0142firstorderopt:0.0574algorithm:'medium-scale:Quasi-Newtonlinesearch'message:[1x131char]从以上两个算法的结果可以看出，最速下降法对bana函数不是十分有效。当目标函数不可微分或者导数求解复杂时，可以无需提供目标函数的导函数的解析形式，MATLAB可以使用差分的方法求导(下降方向)，对应的代码为options=optimset('LargeScale','off,'HessUpdate','steepdesc','MaxFunEvals',250);x=[-1.9,2];[x,fval,exitflag,output]=fminunc(@BanaFun,x,options)计算结果：fminuncstoppedbecauseitexceededthefunctionevaluationlimit,options.Max