优化设计-课件

第二章优化设计OptimizationDesign本章主要内容

优化设计概述

优化问题的数学分析基础一维探索优化方法无约束多维问题的优化方法约束问题的优化方法多目标函数的优化方法

本章重难点

优化设计数学模型的建立，掌握常用的优化方法，如一维探索优化方法、无约束多维问题的优化方法、约束问题的优化方法、以及多目标函数的优化方法等。2.1优化设计概述2.1.1优化设计问题的提出1.传统设计方法：确定产品结构方案；尺寸计算和强度校核；调整方案，重新计算。（循环设计过程）缺点：烦琐，耗时，以牺牲设计效率和质量为代价2.优化设计：转化为最优化问题，利用数学规划的方法，借助于计算机（高速度、高精度和大存储量）的处理，从满足设计要求的一切可行方案中，按照预定的目标自动寻找最优设计的一种设计方法。优化设计三要素：设计变量，目标函数，约束条件。满足：gu(m、z、x)的情况下寻找：一组设计参数m、z、x；（模数、齿数、变位系数）使得：设计目标流量最均匀,体积最小,寿命最长以齿轮泵为例，其优化设计过程如下：2.1.2优化设计的数学模型优化设计的问题首先是建立数学模型，即把实际问题转化为数学模型的形式。优化模型三要素：设计变量，目标函数，约束条件。1.设计变量

设计过程中，进行选择和调整，最终必须确定的独立参数称为设计变量；固定不变，需要事先给定的参数称为设计常量。（1）维数：设计变量的个数称为设计问题的维数。设计变量愈多，设计自由度愈大，可供选择方案愈多，设计愈灵活，难度愈大，求解愈复杂。（2）设计空间:

n个设计变量的坐标轴所形成的n维实空间称为设计空间，用Rn表示。设计空间中，n个设计变量的坐标值组成一个设计点，并代表一个设计方案，可采用如下向量表示：其中，最优设计方案用表示，称为最优点或优化点。二维设计空间三维设计空间x2x1X=[x1

x2]Tx1x2x3X=[x1

x2x3]T2.目标函数

优化设计的任务是在许多可行的方案中找出最优的方案，所谓最优方案是在设计变量中能最好的满足所追求的某些特点的目标，而这些目标又可表达为设计变量的函数，称为目标函数。目标函数可用来评价设计方案的好坏，又称为评价函数。常表示为：目标函数表征的是设计的某项或某些最重要的特征。优化设计就是要通过优选设计变量使目标函数达到最优值。目标函数总可以转化成求最小值的统一形式。等值曲面:目标函数值相等的所有设计点的集合称为目标函数的等值曲面。二维：等值线；三维：等值面；三维以上：等超越面。z等值线族形象地反映了目标函数值的变化规律，越靠近极值点的等值线，表示的目标函数值越小，其分布也越密集。xyo等高线x*（中心极值点）等值线族

二维设计变量下的等值线3.约束条件（函数）

对任何设计都有若干不同的要求和限制，将这些要求和限制表示成设计变量的函数并写成一系列不等式和等式表达式，就构成了设计的约束条件简称约束。其作用是对设计变量的取值加以限制。（1）分类根据对设计变量取值的限制形式：显约束（直接限制）和隐约束（间接限制）根据性质的不同：边界约束和性能约束。边界约束：直接限制每个设计变量的取值范围或彼此相互关系的一些辅助的区域约束。性能约束：由产品性能或设计者要求推导出来的用以间接限制设计变量取值范围的一种约束。

（2）可行域任何一个不等式约束都把设计空间分为两部分，一部分是满足约束条件的称为可行域，另一部分是不满足约束条件的称为非可行域，这两部分的分界是(约束方程)。在约束边界上的点称为边界点两个以上约束边界的交点称为角点等式约束同样把设计空间分成两部分。不等式约束与等式约束的几何意义：在一个优化设计问题的设计空间中，满足所有约束条件的点构成的子空间，称为可行域。【例1】作出下列约束条件构成的可行域：【例2】根据下列约束条件画出可行域。可行域在约束边界的哪一边怎么确定？（3）起作用约束设X为设计空间中的一个点：满足所有约束条件的点称为可行点（内点和边界点）不满足所有约束条件的点称为非可行点（外点）X在某个约束边界上，则这个约束条件称为X的起作用约束X不在某个约束边界上，则这个约束条件称为X的不起作用约束起作用约束设计点X(k)的所有起作用约束的函数序号下标集合用Ik表示，即一般形式：4.优化设计的数学模型

用“max、min”表示极大、极小化，用“s.t”表示“满足于”，“m、p”表示不等式约束与等式约束的个数，则表示如下形式：

本课程中，所有的优化设计问题都是求目标函数的极小值。遇到求极大值的问题，则先通过转化变成极小值问题。与此同时，所有的不等式约束都采用的形式。5.优化设计问题的求解（1）图解法

【例3】求解下列优化问题：最优解是等值线在函数值下降方向上与可行域的最后一个交点。【例4】求解下列优化问题：最优解是等值线在函数值下降方向上与可行域的最后一个交点。非线性问题的最优解要么是一个内点，要么是一个边界点；非线性问题的最优解如果是一个边界点，那么它必定是等值线（面）在函数值下降方向上与可行域的最后一个交点；线性问题的最优解必定是等值线（面）在函数值下降方向上与可行域的最后一个交点；一般情况下：（2）数值迭代法数值迭代法的基本思想：从一个初始点出发，按照一个可行的搜索方向和适当的步长走一步，到达，再从出发，选一个可行的搜索方向和适当的步长走一步，达到，并保证每一步函数值都是下降的，即必须满足（这称为新点的适用性），这样一步一步地重复进行数值计算，直至达到目标函数的极小点。无约束优化问题初始点用某种优化方法确定确定前进步长计算检查若不满足则改变步长，满足则进入下一步从出发用某种优化方法确定确定前进步长计算检查若不满足则改变步长，满足则进入下一步从出发用某种优化方法确定确定前进步长计算检查若不满足则改变步长，满足则进入下一步从出发用某种优化方法确定确定前进步长计算检查若不满足则改变步长，满足则进入下一步——第k个迭代点——从第k个迭代点出发寻找下一个迭代点的搜索方向——沿前进的步长基本迭代公式

由于每次迭代求得的新点均为使函数值有所下降的适用点（如果不是适用点，可改变方向和步长另行搜索适用点），则所得各点必将逐步向该函数的极小值点逼近，最后总可求得非常接近该函数理论最优点的近似最优点。2）约束优化问题

对于约束优化问题，除了检查每个新点的适用性外，还要检查其可行性，即是否满足的约束条件，如果适用性和可行性兼备，再进行下一次迭代，最终自然也能求得非常接近约束最优点的近似最优点。

综上所述，采用数值法进行迭代求优时，除了选择初始点以外，如何确定迭代方向和步长成为非常重要的环节，他们将直接决定着搜索的效率、函数值逐步下降的稳定性和优化过程所需的时间等。A.点距准则

根据相邻两迭代点与间的距离足够小而建立的准则，点距准则可表示为或数值迭代终止准则（计算精度的确定）

B.值差准则

根据相邻的两迭代点的函数值下降量足够小而建立的准则。绝对下降量准则：相对下降量准则：C.梯度准则

根据迭代点的函数梯度达到足够小而建立的准则，表示为或迭代法必须要解决的三个问题迭代算法具有收敛性；在收敛性前提下，选择比较好的初始点X(0)

和适宜的终止判据及收敛精度；选取使目标函数值下降较快的迭代探索方向S(k)和最优的迭代步长α(k)

，确保较快的收敛速度。如何确定S(k)、α(k)优化方法第2节优化设计的数学基础内容简介

优化设计是以数学规划论为理论基础，以计算机为工具的一种现代设计方法。优化设计问题大多是多变量有约束的非线性规划问题，其数学本质是求解多变量非线性函数的极值问题。因此，本节将介绍与此有关的一些数学基础知识。主要介绍的内容如下：■

二次型与正定矩阵■

函数的方向导数与梯度■函数的泰勒近似展开式和黑塞矩阵■

无约束优化问题的极值条件■凸函数与凸规划■约束优化问题的极值条件2.2.1二次型与正定矩阵

在介绍优化方法时，常常是将二次型函数作为对象。其原因除了二次型函数在工程优化问题中有较多的应用且比较简单之外，还因为任何一个复杂的多元函数都可采用泰勒二次展开式做局部逼近，使复杂函数简化为二次函数。因此，需要讨论有关二次型函数的问题。1.二次型函数所谓二次型函数是指含有n个实变量

x1，x2，…，xn的一个二次齐次多项式函数，其表达式为（2-1）式中，aij(i，j=1,2,…,n)——给定的实常数，称为二次型的系数。则式(2-2a)可简记为

(2-2a)若令(2-2b)上式经化简，可写成矩阵形式式中，矩阵A

是由函数f(X)中各项所含系数所组成的

n×n

阶矩阵。若式中aij

=aji

(i,j=1,2,…,n)为常系数，则称式(2-1)和式(2-2a)为二次型函数或简称实二次型。

A称为二次型矩阵，因为aij

=aji

，所以A=AT，称为对称矩阵，因此二次型矩阵都是对称矩阵。

在采用泰勒二次近似展开式讨论函数的极值时，常要分析二次型函数是否正定或负定。二次型的正定与负定的定义简述如下：2.正定矩阵

如果对于任意的非零向量

X=[x1,x2,…，xn]T，即x1，x2，…，xn不全为零，若有

XTAX>0，则称此二次型

f(X)=XTAX是正定二次型，其对应的矩阵A

称为正定矩阵；

若有

XTAX≥0，则称此二次型

f(X)=XTAX为半正定二次型，并称其相应的矩阵A为半正定矩阵；

若有XTAX<0，则称此二次型

f(X)=XTAX为负定二次型，其对应的矩阵A为负定矩阵。

矩阵A的正定与负定的判别，可用矩阵A的各阶顺序主子式的正负来判别。矩阵A的正定条件是：

即矩阵A的各阶主子式均大于零。当矩阵A为正定时，其对应的二次型为正定二次型。如果实二次型

XTAX

中的矩阵A的各阶主子式负、正相间（即所有奇数阶主子式小于零，而所有偶数阶主子式大于零），即则该矩阵

A为负定矩阵，其对应的二次型为负定二次型。

目标函数的等值线（或面）仅从几何方面定性直观的表示出函数的变化规律。这种表示方法虽然直观，但不能定量表示，且多数只限于二元函数。为了能够定量地表明函数特别是多元函数在某一点的变化形态，需要引出函数的方向导数及梯度的概念。2.2.2函数的方向导数与梯度由多元函数的微分学可知，对于一个连续可微函数

f(X)在某一点X(k)的一阶偏导数为1.函数的方向导数（2-3）可简记为它描述了该函数

f(X)在X(k)

沿各坐标轴这一特定方向的变化率。现以二元函数

f(x1，x2)为例，求其沿任一方向

S（它与各坐标轴之间的夹角为α1，α2，见图2-1）的函数变化率。图2-1函数的变化率设该二元函数由沿方向

S变化到点则当X(k)

至

X(k+1)的距离为无限小时，函数的增量与的比值，称为该二元函数

f(x1,x2)

在点

X(k)沿方向

S的方向导数，记为即

（2-5）对于n维函数，可以仿此推导得函数

f(X)在点X(k)沿方向S

的方向导数为（2-6）式中，——为函数f(X)对坐标轴xi的偏导数；——为S

方向的方向余弦。由式(2-5)可知，在同一点（如X(k)点），沿不同的方向（α1或α2不同），函数的方向导数值是不等的，也就是表明函数沿不同的方向上有不同的变化率。因此，方向导数是函数在某点沿给定方向的变化率。

函数在某一确定点沿不同方向的变化率是不同的。为求得函数在点X(k)的方向导数为最大的方向，需引入梯度的概念。2.函数的梯度将式(2-5)写成矩阵形式，则有若令(2-7)于是，可将方向导数表示为(2-8)式中，和分别为向量

和向量

S

的模，其值为

（2-9）和（2-10）式中，θ——为向量和S之间的夹角。

由式(2-8)可以看出，由于一1≤cosθ≤1，故当cosθ=1，即向量与S的方向相同时，方向导数最大，其值为。这表明向量就是点X(k)处的方向导数最大的方向，即函数变化率最大的方向，称为函数在该点的梯度，记作。同理，上述梯度的概念可以推广到多元函数中去，对于n元函数

在某点X(k)的梯度及梯度的模可写为（2-11）（2-12）

函数的梯度在优化设计中有着十分重要的作用。由于梯度是一个向量，而梯度方向是函数具有最大变化率的方向。亦即梯度方向是函数f(X)的最速上升方向，而负梯度则为函数f(X)的最速下降方向。

梯度向量与过点X(k)

的等值线（或等值面）的切线是正交（垂直）的，如图2-2、图2-3所示。所以，函数f(X)在给定点X(k)的梯度向量是函数等值线或等值面在该点X(k)的法线方向。

图2-2梯度方向与等值线的关系图2-3梯度向量与等值面的关系

在最优化方法的讨论中，为研究复杂函数极值问题的方便，常将目标函数（或约束函数）展成泰勒近似多项式。其中最常用的是泰勒二次近似式。设n维目标函数f(X)在X(k)点至少有二阶连续的偏导数，则在这一点邻近的泰勒二次近似展开式并写成矩阵形式时有2.2.3函数的泰勒近似展开式和海赛矩阵(2-13)式(2-13)称为函数f(X)的泰勒二次近似式。其中，是函数f(X)在点X(k)的梯度；是由函数f(X)在点X(k)的所有二阶偏导数组成的矩阵，称函数f(X)在点X(k)的二阶导数矩阵或黑塞(Hessian)矩阵，记作H(X(k))。该二阶导数矩阵的组成形式如下：

(2-14)

黑塞矩阵

H(X(k))

是由目标函数

f(X)

在点

X(k)

处的二阶偏导数组成的n×n

阶对称矩阵。

求解无约束优化问题的实质是求解目标函数f(X)在n

维空间Rn中的极值，因而有必要讨论无约束优化问题的极值条件。2.2.4无约束优化问题的极值条件由高等数学可知，任何一个单值、连续并可微的一元函数

f(X)

，在给定区间内的一点X(*)有极值，其必要条件为

(2-15)仅满足此条件只表明该点是个驻点，尚不能肯定为极值点，即使是极值点也还不能断定是极小点还是极大点，因此还需用函数在该点的二阶导数来判断。

驻点为极值点的充分条件为：对应的二阶导数不等于零，且若

>0，则点为极小点；若<0，则点为极大点。同理，对于二元函数

f(X)=f(x1,x2)来说，在点取得极值的必要条件是写成矩阵形式，即

（2-16）

为推得二元函数极值存在的充分条件，将二元函数

f(x1,x2)在驻点作泰勒二次近似展开，得到二次近似表达式为因为驻点满足的条件，故由上式可得若f(x1,x2)在点处取得极小值，则要求在点附近的一切X均满足条件依据这一条件，应有

此时，X(*)为极小点。为使上式成立，根据二次型的理论可知，只要函数的二阶偏导数矩阵（即黑塞矩阵H(X(*))）必须是正定矩阵。

由此可得，二元函数

f(x1,x2)

在点

X(*)

取得极小值的充分条件是：函数f(x1,x2)在点X(*)处的二阶导数矩阵（即黑塞矩阵H(X(*))）为正定。同理，函数在

X(*)

处取得极大值的充分条件是：函数f(x1,x2)在点X(*)处的黑塞矩阵H(X(*))为负定。

上述结论可推广至多元函数的极值问题。即多元函数f(x1，x2，…，xn)在点取得极小值的充分必要条件是：函数f(X)在该点的梯度为零，二阶偏导数矩阵（即黑塞矩阵H(X(*))）为正定，即（2-17）（2-18）H(X(*))正定同理，多元函数f(x1，x2，…，xn)在点取得极大值的充分必要条件是：函数f(X)在该点的梯度为零，二阶偏导数矩阵为负定。

由于一个函数的极小点(局部极值点）并不是唯一的，而优化问题总是期望能获得函数的全域最小点（全域极值点）。为此，就需知在什么情况下所获得的极小点就是全域最小点，这就涉及到凸集、凸函数与凸规划问题。2.2.5凸函数与凸规划1.凸集设

D

为n维欧氏空间Rn中的一个集合。如果在D内任取两点X(1)和X(2)，其连线上的所有点均在D内，则称这种集合D为n维欧氏空间Rn

的一个凸集。

图2-5(a)、(c)是二维空间的一个凸集；图2-5(b)是非凸集。图2-5凸集与非凸集

X

(1)、X

(2)两点之间的连线，可用数学式表达为（2-19）式中，λ为由0～1(0≤λ≤1)间的任意实数。即对[0，1]上一切λ值得到的点X的全体组成X(1)、X(2)

点的连线。则凸集的数学定义式为

X

(1)，X

(2)∈D

X=λX(1)+(1一λ)X(2)∈D，0≤λ≤1且

凸函数的数学定义如下：设f(X)为定义在凸集D上的一个函数，X

(1)、X(2)

为D

上的任意两点，若对于任意实数λ(0≤λ≤1)恒有2.凸函数（2-20）则称f(X)为凸集D上的凸函数。若式(2-20)中的“≤”为“＜”，则称f(X)为严格凸函数；若式(2-20)中不等号反向，即“≤”为“≥”，则称f(X)为D上的凹函数。

凸函数的几何意义可用一元函数情形说明，如图2-6所示，若函数

f(X)在区间[a,b]内为凸函数，则函数f(X)曲线上任意两点所连的直线不会落在曲线弧线以下。图2-6凸函数的几何意义

凸函数具有如下特性：

(1)设f(X)为定义在凸集D上的一个凸函数，则对于任意实数λ(λ

>0)，则函数λf(X)在凸集上也是凸函数；

(2)设f1(X)和f2(X)为定义在凸集D上的两个凸函数，则f1(X)和f2(X)的线性组合函数

f(X)=f1(X)+f2(X)在D上也是凸函数；

(3)若f(X)为定义在凸集D上的函数，且存在连续二阶导数，则f(X)为D上的凸函数的充要条件是：f(X)的黑塞矩阵H(X)处处是半正定的。若黑塞矩阵H(X)对一切X∈D都正定，则f(X)是D上的严格凸函数。

利用以上性质，就可以判别函数是否具有凸性。如果f(X)是凸集D上的凸函数，并且在D内有极小点，则极小点是唯一的。3.凸规划对于约束优化问题minf(X)X∈Rns.t.gu(X)≤0,

u=1,2,…,m如果目标函数

f(X)和所有的不等式约束gu(X)≤0（u=1,2,…,m）均为凸函数，则称此约束优化问题为凸规划。并需指出的是，如果不等式约束的形式为gu(X)≥0，则gu(X)（u=1,2,…,m）应为凹函数。

凸规划的一个重要特性为：

凸规划的任何局部极小解一定是全域最优解。因此，对于凸规划问题，只要求出一个局部极小解，它就是全域最优解。所以，优化理论与方法常限于讨论凸规划问题。

需要指出的是，实际工程优化问题往往不是凸规划问题。所以，采用常用的优化方法，求得的最优解往往是局部最优解。而且，对于一个复杂的工程优化问题，往往难以判断其是否为凸规划问题。为此，在采用迭代方法求解时，常从多个初始点出发，进行不同的迭代，以求得多个局部极小点，然后比较这些局部极小点，最后得到一个近似全域极小点，作为该问题的最优解。2.2.6约束优化问题的极值条件求解约束优化问题的实质就是在所有的约束条件所形成的可行域内，求得目标函数的极值点，即约束最优点。因而约束优化问题比无约束优化问题更为复杂。

约束优化问题的极值点可能出现两种情况：

一种是如图2-7(a)所示，即目标函数的极值点X*

处于可行域

D之内，故目标函数的极值点X*即为该约束优化问题的极值点；

另一种如图2-7(b)所示，即某约束边界gi

(X)=0将目标函数的自然极值点隔到可行域D之外，因此这时约束优化问题的极值点不是目标函数的自然极值点，而是该约束边界gi

(X)=0与目标函数等值线的切点X*。图2-7约束优化问题极值点(a)极值点在可行域内(b)极值点在可行域的边界上

由高等数学可知，对于等式约束优化问题

可建立如下拉格朗日函数

1.等式约束的极值条件(2-21)(2-22)式中，为拉格朗日乘子向量。令，得(2-23)

式(2-23)就是等式约束问题在点X*

取得极值的必要条件。式(2-23)的几何意义可以解释为：在等式约束的极值点上，目标函数的负梯度等于诸约束函数梯度的线性组合。如图2-8所示，在两个等式约束的交线E上的点X*，约束函数的梯度与目标函数的梯度共面，因此式(2-23)成立，故X*就是极值点。图2-8等式约束问题的极值条件

对于不等式约束优化问题

引入m个松弛变量，可将上面的不等式约束优化问题变成等式约束问题2.不等式约束的极值条件(2-24)(2-25)建立这一问题的拉格朗日函数式中，为松弛变量组成的向量。注意到约束条件为“≤０”的形式，可知约束函数的梯度方向指向可行域外，为满足，必须大于零；而当时，有和，这说明点X在可行域内。

式中，当时有和，这说明点X在约束边界上，为点X的起作用约束。

则有(2-26)，

令该拉格朗日函数的梯度等于零，即使设为点X*的n个起作用约束，且X*

是极值点，则由式(2-26)及其分析可知，必有（2-27）

式(2-27)就是不等式约束优化问题的极值条件，称Kuhn-Tucker条件，简称K-T条件。

该条件表明，若设计点

X*是函数f(X)的极值点，要么（如图2-9所示，此时），要么目标函数的负梯度位于诸起作用约束梯度所构成的夹角或锥体之内。

也就是说，目标函数的负梯度等于诸起作用约束梯度的非负线性组合（如图2-10所示，此时）。

图2-9极值点处目标函数图2-10极值点处目标函数的梯度为零的梯度不为零

应该指出，K-T条件是多元函数取得约束极值的必要条件，既可以用来作为约束极值点的判别条件，又可以用来直接求解比较简单的约束优化问题。但K-T条件不是多元函数取得约束极值的充分条件。只有当目标函数f(X)是凸函数，而全部约束函数也是凸函数（或为凹函数），即为凸规划时，K-T条件才是极值存在的充分必要条件。下面通过一个实例来说明K-T条件的应用。例2-5

试用K-T条件判定点X*=[1,0]T是否为如下优化问题的极值点。解：(1)画出该优化问题的目标函数等值线和可行域图根据该优化问题给出的目标函数和约束条件，表示该问题的可行域

D和目标函数f(X)的一些等值线图如图2-11所示。图2-11例2-5的极值点判断(2)找出起作用的约束由图2-11可见，在点X*=[1，0]T处起作用的约束有g2(X)和g3(X)。

(3)求

f(X)、g2(X)和g3(X)在点X*处的梯度

(4)将以上代入K-T条件式(2-27)，即、、得当λ2=1，λ3=1时，上式成立，满足K-T条件，故点X*=[1,0]T就是该约束优化问题的极小点，如图2-11所示。另外，又经检验得知

f(X)和gi(X)均为凸函数，故f(X)在gi(X)≤0(i=1,2,3)下的极小点X*=[1,0]T是唯一的。ThankYou！本章结束2.3一维探索优化方法

一维搜索的数学形式一维搜索的几何意义常用一维搜索方法：0.618法

插值法

一、概述数值迭代过程中，任何一次迭代，总是从某个已知点出发，沿着给定的方向（用某种优化方法确定）搜索到目标函数在该方向上的极小值点，这个过程称为一维搜索。一维搜索不仅可以求解一维优化问题，同时也是求解多维优化问题的基本步骤。1.一维搜索的概念

怎么理解“一维”的含义？对“一维”的理解寻找目标函数在指定方向上的极小点，在计算上就是从沿前进多少的问题，即求步长因子的问题。从这个意义上讲，一维搜索是一个求解关于的单元目标函数的过程。一维搜索寻找合适的，使最小“一维”是指“一个方向”（）；任一次迭代，都是求使得即其中：表示步长因子表示最优步长因子2.一维搜索的数学形式

3.一维搜索的几何意义

从出发，沿方向一维搜索，就是求方向与等值线的切点，此时的步长因子即为最优步长因子。4.单峰区间

对于所有的一维搜索方法，首先遇到的共同问题是：如何确定一个初始搜索区间，使该区间内含有函数的极小点，且在该区间内函数有唯一的极小点，这个初始搜索区间就是单峰区间。

设函数f(x)在区间内有定义，且(1)在区间内存在极小点，即有

(2)区间上的任意x，均满足；区间上的任意x，有用解析法给单峰区间下一个定义：则称闭区间为函数f(x)的单峰区间。单峰区间的特点：单峰区间内，在极小点的左边，函数是严格减少的，在极小点的右边，函数是严格增加的；如果区间是一个单峰区间，x是区间内的一点，则两个不等式中必有一个成立；单峰区间内的函数图形表现为“高－低－高”的形态。应用这一特征可以确定单峰区间。如果函数具有多个极小点，则表现为多峰函数。此时，需要对变量取值范围进行适当的划分，使每一个子空间只包含一个极小点，才能进行一维搜索。一维搜索时，同样需要在每个子空间内寻找单峰区间。注意：假设第k次得到的区间，若，则可取作为极小点。5.一维搜索的基本思想

一维搜索就是要在初始单峰区间中求单峰函数的极小点。所以找初始单峰区间是一维搜索的第一步，然后将初始单峰区间逐步缩小，直至包括极小点的区间长度小于给定的一个正数，此称为收敛精度或迭代精度。缩小区间的区间消去法无论发生在那种情况，都将包含极小点的区间缩小，即可删去最左段或最右段，然后在保留下来的区间上做同样的处理，如此迭代下去，将使搜索区间逐步减小，直到满足预先给定的精度（终止准则）时，即获得一维优化问题的近似最优解。消去函数值大的内分点到同一侧端点之间的区间1)基本原理

对于目标函数f(x)，在区间[a,b]内，适当插入两个内分点x1和x2(x1<x2),它们把[a,b]分成三段。计算并比较x1和x2两点的函数值f(x1)和f(x2)，因为[a,b]是单峰区间，故当f(x1)>f(x2)时，极小点必在[x1,b]中；当f(x1)≤f(x2)时，极小点必在[a,x2]中。（1）0.618法（黄金分割法）黄金分割法要求在区间[a,b]中插入的两点位置是对称的，如图所示，ax1=x2b。设区间长为L，插入的两个点把区间分成较长的一段α和较短的一段(L

–

α)，如图所示，，，这样，无论删去那一段，保留的区间长度总是α，在每次迭代中，整个区间的长度α与较长一段长度的比等于较长一段长度与较短长度的比。2）黄金分割法的迭代步骤

（1）给定初始单峰区间[a,b]及允许误差ε>0；（2）计算内分点及其函数值（3）比较函数值f1和f2的大小；根据比较结果缩短搜索区间A.当f1≤f2时，极小点必在[a,x2]中，则B.当f1>f2时，极小点必在[x1,b]中，则（4）判断是否满足精度要求。若新区间已缩短至预定精度要求，即，则转第5）步；否则转第3）步，进行下一次迭代计算。（5）输出最终区间的中点作为近似最优点，其对应的函数值即为最优值，他们组成的最优解为：教材P141习题3-14（2）二次插值法适于目标函数易求一阶或二阶导数的情形。插值法：当目标函数比较复杂，不易通过

limf(x(k)+(k)s)=f(*)使目标函数达到极小值时，可以采用一个容易求解极小值的较低次函数p(x)，在满足一定的条件下来近似代替f(x)。

p(x)为二次函数时称为二次插值法，p(x)为三次函数时称为三次插值法。插值法的原理1(k)02(k)3(k)f(1(k))f(2(k))f(3(k))f()p()f()p()优化问题一维优化问题（1个设计变量）多维优化问题（多个设计变量）无约束多维问题单目标函数的优化问题多目标函数的优化问题有约束多维问题2.4无约束优化方法无约束优化方法的核心是确定探索方向（能使目标函数值下降的方向），有了方向，沿这个方向应该走多远（最优探索步长），则可采用一维搜索方法解决。无约束优化方法分为两大类：第一类是只利用目标函数值构成的搜索方法，如坐标轮换法、鲍威尔法和单纯形法等。第二类是利用目标函数的一阶导数甚至二阶导数构造的搜索方法，如梯度法、牛顿法、共轭梯度法和变尺寸法等。

无约束问题的

最优化方法之坐标变换法精彩不容错过将一个多维的无约束最优化问题转化为一系列沿坐标轴方向的一维易优化间题央求解，因此也称降维法。一、坐标轮换法（变量轮换法）基本原理：

坐标轮换法的基本思想：是将一个n维优化问题转化为依次沿n个坐标方向反复进行一维搜索问题。

每次一维搜索时，只允许n个变量的一个改动，其余(n-1)个变量固定不变。

坐标轮换法的基本原理x1x2X*X(0,1)X(1)X(2)X(3)X(0)0x1(0)x1(1)x1(2)x1(3)x1*x2(0)x2(1)x2(2)x2(3)x2*特点：由于直接搜索是通过大量试验结果相比较而得最优解，因此计算时间比较长，且随着设计变量的增多，计算时间增加得很快。实践证明，在变量不超过10个的情况下，直接搜索法由于方法本身直观明确，易于被人所理解与

掌握，虽然计算时间格长，但从使用者的角度来

看，却比解析法更为个人满意。迭代步骤：（1）第1次迭代时，先固定x2=x2(0)

变量值不动，由初始点X(0)沿x1轴向进行一维探索，得到该轴方向上的最优点X(0,1)=[x1(1),

x2(0)]；（2）固定x1=x1(1)

变量值不动，由初始点X(0,1)

沿x2轴向进行一维探索，得到该轴方向上的最优点X(1)=[x1(1),

x2(1)]（3）将X

(1)

作为第1次迭代的改进点，之后，完全依照第1次的步骤进行第2、3、…、k次的坐标轮换迭代，直到满足精度要求后停止迭代。不同性质目标函数坐标轮换法的求优效能x1x2X(1)X*X(0)0x1x2X*X(0)X(1)X(2)X(3)X(4)0X(0)0x1x2X*X(1)收敛速度很快收敛速度很慢求优失效例1.求目标函数的极小点。取初始点解：第一轮迭代：

求最优搜索步长

求最优搜索步长沿着第二个坐标方向搜索：判断终止条件，不满足，进行第二轮迭代：

求最优搜索步长

求最优搜索步长沿着第二个坐标方向搜索：例3:用坐标轮换法求下面问题的最优解，给定初始点X0=[00]T,精度要求ε=0.1解:第一轮迭代求最优步长，即极小化：以X1(1)为新起点，沿e2方向进行一维搜索：仍以最优步长原则确定α2：继续进行第二轮迭代计算，等等。从坐标轮换法的迭代过程可以看出其搜索路线较长，计算效率低。因此，一般认为此法仅适宜n＜10的小型优化问题的求解。另外，此法的效能在很大程度上取决于目标函数的性质。按终止条件检验：

无约束问题的

最优化方法之Powell法精彩不容错过

顾名思义，Powell法是M.J.D.Powell发表的，因其卓越贡献，此方法以其名字命名。文章发表在TheComputerJournal,Vol.7,No.4,pp.352-355,时间是1964年1月。Powell方法是比坐标变换法加速收敛的算法，对目标函数要做求导运算。（至少一次）。对于初学者看书仅仅看书不是明智的选择，因为编书人这一部分所写的内容不完善。我仅仅提出我的问题：1.何为共轭方向2.共轭方向与目标函数有何关系3.如何确定共轭方向4.如何由共轭方向确定目标函数极值5.这种方法的优缺点是什么二、Powell（鲍威尔）法

假设目标函数f(x)在极值点附近的二次近似函数为对二维情况任选取初始点x0沿某个下降方向d0作一维搜索，得x1

因为是沿d0方向搜索的最佳步长，即在点x1处函数f（x）沿方向d0的方向导数为零。考虑到点x1处方向导数与梯度之间的关系，故有α0d0x0x1x*11α1d1d1如果按最速下降法，选择负梯度方向为搜索方向，则将发生锯齿现象。

取下一次的迭代搜索方向d1直指极小点x*。α0d0x0x1x*11α1d1d1如果能够选定这样的搜索方向，那么对于二元二次函数只需顺次进行d0、d1两次直线搜索就可以求到极小点x*

，即有那么这样的d1方向应该满足什么条件呢?对于前述的二次函数:有当时，x*是f(x)极小点，应满足极值必要条件，故有将等式两边同时左乘得：

就是使d1直指极小点x*

，d1所必须满足的条件。两个向量d0和d1称为G的共轭向量，或称d0和d1对G是共轭方向。2.共轭方向的性质性质1

若非零向量系d0,d1,d2,…,dm-1是对G共轭，则这m个向量是线性无关的。性质2

在n维空间中互相共轭的非零向量的个数不超过n。性质3

从任意初始点出发，顺次沿n个G的共轭方向d0,d1,d2,…,进行一维搜索，最多经过n次迭代就可以找到的二次函数f(x)极小点。鲍威尔方法

鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。

基本思想是：直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。对函数：基本思想：在不用导数的前提下，在迭代中逐次构造G的共轭方向。

1.共轭方向的生成设xk,xk+1为从不同点出发，沿同一方向dj进行一维搜索而到的两个极小点。

梯度和等值面相垂直的性质,

dj和

xk,xk+1两点处的梯度gk,gk+1之间存在关系:另一方面，对于上述二次函数，其xk,xk+1两点处的梯度可表示为:因而有取这说明只要沿dj方向分别对函作两次一维搜索，得到两个极小点xk和xk+1

，那么这两点的连线所给出的方向dk就是与dj一起对G共轭的方向。2.基本算法二维情况描述鲍威尔的基本算法:

1）任选一初始点x0，再选两个线性无关的向量，如坐标轴单位向量e1=[1,0]T和e2=[0,1]T作为初始搜索方向。x1x2x0oe1e2d1d2x*12.基本算法2）从x0出发，顺次沿e1，e1作一维搜索，得点，两点连线得一新方向d1x1x2x0oe1e2d1d2x*1x1x2x0oe1e2d1d2x*1用

d1代替e1形成两个线性无关向量d1,e2

，作为下一轮迭代的搜索方向。再从出发，沿d1作一维搜索得点，作为下一轮迭代的初始点。

3）从出发，→

e2,→

d1

作一维搜索，得到点，两点连线得一新方向:2.基本算法x1x2x0oe1e2d1d2x*1沿d2作一维搜索得点x2

。即是二维问题的极小点x*

。方法的基本迭代格式包括共轭方向产生和方向替换两主要步骤。2.基本算法§5.4.3鲍威尔法（Powell法）两次平行搜索产生一个共轭方向，Powell法也是一种共轭方向法，能在有限步长内极小化一个二次函数，是直接搜索方法中使用效果最佳的一种方法。对于维数n<20的目标函数求最优化问题，此法可获得满意效果。Ⅰ、鲍威尔法基本原理、迭代格式原始的Powell法是沿着逐步产生的共轭方向进行一维搜索的。现以二维二次目标函数为例来说明。如下图所示，选定初始点X0(1)，初始方向：

S1(1)=e1=[1,0]T

S2(1)=e2=[0,1]T模式方向S(1)与S(2)之间的关系？

由图可知点X0(2)

、X2(2)是先后两次沿S(1)方向一维搜索的极小点。由共轭性质知：连接X0(2)

，X2(2)构成的矢量S(2)

与S(1)对H共轭。从理论上讲，二维二次正定函数经过这组共轭方向的一维搜索，迭代点已达到函数的极小点X*。将此结构推广至n维二次正定函数，即依次沿n个（S(1)

，S(2)，…，S(n)）共轭方向一维搜索就能达到极小点。Ⅱ、鲍威尔法缺陷当某一循环方向组中的矢量系出现线性相关的情况（退化、病态）时，搜索过程在降维的空间进行，致使计算不能收敛而失败。为了避免此种情况产生，提出了修正的Powell法。新一轮搜索方向新一轮搜索方向和原方向线性相关为了避免鲍威尔法缺陷，提出了修正算法。Ⅲ、修正Powell法映射点和原始Powell法的主要区别在于：在构成第k+1次循环方向组时，不用淘汰前一循环中的第一个方向S1(k)的办法，而是计算函数值并根据是否满足条件计算：

f1=f(Xk(0))f2=f(Xk(n))f3=f(Xk(n+2))找出前一轮迭代法中函数值下降最多的方向m及下降量△m，即：

△m=max｛[f(Xk(i))－f(Xk(i+1))]（i=0,1,…,n-1）｝

=f(Xk(m-1))－f(Xk(m))可以证明：若f3<f1

(f1-2f2+f3)(f1-f2-△m)2<0.5△m(f1-f3)2

同时成立表明方向Sk(n)与原方向组成线性无关，可以用来替换对象△m所对应的方向Sk(m)。否则仍用原方向组进行第k+1轮搜索。例：试用修正Powell法求f(X)=X12+2X22－4X1-2X1X2的最优解。X0=[1,1]T

，收敛精度ε=0.001。思考：如采用原始Powell法，如何判别此题具有几次收敛性？修正Powell算法是否具有同样的收敛性？提示：先沿(e1,e2)进行搜索：e1=[1,0]T，e2=[0,1]T解:f1=f(X0(1）)=－3第一次循环：沿坐标轴方向e1进行一维搜索：得则有代入f(X)令f(X)=X12+2X22－4X1-2X1X2f(X1(1）)=－7以X1(1）为起点，沿坐标轴方向e2进行一维搜索：f(X2(1）

)=－7.5检验是否满足终止迭代条件

代入f(X)并令得则有f(X)=X12+2X22－4X1-2X1X2计算各个方向的函数下降量：△1=f(X0(1))－f(X1(1))=-3－(-7)=4△2=f(X1(1))－f(X2(1))=-7－(-7.5)=0.5映射点：

条件：

满足。故沿新的搜索方向进行

沿作一维搜索：

代入f(X),令

得

=故有，

故以为新起点，沿（）方向一

，沿方向进行一维搜索

维搜索，进行第二次循环：

以为起点沿方向进行搜索，得，

检验：继续进行迭代，计算：

映射点：

条件不成立。进行继续迭代时取

沿方向一维搜索进行第三循环，并得：

,,基本情况同第二循环但更接近极极小点。由第二循环产生的新方向为：由于及为共轭方向，方向进行一维搜索得到

即为目标函数的最优解：目标函数是二次函数，若沿例3-14用改进的鲍威尔法求目标函数解：（1）第1轮迭代计算，沿e1方向进行一维搜索。的最优解。已知初始点[1,1]T，迭代精度例3-14用改进的鲍威尔法求目标函数，沿e1方向进行一维搜索得以为起点，沿第二坐标轴方向e2

进行一维搜索得确定此轮中的最大下降量及其相应方向

反射点及其函数值，

，检验Powell条件由于满足Powell条件，则淘汰函数值下降量最大的方向e1，下一轮的基本方向组为e2，。构成新的方向

沿方向一维搜索得极小点和极小值此点为下轮迭代初始点。

按点距准则检验终止条件

需进行第二轮迭代计算。（2）第2轮迭代计算此轮基本方向组为e2，，分别相当于，，起始点为＝。沿e2方向进行一维搜索得

以为起点沿方向一维搜索得构成新的方向求反射点及其函数值检验Powell条件。

沿方向进行一维搜索得确定此轮中函数值最大下降量及其相应方向检验终止条件

（3）第3轮迭代计算此轮基本方向组为，，起始点为＝，先后沿，方向，进行一维搜索，得，，故最优解检验终止条件

实际上，前两轮迭代的，为共轭方向，由于本例目标函数是二次函数，按共轭方向的二次收敛性，故前两轮的结果就是问题的最优解，但每一轮迭代都需要进行n+1次迭代。三、梯度法1.基本思想

梯度方向是函数值增加最快的方向，而负梯度方向是函数下降最快的方向，所以梯度法以负梯度方向为搜索方向，每次迭代都沿着负梯度方向一维搜索，直到满足精度要求为止。因此，梯度法又称为最速下降法

设在某次迭代中已取得迭代点X(k)，从该点出发，取负梯度方向为搜索方向S(k)，即：这样，第k+1次迭代计算所得的新点为：上式即为梯度法迭代公式。

因为X(k)已知，故和不难求出，只要知道步长

后，就可以得到新点X(k+1)。由于每次迭代能保证，如此反复计算，最后总能达到最优点X*。为了使目标函数值在搜索方向S(k)上获得最多的下降，每次迭代都进行一维搜索求最优步长，即求2.迭代步骤1）任选初始点X(0)，计算精度ε，令k=0

；2）计算和；3）收敛判断，

A.若，则X(k)为近似最优点，停止迭代，输出最优解和；

B.若，则转下一步继续迭代；4）令5）确定最优步长因子，使6）计算；7）令k=k+1，转2）。解：（1）

如果转（2），否则转（5）。【例11】用一阶梯度法求目标函数f(X)=x12+4x22

在初始点X(0)=[22]T，迭代精度=10-2

下的最优解。（2）（3），并转（1）。（4）第7次迭代后，成立，停止迭代。（5）取时，

f(X*)=2.596×10-6≈0梯度法的特点：负梯度方向只是函数值在点X(k)的邻域内下降最快的方向，离开该邻域以后函数值不一定下降最快。因此，采用负梯度方向，从局部看函数值下降快，从全局看却要走很多弯路。因此，梯度法的收敛速度较慢。梯度法的迭代过程，每相邻两步的搜索方向是垂直的，也就是说梯度法的迭代路线是呈锯齿形前进的。梯度法迭代过程中，当迭代点离理论极小点较远时，一次迭代的函数值下降量大。迭代点离极小点越近，函数值下降的速度就越慢。因此，梯度法常与其它优化方法结合使用。即第一步采用梯度法，后面采用其它的方法确定搜索方向。梯度法的收敛速度与目标函数的性质有关。如果目标函数的等值线（面）为同心圆（球），则无论从哪里出发，只需要一次搜索就能达到极小点。四、牛顿法1.基本牛顿法设目标函数是连续二阶可微的，将函数在X(k)点按泰勒级数展开后，取到二次项将上式展开，得对X求导，设X(K+1)是极小点，并令一阶导数为0，得上式即为基本牛顿法的迭代公式，其中S(k)称为牛顿方向。例:用基本牛顿法求目标函数f(X)=x12+4x22在初始点X0)=[22]T，迭代精度1=10-2

下的最优解。解：（1）

（2）（3）如果成立，停止迭代，否则重复执行（1）。（4）取X*=X(1)=[00]T,f(X*)=0。举例用牛顿法求函数的极小值。ε=0.01解：(1)取初始点(2)计算牛顿方向故(3)极小值基本牛顿法的特点：对于二次函数而言，取到二次项的泰勒展开式就是目标函数本身。如果二阶导数矩阵正定，那么按基本牛顿法求出的X(1)就是目标函数的精确极小点。因此，对正定二次函数而言，牛顿法只需一次迭代就可以达到精确极小点。基本牛顿法迭代时步长总是为1，对非二次函数、非正定函数而言，一次迭代并不能达到极小点，有时还可能失效（即总是不能收敛）。2.阻尼牛顿法

基本牛顿法对非正定函数失效是因为沿牛顿方向搜索时，步长总是为1，这并不能保证找到的下一个迭代点是该方向上的极小点。为此，增加步长因子α和一维搜索过程。此时的牛顿法称为阻尼牛顿法。阻尼牛顿法比基本牛顿法多一个一维搜索过程阻尼牛顿法迭代步骤：1）选取初始点X(0)，计算精度ε，令k=0

；2）计算；3）4）5）按一维搜索结果，计算6）收敛判断，

A.若，则X(k+1)为近似最优点，停止迭代，输出最优解和；

B.若，则令k=k+1，转2）继续迭代；用阻尼牛顿法求目标函数极小值：解：（1）梯度（2）一维搜索（3）收敛判断最优解

数学分析表明，牛顿法具有很好的局部收敛性质，对二次函数来说，仅一步就达到优化点，但对一般函数来说，在一定条件下，当初始点的选取充分接近目标函数的极小点时，有很快的收敛速度，但若初始点选取离极小点比较远，就难保证收敛；另外，牛顿法必须求一阶导数、二阶导数矩阵及其逆阵，这对复杂的目标函数来说，是比较较困难的。

五、变尺度法（选学）梯度法构造简单，只用到一阶偏导数，计算量小，迭代初期收敛速度快，但当迭代点到最优点附近时收敛速度极慢；

变尺度法是在梯度法和牛顿法的基础上发展起来的一种优化方法。用得较多的是DFP（Davidon-Fletcher-Powell)变尺度法。1.基本思想牛顿法收敛很快，对二次函数只需迭代一次就能达到最优点，对非二次函数也能较快达到最优点，但牛顿法计算量和存储量偏大。而且某些函数可能根本无法计算二阶偏导数矩阵及其逆阵。

为了综合梯度法和牛顿法的优点，扬长避短，产生了变尺度法。变尺度法的搜索方向为变尺度法的基本迭代公式为2.变尺度矩阵的构建

变尺度矩阵A(k)的构建是从A(0)=I开始，通过迭代公式

A(k+1)=A(k)+E(k)得到的。E(k)称为修正矩阵，通过它的一步步修正，使A(k)逐步逼近，即使变尺度法的迭代方向逐步逼近牛顿方向。修正矩阵取不同的形式，就形成了不同的变尺度法。DFP变尺度法修正矩阵E(k)的构造公式为3.变尺度法的迭代步骤3.举例用变尺度法求函数的极小值。ε

=0.01解：(1)取初始点：(2)一维搜索(3)如何求？(4)搜索方向

与牛顿法比较其结果非常接近，从本例中可以看出用近似矩阵代替二阶导数及逆阵是可行的。如何判断搜索结束？表1无约束优化方法搜索方向之间的相互联系——间接法（海赛矩阵的逆阵）无约束优化方法——间接法总结1、梯度法方向负梯度用到一阶导数适合于精度不高或用于复杂函数寻找一个好的初始点2、牛顿法用到一阶导数和海色矩阵，具有二次收敛性要求海色矩阵非奇异，且维数不宜太高3、共轭梯度法用到一阶导数，具有二次收敛性4、变尺度法收敛