智能纺织品优化设计.ppt

第1章优化设计 优化是使用专门的方法来确定最优的成本 并对某一问题或某一过程的设计进行有效求解的方法 在进行工业决策时 这一技术是主要的定量分析工具之一 在纺织厂以及许多其它工业工程的设计 建设 操作和分析中所涉及的大部分问题均可使用优化方法进行求解 1 1引言 1 1 1概述 在人类活动中 要办好一件事 指规划 设计等 都期望得到最满意 最好的结果或效果 为了实现这种期望 必需有好的预测和决策方法 方法对头 事半功倍 反之则事倍功半 优化方法就是各类决策方法中普遍采用的一种方法 优化设计应用的发展历史 经历了由怀疑 提高认识到实践收效 从而引起广大工程界日益重视的过程 从国际范围看 早期设计师习惯于传统设计方法和经验设计 传统设计由于专业理论和计算工具的限制 设计者只能根据经验和判断先制定设计方案 随后再对给定的方案进行系统分析和校核 往往要经几代人的不断研制 实践和改进 才能使某类产品达到较满意的程度 由于产品设计质 量要求日益提高和设计周期要求日益缩短 传统设计已越来越显得不能适应工业发展的需要 设计师为了掌握优化设计方法 需要在优化理论 建模和计算机应用等方面进行知识更新 70年代到80年代 计算机价格大幅度下降 年轻一代设计师茁壮成长 优化设计应用的诱人威力 市场竞争日益激化 作为产品开发和更新的第一关如何极大地缩短设计周期 提高设计质量和降低设计成本已成为企业生存的生命线 从 从而引起广大企业和设计师的高度重视 特别是CAD CAM以及CIMS 计算机集成制造系统 的发展 使优化设计成为当代不可缺少的技术和环节 用优化设计方法来改造传统设计方法已成为竞相研究和推广并可带来重大变革的发展战略 优化设计在设计领域中开拓了新的途径 在纺织工艺过程设计和工厂操作中的典型问题有很多 也许是无限多 求解方法 优化是在各种高效定量分析方法中找到一个最优的方法 计算机及其相关软件的发展使计算变得可行而且更加有效 近年来 为了普及和推广应用优化技术 已经将各种优化计算程序组成使用十分方便的程序包 并已发展到建立最优化技术的专家系统 这种系统能帮助使用者自 动选择算法 自动运算以及评价计算结果 用户只需很少的优化数学理论和程序知识 就可有效地解决实际优化问题 虽然如此 但最优化的理论和计算方法至今还未十分完善 有许多问题仍有待进一步研究探索 可以预测 随着现代技术的迅速发展 最优化技术必将获得更广泛 更有效的应用 它也必将达到更完善 更深刻的进展 1 1 2优化的作用 为什么工程师对优化感兴趣呢 用优化的方法做出的决策比直接决策可以多得到多少效益呢 工程师们的工作是改进设备的初始设计 并且对已经安装使用的设备尽可能地强化其操作性能 以达到产量最大 成本最小 能耗最小等目的 在工厂操作中 一部分效益来自于工厂操作性能的提高 例如增加高价值产品的产量 或减少污染物的产量 降低能耗 提高过程的效率 延长开工时间 优化还能降低维护费用 减少设备损耗 并提高人员的利用率 此外 还有无形的效益来自于工厂操作者 工程师和管理人员之间的相互配合 系统地识别一个过程或生产线的目标 约束和自由度是非常有益的 它可以产生如下效益 如改进设计的质量 更快更确切地发现并解决问题以及更快地做出决定 由于在过程模型中所用的数据和数学表达式存在一些不确定性 因此对于优化的应用是否有风险 仍存在着争论 当然 这样的争论是有益的 工程师们在把优化技术用于一些问题时必须做出某种判断 这些问题中含有与其相关的 不确定的 但是值得考虑的问题 即必须从精确和实用两个观点来考虑问题 这是因为工厂的操作参数和周围的环境并非一成不变 在某些情况下 会在确定优化的同时加入某些统计的特征去分析产量预测的不确定程度 这可能是一种可行的分析方法 当过程模型是理想的 且对输入和使用的参数仅仅知道一个大概时 必须慎重对待优化的结果 它可以提供优化的上限 另一种对优化设计中不确定性参数影响的评价方法是敏感性分析 通常 过程变量的优化值是不随给定的参数而变化的 敏感性较差 因此 具有确切值的参数并不是寻找优化条件的关键 1 1 3优化的范围和层次 优化可以应用在一个公司的任意层次上 其应用范围包括复杂的组合车间 某个车间内分布的设备 单个装置及某个装置中的子系统 甚至更小的个体 优化问题存在于任何层次上 因而 优化问题可以包括整个公司 某一个车间 一个过程 单个的单元操作 单元操作中的某个装置或者其中的某个中间系 统 而其分析的复杂性则包括只能了解大致的特征或者只能检查到瞬间的详情 这依赖于所设定的结果 可供利用的精确数据和进行优化所需的时间 在一个典型的工厂中 优化可用于管理 过程设计和装置规范 车间操作等 由于轻纺工厂的复杂性 要对一个指定的工厂进行彻底的优化 工作量是很大的 不能进行彻底优化时 常常会依赖于 不完全优化 这是一种特殊的 子优化 变形 子优化是一种操作或一个问题的某一方面进行的优化 在优化中忽略了一些因素 这些因素对工厂的系统或过程有着直接或间接的影响 由于以下原因 子优化通常是很必要的 这些原因有的是考虑了经济性和实用性 有的则是由于时间或人员的限制 以及急于得到答案的难度等 当建立问题存在难度 或者没有现成的技术可以得到全部问题的合理解时 子优化通常是很有用的 在大多数实际情况下 子优化至少提供了一个合理的技术以达到最优 不过 各个子优化的元素没有必要保证使整个系统达到全局最优 子系统目标可能与全局目标并不一致或不吻合 1 2纺织最优化设计概念 纺织的最优化设计 就是在一定的加工条件下 在对加工工艺 加工设备以及产品的性态或其它因素的限制 约束 范围内 选取某些设计变量 设计实验方案 建立目标函数并使其获得最优值的一种新的设计方法 设计变量 目标函数和约束条件这三者在设计空间 以设计变量为坐标轴组成的实空间 的几何表示中构成设计问题 优化设计的一般过程可以用图1 1来表示 相对于常规设计来说 最优化设计是一次革新 图1 1优化设计的一般过程 1 2 1设计变量和目标函数 1设计变量 在设计过程中进行选择并最终必需确定的各项独立参数 称为设计变量 在选择过程中它们是变量 但这些变量一旦确定以后 设计对象也就完全确定 最优化设计是研究怎样合理地优选这些设计变量值的一种现代设计方法 在纺织加工中 常用的独立参数有工艺参数 设备与零部件的规格 原材料的力学和物理特性 产品的规格性能等等 在这些参数中 凡是可以根据设计要求事先给定的 则不是设计变量 而称为设计常量 只有那些需要在设计过程中优选的参数 才可看成是最优化设计中的设计变量 设计变量的数目称为最优化设计的维数 如有n个设计变量 则称为n维设计问题 只有两个设计变量的二维设计问题可用图1 2所示的平面直角坐标表示 有三个设计变量的三维设计问题可用图1 3所表示的空间直角坐标表示 在图1 2中 当设计变量 分别取不同值时 则可得到在坐标平面上不同的相应点 每一个点表示一种设计方案 如果用向量表示这个点 即为二维向量 1 1 同样 在图1 3中 每一个设计方案表示为三维空间的一个点 并可用三维向量来表示该点 1 2 图1 2二维设计问题 图1 3三维设计问题 在一般情况下 若有个设计变量 把第个变量记为 则其全部设计变量可用维向量的形式表示成 1 3 这种以个独立变量为坐标轴组成的维向量空间是一个维实空间 用表示 如果其中任意两向量又有内积运算 则称维欧式空间 用表示 当向量中的各分量都是实变量则称决定了维欧氏空间中的一个点 并用符号表示 在最优化设计中由各设计变量的坐标轴所描述的这种空间就是所谓的 设计空间 它是一个重要概念 图1 3给出了一个具有三个设计变量的设计空间 决定这个空间的三个坐标轴分别描述三个设计变量 通常 设计变量的个数要比3多得多 并且很难用图象表示 这时的维空间又称为超越空间 设计空间中的一个点就是一种设计方案 如图1 4所示 图1 4在三变量 三维 设计空间中设计方案的探索 设计空间中的某点是由各设计变量所组成的向量决定的 点决定了一种设计方案 另一种设计方案点 1 则由另一种设计变量所组成的向量确定 最优化设计中常采用的直接探索法 或称直接搜索法 就是在相邻的设计点间做一系列定向的设计改变 移动 由点到点 1 间的典型移动情况可由下式给出 1 4 向量决定移动的方向 标量决定移动的步长 设计空间的维数表征了设计的自由度 设计变量愈多 则设计的自由度愈大 可供选择的方案愈多 设计愈灵活 但难度愈大 求解亦愈复杂 一般 含有2 10个设计变量的为小型设计问题 10 50个为中大型设计问题 50个以上的为大型设计问题 目前已经解决200个设计变量的大型最优化设计问题 在纺织中的工艺优化问题 基本上都是小型设计问题 2目标函数 在最优化设计中 可将所追求的设计目标 最优指标 用设计变量的函数形式表达出来 这一过程称为建立目标函数 目标函数是设计中预期要达到的目标 它表达为各设计变量的函数表达式 1 5 它代表设计的某项最重要的特征 例如上面所提到的加工工艺 设备规格 原料和产品的性能以及成本等 目标函数是设计变量的标量函数 最优化设计的过程就是优化设计变量使目标函数达到最优值 或找到目标函数的最小值 或最大值 的过程 在最优化设计问题中 可以只有一个目标函数 称为单目标函数 如式 1 5 所示 当在同一设计中要提出多个目标函数时 这种问题称为多目标函数的最优化问题 在一般的纺织最优化设计中 多目标函数的情况较多 设计的综合效果愈好 但问题的求解亦愈复杂 对于多目标函数 可以将它们分别独立地列出来 1 6 也可以把几个设计目标综合到一起 建立一个综合的目标函数表达式 即 1 7 实验中 目标函数中的某些单目标函数之间可能存在着矛盾 这时用一个目标函数表示多目标函数 表示所要求特性的加权和 把多目标函数转化成单目标函数求解 目标函数为 1 8 表示j项指标的加权因子 加权因子是个非负系数 由设计者根据该项指标在最优化设计中所占的重要程度等情况选定 所选择的各项指标的加权因子 应能客观的反映该项最优化设计所追求的总目标 使总目标的综合效果达到最优 1 2 2约束条件和可行域 如前所述 目标函数取决于设计变量 而在很多实际问题中设计变量的取值范围是有限制的或必需满足一些条件 在最优化设计中 这种对设计变量的取值时的限制条件 称为约束条件或设计约束 约束条件可以用数学等式或不等式来表示 不等式约束的形式为或 其中 式中为不等式约束的数目 等式约束 表示等式约束数应少于设计变量数 等式约束对设计变量的约束很严 起着降低设计自由度的作用 在优化设计中 由于引入了约束条件 因此只有满足约束条件的设计方案 才是可行的设计方案 从几何概念看一个不等式约束条件 把设计空间划分为两部分 一部分满足约束条件即 另一部分不满足约束条件即 两部分的分界线 或面 即称为约束线 或面 如图1 5所示的二维设计平面中可以直观理解这个概念 在约束线不满足约束条件的一侧画阴影线表示这部分不符合约束要求 图1 5约束线 在设计空间中 满足设计要求的一切约束所构成的空间 称为可行域 在可行域中 任一点都是可行点 当设计变量均为连续变量时 可行点有无穷多个 优化设计过程就是在可行域中沿着目标函数值不断改善的方向去搜索出最好的解 优化方法的巧妙和威力就是用有限次搜索找出最好点 这种点称最优点或最优解 用表示 如图1 6所示 a b c d 图1 6可行域的几种情况 1 2 4最优化设计的数学模型 选取设计变量 列出目标函数 给定约束条件后构造最优化设计的数学模型 如前所述 任何一个最优化问题均可归结为如下的描述 即在满足给定的约束条件 决定维空间中的可行域 下 选取适当的设计变量 使其目标函数达到最优值 其数学表达式 数学模型 为 求设计变量 在满足约束条件 的条件下 使目标函数达到最优值 目标函数的最优值一般可用最小值 或最大值 的形式来表示 因此 最优化设计的数学模型可简化表示为 1 9 数学模型的建立 既可以用理论推导的方法 也可以用实验的方法 现举例说明建立数学模型的过程 例1 1要用薄木板制造一体积为5的存放成品的货箱 由于存放的货物要求其长度不小于2 为了使耗费的木板最少并减少质量 问应如何选取货箱的长 宽和高 解显然 木板的耗费量与货箱的表面积成正比 如果货箱不带上盖 则目标函数为 约束条件为 所以其数学模型为 如有一个等式约束 则原则上可以消去一个设计变量 当然 这时被消去的那个设计变量必需以显示的形式表达出来 在上述问题中 由等式约束条件得 代入目标函数后原问题的数学模式可简化为 即设计变量由三个减为两个 事实上 当和确定后 根据等式条件 即可确定 建立最优化设计的数学模型以后 即可选择合适的最优化方法解题 求目标函数的最优解 1 3优化方法的数学基础 1 3 1方向导数和梯度 1方向导数 偏导数是沿平行于坐标轴的多个特殊方向的变化率 对于函数沿任意给定方向的变化率 则需采用方向导数的概念 该二元函数 由点 沿着与 轴正向夹角 的 方向S变到点 如 图1 7所示 于是函数的增量为 点到的距离 则在点沿S方向的方向导数为 1 10 可见 方向导数是函数在某点沿给定方向的变化率 可看成偏导数的推广 即 1 11 得 1 12 式中 S的方向余弦 三元函数的函数情况 若S方向与各坐标轴方向间夹角分别为 则函数 在点沿S方向的方向导数为 1 13 多元函数的方向导数可写为 1 14 式中 某方向S的n个方向角 例1 2设目标函数 求在 点沿S方向的方向导数 向量S的 方向为 解由于 故 可见 如果 取不同的值而 点不变 则方向导数的值不同 2梯度 方向导数描述函数在某点给定方向的变化率 一般在同点的不同方向函数的变化率不同 寻优要使路程最短 那么 哪个方向上的变化率最大 如何找到 下面引入梯度的概念 梯度是函数 对各个设计变量的偏导数所 组成的列向量 并以符号 或 表示 即 1 15 梯度方向是指函数值增长最快的方向 梯度的模 为 即函数的最大变化率 沿方向函数值的变化率最大 即可最速上升 沿方向函数值的变化率最小 即可最速下降 目标函数等值线上某点的法线方向即为函数某点的梯度方向 例1 3求函数 在点 和点 的梯度 解由定义知 点 的梯度为 如图1 8所示 同心圆方案是函数 的等值线 图1 8梯度的求法 在点 作与 轴夹角成 的向量 就是该点的梯度 梯度方向是等值线上该点切线的法线方向 点 的梯度为 表明在的梯度为0 即为函数的极值点 若函数在某点有极值 则该点的梯度为0 1 3 2多元函数的泰勒公式及Hessian矩阵 目标函数为一元函数时 在点附近若存在1到n 1阶导数 则可展开成如下泰勒公式 1 16 用简单函数在对原函数作局部逼近 若取前二项 展开式 即用一直线逼近 若取展开式的前三项则表示用曲线逼近 对二元函数同样可以展开成泰勒公式 设目标函数在点附近的泰勒公式 若只取到二次项时为 0 1 17 写成向量矩阵形式 1 18 可简写为 1 19 式中 函数在点的梯度列向量 这是函数在点的二阶偏导数矩阵 称Hessian为矩阵 用表示 为对称矩阵 即2 2阵 n元函数的Hessian矩阵可写为 1 20 n元函数有n个变量 所以它的Hessian矩阵是n n对称矩阵 n元函数的泰勒展开式为 1 21 泰勒展开式对讨论多元函数的极值问题很方便 如果已找到 使 1 22 只能说是多元函数的驻点 不知道是否是极值点 更不知道是极大点还是极小点 但因为 故有 表达式 的右半部为二次型函数 此式说明要判别一个函数的驻点是极大点还是极小点 可以通过判别一个特定二次型是正定还是负定来决定 多元函数用泰勒公式展开式作局部逼近 取到二次项时 函数为二次型 多元函数用泰勒展开式作局部逼近 当取到二次项时 函数为二次型 因此在求目标函数的最优解时 常把某一给定点函数近似地用二次函数代替 使分析问题简化 1 3 3二次型函数及正定矩阵判别 二次型是指含有n个变量的二次齐次多项式 写成矩阵形式 令 则上式记为 若式中 为常系数 则称为二 次型函数或实二次型 A称为二次型矩阵 因为 所以 则A称为对称矩阵 因此二次型矩阵都是对称矩阵 正定判别 若A阵左上角的主子行列式全大于零 则A正定 反之 若A正定 A阵左上角的主子行列式全大于零 二次型函数的一些性质 1 非零向量X 若 是正定的 2 非零向量X 若 是负定的 1 3 4多元函数的极值 对于多元函数 有极值的必要条件是梯度 根据的条件可求点的具体值 但是还无法确定是极值还是驻点 即使是极值还不能断定是极大值还是极小值 这时用泰勒展开二次型 多元目标函数在驻点附近 用泰勒公式的二次项近似表示 则有 在点的领域内 若对一切有 或 则点 为极小点 当 则点为极大点 当 当 则点为鞍点 也可以由Hessian矩阵 由二次型系数构成 判定 当正定 为极小 当负定 为极大 当不定 为鞍点 正定的充要条件为矩阵A的顺序主子式取全大于零 例1 4如有函数 试求极值点 并判断性质 解1 先求解驻点 得到 即驻点 1 1 2 再利用Hessian矩阵判断驻点是否为极值点 二阶偏导 于是Hessian矩阵为 多阶主子式为 即Hessian矩阵为正定 故驻点 1 1 是极小值点 故函数的极小值 1 3 5函数的凸性以及凸函数的判别条件 函数有单峰函数和多峰函数 因此求得极值点无法判定是全域还是局部最优解 需通过研究凸性来解决 凸性这个概念在优化理论和应用中非常有用 1一元函数凸性 设一元函数 若函数曲线上任意两点的连线 永远不在曲线的下面 如图1 9 a 所示 则函数称为凹函数 相反则称为凸函数 如图1 9 b 所示 a b 图1 9函数的凸性概念 上面的曲线均有 1 23 或 这是线段的表达式 当时 当时 所以在0 1范围 凸函数的表达式为 1 24 2多元函数的凸性 设为n维欧氏空间中的一个集合 若其中任意两点 之间连线上所有的点都在这个集合中 则称这种集合为n维欧氏空间的一个凸集 图1 10 a 是二维空间的一个凸集 而 b 不是凸集 a 凸集 b 非凸集 图1 10二维空间的凸集与非凸集 设是上的函数 如果对任何实数对上的任意两点恒有 1 25 则函数就是定义在凸集上的一个凸函数 上式若不带 为 则为严格凸函数 3凸函数的判别条件 1 若函数在上具有连续一阶导数 而又是内部的一个凸集 则为上凸函数的充要条件是 不等式 恒成立 2 若函数在上具有连续二阶导数 而又是内部的一个凸集 则为上的凸函数的充要条件是 的Hessian矩阵 二阶导矩阵 为半正定 用Telan二次项展开式近似表达 对任意Telan展开式为 即 由判断条件可知上式左边应大于或等于零 必需使 即此二次型应为半正定 即Hessian矩阵为半正定 若Hessian矩阵为正定 既上式换为 则为严格的凸函数 例1 5某纺织厂的技术经济分析简化而得的目标函数为 判断此函数是否为凸函数 解利用Hessian矩阵判别 只要证明其Hessian矩阵是非负定即可 将 代入Hessian矩阵 得 该Hessian矩阵的各阶主子式的值为 故Hessian矩阵为正定 所以为严格的凸函数 注意 对于高阶多元目标函数 很难判断是否为凸函数 另外 目标函数也常常是多极值函数 所以求得的极值点不一定是全局点 1 4一维优化方法 1 4 1概述 对一维 也称一元或单变量 函数寻求其极值点就是一维优化方法中限制最优解问题 称一维搜索方法 搜索方法是数学迭代解法 它把搜索范围不断缩小向最优点逼近 当满足收敛准则后 即可求得最优解 在设计空间中选定一个初始设计点 然后从这一点出发 按照某一优化方法所规定的原则 确定初始搜索方向 沿这个方向寻求最优步长 得一个目标函数值有所改进的设 计点 然后以点作为新的始点 再构造此点的新的搜索方向 求新的最优步长 求得改进的设计点 重复这种过程 得到目标函数值不断改进的点列 等点 最后可以达到满足所规定的收敛准则或终止准则要求的理论最优点的近似最优点 这种寻找最优点的反复过程称为数值迭代方法 迭代过程的每一步格式 一般可以写成如下形式 式中 第k步迭代点 即优化过程中所达到的第k次设计点 从第k次设计点出发的搜索方向 从第k次设计点出发 沿方向进行搜索的最优步长 从第k次设计点出发 以为步长沿方向进行搜索所得到的新点 一维搜索方法包括分析方法 微分法 和数值迭代法 数值迭代法又分为直接法 黄金分割法和对分法 和间接法 不需要求导数的二次插值法和需要求导数的三次插值法 1 4 2单峰函数 在给定区间内仅有一个极小点的函数称单峰函数 图1 11为单峰函数的几种情况 图1 11三种单峰函数 1 必位于内 放弃段 将搜索区间缩为 2 必位于内 放弃段 将搜索区间缩为 3 当在内 将搜索区间缩为 下面介绍初始单峰区间的确定及算法 在这里我们只介绍一种方法 进退法 也称外推法 是一种通过比较函数值大小来确定单峰区间的方法 任意给定初始点和步长h 算出和点的函数值 若 说明 将步长增加一倍 取 见图1 12 a 若 说明 需改变寻查方向 即将步长符号改为负 得点 见图1 12 b 以此类推 直至函数值增加为止 图1 12进退法确定单峰区间 若 则将步长再加大一倍 有 图1 12 a 或 图1 12 b 即每跨一步的步长为前一次步长的2倍 直至函数值增加为止 如图1 12 a 中有 则单峰区间为 对于图1 12 b 有 则单峰区间为 利用进退法 一般总可找到单峰区间中的3个点 即2个端点和中间某一个点 对于后面要介绍的二次插值法中要利用3个点的信息 其他方法只要利用2个端点信息 1 4 3黄金分割法 黄金分割法也称0 618法 是通过对黄金分割点函数值的计算和比较 将初始区间逐次进行缩小 直到满足给定的精度要求 即求得一维极小点的近似解 已知的单峰区间为 为了缩小区间 在内按一定规则对称地取2个内部点和 并计算和 可能有三种情况 如图1 13所示 图1 13黄金分割法 图1 13 a 经过一次函数比较 区间缩小一次为 a x2 在新的区间内 保留一个好点和 下一次只需再按一定规则 在新区间内找另一个与对称的点 计算 与比较 如此反复 图1 13 b 淘汰 产生新的单峰区间 x b 图1 13 c 可归纳入上面任一种情况处理 黄金分割法的关键是如何不断找出区间内的2个对称点 保证极小点不会丢掉 且收敛快 设初始区间长度为l 第一次区间缩短率为 则缩短后的区间长度为 第二次区间缩短时 在区间中取点 经比较后又得新区间 由对称性可知 区间的长度为 则本次区间缩短率为 令这两次缩短率相等 即 使方程 1 26 解方程 得合理的根为 由此可知 黄金分割法的均匀缩短率为0 618 即每经过一次函数值比较 都是淘汰本次区间的0 382倍 根据上式 黄金分割法的取点规则是 1 27 1 28 为了使最终区间收敛到给定收敛精度内 区间的缩短次数N必需满足 1 29 即 1 30 由于实际问题的需要和函数形态的不同 常常需要不同的收敛准则确定最优点 对于直接法 有以下几种收敛准则 1 区间绝对精度 2 区间相对精度 3 函数值绝对精度 4 函数值相对精度 黄金分割法特点 1 不必要求可微 只要利用函数值大小的比较 即可很快地找到 2 除了第一次缩小区间要计算两个点及其函数值以外 其余每次只要计算一个点及其函数值 3 可靠性好 黄金分割法可应用到染色等众多过程中 例如在其它条件不变的情况下 优选乳化剂的加入量或水的合适加入量等 例1 6假设某厂为生产一种含有特殊香味得毛织物 现决定在原毛染色中加入某种香型材料 假设其参考添加量为0 1 0 15 现通过试验确定其最佳添加量 解按黄金分割法安排试验 先在含优区间 0 1 1 5 的0 618处取值做第一试验点 则该试验得第一次试验点为 第二试验点为 比较两次试验效果 若好于 则舍去不包括点的以外部分 在留下部分再找出点的对称点 上述试验点的过程如图1 14所示 图1 14第一 第二 第三试验点确定的示意图 比较第二次和第一次试验的结果 如果仍是第一次的试验效果好 则去掉以外的部分 在留下的至区间内继续找出的对称点作为第四试验点 如果点比点的试验效果好 则舍去到这一段 在留下的部分内继续找出的对称点 为第五试验点 见图1 15 图1 15第四 第五试验点确定的示意图 按同样的方法继续下去 直到获得满意的试验效果为止 如果在上述试验中的效果比还好 并且比较满意 则可确定香料的添加量为0 76 是最优添加量 1 4 4对分法 1中心对分法 中心对分法是利用目标函数的一阶导数来判别最优点的存在区间 利用目标函数的一阶导数 取中心对分点 由目标函数的正负 淘汰区间的一半 如图1 16所示 已知 而 故淘汰区间 a x1 留下区间 x1 b 令趋于 再取 求 直至 则有 图1 16中心对分法求解图 对分法特点 一阶可微 且每计算一次 可淘汰区间的一半 收敛很快 当用于无目标函数式的优化试验时 每试验一次要判别下一次试验应淘汰的区间 2两点对分法 已知极小点区间 a b 在其中点左右取2个对称点x1和x2 见图1 17 且有 图1 17两点对分法求解图 1 31 1 32 其中为一个小的正值 应使有明显差异 如图情况 淘汰区间 留下区间 即 令 重复上述过程 直至 方法特点 不要求一阶可微 但每淘汰一次区间需计算2个点及其目标函数值 每次可淘汰本次区间的将近一半 其大小取决于值 可用于有目标函数的设计和无目标函数的优化试验中 例1 7 已知初始极限值 区间 a b 0 0 1 0 收敛精度要求在初始区间的10 以内 即 解法一用古典极值法 即求导方法 由 解得 故x 为极大点 解法二用中心对分法 已知 由x1 a b 2 0 5 可淘汰区间 0 0 5 留下区间 0 5 1 计算x2 0 5 1 0 2 0 75 故精确解x 0 75 f x 0 5625 解法三用两点对分法 已知L0 1 0 取 0 001 计算x1和x2 因为f2 f1 淘汰 0 0 4995 留下新区间 0 4995 1 0 第二次计算点为 因为 淘汰 0 4995 x3 留下新区间 x3 1 0 第三次计算点为 因为 淘汰 留下新区间 此时 已接近 要求精度 取最终区间的中点x 0 74925 0 875125 2 0 8121875作为近似极大点 f x 0 558632715 方法比较 解法一仅需计算一次导数 即可求得精确解 解法二计算了2次导数 求得了精确解 解法三计算了6次目标函数 取最后区间的中点作为近似极大点 与精确解比较 尚有较大误差 可见解法三的计算次数多 但不要求可微 1 4 5二次插值法 二次插值法是多项式逼近法的一种 利用目标函数在若干点的信息和函数值 构成一个与目标函数相接近的低次插值多项式 然后求该多项式的最优解作为原函数的近似最优解 随着区间的逐次缩小 多项式的最优点与原函数最优点之间的距离逐渐缩小 直到满足一定精度要求时终止迭代 设目标函数f x 在三点上的函数值分别为 二次插值多项式为 多项式在插值点的函数值应与目标函数的函数值相等 满足 1 33 求得 1 34 为求极小点 将3个系数代入插值多项式 令一阶导数为零 有 1 35 将 1 34 中的b c代入式 1 35 1 36 式中 由于初始区间较大 第一次构造的多项式极小点的近似解是达不到预期精度的 需要通过几次逼近计算来缩小区间 使构造的点列不断接近目标函数的极小点 区间缩小的原则如图1 18所示 图1 18二次插值区间缩小的四种情况 1 以 为新区间 令 x1 x2不变 2 以 为新区间 令 x3不变 3 以 为新区间 令 x1不变 4 以 为新区间 令 x2 x3不变 二次插值法收敛准则 1 相继两次的二次插值函数极小点 之间距离小于给定精度时 即 及 2 及 上述两种形式实际上是绝对精度和相对精度 二次插值法特点 1 二次插值法只要求连续 不要求其一阶可微 2 收敛速度比黄金分割法快 但可靠性不如黄金分割法好 程序也较长 3 如p x 的相邻两个迭代点重合 则产生死循环 1 5无约束最优化方法和约束最优化方法 1 5 1无约束最优化方法概述 1研究无约束优化方法的意义 对于一个n维目标函数 如果在没有任何限制条件下寻求它的极小点 称无约束极小化问题或无约束优化问题 数学上表达为 大量实际问题都是有约束的 研究无约束优化方法的意义在于 1 一类功能很强 使用方便的有约束优化方法 往往能将有约束问题转化成无约束问题 易于采用无约束优化方法求解 2 有些问题在不很接近最优解时可先作无约束问题求解 然后采用有约束方法求出最优解 3 有些实际问题本身是无约束的 或把有些约束问题经过模型变换可以转化为无约束问题求解 4 对于多维无约束问题来说 古典极值理论中令一阶导数为零 但要求二阶可微 且要判断Hessian矩阵为正定才能求得极小点 这种方法有理论意义 但无实用价值 和一维问题一样 若多元函数F X 不可微 亦无法求解 但古典极值理论是无约束优化方法发展的基础 2多维无约束优化方法的分类 目前已研究出很多种无约束优化方法 它们的主要不同点在于构造搜索方向上的差别 概括起来 可分为直接法和间接法两大类 其详细分类如表1 1所示 1 5 2坐标轮换法 1方法概述 坐标轮换法的基本构思是将一个n维优化问题转化为依次沿n个坐标方向反复进行一维搜索问题 这种方法的实质是把n维问题的求优过程转化为对每个变量逐次进行一维求优的循环过程 每次一维搜索时 只允许个变量的一次改动 其余 n 1 个变量固定不变 故坐标轮换法也常称单变量法或变量交错法 2迭代过程 1 任选初始点 搜索方向 2 以为初始点 沿e1作正向试探性移步 步长取 若试探成功 沿此方向一维搜索 否则 沿坐标的负方向试探 若正负方向试探均失败 则迭代点不动 转入下一步 3 以为沿e2方向作为一维搜索的新起点 按步骤 2 进行 得点 以此类推 进行完一轮一维搜索后 得 4 以作为第二轮的初始点 重复步骤 2 和 3 得第二轮搜索的终点 相继进行第三 第四轮等的搜索 5 如果从某轮的起始点出发 依次沿n个坐标轴的正负方向试探均失败 则缩短初始试探步长 返回 2 当初始步长缩减到足够小 满足时 迭代终止 3方法特点 1 计算量少 程序简单 但计算效率较低 特别在维数很高时很费机时 故仅适用于n较少 n 10 的目标函数求优 2 改变初始点重新迭代 可避免出现病态 4算法盒图见图1 19 图1 19坐标轮换法算法盒图 例1 8坐标轮换法求目标函数 的无约束最优解 初始点 解第一轮轮迭代 1 沿向一维搜索 2 求 求得 以为新起点 沿方向一维搜索 求 同理得到 3 判别 继续进行第二轮迭代计算返回到1 重复循环 1 5 3鲍威尔法 鲍威尔法是以共轭方向为基础的收敛较快的直接法之一 是一种十分有效的算法 在无约束方法中许多算法都是以共轭方向作为搜索方向 它具有许多特点 根据构造共轭方向的原理不同 可以形成不同的共轭方向法 1共轭方向法的概念 1 定义 设A为n阶对称正定矩阵 若有两个n维矢量S1和S2 满足 则称矢量S1和S2对矩阵A共轭 共轭矢量的方向称共轭方向 即S1和S2是在A度量意义下的正交 可见 S1和S2本来不相交 而与S1正交 与S2正交 若A E 则有 变成直角坐标方向 即对单位矩阵E的正交 推广到n个n维矢量的情形 设有n个不为零的n维不同矢量 如满足下面的两个条件 则称n个n维矢量是对A共轭的 2 共轭方向与函数极小点的关系 设有一般二维二次正定函数 其等直线是同心椭圆族 见图1 20 图1 20同心椭圆族特性 从出发 沿S1方向作一维搜索 得最优点 与椭圆相切 再从另一初始点出发 仍沿S1方向作一维搜索 得最优点 也与椭圆相切 设与连线的方向为S2 则S2必过椭圆族的中心 即X 点 且S1和S2必与A正交 2搜索方向 1964年 鲍威尔提出这种算法 其基本思想是用迭代点的目标函数值来构造共轭方向 然后从任一初始点开始 逐次沿共轭方向作一维搜索求极小点 并在以后的实践中进行了改进 其具体构造过程如下所述 任选初始点 然后与坐标轮换法一样 分别沿坐标方向e1 e2 en作一维搜索 依次求得近似极小点 每作完一次搜索 连接初始点和最后一个点构造新的方向 并判断是否要替换原来的某一方向 3迭代过程 1 任选初始点 给定精度 k 1 取初始方向组为坐标单位矢量 即 2 沿诸方向作n次一维搜索 依次确定各最优步长 使 得到点列 3 收敛准则判断 若或对于所有i 1 2 n满足则迭代结束 否则转下一步 4 计算各点的函数值 并找出相邻两点函数值之差最大者 以标记 即 及与之对应的两个点和 并以表示该两点的连线所指方向 5 计算映射点 及函数值 判断 是否成立 若两者或其中之一成立 则转入下步 否则转入步骤 7 6 令k k 1 计算新一轮的初始点和方向组为 并返回步骤 2 7 产生第n 1个新方向并在该方向上作一维搜索求最优步长 使 得此方向上的极小点 8 令 返回步骤 2 1 5 4最速下降法 梯度法 和共轭梯度法 1最速下降法 梯度法 1 方法概述 基本思想 任一点的负梯度方向是函数值在该点下降最快的方向 将n维问题转化为一系列沿负梯度方向 用一维搜索方法寻优的问题 利用负梯度作为搜索方向 故称最速下降法或梯度法 收敛准则为 2 迭代过程 1 任选初始点 给定收敛精度 2 求迭代点的负梯度方向 对迭代点 k 0 1 2 求的梯度 计算梯度的模 确定负梯度的单位向量 3 进行一维搜索 以为起点 沿方向作一维搜索求最优步长 使 于是得下一个迭代点 4 当迭代点满足收敛准则时 迭代结束 否则 令 返回步骤2 3 梯度法动态迭代图 见图1 21 图1 21梯度法动态迭代图 例1 9求 的极小值 初始点 收敛精度 解1 给定初始点 允差置 2 计算迭代点的梯度和方向 原函数梯度为 点的为 梯度的负方向为 3 最优步长因子 由迭代公式 令 求得 4 迭代计算 梯度模 5 判别 不满足精度要求 以 为起点 从2 重复 直到为止 2共轭梯度法 为克服梯度法中先快后慢之不足引入共轭梯度概念 共轭梯度法最早是由Fletcher和Reeves 1964 提出的 如果是二阶的 并且在每一个搜索方向上被准 确的最小化 那么它具有最多在次迭代中收敛的理想特性 这是因为它的搜索方向共轭 这种方法仅仅比最速下降法增大了很少的计算量 但却显示出较大的改进 它结合了当前梯度向量的信息以及前一次迭代的梯度向量信息 来求得一个新的搜索方向 可以利用当前梯度和原搜索梯度的线性组合来计算新的搜索方向 这种方法的优点是在每步计算中仅仅需要存储少量信息 所以能被应用到大型问题上 1 原理 利用目标函数的梯度确定共轭方向 使得计算简便而效果又好 设目标函数 1 37 其中 的二阶导数矩阵 是常数向量 是常数 在次迭代计算中从出发求 一维搜索 如图1 22所示 求最优步长因子 图1 22共轭梯度法的原理 在两点处函数的梯度分别为 两式相减为 1 38 为简便 令 所以 为使下一次搜索方向对A共轭 需有 代入 则得 1 39 由此式可见 它不含矩阵A 只要求出相应点得梯度 便可求得与共轭的方向 即共轭方向只与相邻两迭代点的梯度有关 2 共轭梯度方向的形成 若在第次迭代中点的负梯度已知 其方向为 则构成的共轭方向应满足 与 若为实对称矩阵 方向为共轭方向 则 令共轭方向表示成在迭代点的负梯度向量与前一迭代搜索方向两者的线性组合 即 1 40 式中 要使求出的与共轭 故称为共轭系数 共轭系数的求法 将 1 40 代入式 1 39 得 1 41 由于相邻两次迭代的负梯度方向与线性无关且正交 即 是一正交系 故有 或 1 42 式 1 41 可简化为 1 43 即 1 44 式中 分别为点 梯度的模 3 迭代步骤 1 任选初始点给定计算精度和输入维数 计算 令 取 2 用一维搜索求的最优解 即 并计算在处的梯度 3 终止判别 若迭代终止 否则转4 4 判别 是 则令并转1 否 若 转5 5 计算共轭方向 计算 6 令转2 4 共轭梯度法算法盒图 见图1 23 例1 10用共轭梯度法求函数 的最小值 解1 取 将代入 求 得 则 2 求 同前处理求得 特点 快 只求两点就找到 1 5 5阻尼牛顿法和DFP变尺度法 1阻尼牛顿法 1 方法概述 牛顿法是求函数极值的最古老算法之一 其基本思想是在点的邻域内用一个二次函数去近似替代原目标函数 然后求二次函数的极小点作为下一个迭代点 通过不断构造二次函数和迭代计算 使迭代点逼近函数的极小点 阻尼牛顿法是在原始牛顿法基础上进行修正 能保证每次迭代点的函数值都有所下降 2 阻尼牛顿法迭代过程 1 选一个好的初始点 给定收敛精度 令 2 计算的梯度方向 及其模 3 检验收敛准则 若 输出 否则转入下一步 4 计算点的 并求其逆矩阵 5 确定牛顿方向 并沿此方向作一维搜索求步长 使 6 计算迭代点 令k k 1 返回步骤2 3 方法特点 1 初始点应选在附近 有一定难度 2 尽管每次迭代都不会使函数值上升 但不能保证每次下降 3 若迭代点的Hessian矩阵为奇异 则无法求逆矩阵 不能构造牛顿方向 4 不仅要计算梯度 还要求海赛矩阵及其逆矩阵 计算量和存储量大 此外 对于二阶不可微的F X 也不适用 虽然阻尼牛顿法有上述缺点 但在特定条件下它具有收敛最快的优点 并为其他的算法提供了思路和理论依据 2DFP变尺度法 1 方法概述 梯度法的最大优点是初始点可任选 且开始几次迭代 目标函数值下降很快 其主要缺点是迭代点接近极小点时 对二次正定函数收敛也非常慢 牛顿法的最大优点是对二次正定函数迭代一次即收敛 但也有不少缺点 人们自然会想到 能否吸取这两种方法之长 努力克服它们 的缺点 来建立更好的算法 DFP变尺度法就是这样的算法之一 这种算法首先有戴维顿 Davidon 于1959年提出 又于1963年由弗莱彻 Fletcher 和鲍威尔加以发展和完善 成为现代公认的较好的算法之一 DFP法是基于牛顿法的思想又作了重要改进 这种算法仅用到梯度 不必计算海赛阵及其逆矩阵 但又能使搜索方向逐渐逼近牛顿方向 具有较快的收敛速度 2 迭代过程 1 任选初始点 计算收敛精度 维数n 2 给定变尺度矩阵初值 单位矩阵 令 置k 0 3 求探索方向和最优步长因子 4 进行一维搜索 求下一个迭代点 5 检验是否满足 若满足 则即为极小点 停止迭代 否则转下一步 6 检查迭代次数 若 则 转向步骤2 若则进行下一步 7 构造新的探索方向 为此应计算 然后令转步骤3 1 5 6线性规划 单纯形法 线性规划是应用最广的优化技术之一 也可以说是一种最有效的优化技术 目标函数和约束函数都是线性函数的最优化问题 称为线性规划或线性优化问题 线性规划是数学规划中的一个比较成熟的分支 在生产计划 工程预算和经济管理领域内应用十分广泛 同时 线性规划算法也可作为求解非线性有约束优化问题的子问题的工具 如可行方向法中可行方向的搜寻就是采用线性规划方法 下面是在工厂管理中出现的线性规划例子 1 按进度表安排员工 使一周中每天的劳动人数都很充足 并且要让工人的满意程度和劳动生产率尽可能的高 2 选择即将要生产的产品 充分利用现有的资源 并在当前的价格下获取最大的利润 3 找到一个工厂车间到仓库的分配模式 在有限的能力下使成本最小 4 在考虑到利润 竞争对手出标和操作约束条件的情况下 使竞标成功 当用数学语言表述时 所有这些问题都隐含了许多变量 等式和不等式 一个解决方案不仅要满足所有的约束条件 而且必须完成目标函数的极值要求 例如利润最大或成本最小 利用现代软件 可以建立并解决带有数千个变量和约束条件的线性问题 1线性规划的标准形式与解 线性规划的数学模型同样由设计变量 目标函数和约束条件组成 不过其中的约束条件除变量非负性限制外都采用等式约束 线性规划问题的一般形式为 1 45 其矩阵形式为 1 46 式中 AX B 约束方程 B 常数向量 A 系数矩阵 一般情况下 应有 因为当m n时约束方程只有一个惟一的解 不存在可供选择的其他解 不存在优化问题 当时 约束方程有无穷多组解 线性规划就是要从这无穷多组解中寻找一个使目标函数极小化的最优解 在线性规划的数学模型中 约束条件主要是等式约束 不等式约束仅限于变量的非负约束 对于其他形式的不等式约束 可以通过引入松弛变量的方法将其转化为等式约束 例如 对于约束条件 可通过引人松弛变量 变换为 如果原来问题中的某些变量并不要求非负 则可将其变换为两个非负变量之差 经过上述处理后 线性规划问题总能变换为式 1 32 或式 1 33 所示的线性规划的标准形式 例1 11某车间生产甲 乙两种产品 生产甲种产品每件需要材料9kg 3个工时 4kw电能 可获利60元 生产乙种产品每件需用材料4kg 10个工时 5kw电能 可获利120元 若每天能供应材料360kg 有300个工时 能供200kw电能 则每天生产甲 乙两种产品各多少件才能够获得最大的利润 设每天生产的甲 乙两种产品分别为 件 则此问题的数学模型如下 引入松弛变量 将其转换为标准形式 该问题的解如图1 24所示 在约束方程中 若令n m个变量为0 就可求得另外m个不全为0的解 于是这m个不全为0的解和n m个为0的解共同组成一个解向量 称为线性规划问题的基本解 其中m个不全为0的变量称为基本变量 其余n m个为0的变量称为非基本变量 在系数矩阵中 任取m列可以构成一个基本解 可知一个线性规划问题的基本解的个数等于排列组合数 图1 24二维线性规划问题的图解法 由图可以看出 线性规划的约束边界为一组直线或平面 由这些直线和平面构成的可行域是一个封闭的凸多边形或凸多面体 这个凸多边形或凸多面体的每一个顶点对应该线性规划问题的一个基本可行解 因此线性规划问题的最优解必定在这些顶点上取得 实际上 线性规划解法就是一种关于基本可行解的迭代算法 或者说是一种可行域顶点转换的算法 2基本可行解及其转换 既然线性规划问题的最优解必定在约束条件所围成的凸多边形或凸多面体的顶点上取得 而每一个顶点都 是线性规划问题的一个基本可行解 则线性规划问题的求解可归结为找出目标函数值下降的基本可行解的过程 这样 求解线性规划问题需要解决以下两个问题 基本可行解的求解 新的基本可行解应使目标函数有较大的下降 1 基本解及其转换 1 基本解的产生根据基本解的定义 对由系数矩阵和常数向量组成的如下增广矩阵 1 47 进行一系列初等变换 将其中系数矩阵的m列依次变为基向量时 满足约束方程的一个基本解便产生了 若经m次主元变换后 将增广矩阵的前m列变为如下单位子矩阵 1 48 约束方程变换为如下的正则方程 1 49 则 对应的基本解为 1 50 其中 前m个变量为基本变量 后n m个变量为非基本变量 若变换后的常数项均为非负 即 则此基本解是一个基本可行解 可见 得到一个基本解或基本可行解的方法 都是对增广矩阵进行高斯消元变换 消元变换的基本公式为 上式表明了对转轴变量以为转轴元素的转轴变换或消元变换 2 解的转换在式 1 48 的增广矩阵中 将某一非基本变量对应的任意一个系数作为转轴变换的转轴元素 进行另一次消元变换 又可得到一个新的增广矩阵和相应的基本