《高级运筹学》PPT课件.ppt

《《高级运筹学》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《高级运筹学》PPT课件.ppt（310页珍藏版）》请在三一办公上搜索。

1、高级运筹学,提 纲,1.课程介绍2.课程安排3.预备知识 3.1 凸集与凸函数 3.2 梯度 3.3正定矩阵,半正定矩阵,Hesse矩阵 3.4 局部极小点,全局极小点,1.课程介绍,运筹学：Operational Research Operations Research European Journal of Operational Research Operations Research,运筹学分支,数学规划-网络分析排队论存储论对策论决策论图论 搜索论 统筹论,线性规划非线性规划整数规划目标规划动态规划随机规划模糊规划几何规划动态规划组合优化,运筹学应用,1.市场销售 2.生产计划3.库

2、存管理 4.运输问题5.财政和会计 6.人事管理,7.设备维修、更新8.可靠性9.项目选择和评价10.工程的优化设计11.计算机和信息系统12.城市管理13.选址定位,2.课程安排,教材：最优化理论与算法(第2版)清华大学研究生公共课教材 陈宝林 编著,2005年10月,清华大学出版社,Nonlinear Programming:Theory and Algorithms by Mokhtar S.Bazaraa,Hanif D.Sherali,and C.M.Shetty-May 5,2006,理论与方法并重重应用,轻证明,基本内容,第0章 预备知识第1章 无约束极值问题 1.1 最优性条件

3、 1.2 一维搜索 1.3 最速下降法 1.4 牛顿法,第2章 约束极值问题 2.1 最优性条件 2.2 惩罚函数法第3章 案例,第0章 预备知识,1.数学概念内点-S中x点的某个领域包含在S中.开集-每个点都是内点.闭集-闭包是其自身.紧集-有界闭集.闭包 集合S中的内点与边界,记为 cl S,第0章 预备知识,向量及其运算加减、数乘向量线性独立仿射独立(Affine Independence),线性组合仿射组合凸组合,线性包 集合S中所有点的线性组合仿射包 集合S中所有点的仿射组合凸包 集合S中所有点的凸组合,生成向量 任一向量都可表示内积向量夹角 向量范数,矩阵范数,正定矩阵,半正定矩阵

4、负定矩阵,半负定矩阵连续可微二次连续可微,梯度列向量 Hesse矩阵,Jacobi 矩阵,中值定理,Taylor展开式,一阶Taylor展开式二阶Taylor展开式,2.凸集与凸函数,2.1 凸集,凸集的性质,d为S的方向：S闭凸集，d为非零向量,凸集的闭包与内部,凸集的支撑超平面,凸多面体,凸函数基础,凸函数的次梯度,可微凸函数,凸集分离定理,超平面分离集合S1,S2,强分离必严格分离，严格分离必分离.,闭凸集的性质定理1.,点与凸集的分离 定理2闭凸集与不属于它的点是可分离的.,两个非空凸集的分离定理,凸集定理的应用,Gordan 定理,2.2 凸函数,2.21 凸函数基本性质2.22 凸

5、函数代数运算2.23 凸函数的 Lipschitz 连续性2.24 凸函数的可微性,2.21 凸函数基本性质,2.22凸函数代数运算,2.23 凸函数的Lipschitz连续性,2.24光滑凸函数的微分,凸函数的判定,二次函数的凸性判定很简单,凸性的推广,凸函数拟凸函数可微凸函数伪凸函数伪凸函数拟凸函数,无约束问题的最优性条件,华国伟北京交通大学经管学院物流管理系,提纲,一、预备知识二、无约束问题的最优解,第三讲 求解无约束问题的牛顿法,华国伟北京交通大学经管学院物流管理系,提纲,一、牛顿法二、收敛速度,斐波那契法(分数法)黄金分割法(0.618法),1.2 牛顿法的二次收敛性,第四讲 求解无

6、约束问题的最速下降法,华国伟北京交通大学经管学院物流管理系,提纲,一、最速下降法二、全局收敛性三、二次函数下的收敛速度,3.二次函数下的收敛速度,6.凸函数线搜索的二分方法,二分法步骤,第五讲 约束优化问题的最优性条件,华国伟北京交通大学经管学院物流管理系,提纲,一、约束优化问题二、最优性必要条件 2.1 几何必要条件 2.2 代数必要条件三、最优性充分条件四、约束规范,一、约束优化问题,二、最优性必要条件,2.1 几何必要条件,最优值点没有可行下降方向,即下降方向必不可行,可行方向必不下降.,凸集分离定理,u,2.2 代数必要条件,KKT必要条件,三、最优性充分条件,凸规划,-凸,-凸,-线

7、性,伪凸-,拟凸-,线性-,四、约束规范,二阶最优性条件,2,约束优化问题KKT二阶必要条件,2,体现约束,无约束优化问题二阶必要条件,可行方向,无约束优化问题二阶充分条件,第六讲 约束优化问题的惩罚函数法和碰壁函数法,华国伟北京交通大学经管学院物流管理系,提纲,一、引言二、惩罚函数法 2.1 收敛性定理 2.2 KKT乘子 2.3 精确惩罚函数法 2.4 带不等式约束和等式约束的罚函数法,三、碰壁函数法3.1 碰壁函数法收敛性定理3.2 碰壁函数法的KKT乘子,1.引言,解从不可行到可行,解始终可行,2.罚函数法 Penalty Methods,惩罚函数,2.1 收敛性定理,2.2 KKT乘

8、子,2.3 精确惩罚函数法,2.4 带不等式约束和等式约束的罚函数法,三、碰壁函数法 Barrier Methods,3.1 碰壁函数法收敛性定理,3.2 碰壁函数法的KKT乘子,令,第七讲 约束优化的对偶理论,华国伟北京交通大学经管学院物流管理系,提纲,一、概述二、对偶的重要性三、对偶问题四、对偶问题的构建步骤五、对偶构建的例子六、原问题与对偶问题的几何解释,七、对偶问题的凹最大值问题八、弱对偶问题九、优化准则的鞍点十、凸问题的强对偶性十一、对偶性策略十二、离散问题中的拉格朗日对偶性十三、锥对偶性,1.概述,2.对偶的重要性,3.对偶问题,3.2 对偶问题的定义,复杂约束放到目标中,4.对偶问题的构建步骤,5.优化问题的对偶构建例子,5.1 线性问题的对偶性,5.2 二元整数问题的对偶性,5.3 对数障碍问题的对偶性,5.5 带有不同约束形式问题的注释,6.原问题与对偶问题的几何解释,7.对偶问题的凹最大问题,鞍点这词来自于不定二次型x2-y2的二维图形,像马鞍:x-轴方向往上曲,在y-轴方向往下曲.,11.2 把一个大问题对偶化成几个小问题,The game is over.,