第三章-无约束最优化方法

1第三章无约束最优化方法同济大学土木工程学院建筑工程系杨彬[e-mail]2第三章无约束最优化方法最优化的数学模型为求minsubjectto(ors.t.)12,,,xxTnnxxxRxf0xjg1,2,,jm0xkh1,2,,kmmp数学规划方法是在规定的约束条件下，用数学手段直接求目标函数的极大、极小值。特殊情况：31、无约束最优化问题——不存在约束条件2、线性规划——当目标函数、约束函数均是变量X的线性函数时3、非线性规划——当函数中至少有一个是非线性函数时第三章无约束最优化方法43-1无约束最优化方法概述无约束最优化问题是数学规划的基础。第三章无约束最优化方法求函数极小值。无约束最优化问题的定义：求函数的极小（或极大）值，（n维欧氏空间）。xfxnR5第三章无约束最优化方法根据函数极值条件确定了极小点*x则函数f(x)在附近的一切x均满足不等式*x*fxfx所以函数f(x)在处取得局部极小值，称为局部极小点。*x*x而优化问题一般是要求目标函数在某一区域内的全局极小点。函数的局部极小点是不是一定是全局极小点呢？一、最优性条件6下凸的一元函数第三章无约束最优化方法可以证明凸规划问题的局部最小点就是其全局最小点。7凸集一个点集（或区域），如果连接其中任意两点的线段都全部包含在该集合内，就称该点集为凸集，否则为非凸集。1x2x2x第三章无约束最优化方法8凸函数函数f(x）为凸集定义域内的函数，若对任何的011x2x及凸集域内的任意两点存在如下不等式：121211()fxxfxfx称fx是定义在凸集上的一个凸函数。第三章无约束最优化方法9第三章无约束最优化方法10凸规划对于约束优化问题minfx..st0jgx1,2,...,jm若fxjgx都为凸函数，则此问题为凸规划。第三章无约束最优化方法11第三章无约束最优化方法设Q是n×n阶对称矩阵。若且都有，则称矩阵Q是正定的xnR0x0xQxT若都有，则称矩阵Q是半正定的0xQxTxnR若且都有，则称矩阵Q是负定的xnR0x0xQxT若都有，则称矩阵Q是半负定的xnR0xQxT一个对称矩阵是不是正定的，可以用Sylvester定理来判定。定理(Sylvester)一个n×n阶对称矩阵Q是正定矩阵的充分必要条件是，矩阵Q的各阶主子式都是正的。正定矩阵12第三章无约束最优化方法多元函数的梯度和性质定义以的n偏导数为分量的向量称为在x处的梯度，记为梯度也可以称为函数关于向量x的一阶导数。xfxf12,,,xxxxTnffffxxxxf13第三章无约束最优化方法梯度的性质①、函数在某点的梯度若不为零，则必与过该点的等值面“垂直”；②、梯度方向是函数具有最大变化率的方向。如图所示，证明上面性质①。为了证明性质②引入方向导数的概念。梯度方向与等值面的关系14第三章无约束最优化方法方向导数沿d方向的方向向量12coscos...cosnd即00Txffxdd0cos,Tfxfd15第三章无约束最优化方法方向导数的正负决定了函数的升降，而升降的快慢就由它的绝对值大小来决定。方向导数又称为函数在点x0处沿d方向的变化率。下降最快的方向称为最速下降方向。0fxdxf16第三章无约束最优化方法Hessian矩阵（函数的梯度是它的一阶导数，Hessian矩阵是函数的二阶导数）xfxfxf22222111222221222222212nnnnnfffxxxxxfffffxxxxxfffxxxxx**xxxxxxxxxxx函数取得极小的充分条件是函数的Hessian矩阵为正定方阵xfxf17第三章无约束最优化方法方阵为正定的定义是：若对任何向量d(d!=0)，有f2*x0Tfd2*dx对称正定方阵的检验方法是所有主子式均大于零。f2*x二、迭代方法求解minxf12,,,xxTnnxxxR的问题可以转变为求解n元方程组0xf无约束最优化问题的问题。一般地，这是一个非线性方程组，可对其采用迭代法求解之。18第三章无约束最优化方法下降迭代算法算法：给定目标函数的极小点的一个初始估计点，然后按一定的规则产生一个序列，这种规则通常称为算法。如果这个序列的极限恰好是问题（3-1）的极小点，即xf0xxk*x*limxxkk或等价地*lim0x-xkk那么就说该算法所产生的序列收敛于*x19第三章无约束最优化方法下降迭代法：在给定初始点后，如果每迭代一步都使目标函数有所下降，即，那么这种迭代法称为下降法。1xxkkff假定我们已经迭代到点处，那么下一步迭代将有以下两种情况之一发生：xk①、从出发沿任何方向移动，目标函数不再下降。是局部极小点，迭代终止。②、从出发至少存在一个方向使目标函数有所下降。这时，从中选定一个下降方向，再沿这个方向适当迈进一步，即在直线xkxkxkpk20第三章无约束最优化方法xxpkkt上适当选定一个新点1xxpkkkkt使得k+1kxxpxkkkfftf那么就说完成了第次迭代。上式中的称为步长因子。1kkt在迭代过程中有两个规则需要确定：一个是下降方向的选取；一个步长因子的选取。pkkt21第三章无约束最优化方法下降迭代算法的基本格式如下：①、选定初始点，置；②、按某种规则确定使得③、按某种规则确定使得④、计算⑤、判定是否满足终止准则，若满足，则打印和，停止迭代计算；否则置，转②继续迭代。0x0kpk0xpTkkfktkxpxkkkftf1xxpkkkkt1xk1xk1xkf1kk22第三章无约束最优化方法上述算法可用如下框图表达开始选定x0确定p使得确定t使得0)(0pxfT)()(00xftpxftpxx0x满足终止准则xx0X,f(x)停是否23第三章无约束最优化方法三、无约束最优化方法的分类解析法直接法数学模型复杂时不便求解可以处理复杂函数及没有数学表达式的优化设计问题直接法:单变量直接法——0.618法，分数法，抛物线法，多项式插值；多变量直接法（爬山法）——模态搜索法，方向加速法，单纯形法。解析法:函数的导数——梯度法，牛顿法，共轭梯度法，变尺度法等。243-2一维搜索（0.618法）3-2一维搜索——0.618法——实际问题的最优设计变量很多，经过分析简化，可以只考虑对目标函数影响最大的一个变量，也就是单变量的最优设计问题。一维搜索就是求一元函数的极小点，即假定，且函数可微，则由极限的必备条件得一维搜索又称为直线搜索。minfxx1fxR0fx250.618法0.618法适用于一般的单峰函数。所谓单峰函数，是指这样的函数：在极小点的左边，函数是严格减小的；在的右边，函数是严格增加的。也就是说，若是任意两点：*x*x12xx当时，则*2xx12fxfx当时，则*1xx12fxfx3-2一维搜索（0.618法）26从图中可看出，假定不知道极小点的位置，任取两点，如果，则必在之间；若，则；若，则。*x12xx12fxfx*x12,xx12fxfx*2xx12fxfx*1xx3-2一维搜索（0.618法）27设给定一个较小的步长δ，从α=0开始，先计算φ(0)，然后计算在的函数值φ(δ)；如果φ(δ)φ(0)，则讲步长δ增大1.618倍，得到一个新点,计算φ(2.618δ)；如果φ(2.618δ)仍小于φ(δ)，再继续增加步长为原步长的1.618倍，如下图所示，从而得到一系列点的αj的值为3-2一维搜索（0.618法）0)618.1(618.2618.11)-(3.2)618.1(0'jij28在内任取两点，由上面的讨论可以知道，通过比较与，立刻可以断定极小点在区间内，还是在内，这样区间被缩小了，新的区间取作。在中，又可取两点，通过比较函数值得到新的区间，这样不断缩小区间，最后便可确定出近似的极小点，如图所示。,ab11xx1fx1fx1,ax1,xb11,ab11,ab22xx22,ab3-2一维搜索（0.618法）29应该怎样选取与呢？ixix设区间的长为1，在与点相距分别为和的点插和。为确定和，我们提出一些条件：,aba1x1x第一，希望和两点在中的位置是对称的。这样一来，无论删除哪一段，总是保留长为的区间（板书所示）。按这一条件有ixix,ab11axxb即1（3-2.1）3-2一维搜索（0.618法）30第二，无论删除哪一段，例如删除，在保留下来的区间里，再插入一个点使得，在中的位置与和在中的位置具有相同的比例。这就保证每次迭代都以同一的比率缩短区间。按这一条件有1,xb2x2x1x1,ax'1x1x,ab''1121'111axaxaxababax即1（3-2.2）或23-2一维搜索（0.618法）31把（3-2.1）代入（3-2.2）中得到关于的一元二次方程210合理的根是510.6182350.3822上述缩短搜索区间的迭代方法称为黄金分割法或优选法。下面介绍它的步骤。3-2一维搜索（0.618法）32算法（黄金分割法）已知，终止限。fx①确定的初始搜索区间；②计算，；③计算，；④若，则打印，停机；否则，若，转⑤；⑤判断是否满足；若满足，则置然后转③；否则，若，则置然后转②。fx,ab1xaba21ffx11xabx11ffx11xx*112xxx11xx12ff11121,,bxxxff12ff11112,,axxxff3-2一维搜索（0.618法）33例3-1用0.618法求在区间上的极小值，要求极小点所在区间长度小于0.05。32393fxxxx1,5解第一次迭代（板书）1、在确定区间内取两个试验点,1,5ab11,xx110.3821.2920.6182.708xabaxaba2、计算函数值11,fxfx111.46420.486fxfx3、比较函数值11fxfx3-2一维搜索（0.618法）34是好点，要保留，于是区间缩小为，在此区间中，再去找好点。1x1,ax第一次迭代至此完毕，仿此步骤迭代数次后，得0.981,1.025,0.0440.05kkkkabba符合精度要求，无须再迭代。故极小点所在区间为，极小值为0.981,1.0251.0031.999952kkabff3-2一维搜索（0.618法）353-2一维搜索（0.618法）36例3-2有一简支鱼腹式金属吊车梁，中心点有一集中荷载，求最轻设计的断面值。50,130PkNMPa解如图所示，设跨距中间1/3部分与其它部分的梁高分别为和，梁宽为。根据构造要求1x2x3x22310,2xxcmx3-2一维搜索（0.618法）37由简支梁的弯矩图知134236middlePlMPlPlM相应的抗弯模量为1132middleMSMS3-2一维搜索（0.618法）3821322328851923xxxx化