《最优化方法》课程教学大纲.docx

最优化方法课程教学大纲一、课程基本信息课程代码：102193课程名称：最优化方法英文名称：Optimization Methods课程类别：专业选修课 学 时：48 学分：3适用对象:大三学生考核方式：考试先修课程：高等代数，数学分析二、课程简介本课程介绍线性规划，非线性规划的优化算法，主要包括：单纯形法，最速下降法，牛顿法，共轭梯度法，拟牛顿法等。 This course will introduce optimization methods in linear programming, and nonlinear programming, including: simplex method, steepest descent method, Newtons method, Conjugate gradient method and quasi Newton method et al.三、课程性质与教学目的本课程是面向大三数学与应用数学，信息与计算科学专业学生开设的专业选修课。课程目的是介绍最优化的一些方法，作为人工智能的重要辅助课程，培养和增强学生解决实际数据分析问题中优化算法设计的能力。四、教学内容及要求第一章 最优化简介（一） 目的与要求介绍最优化的研究内容和框架（二） 教学内容 最优化的研究范畴1 主要内容最优化方法的发展历程，分类2 基本概念和知识点最优化方法方法的简史.3 问题与应用（能力要求）了解最优化方法的发展历程.（三） 思考与实践思考最优化方法所涉及的基础预备知识。（四） 教学方法与手段课堂讲授第二章 凸优化（一）目的与要求介绍凸优化的基本概念和研究内容（二）教学内容1.主要内容 凸集，凸包，凸函数，方向导数，上图2.基本概念和知识点 凸集，凸函数3.问题与应用（能力要求）凸函数的判别（三）思考与实践 上图的应用（四）教学方法与手段课堂讲授第三章 一维优化（1） 目的与要求 掌握一维优化问题的可微性，凸性判别条件。（二）教学内容第一节 可微性和凸性1.主要内容 可微性和凸性的判别2.基本概念和知识点 可微性的判别条件3.问题与应用（能力要求）掌握函数凸性的判别手段第二节 最优性条件1.主要内容 极小值，最小值，关键点，鞍点2.基本概念和知识点 极值，鞍点3.问题与应用（能力要求）掌握如何求解极小值，最小值，判断一个极值点是否是鞍点第三节 牛顿法1.主要内容 牛顿法的计算公式，优缺点2.基本概念和知识点 牛顿法的计算公式3.问题与应用（能力要求）掌握牛顿法的计算公式和优缺点。第四节 直线搜索方法1.主要内容 黄金分割法，Fibonacci法2.基本概念和知识点 黄金分割法的缩减比例，Fibonacci法与黄金分割法的异同3.问题与应用（能力要求）掌握黄金分割法和Fibonacci法的异同，以及迭代公式（三）思考与实践编程实现黄金分割法和Fibonacci法。（四）教学方法与手段课堂讲授第四章 线性规划（一）目的与要求理解和掌握线性规划的判别方法，最优性条件，单纯形法的原理和灵敏度分析（二）教学内容第一节 线性规划的框架和对偶性1.主要内容 线性规划模型的特点和对偶规划问题的计算2.基本概念和知识点 基本可行解，进基，离基变量3.问题与应用（能力要求）掌握线性规划基本可行解的求解以及进基，离基变量的选取第二节 最优性条件1.主要内容 KT条件2.基本概念和知识点 理解和掌握互补松弛条件3.问题与应用（能力要求）运用互补松弛条件来计算原问题和对偶问题的解之间的关系。第三节 单纯形法1.主要内容 单纯形法的计算原理2.基本概念和知识点 判别数的计算，进基变量和离基变量的选取3.问题与应用（能力要求）运用单纯形法求解线性规划问题第四节 灵敏度分析1.主要内容 改变目标函数，约束方程的系数，右端变量，增加新的变量以及新的约束如何求解新问题2.基本概念和知识点 增加约束，改变右端向量，改变技术系数等情形下，新的最优解和原最优解之间的关系3.问题与应用（能力要求）掌握在目标问题系数变化，约束改变等情形下，如何从已有的解出发得到新的最优可行解。（三）思考与实践掌握线性规划问题求解的单纯形法，会进行灵敏度分析。（四）教学方法与手段课堂讲授第五章 无约束优化（一）目的与要求介绍无约束优化问题的最优性条件，最速下降法，坐标下降法，牛顿法，直线搜索，拟牛顿法，共轭梯度法等（二）教学内容第一节 最优性条件1.主要内容 无约束规划问题的最优性条件2.基本概念和知识点 介绍无约束规划问题的极值条件，一阶判别条件，二阶判别条件，顺序主子式来判别Hesse矩阵是否正定，负定。3.问题与应用（能力要求）掌握如何运用最优性条件来判定是否是极大值还是极小值还是鞍点，会运用顺序主子式来判别Hesse矩阵是否正定，负定。第二节 最速下降法，坐标下降法，Nesterov加速梯度法1.主要内容 最速下降法，坐标下降法，Nesterov加速梯度法的原理2.基本概念和知识点 梯度方向，加速梯度3.问题与应用（能力要求）掌握最速下降法，坐标下降法，Nesterov加速梯度法的迭代公式第三节 牛顿法1.主要内容 牛顿法，阻尼牛顿法的计算公式2.基本概念和知识点 牛顿法，阻尼牛顿法的联系区别。3.问题与应用（能力要求） 掌握如何运用牛顿法来求解无约束规划问题第四节 直线搜索和拟牛顿法1.主要内容 直线搜索的含义，收敛速率，拟牛顿法的计算原理2.基本概念和知识点 介绍直线搜索的概念，线性收敛，二次收敛，超线性收敛，秩1校正，秩2校正。3.问题与应用（能力要求）掌握拟牛顿法的计算公式第五节 共轭梯度法1.主要内容 共轭梯度法的计算公式2.基本概念和知识点 介绍共轭的概念，共轭梯度发的迭代思想。3.问题与应用（能力要求）掌握共轭梯度法的计算公式和迭代思想。（三）思考与实践拟牛顿法，共轭梯度法的异同。（四）教学方法与手段课堂讲授第六章 约束规划（一）目的与要求介绍约束规划问题的最优性条件，迭代算法(可行方向法，Frank-Wolfe方法，罚函数法，梯度投影法)的原理（二）教学内容第一节 最优性条件1.主要内容 等式约束和不等式约束的最优性条件。2.基本概念和知识点 起作用集的概念，KKT条件。3.问题与应用（能力要求）掌握互补松弛条件的运用，以及KKT点的判定第二节 可行方向法1.主要内容 Zoutendijk可行方向法2.基本概念和知识点 了解Zoutendijk可行方向法所针对的问题类型，以及计算迭代思想3.问题与应用（能力要求）掌握Zoutendijk可行方向法的计算公式，会运用其求解实际问题。第三节 Frank-Wolfe算法1.主要内容 Frank-Wolfe算法2.基本概念和知识点 掌握Frank-Wolfe算法的思想和计算步骤3.问题与应用（能力要求）掌握Frank-Wolfe算法的适用问题，优缺点。第四节 罚函数法1.主要内容 内点法，外点法，拉格朗日乘子法2.基本概念和知识点 介绍内点法，外点法和拉格朗日乘子法的基本计算思想。3.问题与应用（能力要求）掌握针对不同的问题如何选择内点法，外点法以及拉格朗日乘子法。第五节 梯度投影法1.主要内容 梯度投影法2.基本概念和知识点 介绍梯度投影的基本计算思想。3.问题与应用（能力要求）掌握运用梯度投影法来求解约束规划问题第六节 起作用集法1.主要内容 起作用集法2.基本概念和知识点 介绍起作用集法的基本迭代思想和计算公式。3.问题与应用（能力要求）掌握起作用集法来求解约束规划问题（三）思考与实践 编程实现可行方向法，Frank-Wolfe算法，罚函数法，梯度投影法以及起作用集方法在求解约束规划问题中的应用（四）教学方法与手段课堂讲授五、各教学环节学时分配教学环节教学时数课程内容讲课习题课讨论课实验其他教学环节小计第一章40课堂随时讨论4第二章41课堂随时讨论5第