最优化问题的数学模型ppt课件.ppt

《最优化问题的数学模型ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最优化问题的数学模型一般形式其中为连续函数，通常还要求连续可微.根据实际问题的不同要求，最优化模型有不同的形式，但经过适当的变换都可以转换成上述一般形式.决策变量目标函数约束函数最优化问题的分类最优化问题无约束最优化问题约束最优化问题等式约束最优化问题不等式约束最优化问题混合约束优化问题根据约束条件分类最优化问题的分类最优化问题连续最优化：决策变量取值连续离散最优化：决策变量取值离散光滑最优化：函数连续可微非光滑最优化：有一个非光滑线性规划非线性最优化根据决策变量的取值整数规划，资源配置，邮路问题生产安排等最优化问题无约束

2、最优化问题约束最优化问题线性规划二次规划二次罚函数线性搜索最速下降法，牛顿法，拟牛顿法，共轭方向法单纯形法对偶单纯形法有效约束集法可行方向法最小二乘法定义设集合若对于任意两点及实数都有：则称集合为凸集．换句话说，如果任意两点则连接x与y的直线段上的所有点都在D内。定义:设实数则称为的凸组合．定理：D是凸集的充分必要条件是D中任意有限个点的凸组合仍然在D中。例：证明超球为凸集．证明：设为超球中的任意两点，则有：即点属于超球所以超球为凸集．常见的凸集：空集，整个欧氏空间注：超平面：开半空间：闭半空间：由有限个闭半空间的交组成的

3、集合叫多面集，其中是非零向量，是数。多面集是一个闭凸集。是多面集吗？是多面集吗？yesyes凸集的性质(１)有限个凸集的交集为凸集．(２)设是凸集，是一实数，则是凸集.(３)设是凸集，则的和(差)集是凸集.注：和集和并集有很大的区别，凸集的并集未必是凸集，而凸集的和集是凸集．定义设为两非空凸集，若存在非零向量和实数使得：则称超平面分离了集合和如果则称集合H严格分离和定理设为非空闭凸集，则存在非零向量和实数使得：即存在超平面严格分离点与凸集注：点与闭凸集的分离定理。Dy.定理设是非空凸集，则存在非零向量使成立闭包:D的闭包是

4、所有包含D的闭凸集的交.(点与凸集的分离定理)定理设是的两个非空凸集，则存在超平面分离和即存在非零向量使得(两个凸集的分离定理)且投影定理设是非空闭凸集，但则：(１)存在唯一的点使得集合到点的距离最小，即：(２)是点到集合的最短距离点的充要条件为：DY...Farkas引理设为矩阵，则下述两组方程中有且仅有一组有解：其中Farkas引理在最优化理论研究中起重要作用Farkas引理的另一种形式设l.l’是两个非负整数，a0,ai(i=1,…,l)和bi(i=1,…,l’)是Rn中的向量，则线性方程组和不等式组无解当且仅当存在

5、实数使得凸函数定义设函数定义在凸集定义在凸集上，若对任意的及任意的都有：则称函数为凸集上的凸函数．定义严格凸函数注：将上述定义中的不等式反向，可以得到凹函数的定义．xyf(x)f(y)例：设试证明在上是严格凸函数．证明:设且都有：因此在上是严格凸函数．例：试证线性函数是证明:设上的凸函数．则所以是凸函数．类似可以证明是凹函数．例：二次函数是Rn上的严格凸函数当且仅当G是正定矩阵.证明：严格凸f(x)严格凸G正定.二次函数G不定f(x)既不是凸函数也不是凹函数G正定f(x)是严格凸函数G负正半定f(x)是凹函数G负定f(x)

6、是严格凹函数G正半定f(x)是凸函数性质(１)设(２)设函数，是凸集上的凸函数，实数则也是上的凸函数．是凸集上的凸则也是上的凸函数．(３)设是凸集上的凸函数，则则也是上的凸函数.(4）设是凸集上的凸函数，也是上的凸函数,其中凸规划定义可行域是凸集，目标函数是凸函数的最优化问题称为凸规划问题定理(1)局部最优解也是全局最优解.(2)如果目标函数是严格凸的，则是唯一的全局最优解.设是凸规划问题的一个局部最优解，则如果每一个约束函数都是凹函数，则可行域F是凸集.如果每一个约束函数都是凸函数，则可行域F是凸集.如果每一个约束函数即

7、是凸函数又是凹函数，则可行域F是凸集.凸函数的判定定理函数是上凸函数的充分必要条件是对任意的单变量函数是关于的凸函数.一阶条件定理设上的可微函数,则是上凸函数的充要条件是是严格凸函数的充要条件：是定义在非空凸集(1)（2）二阶条件定理设在开凸集内二阶可微，则(1)是内的凸函数的充要条件为，在内任一点处，的Hesse矩阵正半定,(2)如果的Hesse矩阵（二阶导数矩阵）在D上正定,则是D上的严格凸函数;反之，如果是D上的的严格凸函数,则在D上正半定.与凸函数关系密切的是水平集定理设是非空凸集,f是定义在D上的凸函数,是任一个

8、实数,则水平集是一个凸集.定理设f是非空凸集上的连续凸函数,则水平集是闭凸集.定理设f是非空凸集上二次连续可微,且存在常数使得则水平集是有界闭凸集.初始点的选取依赖于方法的收敛性能.一个算法称为收敛的，如果算法产生的序列满足一个算法如果对于任意给定的初始点都能够收敛，就说这个方法全局收敛或总体收敛.有些