《高级运筹学》PPT课件

高级运筹学,提纲,1.课程介绍2.课程安排3.预备知识3.1凸集与凸函数3.2梯度3.3正定矩阵,半正定矩阵,Hesse矩阵3.4局部极小点,全局极小点,1.课程介绍,运筹学：OperationalResearchOperationsResearchEuropeanJournalofOperationalResearchOperationsResearch,运筹学分支,数学规划-网络分析排队论存储论对策论决策论图论搜索论统筹论,线性规划非线性规划整数规划目标规划动态规划随机规划模糊规划几何规划动态规划组合优化,运筹学应用,1.市场销售2.生产计划3.库存管理4.运输问题5.财政和会计6.人事管理,7.设备维修、更新8.可靠性9.项目选择和评价10.工程的优化设计11.计算机和信息系统12.城市管理13.选址定位,2.课程安排,教材：最优化理论与算法(第2版)清华大学研究生公共课教材陈宝林编著,2005年10月,清华大学出版社,NonlinearProgramming:TheoryandAlgorithmsbyMokhtarS.Bazaraa,HanifD.Sherali,andC.M.Shetty-May5,2006,理论与方法并重重应用,轻证明,基本内容,第0章预备知识第1章无约束极值问题1.1最优性条件1.2一维搜索1.3最速下降法1.4牛顿法,第2章约束极值问题2.1最优性条件2.2惩罚函数法第3章案例,第0章预备知识,1.数学概念内点-S中x点的某个领域包含在S中.开集-每个点都是内点.闭集-闭包是其自身.紧集-有界闭集.闭包集合S中的内点与边界,记为clS,第0章预备知识,向量及其运算加减、数乘向量线性独立仿射独立(AffineIndependence),线性组合仿射组合凸组合,线性包集合S中所有点的线性组合仿射包集合S中所有点的仿射组合凸包集合S中所有点的凸组合,生成向量任一向量都可表示内积向量夹角向量范数,矩阵范数,正定矩阵,半正定矩阵负定矩阵,半负定矩阵连续可微二次连续可微,梯度列向量Hesse矩阵,Jacobi矩阵,中值定理,Taylor展开式,一阶Taylor展开式二阶Taylor展开式,2.凸集与凸函数,2.1凸集,凸集的性质,d为S的方向：S闭凸集，d为非零向量,凸集的闭包与内部,凸集的支撑超平面,凸多面体,凸函数基础,凸函数的次梯度,可微凸函数,凸集分离定理,超平面分离集合S1,S2,强分离必严格分离，严格分离必分离.,闭凸集的性质定理1.,点与凸集的分离定理2闭凸集与不属于它的点是可分离的.,两个非空凸集的分离定理,凸集定理的应用,Gordan定理,2.2凸函数,2.21凸函数基本性质2.22凸函数代数运算2.23凸函数的Lipschitz连续性2.24凸函数的可微性,2.21凸函数基本性质,2.22凸函数代数运算,2.23凸函数的Lipschitz连续性,2.24光滑凸函数的微分,凸函数的判定,二次函数的凸性判定很简单,凸性的推广,凸函数拟凸函数可微凸函数伪凸函数伪凸函数拟凸函数,无约束问题的最优性条件,华国伟北京交通大学经管学院物流管理系,提纲,一、预备知识二、无约束问题的最优解,第三讲求解无约束问题的牛顿法,华国伟北京交通大学经管学院物流管理系,提纲,一、牛顿法二、收敛速度,斐波那契法(分数法)黄金分割法(0.618法),1.2牛顿法的二次收敛性,第四讲求解无约束问题的最速下降法,华国伟北京交通大学经管学院物流管理系,提纲,一、最速下降法二、全局收敛性三、二次函数下的收敛速度,3.二次函数下的收敛速度,6.凸函数线搜索的二分方法,二分法步骤,第五讲约束优化问题的最优性条件,华国伟北京交通大学经管学院物流管理系,提纲,一、约束优化问题二、最优性必要条件2.1几何必要条件2.2代数必要条件三、最优性充分条件四、约束规范,一、约束优化问题,二、最优性必要条件,2.1几何必要条件,最优值点没有可行下降方向,即下降方向必不可行,可行方向必不下降.,凸集分离定理,u,2.2代数必要条件,KKT必要条件,三、最优性充分条件,凸规划,-凸,-凸,-线性,伪凸-,拟凸-,线性-,四、约束规范,二阶最优性条件,2,约束优化问题KKT二阶必要条件,2,体现约束,无约束优化问题二阶必要条件,可行方向,无约束优化问题二阶充分条件,第六讲约束优化问题的惩罚函数法和碰壁函数法,华国伟北京交通大学经管学院物流管理系,提纲,一、引言二、惩罚函数法2.1收敛性定理2.2KKT乘子2.3精确惩罚函数法2.4带不等式约束和等式约束的罚函数法,三、碰壁函数法3.1碰壁函数法收敛性定理3.2碰壁函数法的KKT乘子,1.引言,解从不可行到可行,解始终可行,2.罚函数法PenaltyMethods,惩罚函数,2.1收敛性定理,2.2KKT乘子,2.3精确惩罚函数法,2.4带不等式约束和等式约束的罚函数法,三、碰壁函数法BarrierMethods,3.1碰壁函数法收敛性定理,3.2碰壁函数法的KKT乘子,令,第七讲约束优化的对偶理论,华国伟北京交通大学经管学院物流管理系,提纲,一、概述二、对偶的重要性三、对偶问题四、对偶问题的构建步骤五、对偶构建的例子六、原问题与对偶问题的几何解释,七、对偶问题的凹最大值问题八、弱对偶问题九、优化准则的鞍点十、凸问题的强对偶性十一、对偶性策略十二、离散问题中的拉格朗日对偶性十三、锥对偶性,1.概述,2.对偶的重要性,3.对偶问题,3.2对偶问题的定义,复杂约束放到目标中,4.对偶问题的构建步骤,5.优化问题的对偶构建例子,5.1线性问题的对偶性,5.2二元整数问题的对偶性,5.3对数障碍问题的对偶性,5.5带