非线性规划多维无约束优化.ppt

第六章 非线性规划 多维无约束非线性优化,概述,多维无约束优化问题是指在没有任何限制条件下寻求目标函数的极小点。其表达形式为：研究无约束优化问题的意义：在求解有约束优化问题的解时，有一大类解法是通过对约束条件的处理，把有约束问题变成一系列无约束的问题进行求解。研究无约束优化问题的解，也为研究约束优化问题的解法打下基础；在实际问题中，某些实际问题的数学模型本身也可能是一个无约束优化问题。在研究最优化问题时，通常首先要研究无约束问题的最优化问题。无约束优化问题求解的方法有多种，它们的主要不同点在于如何构造搜索方向。,最速下降法,基本思想最速下降法由法国数学家Cauchy于1847年首先提出。该算法在每次迭代中，沿最速下降方向（负梯度方向）进行搜索，每步沿负梯度方向取最优步长，因此这种方法称为最优梯度法算法特点最速下降法方法简单，只以一阶梯度的信息确定下一步的搜索方向，收敛速度慢；越是接近极值点，收敛越慢它是其它许多无约束、有约束最优化方法的基础。该法一般用于最优化开始的几步搜索。,最速下降法,算法分析,最速下降法,最速下降法由初始点向最优点迭代过程示意图,最速下降法,算法步骤,最速下降法,最速下降法的特点,牛顿法,概述为了寻找收敛速度快的无约束最优化方法，我们考虑在每次迭代时，用适当的二次函数去近似目标函数，并用迭代点指向近似二次函数极小点的方向来构造搜索方向，然后精确地求出近似二次函数的极小点，以该极小点作为的极小点的近似值这就是Newton切线法的基本思想，它是Newton切线法的推广,牛顿法,算法分析,牛顿法,迭代步骤,牛顿法,例1 用牛顿法求函数的极小点,牛顿法,牛顿法的收敛性质,阻尼牛顿法,算法思想 在牛顿法的实际操作中必须要选择一个具有较优目标值的初始点，但这往往是困难的。为了克服这个缺点，人们提出了“阻尼牛顿法”对此进行修正。,阻尼牛顿法,迭代步骤,阻尼牛顿法,收敛性质,阻尼牛顿法,例1 利用阻尼牛顿法求解非线性规划问题 取初始点，则,利用牛顿法和阻尼牛顿法求解二次型,共轭方向法,基本思想,共轭方向法,理论基础,共轭方向法,共轭的性质,共轭方向法,原理,共轭方向法,迭代步骤,共轭梯度法,基本思想,共轭梯度法,迭代步骤,共轭梯度法,FR公式,共轭梯度法,PRP公式和DM公式 与FR公式类似，我们还还可以采用Polak-Ribilere-Polyak(PRP)公式和Dixon-Myers公式。其形式分别为 FR、PRP、DM这三个公式对于二次型函数问题的求解效果相同，对于非二次型函数在数值计算上会有差异，结果也会有所不同。,共轭梯度法,例1 利用FR法求解无约束非线性规划问题,拟牛顿法,什么是拟牛顿法拟牛顿法的优点 仅需一阶导数（牛顿法需二阶导数）保持正定，使得方法具有下降性质每次迭代需 次乘法运算（牛顿法需 次乘法运算）搜索方向是相互共轭的，从而具有二次终止性,变尺度算法,概述变尺度法又称Davidon-Fletcher-Powell(DFP)算法，这是因为该算法在1959年由Davidon提出，后来经Fletcher和Powell解释并改进而得名。它是变尺度算法中提得最早的一个，该算法超线性收敛，对解多元函数的无约束极小是一个比较好的方法。该算法属于拟牛顿法的一种，变尺度法是求解无约束极值问题的一种有效方法，由于它避免了计算二阶导数矩阵及其求逆计算，又比梯度法的收敛速度快，特别是对高维问题具有显著的优越性，因而使变尺度法获得了很高的声誉，被称之为在算法上有“突破”。例如在1962年以前，由于原有各种算法计算耗时太多，因而求解非线性函数的极小值一般只能计算10个变量以下的问题，而应用了DFP法，可以在几分钟内计算出100个变量的函数极小值，有的问题只用半分钟即可解出。而相应的问题用其它算法求解，则要30分钟才能解出。变尺度法和共轭梯度法一样，都是为了克服梯度法收敛慢和Newton法计算工作量大的缺点而提出来的一种算法。,变尺度算法,基本思想,变尺度算法,DFP算法BFGS算法,变尺度算法,迭代步骤,变尺度算法,例1 利用变尺度算法求解无约束非线性规划问题,变尺度算法,变尺度算法,变尺度算法,变尺度算法和共轭梯度法的统一,多维无约束优化的求解函数fminunc,概述MATLAB优化工具箱中提供了多维无约束非线性优化的求解函数fminunc，在MATLAB的该求解函数中运用到了我们前面提到的多种算法，例如利用梯度信息或者Hessian矩阵信息的迭代算法，或者如果用户不提供梯度信息的话，可能使用到有限差分形式去估计相应值的方法。在下面函数使用过程中的算法和参数的设置时，将会重点讲述这些问题调用格式：x=fminunc(fun,x0)x=fminunc(fun,x0,options)x=fminunc(problem)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(.),多维无约束优化的求解函数fminunc,输入参数和输出参数,多维无约束优化的求解函数fminunc,多维无约束优化的求解函数fminunc,fminunc的输出参数主要包括x、fval、grad、hessian、exitflag、output，其中grad和hessian分别返回x处的梯度和Hessian矩阵信息。算法终止时状态指示结构变量exitflag取值代表的物理意义和输出参数output结构变量中所包含的信息分别如表所示：,多维无约束优化的求解函数fminunc,控制参数设置方法（打开word文档即可查看）命令详解 x=fminunc(fun,x0)从初始点x0开始寻找目标函数fun的局部极小点x，x0可以是标量、向量或矩阵x=fminunc(fun,x0,options)在求解问题的同时用options指定的优化参数进行目标函数的最小化x,fval=fminunc(.)返回最优解x处的目标函数值fval x,fval,exitflag=fminunc(.)在优化计算结束之时返回exitflag值，描述函数计算的退出条件x,fval,exitflag,output=fminunc(.)在优化计算结束之时返回返回结构变量output x,fval,exitflag,output,grad=fminunc(.)在优化计算结束之时返回解x处的梯度x,fval,exitflag,output,grad,hessian=fminunc(.)在优化计算结束之时返回解x处的Hessian矩阵,多维无约束优化的求解函数fminunc,fminunc可以根据用户选择的不同参数，选用不同的优化方法 大型优化算法 若用户在fun函数中提供梯度信息，则默认时函数将选择大型优化算法，该 算法是基于内部映射牛顿法的子空间置信域法。计算中的每一次迭代涉及用 PCG法求解大型线性系统得到的近似解。中型优化算法 当不使用大型规模算法，即通过optimset将options.LargeScale设置为off时，fminunc在优化过程中选用BFGS拟牛顿法，即通过BFGS校正来更新对目标函数 的Hessian矩阵的估计值。我们可以将参数HessUpdate设置为dfp使得fminunc采用DFP校正来更新对目标函数的Hessian矩阵的逆的估计；将HessUpdate设置为steepdesc同时将LargeScale设置为off，则此时使用最速下降法，但是一般不推荐使用最速下降法。在此强调一下，当使用大型规模算法时，必须在定义目标函数的M-函数文件中给出梯度向量的解析形式，同时设置控制参数GradObj的值为on，当没有设置控制参数LargeScale为off，且用户没有提供梯度向量的计算公式时，MATLAB将返回一个警告信息。,多维无约束优化的求解函数fminunc,fminunc在求解无约束最优化问题时的局限性 最优化问题的目标函数必须是连续的，且fminunc不能保证给出的是全局最优解，有时会给出局部最优解。fminunc只能对实数进行优化，即设计变量x的值只能为实数，且f(x)必须返回实数，当x为复数时，必须将其分解成实部和虚部。fminunc不适合用于求解目标函数为函数平方的问题，即若最优问题具有如下形式的目标函数：则最好使用lsqnonlin函数进行求解。,多维无约束优化的求解函数fminunc,例1 求解下述无约束最优化问题,多维无约束优化的求解函数fminunc,多维无约束优化的求解函数fminunc,例2 求解无约束最优化问题 其中n=1000 方法一：利用梯度向量和Hessian矩阵的精确计算公式,多维无约束优化的求解函数fminunc,多维无约束优化的求解函数fminunc,方法二：利用梯度向量和Hessian矩阵的稀疏形式,多维无约束优化的求解函数fminunc,多维无约束优化的求解函数fminunc,多维无约束优化的求解函数fminunc,例3 使用匿名函数调用求解无约束最优化问题 其中a=3，b=2，c=5,多维无约束优化的求解函数fminsearch,概述MATLAB中求解无约束优化问题还可以调用fminsearch函数，该函数和fminunc不同，因为fminsearch进行寻优的算法基于不使用梯度的单纯形法。其应用范围也是无约束的多维非线性规划问题。fminsearch和fminbnd类似，不同之处在于fminsearch解决的是多维函数的寻优问题，而且在fminsearch中指定的是初始点，而在fminbnd指定的是一个搜索的区间。fminsearch的寻优过程实际上就是在初始点附近找到最优化问题目标函数的一个局部极小点。由于函数fminseach的输入输出参数以及函数使用方法很多地方均和fminunc类似，故在此不再详细赘述，本节在进行一个简单的用法总结之后，给出fminsearch的几个应用实例。函数fminsearch的输入参数有fun,x0和options；输出参数有x、fval、exitflag和output；其可以设置的控制参数包括Display、FunValCheck、MaxFunEvals、MaxIter、OutputFcn、PlotFcns、TolFun、TolX，具体方法和fminunc类似，读者可以自行翻阅帮助信息。,多维无约束优化的求解函数fminsearch,调用方法x=fminsearch(fun,x0)从初始点x0开始寻找目标函数fun的局部极小点x，x0可以是标量、向量或矩阵。x=fminsearch(fun,x0,options)在求解问题的同时用options指定的优化参数进行目标函数的最小化，x,fval=fminsearch(.)返回最优解x处的目标函数值fvalx,fval,exitflag=fminsearch(.)在优化计算结束之时返回exitflag值，描述函数计算的退出条件。x,fval,exitflag,output=fminsearch(.)在优化计算结束之时返回返回结构变量output,多维无约束优化的求解函数fminsearch,例1 求解最优化问题,多维无约束优化的求解函数fminsearch,例2 求解下述最优化问题,多维无约束优化的求解函数fminsearch,例3 求解下述最优化问题,