最优化方法(刘)第一章.ppt

1、最优化方法,刘丽华,第一章,基本概念, 1.1 最优化问题 简介,最优化是一门应用十分广泛的学科，它研究在有限种或无限种可行方案中挑选最优方案，构造寻求最优解的计算方法。达到最优目标的方案，称为最优方案，搜索最优方案的方法，称为最优化方法。这种方法的数学理论，称为最优化理论。,实际上最优化方法已广泛应用于空间技术、军事科学、电子工程、通讯工程、自动控制、系统识别、资源分配、计算数学、经济管理等等领域。,最优化方法包括的内容很广泛，如线性规划、非线性规划、整数规划、动态规划、多目标规划、组合优化等等。本教程重点介绍线性规划和非线性规划。,最优化问题的数学模型一般形式为：,（目标函数）,（等式约束

2、）,（不等式约束）,其中,相关定义（P7P8）,定义.1 可行解满足约束条(1.2)和(1.3) 的x称为可行解，也称为可行点或容许点。,定义.2 可行域全体可行解构成的集合称为可行域，也称为容许集，记为F,即：,定义.3 整体最优解若：,对于一切,则称,恒有,为最优化,问题的整体最优解。,若：,恒有,则称,为最优化,问题的严格整体,最优解。,定义.4 局部最优解若：,存在,的某邻域,使得对于一切,恒有,则称,为最优化问题的局,部最优解。,其中,同样有：严格局部最优解。,而局部最优解不一定是整体最优解。,显然，整体最优解一定是局部最优解，,注意：,求解最优化问题，实际上是求可行域,F上的整体最

3、优解。,但是，,在一般情况下，,整体最优解是很难求出的，往往只能求出局部最优解。,定义.5 范数P9：,在,维向量空间,中，,定义实函数,使其满足以下三个条件：,（）对任意,有,在,当且仅当,时,（）对任意,及实数,有,（）对任意,有,则称函数,为,上的向量范数。,两类比较常见的范数：,P-范数：,其中最常用的是2-范数，即：,范数：,最优化问题的分类,根据数学模型中有无约束函数分为有约束的最优化问题和无约束的最优化问题。,根据目标函数和约束函数的函数类型分类：线性最优化问题、非线性最优化问题、二次规划、多目标规划、动态规划、整数规划、规划。,1.2,一、凸集和凸函数,凸集,定义1,设集合,若

4、对于任意两点,及实数,都有：,则称集合,为凸集,注：,常见的凸集：空集，整个欧氏空间,超平面：,半空间：,例1：,证明超球,为凸集,证明：,设,为超球中的任意两点，,则有：,即点,属于超球,所以超球为凸集,凸集的性质,（）,有限个（可以改成无限）凸集的交集,为凸集,（）,设,是凸集，,是一实数，,则下面的,集合是凸集：,（）,设,是凸集，,则,的和集,是凸集,注：,和集和并集有很大的区别，凸集的并集,未必是凸集，而凸集的和集是凸集,例：,表示,轴上的点,表示,轴上的点,则,表示两个轴的所有点，,它不是凸集；,而,凸集,推论：,设,是凸集，,则,也是凸集，,其中,是实数,定义2:,设,实数,则,

5、称为,的凸组合,注：,凸集中任意有限个点的凸组合仍然在该,凸集中,极点,定义1,设,为凸集，,若,中不存在,两个相异的点,及某一实数,使得,则称,为,的极点,例：,则,上的点均为极点,证：,设,若存在,及,使得,则：,不等式要取等号，必须,且,容易证明,根据定义可知,为极点,凸函数P20-29,定义4,设函数,定义在凸集,定义在凸集,上，,若对任意的,及任意的,都有：,则称函数,为凸集,上的凸函数,定义5,严格凸函数,注：,将上述定义中的不等式反向，可以得到,凹函数的定义,例1：,设,试证明,在,上是严格凸函数,证明:,设,且,都有：,因此,在,上是严格凸函数,例2：,试证线性函数是,证明:,

6、设,上的凸函数,则,所以,是凸函数,类似可以证明,是凹函数,凸函数的几何性质,对一元函数,在几何上,表示连接,的线段,表示在点,处的,函数值,所以一元凸函数表示连接函数图形上任意两点,的线段总是位于曲线弧的上方,凸函数的性质,（）,设,（）,设,函数，,是凸集,上的凸函数，,实数,则,也是,上的凸函数,是凸集,上的凸,实数,则,也是,上的凸函数,（）,设,是凸集,上的凸函数，,是实数，,则水平集,是凸集,下面的图形给出了凸函数,的等值线的图形，可以看出水平集是凸集,凸函数的判定,定理1:,设,是定义在凸集,上，,令,则:,(1),是定义在凸集,是凸集,上的凸函数的充要条件是对,任意的,一元函数

7、,为,上的凸函数.,(2),设,若,在,上为严格,凸函数，,则,在,上为严格凸函数,该定理的几何意义是：凸函数上任意两点之,间的部分是一段向下凸的弧,一阶条件,定理2.1:,设在凸集,上,可微，,则：,在,上为凸函数的充要条件是对任意的,都有：,定理2.2:,严格凸函数(充要条件),二阶条件,定理3:,设在开凸集,内,二阶可微，则,(1),是,内的凸函数的充要条件为，,在,内任一点,处，,的海色矩阵,半正定,其中：,二阶条件,定理3:,设在开凸集,内,二阶可微，则,(2),若在,内,正定,则,在,内,二阶可微，则,是严格凸函数,注:,反之不成立,例：,显然是严格凸的，,但在点,处,不是正定的,

8、凸规划,定义6,设,为凸集，,为,上的凸函数，,则称规划问题,为凸规划问题,定理4,(1),凸规划问题的任一局部极小点,是,整体极小点，全体极小点组成凸集,(2),若,是凸集,上的严格凸函数，,且凸规划问题,整体极小点存在，,则整体极小点是唯一的,二、凸集的分离,定义1,设,为两非空凸集，,若存在,非零向量,和实数,使得：,则称超平面,分离了集合,和,注：,严格分离,定理1,设,是非空闭凸集，,但,则：,（）,存在唯一的点,使得集合,到点,的距离最小，,即：,（）,是点,到集合,的最短距离点的,充要条件为：,注：,闭凸集外一点与闭凸集的极小距离，,即投影定理。,定理2,设,为非空闭凸集，,则存

9、在非零向量,和实数,使得：,即存在超平面,严格分离点,与凸集,注：,点与闭凸集的分离定理。,引理1,设,为,矩阵，,则下述两组方程中有且仅有一组有解：,其中,注：,以上是在最优化理论研究中起重要作用,的Farkas引理。,定义2,设,为非空集合，,且点,属于集合,的边界，,即,若存在非零,向量,使成立：,或者,则称超平面,是集合,在其边界点,的支撑超平面。,定理3,设,为非空凸集，,则存在,非零向量,使成立,即凸集,在其边界点处存在支撑超平面，,其中,表示集合,的闭包。,注：,非空凸集在其任一个边界点处都存在,支撑超平面。,推论1,设,是非空凸集，,则存在,非零向量,使成立,定理4,设,是,的

10、两个非空凸集，,且,则存在超平面分离,和,即存在非零向量,使得,注：,以上是两凸集分离定理。,定理5,设,为,阶矩阵，,则或者存在,使,则或者存在,使,且两者不能同时成立。,注：,以上是非线性最优化理论中具有重要,作用的Gordan择一定理。,1.3 最优性条件,约束最优性条件,等式约束问题,一阶必要条件,定理1:,若,(1),是等式约束问题的局部最优解；,(2),与,在,的某邻域内,连续可微；,(3),线性无关；,则存在一组不全为零的实数,使得：,二阶充分条件,定理2:,对等式约束问题，若：,(1),与,是二阶连续,可微函数；,(2),与,使：,(3),且,且,均有,则,是等式约束问题的严格

11、局部极小点,不等式约束问题,定义1:,有效约束：,若(2)中的一个可行点,使得,某个不等式约束,变成等式，,即,则,称为关于,的有效约束,非有效约束：,若对,则,称为,关于,的非有效约束,有效集：,定义2:,锥：,的子集，,如果它关于正的数乘运算,是封闭的,如果锥也是凸集，则称为凸锥,凸锥关于加法和正的数乘运算是封闭的,定理3:,在(2)中，假设：,(1),为(2)的局部最优解且,(2),与,在,点可微；,(3),在,点连续；,则,与,交为空,例1：,确定：,在点,处的可行下降方向.,解：,设,一阶必要条件,定理4:,(Fritz-John一阶必要条件)(1948),设,为问题(2)的局部最优

12、解且,在,点可微，,则存在非零向量,使得：,例2：,验证是否满足Fritz-John条件：,验证,处Fritz-John条件是否成立？,解：,取,总有,成立,一阶必要条件,定理5:,(Kuhn-Tucker一阶必要条件)(1951),设,为问题(2)的局部最优解,在,点可微，,对于,的,线性无关，,则存在非零向量,使得：,例3：,验证是否满足Kuhn-Tucker条件：,验证,处kuhn-Tucker条件是否成立？,解：,对,所以,不是KT点,原因是,线性相关,一般约束问题,一阶必要条件,定理6:,(Kuhn-Tucker一阶必要条件),设,为问题(3)的局部最优解,在,点可微，,对于,的,线

13、性无关，,则存在非零向量,使得：,例4：,验证是否满足Kuhn-Tucker条件：,试验证最优点,为KT点,解：,令,所以,即：,所以：,是KT点,二阶必要条件,定理7:,设,是(3)的最优解且函数,与,是二阶连续,可微函数.,又设,约束规范条件在点,成立，,从而存在,使,KT条件成立,如果严格互补松弛条件在,成立，则：,对一切满足,的方向,均成立,二阶充分条件,定理8:,设,(3)的函数,与,是二阶连续,可微函数.,又设,约束规范条件在点,成立，,若存在,使,KT条件成立,如果严格互补松弛条件在,成立，,且对所有,满足,的非零向量,有：,则,是问题(3)的一个严格局部最优解, 1.4 最优化

14、方法 概述,迭代算法：选取一个初始可行点,由这个初始可行点出发，依次产生一个可行点列：,记为,使得,恰好是问题的一个最优解，,或者该点列,收敛到问题的一个最优解。,下降算法：在迭代算法中一般要求：,可行点列的产生,在,处求得一个方向,处求得一个方向,（可行下降方向）,在射线,上求一点：,使得,其中,称为步长。,下降方向,定义1.6,下降方向：,在点,处，,对于方向,若存在实数,使得任意的,有：,成立，,则称,为函数,在点,处,的一个下降方向。,当,具有连续的一阶偏导数，令,由Taylor公式：,当,时，有,所以（,充分小时）,是,在,处的一个,下降方向。,通常称满足：,的方向,为,在,处的下降方向。,可行方向（P17）,定义1.7,可行方向：,已知区域,对于向量,若存在实数,使得任意的,有：,则称,为,点处,关于区域,的可行方向。,下降方向关于区域,可行，则称为可行下降,方向。,最优化问题的算法的一般迭代格式,给定初始点,令,（）确定,处的可行下降方向,（）确定步长,使得：,（）令,（）若,满足某种终止准则，则停止；,否则令,转（）,收敛性,如果一个算法只有当初始点充分接近最优解时，产生的点列才收敛，则称该算法为具有局部收敛的算法。,如果对任意的初始点，由算法产生的点列都收敛，则称该算法为具有全局收敛的算法。,具有全局收敛性的算法