智能纺织品优化设计.ppt

《智能纺织品优化设计.ppt》由会员分享，可在线阅读，更多相关《智能纺织品优化设计.ppt（225页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第1 1章章 优化设计优化设计优化是使用专门的方法来确定最优的成本，并对某一问题或某一过程的设计进行有效求解的方法。在进行工业决策时，这一技术是主要的定量分析工具之一。在纺织厂以及许多其它工业工程的设计、建设、操作和分析中所涉及的大部分问题均可使用优化方法进行求解。2021/9/2111.1 引言引言1.1.1 概述概述 在人类活动中，要办好一件事（指规划、设计等），都期望得到最满意、最好的结果或效果。为了实现这种期望，必需有好的预测和决策方法。方法对头，事半功倍，反之则事倍功半。优化方法就是各类决策方法中普遍采用的一种方法。2021/9/212优化设计应用的发展历史，经历了由怀疑、提高认识

2、到实践收效，从而引起广大工程界日益重视的过程。从国际范围看，早期设计师习惯于传统设计方法和经验设计。传统设计由于专业理论和计算工具的限制，设计者只能根据经验和判断先制定设计方案，随后再对给定的方案进行系统分析和校核，往往要经几代人的不断研制、实践和改进，才能使某类产品达到较满意的程度。由于产品设计质2021/9/213量要求日益提高和设计周期要求日益缩短，传统设计已越来越显得不能适应工业发展的需要。设计师为了掌握优化设计方法，需要在优化理论、建模和计算机应用等方面进行知识更新。70年代到80年代，计算机价格大幅度下降，年轻一代设计师茁壮成长，优化设计应用的诱人威力，市场竞争日益激化，作为产品开

3、发和更新的第一关如何极大地缩短设计周期、提高设计质量和降低设计成本已成为企业生存的生命线，从2021/9/214从而引起广大企业和设计师的高度重视。特别是CAD/CAM以及CIMS（计算机集成制造系统）的发展，使优化设计成为当代不可缺少的技术和环节。用优化设计方法来改造传统设计方法已成为竞相研究和推广并可带来重大变革的发展战略，优化设计在设计领域中开拓了新的途径。2021/9/215 在纺织工艺过程设计和工厂操作中的典型问题有很多（也许是无限多）求解方法。优化是在各种高效定量分析方法中找到一个最优的方法。计算机及其相关软件的发展使计算变得可行而且更加有效。近年来，为了普及和推广应用优化技术，已

4、经将各种优化计算程序组成使用十分方便的程序包，并已发展到建立最优化技术的专家系统，这种系统能帮助使用者自2021/9/216动选择算法，自动运算以及评价计算结果，用户只需很少的优化数学理论和程序知识，就可有效地解决实际优化问题。虽然如此，但最优化的理论和计算方法至今还未十分完善，有许多问题仍有待进一步研究探索。可以预测，随着现代技术的迅速发展，最优化技术必将获得更广泛、更有效的应用，它也必将达到更完善、更深刻的进展。2021/9/2171.1.2 优化的作用优化的作用为什么工程师对优化感兴趣呢？用优化的方法做出的决策比直接决策可以多得到多少效益呢？工程师们的工作是改进设备的初始设计，并且对已经

5、安装使用的设备尽可能地强化其操作性能，以达到产量最大、成本最小、能耗最小等目的。2021/9/218在工厂操作中，一部分效益来自于工厂操作性能的提高，例如增加高价值产品的产量（或减少污染物的产量）、降低能耗、提高过程的效率、延长开工时间。优化还能降低维护费用，减少设备损耗，并提高人员的利用率。此外，还有无形的效益来自于工厂操作者、工程师和管理人员之间的相互配合。系统地识别一个过程或生产线的目标、约束和自由度是非常有益的，它可以产生如下效益，如改进设计的质量、更快更确切地发现并解决问题以及更快地做出决定。2021/9/219 由于在过程模型中所用的数据和数学表达式存在一些不确定性，因此对于优化的

6、应用是否有风险，仍存在着争论。当然，这样的争论是有益的。工程师们在把优化技术用于一些问题时必须做出某种判断，这些问题中含有与其相关的、不确定的、但是值得考虑的问题。即必须从精确和实用两个观点来考虑问题，这是因为工厂的操作参数和周围的环境并非一成不变。在某些情况下2021/9/2110会在确定优化的同时加入某些统计的特征去分析产量预测的不确定程度，这可能是一种可行的分析方法。当过程模型是理想的，且对输入和使用的参数仅仅知道一个大概时，必须慎重对待优化的结果，它可以提供优化的上限。另一种对优化设计中不确定性参数影响的评价方法是敏感性分析。通常，过程变量的优化值是不随给定的参数而变化的（敏感性较差）

7、。因此，具有确切值的参数并不是寻找优化条件的关键。2021/9/21111.1.3 优化的范围和层次优化的范围和层次优化可以应用在一个公司的任意层次上，其应用范围包括复杂的组合车间、某个车间内分布的设备、单个装置及某个装置中的子系统、甚至更小的个体。优化问题存在于任何层次上，因而，优化问题可以包括整个公司、某一个车间、一个过程、单个的单元操作、单元操作中的某个装置或者其中的某个中间系2021/9/2112统。而其分析的复杂性则包括只能了解大致的特征或者只能检查到瞬间的详情，这依赖于所设定的结果、可供利用的精确数据和进行优化所需的时间。在一个典型的工厂中，优化可用于管理、过程设计和装置规范、车间

8、操作等。2021/9/2113 由于轻纺工厂的复杂性，要对一个指定的工厂进行彻底的优化，工作量是很大的。不能进行彻底优化时，常常会依赖于“不完全优化”，这是一种特殊的“子优化”变形。子优化是一种操作或一个问题的某一方面进行的优化，在优化中忽略了一些因素，这些因素对工厂的系统或过程有着直接或间接的影响。由于以下原因，2021/9/2114子优化通常是很必要的，这些原因有的是考虑了经济性和实用性，有的则是由于时间或人员的限制，以及急于得到答案的难度等。当建立问题存在难度，或者没有现成的技术可以得到全部问题的合理解时，子优化通常是很有用的。在大多数实际情况下，子优化至少提供了一个合理的技术以达到最优

9、。不过，各个子优化的元素没有必要保证使整个系统达到全局最优。子系统目标可能与全局目标并不一致或不吻合。2021/9/21151.2 纺织最优化设计概念纺织最优化设计概念 纺织的最优化设计，就是在一定的加工条件下，在对加工工艺、加工设备以及产品的性态或其它因素的限制（约束）范围内，选取某些设计变量，设计实验方案，建立目标函数并使其获得最优值的一种新的设计方法。设计变量、目标函数和约束条件这三者在设计空间（以设计变量为坐标轴组成的实空间）的几何表示中构成设计问题。优化设计的一般过程可以用图1-1来表示。相对于常规设计来说，最优化设计是一次革新。2021/9/2116图1-1优化设计的一般过程202

10、1/9/21171.2.1 设计变量和目标函数设计变量和目标函数1设计变量在设计过程中进行选择并最终必需确定的各项独立参数，称为设计变量。在选择过程中它们是变量，但这些变量一旦确定以后，设计对象也就完全确定。最优化设计是研究怎样合理地优选这些设计变量值的一种现代设计方法。2021/9/2118在纺织加工中，常用的独立参数有工艺参数、设备与零部件的规格、原材料的力学和物理特性、产品的规格性能等等。在这些参数中，凡是可以根据设计要求事先给定的，则不是设计变量，而称为设计常量。只有那些需要在设计过程中优选的参数，才可看成是最优化设计中的设计变量。2021/9/2119设计变量的数目称为最优化设计的维

11、数，如有n个设计变量，则称为n维设计问题，只有两个设计变量的二维设计问题可用图1-2所示的平面直角坐标表示；有三个设计变量的三维设计问题可用图1-3所表示的空间直角坐标表示。2021/9/2120在图1-2中，当设计变量，分别取不同值时，则可得到在坐标平面上不同的相应点，每一个点表示一种设计方案。如果用向量表示这个点，即为二维向量（1-1）同样，在图1-3中，每一个设计方案表示为三维空间的一个点，并可用三维向量来表示该点（1-2）2021/9/2121图1-2二维设计问题图1-3三维设计问题2021/9/2122在一般情况下，若有个设计变量，把第个变量记为，则其全部设计变量可用维向量的形式表示

12、成（1-3）2021/9/2123 这种以 个独立变量为坐标轴组成的 维向量空间是一个 维实空间，用 表示，如果其中任意两向量又有内积运算，则称维欧式空间，用表示。当向量中的各分量都是实变量则称 决定了 维欧氏空间 中的一个 点，并用符号 表示。在最优化设计中由各设计变量的坐标轴所描述的这种空间 就是所谓的“设计空间”，它是一个重要概念。2021/9/2124图1-3给出了一个具有三个设计变量的设计空间。决定这个空间的三个坐标轴分别描述三个设计变量。通常，设计变量的个数要比3多得多，并且很难用图象表示，这时的维空间又称为超越空间。设计空间中的一个点就是一种设计方案，如图1-4所示。2021/9

13、/2125图1-4在三变量（三维）设计空间中设计方案的探索设计空间中的某点是由各设计变量所组成的向量 决定的，点 决定了一种设计方案，另一种设计方案点(+1)则由另一种设计变量所组成的向量 确定。2021/9/2126最优化设计中常采用的直接探索法（或称直接搜索法），就是在相邻的设计点间做一系列定向的设计改变（移动）。由点到点（+1）间的典型移动情况可由下式给出（1-4）向量决定移动的方向，标量决定移动的步长。2021/9/2127设计空间的维数表征了设计的自由度，设计变量愈多，则设计的自由度愈大、可供选择的方案愈多、设计愈灵活，但难度愈大、求解亦愈复杂。一般，含有210个设计变量的为小型设计

14、问题；1050个为中大型设计问题；50个以上的为大型设计问题。目前已经解决200个设计变量的大型最优化设计问题。在纺织中的工艺优化问题，基本上都是小型设计问题。2021/9/21282目标函数在最优化设计中，可将所追求的设计目标（最优指标）用设计变量的函数形式表达出来，这一过程称为建立目标函数。目标函数是设计中预期要达到的目标，它表达为各设计变量的函数表达式（1-5）它代表设计的某项最重要的特征，例如上面所提到的加工工艺、设备规格、原料和产品的性能以及成本等。2021/9/2129目标函数是设计变量的标量函数。最优化设计的过程就是优化设计变量使目标函数达到最优值，或找到目标函数的最小值（或最大

15、值）的过程。在最优化设计问题中，可以只有一个目标函数，称为单目标函数，如式（1-5）所示。当在同一设计中要提出多个目标函数时，这种问题称为多目标函数的最优化问题。在一般的纺织最优化设计中，多目标函数的情况较多，设计的综合效果愈好，但问题的求解亦愈复杂。2021/9/2130对于多目标函数，可以将它们分别独立地列出来（1-6）也可以把几个设计目标综合到一起，建立一个综合的目标函数表达式，即（1-7）2021/9/2131实验中，目标函数中的某些单目标函数之间可能存在着矛盾，这时用一个目标函数表示多目标函数，表示所要求特性的加权和。把多目标函数转化成单目标函数求解，目标函数为（1-8）2021/9

16、/2132表示j项指标的加权因子。加权因子是个非负系数，由设计者根据该项指标在最优化设计中所占的重要程度等情况选定。所选择的各项指标的加权因子，应能客观的反映该项最优化设计所追求的总目标，使总目标的综合效果达到最优。2021/9/21331.2.2 约束条件和可行域约束条件和可行域如前所述，目标函数取决于设计变量，而在很多实际问题中设计变量的取值范围是有限制的或必需满足一些条件。在最优化设计中，这种对设计变量的取值时的限制条件，称为约束条件或设计约束。约束条件可以用数学等式或不等式来表示。不等式约束的形式为 或 ，其中 ，式中 为不等式约束的数目。2021/9/2134等式约束 表示等式约束数

17、应少于设计变量数，等式约束对设计变量的约束很严，起着降低设计自由度的作用。在优化设计中，由于引入了约束条件，因此只有满足约束条件的设计方案，才是可行的设计方 案。从 几 何 概 念 看 一 个 不 等 式 约 束 条 件 ，把设计空间划分为两部分：2021/9/2135一部分满足约束条件即；另一部分不满足约束条件即；两部分的分界线（或面）即称为约束线（或面）。如图1-5所示的二维设计平面中可以直观理解这个概念，在约束线不满足约束条件的一侧画阴影线表示这部分不符合约束要求。图1-5约束线2021/9/2136在设计空间中，满足设计要求的一切约束所构成的空间，称称为为可可行行域域。在可行域中，任一

18、点都是可行点。当设计变量均为连续变量时，可行点有无穷多个。优化设计过程就是在可行域中沿着目标函数值不断改善的方向去搜索出最好的解。优化方法的巧妙和威力就是用有限次搜索找出最好点，这种点称最优点或最优解，用表示,如图1-6所示。2021/9/2137(a)(b)(c)(d)图1-6可行域的几种情况2021/9/21381.2.4 最优化设计的数学模型最优化设计的数学模型选取设计变量，列出目标函数、给定约束条件后构造最优化设计的数学模型。如前所述，任何一个最优化问题均可归结为如下的描述，即在满足给定的约束条件（决定维空间中的可行域）下，选取适当的设计变量，使使其其目目标标函函数数 达到最优值。其数

19、学表达式达到最优值。其数学表达式（数学模型数学模型）为：2021/9/2139求设计变量在满足约束条件的条件下，使目标函数达到最优值。2021/9/2140目标函数的最优值一般可用最小值（或最大值）的形式来表示，因此，最优化设计的数学模型可简化表示为（1-9）数学模型的建立，既可以用理论推导的方法，也可以用实验的方法，现举例说明建立数学模型的过程。2021/9/2141例例1-1要用薄木板制造一体积为5的存放成品的货箱，由于存放的货物要求其长度不小于2。为了使耗费的木板最少并减少质量，问应如何选取货箱的长、宽和高？解解 显然，木板的耗费量与货箱的表面积成正比，如果货箱不带上盖，则目标函数为20

20、21/9/2142约束条件为所以其数学模型为2021/9/2143如有一个等式约束，则原则上可以消去一个设计变量。当然，这时被消去的那个设计变量必需以显示的形式表达出来。在上述问题中，由等式约束条件得，代入目标函数后原问题的数学模式可简化为2021/9/2144即设计变量由三个减为两个，事实上，当和确定后，根据等式条件，即可确定。建立最优化设计的数学模型以后，即可选择合适的最优化方法解题，求目标函数的最优解。2021/9/21451.3 优化方法的数学基础优化方法的数学基础1.3.1 方向导数和梯度方向导数和梯度1 方向导数方向导数偏导数是沿平行于坐标轴的多个特殊方向的变化率。对于函数沿任意给

21、定方向的变化率，则需采用方向导数的概念。2021/9/2146该二元函数，由点沿着与轴正向夹角的方向S变到点，如图1-7所示。于是函数的增量为点 到 的距离 2021/9/2147则在点沿S方向的方向导数为（1-10）可见，方方向向导导数数是是函函数数在在某某点点沿沿给给定定方方向向的的变化率，变化率，可看成偏导数的推广。即：2021/9/2148（1-11）得（1-12）2021/9/2149式中 S的方向余弦三元函数的函数情况：若S方向与各坐标轴方向间夹角分别为，则函数在点沿S方向的方向导数为（1-13）2021/9/2150多元函数的方向导数可写为（1-14）式中，某方向S的n个方向角例

22、例1-2设目标函数求在 点沿S方向的方向导数，向量S的方向为 2021/9/2151解解 由于 故 可见，如果 取不同的值而 点不变，则方向导数的值不同。2021/9/21522梯度方向导数描述函数在某点给定方向的变化率。一般在同点的不同方向函数的变化率不同。寻优要使路程最短。那么，哪个方向上的变化率最大？如何找到？下面引入梯度的概念。梯度是函数梯度是函数 对各个设计变量的偏导数所对各个设计变量的偏导数所组成的组成的列向量列向量，并以符号，并以符号 或 表示，即2021/9/2153（1-15）梯度方向是指函数值增长最快的方向。梯度方向是指函数值增长最快的方向。梯度的模梯度的模为 即函数的最大

23、变化率。2021/9/2154沿方向函数值的变化率最大，即可最速上升；沿方向函数值的变化率最小，即可最速下降；目标函数等值线上某点的法线方向即为函数某点的梯度方向。例例1-3求函数在点 和点 的梯度。2021/9/2155解解 由定义知：点 的梯度为：如图1-8所示，同心圆方案是函数的等值线，图1-8梯度的求法2021/9/2156在点 作与轴夹角成 的向量就是该点的梯度。梯梯度度方方向向是是等等值值线线上上该该点点切切线线的法线方向。的法线方向。点 的梯度为 表明在的梯度为0，即为函数的极值点。若函数在某点有极值，则该点的梯度为若函数在某点有极值，则该点的梯度为0。2021/9/21571.

24、3.2 多元函数的泰勒公式及多元函数的泰勒公式及Hessian矩阵矩阵目标函数为一元函数时，在点附近若存在1到n+1阶导数，则可展开成如下泰勒公式（1-16）用简单函数在对原函数作局部逼近。若取前二项（展开式）即用一直线逼近，若取展开式的前三项则表示用曲线逼近。2021/9/2158对二元函数同样可以展开成泰勒公式。设目标函数在点附近的泰勒公式，若只取到二次项时为0（1-17）2021/9/2159 写成向量矩阵形式（1-18）2021/9/2160可简写为（1-19）式中，函数在点的梯度列向量2021/9/2161 这这是是函函数数在在点点 的的二二阶阶偏偏导导数数矩矩阵阵，称称Hessia

25、n为为矩矩阵阵，用表示。（为对称矩阵）即22阵。2021/9/2162n元函数的Hessian矩阵可写为（1-20）2021/9/2163n元函数有n个变量，所以它的Hessian矩阵是nn对称矩阵。n元函数的泰勒展开式为（1-21）泰勒展开式对讨论多元函数的极值问题很方便。如果已找到 ，使2021/9/2164（1-22）只能说 是多元函数的驻点，不知道是否是极值点，更不知道是极大点还是极小点。但因为，故有，表达式2021/9/2165的右半部为二次型函数，此式说明要判别一个函数的驻点是极大点还是极小点，可以通过判别一个特定二次型是正定还是负定来决定。多元函数用泰勒公式展开式作局部逼近，取到

26、二次项时，函数为二次型。2021/9/2166多元函数用泰勒展开式作局部逼近，当取到二次项时，函数为二次型。因此在求目标函数的最优解时，常把某一给定点函数近似地用二次函数代替，使分析问题简化。1.3.3 二次型函数及正定矩阵判别二次型函数及正定矩阵判别二二次次型型是是指指含含有有n个个变变量量 的的二二次齐次多项式次齐次多项式2021/9/21672021/9/2168写成矩阵形式2021/9/2169令 则上式记为若式中 为常系数，则称为二次型函数或实二次型实二次型。A称为二次型矩阵称为二次型矩阵。2021/9/2170因为，所以，则A称为对称矩阵，因此二次型矩阵都是对称矩阵。正正定定判判别

27、别：若A阵左上角的主子行列式全大于零，则A正定；反之，若A正定，A阵左上角的主子行列式全大于零。二次型函数的一些性质：（1）非零向量X，若，是正定的。（2）非零向量X，若，是负定的。2021/9/21711.3.4 多元函数的极值多元函数的极值对对 于于 多多 元元 函函 数数，有有 极极 值值 的的 必必 要要 条条 件件 是是 梯梯 度度 ，根据的条件可求点的具体值。但是还无法确定是极值还是驻点，即使是极值还不能断定是极大值还是极小值，这时用泰勒展开二次型。多元目标函数在驻点附近，用泰勒公式的二次项近似表示，则有2021/9/2172在点的领域内，若对一切有：或，则点为极小点。当，则点为极

28、大点。当当，则点为鞍点。也可以由Hessian矩阵（由二次型系数构成）判定：当正定，为极小；当负定，为极大；当不定，为鞍点。正定的充要条件为矩阵A的顺序主子式取全大于零。2021/9/2173例例1-4 如有函数试求极值点，并判断性质。解解1）先求解驻点。得到 即驻点（1，1）2021/9/21742）再利用Hessian矩阵判断驻点是否为极值点。二阶偏导于是Hessian矩阵为2021/9/2175多阶主子式为即Hessian矩阵为正定。故驻点（1，1）是极小值点，故函数的极小值。2021/9/21761.3.5 函数的凸性以及凸函数的判别条件函数的凸性以及凸函数的判别条件函数有单峰函数和多

29、峰函数，因此求得极值点无法判定是全域还是局部最优解，需通过研究凸性来解决。凸性这个概念在优化理论和应用中非常有用。1一元函数凸性设一元函数，若函数曲线上任意两点的连线，永远不在曲线的下面，如图1-9（a）所示，则函数称为凹凹函数，相反则称为凸函数，如图1-9（b）所示。2021/9/2177(a)(b)图1-9函数的凸性概念2021/9/2178上面的曲线均有：（1-23）或 这是线段的表达式。当 时，；当时，所以在01范围。凸函数的表达式为（1-24）2021/9/21792多元函数的凸性设为n维欧氏空间中的一个集合，若若其其中中任任意意两两点点，之之间间连连线线上上所所有有的的点点都都在在

30、这这个个集集合合中中，则则称称这这种种集集合合 为为n维维欧欧氏氏空空间间的的一一个个凸凸集集。图1-10(a)是二维空间的一个凸集，而(b)不是凸集。2021/9/2180(a)凸集(b)非凸集图1-10二维空间的凸集与非凸集2021/9/2181设是上的函数，如果对任何实数对上的任意两点恒有(1-25)则函数 就是定义在凸集 上的一个凸函数。上式若不带“”为“f1，淘汰0,0.4995，留下新区间0.4995,1.0。第二次计算点为：因为，淘汰0.4995,x3，留下新区间x3,1.0。2021/9/21113第三次计算点为：因为 ，淘汰 ，留下新区间 ，此时，已接近要求精度。2021/9

31、/21114取最终区间的中点x*(0.74925+0.875125)/2=0.8121875作为近似极大点，f(x*)=0.558632715。方方法法比比较较：解法一仅需计算一次导数，即可求得精确解。解法二计算了2次导数，求得了精确解。解法三计算了6次目标函数，取最后区间的中点作为近似极大点，与精确解比较，尚有较大误差。可见解法三的计算次数多，但不要求可微。2021/9/211151.4.5 二次插值法二次插值法 二次插值法是多项式逼近法的一种，利用目标函数在若干点的信息和函数值，构成一个与目标函数相接近的低次插值多项式，然后求该多项式的最优解作为原函数的近似最优解。随着区间的逐次缩小，多项

32、式的最优点与原函数最优点之间的距离逐渐缩小，直到满足一定精度要求时终止迭代。2021/9/21116设目标函数f(x)在三点上的函数值分别为，二次插值多项式为 多项式在插值点的函数值应与目标函数的函数值相等，满足：（1-33）2021/9/21117求得（1-34）为求极小点，将3个系数代入插值多项式，令一阶导数为零，有（1-35）2021/9/21118将（1-34）中的b、c代入式（1-35）（1-36）式中 由于初始区间较大，第一次构造的多项式极小点的近似解是达不到预期精度的，需要通过几次逼近计算来缩小区间，使构造的点列不断接近目标函数的极小点。区间缩小的原则如图1-18所示。2021/

33、9/21119图1-18二次插值区间缩小的四种情况（1），以为新区间，令 x1、x2不变；（2），以为新区间，令，x3不变；2021/9/21120（3），以为新区间，令，x1不变；（4），以 为新区间，令，x2、x3不变。二次插值法收敛准则：（1）相继两次的二次插值函数极小点、之间距离小于给定精度时，即：及2021/9/21121（2）及上述两种形式实际上是绝对精度和相对精度。二次插值法特点：（1）二次插值法只要求连续，不要求其一阶可微。（2）收敛速度比黄金分割法快，但可靠性不如黄金分割法好，程序也较长。（3）如p(x)的相邻两个迭代点重合，则产生死循环。2021/9/211221.5 无约

34、束最优化方法和约束最优化方法无约束最优化方法和约束最优化方法1.5.1 无约束最优化方法概述无约束最优化方法概述 1研究无约束优化方法的意义对于一个n维目标函数，如果在没有任何限制条件下寻求它的极小点，称无约束极小化问题或无约束优化问题。数学上表达为大量实际问题都是有约束的，研究无约束优化方法的意义在于：2021/9/21123（1）一类功能很强、使用方便的有约束优化方法，往往能将有约束问题转化成无约束问题，易于采用无约束优化方法求解。（2）有些问题在不很接近最优解时可先作无约束问题求解，然后采用有约束方法求出最优解。（3）有些实际问题本身是无约束的，或把有些约束问题经过模型变换可以转化为无约

35、束问题求解。2021/9/21124（4）对于多维无约束问题来说，古典极值理论中令一阶导数为零，但要求二阶可微，且要判断Hessian矩阵为正定才能求得极小点，这种方法有理论意义，但无实用价值。和一维问题一样，若多元函数F(X)不可微，亦无法求解。但古典极值理论是无约束优化方法发展的基础。2多维无约束优化方法的分类目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。概括起来，可分为直接法和间接法两大类，其详细分类如表1-1所示。2021/9/211251.5.2 坐标轮换法坐标轮换法1方法概述坐标轮换法的基本构思是将一个n维优化问题转化为依次沿n个坐标方向反复进行一维搜

36、索问题。这种方法的实质是把n维问题的求优过程转化为对每个变量逐次进行一维求优的循环过程。每次一维搜索时，只允许个变量的一次改动，其余(n-1)个变量固定不变。故坐标轮换法也常称单变量法或变量交错法。2021/9/211262迭代过程（1）任选初始点 ，搜索方向（2）以为初始点，沿e1作正向试探性移步，步长取。若试探成功，沿此方向一维搜索；否则，沿坐标的负方向试探。若正负方向试探均失败，则迭代点不动，转入下一步。2021/9/21127（3）以为沿e2方向作为一维搜索的新起点，按步骤（2）进行，得点。以此类推，进行完一轮一维搜索后，得。（4）以作为第二轮的初始点，重复步骤（2）和（3），得第二轮

37、搜索的终点，相继进行第三、第四轮等的搜索。（5）如果从某轮的起始点出发，依次沿n个坐标轴的正负方向试探均失败，则缩短初始试探步长，返回(2)。当初始步长缩减到足够小，满足时，迭代终止。2021/9/211283方法特点（1）计算量少，程序简单，但计算效率较低，特别在维数很高时很费机时，故仅适用于n较少（n10）的目标函数求优。（2）改变初始点重新迭代，可避免出现病态。4算法盒图见图1-19。2021/9/21129图1-19坐标轮换法算法盒图2021/9/21130例1-8坐标轮换法求目标函数的无约束最优解，初始点解解 第一轮轮迭代1）沿向一维搜索2）求：2021/9/21131求得以为新起点

38、，沿方向一维搜索求 同理得到：3）判别继续进行第二轮迭代计算返回到1）重复循环2021/9/211321.5.3 鲍威尔法鲍威尔法 鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。在无约束方法中许多算法都是以共轭方向作为搜索方向，它具有许多特点。根据构造共轭方向的原理不同，可以形成不同的共轭方向法。1共轭方向法的概念（1）定义 设A为n阶对称正定矩阵，若有两个n维矢量S1和S2，满足：2021/9/21133则称矢量S1和S2对矩阵A共轭，共轭矢量的方向称共轭方向，即S1和S2是在A度量意义下的正交。可见，S1和S2本来不相交，而与S1正交，与S2正交。若AE，则有，变

39、成直角坐标方向，即对单位矩阵E的正交。推广到n个n维矢量的情形。设有n个不为零的n维不同矢量，如满足下面的两个条件：则称n个n维矢量是对A共轭的。2021/9/21134（2）共轭方向与函数极小点的关系 设有一般二维二次正定函数其等直线是同心椭圆族，见图1-20。图1-20同心椭圆族特性从出发，沿S1方向作一维搜索，得最优点（与椭圆相切）；再从另一初始点出发，2021/9/21135仍沿S1方向作一维搜索，得最优点（也与椭圆相切），设与连线的方向为S2，则S2必过椭圆族的中心，即X*点，且S1和S2必与A正交。2搜索方向1964年，鲍威尔提出这种算法，其基本思想是用迭代点的目标函数值来构造共轭

40、方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后的实践中进行了改进。其具体构造过程如下所述。2021/9/21136任选初始点，然后与坐标轮换法一样，分别沿坐标方向e1，e2，en作一维搜索，依次求得近似极小点、。每作完一次搜索，连接初始点和最后一个点构造新的方向，并判断是否要替换原来的某一方向。3迭代过程（1）任选初始点，给定精度，k=1，取初始方向组为坐标单位矢量，即：2021/9/21137（2）沿诸方向作n次一维搜索，依次确定各最优步长，使得到点列（3）收敛准则判断：若或对于所有i=1,2,n满足则迭代结束。否则转下一步。2021/9/21138（4）计算各点的函

41、数值，并找出相邻两点函数值之差最大者，以标记，即及与之对应的两个点和，并以表示该两点的连线所指方向。（5）计算映射点 及函数值、，判断 2021/9/21139是否成立。若两者或其中之一成立，则转入下步。否则转入步骤（7）。（6）令k=k+1，计算新一轮的初始点和方向组为并返回步骤（2）。（7）产生第n+1个新方向并在该方向上作一维搜索求最优步长，使2021/9/21140得此方向上的极小点（8）令，返回步骤（2）。1.5.4 最速下降法最速下降法（梯度法梯度法）和共轭梯度法和共轭梯度法1最速下降法（梯度法）（1）方法概述 基本思想：任一点的负梯度方向是函数值在该点下降最快的方向。将n维问题转

42、化为一系列沿负梯度方向2021/9/21141用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。收敛准则为（2）迭代过程1）任选初始点 ，给定收敛精度 。2）求迭代点 的负梯度方向。对迭代点 ，k=0,1,2,，求 的梯度：2021/9/21142计算梯度的模 确定负梯度的单位向量3）进行一维搜索。以 为起点，沿 方向作一维搜索求最优步长 ，使于是得下一个迭代点2021/9/211434）当迭代点满足收敛准则时，迭代结束。否则，令，返回步骤2）。（3）梯度法动态迭代图，见图1-21。图1-21梯度法动态迭代图2021/9/21144例例1-9 求的极小值，初始点 收敛精

43、度 解解1）给定初始点，允差置2）计算迭代点的梯度和方向原函数梯度为：2021/9/21145点的为梯度的负方向为3）最优步长因子，由迭代公式2021/9/21146令 求得 4）迭代计算2021/9/21147梯度模5）判别不满足精度要求，以为起点 从2)重复，直到为止。2共轭梯度法为克服梯度法中先快后慢之不足引入共轭梯度概念，共轭梯度法最早是由Fletcher和Reeves（1964）提出的。如果是二阶的，并且在每一个搜索方向上被准2021/9/21148确的最小化，那么它具有最多在次迭代中收敛的理想特性，这是因为它的搜索方向共轭。这种方法仅仅比最速下降法增大了很少的计算量，但却显示出较大

44、的改进。它结合了当前梯度向量的信息以及前一次迭代的梯度向量信息，来求得一个新的搜索方向。可以利用当前梯度和原搜索梯度的线性组合来计算新的搜索方向。这种方法的优点是在每步计算中仅仅需要存储少量信息，所以能被应用到大型问题上。（1）原理利用目标函数的梯度确定共轭方向，使得计算简便而效果又好。2021/9/21149设目标函数（1-37）其中，的二阶导数矩阵；是常数向量，；是常数，在次迭代计算中从出发求（一维搜索）。如图1-22所示，求最优步长因子。2021/9/21150图1-22共轭梯度法的原理在两点处函数的梯度分别为：两式相减为（1-38）为简便，令2021/9/21151 所以 为使下一次搜

45、索方向对A共轭，需有代入，则得（1-39）由此式可见，它不含矩阵A，只要求出相应点得梯度，便可求得与共轭的方向。即共轭方向只与相邻两迭代点的梯度有关。2021/9/21152（2）共轭梯度方向的形成若在第 次迭代中 点的负梯度 已知，其方向为 ，则构成的共轭方向 应满足 与 若为实对称矩阵，方向为共轭方向。则：令共轭方向表示成在迭代点的负梯度向量与前一迭代搜索方向两者的线性组合，即（1-40）式中：要使求出的与共轭，故称为共轭系数。2021/9/21153共轭系数的求法：将（140）代入式（139）得（1-41）由于相邻两次迭代的负梯度方向与线性无关且正交，即是一正交系，故有 或（1-42）式

46、（141）可简化为（1-43）2021/9/21154即（1-44）式中：、分别为点、梯度的模。（3）迭代步骤1）任选初始点给定计算精度和输入维数，计算，令，取2）用一维搜索求 的最优解 ，即2021/9/21155并计算在处的梯度3）终止判别若迭代终止，否则转4)4）判别？是：则令并转1)否：若，转5)5）计算共轭方向，计算2021/9/211566）令转2)（4）共轭梯度法算法盒图，见图1-23。例例1-10 用共轭梯度法求函数的最小值。解解1）取 2021/9/21157将 代入 ，求 ，得 ，则2）求 2021/9/21158同前处理求得特点：特点：快！只求两点就找到2021/9/21

47、1591.5.5 阻尼牛顿法和阻尼牛顿法和DFP变尺度法变尺度法1阻尼牛顿法（1）方法概述 牛顿法是求函数极值的最古老算法之一。其基本思想是在点 的邻域内用一个二次函数 去近似替代原目标函数 ，然后求二次函数的极小点作为下一个迭代点 ，通过不断构造二次函数和迭代计算，使迭代点逼近函数的极小点 。阻尼牛顿法是在原始牛顿法基础上进行修正，能保证每次迭代点的函数值都有所下降。2021/9/21160（2）阻尼牛顿法迭代过程1）选一个好的初始点 ，给定收敛精度 ，令 。2）计算的梯度方向：及其模。3）检验收敛准则。若，输出，否则转入下一步。4）计算点的，并求其逆矩阵。5）确定牛顿方向，并沿此方向作一维

48、搜索求步长，使2021/9/211616）计算迭代点：，令k=k+1，返回步骤2)。（3）方法特点1）初始点应选在 附近，有一定难度。2）尽管每次迭代都不会使函数值上升，但不能保证每次下降。3）若迭代点的Hessian矩阵为奇异，则无法求逆矩阵，不能构造牛顿方向。4）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的F(X)也不适用。2021/9/21162虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。2DFP变尺度法（1）方法概述梯度法的最大优点是初始点可任选，且开始几次迭代，目标函数值下降很快，其主要缺点是

49、迭代点接近极小点时，对二次正定函数收敛也非常慢。牛顿法的最大优点是对二次正定函数迭代一次即收敛，但也有不少缺点。人们自然会想到，能否吸取这两种方法之长，努力克服它们2021/9/21163的缺点，来建立更好的算法。DFP变尺度法就是这样的算法之一。这种算法首先有戴维顿（Davidon）于1959年提出，又于1963年由弗莱彻（Fletcher）和鲍威尔加以发展和完善，成为现代公认的较好的算法之一。DFP法是基于牛顿法的思想又作了重要改进。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。2021/9/21164（2）迭代过程1）任选初始点 ，计

50、算收敛精度 ，维数n；2）给定变尺度矩阵初值 （单位矩阵），令 ，置k=0；3）求探索方向和最优步长因子4）进行一维搜索，求下一个迭代点2021/9/211655）检验是否满足，若满足，则即为极小点，停止迭代。否则转下一步；6）检查迭代次数，若 ，则 ，转向步骤2)，若 则进行下一步；7）构造新的探索方向为此应计算 、然后令 转步骤3)。2021/9/211661.5.6 线性规划线性规划单纯形法单纯形法 线性规划是应用最广的优化技术之一，也可以说是一种最有效的优化技术。目标函数和约束函数都是线性函数的最优化问题，称为线性规划或线性优化问题。线性规划是数学规划中的一个比较成熟的分支。在生产计划