优化设计的理论与数学基础NEW

1、2-1 目标函数的泰勒展开 2-2 优化方法中搜寻方向的理论基础 2-3 凸集与凸函数 2-4 优化问题有最优解的条件,第二章 优化设计的理论与数学基础,2,教学目的、要求 1熟悉函数梯度的概念 2掌握无约束优化最优解的条件 3掌握KT-条件的应用 教学重点 1梯度矩阵和海赛矩阵 2凸函数的性质 3共轭方向,方向导数,从多元函数的微分学得知，对于一个连续可微函数f(x)在某一点 的一阶偏导数为：,它表示函数f(x)值在 点沿各坐标轴方向的变化率。,有一个二维函数，如图2-1所示。,1.方向导数,图2.1 函数的方向导数,其函数在 点沿d方向的方向导数为,6,2-1 目标函数的Taylor 展开

2、式,式中,一、 一元函数的Taylor 展开式,泰勒（Taylor）中值定理 如果函数f(x)在含有x(k)的某个开区间(a,b)内具有直到(n+1)阶的导数，则对任一x ，有,拉格朗日余项,7,* 在实际计算中, 常取前三项(二次函数)来近似原函数:,8,二、 多元函数的Taylor 展开式,1.二元函数的Taylor 展开式（取到前三项）,矩阵相乘,9,式中,点距矢量,梯度矢量,二阶偏导数矩阵,10,2.推广到n维目标函数,(4),海赛矩阵,11,解：因为,则,又因为：,故Hesse阵为：,12,例题:,用泰勒展开将函数,13,简化的线性函数,简化的二次函数,14,三、 二次型函数,是指含

3、有n个自变量的二次齐次函数,15,16,17,* 矩阵A为正定的充要条件-A的各阶主子式均大于零。,如 为正定，则必有：,18,2-2 等值（线）面,对于可计算的函数 f(X)，给定一个设计点 X(k)(x1(k),x2(k), ,xn (k)，f(X)总有一个定值c 与之对应；而当f(x)取定值 c 时，则有无限多个设计点X(i)(x1(i), x2(i), ,xn(i) ) （i=1,2, ）与之对应，这些点集构成一个曲面，称为等值面。,当 c 取c1,c2, 等值时，就获得一族曲面族，称为等值面族。,19,当f(x)是二维时，获得一族等值线族； 当f(x)是三维时，获得一族等值面族； 当

4、f(x)大于三维时，获得一族超等值面族。,二维等值线,20,等值线的“心” （以二维为例）,一个“心”：是单峰函数的极（小）值点，是全局极（小）值点。 没有“心”：如线性函数的等值线是平行的，无“心”，认为极值点在无穷远处。,多个“心”：不是单峰函数，每个极（小）值点只是局部极（小）值点，必须通过比较各个极值点和“鞍点”（须正确判别）的值，才能确定极（小）值点。,21,等值线的形状： 同心圆族、椭圆族，近似椭圆族；,等值线的疏密： 沿等值线密的方向，函数值变化快； 沿等值线疏的方向，函数值变化慢。 等值线的疏密定性反应函数值变化率。,严重非线性函数病态函数的等值线族是严重偏心和扭曲、分布疏密严

5、重不一的曲线族。-不利于优化设计,22,2-2 关于优化方法中搜索方向的理论基础,1.方向导数,一.函数的最速下降方向,2.最速下降方向,二.共轭方向,1.正定二次函数,2.共轭方向的基本概念,3.构成共轭方向的方法,23,1)定义-函数沿指定方向 的平均变化率的极限。,1. 方向导数,一.函数的最速下降方向,24,2)方向余弦,25,3)方向导数的计算,26,2.最速下降方向,因为,于是,单位矢量,令,27,2-2 优化方法中搜寻方向的理论基础,连续可微的n维目标函数F(X)，在点X(k)的一阶偏导数为,分别表示F(X)在X(k)沿各坐标轴方向的变化率,28,二维函数,函数 在X(k)点处沿

6、 方向的方向导数为,方向导数表示函数F(X)在点X(k)沿 方向的变化率,29,证明:由于函数可微，则增量可表示为,30,方向导数表示函数F(X)在点X(k)沿 方向的变化率,31,对于n维目标函数F(X) ，其方向导数,2.梯度,梯度的模,32,单位矢量,从上式可得出如下结论：,* 最速下降只是局部性质.,3）在与梯度垂直的方向（等值线的切线方向）上，函数的变化率为零。,2）梯度的模是最大的方向导数。 负梯度方向是函数的最速下降 方向，该方向为等值线（面） 的法线方向；,1）方向导数是梯度在指定方向上的投影；,解,方向导数,35,则函数在 处的最速下降方向是,例： 试求目标函数 在点 处的最

7、速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。,解： 由于,36,新点是,这个方向上的单位向量是：,37,二.共轭方向,*当n=2时，,1）矩阵表示,1.正定二次函数,也适于多元函数,38,2)正定二元二次函数的特点,（1）正定二元二次函数的等值线是一族同心椭圆，其中心坐标就是该函数的极小点。,（2）过同心椭圆族的中心作任意直线与椭圆族中任意两椭圆相交，再过两交点所作相应椭圆的切线必相互平行。,39,2.共轭方向的基本概念,* 几何意义: 经过线性变换A后成了与 正交的向量.,例：,设A为nn阶正定对称矩阵， 是两个n维向量，若存在 则称 对A共轭。,1)定义,40,2)共轭方

8、向的性质,* 这种性质称为有限步收敛性（亦称二次收敛性）,（2）从任意选定的初始点出发，只要依次沿n个共轭方向进行一维搜索，一轮后便可达到n元正定二次函数的极小点。,(证明见席少霖:最优化方法，P97）,（1）若矢量系 彼此对正定对称矩阵A共轭，则它们组成线性无关的矢量系；,41,3.构成共轭方向的方法,设 为平行于 的两条直线，则过这两直线上正定 n元二次目标函数的极小点 的向量 和 对Hession矩阵A共轭。,42,证明：,二次函数,其梯度为,因 分别为两直线上的极小点，故有,将上述两式相减,43,例：对于目标函数 ，给定 ，试求出与 共轭的方向 ，并求出目标函数的极小点。,2）取初始点

9、 ，沿 方向搜索,解：,1）,44,再从 出发，沿 搜索得,45,2-3 凸集与凸函数,凸集,非凸集,*若X是X1和X2连线上的点，则有,一、凸集- 若任意两点 ，对于 ， 恒有 ， 则 D 为凸集。,整理后即得,46,二 凸函数,设f(X)为定义在 Rn 内一个凸集D上的函数，若对于 及D上的任意两点X1,X2,恒有 则f(X)为定义在D上的一个凸函数。,1.定义,47,2.凸函数的基本性质,两边乘上,证: 由定义,（1）设 为定义在凸集D上的凸函数， 为任意正实数,则 也是定义在 D上的凸函数。,48,证: 由定义,（2）设 、 均为定义在凸集D上的凸函数，则 + 也是定义在 D上的凸函数

10、。,（3）设 、 均为定义在凸集D上的凸函数， 为任意正实数，则 也是定义在D上的凸函数。,两式相加,整理后可得证.,49,3.凸函数的判定,若D为凸集，F(x)为定义在D上的凸函数，则此规划为凸规划。,对于数学规划问题：,4.凸规划,凸规划的最优点是唯一的.,50,解： 函数为凸函数的充要条件为：海赛矩阵是正定的。 海赛矩阵,故海赛矩阵正定，因此F(X)为凸函数。,51,52,二、共轭方向,*当n=2时，,1）矩阵表示,1.正定二次函数,53,2) 正定二元二次函数的特点,) F=f 时有极小. 此时椭圆缩为一点, 即椭圆中心.,) F只影响椭圆的大小, 不影响其中心位置-同心;,椭圆方程经

11、平移和转动后可去掉一次项和交叉项, 故写成下述形式不失一般性:,因函数为正定，故A为正定，即： 由于判别式0，无论F(X)取何值,所得方程均为椭圆方程,证：,（1）正定二元二次函数的等值线是一族同心椭圆，其中心坐标就是该函数的极小点。,54,（2）过同心椭圆族的中心作任意直线与椭圆族中任意两椭圆相交，再过两交点所作相应椭圆的切线必相互平行。,为常量,说明该直线上各椭圆的斜率均相等.,设过中心的直线为 , 代入上式得:,就上式对 求导:,证:,2.共轭方向的基本概念,1)定义,由（3）,正交矢量的点积为0,设A为2*2阶正定对称矩阵， 是两个2维向量，若存在 则称 对A共轭。,例：,57,* 几

12、何意义: 经过线性变换A后成了与 正交的向量.,设A为n*n阶正定对称矩阵， 是两个n维向量，若存在 则称 对A共轭。,58,2-3 凸集与凸函数,当极值点X*能使f（X*）在整个可行域中为最小值时，即在整个可行域中对任一X都有f（X）f（X*）时，则X*就是最优点，且称为全域最优点或整体最优点。若f（X*）为局部可行域中的极小值而不是整个可行域中的最小值时，则称X*为局部最优点或相对最优点。最优化设计的目标是全域最优点。为了判断某一极值点是否为全域最优点，研究一下函数的凸性很有必要。 函数的凸性表现为单峰性。对于具有凸性特点的函数来说，其极值点只有一个，因而该点既是局部最优点亦为全域最优点。

13、,59,一、凸集,设D为n维欧氏空间中的一个集合，若其中任意两点X(1)、X(2)之间的联接直线都属于D，则称这种集合D为n维欧氏空间的一个凸集。图2-3（a）是二维空间的一个凸集，而图2-3（b）不是凸集。,60,X,距离y,D,凸集的数学表达,点X的表达式为,对于集合D内的任意两点X1与X2连线，如果连线上的任意点X均满足： 则该集D定义为一个凸集。,61,二、凸函数,如去掉式中的等号,则称严格凸函数,设F(X)为定义在 Rn 内一个凸集D上的函数，若对于 及D上的任意两点X1,X2,恒有 则F(X)为定义在D上的一个凸函数。,1.定义,一元凸函数的几何意义,62,2.凸函数的基本性质,证

14、: 由定义 两边乘上 :,i）设 为定义在凸集D上的凸函数， 为任意正实数则 也是定义在 D上的凸函数。,63,ii）设 、 均为定义在凸集D上的凸函数，则 + 也是定义在 D上的凸函数。,证: 由定义 两式相加, 整理后可得证。,iii）设 、 均为定义在凸集D上的凸函数， 为任意正实数，则 也是定义在 D上的凸函数。,64,ii）对于整个可行域，恒有 ， 则X*为全局极小点；,i）对于X*的一个邻域，恒有 ， 则X*为局部极小点；,3.局部极小点和全局极小点,三、凸规划,对于约束优化问题,式中若F（X）、 均为凸函数，则称此问题为凸规划。,2）凸规划问题中的任何局部最优解都是全局最优解；,

15、1）可行域 为凸集；,凸规划的一些性质：,66,2-4 优化问题有最优解的条件,2.多元函数具有极小值的充要条件,1.一元函数具有极小值的充要条件,一、无约束优化最优解的条件,67,简易证明：,由矩阵理论可知,因,故,68,例：求 的极小点。,解：,69,二、约束优化最优解的条件,1.约束优化问题的类型,（1）IP型（不等式约束优化问题）,（2）EP型（等式约束优化问题）,70,（3）GP型（一般约束优化问题）,71,（2）对于整个可行域，恒有 ， 则X*为全局极小点；,（1）对于X*在可行域中的一个邻域，恒有 ，则X*为局部极小点；,2局部极小点与全局极小点,72,3.IP型约束问题解的必要

16、条件,等价于无约束优化问题,（1）,73,（2）目标函数是凸函数,可行域是凸集，则目标函数等值线与适时约束曲面的切点为最优点，而且是全局最优点。,74,（3）迭代点位于两约束的交点上。,75,2.约束问题解的必要条件,推广至n维目标函数,（1）EP型,76,77,对IP型优化问题，X*为最优解的条件为：,该问题共有P个约束，对于不起作用约束, 。,（2）IP型约束问题解的必要条件,78,(3).GP型约束问题解的必要条件,综合1、2两种情况，GP型约束问题解的必要条件为,上述条件称为库恩塔克条件（KT条件）,79,80,K-T条件是多元函数取得约束极值的必要条件,以用来作为约束极值的判断条件，

17、又可以来直接求解较简单的约束优化问题。,对于目标函数和约束函数都是凸函数的情况， 符合K-T条件的点一定是全局最优点。这种情况K-T条件即为多元函数取得约束极值的充分必要条件。,3.K-T条件的应用,）进行可行性检查，找出起作用约束； ）对起作用约束求拉氏乘子，若 非负， 有确定值，则 X* 为 K-T 点。,对X*进行检验,81,例：库恩塔克（K-T）条件应用举例,s.t,判断1 0T是否为约束最优点。,82,(1)当前点 为可行点，因满足约束条件,(3) 各函数的梯度：,（2）在 起作用约束为g1和g2 , 因,83,（4）求拉格朗日乘子,由于拉格朗日乘子均为非负，说明 是一个局部最优点，因为它满足K-T条件。,84,s.t,85,86,1.对于目标函数,要求在点X(k)=2,2.5T作二次taylor展开，写出用于逼近的二次型函数。,解：,87,取上式的二次项部分，得到用于逼近的二次型函数为,88,2.已知优化数学模型,要求：1）画出目标函数等值线及可行域D； 2）设计点X(k)=1,1T 、X(k)=2,0.5T是否为可行点； 3）可行域是否为凸集； 4）标出约束最优点，并