第三章 无约束最优化方法.ppt

1,建筑结构优化设计原理,第三章无约束最优化方法,同济大学土木工程学院建筑工程系杨彬Course_yb,2,第三章无约束最优化方法,最优化的数学模型为求minsubjectto(ors.t.),数学规划方法是在规定的约束条件下，用数学手段直接求目标函数的极大、极小值。特殊情况：,3,1、无约束最优化问题不存在约束条件2、线性规划当目标函数、约束函数均是变量X的线性函数时3、非线性规划当函数中至少有一个是非线性函数时,第三章无约束最优化方法,4,3-1无约束最优化方法概述,无约束最优化问题是数学规划的基础。,第三章无约束最优化方法,求函数极小值。,无约束最优化问题的定义：求函数的极小（或极大）值，（n维欧氏空间）。,5,第三章无约束最优化方法,根据函数极值条件确定了极小点,则函数f(x)在附近的一切x均满足不等式,所以函数f(x)在处取得局部极小值，称为局部极小点。,而优化问题一般是要求目标函数在某一区域内的全局极小点。,函数的局部极小点是不是一定是全局极小点呢？,一、最优性条件,6,下凸的一元函数,第三章无约束最优化方法,可以证明凸规划问题的局部最小点就是其全局最小点。,7,凸集,一个点集（或区域），如果连接其中任意两点的线段都全部包含在该集合内，就称该点集为凸集，否则为非凸集。,第三章无约束最优化方法,8,凸函数,函数f(x）为凸集定义域内的函数，若对任何的,称,是定义在凸集上的一个凸函数。,第三章无约束最优化方法,9,第三章无约束最优化方法,10,凸规划,对于约束优化问题,第三章无约束最优化方法,11,第三章无约束最优化方法,设Q是nn阶对称矩阵。,若且都有，则称矩阵Q是正定的,若都有，则称矩阵Q是半正定的,若且都有，则称矩阵Q是负定的,若都有，则称矩阵Q是半负定的,一个对称矩阵是不是正定的，可以用Sylvester定理来判定。,定理(Sylvester)一个nn阶对称矩阵Q是正定矩阵的充分必要条件是，矩阵Q的各阶主子式都是正的。,正定矩阵,12,第三章无约束最优化方法,多元函数的梯度和性质,定义以的n偏导数为分量的向量称为在x处的梯度，记为梯度也可以称为函数关于向量x的一阶导数。,13,第三章无约束最优化方法,梯度的性质、函数在某点的梯度若不为零，则必与过该点的等值面“垂直”；、梯度方向是函数具有最大变化率的方向。如图所示，证明上面性质。为了证明性质引入方向导数的概念。,梯度方向与等值面的关系,14,第三章无约束最优化方法,方向导数,沿d方向的方向向量,即,15,第三章无约束最优化方法,方向导数的正负决定了函数的升降，而升降的快慢就由它的绝对值大小来决定。方向导数又称为函数在点x0处沿d方向的变化率。下降最快的方向称为最速下降方向。,16,第三章无约束最优化方法,Hessian矩阵（函数的梯度是它的一阶导数，Hessian矩阵是函数的二阶导数）,函数取得极小的充分条件是函数的Hessian矩阵为正定方阵,17,第三章无约束最优化方法,方阵为正定的定义是：若对任何向量d(d!=0)，有,对称正定方阵的检验方法是所有主子式均大于零。,二、迭代方法,求解,min,的问题可以转变为求解n元方程组,无约束最优化问题,的问题。一般地，这是一个非线性方程组，可对其采用迭代法求解之。,18,第三章无约束最优化方法,下降迭代算法,算法：给定目标函数的极小点的一个初始估计点，然后按一定的规则产生一个序列，这种规则通常称为算法。如果这个序列的极限恰好是问题（3-1）的极小点，即,或等价地,那么就说该算法所产生的序列收敛于,19,第三章无约束最优化方法,下降迭代法：在给定初始点后，如果每迭代一步都使目标函数有所下降，即，那么这种迭代法称为下降法。,假定我们已经迭代到点处，那么下一步迭代将有以下两种情况之一发生：,、从出发沿任何方向移动，目标函数不再下降。是局部极小点，迭代终止。、从出发至少存在一个方向使目标函数有所下降。这时，从中选定一个下降方向，再沿这个方向适当迈进一步，即在直线,20,第三章无约束最优化方法,上适当选定一个新点,使得,那么就说完成了第次迭代。上式中的称为步长因子。,在迭代过程中有两个规则需要确定：一个是下降方向的选取；一个步长因子的选取。,21,第三章无约束最优化方法,下降迭代算法的基本格式如下：,、选定初始点，置；、按某种规则确定使得、按某种规则确定使得、计算、判定是否满足终止准则，若满足，则打印和，停止迭代计算；否则置，转继续迭代。,22,第三章无约束最优化方法,上述算法可用如下框图表达,23,第三章无约束最优化方法,三、无约束最优化方法的分类,解析法,直接法,数学模型复杂时不便求解,可以处理复杂函数及没有数学表达式的优化设计问题,直接法:单变量直接法0.618法，分数法，抛物线法，多项式插值；多变量直接法（爬山法）模态搜索法，方向加速法，单纯形法。,解析法:函数的导数梯度法，牛顿法，共轭梯度法，变尺度法等。,24,3-2一维搜索（0.618法）,3-2一维搜索0.618法,实际问题的最优设计变量很多，经过分析简化，可以只考虑对目标函数影响最大的一个变量，也就是单变量的最优设计问题。,一维搜索就是求一元函数的极小点，即假定，且函数可微，则由极限的必备条件得一维搜索又称为直线搜索。,25,0.618法0.618法适用于一般的单峰函数。所谓单峰函数，是指这样的函数：在极小点的左边，函数是严格减小的；在的右边，函数是严格增加的。也就是说，若是任意两点：,当时，则,当时，则,3-2一维搜索（0.618法）,26,从图中可看出，假定不知道极小点的位置，任取两点，如果，则必在之间；若，则；若，则。,3-2一维搜索（0.618法）,27,设给定一个较小的步长，从=0开始，先计算(0)，然后计算在的函数值()；如果()0，则新区间取为1,3若f(3)0则新区间取为3,2。然后定义为新区间1,2继续计算下去，直到满足误差限。,3-2一维搜索（两点格式）,52,常见的决定的方法有弦位法和二分法。弦位法是利用在点1的f(1)及点2的f(2)，对f()进行线性插值：,该式给出f()=0的点的近似值3：,由此得到：,3-2一维搜索（两点格式）,53,二分法简单地将取成0.5,即,二分法每次将搜索区间长度缩小为原长的一半，所以可以预测要经过多少次迭代才能将区间缩小到制定长度。例如，约经过20次迭代可以将原区间缩小为1/106的长度。,3-2一维搜索（两点格式）,54,3-3求多变量极值的直接搜索法,3-3求多变量极值的直接搜索法,单纯形法,55,所谓单纯形，是在n维空间里对n+1个顶点组成的多面体，如果这个额多面体各边相等，则成为正单纯形。单纯形的优化方法，就是在单纯形的顶点处的函数值进行比较，丢掉其中最坏的点，而代之以新的点，构成新的单纯形。按此顺序，每次把坏的丢掉，好的留下，逐步逼近极小点。,单纯形法第一步是选择一个合理的初始设计x0=(x01,x02x0n)T，并以它为顶点构建边长为a的正单纯形，通常规定其余顶点为：x1=x0+(p,q,q,q)T.xn=x0+(p,q,q,q)T,3-4无约束优化的单纯形法,56,可以验证该单纯形各边长为a，接着开始迭代过程。,设在第k次迭代得到一个单纯形，其n+1个顶点x0,x1.xn，迭代过程如下：,(1)准备。计算这n+1个顶点处的函数值：比较得到最优点xl、最坏点xh和次坏点xb;,去掉最劣点，把剩下点的形心找出来：,3-4无约束优化的单纯形法,57,(2)反射。以为中心将xh反射而得到，如图。,经验表明，取a=1较好。计算目标函数在的值。若，即比最好点还好，可让沿此直线延伸，转入第(3)步；否则转入第(4)步,3-4无约束优化的单纯形法,58,(3)延伸。让沿着直线延伸到：,一般取=2较好。然后计算该点处函数值，若则用代替，得到新的单纯形，然后再返回(1)；反之，说明延伸不成功，退回到，返回(1)。,3-4无约束优化的单纯形法,59,(4)收缩。进入这一步是因为：，即反射点不比最优点好，有两种可能：1、如果新点比次坏点还差，如果按老套路会出现死循环，故此时，从和中挑出一个最坏点并舍弃，如果舍弃，则把收缩到：,否则，按下式把收缩到：式中，0f(x(k),（2）方向S（k）和f(x(k)正交,（3）H-1存在但非正定，S（k）并不给出下山方向,（4）H-1不存在,89,三、共轭方向法和共轭梯度法,梯度法收敛慢，牛顿法虽加快了收敛，但每次要计算二阶导数矩阵及其求逆，计算工作量太大。共轭方向法收敛速度比牛顿法慢，但比梯度法快，而且不需要计算二阶导数和矩阵求逆，总的效果比牛顿法好。,考察二维情况,对于二元二次函数,3-5无约束最优化的解析法,90,任选初始点，沿某个下降方向作一维搜索得，即取得极值的充要条件是,而,故式（3-65）将变成,而且向量所在的直线必与某条等值线相切于点。,3-5无约束最优化的解析法,91,下一次迭代，若按最速下降法选择负梯度方向为搜索方向，那么，将要发生锯齿现象。,希望下一次迭代的搜索方向将直指极小点,方向应满足什么条件，怎样确定？,3-5无约束最优化的解析法,92,因为直指极小点，所以可以写成,对,求导,因为是极小点，所以,将式（3-68）代入式（3-70），可得,即,3-5无约束最优化的解析法,93,等式两边左乘,其中第一项，据式（3-67)等于零，为不等于零的常数，所以,这就是使向量直指极小点所必需满足的条件。,满足式（3-73）的两个向量和称为C的共轭向量，或称和的方向是共轭方向。,对于二元二次目标函数，从任意初始点出发，沿任意下降方向作一维搜索得到，再从出发沿的共轭方向作一维搜索得到的必是极小点。,3-5无约束最优化的解析法,94,例3-10用共轭方向法求函数的极小值，设初始点为。,3-5无约束最优化的解析法,95,3-5无约束最优化的解析法,96,3-5无约束最优化的解析法,97,共轭方向法,梯度法收敛慢，牛顿法虽加快了收敛，但每次要计算二阶导数矩阵及其求逆，计算工作量太大。,3-5无约束最优化的解析法,98,作为一种迭代法：共轭方向是在迭代过程中逐次产生的，在迭代的第一步中，取负梯度方向作为移动方向，即，而在以后各步中，则以负梯度方向加上已产生的方向的线性组合作为移动方向：,共轭梯度法,这时，利用向量与关于C共轭的特性，即,将式（3-75）两边的矩阵转置后均乘以，则得,3-5无约束最优化的解析法,99,这种在迭代过程中逐次产生共轭方向的方法，称为共轭梯度法。,当不是极小点时，可用下式代替式（3-77）：,这样，可以不必计算H（海色矩阵），而直接由函数的梯度计算的值。,3-5无约束最优化的解析法,100,共轭梯度法的迭代步骤如下：,1.给定初始值，并令。,2.对于k=0,1,2,.,n-1令,其中，可由下式求得,当kn-1时，令,其中,3-5无约束最优化的解析法,101,3.当，则迭代停止，否则以代替，并回到第一步。,3-5无约束最优化的解析法,用共轭梯度法求目标函数的极小值，初始点选在x(0)=(0,0)T，精度为0.01。,102,3-5无约束最优化的解析法,用共轭梯度法求目标函数的极小值，初始点选在x(0)=(0,0)T，精度为0.01。,103,3-5无约束最优化的解析法,用共轭梯度法求目标函数的极小值，初始点选在x(0)=(0,0)T，精度为0.01。,104,3-5无约束最优化的解析法,105,四、变尺度法牛顿法、梯度法可以归结为下述公式：,其中，为nn矩阵，若令矩阵等于单位矩阵，即，则得梯度法若令为F(X)的二阶导数矩阵的逆矩阵，便是牛顿法。,收敛慢,收敛快，但要求二阶导数和矩阵求逆，计算工作量大,变尺度法是选取一个，使其逼近海色矩阵的逆，则由式（3-79）确定的算法就可以保持收敛快的特点，又避免了冗繁的计算工作。,3-5无约束最优化的解析法,106,构造一个矩阵序列，使之逼近二阶导数矩阵的逆阵。,开始时，取，然后按下列递推公式计算每次迭代的H:,式中，为修正矩阵。可以构造不同形式的最常用的一种形式，构成变尺度法的递推公式：,其中,3-5无约束最优化的解析法,107,根据以上分析，可得变尺度法的迭代步骤：,1.给定初始点与初始矩阵,2.令,其中，求，使,3.若，则令，并终止迭代，否则利用,修正矩阵，并回到2，继续迭代。,3-5无约束最优化的解析法,108,3-5无约束最优化的解析法,用变尺度法求目标函数的极小值，初始点选在x(0)=(0,0)T，精度为0.01。,109,3-5无约束最优化的解析法,用变尺度法求目标函数的极小值，初始点选在x(0)=(0,0)T，精度为0.01。,110,3-5无约束最优化的解析法,111,3-6目标函数为平方和的极小问题,3-6目标函数为平方和的极小问题,最小二乘法、修正阻尼最小二乘法,对于有些实际问题，要求满足不等式方程组,的点X，这里为给定的性能控制指标，各可以相同、也可以不同。,一般地说，是非线性的，现在要解非线性不等式（3-82），经常采用的手段是把问题转化为求X，使,112,的问题。给定的诸，可以作为计算过程中的控制量，一旦达到所述要求，即可终止计算。,平方和形式,最小二乘法（高斯牛顿法）,函数（3-83）的一阶偏导数,设是函数（3-83）的极小点的一个近似点，为了求得下一个近似点，在附近将函数各项展开，取其线性近似式：,3-6目标函数为平方和的极小问题,113,3-6目标函数为平方和的极小问题,由式（3-84）得到f(X)的一个二次的逼近函数：,因为,即,其中,114,3-6目标函数为平方和的极小问题,又因为,即,将式（3-87）与式（3-88）代入一般无约束极值的牛顿公式：,得,这种把非线性最小二乘问题化为一系列线性最小二乘问题来求解的方法，就是通常所说的最小二乘法。,此法收敛速度慢些，但它避免了通常牛顿法中必须求二阶导数的逆阵。,115,3-6目标函数为平方和的极小问题,例求解,解：,先用一般求极