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