最优化方法刘第一章

《最优化方法刘第一章》由会员分享，可在线阅读，更多相关《最优化方法刘第一章（72页珍藏版）》请在装配图网上搜索。

1、最优化方法最优化方法刘丽华刘丽华第一章第一章基本概念基本概念 1.1 1.1 最优化问题最优化问题简介简介最优化是一门应用十分广泛的学科，它研究最优化是一门应用十分广泛的学科，它研究在有限种或无限种可行方案中挑选最优方案，构造在有限种或无限种可行方案中挑选最优方案，构造寻求最优解的计算方法。达到最优目标的方案，称寻求最优解的计算方法。达到最优目标的方案，称为为最优方案最优方案，搜索最优方案的方法，称为，搜索最优方案的方法，称为最优化方最优化方法法。这种方法的数学理论，称为。这种方法的数学理论，称为最优化理论最优化理论。实际上最优化方法已广泛应用于空间技术、实际上最优化方法已广泛应用于空间技术、

2、军事科学、电子工程、通讯工程、自动控制、系统军事科学、电子工程、通讯工程、自动控制、系统识别、资源分配、计算数学、经济管理等等领域。识别、资源分配、计算数学、经济管理等等领域。最优化方法包括的内容很广泛，如线性规划、最优化方法包括的内容很广泛，如线性规划、非线性规划、整数规划、动态规划、多目标规划、非线性规划、整数规划、动态规划、多目标规划、组合优化等等。本教程重点介绍组合优化等等。本教程重点介绍线性规划和非线性线性规划和非线性规划规划。最优化问题的数学模型一般形式为：最优化问题的数学模型一般形式为：（目标函数目标函数）（等式等式约束）约束）（不等式不等式约束）约束）其中其中相关定义（P7P8

3、）定义.1 可行解满足约束条(1.2)和(1.3)的x称为可行解，也称为可行点或容许点。定义.2 可行域全体可行解构成的集合称为可行域，也称为容许集，记为F,即：定义.3 整体最优解若：对于一切则称恒有为最优化问题的整体最优解。若：恒有则称为最优化 问题的严格整体最优解。定义.4 局部最优解若：存在的某邻域使得对于一切恒有则称为最优化问题的局部最优解。其中同样有：严格局部最优解。而局部最优解不一定是整体最优解。显然，整体最优解一定是局部最优解，注意：求解最优化问题，实际上是求可行域F上的整体最优解。但是，在一般情况下，整体最优解是很难求出的，往往只能求出局部最优解。定义.5 范数P9：在维向量

4、空间中，定义实函数使其满足以下三个条件：（）对任意有在当且仅当时（）对任意及实数有（）对任意有则称函数为上的向量范数。两类比较常见的范数：P-范数：其中最常用的是2-范数，即：范数：最优化问题的分类根据数学模型中有无约束函数分为有约束的最优化问题和无约束的最优化问题。根据目标函数和约束函数的函数类型分类：线性最优化问题、非线性最优化问题、二次规划、多目标规划、动态规划、整数规划、规划。1.2一、凸集和凸函一、凸集和凸函数数凸集定义1设集合若对于任意两点及实数都有：则称集合为凸集注：常见的凸集：空集，整个欧氏空间超平面：半空间：例1：证明超球为凸集证明：设为超球中的任意两点，则有：即点属于超球所

5、以超球为凸集凸集的性质（）有限个（可以改成无限）凸集的交集为凸集（）设是凸集，是一实数，则下面的集合是凸集：（）设是凸集，则的和集是凸集注：和集和并集有很大的区别，凸集的并集未必是凸集，而凸集的和集是凸集例：表示轴上的点表示轴上的点则表示两个轴的所有点，它不是凸集；而凸集推论：设是凸集，则也是凸集，其中是实数定义2:设实数则 称为 的凸组合 注：凸集中任意有限个点的凸组合仍然在该凸集中 极点定义1设为凸集，若中不存在两个相异的点及某一实数使得则称为的极点例：则上的点均为极点证：设若存在及使得则：不等式要取等号，必须且容易证明根据定义可知为极点凸函数P20-29定义4设函数定义在凸集定义在凸集上

6、，若对任意的及任意的都有：则称函数为凸集上的凸函数定义5 严格凸函数注：将上述定义中的不等式反向，可以得到凹函数的定义例1：设试证明在上是严格凸函数证明:设且都有：因此在上是严格凸函数例2：试证线性函数是证明:设上的凸函数则所以是凸函数类似可以证明是凹函数凸函数的几何性质对一元函数在几何上表示连接的线段表示在点处的函数值所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方凸函数的性质（）设（）设函数，是凸集上的凸函数，实数则也是上的凸函数是凸集上的凸实数则也是上的凸函数（）设是凸集上的凸函数，是实数，则水平集是凸集下面的图形给出了凸函数的等值线的图形，可以看出水平集是凸集凸函数的

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

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

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

10、1.3 最优性条件最优性条件约束最优性条件约束最优性条件等式约束问题一阶必要条件定理1:若(1)是等式约束问题的局部最优解；(2)与在的某邻域内连续可微；(3)线性无关；则存在一组不全为零的实数使得：二阶充分条件定理2:对等式约束问题，若：(1)与是二阶连续可微函数；(2)与使：(3)且且均有则是等式约束问题的严格局部极小点不等式约束问题定义1:有效约束：若(2)中的一个可行点使得某个不等式约束变成等式，即则称为关于 的有效约束非有效约束：若对则称为关于的非有效约束有效集：定义2:锥：的子集，如果它关于正的数乘运算是封闭的 如果锥也是凸集，则称为凸锥凸锥关于加法和正的数乘运算是封闭的定理3:在

11、(2)中，假设：(1)为(2)的局部最优解且(2)与在点可微；(3)在点连续；则与交为空例1：确定：在点处的可行下降方向.解：设一阶必要条件定理4:(Fritz-John一阶必要条件)(1948)设为问题(2)的局部最优解且在点可微，则存在非零向量使得：例2：验证是否满足Fritz-John条件：验证处Fritz-John条件是否成立？解：取总有成立一阶必要条件定理5:(Kuhn-Tucker一阶必要条件)(1951)设为问题(2)的局部最优解,在点可微，对于的线性无关，则存在非零向量使得：例3：验证是否满足Kuhn-Tucker条件：验证处kuhn-Tucker条件是否成立？解：对所以不是K

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

13、的一个严格局部最优解 1.4 1.4 最优化方法最优化方法概述概述迭代算法：选取一个初始可行点由这个初始可行点出发，依次产生一个可行点列：记为使得恰好是问题的一个最优解，或者该点列收敛到问题的一个最优解。下降算法：在迭代算法中一般要求：可行点列的产生在处求得一个方向处求得一个方向（可行下降方向）在射线上求一点：使得其中称为步长。下降方向定义1.6下降方向：在点处，对于方向若存在实数使得任意的有：成立，则称为函数在点处的一个下降方向。当具有连续的一阶偏导数，令由Taylor公式：当时，有所以（充分小时）是在处的一个下降方向。通常称满足：的方向为在处的下降方向。可行方向（P17）定义1.7可行方向

14、：已知区域对于向量若存在实数使得任意的有：则称为点处关于区域的可行方向。下降方向关于区域可行，则称为可行下降方向。最优化问题的算法的一般迭代格式给定初始点令（）确定处的可行下降方向（）确定步长使得：（）令（）若满足某种终止准则，则停止；否则令转（）收敛性如果一个算法只有当初始点充分接近最优解时，产生的点列才收敛，则称该算法为具有局部收敛的算法。如果对任意的初始点，由算法产生的点列都收敛，则称该算法为具有全局收敛的算法。具有全局收敛性的算法才有实用意义。但对算法的局部收敛性分析，在理论上是重要的，因为它是全局收敛性分析的基础。收敛速度定义1.8设序列收敛于而且：若则称序列为线性收敛的，称为收敛比；若则称序列为超线性收敛的。收敛速度定义1.9设序列收敛于若对则称序列为有：阶收敛的。特别当：时称为二阶收敛的。终止准则对于一种算法，应该有某种终止准则，当某次迭代满足终止准则时，就停止迭代。常用的终止准则有：（）或（）或（）其中是预先给定的。