第一讲预备知识精选文档.ppt
第一讲预备知识本讲稿第一页，共七十二页提提 纲纲1.课程介绍课程介绍2.课程安排课程安排3.预备知识预备知识 3.1 凸集与凸函数凸集与凸函数 3.2 梯度梯度 3.3正定矩阵正定矩阵,半正定矩阵半正定矩阵,Hesse矩阵矩阵 3.4 局部极小点局部极小点,全局极小点全局极小点 本讲稿第二页，共七十二页1.课程介绍课程介绍运筹学：Operational Research Operations Research European Journal of Operational Research Operations Research 本讲稿第三页，共七十二页运筹学分支数学规划数学规划-网络分析网络分析排队论排队论存储论存储论对策论对策论决策论决策论图论图论 搜索论搜索论 统筹论统筹论 l线性规划线性规划l非线性规划非线性规划l整数规划整数规划l目标规划目标规划l动态规划动态规划l随机规划随机规划l模糊规划模糊规划l几何规划几何规划l动态规划动态规划l组合优化组合优化本讲稿第四页，共七十二页运筹学应用1.市场销售市场销售 2.生产计划生产计划3.库存管理库存管理 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 最优性条件最优性条件 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中所有点的中所有点的凸凸组合组合本讲稿第十四页，共七十二页生成向量生成向量 任一向量都可表示任一向量都可表示内积内积向量夹角向量夹角 向量范数向量范数本讲稿第十五页，共七十二页矩阵范数矩阵范数本讲稿第十六页，共七十二页正定矩阵正定矩阵,半正定矩阵半正定矩阵负定矩阵负定矩阵,半负定矩阵半负定矩阵连续可微连续可微二次连续可微二次连续可微本讲稿第十七页，共七十二页梯度梯度列向量列向量 Hesse矩阵矩阵本讲稿第十八页，共七十二页Jacobi 矩阵矩阵本讲稿第十九页，共七十二页中值定理中值定理本讲稿第二十页，共七十二页Taylor展开式一阶Taylor展开式二阶Taylor展开式本讲稿第二十一页，共七十二页2.凸集与凸函数本讲稿第二十二页，共七十二页2.1 凸集凸集本讲稿第二十三页，共七十二页本讲稿第二十四页，共七十二页凸集的性质凸集的性质本讲稿第二十五页，共七十二页d为为S的方向的方向：S闭凸集，d为非零向量本讲稿第二十六页，共七十二页本讲稿第二十七页，共七十二页本讲稿第二十八页，共七十二页凸集的闭包与内部凸集的闭包与内部本讲稿第二十九页，共七十二页本讲稿第三十页，共七十二页凸集的支撑超平面凸集的支撑超平面本讲稿第三十一页，共七十二页凸集分离定理凸集分离定理超平面分离集合超平面分离集合S1,S2强分离必严格分离，严格分离必分离强分离必严格分离，严格分离必分离.本讲稿第三十二页，共七十二页本讲稿第三十三页，共七十二页凸多面体凸多面体本讲稿第三十四页，共七十二页本讲稿第三十五页，共七十二页凸函数基础凸函数基础本讲稿第三十六页，共七十二页本讲稿第三十七页，共七十二页本讲稿第三十八页，共七十二页本讲稿第三十九页，共七十二页凸函数的次梯度凸函数的次梯度本讲稿第四十页，共七十二页本讲稿第四十一页，共七十二页本讲稿第四十二页，共七十二页本讲稿第四十三页，共七十二页本讲稿第四十四页，共七十二页可微凸函数可微凸函数本讲稿第四十五页，共七十二页本讲稿第四十六页，共七十二页凸集分离定理凸集分离定理超平面分离集合超平面分离集合S1,S2强分离必严格分离，严格分离必分离强分离必严格分离，严格分离必分离.本讲稿第四十七页，共七十二页闭凸集的性质闭凸集的性质定理定理1.本讲稿第四十八页，共七十二页点与凸集的点与凸集的分离分离 定理定理2闭凸集与不属于它的点是可分离的闭凸集与不属于它的点是可分离的.本讲稿第四十九页，共七十二页两个非空凸集的分离定理本讲稿第五十页，共七十二页凸集定理的应用本讲稿第五十一页，共七十二页Gordan 定理本讲稿第五十二页，共七十二页2.2 凸函数本讲稿第五十三页，共七十二页2.21 凸函数基本性凸函数基本性质2.22 凸函数代数运算凸函数代数运算2.23 凸函数的凸函数的 Lipschitz 连续性性2.24 凸函数的可微性凸函数的可微性本讲稿第五十四页，共七十二页2.21 凸函数基本性质本讲稿第五十五页，共七十二页本讲稿第五十六页，共七十二页本讲稿第五十七页，共七十二页本讲稿第五十八页，共七十二页本讲稿第五十九页，共七十二页本讲稿第六十页，共七十二页本讲稿第六十一页，共七十二页利用上图概念，我们得到凸函数的下述利用上图概念，我们得到凸函数的下述Jensen不等式不等式本讲稿第六十二页，共七十二页本讲稿第六十三页，共七十二页本讲稿第六十四页，共七十二页2.22凸函数代数运算本讲稿第六十五页，共七十二页本讲稿第六十六页，共七十二页本讲稿第六十七页，共七十二页本讲稿第六十八页，共七十二页2.23 凸函数的Lipschitz连续性 本讲稿第六十九页，共七十二页2.24光滑凸函数的微分 本讲稿第七十页，共七十二页凸函数的判定本讲稿第七十一页，共七十二页二次函数的凸性判定很简单本讲稿第七十二页，共七十二页
