数值最优化1.ppt

1、数值最优化,主讲：陈高洁 ,推荐教材： 李董辉等，数值最优化，科学出版社,参考教材 ： 1、袁亚湘，孙文瑜， 最优化理论与方法， 科学出版社 2、陈宝林， 最优化理论与算法，清华大学出版社,前言 一、什么是最优化 最优化是一门应用性相当广泛的学科，它讨论决策问题的最佳选择之特性，寻找最佳的计算方法，研究这些计算方法的理论性质及其实际计算表现。 应用范围：信息工程及设计、经济规划、生产管理、交通运输、国防工业以及科学研究等诸多领域。,二、包含的内容 按照优化思想分为经典方法与现代方法。 经典方法主要包括：线性规划、非线性规划、整数规划、动态规划等 现代方法主要包括：随机规划、模糊规划、模拟退火算

2、法、遗传算法、禁忌搜索和人工神经网络等。 我们学习的内容主要是经典的最优化方法。 内容包括无约束最优化方法、约束最优化方法、线性规划及其对偶规划等主要内容。,三、学习方法 1、认真听讲，课后及时复习巩固，并主动完成课后习题。 2、多看参考书，通过不同学者的讲述，全方位理解最优化方法的思想方法和应用，特别是计算方法。 3、学以致用，通过最优化方法的学习，培养研究生数学建模的能力和解决实际问题的能力。大家可以尝试对于一些实际问题，先建立数学模型，转化为数学问题，通过一些算法解决。,课程内容,一、基本概念与基础知识 (第一章、第二章),二、最优性条件 (第二章、第八章),三、各类算法 (其它各章),

3、第一章 引言,第一节 最优化问题概述 第二节 凸集与凸函数,1. 最优化问题的提出,例1.1.1（食谱问题）设市场上可以买到n种不同的食品，每种食品含有m种营养成分。设每单位的j种食品含i种营养成分的数量为aij，i=1,，m, j=1,n.第j种食品的单位价格为cj, j=1,n.再设每人每天对第i种营养成分的需求量为bi,i=1,m.试确定在保证营养需求条件下的经济食谱。,例1.1.2（数据拟合问题）设有观测数据(xk, yk), k=1,5,其值由表1.1给出：,试用一个简单的函数关系拟合这些数据。,2. 最优化问题的数学模型,其中 是定义在 上的实值函数。,（1.1）,无约束最优化问题

4、 （ ） 约束最优化问题,基本概念：可行点、可行域,局部最优解,全局最优解,其中,到目前为止，大多数最优化算法求到的都是局部极小点。为了求得全局极小点，一种解决办法是，先求出所有的局部极小点，然后再从中找出全局极小点。,极大值问题与极小值问题的关系,3. 回顾几个数学概念,梯度向量：,Hessian矩阵：,例,梯度的性质：,当梯度,连续时，,第一，若,，则,必垂直于,过点,处的等值面；,第二，梯度方向是函数具有最大变化率的方向。,下面以,为例来解释这个性质。,下图是该函数的等值线图。,今考虑一点,，不妨取坐标为,。设想有,出发沿某个方向移动到了点,，其坐标,，那么目标函数值将产生如下变化量,一

5、动点从,设为,假定,。试问：动点沿哪个方向移动会使,目标函数值有最多的下降或上升？,从图上看，这相当于问：在以点,为圆心、以1为半径,的圆周上，哪一个点具有最大的或最小的目标函数值。,为了一般地描述函数,在点,处沿,情况及变化速度，须引入上升方向和下降方向及方向导数 的概念。,方向的变化,函数,在点,处沿,方向的变化反映的是函数,在一条直线上的变化，空间中由一点,和一方向,所确定的直线方程为,上升方向和下降方向 设,是连续函数。,若存在,，对于,都有,，则称,方向是,在点,处的上升方向；若存在,对于,都有,，则称,方向是,在点,处的下降方向。,定义1.9 设,在点,处可微，,是非,方向上的单位

6、向量。如果极限,零向量,存在，则称其为函数,在点,处沿,方向的方向导数，,。,记作,思考：,与,的异同。,若,，则,方向是,在点,处的上升方向；,根据极限理论，易见,若,，则,方向是,在点,处的下降方向。,因此，方向导数的正负决定了函数值的升降。,定理1.2 设,在点,处可微，则,，,其中,是非零向量,方向上的单位向量。,定理1.2又表明：只要,，则,方向是,在点,处的上升方向；只要,，则,方向是,在点,处的下降方向。,函数值升降的快慢则是由方向导数绝对值的大小决 定的。绝对值越大，升或降的速度就越快；绝对值越小， 升或降的速度就越慢。这是因为,据此有,) 等号成立当且仅当,与,同方向或与,同

7、方向。且当,与,同方向时，,取到最大值,。,当,与,同方向时，,取到最小值,) 若,是锐角，则,;,若,是钝角，则,。,因此，方向导数又可以称为函数,在点,处沿,方向的变化率。,使函数值下降最快的方向称为最速下降方向。,最速下降方向为,几个常用函数的梯度公式,（1）若,，则,，即,（2）,（3）,；,（4）,.,；,；,一阶Taylor 展开式：,二阶Taylor 展开式：,多元函数的Taylor展开式在最优化方法中十分重要， 许多方法及其收敛性的证明都是从它出发的。,首先将向量长度概念推广到Rn(或Cn)中.,称为向量x, y的数量积(内积). 将非负实数,称为向量x的欧氏范数.,定义1.

8、设x=(x1,x2,xn)T, y= (y1,y2,yn)TRn , 将实数,向量和矩阵的范数,我们还可以用其他办法来度量Rn中向量的“大小”. 例如, 对于x=(x1,x2)TRn, 可以用一个x的函数N(x)=max|xi|来度量 x 的“大小”, 而且这种度量 x 的“大小”的方法计算起来比欧氏范数方便. 在许多应用中, 对度量x的“大小”的函数N(x)都要求是正定的、齐次的且满足三角不等式. 下面我们给出向量范数的一般定义.,(1) |x|0(|x|=0当且仅当x=0) (正定性), (2) |x|=| |x|, 对任何R(或C)(齐次性), (3) |x+y| |x|+|y| (三角

9、不等式). 则称f(x)=|x|是Rn(或Cn)上的一个向量范数(或模).,定义2.(向量的范数) 如果向量xRn(或Cn)的某个实值函数f(x)=|x|，满足条件:,下面给出几种常用的向量范数, 设x=(x1,x2,xn)T.,容易证明前三种范数是的p-范数特殊情况, 其中,向量的-范数(最大范数),向量的1-范数,向量的p-范数(0p+),向量的欧氏范数, 2范数(本书中采用),例 计算向量 x=(1,-2,3)T的各种范数.,解,定理1. (向量范数的连续性) 设函数f(x)=|x|为Rn上任一向量范数, 则f(x)是x 的分量 x1,x2,xn的连续函数.,定理2.(向量范数的等价性)

10、 设|x|s, |x|t为Rn上任意的两种范数, 则存在常数c1,c20, 使得对一切xRn有,结论: 如果在一种范数意义下向量序列收敛时, 则在任何一种范数意义下该向量序列均收敛.,定理3. , 其中|为向量的任一种范数.,定义3. 设x(k)为Rn中一向量序列, x*Rn, 记 x(k)=(x1(k),xn(k)T, x*=(x1*,xn*)T. 如果,则称x(k)收敛于x*. 记为,下面我们将向量范数概念推广到矩阵上去. 可以将Rnn中的矩阵A=(aij)nn当作n2维向量, 则由向量的2-范数可以得到Rnn中矩阵的一种范数,称为A的Frobenius范数. |A|F显然满足正定性、齐次

11、性及三角不等式.,下面我们给出矩阵范数的一般定义.,定义4.(矩阵的范数) 如果矩阵ARnn的某个实值函数N(A)=|A|，满足条件:,(1) |A| 0 (|A|=0当且仅当A=0) (正定性)；,(2) |cA|=|c| |A|, c为实数 (齐次性)；,(3) 对任意A,B有|A+B| |A|+|B| (三角不等式),(4) 对任意A,B有|AB| |A| |B| (相容性)；,则称 N(A) 是Rnn上的一个矩阵范数(或模).,上面我们定义的F(A)=|A|F就是Rnn上的一个矩阵范数.,上述条件(即不等式)就称为矩阵范数与向量范数的相容性条件.,由于在大多数与估计有关的问题中, 矩阵

12、和向量会同时参与讨论, 所以希望引进一种矩阵的范数, 它是和向量范数相联系而且和向量范数相容的, 即对任何向量xRn及矩阵ARnn都成立,|Ax|A| |x|.,为此我们再引进一种矩阵的范数.,定义5.(矩阵的算子范数) 设xRn, ARnn, 给出一种向量范数|x|v(如v=1,2或), 相应地定义一个矩阵的非负函数,可验证|A|v满足定义4, 所以|A|v是Rnn上矩阵的一个范数, 称为A的算子范数.,定理4. 设|x|v是Rn上的一个向量范数, 则|A|v是Rnn上矩阵的范数, 且满足相容条件,显然这种矩阵的范数|A|v依赖于向量范数|x|v的具体含义. 也就是说, 当给出一种具体的向量

13、范数|x|v时, 相应地就得到了一种矩阵范数|A|v.,定理5. 设xRn, A=(aij)Rnn, 则有常用的算子范数,（称为A的行范数）,（称为A的列范数）,（称为A的2-范数）.,其中max(ATA)表示ATA的最大特征值, 由于矩阵2-范数与ATA 的特征值有关，所以又称为A的谱范数.,例.,求矩阵A的各种常用范数,解:,由于,特征方程为,容易计算,计算较复杂,对矩阵元素的 变化比较敏感,不是从属范数,较少使用,使用最广泛,性质较好,Jacobi矩阵,设向量值函数,连续可微.,在,点的Jacobi矩阵为,例,4. 凸集和凸函数,凸集和凸函数是线性规划和非线性规划都要涉及的 基本概念。关

14、于凸集和凸函数的一些定理在最优化 问题的理论证明及算法研究中具有重要的作用。,凸集,直观上，凸集就是空间中内部无“洞”，边界又不向 内凹的一些点的集合，其基本特征是该集合中任意两点 间的线段仍然属于这个集合。,非凸集,凸集,空间中两点间的线段是由点的凸组合定义的。,定义. 设,是,中的,个已知点。,点,，若存在满足,的非负实数,对于,使得,，则称,是,的一个凸组合。,又若,是满足,的正实数，则称,是,的一个严格凸组合。,两点,的凸组合,恰是连接两点的,的线段。,线段，而严格凸组合是不含端点,定义1.2.1 设集合,。如果,中任意两点的,，那么集合,称为凸集。,任意凸组合仍然属于,规定：空集是凸

15、集。,常见的凸集有超平面，直线，球.,凸函数,定义1.16 设,，其中,为凸集。若对于,中的任意互异两点,和任意一对满足,的非负实数,，,总有,则称,是定义在凸集,上的凸函数。又若对于任意,的正实数,，总有,一对满足,则称,是定义在凸集,上的严格凸函数。,若,是凸集,上的（严格）凸函数，则称,是凸集,上的（严格）凹函数。,凸函数有以下重要性质。,定理6,（1）若,是定义在凸集,上的凸函数，,是,也是,上的凸函数。,任意的非负实数，则,（2）若,是定义在凸集,上的凸函数，则,也是,上的凸函数。,由定理6易见，定义在凸集上的任意有限个凸函数 的任意非负组合仍然是凸函数。,定理1.7 设,，其中,为

16、非空凸集，若,是凸函数，则对于任意实数,，,水平集,是凸集。,判断一个函数是否为凸函数，一般说来，是比较困 难的。但当函数可微时，有以下几个判定定理。,定理7. 设,定理8. 设,二次连续可微，则下面的命题等价：,（1）函数,是凸函数.,定理8有明显直观的几何解释。 可微函数为凸函数的充要条件是在其 定义域凸集中任一点处的切平面（切 线）都不在曲面（曲线）的上方。右 图画出了一维的情形。,（2）对任意,，一元函数,是0,1上的凸函数.,（3）对任意,，下面不等式成立,（4）梯度函数,单调,（5）对所有,半正定.,定理9. 设,是二次可微函数，,为非,空开凸集。,则,为,上凸函数的充要条件是He

17、sse矩阵,在,上处处半正定。,定理10. 设,是二次可微函数，,为非,空凸集，,若,的Hesse矩阵,在,上处处正定，则,是,上的严格凸函数。,这个命题的逆命题不真。,例如，,在,上为严格凸函数，,在,处是半正定的。,但是它的Hesse矩阵,凸规划,设,是定义在非空凸集,上的凸函数，,则形式为,（1.36）,的最优化问题称为凸规划问题，简称凸规划。换言之， 定义在凸集上的凸函数的极小化问题是凸规划问题。,若,都是,上的凹函数，,都是,上的线性函数，容易验证集合,是凸集。在这种情况下，凸规划（1.36）可以表示成如下形式,（1.37）,下面的定理指出了凸规划的一些重要性质。,定理1.11 设,是凸规划（1.36）的局部极小点。则,i）,是（1.36）的全局极小点；,ii）当,是严格凸函数时，,是（1.36）的唯一极小点；,iii）（1.36）的全部极小点的集合是凸集。,定理1.12 设,是可微凸函数，,是非空,。,凸集，,则,是凸规划（1.36）的极小点的充要,中任意一点,，总有,。,条件是，对于,定理1.12表明，凸规划（1.36）在最优点处的任何 容许方向（定义4.3）都不是下降方向。,推论1.13 设,是可微