第九章经典最优化方法

1第九章经典最优化方法9.1最优化的基本概念最优化方法是一门古老而又年青的学科。这门学科的源头可以追溯到17世纪法国数学家拉格朗日关于一个函数在一组等式约束条件下的极值问题（求解多元函数极值的Lagrange乘数法）。19世纪柯西引入了最速下降法求解非线性规划问题。直到20世纪三、四十年代最优化理论的研究才出现了重大进展，1939年前苏联的康托洛维奇提出了解决产品下料和运输问题的线性规划方法；1947年美国的丹奇格提出了求解线性规划的单纯形法，极大地推动了线性规划理论的发展。非线性规划理论的开创性工作是在1951年由库恩和塔克完成的，他们给出了非线性规划的最优性条件。随着计算机技术的发展，各种最优化算法应运而生。比较著名的有DFP和BFGS无约束变尺度法、HP广义乘子法和WHP约束变尺度法。最优化问题本质是一个求极值问题，几乎所有类型的优化问题都可概括为如下模型：给定一个集合（可行集）和该集合上的一个函数（目标函数），要计算此函数在集合上的极值。通常，人们按照可行集的性质对优化问题分类：如果可行集中的元素是有限的，则归结为“组合优化”或“网络规划”，如图论中最短路、最小费用最大流等；如果可行集是有限维空间中的一个连续子集，则归结为“线性或非线性规划”；如果可行集中的元素是依赖时间的决策序列，则归结为“动态规划”；如果可行集是无穷维空间中的连续子集，则归结为“最优控制”。线性规划与非线性规划是最优化方法中最基本、最重要的两类问题。一般来说，各优化分支有其相应的应用领域。线性规划、网络规划、动态规划通常用于管理与决策科学；最优控制常用于控制工程；非线性规划更多地用于工程优化设计。前面提到的算法是最优化的基本方法，它们简单易行，对于性态优良的一般函数，优化效果较好。但这些经典的方法是以传统微积分为基础的，不可避免地带有某种局限性，主要表现为：①大多数传统优化方法仅能计算目标函数的局部最优点，不能保证找到全局最优解。对于多峰值函数，这些方法往往由于过分追求“下降”而陷于局部最优解；②许多传统优化方法对目标函数的光滑性、凹凸性等有较高的要求，对于离散型函数、随机型函数基本上无能为力。二十世纪六、七十年代以来，人们将人工智能技术和生物进化机理引入最优化方法，逐渐形成了一批完全不同于传统优化方法、令人耳目一新的现代优化方2法。如模拟退火、神经网络、进化计算、模糊逻辑等，其中进化计算中的遗传算法以其良好的全局搜索性成为现代优化算法中最受关注的算法之一，已被广泛应用于函数优化、组合优化、自动控制、生产调度、图像与信号处理、机器人和人工生命等领域。9.1.1预备知识1、梯度定义9.1对n元可微函数nxxxfXf,,,21，向量nxfxfxf,,,21称为f在X处的梯度，记为Xf或Xgradf，称为梯度算子或Hamilton算子。从几何上讲，Xf的方向是f在X处上升最快的方向，Xf的模是f在X处上升最快的速率。若0Xf，则函数曲面在X处的切平面是水平的。2、二阶导数矩阵定义9.2设n元函数nxxxfXf,,,21具有二阶连续偏导数，则f的所有二阶偏导数构成的矩阵''''2''1''2''22''21''1''12''11nnnnnnfffffffff称为f在X处的二阶导数矩阵或海色（Hessain）矩阵，记为Xf2。显然，Xf2是一个对称矩阵。在几何上，Xf2反映了函数曲面的弯曲方向。若02Xf（正定），则函数曲面向上弯曲（凹）；若02Xf（负定），则函数曲面向下弯曲（凸）。例9.1设A为n阶对称矩阵，b、X为n元列向量，c为标量，对二次函数cXbAXXXfTT21求梯度Xf、Hessain矩阵Xf2。解：可将算子、2理解为对向量函数的一阶、二阶导数，易得bAXXfAXf23、n元函数的二阶Taylor展式3一元函数的Taylor展式：nnnRxnxfxxfxxfxfxxf!)(!2)()()()(0)(20000其中10,)!1()(10)1(nnnxnxxfR二元函数的Taylor展式：),(),(),(000000yxfyyxxyxfyyxxfnnRyxfyyxxnyxfyyxx),(!1),(!2100002其中10),,()!1(1001yyxxfyyxxnRnn二元函数的二阶Taylor展式：yyxfyxyxfxyxfyyxxf),(),(),(),(0000000022002200200220022),(),(),(),(!21Ryyxfyxyyxfxyyxyxfyxxyxfx若引入矩阵记号,,,,,0000XXXyxXyxXTT202020220202000)()()()()(,)(,)(yXfxyXfyxXfxXfXfAyXfxXfXfbT则2020021RXXXXXfXfXfTT2021RXAXXbXfTTn元函数的二阶Taylor展式与二元函数的二阶Taylor展式形式类似。4、凸集与凸函数定义9.3设nRS，若S中任两点的连线都属于S，即对任意1X、SX2，均有)10()1(21SXX，则称S为一个凸集。定义9.4设)(Xf为定义在凸集S上的函数，若对任意1X、SX2，均有)10()1()1(2121XfXfXXf，则称)(Xf为S上的凸函4数。若上式改为严格不等式，则称)(Xf为S上的严格凸函数。定理9.1（一阶判别条件）一阶可微函数)(Xf在凸集S上为凸函数的充要条件是：对任意1X、SX2，均有12112XXXfXfXfT。定理9.2（二阶判别条件）二阶连续可微函数)(Xf在凸集S上为凸函数的充要条件是：对任意SX，Xf2半正定。)(Xf为严格凸函数的充要条件是Xf2正定。9.1.2最优化的基本概念最优化问题的数学模型为),,2,1(0),,,()(..),,,()(min2121mixxxgxgtsxxxfxfniin),,,(21nxxxf称为目标函数，),,,(21nixxxg称为约束函数。当),,,(21nxxxf和),,,(21nixxxg均为线性时，称之为线性规划（LP）；当),,,(21nxxxf和),,,(21nixxxg至少有一个为非线性时，称之为非线性规划（NLP）。对非线性规划，如果变量x的取值范围没有限制，称之为无条件极值或无约束最优化，否则称之为条件极值或约束最优化。求解最优化问题最常用的方法是迭代法。迭代法的基本思想是：从最优点的一个初始值0x出发，按一定迭代法则产生点序列),2,1(kxk，使目标函数值kxf逐步减小。当序列kx是有限点列时，其最后一点即为最优解；当kx是无穷点列时，其极限点*x即为最优解。对于迭代法有下列四个问题：①如何由kx产生1kx，即迭代格式或算法结构；②迭代何时中止，即停止准则或最优性条件；③迭代产生的序列是否收敛于最优解*x，即收敛性问题；④收敛算法的收敛速度问题。1、最优性条件由微积分知识不难得出下列最优性条件。定理9.3（一阶必要条件）设Xf可微，若nRX*为Xf的一个极小点，则0*Xf。①本定理的几何意义是，函数在*X处取极小值的必要条件是该函数曲面在*X处的切平面是水平的；5②梯度为零的点可能是极小或极大点，也可能是鞍点即既非极小也非极大的点。定理9.4（二阶充要条件）设Xf二阶连续可微，若0*Xf，且*X处的二阶导数矩阵*2Xf正定，则*X为极小点。本定理的几何意义是，*X为极小点的充要条件是函数曲面在*X处有水平切平面且向上弯曲。定理9.5（凸函数的最优性条件）设Xf为二阶连续可微的凸函数，且0*Xf，则*X为全局极小点。2、算法结构根据最优条件，从理论上讲，可以先解非线性方程组0Xf，然后再判定其解的二阶导数矩阵Xf2是否正定，即可求出函数的最优解。但由于解非线性方程组和判定矩阵是否正定是极为复杂和困难的，其难度甚至已超过优化问题本身。因此，上述想法在实际上是不可行的。最优化中大多采用逐步下降算法，其基本思想是：根据当前解选择一个适当的下降方向，沿此方向下降到一个合适位置从而得到新解，然后判断新解是否为最优解；若是，则停止，否则重复上述过程。经过有限次迭代后，在一定条件下即可得出近似最优解。下降算法的迭代格式为：kkkkptXX1，其中kX是第k次迭代点，kp是第k次迭代方向，)0(kktt是第k次迭代步长。显然，用迭代法求解无约束最优化问题的关键是：构造迭代方向kp和确定迭代步长kt。确定迭代步长kt可通过一维搜索方法进行，而选择不同的方法构造迭代方向kp，将会得到不同的算法。根据一阶Taylor展式)(1kkkTkkkkkktopXftXfptXfXfkkkkkTkkkktttopXfXfptXf)(可见，如果0kkTpXf，那么存在0t，使得当ttk0时上式右端小于零，从而kkkkXfptXf，即kp为下降方向的条件是其与梯度方向成钝角。3、收敛性与收敛速度—个算法是否收敛，往往同初始点0x的选取有关。如果只有当0x充分接近最优解*x时，由算法产生的点列才收敛于*x，则该算法称为具有局部收敛性的算法。如果对于任意的初始点0x，由算法产生的点列都收敛于最优解*x，则这6个算法称为具有全局收敛性的算法。由于一般情况下最优解*x是未知的，所以严格来说只有具有全局收敛性的算法才是有实用意义的。令人遗憾的是大多数经典优化算法都是局部优化算法，全局优化的理论和算法远不及局部优化那么成熟，至今为止还没有得到类似于局部极小点那样的解析条件，即没有肯定的方法能判断一个局部极小点是否为全局极小点，现有的一些全局优化算法也只能在一定程度上避免迭代终止于一个非全局的局部极小点。定义9.5设点列kx收敛于*x，且对实数1p，有pkkkxxxx**1lim，0，则称点列kx为p阶收敛的。9.2一维搜索方法在基本迭代格式kkkkptxx1中，若已知当前点kx和迭代方向kp，则迭代步长kt可由kktpxft)(的极小值确定，即)(mintptxfkkk。这种确定kt的方法称为一维搜索，其实质就是求一元函数)(t的极小值。一维搜索方法分为两类：一类是不需要求导运算、只利用)(t的函数值、适用于单峰函数的直接法，主要有黄金分割法（0.618法）和斐波那契（Fibonacci）法；另一类是需要求导运算的解析法，例如插值方法等。直接法能适应)(t不可微的情况，而解析法的效率相对较高。9.2.1直接法1、确定搜索区间ba,的进退算法在区间ba,中任取一点c，若)()(ca，)()(bc(两头大中间小)，则ba,为搜索区间。①取定初始点0a及初始步长t；②令tac，计算)(a和)(c；③若)()(ca，转④，否则缩短步长t，比如3tt（后退运算），转②；7④加大步长t，比如tt3（前进运算），令tcb；⑤若)()(cb，则得到ba,，否则bcca,，转④。2、