资源描述
结构优化设计结构优化设计崔昌禹崔昌禹第第 三三 章章无约束优化方法无约束优化方法学习内容3.1 无约束优化方法的一般概念3.2 一维搜索方法(步长的确定方法)黄金分割法，牛顿法结构优化设计基本概念的回顾结构优化设计基本概念的回顾结构优化模型结构优化模型 设计变量设计变量：目标函数目标函数：约束约束条件条件：在设计中可调整变化的基本参数。在设计中可调整变化的基本参数。目标函数是设计中预期要达到的目标，目标函数是设计中预期要达到的目标，是人们用来衡量设计方案好坏的一种是人们用来衡量设计方案好坏的一种广义的性能指标广义的性能指标。一个可行的设计方案必须满足一系一个可行的设计方案必须满足一系列条件，这些条件称为约束条件。列条件，这些条件称为约束条件。结构优化设计的主要内容：结构优化设计的主要内容：一）一）结构优化模型结构优化模型建立建立二）二）结构优化结构优化方法方法概念：概念：1.1.设计向量设计向量2.设计空间设计空间(2)(2)连续变量连续变量、离散变量离散变量(1)(1)主动变量主动变量、被动变量：被动变量：分类分类 分类分类(1)(1)单单目标函数目标函数 (2)(2)多目标函数多目标函数 概念：目标函数的等值面概念：目标函数的等值面1.约束函数约束函数 2.2.约束方程约束方程3.3.约束面约束面4.4.可行域可行域 结构优化设计的数学模型一、整体形式（组合向量空间的数学模型一、整体形式（组合向量空间的数学模型）设计向量性态向量组合向量二、常用形式（设计向量空间的数学模型）二、常用形式（设计向量空间的数学模型）第三章第三章3.1 无约束优化方法的无约束优化方法的 一般概念一般概念Graduate Course of Optimum Design of Structures HIT,Lu Dagang,Spring 2007一、整体形式（组合向量空间的数学模型一、整体形式（组合向量空间的数学模型）设计向量性态向量组合向量二、常用形式（设计向量空间的数学模型）二、常用形式（设计向量空间的数学模型）无约束优化问题无约束优化问题 （方法较简单、思想较明确.)约束优化问题约束优化问题解法的基本思想可以推广无约束化3.1 无约束优化方法的一般概念无约束优化一维问题多维问题无约束优化算法解析搜索算法直接搜索算法梯度法(一阶法)共轭梯度法(一阶法)牛顿法(二阶法)拟牛顿法坐标轮换法方向加速法(Powell法)步长加速法(模式搜索法)单纯形法一般不去解方程组（一般不去解方程组（2 2）无约束优化一般形式无约束优化一般形式无约束极值存在的必要条件为：无约束极值存在的必要条件为：(1)(2)3.1 无约束优化方法的一般概念(1)目标函数目标函数 不具备解释性，因此不具备解释性，因此 非线性方非线性方程组无法形成。程组无法形成。(2)即即使形成了使形成了 ，求它的解与接绝缘问题一样很困难。，求它的解与接绝缘问题一样很困难。(3)即即使求得了使求得了 的解，很难验证的解，很难验证或或满足充分条件或凸满足充分条件或凸性条件。性条件。一般不去解方程组（一般不去解方程组（2 2）略去高阶无穷小量，保留一阶项：略去高阶无穷小量，保留一阶项：无约束优化一般形式无约束优化一般形式无约束极值存在的必要条件为：无约束极值存在的必要条件为：在将在将 部近部近 处按泰勒公式展开目标函数处按泰勒公式展开目标函数(1)(2)(3)如果使如果使就可以得到就可以得到表明如果沿着目标函数值降低的方向，一步步向前搜索，最终可以找到最优解。如果沿着目标函数值降低的方向，一步步向前搜索，最终可以找到最优解。3.1 无约束优化方法的一般概念无约束优化方法的数值算法数值算法的迭代公式数值算法的迭代公式向量形式：向量形式：分量形式：分量形式：设计变量的改变量：设计变量的改变量：最优步长搜索方向下降方向应取过点与目标函数的梯度方向成钝角的范围内下降方向应取过点与目标函数的梯度方向成钝角的范围内。ABCFig.2 搜索方向搜索方向Fig.1 下降方向范围下降方向范围3.1 无约束优化方法的一般概念搜索方向的选择原则；搜索方向的选择原则；（1）必须是下降方向。）必须是下降方向。（2）尽可能指向极小点，或使函数下降最快。）尽可能指向极小点，或使函数下降最快。（3）构造）构造搜索方向时，计算量小。搜索方向时，计算量小。步长选择方案；步长选择方案；（1）定步长）定步长（2）变步长）变步长（3）最优步长）最优步长不变无约束优化方法的一般算法Step1 选择初始点 ，令迭代号 。Step3 沿搜索方向 确定最优步长因子 ，使得Step5 验算算法的收敛条件，若收敛，则停机；否则置 ，转步骤2。Step2 确定搜索方向 ，使即：Step4 按迭代公式确定 点；或或3.2 一维搜索方法一维搜索方法 （步长的确定方法）（步长的确定方法）3.2 一维搜索方法（步长的确定方法）一维搜索方法（步长的确定方法）3.2 一维搜索方法一维搜索问题沿给定方向，按一定方法和步骤寻求目标函数最小点称为一维搜索。在 附近小步长范围内，在 方向上只有一个局部极小值点。假定;一维搜索算法解析法试探法：二分法、黄金分割法、Fibonacci法等。（区间消去原理）插值法：牛顿法、二次插值法、三次插值法等。（函数逼近原理）非精确线性搜索法3.2 一维搜索方法区间消去法的基本原理确定搜索区间采用区间消去法逐步缩短搜索区间局优点(a)(b)(c)(1)，极小点必在 内。(2)，极小点必在 内。(3)，极小点必在 内。3.2.1 黄金分割法（0.618法）的基本原理黄金分割法（0.618法）的基本原理黄金分割法的要求：(1)试探点 、与端点 、等距(对称)(2)区间缩短率相同第一次缩短：去掉b1b区间缩短率第二次缩短：去掉a1b1区间缩短率黄金分割黄金分割法（0.618法）的计算流程图黄金分割法（0.618法）的程序演示与算例算例算例1 a b b-a0.618(b-a)a1 b1 f1 f2(1)f1f2 -6.0006.00012.0007.416-1.4161.41618.5012.510(2)f1f2-1.4166.0007.4164.5381.4163.1602.510-0.972(3)f1f21.4164.2492.8331.7512.4983.167-0.748-0.972(5)f1f22.4984.2491.7511.0823.1673.580-0.972-0.664.(11)f1f22.9713.0690.0980.0613.0093.008-0.999-0.9923.2.2 线性搜索的牛顿法线性搜索牛顿法的基本原理：在 点将进行泰勒展开 牛顿法的计算步骤与程序演示牛顿法的计算步骤：Step1 给定初始点 ，精度要求 ，并令 。Step2 计算Step3 计算Step4 若，则求得近似解 ，停止计算；否则转步骤5；Step5 令k=k+1，转步骤2。算例算例142.678E-04156.0004.000000.268E-0484.0190.225E-034.0002732.493E-02-155.9734.000270.249E-0285.8224.025202 2.367E-01-152.8994.025200.2367103.680 24.5414.262191 7.380E-01-101.004.262190.7301168.000124.0005.0000002.140给定初始点和精度要求计算最终结果学习内容的总结学习内容的总结 无约束优化方法的一般概念无约束优化方法的一般概念无约束优化一般形式无约束优化一般形式无约束优化迭代式无约束优化迭代式 一维搜索问题一维搜索问题沿给定方向，按一定方法和步骤寻求目标函数最小点称为一维搜索。黄金分割法（黄金分割法（0.618法）法）线性搜索的牛顿法线性搜索的牛顿法无约束优化方法的一般算法无约束优化方法的一般算法区间消去法的基本原理区间消去法的基本原理黄金分割法的要求黄金分割法的要求线性搜索牛顿法的基本原理线性搜索牛顿法的基本原理黄金分割法的算法黄金分割法的算法线性搜索牛顿法的算法线性搜索牛顿法的算法第三章第三章3.3 无约束优化问题的无约束优化问题的 解析搜索法解析搜索法无约束优化算法解析搜索算法直接搜索算法梯度法(一阶法)共轭梯度法(一阶法)牛顿法(二阶法)拟牛顿法坐标轮换法方向加速法(Powell法)步长加速法(模式搜索法)单纯形法3.3 无约束优化的解析搜索方法无约束优化迭代式无约束优化迭代式3.3 无约束优化的解析搜索方法略去高阶无穷小量，保留一阶项：略去高阶无穷小量，保留一阶项：在将在将 部近部近 处按泰勒公式展开目标函数处按泰勒公式展开目标函数如果使如果使就可以得到就可以得到无约束优化一般形式无约束优化一般形式当当 时，时，下降最快的方向：函数沿负梯度方向下降最快。下降最快的方向：函数沿负梯度方向下降最快。无约束优化迭代式无约束优化迭代式3.3 无约束优化的解析搜索方法梯度法（最速下降法）梯度法（最速下降法）1847年柯西（Cauchy）提出梯度法的基本思想：使目标函数沿它下降最快的方向前进，梯度法的基本思想：使目标函数沿它下降最快的方向前进，逐步走向最优点，因而又称逐步走向最优点，因而又称最速下降法最速下降法。3.3 无约束优化的解析搜索方法梯度法的搜索方向梯度法的搜索方向：梯度法的迭代公式：梯度法的迭代公式：梯度向量梯度向量步长：步长：取一取一维搜索的最佳步搜索的最佳步长梯度法的计算步骤Step1Step1 估计初始点估计初始点 ，设置精度要求，设置精度要求 ，并令，并令 。Step6Step6 更新设计点更新设计点Step2Step2 计算计算 在点在点 处的梯度处的梯度Step3Step3 计算计算 ，若，若 ，则停机，输出最优，则停机，输出最优点点 否则继续。否则继续。Step4Step4 计算当前点计算当前点 处的搜索方向处的搜索方向Step5Step5 计算最优步长计算最优步长令令k=k+1k=k+1，转步骤转步骤2 2。梯度法步骤的特点：梯度法步骤的特点：梯度法的步骤是相互正交的方向顺序移动。梯度法的步骤是相互正交的方向顺序移动。，梯度法的搜索方向梯度法的搜索方向：最速下降方向的正交性设计点在设计空间的移动过程:梯度法的特点：梯度法的步骤是相互正交的方向顺序移动。梯度法的程序演示与算例算例算例1（1）估计初始点 ，设置精度要求 0.1E-5 （2）计算 初始点处梯度：梯度法的搜索方向：（3）计算最优步长：（4）更新设计变量：（5）验算优化精度：最终结果：梯度法的特点梯度法的特点优点优点 （1 1）迭代过程简单，编制程序较易，）迭代过程简单，编制程序较易，一次迭代的工作量较少，计算机内存量小。一次迭代的工作量较少，计算机内存量小。（2 2）函数值下降方向明确，对初始点没有严格要求。）函数值下降方向明确，对初始点没有严格要求。缺点缺点 跌代过程中走许多弯路，有些情况下，收敛速度较慢。跌代过程中走许多弯路，有些情况下，收敛速度较慢。3.1 无约束优化方法的一般概念无约束优化方法的一般概念3.2 一维搜索方法（步长的确定方法）一维搜索方法（步长的确定方法）3.3 无约束优化的解析搜索方法无约束优化的解析搜索方法无约束优化一般形式数值算法的迭代公式设计变量的改变量：最优步长搜索方向无约束优化方法的数值算法(1)黄金分割法(2)线性搜索的牛顿法基本原理、计算步骤基本原理、计算步骤梯度法的基本思想、计算步骤、最速下降方向的正交性梯度法的基本思想、计算步骤、最速下降方向的正交性-梯度法梯度法总结总结3.3.2 共轭梯度法共轭梯度法(Fletcher-Reeves)(Fletcher-Reeves)3.3 无约束优化问题的解析搜索法无约束优化问题的解析搜索法梯度法的特点梯度法的特点优点优点 （1 1）迭代过程简单，编制程序较易，）迭代过程简单，编制程序较易，一次迭代的工作量较少，计算机内存量小。一次迭代的工作量较少，计算机内存量小。（2 2）函数值下降方向明确，对初始点没有严格要求。）函数值下降方向明确，对初始点没有严格要求。缺点缺点 跌代过程中走许多弯路，有些情况下，收敛速度较慢。跌代过程中走许多弯路，有些情况下，收敛速度较慢。最速下降方向的正交性设计点在设计空间的移动过程:梯度法的特点：梯度法的步骤是相互正交的方向顺序移动。跌代过程中走许多弯路，有些情况下，收敛速度较慢。跌代过程中走许多弯路，有些情况下，收敛速度较慢。搜索方向没有直接指向最优点搜索方向没有直接指向最优点3.3.2共轭梯度方法需要改进搜索方向，希望搜索方向需要改进搜索方向，希望搜索方向直接指向最优点直接指向最优点。可以避免跌代过程中走许多弯路，加快收敛速度可以避免跌代过程中走许多弯路，加快收敛速度。共轭梯度方法共轭梯度法Fletcher&Reeves(1964)一般函数一般函数f(xf(x)的的Taylor展开展开一般函数一般函数f(xf(x)可以表示成序列的二次型函数可以表示成序列的二次型函数共轭梯度法共轭梯度法（一）共轭方向的概念和性质（一）共轭方向的概念和性质1.问题的提出问题的提出共轭方向的概念是在研究二次函数共轭方向的概念是在研究二次函数A为对称正定矩阵为对称正定矩阵时提出的。时提出的。若若 指向极小点指向极小点 的索索方向，则可以写成的索索方向，则可以写成;:最优长度。最优长度。(1)(2)(3)(4)=指向极小点指向极小点 的索索方向的索索方向 与与 称为对于称为对于 A 共轭。共轭。2.2.共轭方向的概念共轭方向的概念定义：设定义：设 A 为为 实对称正定矩阵，实对称正定矩阵，为为 维向量组，若维向量组，若则称则称 为为 A 共轭向量系。共轭向量系。说明说明 指向极小点指向极小点 的索索方向的索索方向 与与 对于对于 A 共轭。共轭。（1 1）若）若 A 是单位矩阵是单位矩阵 I I 则则 是正交向量是正交向量,说明共轭是正交的推广。说明共轭是正交的推广。共轭称共轭称A正交正交（2）A可以写成可以写成（3）若）若设设通过线性变换通过线性变换后后正交正交。后后正交正交。通过线性变换通过线性变换3.3.共轭方向的共轭方向的性质性质性质性质1：设：设 A 为为 实对称正定矩阵，若非零向量系实对称正定矩阵，若非零向量系 对对 A 共轭，则这共轭，则这 个向量线性无关。个向量线性无关。性质性质2：设：设 A 为为 实对称正定矩阵，若非零向量系实对称正定矩阵，若非零向量系 对对 A 共轭，则共轭，则 也也 对对 A 共轭。共轭。维空间中互相共轭的非零向量的个数不超过维空间中互相共轭的非零向量的个数不超过 。性质性质3：在：在性质性质5：从任意初始点：从任意初始点出发，顺次沿出发，顺次沿个个的共轭方向的共轭方向进行一维搜索，最多经过进行一维搜索，最多经过次迭代就次迭代就的极小点的极小点。可以找到二次函数可以找到二次函数性质性质4：设：设 A 为为 实对称正定矩阵，若非零向量系实对称正定矩阵，若非零向量系 对对 A 共轭，则任意向量共轭，则任意向量 可表示；可表示；性质性质4：设：设 A 为为 实对称正定矩阵，若非零向量系实对称正定矩阵，若非零向量系 对对 A 共轭，则任意向量共轭，则任意向量 可表示；可表示；证明：证明：任意向量任意向量 可以表示成可以表示成用用左乘式（左乘式（1）得）得性质性质5：从任意初始点：从任意初始点出发，顺次沿出发，顺次沿个个的共轭方向的共轭方向进行一维搜索，最多经过进行一维搜索，最多经过次迭代就次迭代就的极小点的极小点。可以找到二次函数可以找到二次函数证明：证明：二次函数二次函数 在在 处处Taylor展开展开一维搜索的最优步长一维搜索的最优步长 应满足；应满足；（二）共轭方向法（二）共轭方向法 共轭方向法是建立在共轭方向性质共轭方向法是建立在共轭方向性质5 5的基础上，的基础上，它提供了求二次函数极小点的原则和方法，它提供了求二次函数极小点的原则和方法，其步骤是：其步骤是：（2 2）沿）沿方向进行一维搜索，求最优步长，得方向进行一维搜索，求最优步长，得（4 4）提供新的共轭方向）提供新的共轭方向，使，使提供共提供共轭向量系的方法有多种，如共向量系的方法有多种，如共轭梯度法，梯度法，PowellPowell方法等。方法等。，下降方向，下降方向和收敛精度和收敛精度，置置 。（1）选定初始点）选定初始点（3）判断）判断是否满足，若满足则输出是否满足，若满足则输出，停机，否则转（，停机，否则转（4 4）。）。1.（5）置）置，转（，转（2 2）（二）共轭梯度法（二）共轭梯度法(1)初始搜索方向的确定初始搜索方向的确定(2)新的搜索方向新的搜索方向-共轭方向的确定共轭方向的确定构造共轭方向的具体方法构造共轭方向的具体方法，下降方向，下降方向 取取 处的负梯度方向；处的负梯度方向；选定初始点选定初始点Fletcher&Reeves(1964)式中式中又因又因为为A共轭系，共轭系，为使为使共轭，应使共轭，应使故故共轭梯度方法共轭梯度法Fletcher&Reeves(1964)共轭梯度方向 关于对称正定矩阵 正交，即：for all and ,.共轭梯度法的计算步骤Step1 估计初始点 ，设置精度要求 ，并令 。计算Step2 计算 在点 处的梯度Step3 计算 ，若 ，则停机，输出最优点 ；否则继续。Step4 计算新的共轭方向Step6 更新设计Step5 计算最优步长令k=k+1，转步骤2。验算停机准则。若 ，则停止；否则，转向步骤4。3.3.3 牛顿牛顿法法1.1.基本思路基本思路3.3.3 牛顿法牛顿法利用利用二次函数二次函数来逐点逼近来逐点逼近原函数原函数二次函数极小点二次函数极小点来近似来近似原函数极小点原函数极小点并并逐渐逼近原函数极小点逐渐逼近原函数极小点。基本思路基本思路梯度法梯度法牛顿法牛顿法接近极小点下降慢接近极小点下降慢接近极小点下降也快接近极小点下降也快只考虑了迭代点的局部性质只考虑了迭代点的局部性质只利用了一阶偏导数只利用了一阶偏导数全面地确定合适的搜索方向全面地确定合适的搜索方向利用了一阶偏导数，二阶偏导数利用了一阶偏导数，二阶偏导数一阶收敛一阶收敛二阶收敛二阶收敛2.2.牛顿迭代公式牛顿迭代公式极小点极小点 的一个近似点的一个近似点极小点极小点多元函数多元函数迭代公式迭代公式在在 处将处将 进行进行Taylor展开展开牛顿迭代公式：牛顿迭代公式：牛顿方向：牛顿方向：3.3.牛顿法的计算步骤牛顿法的计算步骤Step1Step1 估计初始点估计初始点 ，设置精度要求，设置精度要求 ，并令，并令 。Step2Step2 计算计算 在点在点 处的处的Step3Step3 计算计算Step4Step4若若 ，则停机，输出最优，则停机，输出最优点点；否则，否则，令令k=k+1k=k+1，转步骤转步骤2 2。4.4.牛顿法存在的问题牛顿法存在的问题（1）不存在，导致不存在，导致 无意义。无意义。（2）存在但不正定，由于存在但不正定，由于 非负，非负，不是下降方向，导致不是下降方向，导致（3）存在且正定，但若存在且正定，但若 很大，因而不能保证目标函数下降。很大，因而不能保证目标函数下降。（4）与与 正交，既不是下降方向也不是上升方向。正交，既不是下降方向也不是上升方向。牛顿法没有明确搜索方向的下降性，初始点的依赖也很大，牛顿法没有明确搜索方向的下降性，初始点的依赖也很大，可能出现异常的情况。可能出现异常的情况。（1）不存在，导致不存在，导致 无意义。无意义。4.4.牛顿法的牛顿法的改进改进措施：改变搜索方向，采用最速下降方向，即；措施：改变搜索方向，采用最速下降方向，即；（2）存在但不正定，由于存在但不正定，由于 非负，非负，不是下降方向，导致不是下降方向，导致措施：改变搜索方向，采用负的牛顿方向，即；措施：改变搜索方向，采用负的牛顿方向，即；（3）存在且正定，但若存在且正定，但若 很大，因而不能保证目标函数下降。很大，因而不能保证目标函数下降。措施：采用对步长阻尼措施：采用对步长阻尼的方法（阻尼的方法（阻尼牛顿法）即；牛顿法）即；步长阻尼系数步长阻尼系数（4）与与 正交，既不是下降方向也不是上升方向。正交，既不是下降方向也不是上升方向。措施：改变搜索方向，采用最速下降方向，即；措施：改变搜索方向，采用最速下降方向，即；4.4.改进改进牛顿法的算法牛顿法的算法Step1Step1 估计初始点估计初始点 ，设置精度要求，设置精度要求 ，并令，并令 。Step2Step2 计算计算 在点在点 处的处的Step4Step4 计算计算Step9 Step9 若若 ，则停机，输出最优，则停机，输出最优点点；否则，否则，令令k=k+1k=k+1，转步骤转步骤2 2。Step3Step3 检查检查是，转是，转1010Step5Step5 检查检查是，转是，转1010Step6Step6 检查检查是，转是，转1111Step7Step7 计算计算Step8Step8 计算计算Step10Step10 置置，转，转7 7Step11Step11 置置，转，转7 7牛顿法的特点牛顿法的特点优点优点：具有二次收敛速度，：具有二次收敛速度，对于正定二元二次函数，只需要一次迭代可以达到极小点。对于正定二元二次函数，只需要一次迭代可以达到极小点。缺点缺点：对目标函数要求严。：对目标函数要求严。计算复杂，除了求梯度以外，还要计算海色矩阵及其逆矩阵，计算复杂，除了求梯度以外，还要计算海色矩阵及其逆矩阵，所需要的存储量大。所需要的存储量大。3.3.4 拟牛顿拟牛顿法法（变尺度法）（变尺度法）牛顿法的特点牛顿法的特点优点优点：具有二次收敛速度，：具有二次收敛速度，对于正定二元二次函数，只需要一次迭代可以达到极小点。对于正定二元二次函数，只需要一次迭代可以达到极小点。缺点缺点：对目标函数要求严。：对目标函数要求严。计算复杂，除了求梯度以外，还要计算海色矩阵及其逆矩阵，计算复杂，除了求梯度以外，还要计算海色矩阵及其逆矩阵，所需要的存储量大。所需要的存储量大。梯度法的特点梯度法的特点优点优点 （1 1）迭代过程简单，编制程序较易，）迭代过程简单，编制程序较易，开始时收敛快，开始时收敛快，一次迭代的工作量较少，计算机内存量小。一次迭代的工作量较少，计算机内存量小。（2 2）函数值下降方向明确，对初始点没有严格要求。）函数值下降方向明确，对初始点没有严格要求。缺点缺点 迭迭代过程中走许多弯路，有些情况下，代过程中走许多弯路，有些情况下，接近极小点时接近极小点时收敛速度较慢。收敛速度较慢。拟拟牛顿法的牛顿法的基本思想基本思想构造一种构造一种能保留能保留拟牛顿和梯度法优点，拟牛顿和梯度法优点，又又能避免其缺点能避免其缺点的算法的算法。（1 1）收敛速度快）收敛速度快（2 2）避免）避免计算海色矩阵及其逆矩阵，减少工作量。计算海色矩阵及其逆矩阵，减少工作量。（一）拟牛顿法的基本原理（一）拟牛顿法的基本原理变尺度矩阵变尺度矩阵梯度法梯度法牛顿法牛顿法拟牛顿法的迭代公式：拟牛顿法的迭代公式：拟牛顿法的搜索方向：拟牛顿法的搜索方向：牛顿法牛顿法拟牛顿法（变尺度法）（二）构造变尺度矩阵（二）构造变尺度矩阵 的基本要求的基本要求 必须是对称正定矩阵。必须是对称正定矩阵。满足拟牛顿条件：满足拟牛顿条件：如果取如果取 为极值点附近第为极值点附近第 k+1 k+1 次点，则有次点，则有拟牛顿条件拟牛顿条件如果迫使如果迫使 逼近逼近 ，则有，则有 满足迭代格式：满足迭代格式：拟牛顿法（变尺度法）DFP公式拟牛顿法（变尺度法）BFGS公式拟牛顿法（变尺度法）DFP方法Davidon,Fletcher&Powell(1959,1963)Step1 估计初始点 ，设置精度要求 ，并令 。Step2 计算梯度向量范数 ，若 ，则停机；否则继续。Step3 构造初始DFP方向，取Step7 构造DFP方向,Step5 检查是否满足终止准则。若Step4 计算最优步长令，计算 更新设计，则迭代终止。Step6 检查迭代次数。若 ，令，返回step3；否则，转step7.令，返回step4.拟牛顿法（变尺度法）BFGS方法Broyden-Fletcher-Goldfarb-Shanno(1981)Step1 估计初始点 ，设置精度要求 ，并令 。Step2 计算梯度向量范数 ，若 ，则停机；否则继续。Step3 构造初始DFP方向，取Step7 构造BFGS方向,Step5 检查是否满足终止准则。若Step4 计算最优步长令，计算 更新设计，则迭代终止。Step6 检查迭代次数。若 ，令，返回step3；否则，转step7.令，返回step4.无约束优化问题的无约束优化问题的 解析搜索法解析搜索法小结小结无约束优化算法解析搜索算法解析搜索算法直接搜索算法梯度法梯度法(一阶法一阶法)共轭梯度法共轭梯度法(一阶法一阶法)牛顿法牛顿法(二阶法二阶法)拟牛顿法拟牛顿法坐标轮换法方向加速法(Powell法)步长加速法(模式搜索法)单纯形法无约束优化一般形式无约束优化一般形式无约束优化迭代式无约束优化迭代式搜索方向的选择原则；搜索方向的选择原则；（1）必须是下降方向。）必须是下降方向。（2）尽可能指向极小点，或使函数下降最快。）尽可能指向极小点，或使函数下降最快。（3）构造）构造搜索方向时，计算量小。搜索方向时，计算量小。步长选择方案；步长选择方案；（1）定步长）定步长（2）变步长）变步长（3）最优步长）最优步长不变梯度法（最速下降法）梯度法（最速下降法）1847年柯西（Cauchy）提出梯度法的基本思想：使目标函数沿它下降最快的方向前进，梯度法的基本思想：使目标函数沿它下降最快的方向前进，逐步走向最优点，因而又称逐步走向最优点，因而又称最速下降法最速下降法。梯度法的搜索方向梯度法的搜索方向：梯度法的迭代公式：梯度法的迭代公式：需要改进搜索方向，希望搜索方向需要改进搜索方向，希望搜索方向直接指向最优点直接指向最优点。可以避免跌代过。可以避免跌代过程中走许多弯路，加快收敛速度程中走许多弯路，加快收敛速度。共轭梯度法共轭梯度法Fletcher&Reeves(1964)新的搜索方向新的搜索方向-共轭方向的确定共轭方向的确定式中式中基本思路基本思路:牛顿法牛顿法利用利用二次函数二次函数来逐点逼近来逐点逼近原函数原函数二次函数极小点二次函数极小点来近似来近似原函数极小点原函数极小点并并逐渐逼近原函数极小点逐渐逼近原函数极小点。牛顿迭代公式：牛顿迭代公式：牛顿方向：牛顿方向：牛顿法的牛顿法的改进改进拟拟牛顿法的牛顿法的基本思想基本思想构造一种构造一种能保留能保留拟牛顿和梯度法优点，拟牛顿和梯度法优点，又又能避免其缺点能避免其缺点的算法的算法。（1 1）收敛速度快）收敛速度快（2 2）避免）避免计算海色矩阵及其逆矩阵，减少工作量。计算海色矩阵及其逆矩阵，减少工作量。拟牛顿法的迭代公式：拟牛顿法的迭代公式：拟牛顿法的搜索方向：拟牛顿法的搜索方向：构造变尺度矩阵构造变尺度矩阵 的基本要求的基本要求 必须是对称正定矩阵。必须是对称正定矩阵。满足拟牛顿条件：满足拟牛顿条件：满足迭代格式：满足迭代格式：DFP公式BFGS公式以以 逼近逼近牛顿法牛顿法共轭梯度法共轭梯度法梯度法梯度法第三章第三章3.4 无约束优化问题的无约束优化问题的 直接搜索法直接搜索法Graduate Course of Optimum Design of Structures HIT,Lu Dagang,Spring 2007直接搜索算法直接搜索算法坐标轮换法坐标轮换法方向加速法方向加速法(Powell(Powell法法)步长加速法步长加速法(模式搜索法模式搜索法)单纯形法单纯形法3.4 无约束优化的直接搜索算方法目标函数：目标函数：没有明显的解释表达式，没有明显的解释表达式，只存在目标函数与设计变量的对应关系。只存在目标函数与设计变量的对应关系。很难求得或根本不存在一阶、二阶导数。很难求得或根本不存在一阶、二阶导数。直接搜索算法的特点：直接搜索算法的特点：（1）不用一阶、二阶导数。）不用一阶、二阶导数。（2）对目标函数解释性质不作苛刻的要求。）对目标函数解释性质不作苛刻的要求。（3）适用面广）适用面广（4）收敛速度较慢）收敛速度较慢3.4.1 坐标轮换法（降维法）坐标轮换法（降维法）（一）坐标轮换法的基本思想（一）坐标轮换法的基本思想将一个多维的无约束问题转化为将一个多维的无约束问题转化为 一系列一维优化问题来解决。一系列一维优化问题来解决。3.4.1 坐标轮换法（降维法）坐标轮换法（降维法）搜索方向搜索方向坐标轴方向；坐标轴方向；步长步长取一取一维搜索的最佳步搜索的最佳步长；迭代公式；迭代公式；注意注意（1）除变量）除变量 外其余的变量视为常量。外其余的变量视为常量。（2 2）放宽步长取值范围）放宽步长取值范围 可以等于零，也可以小于零，可以等于零，也可以小于零，也可以大于零。也可以大于零。3.4 无约束优化问题的直接搜索方法坐标轮换法Desopo(1959)Step1 估计初始点 ，设置精度要求 ，并令 。Step2 从点 出发，沿坐标轴方向 进行一维搜索，求 和 ，使得 Step3 检查迭代次数。若 k=n，转Step4；否则，令 k=k+1，返回Step2。Step4 检查是否满足终止准则。若 ，终止迭代，将 作为近似最优解；否则，令 ，返回Step1。坐标轮换法（降维法）的特点坐标轮换法（降维法）的特点c)若等值线出现脊线，本来沿脊若等值线出现脊线，本来沿脊线方线方 向一步可到达最优点，但采用此向一步可到达最优点，但采用此法将法将 终止到脊线上而找不到最优点。终止到脊线上而找不到最优点。（1 1）程序简单，易于掌握。）程序简单，易于掌握。（2）计算效率较低。）计算效率较低。（3）与目标函数等值线的形状有很大关系。）与目标函数等值线的形状有很大关系。a)若若目标函数为二元二次函数目标函数为二元二次函数,其其等值线为圆或长短轴平行于坐标等值线为圆或长短轴平行于坐标轴的椭圆时，此法是有效的，一轴的椭圆时，此法是有效的，一般经两次搜索即可。般经两次搜索即可。b)b)若等值线为长短不平行于坐标轴若等值线为长短不平行于坐标轴 的椭圆，则需多次迭代才能到达的椭圆，则需多次迭代才能到达最优点。最优点。3.4.2 3.4.2 步长加速法步长加速法(模式搜索法模式搜索法)(一一)基本思路基本思路 进行某次试验进行某次试验发现某个方向的目标函数下降趋势发现某个方向的目标函数下降趋势继续沿该方向移动，目标函数还有可能下降继续沿该方向移动，目标函数还有可能下降加大步长，寻找一个目标函数下降最多的点。加大步长，寻找一个目标函数下降最多的点。(二二)步长加速法的两类步长加速法的两类“移动移动”步长加速法：步长加速法：(1)(1)探测性搜索探测性搜索(2)(2)模式搜索模式搜索(1)(1)探测性搜索探测性搜索给定初始点给定初始点 和步长和步长（利用（利用坐标轮换法）坐标轮换法）搜索方向取坐标方向：搜索方向取坐标方向：取试验点取试验点其余变量不变，形成新的探测点其余变量不变，形成新的探测点探测成功。探测成功。（1）探测失败。取探测失败。取 重新探测。重新探测。（2）探测失败。取探测失败。取 重新进行重新进行（1）（）（2）探测。探测。（3）如果（如果（1）（）（2）都没有）都没有探测点，即；探测点，即；探测成功探测成功（如无探测点取如无探测点取 ）开始第开始第i+1i+1个分量探测个分量探测n n个分量的探测结束后形成新的个分量的探测结束后形成新的试验点试验点(2)(2)模式搜索模式搜索求新试验点求新试验点搜索方向；搜索方向；步长；步长；2 2）从）从 出发再进行探测性搜索，得到点出发再进行探测性搜索，得到点1）A)若若 ，则令，则令 ，一次迭代完成。，一次迭代完成。B)若若 ，则令，则令 ,并将步长缩小，并将步长缩小，C)C)重新探测性搜索开始，如果步长足够小，则迭代终止。重新探测性搜索开始，如果步长足够小，则迭代终止。3.4 无约束优化问题的直接搜索方法模式搜索法Hooks&Jeeves(1961)Step1 选取初始点 ，初始步长 ，给定收缩因子 ，给定允许误差 ，令 。Step2 确定参考点，令 。Step3 进行正轴向探测。从点 出发，沿 作正轴向探测：若令 ，转Step5；否则，转Step4。Step4 进行负轴向探测。从点 出发，沿 作负轴向探测：若令 ，转Step5；否则，转Step5。Step5 检验探测次数：若 ，令 ，返回Step3；否则，令转Step6。3.4 无约束优化问题的直接搜索方法模式搜索法Step6 进行模式移动：若 ，从点 出发，沿加速方向Step7 检查是否满足终止准则。若 ，迭代终止，得到近似最优解 ；否则，转Step8。Step8 缩短步长。若 ，令 ，返回Step2；否则，令 ，返回Step2。作模式移动得到试验点 并将步长缩小，从 点出发重新探测性搜索开始，得出新的点返回Step3；否则，转Step7。3.4.3 3.4.3 方向加速法方向加速法(Powell(Powell法法)（一）（一）方向加速法方向加速法的基本思想的基本思想如果不同的初始点如果不同的初始点 ，出发，沿同一方向出发，沿同一方向 求极小点求极小点 ，那么连接这两个一维极小点的直线必通过极小点，那么连接这两个一维极小点的直线必通过极小点 。对二次函数对二次函数 来说来说方向加速法方向加速法的实质：的实质：共轭方向法共轭方向法即即：，A-共轭共轭即即：，A-共轭共轭.(1).(2).(3)(4)-(3).(4).(5)（二二）方向加速法方向加速法的的迭代方法迭代方法第一步迭代第一步迭代第二步迭代第二步迭代（三三）方向加速法方向加速法的的方向调整方向调整 对应的搜索方向为对应的搜索方向为方向进行搜索，步长取方向进行搜索，步长取求探索点求探索点计算对应的目标函数值计算对应的目标函数值检验不等式检验不等式（1）确定可能需要替换的确定可能需要替换的方向方向（2）判断调整判断调整方向方向的必要性的必要性如不等式成立，搜索方向不变，如不等式成立，搜索方向不变，不能沿不能沿 方向延伸，方向延伸，如不等式不成立如不等式不成立，用，用 替换替换 方向。方向。（四四）方向加速法方向加速法的的算法算法 Step1Step1 给定初始点给定初始点 ，搜索方向，搜索方向 ，设置精度要求，设置精度要求 ，并令，并令 。Step4Step4 计算计算Step7Step7 若若 则转则转1111，若，若 ，则转，则转1212Step8Step8 若若 则转则转9,9,否则否则 转转2 2Step2Step2 计算计算Step3Step3 计算计算Step5Step5 若若 j=n,j=n,则转则转6 6，否则，否则 j=j+1 转转3 3。Step4Step4 计算计算 ,若若 则则 记记 M=m M=m。Step6Step6 若若 则则 停机，否则停机，否则 转转2 2。Step9 Step9 计算计算转转2 23.4.4 单纯形方法单纯形方法Nelder&Mead(1965)在不计算导数的情况下，对在不计算导数的情况下，对n维空间的维空间的n+1个点（它们构成一个单纯形的顶点）个点（它们构成一个单纯形的顶点）上的函数值进行比较，丢掉其中最坏点，代替以新的点构成一个新的单纯形的上的函数值进行比较，丢掉其中最坏点，代替以新的点构成一个新的单纯形的顶点，逐步逼近极小值点。顶点，逐步逼近极小值点。不是某一个方向进行搜索不是某一个方向进行搜索（一）单纯形方法的基本思路（一）单纯形方法的基本思路（二）单纯形方法的组成（二）单纯形方法的组成（1）初始单纯形的形成）初始单纯形的形成（2）迭代方法）迭代方法单纯形单纯形 ：是指在是指在n维空空间中由中由n+1个个线性独立的性独立的顶点构成的点构成的简单图形或凸多面体。形或凸多面体。例如：一维空间：线段，二维空间：三角形，三维空间：四面体。例如：一维空间：线段，二维空间：三角形，三维空间：四面体。当单纯形各定点之间的距离相等时，则称为正规单纯形。当单纯形各定点之间的距离相等时，则称为正规单纯形。一维空间一维空间:二维空间：二维空间：三维空间：三维空间：正规单纯形正规单纯形 ：是指在是指在维空空间中由中由n+1个个线性独立的性独立的顶点构成的，点构成的，单纯形各定点之间的距离相等的单纯形各定点之间的距离相等的简单几何几何图形。形。二维空间：二维空间：三维空间：三维空间：一维空间一维空间:（1）初始单纯形的形成）初始单纯形的形成给定初始点给定初始点 正规单纯形边长正规单纯形边长 定义：定义：（2）迭代方法）迭代方法1.反射反射:2.延伸延伸:反射成功的前提下，既：反射成功的前提下，既：3.收缩：收缩：反射失败的前提下进行，既：反射失败的前提下进行，既：若若 ，则以以 代替代替 否否则以以 代替代替 反射反射 延伸延伸 收缩收缩 压缩压缩4.压缩压缩:时时时，先以时，先以 替换替换 以后再收缩。以后再收缩。时，既时，既反射反射失败，失败，收缩收缩也失败时；（也失败时；（不动）不动）单纯形的迭代过程单纯形的迭代过程3.4 无约束优化问题的直接搜索方法单纯形调优法 Step1Step1 选取初始数据。选取以 为顶点的初始单纯形 ，给定反射系数 ，紧缩系数 ，扩展系数 ，收缩系 数 ，允许误差 。Step2Step2 顶点重新编号，将单纯形的n+1个顶点按目标函数值大小重新编号，使其 满足 。Step3Step3 检查是否满足终止准则。求单纯形 的重心 若 ，迭代终止，为问题的近似最 优解；否则，转Step 4。Step4Step4 求反射点。计算反射点 ，若 转Step5;否则，当 时转Step6，当 转Step7。Nelder&Mead(1965)3.4 无约束优化问题的直接搜索方法Step5Step5 扩展。计算扩展点 。若 ，令 ，构造扩展单纯形，转Step2；否则，转Step6。Step6Step6 反射。令 ，构造反射单纯形，返回Step2。Step7Step7 收缩。把 和 之间对应目标函数值较小的点记作 ，计算收缩 点 。若 ，令 ，构造收缩单纯形，返回Step2；否则，转Step8。Step8Step8 紧缩。令 构造紧缩单纯形，返回 Step2。谢 谢！
展开阅读全文