高级运筹学

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