智能纺织品优化设计

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第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）,向量 决定移动的方向，标量 决定移动的步长。,设计空间的维数表征了设计的自由度，设计变量愈多，则设计的自由度愈大、可供选择的方案愈多、设计愈灵活，但难度愈大、求解亦愈复杂。一般，含有210个设计变量的为小型设计问题；1050个为中大型设计问题；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为矩阵,，用 表示。,（,为对称矩阵,）,即22阵。,n元函数的Hessian矩阵可写为,（1-20）,n元函数有n个变量，所以它的Hessian矩阵是nn对称矩阵。,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）,或,这是线段的表达式。,当 时， ；,当 时， ，所以 在01范围。,凸函数的表达式为,（1-24）,2 多元函数的凸性,设 为n维欧氏空间中的一个集合，,若其中任意两点， 之间连线上所有的点都在这个集合中，则称这种集合 为n维欧氏空间的一个凸集。,图1-10(a)是二维空间的一个凸集，而(b)不是凸集。,(a) 凸集,(b) 非凸集,图1-10 二维空间的凸集与非凸集,设 是 上的函数，如果对任何实数,对 上的任意 两点恒有,(1-25),则函数 就是定义在凸集 上的一个凸函数。上式若不带“”为“,f,1,，淘汰0,0.4995，留下新区间0.4995,1.0。,第二次计算点为：,因为，淘汰0.4995,x,3,，留下新区间,x,3,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）,，以,为新区间，令,x,1,、,x,2,不变；,（2）,，以,为新区间，令,，,x,3,不变；,（3）,，以,为新区间，令,，,x,1,不变；,（4）,，以,为新区间，令,，,x,2,、,x,3,不变。,二次插值法收敛准则：,（,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,）,以 为初始点，沿,e,1,作正向试探性移步，步长取 。若试探成功，沿此方向一维搜索；否则，沿坐标的负方向试探。若正负方向试探均失败，则迭代点不动，转入下一步。,（3）,以 为沿,e,2,方向作为一维搜索的新起点，按步骤,（,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,维矢量,S,1,和,S,2,，满足：,则称矢量,S,1,和,S,2,对矩阵,A,共轭，共轭矢量的方向称共轭方向，即,S,1,和,S,2,是在,A,度量意义下的正交。可见，,S,1,和,S,2,本来不相交，而 与,S,1,正交， 与,S,2,正交。若,A,E,，则有 ，变成直角坐标方向，即对单位矩阵,E,的正交。,推广到,n,个,n,维矢量的情形。设有,n,个不为零的,n,维不同矢量，如满足下面的两个条件：,则称,n,个,n,维矢量 是对,A,共轭的。,（2）,共轭方向与函数极小点的关系,设有一般二维二次正定函数,其等直线是同心椭圆族，见图1-20。,图1-20 同心椭圆族特性,从 出发，沿,S,1,方向作一维搜索，得最优点,（,与椭圆相切,）,；再从另一初始点 出发，,仍沿,S,1方向作一维搜索，得最优点,（,也与椭圆相切,）,，设 与 连线的方向为,S,2,，则,S,2,必过椭圆族的中心，即,X,*点，且,S,1,和,S,2,必与,A,正交。,2 搜索方向,1964年，鲍威尔提出这种算法，其基本思想是用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后的实践中进行了改进。其具体构造过程如下所述。,任选初始点 ，然后与坐标轮换法一样，分别沿坐标方向,e,1,，,e,2,，,e,n,作一维搜索，依次求得近似极小点 、 、 。每作完一次搜索，连接初始点和最后一个点构造新的方向，并判断是否要替换原来的某一方向。,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）,式中： 要使求出的 与 共轭，故称为共轭系数。,共轭系数的求法：,将,（,140,）,代入式,（,139,）,得,（1-41）,由于相邻两次迭代的负梯度方向与线性无关且正,交，即,是一正交系，,故有,或,（1-42）,式,（141）,可简化为,（1-43）,即,（1-44）,式中： 、 分别为点 、 梯度的模。,（3）,迭代步骤,1）,任选初始点 给定计算精度 和输入维数 ，计算 ，令 ，取,2）,用一维搜索求 的最优解 ，即,并计算在 处的梯度,3）,终止判别,若 迭代终止，否则转,4),4）,判别 ？,是：则令 并转,1),否：若 ，转,5)