最优化方法与最优控制3

1、解2°：按二次函数计算。取；收敛性检查：；得到，。2-2-6 变尺度法在梯度法中，是以在处的最速下降方向作为搜索方向。这种搜索是局部性的，搜索会产生拉锯现象，使收敛放慢。若要快速收敛，搜索方向应取处的牛顿方向，即，式中 是 处的海森矩阵。显然，要得到牛顿方向，需要计算二阶导数及海森矩阵的逆矩阵，相当麻烦。如果，则梯度方向和牛顿方向一致。为了克服梯度法和牛顿法的缺点，可按 (2-32)方向进行搜索。为保证向下降方向搜索，且计算方便，要求矩阵具有以下性质：1. 是正定的；2. 保证关于矩阵是共轭的；3. 与具有递推关系，即， (2-33)式中 称为校正矩阵。为使关于矩阵共轭，并注意到式(

2、2-32)则有，。 (2-34)由式(2-17)知，则下式给出的满足式(2-34)，。 (2-35)式中 为任一实数。显然，如果和关于共轭，。 (2-36)由式(2-35)减式(2-36)，得到，。(2-37)当时，则。 (2-38)记，。由于是二次函数，所以有。 (2-39)由式(2-37)得， 。 (2-40)将式(2-39)代入式(2-40)和式(2-38)，得到， ； (2-41)。 (2-42)式中 。根据式(2-41)和式(2-42)可以构造出，在已知的条件下，由式(2-33)计算，在由(2-32)计算。校正矩阵应当能够由已知的、和构造出来。下面叙述校正矩阵是如何构造的及其推导过程

3、。Huang构造的具有简单形式。 (2-43)式中 ，。易知，如果这两个向量选择为；。 (2-44)则式(2-43)构造的满足式(2-41)和(2-42)。再要求向量和具有如下形式， (2-45)参数、和只需满足式(2-46)。，。 (2-46)显然，由2个线性方程求解5个未知数，有3个参数可以自由选择，即有无穷多组解。不同参数组构成不同形式的，也就是不同形式的变尺度法。一般选初始矩阵为单位矩阵。1970年Huang把各种变尺度法公式归纳成含有三个自由参数的公式。该公式所能产生的变尺度法称为Huang簇。下面说明：按式(2-45)和式(2-46)构造的向量和满足式(2-44)。由式(2-39)

4、及的定义，得，。又得，。 (2-47)将式(2-36)两边乘，并注意到式(2-47)，则有，。将上式乘以，并注意到式(2-39)，即得，。注意到和及式(2-35)，得知，。得证：按式(2-45)和式(2-46)构造的向量和满足式(2-44)。由公式；(2-33)；(2-43)；(2-45)，。(2-46)构成矩阵称为Huang矩阵类。由Huang矩阵类中构成的搜索方向是关于共轭的，而且有。该结果与参数、和的选取无关。特别地，当时，第步迭代方向就是牛顿方向。下面介绍Huang矩阵类的两种算法：1. 秩1算法在Huang算法中，选取，隐含着。由式(2-43)得，因和都是维向量，所以是秩为1的矩阵。

5、因此，该算法称为秩1 算法。将代入式(2-33)得。 (2-48)如果选取，则有。 (2-49)这是对称的秩 1算法。当、为正定矩阵时，亦为正定矩阵。的不同选取方法得到不同的秩 1算法。2. 秩2算法在Huang算法中，选取和，由(2-45)和(2-46)得到，。 (2-50)把式(2-50)代入式(2-45)，进而代入式(2-43) ，得到(2-51)在选取、为正定矩阵时，也是正定矩阵。在式(2-51)中，令，得到。 (2-52)该公式就是有名的DFP变尺度法公式。如果在式(2-51)中，令，则有。(2-53)该公式是BFGS(Broyden-Flecther-Goldfarb-Shanon

6、)公式。BFGS算法比DFP算法具有更好的稳定性。在计算的过程中，要保证的对称性和正定性，否则，导致算法失败。只要在编制程序时注意计算细节，就能够保证的对称性；而的正定性，则可利用是否下降来检查。如果，则将作为新起点，重新选取，继续运算。变尺度法求解函数极值的计算步骤：1. 选取初始点，允许误差；选取初始矩阵；2. 计算、；置、；3. 计算满足，；计算、；4. 收敛性检查：若，则，终止计算；否则，继续；5. 是否下降检查：若，则置、，转到步骤3；否则，继续；6. 检查循环变量：若，则转到步骤8；否则，继续；7. 计算；(1) DFP算法：按式(2-52)计算；(2) BFGS算法：按式(2-5

7、3)计算；计算；循环变量加1；返回步骤3；8. 置、；返回步骤3。下面给出应用变尺度法求解函数极值的计算例子，例子中的函数是二次函数。二次函数求极值有最简单方法，该例解题涉及到这种方法。之所以用二次函数作变尺度法求解函数极值的计算例子，只是便于叙述和使用较少迭代次数。例2-17 设二次函数如下，应用变尺度法求解函数极值。，解：若将问题规范化为：令，则有；。易知，当时，函数取极小值，即，。仅仅是为了讨论方便，采用二次函数作为比较BFGS算法和DFP算法的区别。这两种算法的差别，只体现在计算所使用的公式不同。令，则有。选取初始点，；据，得； 收敛性检查：；未达到要求，继续；检查函数值是否下降：；正

8、在下降，继续；BFGS计算*，；，； 收敛性检查：；已达到要求，终止计算。得到，。在计算之前， DFP算法和BFGS算法的各步计算结果完全相同，区别在这之后：DFP计算*，；，；收敛性检查：；未达到要求，继续；检查函数值是否下降：；正在下降，继续；DFP计算*，；，； 收敛性检查：；已达到要求，终止计算。得到，。比较两种算法的计算过程，知道BFGS算法比DFP算法收敛快。2-3 求解多元函数无约束极值的直接法不使用导数而直接利用目标函数进行比较、搜索，称为直接法。本节介绍单纯形法、模式搜索法和方向加速法。2-3-1 单纯形法在维空间，由个顶点组成的凸包称为单纯形，例如一维中的线段、二维中的三角

9、形、三维中的四面体等。如果单纯形个顶点中任意两点的距离都相等，则称为正规单纯形。下面叙述正规单纯形是如何构成的。在下面的叙述中，变量右上标表示顶点在单纯形中的编号，不表示变量的幂次。设单纯形的初始点为，第点为，它们的元素表达如下：，。 (2-54)正规单纯形中任意两顶点的距离都相等，则和满足下面的两个方程，；，。解这两个方程，可得到4组解。取的一组：， 。 (2-55)单纯形算法的基本思想是找出新的一点代替原点中性能最差的一点，组成新的单纯形。如此不断进行，直到找到满足精度要求的极小值点。为便于叙述，记，并定义单纯形中函数值最大点 、最小点、次最大点和排除的单纯形所有顶点的质心如下：，。单纯形

10、算法含有反射、延伸、收缩等操作步骤。下面按单纯形法的操作顺序，逐个地说明这些运算步骤，并以二维空间的示意图帮助理解。在图例中，简单形状的虚线是等函数值线，图形中心是极小值点。1. 反射 令，式中 是常数，称为反射系数； 称为关于的反射点。从开始，沿方向到达点，若，则用代替构成新的单纯形，如图2-2所示。2. 延伸 当时，表明反射得到新的最小点，需沿反射方向延伸到，即，式中 为延伸系数。此时，如果，则用代替构成新的单纯形，如图2-3所示。若，则用代替构成新的单纯形，如图2-4所示。dcxfdcxydcxyfsdcxfsdcxf图2-5收缩(a)图2-5收缩(b)图2-3延伸图2-4延伸图2-2反

11、射3. 收缩 如果，则要进行收缩。收缩到，即，式中 为收缩系数。是最大点和反射点中函数值较小的点，即。如果，则用代替构成新的单纯形，如图2-5所示。4. 压缩 如果，说明收缩也失败了，则将单纯形向最小值点进行压缩。各新顶点是原顶点和最小点的中点，其数值按下述表达式计算，。单纯形算法中，一般选取、和比较合适。收敛性检查如下：， (2-56)式中 是给定的允许误差，即算法收敛的检查标准。使用单纯形法求函数极值的计算步骤归纳如下：1. 算法初始化(1) 确定运算参数：、和；(2) 选取初始点，正规单纯形的边长；(3) 按式(2-54)和式(2-55)构造初始单纯形；(4) 单纯形顶点函数值计算；2.

12、 找出最大点、最小点、次最大点，计算质心；3. 收敛性检查：按式(2-56)判断是否收敛，若收敛，则终止计算；否则，继续；4. 反射：计算反射点及；(1) 若，转步骤5；否则，继续；(2) 若，用、依次代替、，转步骤2；否则，转步骤6；5. 延伸：计算延伸点及；若，则用、依次代替、，转步骤2；否则，用、依次代替、，转步骤2；6. 收缩：据，确定点；计算收缩点及；若，用、依次代替、，转步骤2；否则，继续；7. 压缩：计算压缩后的单纯形顶点及对应的函数值，；转步骤2。2-3-2 模式搜索法模式搜索法又称为步长加速法。该算法包括探测性搜索和模式移动两部分。探测性搜索 设初始点为，沿坐标探测的步长为(

13、可以是常数，为坐标编号)。依次沿坐标搜索 和 。是第分量的单位向量。是每次搜索完成后的点。每次都是以前一次搜索的结果作为起点。首先计算，若，则，继续下一个坐标搜索；否则，计算，若，则，否则，；继续下一个坐标搜索。个分量都搜索完成后，若，表明比要好，即探测性搜索找到了函数值下降的方向。若，表明未能找到下降方向，需要改变步长，重新作探测性搜索。模式移动 在知道下降方向后，沿该方向移动测试点，这就是模式移动。新的测试点按下式计算；。有了新的测试点，重复探测性搜索和模式移动。直到所有坐标的搜索步长时，认为，已找到了极小值点。2-3-3 方向加速法方向加速法(Powell方法)本质上属于共轭方向法，该方

14、法中不使用导数，而是通过迭代来构造正定矩阵的共轭方向向量。该方法的计算步骤如下：1. 选取初始点，允许误差和坐标方向；2. 置共轭向量；3. 依次按方向向量搜索，计算，其中 满足，；4. 计算，定义如下，；5. 计算；6. 若 ，转步骤9；7. 若 ，置；8. 转步骤11。9. 计算；置；10. 计算计算，其中 满足；11. 收敛性检查，若，已收敛，终止计算；12. 置，转步骤3；方向加速法也有两个组成部分，探测性搜索和更新共轭方向。步骤3步骤5类似模式搜索法的探测性搜索，其余步骤为更新共轭方向。2-4 多元函数带约束极小化带约束的非线性规划问题的数学模型为目标函数约束条件(2-57)式中 、

15、和至少有一个是非线性的，且和不全为零。求解带约束的非线性规划问题的大多数算法是将原问题转换为一系列无约束非线性规划或线性规划问题来处理。本节介绍带等式约束和不等式约束条件下的极小化方法及罚函数法。2-4-1 等式约束条件下的极小化在带约束的非线性规划问题(2-57)中，只要求满足等式约束，就是带等式约束的非线性规划问题。如果在点，的秩为(满秩)，即约束条件线性无关，则称是正则点。； ，。如果和连续且具有连续的一阶导数，它们的一阶泰勒展开式为，如果和都满足约束条件，即、，忽略高阶无穷小，得到。定义为中的一个维子空间。如果在处达到相对极小，则对充分小的，有。 因，则要求。因此得到，满足约束条件时，

16、在处达到相对极小的一阶必要条件： 在充分小时，。该必要条件表明，正交于维子空间，即它是属于的维正交补空间，该补空间的基底是。于是，存在拉格朗日(Lagrangian)常数，使得时，有。构造拉格朗日函数，则得到在正则点达到相对极小的一阶必要条件：， (2-58)必要条件(2-58)是一组包含个变量，即向量和元素的个方程。拉格朗日函数在点的二阶泰勒展开式为。对于任意的，和都满足达到相对极小的必要条件，如果有，即 ， (2-59)则由二阶泰勒展开式得到。于是，式(2-58)和式(2-59)是在正则点上成为相对极小的充要条件。例2-18 目标函数与等式约束条件都是非线性函数的例子。求原点到球面的最短距

17、离。解：记原点到球面的距离平方为，则问题的数学描述为目标函数 ；约束条件 。构造拉格朗日函数，充要条件为，；由条件，消去变量，得到、和，代入约束条件，整理后，得到；在两组解，和，中，取满足，的一组解，即 、和。点评：本例可以避开关于取值的讨论，直接按值的大小来选取；若用解析几何方法来求解该例，只需求解过原点和球心的直线与球面的近交点。 本例的直线方程就是，则避开了非线性规划问题的许多麻烦。例2-19 目标函数是非线性函数，而等式约束条件是线性函数的例子。求平面上到原点距离最短的点。解：记平面上任一点到原点距离的平方值为，则问题的数学描述为目标函数 ；约束条件 。构造拉格朗日函数，充要条件为，；

18、由条件，得到、和；代入约束条件，得到、 和。即，。2-4-2 不等式约束条件下的极小化在带约束的非线性规划问题(2-57)中，只要求满足不等式约束，就是带不等式约束的非线性规划问题。引入辅助变量将不等式约束条件转化为如下等式约束条件，。同样，有拉格朗日函数；式中 ，。这样，就可以按等式约束来处理。则在正则点达到极小的一阶必要条件：(2-60)，。(2-61)函数对和的二阶导数矩阵为，再由等式约束条件可得，的空间满足，。 (2-62)函数在上达到极小的二阶必要条件是 ，。 (2-63)下面，将导出极小解的必要条件。为便于讨论，记集合。1. 若，即，则。由式(2-62)知道，可以取任意值。因而定义

19、空间满足。为保证对任意的，式(2-63)都成立，要求：；。2. 若，即，则。为保证式(2-61)成立，必有。对于任意的总存在，使式(2-62)成立又不影响式(2-63)。于是，得到结论：二阶必要条件中不必考虑辅助变量。函数受，不等式约束条件时，在上达到极小值的必要条件是：对于函数满足(1) ；(2) ，；(3) 。例2-19 目标函数和不等式约束条件都是非线性函数的例子。求函数在约束条件，限制下的极小值。解：；关于极值点的讨论：(1) 极值点不在边界上，即和；解得，；不满足条件；(2) 极值点同时在两个边界上，即和；解得，且和且；只有满足条件；(3) 极值点在第一边界上但不在第二边界上，即和；

20、解得，和；都不满足条件；(4) 极值点不在第一边界上，但在第二边界上，即和；解得，；不满足条件；四种情况讨论后，只得到一组可行解。于是，。若要检验二阶条件，可使用公式；即在上达到极小值。一般情况下，不必检验二阶条件；若有多组可行解，只需比较各点的函数值，取最小的就可。2-4-3 罚函数法在前面介绍的解有约束的非线性极小化方法，都是先将约束条件乘以拉格朗日乘子加上目标函数构成拉格朗日函数，再求满足拉格朗日函数极小化必要条件的极小点。罚函数法是，将约束条件和罚因子的组合加入目标函数，构成罚函数，再求一系列罚函数的极小值来代替，从而把有约束极小化问题转化为一系列无约束极小化问题。因此，罚函数法又成为

21、序贯无约束极小化方法(SUMT, Sequential Unconstrained Minimization technique)。构造罚函数需要经验和技巧，下面给出一个简单的例子。例2-20 求 ，。解：设罚函数构成如下， (2-64)式中 是罚因子，表示在约束条件不满足时，予以“惩罚”，使罚函数值增大，所以。下标表示逼近过程中的序号。本例的极值点满足；。显然，即无约束条件，则；当，即才能使取极小值，这时，就是在约束下的极值点。对于等式约束的极小化问题，可以按式(2-64)所示方法，构造罚函数。随着的增大逐一求出的极小点，当为无穷大时，的极小点就是的极小点。这就是将有约束极小化问题转化为求一

22、系列无约束极小化问题的罚函数法。 前几节介绍的多元函数无约束极小化方法都可用来求的极小值。罚函数法分为外点法和内点法，若迭代点是从可行域外部逐步向最优点逼近，称为外点法。 内点法是从内部逼近最优点。1. 外点法外点法的迭代是从可行域外部开始，逐步加大罚因子，迫使迭代点向可行域靠近。而对于可行域内的迭代点不予“惩罚”。设有非线性规划问题。 (2-65)该问题的罚函数构成如下。 (2-66)式中 是第次迭代的罚因子，且，是单位阶跃函数，即。这样，当足够大时，的解近似问题(2-65)的解。式(2-66)给出的罚函数等价于。对于既有等式约束，又有不等式约束的非线性规划，罚函数的构成如下。 (2-67)

23、罚函数外点法的主要步骤为1. 算法初始化：选取初始点，允许误差，罚因子，增大系数()；2. 无约束极小化：以为起点，的最优点为；3. 收敛性检查：若，则，结束运算；否则，返回步骤2。例2-21 试用罚函数外点法求解。解：记，按式(2-67)构造罚函数。试取，即不考虑不等式约束条件，解等式约束极小化问题得到，显然，不满足不等式约束。则罚函数应为。罚函数取极值的必要条件为；由式(1)和(3)得 ，代入式(2)得。当，即得，。说明：将等式约束条件代入目标函数是明智的作法，如本例转化为，则计算要方便一些。2. 内点法内点法是将初始点选在可行域内，再逐步逼近最优点。如果迭代点越靠近边界，“惩罚”越重，以

24、防止迭代点越出边界。由于内点法的迭代点是在可行域内，它仅适合于不等式约束极小化问题。若含有等式约束，则利用等式约束减少变量个数，有利于问题求解，参见例2-21的说明。对于以下的不等式约束极小化问题。 (2-68)内点法的罚函数构成为， (2-69)式中 为第次迭代的罚因子。式(2-69)把不等式约束极小化问题(2-68)转化为无约束极小化问题。当时，满足的就是原问题的解。罚函数内点法的主要步骤为1. 算法初始化：选取初始点，允许误差，罚因子，减小系数()；2. 无约束极小化：以为起点，的最优点为；3. 收敛性检查：若，则，结束运算；否则，返回步骤2。例2-22 试用罚函数内点法求解。解：构造罚

25、函数；求取的解析表达式(三次方程的解析解)较困难，当时，有两组解 和 。显然，不满足约束条件，即，。说明：本例与下面的问题相同，设在三维空间有一平面 ，该平面将空间划分成两部分，其一为。试在内求取到距离最短的点。也就是求点在平面上的投影。这表明，若最优解在某个不等式约束条件的边界上时，该不等式约束条件等价于等式约束条件。2-5 非线性规划应用举例非线性规划应用很广泛，只要目标函数是参数的非线性函数，那么，参数最优化问题就是非线性规划问题。有许多应用实例的背景知识较深，很难用简单几句话叙述清楚，如神经元网络训练BP算法、地震震中及震级估计等。因此，在这一节中，只简单叙述几个应用示例。2-5-1

26、线性离散系统辩识设已知线性离散系统的结构为，式中 是系统输出；是系统输入，在开环测试时，采用伪随机二进制信号；是零均值正态分布的过程干扰。为便于讨论未知参数的估计问题，采用以下定义的参数估计值向量、数据向量数学符号：，。当用测试数据、 和参数估计值拟合系统时，有。 (2-70)式中 是拟合残差，它是过程干扰的估计值。在测试数据的测量误差可以忽略条件下，参数估计的目标函数为。 (2-71)记，则有。根据非线性多元函数极值的必要条件有，则得到参数估计值为。这就是参数估计中最基本的最小二乘法。2-5-2 制造工厂的库存优化问题如果工厂的生产能力超过销售量，而且只能采用周期生产来维持产销平衡，即在一个生产周期中只连续生产一段时间 。考虑每件产品的月(30天)储存费用和每次恢复生产的额外开销。安排生产的最优化目标是，在保