优化设计.ppt

现代设计方法现代设计方法第三章第三章 优化设计优化设计Optimization Design现代设计方法现代设计方法本章主要内容本章主要内容 优化设计概述优化设计概述 优化问题的数学分析基础优化问题的数学分析基础 一维探索优化方法一维探索优化方法 无约束多维问题的优化方法无约束多维问题的优化方法 约束问题的优化方法约束问题的优化方法 多目标函数的优化方法多目标函数的优化方法 现代设计方法现代设计方法本章重难点本章重难点 优化设计数学模型的建立，掌握常用的优优化设计数学模型的建立，掌握常用的优化方法，如一维探索优化方法、无约束多维问化方法，如一维探索优化方法、无约束多维问题的优化方法、约束问题的优化方法、以及多题的优化方法、约束问题的优化方法、以及多目标函数的优化方法等。目标函数的优化方法等。现代设计方法现代设计方法3.1 3.1 优化设计概述优化设计概述3.1.1 3.1.1 优化设计问题的提出优化设计问题的提出1.1.传统设计方法：传统设计方法：确定产品结构方案；尺寸计算和强度确定产品结构方案；尺寸计算和强度校核；调整方案，重新计算。校核；调整方案，重新计算。（循环设计过程）（循环设计过程）缺点：缺点：烦琐，耗时，以牺牲设计效率和质量为代价烦琐，耗时，以牺牲设计效率和质量为代价2.2.优化设计：优化设计：转化为最优化问题，利用数学规划的方法，转化为最优化问题，利用数学规划的方法，借助于计算机（高速度、高精度和大存储量）的处理，借助于计算机（高速度、高精度和大存储量）的处理，从满足设计要求的一切可行方案中，按照预定的目标自从满足设计要求的一切可行方案中，按照预定的目标自动寻找最优设计的一种设计方法。动寻找最优设计的一种设计方法。优化设计三要素：优化设计三要素：设计变量，目标函数，约束条件。设计变量，目标函数，约束条件。现代设计方法现代设计方法满足：满足：gu(m、z、x)的情况下的情况下寻找：寻找：一组设计参数一组设计参数m、z、x；（；（模数、齿数、模数、齿数、变位系数）变位系数）使得：使得：设计目标设计目标流量最均匀流量最均匀,体积最小体积最小,寿命最长寿命最长以齿轮泵为例，其优化设计过程如下：以齿轮泵为例，其优化设计过程如下：现代设计方法现代设计方法3.1.2 3.1.2 优化设计的数学模型优化设计的数学模型 优化设计的问题首先是建立数学模型，即把实际优化设计的问题首先是建立数学模型，即把实际问题转化为数学模型的形式。问题转化为数学模型的形式。优化模型三要素：优化模型三要素：设计变设计变量，目标函数，约束条件。量，目标函数，约束条件。1.1.设计变量设计变量 设计过程中，进行选择和调整，最终必须确定的独设计过程中，进行选择和调整，最终必须确定的独立参数称为立参数称为设计变量设计变量；固定不变，需要事先给定的参数；固定不变，需要事先给定的参数称为称为设计常量设计常量。（1 1）维数：）维数：设计变量的个数称为设计问题的维数。设设计变量的个数称为设计问题的维数。设计变量愈多，设计自由度愈大，可供选择方案愈多，设计变量愈多，设计自由度愈大，可供选择方案愈多，设计计愈愈灵活，难度愈大，求解愈复杂。灵活，难度愈大，求解愈复杂。现代设计方法现代设计方法（2 2）设计空间）设计空间:n 个设计变量的坐标轴所形成的个设计变量的坐标轴所形成的n维实维实空间称为设计空间，用空间称为设计空间，用Rn表示。设计空间中，表示。设计空间中，n 个设计个设计变量的坐标值组成一个设计点，并代表一个设计方案，变量的坐标值组成一个设计点，并代表一个设计方案，可采用如下向量表示可采用如下向量表示：其中，最优设计方案用其中，最优设计方案用 表示，称为表示，称为最优点最优点或或优化点优化点。现代设计方法现代设计方法二维设计空间二维设计空间三维设计空间三维设计空间x2x1X=x1 x2Tx1x2x3X=x1 x2 x3 T现代设计方法现代设计方法2.2.目标函数目标函数 优化设计的任务是在许多可行的方案中找出最优的优化设计的任务是在许多可行的方案中找出最优的方案，所谓最优方案是在设计变量中能最好的满足所追方案，所谓最优方案是在设计变量中能最好的满足所追求的某些特点的目标，而这些目标又可表达为设计变量求的某些特点的目标，而这些目标又可表达为设计变量的函数，称为的函数，称为目标函数。目标函数。目标函数可用来评价设计方案目标函数可用来评价设计方案的好坏，又称为的好坏，又称为评价函数评价函数。常表示为：。常表示为：目标函数表征的是设计的某项或某些最重要的特征。目标函数表征的是设计的某项或某些最重要的特征。优化设计就是要通过优选设计变量使目标函数达到最优值。优化设计就是要通过优选设计变量使目标函数达到最优值。目标函数总可以转化成求最小值的统一形式。目标函数总可以转化成求最小值的统一形式。现代设计方法现代设计方法等值曲面等值曲面:目标函数值相等的所有设计点的集合称为目目标函数值相等的所有设计点的集合称为目标函数的等值曲面。二维：等值线；三维：等值面；三标函数的等值曲面。二维：等值线；三维：等值面；三维以上：等超越面。维以上：等超越面。z等值线族形象地反映了目标等值线族形象地反映了目标函数值的变化规律，越靠近函数值的变化规律，越靠近极值点的等值线，表示的目极值点的等值线，表示的目标函数值越小，其分布也越标函数值越小，其分布也越密集。密集。xyo等高线等高线x*（中心极值点）（中心极值点）等值线族等值线族 二维设计变量下的等值线二维设计变量下的等值线现代设计方法现代设计方法3.3.约束条件（函数）约束条件（函数）对任何设计都有若干不同的要求和限制，将这些要对任何设计都有若干不同的要求和限制，将这些要求和限制表示成设计变量的函数并写成一系列不等式和求和限制表示成设计变量的函数并写成一系列不等式和等式表达式，就构成了设计的等式表达式，就构成了设计的约束条件约束条件简称简称约束约束。其作。其作用是对设计变量的取值加以限制。用是对设计变量的取值加以限制。现代设计方法现代设计方法（1）分类）分类 根据对设计变量取值的限制形式：根据对设计变量取值的限制形式：显约束（直接限制）显约束（直接限制）和和隐约束（间接限制）隐约束（间接限制）根据性质的不同：根据性质的不同：边界约束边界约束和和性能约束性能约束。边界约束：边界约束：直接限制每个设计变量的取值范围或彼此直接限制每个设计变量的取值范围或彼此相互关系的一些辅助的区域约束。相互关系的一些辅助的区域约束。性能约束：性能约束：由产品性能或设计者要求推导出来的用以由产品性能或设计者要求推导出来的用以间接限制设计变量取值范围的一种约束。间接限制设计变量取值范围的一种约束。现代设计方法现代设计方法（2 2）可行域）可行域 任何任何一个不等式约束一个不等式约束都把设计空间分为两部分，都把设计空间分为两部分，一部分是满足约束条件的称为一部分是满足约束条件的称为可行域可行域，另一部分是，另一部分是不满足约束条件的称为不满足约束条件的称为非可行域非可行域，这两部分的分界，这两部分的分界是是 (约束方程约束方程)。在约束边界上的点称为在约束边界上的点称为边界点边界点 两个以上约束边界的交点称为两个以上约束边界的交点称为角点角点等式约束同样把设计空间分成两部分。等式约束同样把设计空间分成两部分。现代设计方法现代设计方法不等式约束与等式约束的几何意义：不等式约束与等式约束的几何意义：在一个优化设计问题的设计空间中，满足所有在一个优化设计问题的设计空间中，满足所有约束条件的点构成的子空间，称为约束条件的点构成的子空间，称为可行域可行域。现代设计方法现代设计方法【例例1】作出下列约束条件构成的可行域：作出下列约束条件构成的可行域：现代设计方法现代设计方法【例例2 2】根据下列约束条件画出可行域。根据下列约束条件画出可行域。可行域在约束边界的哪可行域在约束边界的哪一边怎么确定？一边怎么确定？现代设计方法现代设计方法（3 3）起作用约束）起作用约束设设X X为设计空间中的一个点：为设计空间中的一个点：满足所有约束条件的点称为可行点（内点和边界点）满足所有约束条件的点称为可行点（内点和边界点）不满足所有约束条件的点称为非可行点（外点）不满足所有约束条件的点称为非可行点（外点）X X在某个约束边界上，则这个约束条件称为在某个约束边界上，则这个约束条件称为X X的的起作起作用约束用约束X X不在某个约束边界上，则这个约束条件称为不在某个约束边界上，则这个约束条件称为X X的不的不起作用约束起作用约束现代设计方法现代设计方法起作用约束起作用约束设计点设计点X X(k)(k)的所有起作用约的所有起作用约束的函数序号下标集合用束的函数序号下标集合用I Ik k表示，即表示，即现代设计方法现代设计方法一般形式：一般形式：4.4.优化设计的数学模型优化设计的数学模型现代设计方法现代设计方法 用用“maxmax、minmin”表表 示示 极极 大大、极极 小小 化化，用用“s.ts.t”表表示示“满满足足于于”，“m m、p p”表表示示不不等等式式约约束与等式约束的个数，则表示如下形式：束与等式约束的个数，则表示如下形式：现代设计方法现代设计方法 本本课课程程中中，所所有有的的优优化化设设计计问问题题都都是是求求目目标标函函数数的的极极小小值值。遇遇到到求求极极大大值值的的问问题题，则则先先通通过过转化变成极小值问题。转化变成极小值问题。与此同时，所有的不等式约束都采用与此同时，所有的不等式约束都采用的形式。的形式。现代设计方法现代设计方法5.优化设计问题的求解优化设计问题的求解（1）图解法）图解法 【例例3】求解下列优化问题：求解下列优化问题：现代设计方法现代设计方法最优解是等值线在函最优解是等值线在函数值下降方向上与可数值下降方向上与可行域的最后一个交点。行域的最后一个交点。现代设计方法现代设计方法【例例4】求解下列优化问题：求解下列优化问题：现代设计方法现代设计方法最优解是等值线在最优解是等值线在函数值下降方向上函数值下降方向上与可行域的最后一与可行域的最后一个交点。个交点。现代设计方法现代设计方法非线性问题的最优解要么是一个内点，要么是非线性问题的最优解要么是一个内点，要么是一个边界点；一个边界点；非线性问题的最优解如果是一个边界点，那么非线性问题的最优解如果是一个边界点，那么它必定是等值线（面）在函数值下降方向上与它必定是等值线（面）在函数值下降方向上与可行域的最后一个交点；可行域的最后一个交点；线性问题的最优解必定是等值线（面）在函数线性问题的最优解必定是等值线（面）在函数值下降方向上与可行域的最后一个交点；值下降方向上与可行域的最后一个交点；一般情况下：一般情况下：现代设计方法现代设计方法（2 2）数值迭代法）数值迭代法数值迭代法的基本思想：数值迭代法的基本思想：从一个初始点从一个初始点 出发，按照一个出发，按照一个可行的搜索方向可行的搜索方向和和适当的步长适当的步长走一步，到达走一步，到达 ，再从，再从 出发，出发，选一个可行的搜索方向和适当的步长走一步，达到选一个可行的搜索方向和适当的步长走一步，达到 ，并保证每一步函数值都是下降的，即必须满足，并保证每一步函数值都是下降的，即必须满足 （这称为新点的（这称为新点的适用性适用性），这样一步一步地重复，这样一步一步地重复进行数值计算，直至达到目标函数的极小点。进行数值计算，直至达到目标函数的极小点。现代设计方法现代设计方法无约束优化问题无约束优化问题初始点初始点 用某种优化方法确定用某种优化方法确定 确定前进步长确定前进步长 计算计算 检查检查 若不满足则改变步长，若不满足则改变步长，满足则进入下一步满足则进入下一步从从 出发出发 用某种优化方法确定用某种优化方法确定 确定前进步长确定前进步长 计算计算 检查检查 若不满足则改变步长，若不满足则改变步长，满足则进入下一步满足则进入下一步从从 出发出发 用某种优化方法确定用某种优化方法确定 确定前进步长确定前进步长 计算计算 检查检查 若不满足则改变步长，若不满足则改变步长，满足则进入下一步满足则进入下一步从从 出发出发 用某种优化方法确定用某种优化方法确定 确定前进步长确定前进步长 计算计算 检查检查 若不满足则改变步长，若不满足则改变步长，满足则进入下一步满足则进入下一步现代设计方法现代设计方法第第k k个迭代点个迭代点从第从第k k个迭代点出发寻找下一个迭代个迭代点出发寻找下一个迭代点的搜索方向点的搜索方向沿沿 前进的步长前进的步长基本迭代公式基本迭代公式现代设计方法现代设计方法 由于每次迭代求得的新点均为使函数值有所下由于每次迭代求得的新点均为使函数值有所下降的适用点（如果不是适用点，可改变方向和步长降的适用点（如果不是适用点，可改变方向和步长另行搜索适用点），则所得各点必将逐步向该函数另行搜索适用点），则所得各点必将逐步向该函数的极小值点逼近，最后总可求得非常接近该函数理的极小值点逼近，最后总可求得非常接近该函数理论最优点的近似最优点论最优点的近似最优点 。现代设计方法现代设计方法2 2）约束优化问题）约束优化问题 对于约束优化问题，除了检查每个新点的适对于约束优化问题，除了检查每个新点的适用性外，还要检查其用性外，还要检查其可行性可行性，即是否满足，即是否满足 的约束条件，如果适用性和可行性兼备，再进行的约束条件，如果适用性和可行性兼备，再进行下一次迭代，最终自然也能求得非常接近约束最下一次迭代，最终自然也能求得非常接近约束最优点的近似最优点优点的近似最优点 。现代设计方法现代设计方法 综上所述，采用数值法进行迭代求优时，除了综上所述，采用数值法进行迭代求优时，除了选择初始点选择初始点 以外，如何确定迭代方向以外，如何确定迭代方向 和步长和步长 成为非常重要的环节，他们将直接决定着搜索的成为非常重要的环节，他们将直接决定着搜索的效率、函数值逐步下降的稳定性和优化过程所需的效率、函数值逐步下降的稳定性和优化过程所需的时间等。时间等。现代设计方法现代设计方法A.A.点距准则点距准则 根据相邻两迭代点根据相邻两迭代点 与与 间的距离足够小间的距离足够小而建立的准则，点距准则可表示为而建立的准则，点距准则可表示为或 数值迭代终止准则（计算精度数值迭代终止准则（计算精度 的确定）的确定）现代设计方法现代设计方法B.B.值差准则值差准则 根据相邻的两迭代点的函数值下降量足够小而根据相邻的两迭代点的函数值下降量足够小而建立的准则。建立的准则。绝对下降量准则：绝对下降量准则：相对下降量准则：相对下降量准则：现代设计方法现代设计方法C.C.梯度准则梯度准则 根据迭代点的函数梯度达到足够小而建立的准根据迭代点的函数梯度达到足够小而建立的准则，表示为则，表示为或或现代设计方法现代设计方法迭代法必须要解决的三个问题迭代法必须要解决的三个问题u 迭代算法具有收敛性；迭代算法具有收敛性；u 在收敛性前提下，选择比较好的初始点在收敛性前提下，选择比较好的初始点X(0)和适宜的和适宜的终止判据及收敛精度终止判据及收敛精度 ；u 选取使目标函数值下降较快的迭代探索方向选取使目标函数值下降较快的迭代探索方向 S(k)和最和最优的迭代步长优的迭代步长(k)，确保较快的收敛速度。，确保较快的收敛速度。如何确定如何确定S(k)、(k)优化方法优化方法 现代设计方法现代设计方法3.2 3.2 优化设计的数学分析基础优化设计的数学分析基础优化设计的本质：求极值。优化设计的本质：求极值。1.1.函数的泰勒展开函数的泰勒展开 为便于对多变量问题进行数学分析和求解，往往需为便于对多变量问题进行数学分析和求解，往往需要采用线性函数和二次函数替代简化目标函数。要采用线性函数和二次函数替代简化目标函数。（1 1）一元函数的）一元函数的f(X)泰勒展开：泰勒展开：若若f(x)在含有在含有x(0)处的某处的某个开区间内直到（个开区间内直到（n+1阶可导，只要开区间（）阶可导，只要开区间（a,b）足）足够小够小,则该函数在则该函数在（a,b）内）内x(0)点点处的二阶泰勒展开式为：处的二阶泰勒展开式为：现代设计方法现代设计方法（2）二元函数）二元函数f(x1，x2)的泰勒展开：的泰勒展开：现代设计方法现代设计方法现代设计方法现代设计方法（3）多元函数）多元函数f(x1，x2,xn)的泰勒展开：的泰勒展开：现代设计方法现代设计方法（3）多元函数）多元函数f(x1，x2,xn)的泰勒展开：的泰勒展开：:目标函数目标函数f(x)在点在点x(0)的所有一阶偏导数组成的的所有一阶偏导数组成的矩阵向量矩阵向量(一阶导数矩阵向量或梯度）一阶导数矩阵向量或梯度）:目标函数目标函数f(x)在点在点x(0)的所有二阶偏导数组成的的所有二阶偏导数组成的矩阵矩阵(二阶导数矩阵或海色矩阵，记作二阶导数矩阵或海色矩阵，记作H(x)），），nn阶对称矩阵阶对称矩阵现代设计方法现代设计方法2.2.目标函数极值的存在性目标函数极值的存在性优化设计的首要工作是判断极值的存在性，如不存在极优化设计的首要工作是判断极值的存在性，如不存在极值，优化设计无意义。值，优化设计无意义。（1 1）无约束无约束目标函数极值的存在性目标函数极值的存在性目标函数为一元函数目标函数为一元函数 f(x)f(x)在点在点x(0)(0)处有极值的充要条件为：处有极值的充要条件为：时，有极小值；时，有极小值；时，有极大值。时，有极大值。现代设计方法现代设计方法一元函数的极值点一元函数的极值点极小值点极小值点0 xyy=f(x)x00 xyy=f(x)x00yy=f(x)x0极大值点极大值点不存在极值点不存在极值点现代设计方法现代设计方法目标函数为多元函数目标函数为多元函数 f(x1，x2,xn)f(X)在点在点X(0)处有极值的充要条件为：处有极值的充要条件为：（必要条件）（必要条件）（充分条件）（充分条件）正定正定时，有极小值；时，有极小值；（必要条件）（必要条件）（充分条件）（充分条件）负定负定时，有极大值；时，有极大值；现代设计方法现代设计方法【例例 5】试证明函数试证明函数 在点在点 处具有极小值。处具有极小值。解：解：将将 代入得代入得H(X(0)正定，目标函数在（正定，目标函数在（2,4）处具有极小值。）处具有极小值。现代设计方法现代设计方法（2）目标函数的凸性）目标函数的凸性 目标函数的极值点一般是相对于它附近的局部区目标函数的极值点一般是相对于它附近的局部区域中的各点而言的，目标函数在其整个可行区域中，域中的各点而言的，目标函数在其整个可行区域中，有时可能存在有时可能存在许多个极值点许多个极值点，优化设计时应力求找到，优化设计时应力求找到多个极值点中的最小值点多个极值点中的最小值点，即，即全局最优点或整体最优全局最优点或整体最优点点，其它非最小值的极值点称为，其它非最小值的极值点称为局部最优点局部最优点或或相对最相对最优点优点。凸性：凸性：单峰性单峰性，目标函数若为凸性，极值点只有一个，目标函数若为凸性，极值点只有一个，即为全局最优点。即为全局最优点。现代设计方法现代设计方法凸集：凸集：假设在假设在n维欧式空间维欧式空间 Rn 中有一个集合中有一个集合D，即，即 ，若，若D内任意两点内任意两点X(1),X(2)之间的连接直线都属于集合之间的连接直线都属于集合D,则则D为为n维欧式空间内的一个维欧式空间内的一个凸集凸集，否则为否则为非凸集非凸集。如果将如果将X(1),X(2)之间的连接直线用之间的连接直线用 表表达，则凸集的数学表达式为：达，则凸集的数学表达式为：若若则则现代设计方法现代设计方法x2x1x(2)x(1)x2x1x(2)x(1)凸集凸集非凸集非凸集凸集的几何特征凸集的几何特征：其任意两点连线上的一切点都位于这个几何内。其任意两点连线上的一切点都位于这个几何内。现代设计方法现代设计方法凸函数：凸函数：凸函数的数学表达式为：凸函数的数学表达式为：f(x)x2x1xf(x2)f(x1)现代设计方法现代设计方法判断函数判断函数f(x)为为凸函数的充要条件：凸函数的充要条件：方法方法1：若函数若函数f(x)在在D上具有上具有一阶的连续导数一阶的连续导数，对任意，对任意两点两点x(1),x(2),f(x)为凸函数的充要条件是为凸函数的充要条件是:恒成立恒成立方法方法2：若函数若函数f(X)在在D上具有上具有二阶的连续导数二阶的连续导数，则，则f(X)为凸函数的充要条件是为凸函数的充要条件是:H(X)处处半正定处处半正定 凸性形态表现为凸性形态表现为下凸下凸时，函数为时，函数为凸函数凸函数；凸性表；凸性表现为现为上凸上凸时，函数为时，函数为凹函数凹函数。现代设计方法现代设计方法 凸规划凸规划 对于非线性规划对于非线性规划 若其中若其中 f(x)和和 gu(x)均为凸函数（对于均为凸函数（对于 ，约束为凹函数），则这样的规划问题称为约束为凹函数），则这样的规划问题称为凸规划凸规划。现代设计方法现代设计方法（3）有约束目标函数极值的存在性）有约束目标函数极值的存在性 目标函数有约束极值还是无约束极值，主要取决目标函数有约束极值还是无约束极值，主要取决于约束条件对极值和极值点的影响。同样的目标函数于约束条件对极值和极值点的影响。同样的目标函数对于不同的约束条件，可能出现不同的最优值和最优对于不同的约束条件，可能出现不同的最优值和最优点，其原因在于不同的约束条件限制了设计变量不同点，其原因在于不同的约束条件限制了设计变量不同的取值范围。的取值范围。有约束最优问题需要解决的问题有约束最优问题需要解决的问题u 判断约束极值点存在的条件；判断约束极值点存在的条件；u 判断找到的极值点是全局最优点还是局部最优点。判断找到的极值点是全局最优点还是局部最优点。现代设计方法现代设计方法A.A.无约束最优点为可行域的无约束最优点为可行域的内点，此时目标函数的最内点，此时目标函数的最优点就是约束问题的最优优点就是约束问题的最优点；点；约束最优点和无约束最优点的相互关系：约束最优点和无约束最优点的相互关系：现代设计方法现代设计方法B.B.无约束最优点在可行域外，无约束最优点在可行域外，约束问题的最优点是约束约束问题的最优点是约束边界上的一点，该点是约边界上的一点，该点是约束边界与目标函数一条等束边界与目标函数一条等值线（面）的切点；值线（面）的切点；现代设计方法现代设计方法【例例6 6】用用K KT T条件判断点条件判断点 是否是下列约是否是下列约束优化问题的约束极值点。束优化问题的约束极值点。现代设计方法现代设计方法解：在点解：在点 X*=2 0T处起作用的约束为处起作用的约束为 g1(X)、g2(X)，相关函数在点相关函数在点 X*处的梯度为处的梯度为现代设计方法现代设计方法由于由于 1=2=0.5 满足满足K-T条件，所以点条件，所以点X*=2 0T为全域最优点。为全域最优点。现代设计方法现代设计方法对于等式约束问题对于等式约束问题 等式约束的极值条件等式约束的极值条件可以建立拉格朗日函数可以建立拉格朗日函数 现代设计方法现代设计方法这就是等式约束问题在点这就是等式约束问题在点X*取得极值的必要条件，取得极值的必要条件，它的含义是：它的含义是：在等式约束问题的极值点上，目标函数的负梯在等式约束问题的极值点上，目标函数的负梯度等于诸约束函数在该点梯度的线性组合。度等于诸约束函数在该点梯度的线性组合。现代设计方法现代设计方法对于不等式约束问题对于不等式约束问题 不等式约束的极值条件不等式约束的极值条件可以通过引入可以通过引入m m个个松弛变量松弛变量将不等式约束变成等式约束将不等式约束变成等式约束现代设计方法现代设计方法然后类似地建立拉格朗日函数然后类似地建立拉格朗日函数 现代设计方法现代设计方法现代设计方法现代设计方法以上两点可以统一用一个条件来表示：以上两点可以统一用一个条件来表示：现代设计方法现代设计方法K-TK-T（Kuhn-Tucker)Kuhn-Tucker)条件：条件：现代设计方法现代设计方法满足满足K-T条件条件的点称为的点称为K-T点点。对于一般对于一般非线性规划问题非线性规划问题，K-T点一定是点一定是约束极值点约束极值点，但却不一定是但却不一定是全域最优点全域最优点。一般采用。一般采用多初始点多初始点下的极下的极值点是否都值点是否都逼近同一点逼近同一点（可看成最优点）的近似方法（可看成最优点）的近似方法来判别。来判别。但是，对于但是，对于目标函数目标函数为为凸函数凸函数，可行域为凸集可行域为凸集的的凸规凸规划划问题，问题，K-T点点一定是一定是全域最优点全域最优点。现代设计方法现代设计方法3.3 3.3 一维探索优化方法一维探索优化方法 一维搜索的数学形式一维搜索的数学形式 一维搜索的几何意义一维搜索的几何意义 常用一维搜索方法常用一维搜索方法：进退法进退法 黄金分割法黄金分割法 现代设计方法现代设计方法一、概述一、概述数值迭代过程中，任何一次迭代，总是从某个已数值迭代过程中，任何一次迭代，总是从某个已知点知点 出发，沿着给定的方向出发，沿着给定的方向 （用某种优化（用某种优化方法确定）搜索到目标函数在该方向上的极小值方法确定）搜索到目标函数在该方向上的极小值点点 ，这个过程称为一维搜索。，这个过程称为一维搜索。一维搜索不仅可以求解一维优化问题，同时也是一维搜索不仅可以求解一维优化问题，同时也是求解多维优化问题的基本步骤。求解多维优化问题的基本步骤。1.1.一维搜索的概念一维搜索的概念 怎么理解怎么理解“一维一维”的含义？的含义？现代设计方法现代设计方法对对“一维一维”的理的理解解寻找目标函数在指定方向上的极小点，在计算上寻找目标函数在指定方向上的极小点，在计算上就是从就是从 沿沿 前进多少的问题，即求步长因子前进多少的问题，即求步长因子 的问题。从这个意义上讲，一维搜索是一个求的问题。从这个意义上讲，一维搜索是一个求解关于解关于 的单元目标函数的过程。的单元目标函数的过程。一维搜索一维搜索寻找合适的寻找合适的 ，使，使 最小最小“一维一维”是指是指 “一个方向一个方向”（）；现代设计方法现代设计方法任一次迭代，都是求任一次迭代，都是求使得使得即即其中：其中：表示步长因子表示步长因子 表示最优步长因子表示最优步长因子2.2.一维搜索的数学形式一维搜索的数学形式 现代设计方法现代设计方法3.3.一维搜索的几何意义一维搜索的几何意义 从从 出发，沿方向出发，沿方向 一一维搜索，就是求维搜索，就是求方向方向 与与等值线的切点等值线的切点，此时的步长，此时的步长因子即为最优步长因子。因子即为最优步长因子。现代设计方法现代设计方法4.4.单峰区间单峰区间 对于所有的一维搜索方法，对于所有的一维搜索方法，首先遇到的共同问题是：如何首先遇到的共同问题是：如何确定一个确定一个初始搜索区间初始搜索区间，使该，使该区间内区间内含有函数的极小点含有函数的极小点，且，且在该区间内函数有在该区间内函数有唯一的极小唯一的极小点点 ，这个初始搜索区间就，这个初始搜索区间就是单峰区间。是单峰区间。现代设计方法现代设计方法 设函数设函数f(x)在区间在区间 内有定内有定义，且义，且(1)(1)在区间内存在极小点在区间内存在极小点 ，即有，即有 (2)(2)区间区间 上的任意上的任意x，均满足，均满足 ；区间；区间上的任意上的任意x，有，有 用解析法给单峰区间下一个定义：用解析法给单峰区间下一个定义：则称闭区间则称闭区间 为函数为函数f(x)的的单峰区间单峰区间。现代设计方法现代设计方法单峰区间的特点：单峰区间的特点：单峰区间内，在极小点的左边，函数是严格减少单峰区间内，在极小点的左边，函数是严格减少的，在极小点的右边，函数是严格增加的；的，在极小点的右边，函数是严格增加的；如果区间如果区间 是一个单峰区间，是一个单峰区间，x是区间内的一是区间内的一点，则点，则 两个不等式中必有两个不等式中必有一个成立；一个成立；单峰区间内的函数图形表现为单峰区间内的函数图形表现为“高低高高低高”的的形态。形态。应用这一特征可以确定单峰区间。应用这一特征可以确定单峰区间。现代设计方法现代设计方法如果函数具有多个极小点，则表现为多峰函数。此如果函数具有多个极小点，则表现为多峰函数。此时，需要对变量取值范围进行适当的划分，使每一时，需要对变量取值范围进行适当的划分，使每一个子空间只包含一个极小点，才能进行一维搜索。个子空间只包含一个极小点，才能进行一维搜索。一维搜索时，同样需要在每个子空间内寻找单峰区一维搜索时，同样需要在每个子空间内寻找单峰区间。间。注意注意：现代设计方法现代设计方法假设第假设第k k次得到的区间次得到的区间 ，若，若 ，则可取则可取 作为极小点。作为极小点。5.5.一维搜索的基本思想一维搜索的基本思想 一维搜索就是要在初始单峰区间中求单峰函数的一维搜索就是要在初始单峰区间中求单峰函数的极小点。所以找初始单峰区间是一维搜索的第一极小点。所以找初始单峰区间是一维搜索的第一步，然后将初始单峰区间逐步缩小，直至包括极步，然后将初始单峰区间逐步缩小，直至包括极小点的区间长度小于给定的一个正数小点的区间长度小于给定的一个正数 ，此，此 称称为收敛精度或迭代精度。为收敛精度或迭代精度。现代设计方法现代设计方法缩小区间的区间消去法缩小区间的区间消去法 现代设计方法现代设计方法无论发生在那种情况，都将包含极小点的区间缩小，无论发生在那种情况，都将包含极小点的区间缩小，即可删去最左段或最右段，然后在保留下来的区间即可删去最左段或最右段，然后在保留下来的区间上做同样的处理，如此迭代下去，将使搜索区间逐上做同样的处理，如此迭代下去，将使搜索区间逐步减小，直到满足预先给定的精度（终止准则）时，步减小，直到满足预先给定的精度（终止准则）时，即获得一维优化问题的近似最优解。即获得一维优化问题的近似最优解。消去函数值大的消去函数值大的内分点到同一侧内分点到同一侧端点之间的区间端点之间的区间现代设计方法现代设计方法6.6.探索区间探索区间(初始单峰区间）初始单峰区间）的确定（的确定（2 2种方法）种方法）一维问题的探索方向是确定的，一维探索实际一维问题的探索方向是确定的，一维探索实际是求可行域内的是求可行域内的最优步长最优步长 (k),使目标函数值达到最小使目标函数值达到最小，首先必须确定首先必须确定包含最优点的可行域包含最优点的可行域 s,e。现代设计方法现代设计方法（1）外推法）外推法 外推法的基本思想是选取步长外推法的基本思想是选取步长=h,2h,4h，并计算相应的并计算相应的X(k)+h,X(k)+2h,X(k)+4h,然后分别计然后分别计算各点目标函数值，通过比较目标函数值确定初始单峰算各点目标函数值，通过比较目标函数值确定初始单峰区间。区间。h 的估计值根据下式选取的估计值根据下式选取:当当 时，时，试验步长试验步长 h=K；否则取；否则取 S S 是通过某种优化方法已经确是通过某种优化方法已经确定的目标函数值下降方向定的目标函数值下降方向现代设计方法现代设计方法将将 分别代入分别代入目标函数计算。目标函数计算设设 为函数值为函数值下降的最后一点下降的最后一点，为为数值上升的第一点数值上升的第一点，则单峰区间可定义为：，则单峰区间可定义为：现代设计方法现代设计方法（2）进退法）进退法 包含最优点包含最优点的单峰区间的单峰区间 s,e内，目标函数值内，目标函数值呈现呈现“大大小小大大”的的U字形字形。假设假设 (1)(2)f(2)f(k)+h)，则将，则将步长增加一倍步长增加一倍(2h)；得到下得到下一个点一个点(k)+3h。比较相邻三点函数值：比较相邻三点函数值：如果如果 f(k)+h)f(k)+3h)，则探索区间，则探索区间 s,e为为(k),(k)+3h 否则，再将步长增加一倍，重复上述运算。否则，再将步长增加一倍，重复上述运算。前进方向前进方向现代设计方法现代设计方法 后退算法：后退算法：将将(k)和和(k)+h代入目标函数，如果代入目标函数，如果 f(k)f(k)，则探索区间，则探索区间 s,e 为为(k)-h,(k)+h，否则将步长加倍并按前进算法重复，否则将步长加倍并按前进算法重复上述运算。上述运算。后退方向后退方向现代设计方法现代设计方法【例例7 7】试用进退算法确定函数试用进退算法确定函数 的初始的初始搜索区间搜索区间 ，设初始点，设初始点 ，初始步长，初始步长h=1。采用不同的初始点、不同的初始步长得到的初采用不同的初始点、不同的初始步长得到的初始单峰区间可能不一样，但只要这个单峰区间始单峰区间可能不一样，但只要这个单峰区间包含极小点，就是正确的。包含极小点，就是正确的。现代设计方法现代设计方法 1.Fibonacci法（分数法）法（分数法）F(0)=F(1)=1,F(n)=F(n-1)+F(n+1)(n2)Fibonacci法是按照上式产生的法是按照上式产生的Fibonacci数数F(n)，确定，确定缩短率缩短率(n)=1/F(n)采用采用Fibonacci数列确定区间内计算点的位置及所对应数列确定区间内计算点的位置及所对应的缩短率的缩短率 (n)，迭代步骤如下：，迭代步骤如下：二、一维搜索方法二、一维搜索方法现代设计方法现代设计方法1）按照缩短率按照缩短率 (n)小于相对精度小于相对精度 ，计算点的个数，计算点的个数n。2）选出计算点，第一次时按照以下公式选取两个计算选出计算点，第一次时按照以下公式选取两个计算点，并根据它们的函数值大小确定新区间及下一步该点，并根据它们的函数值大小确定新区间及下一步该继承的点。继承的点。进而求出点的个数进而求出点的个数 n。现代设计方法现代设计方法如果如果 f(2(0)f(1(0)，则探索区间，则探索区间 s(0),e(0)缩缩短为短为 s(0),2(0)，同时，同时 2(1)=1(0)；如果如果 f(2(0)f(1(0)，则探索区间，则探索区间 s(0),e(0)缩缩短为短为 1(0),e(0)，同时，同时 1(1)=2(0)；现代设计方法现代设计方法3）按照下面的迭代公式进行下一次迭代，并进行按照下面的迭代公式进行下一次迭代，并进行与与2）完全相同的判断和操作。）完全相同的判断和操作。现代设计方法现代设计方法如果如果 f(2(k)f(1(k)，则探索区间，则探索区间 s(k-1),e(k-1)缩缩短为短为 s(k-1),2(k)，同时，同时 2(k+1)=1(k)；如果如果 f(2(k)f(1(k)，则探索区间，则探索区间 s(k-1),e(k-1)缩缩短为短为 1(k),e(k-1)，同时，同时 1(k+1)=2(k)；4）判断）判断迭代次数迭代次数 k 是否等于是否等于n，如果成立，则终止，如果成立，则终止迭代，否则按迭代，否则按3）继续下一次的迭代。）继续下一次的迭代。现代设计方法现代设计方法（2）0.618法（法（黄金分割法）黄金分割法）采用采用固定的缩短率固定的缩短率 。Fibonacci法与法与0.618法缩短率之间的关系法缩短率之间的关系现代设计方法现代设计方法2.黄金分割法黄金分割法1)1)基本原理基本原理 对于目标函数对于目标函数f(x)，在区间，在区间a,b内，适当插入两个内，适当插入两个内分点内分点x1和和x2(x1 f(x2)时，极小点必在时，极小点必在x1,b中；中；当当f(x1)f(x2)时，极小点必在时，极小点必在a,x2中。中。现代设计方法现代设计方法黄金分割法要求在区间黄金分割法要求在区间a,b中插入的两点位置是对中插入的两点位置是对称的，如图所示，称的，如图所示，ax1=x2b。设区间长为。设区间长为L，插入的，插入的两个点把区间分成较长的一段两个点把区间分成较长的一段和较短的一段和较短的一段(L )，如图所示，如图所示，这样，无，这样，无论删去那一段，保留的区间长度总是论删去那一段，保留的区间长度总是，在每次迭，在每次迭代中，整个区间的长度代中，整个区间的长度与较长一段长度的比等于与较长一段长度的比等于较长一段长度与较短长度的比。较长一段长度与较短长度的比。现代设计方法现代设计方法现代设计方法现代设计方法2 2）黄金分割法的迭代步