第四讲无约束优化

无约束优化标准形式：RminnXfX其中1:RRnfRmaxnXfX=Rmin[]nXfX数学预备知识1梯度nR定义1设f(X)是定义在n维欧氏空间的上的可微函数，我们称12()()()(,,,)TnfXfXfXxxx为函数f(X)在点X处的梯度，记为▽f(X).1，梯度方向是函数在点X处增长最快的方向，负梯度方向是函数在点X处下降最快的方向.2，梯度的模是函数沿这一方向的变化率.3，满足梯度()0fX的点称为驻点，在区域内部极值点必为驻点，而驻点不一定是极值点.2黑塞（Hesse）矩阵定义2设f(X)是定义在nR上的二阶可微函数，则以其二阶偏导数为元素构成的下述n×n矩阵称为函数f(X)在点X的黑塞矩阵，记为H(X)或2()fX.当f(X)二阶偏导数连续时H(X)是对称矩阵.2222112122222212222212()()nnnnnnfffxxxxxfffHXfXxxxxxfffxxxxxx当f(X)是二次函数：1()2TTfXXAXBXC时，2()fXA即二次函数的黑塞矩阵与点X无关.例1，设43222123122313()234fXxxxxxxxxx求()fX2()fX和解32112322213321342()64642xxxxfXxxxxxxx212132123112222()21242462xxxxfXxxxx3多元函数的泰勒展开式定理1（多元函数的泰勒展开式）设f(X)是定义在nDR上的函数，且XD为一给定点，XD为任一点，那么1.若f(X)连续可微，则存在(0,1)，使()()()()TfXfXfXX其中();XXX2.若f(X)二次连续可微，则存在(0,1)使21()()()()()()()2TTTfXfXfXXXXXfXX其中();XXX3.若f(X)二次连续可微，则22()()()()1()()()()2TTTfXfXfXXXXXfXXXXX5.1.4正定矩阵、负定矩阵、半定矩阵、不定矩阵名称定义充要条件正定矩阵特征值都大于零的实对称矩阵半正定矩阵特征值都不小于零的实对称矩阵负定矩阵特征值都小于零的实对称矩阵半负定矩阵特征值都不大于零的实对称矩阵不定矩阵特征值既有大于零的又有小于零的实对称矩阵有两个奇数阶主子式，其中一个为正，另一个为负0,1,2,,iAindet0,0,1,2,,1iAAin0,,1,2,,0,iiAini为奇数为偶数0,det0,,1,2,,10,iiAAini为奇数为偶数5.2无约束最优化问题的解5.2.1无条件最优化问题的最优性条件1.用黑塞矩阵判断驻点的性质已知函数f(X)的驻点X，可以利用驻点处的黑塞矩阵来判断驻点的性质：（1）若2()fX是正定的，则驻点X是极小点；（2）若2()fX是负定的，则驻点X是极大点；（3）若2()fX是不定的，则驻点X不是极值点；（4）若2()fX是半定的，则驻点X可能是极值点；也可能不是极值点，视高阶导数情况而定.2极值点的必要条件和充分条件定义1对于问题（1），设nXR是任一给定点，P是是非零向量，若存在一个数0，使得对于任意(0,)都有()()fXPfX,则称P是f(X)在X处的下降方向.定理1设1:nnfRRXR在可微，如果存在向量nPR使得()0,().fXPPfXX则为在处的下降方向定理2（一阶必要条件）设f在点nXR可微，如果X是（1）的局部最优解，则必有()0fX＝称为驻点.定理3（二阶必要条件）设f在点nXR二次可微，X如果是（1）的局部最优解，则必有()0fX＝且黑塞矩阵是半正定的.定理4（二阶充分条件）设f在点nXR二次可微，如果()0fX＝且H（X）正定，则是问题（1）的X严格局部最优解定理5（充要条件）设f是定义在n维欧氏空间nR上的凸函数，nXR，则为全局极值点的充要条件是X()0fX＝.若f是严格凸函数，则全局极值点是唯一的.搜索算法概述搜索法的基本思想：首先给定目标函数的极小点的初始估计0X然后按照一定的规则产生一个点列kX这种规则通常就叫做算法希望点列的极限就是函数的极小值点下降算法一般步骤：⑴给定初始点0RnX（越靠近最优解越好）,令k=0；⑵假定已得到非最优解kX，则选定一个搜索方向kS使得沿kS方向函数值可下降，由定理1可知0kfXS；⑶由kX出发，以kS为方向，作射线kkXS（0）在此射线上选定步长k使得由此确定出点1kkkkXXSkkkkfXSfX；⑷检验所得的新点1kX是否最优解或近似解，检验的方法可因算法的不同而不同，例如对于预先给定的精度0，若满足：1kfX，或1kkfXfX或1kkXX则可认为1kX是近似最优解，停止迭代，得点*1kXX，否则令k=k+1进行（2）继续迭代。⑴给定初始点0RnX，允许误差0,令k=0；⑵计算kXf；⑶检验是否满足收敛性的判别准则：kXf，若满足，则停止迭代，得点kXX*，否则进行⑷；⑷令kkXfS，从kX出发，沿kS进行一维搜索，即求k,使得：kkkkkSXfSXf0min；⑸令kkkkSXX1，k=k+1返回⑵.最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法.5.2.3．最速下降法（共轭梯度法）算法步骤：5.2.4牛顿法算法步骤：如果f是对称正定矩阵A的二次函数，则用牛顿法，经过一次迭代就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收敛速度还是很快的.牛顿法的收敛速度虽然较快，但要求黑塞矩阵可逆，要计算二阶导数和逆矩阵，就加大了计算机的计算量和存储量.(1)选定初始点0RnX，给定允许误差0，令k=0；(2)求kXf,12kXf.检验：若kXf,则停止迭代,*kXX令.否则,转(3)；(3)令kkkXfXfS12][（牛顿方向）；(4)kkkSXX1,1kk,转回(2).3．拟牛顿法为克服牛顿法的缺点，同时保持较快收敛速度的优点，利用第k步和第k+1步得到的kX，1kX，)(kXf，)(1kXf，构造一个正定矩阵1kG近似代替)(2kXf,或用1kH近似代替12))((kXf，将牛顿方向改为：1kG1kS=-)(1kXf，1kS=-1kH)(1kXf从而得到下降方向.通常采用迭代法计算1kG，1kH，迭代公式为:BFGS（Boryden-Fletcher-Goldfarb-Shanno）公式TT1TT()()()()kkkkkkkkkkkkkffGxxGGGfxxGxTT1TT()()1()()kkkkkkkkkkkfHfxxHHfxfxTTT()()()kkkkkkkkxfHHfxfxDFP（Davidon-Fletcher-Powell）公式：TT1TT()()1()()kkkkkkkkkkkXGXffGGXffXTTT()()()kkkkkkkkfXGGXfXfTT1TT()()()()kkkkkkkkkkkkkXXHffHHHfXfHf计算时可置IH1（单位矩阵），对于给出的1X利用上面的公式进行递推.这种方法称为拟牛顿法.返回MATLAB优化工具箱简介1.MATLAB求解优化问题的主要函数类型模型基本函数名一元函数极小minF（x）s.t.x1xx2x=fminbnd(‘F’,x1,x2)无约束极小minF(X)X=fminunc(‘F’,X0)X=fminsearch(‘F’,X0)线性规划minXcTs.t.AX≤bX=linprog(c,A,b)二次规划min21xTHx+cTxs.t.Ax≤bX=quadprog(H,c,A,b)约束极小（非线性规划）minF(X)s.t.G(X)≤0X=fmincon(‘FG’,X0)达到目标问题minrs.t.F(x)-wr≤goalX=fgoalattain(‘F’,x,goal,w)极小极大问题minmax{Fi(x)}x{Fi(x)}s.t.G(x)≤0X=fminimax(‘FG’,x0)2.优化函数的输入变量使用优化函数或优化工具箱中其他优化函数时,输入变量见下表:变量描述调用函数f线性规划的目标函数f×X或二次规划的目标函数XT×H×X+f×X中线性项的系数向量linprog,quadprogfun非线性优化的目标函数.fun必须为行命令对象或M文件、嵌入函数、或MEX文件的名称fminbnd,fminsearch,fminunc,fmincon,lsqcurvefit,lsqnonli,fgoalattain,fminimaxH二次规划的目标函数XT×H×X+f×X中二次项的系数矩阵quadprogA,bA矩阵和b向量分别为线性不等式约束：bAX中的系数矩阵和右端向量linprog,quadprog,fgoalattain,fmincon,fminimaxAeq,beqAeq矩阵和beq向量分别为线性等式约束：beqXAeq中的系数矩阵和右端向量linprog,quadprog,fgoalattain,fmincon,fminimaxvlb,vubX的下限和上限向量：vlb≤X≤vublinprog,quadprog,fgoalattain,fmincon,fminimax,lsqcurvefit,lsqnonlinX0迭代初始点坐标除fminbnd外所有优化函数x1,x2函数最小化的区间fminbndoptions优化选项参数结构，定义用于优化函数的参数所有优化函数3.优化函数的输出变量见下表:变量描述调用函数x由优化函数求得的值.若exitflag0,则x为解;否则,x不是最终解,它只是迭代停止时优化过程的值所有优化函数fval解x处的目标函数值linprog,quadprog,fgoalattain,fmincon,fminimax,lsqcurvefit,lsqnonlin,fminbndexitflag描述退出条件:exitflag0,表示目标函数收敛于解x处exitflag=0,表示已达到函数评价或迭代的最大次数exitflag0,表示目标函数不收敛output包含优化结果信息的输出结构.Iterations:迭代次数Algorithm:所采用的算法FuncCount:函数评价次数所有优化函数4．控制参数选项的设置(3)MaxIter:允许进行迭代的最大次数,取值为正整数.选项中常用的几个参数的名称、含义、取值如下:(1)陈列:显示水平.取值为'off'时,不显示输出;取值为'iter'时,显示每次迭代的信息;取值为'final'时,显示最终结果.默认值为'final'.(2)MaxFunEvals:允许进行函数评价的最大次数,取值为正整数.例：opts=optimset('Display','iter','TolFun',1e-8)该语句创建一个称为选择的优化选项结构,其中显示参数设为'iter',Tol