《最优化方法(双语)》课程教学大纲 一、课程基本信息 课程代码:102193 课程名称:最优化方法(双语) 英文名称:Optimization methods 课程类别:专业课 学 时:48 学分:3 适用对象:大二、大三学生 考核方式:考试 先修课程:概率论,数理统计,线性代数 二、课程简介 本课程介绍与优化问题相关的线性规划,非线性规划等各种算法,包括:单纯形 法,最速下降法,牛顿法,拟牛顿法,共轭梯度法,以及线性规划的约束条件等内容。 This course will introduce linear programming methods,nonlinear programming methods,including:simplex method,steepest descent method,Newton's method,quasi Newton method,conjugate Gradient method etc.,which are highly related with optimization problems in practice.Theoretical analysis about optimization conditions will also be investigated in this course. 三、课程性质与教学目的 本课程是面向大二应用统计专业学生,大三数学与应用数学专业开设的专业限修 课,可作为其他专业学生的选修课。课程目的是介绍与优化问题密切相关的各种优化 算法,培养和增强学生解决实际数据分析问题的能力。 课程思政总体思路:最优化方法如今广泛应用于人工智能,运筹,物流,国防等 领域。英国1947年最早将最优化方法应用于战争中,举握了主动权。现在世界局势 纷繁复杂,如果我们能够利用最新的最优化方法,这将有助于我国在人工智能,国防 等领域抢占先机,争夺话语权。 四、教学内容及要求 第一章最优化问题分类 (一)目的与要求 1.介绍数学专业英语,不同类型的决策问题,本书的记号,最优化的问 题分类和模型,基本框架及相关基础知识 2.了解本书所要介绍的内容以及数据集
1 《最优化方法(双语)》课程教学大纲 一、课程基本信息 课程代码:102193 课程名称: 最优化方法(双语) 英文名称:Optimization methods 课程类别:专业课 学 时:48 学 分:3 适用对象: 大二、大三学生 考核方式:考试 先修课程:概率论,数理统计,线性代数 二、课程简介 本课程介绍与优化问题相关的线性规划,非线性规划等各种算法,包括:单纯形 法,最速下降法,牛顿法,拟牛顿法,共轭梯度法,以及线性规划的约束条件等内容。 This course will introduce linear programming methods, nonlinear programming methods, including: simplex method, steepest descent method,Newton’s method, quasi Newton method,conjugate Gradient method etc., which are highly related with optimization problems in practice. Theoretical analysis about optimization conditions will also be investigated in this course. 三、课程性质与教学目的 本课程是面向大二应用统计专业学生,大三数学与应用数学专业开设的专业限修 课,可作为其他专业学生的选修课。课程目的是介绍与优化问题密切相关的各种优化 算法,培养和增强学生解决实际数据分析问题的能力。 课程思政总体思路:最优化方法如今广泛应用于人工智能,运筹,物流,国防等 领域。英国 1947 年最早将最优化方法应用于战争中,掌握了主动权。现在世界局势 纷繁复杂,如果我们能够利用最新的最优化方法,这将有助于我国在人工智能,国防 等领域抢占先机,争夺话语权。 四、教学内容及要求 第一章 最优化问题分类 (一)目的与要求 1.介绍数学专业英语,不同类型的决策问题,本书的记号,最优化的问 题分类和模型,基本框架及相关基础知识 2.了解本书所要介绍的内容以及数据集
(二)教学内容 第一节数学专业英语 1.主要内容 数学专业英语的表达方式 2.基本概念和知识点 数学专业英语,最优化问题分类 3.问题与应用(能力要求) 了解数学专业英语的表达方式,优化问题分类 第二节本书内容安排 1.主要内容 介绍数学专业英语,最优化问顿分类 2.基本概念和知识点 不同分支数学的英文表达方式,优化问题的分类 3.问题与应用(能力要求) 对实践问题能够进行建模分类。 (三)思考与实践 思考最优化方法所涉及的基础预备知识。 (四)教学方法与手段 课堂讲授 第二章凸优化 (一)目的与要求 1.介绍凸优化的相关概念,凸集,闭集的定义,以及上图,方向导数等 概念 2.掌握凸集凸函数的判别方式,上图的使用方法以及计算方向导数的方 (二)教学内容 第一节最优化发展简史 1.主要内容 最优化的发展历程 2.基本概念和知识点 80年代以前的发展历程和80年代以后的发展历程 3.问题与应用(能力要求) 掌握最优化的发展历程 第二节凸集,闭集,闭包 1.主要内容 2
2 (二)教学内容 第一节 数学专业英语 1.主要内容 数学专业英语的表达方式 2.基本概念和知识点 数学专业英语,最优化问题分类 3.问题与应用(能力要求) 了解数学专业英语的表达方式,优化问题分类 第二节 本书内容安排 1.主要内容 介绍数学专业英语,最优化问题分类 2.基本概念和知识点 不同分支数学的英文表达方式,优化问题的分类 3.问题与应用(能力要求) 对实践问题能够进行建模分类。 (三)思考与实践 思考最优化方法所涉及的基础预备知识。 (四)教学方法与手段 课堂讲授 第二章 凸优化 (一)目的与要求 1. 介绍凸优化的相关概念,凸集,闭集的定义,以及上图,方向导数等 概念 2. 掌握凸集凸函数的判别方式,上图的使用方法以及计算方向导数的方 法 (二)教学内容 第一节 最优化发展简史 1.主要内容 最优化的发展历程 2.基本概念和知识点 80 年代以前的发展历程和 80 年代以后的发展历程 3.问题与应用(能力要求) 掌握最优化的发展历程 第二节 凸集,闭集,闭包 1.主要内容
凸集,凸函数的定义及判别方法,闭包的含义 2.基本概念和知识点 凸集,凸函数,闭包 3.问题与应用(能力要求) 掌握凸集、凸函数的判别方法 第三节上图,方向导数 1.主要内容 上图的含义和方向导数的定义,计算方法 2.基本概今和知识点 上图,方向导数 3.问题与应用(能力要求) 会构建上图,计算方向导数。 (三)思考与实践 上图与凸函数的关系,方向导数与导数的关系 (四)教学方法与手段 课堂讲授 第三章一维优化问题 (一)目的与要求 掌握可微,凸性 一维优化问题的最优性条件,牛顿法,搜索方法等优化 方法 (二)教学内容 第一节可微与凸性 1.主要内容 凸函数的一阶二阶判别条件,仿射包,仿射集的概念。 2.基本概念和知识点 凸函数的判别条件,仿射包 3.问题与应用(能力要求) 掌握凸函数一阶二阶判别条件 第二节最优性条件 1.主要内容 局部极值点,全局极值点,驻点,关键点,鞍点 2.本概今和知识占 极值点,驻点,鞍点 3.问题与应用(能力要求) 掌握局部极值点和全局极值点的判别方法,会判定鞍点
3 凸集,凸函数的定义及判别方法,闭包的含义 2.基本概念和知识点 凸集,凸函数,闭包 3.问题与应用(能力要求) 掌握凸集、凸函数的判别方法 第三节 上图,方向导数 1.主要内容 上图的含义和方向导数的定义,计算方法 2.基本概念和知识点 上图,方向导数 3.问题与应用(能力要求) 会构建上图,计算方向导数。 (三)思考与实践 上图与凸函数的关系,方向导数与导数的关系 (四)教学方法与手段 课堂讲授 第三章 一维优化问题 (一)目的与要求 掌握可微,凸性,一维优化问题的最优性条件,牛顿法,搜索方法等优化 方法 (二)教学内容 第一节 可微与凸性 1.主要内容 凸函数的一阶二阶判别条件,仿射包,仿射集的概念。 2.基本概念和知识点 凸函数的判别条件,仿射包。 3.问题与应用(能力要求) 掌握凸函数一阶二阶判别条件 第二节 最优性条件 1.主要内容 局部极值点,全局极值点,驻点,关键点,鞍点 2.基本概念和知识点 极值点,驻点,鞍点 3.问题与应用(能力要求) 掌握局部极值点和全局极值点的判别方法,会判定鞍点
第三节牛顿法 1.主要内容 牛顿法的原理和计算步骤 2.基本概念和知识点 牛顿法的一阶迭代公式和二阶迭代公式 3.问题与应用(能力要求) 掌握牛顿法的计算步骤,优缺点。 第四节搜索方法 1.主要内容 搜索问题模型,单峰函数,黄金分割法,Fibonacci法,抛物线内插 2.基本概念和知识点 黄金分割法,Fibonacci法 3.问题与应用(能力要求) 掌握黄金分割法,Fibonacci法的计算步骤和异同。 (三)思考与实践 思考黄金分割法,Fibonacci法的先决条件和收敛速率。 (四)教学方法与手段 课堂讲授 第四章线性规划 (一)目的与要求 理解和掌握原问题和对偶问题的关系,掌握常见的单纯性方法:两阶段法, 大M法,线性规划的最优性条件,会进行灵敏度分析 (二)教学内容 第一节原问题与对偶问题 1.主要内容 介绍原问题和对偶问题两者之间的关系,原问题和对偶问题的对应关系 2.基本概念和知识点 原问题,对偶问题 3.问题与应用(能力要求) 能够写出原问题的对偶问题,掌握对偶问题的约束条件与原问题的相应 约束之间的关系。 第二节单纯形法 1.主要内容 介绍松弛变量和人工变量的作用,介绍解决线性规划问题的两阶段法, 4
4 第三节 牛顿法 1.主要内容 牛顿法的原理和计算步骤 2.基本概念和知识点 牛顿法的一阶迭代公式和二阶迭代公式 3.问题与应用(能力要求) 掌握牛顿法的计算步骤,优缺点。 第四节 搜索方法 1.主要内容 搜索问题模型,单峰函数,黄金分割法,Fibonacci 法,抛物线内插 法 2.基本概念和知识点 黄金分割法,Fibonacci 法 3.问题与应用(能力要求) 掌握黄金分割法,Fibonacci 法的计算步骤和异同。 (三)思考与实践 思考黄金分割法,Fibonacci 法的先决条件和收敛速率。 (四)教学方法与手段 课堂讲授 第四章 线性规划 (一)目的与要求 理解和掌握原问题和对偶问题的关系,掌握常见的单纯性方法:两阶段法, 大 M 法,线性规划的最优性条件,会进行灵敏度分析 (二)教学内容 第一节 原问题与对偶问题 1.主要内容 介绍原问题和对偶问题两者之间的关系,原问题和对偶问题的对应关系 2.基本概念和知识点 原问题,对偶问题 3.问题与应用(能力要求) 能够写出原问题的对偶问题,掌握对偶问题的约束条件与原问题的相应 约束之间的关系。 第二节 单纯形法 1.主要内容 介绍松弛变量和人工变量的作用,介绍解决线性规划问题的两阶段法
大M法 2.基本概念和知识点 进基变量,离基变量,两阶段法,大M法,人工变量,松弛变量 3.问题与应用(能力要求) 明白单纯形法的求解思路,掌握线性规划问题的求解方法:两阶段法, 大M法,会通过引入松弛变量和人工变量来转化原问题,并采用相应的方 法求解 第三节最优性条件 1.主要内容 KKT条件,互补松弛条件 2.基本概念和知识点 KKT点 3.问题与应用(能力要求) 掌握如何运用互补松弛条件,会判定驻点是否是KKT点 第四节灵敏度分析 1.主要内容 灵敏度分析涉及的五大领域 2.基本概念和知识点 技术系数 3.问题与应用(能力要求) 当改变系数矩阵A,右端向量b,目标函数系数c,增加额外约束,增 加新的变量时,能够通过原优化解来求解新问题的解。 (三)思考与实践 思考进基变量和离基变量对应的几何意义,KT条件,互补松弛条件。 (四)教学方法与手段 课堂讲授 第五章无约束优化问题 (一)目的与要求 介绍无约束优化问题的最优性条件,最速下降法,牛顿法,阻尼牛顿法, 直线搜索,拟牛顿法,共轭梯度法,最小二乘法等方法 (二)教学内容 第一节最优性条件 1.主要内容 极值点,最值点的判别方法 2.基本概念和知识点
5 大 M 法 2.基本概念和知识点 进基变量,离基变量,两阶段法,大 M 法,人工变量,松弛变量 3.问题与应用(能力要求) 明白单纯形法的求解思路,掌握线性规划问题的求解方法:两阶段法, 大 M 法,会通过引入松弛变量和人工变量来转化原问题,并采用相应的方 法求解。 第三节 最优性条件 1.主要内容 KKT 条件,互补松弛条件 2.基本概念和知识点 KKT 点 3.问题与应用(能力要求) 掌握如何运用互补松弛条件,会判定驻点是否是 KKT 点 第四节 灵敏度分析 1.主要内容 灵敏度分析涉及的五大领域 2.基本概念和知识点 技术系数 3.问题与应用(能力要求) 当改变系数矩阵 A,右端向量 b,目标函数系数 c,增加额外约束,增 加新的变量时,能够通过原优化解来求解新问题的解。 (三)思考与实践 思考进基变量和离基变量对应的几何意义,KKT 条件,互补松弛条件。 (四)教学方法与手段 课堂讲授 第五章 无约束优化问题 (一)目的与要求 介绍无约束优化问题的最优性条件,最速下降法,牛顿法,阻尼牛顿法, 直线搜索,拟牛顿法,共轭梯度法,最小二乘法等方法 (二)教学内容 第一节 最优性条件 1.主要内容 极值点,最值点的判别方法 2.基本概念和知识点
方向导数,矩阵的正定、负定、不定,希尔维斯特准则 3.问题与应用(能力要求) 掌握无约束优化问题的极值求解方法,会通过二阶矩阵来判定所求的驻 点是否是极值点 第二节最速下降法 1.主要内容 介绍最速下降法的计算法,锯齿现象 2.基本概念和知识点 最速下降方向,锯齿现象 3.问题与应用(能力要求) 掌握最速下降法的计算方法,优缺点,锯齿现象的产生原因。 第三节牛顿法 1.主要内容 介绍收敛速率的概念,牛顿法和阻尼牛顿法的迭代思想 2.基本概念和知识点 收敛速率,牛顿方向,阻尼牛顿法 3.问题与应用(能力要求) 掌握线性收敛,二次收敛,超线性收敛的区别,掌握牛顿法,阻尼牛顿 法的计算方法,优缺点。 第四节直线搜索和拟牛顿法 1.主要内容 介绍直线搜索的两大关键因素,介绍Armijo直线搜索,阻尼牛顿法的 迭代思想 2.基本概念和知识点 直线搜索,Armijo直线搜索,阻尼牛顿法,DFP算法,BFGS算法,拟牛 顿条件 3.问题与应用(能力要求) 掌握Armi jo直线搜索的策略,掌握DFP算法,BFGS算法的计算方法 第五节共轭梯度法 1.主要内容 介绍共轭梯度法的原理,FR方法,PR方法的迭代公式 2.基本概念和知识点 共轭方向,FR方法,PR方法 3.问颗与应用(能力要求) 掌握FR方法,PR方法的计算步骤,了解共轭梯度法的优缺点 6
6 方向导数,矩阵的正定、负定、不定,希尔维斯特准则 3.问题与应用(能力要求) 掌握无约束优化问题的极值求解方法,会通过二阶矩阵来判定所求的驻 点是否是极值点 第二节 最速下降法 1.主要内容 介绍最速下降法的计算法,锯齿现象 2.基本概念和知识点 最速下降方向,锯齿现象 3.问题与应用(能力要求) 掌握最速下降法的计算方法,优缺点,锯齿现象的产生原因。 第三节 牛顿法 1.主要内容 介绍收敛速率的概念,牛顿法和阻尼牛顿法的迭代思想 2.基本概念和知识点 收敛速率,牛顿方向,阻尼牛顿法 3.问题与应用(能力要求) 掌握线性收敛,二次收敛,超线性收敛的区别,掌握牛顿法,阻尼牛顿 法的计算方法,优缺点。 第四节 直线搜索和拟牛顿法 1.主要内容 介绍直线搜索的两大关键因素,介绍 Armijo 直线搜索,阻尼牛顿法的 迭代思想 2.基本概念和知识点 直线搜索,Armijo 直线搜索,阻尼牛顿法,DFP 算法,BFGS 算法,拟牛 顿条件 3.问题与应用(能力要求) 掌握 Armijo 直线搜索的策略,掌握 DFP 算法,BFGS 算法的计算方法 第五节 共轭梯度法 1.主要内容 介绍共轭梯度法的原理,FR 方法,PR 方法的迭代公式 2.基本概念和知识点 共轭方向,FR 方法,PR 方法 3.问题与应用(能力要求) 掌握 FR 方法,PR 方法的计算步骤,了解共轭梯度法的优缺点
第六节最小二乘法 1.主要内容 介绍最小二乘法的原理和计算思路,优缺点 2.基本概念和知识点 最小二乘,线性回归 3.问题与应用(能力要求) 掌握最小二乘法的计算方法 (三)思考与实践 思考无约束优化问题常见迭代方法:最速下降法,牛顿法,共轭梯度法的 优缺点。 (四)教学方法与手段 课堂讲授 第六章约束规划 (一)目的与要求 介绍约束规划问题的最优性条件,可行方向法,罚函数法,梯度投影法, Frank--Wolf方法,起作用集方法。 (二)教学内容 第一节最优性条件 1.主要内容 介绍线性约束和非线性约束的KT条件,LICQ 2.基本概念和知识点 一阶条件,二阶条件,LICQ 3.问题与应用(能力要求) 掌握KT点的求法 第二节可行方向法 1.主要内容 介绍可行方向,线性,非线性情形的Zoutendijk迭代方法 2.基本概念和知识点 可行方向,Zoutendijk方法 3.问题与应用(能力要求) 掌握Zoutendijk方法的计算步骤 第三节罚函数法 1.主要内容 介绍内点法,外点法,乘子法 2.基本概念和知识点
7 第六节 最小二乘法 1.主要内容 介绍最小二乘法的原理和计算思路,优缺点 2.基本概念和知识点 最小二乘,线性回归 3.问题与应用(能力要求) 掌握最小二乘法的计算方法 (三)思考与实践 思考无约束优化问题常见迭代方法:最速下降法,牛顿法,共轭梯度法的 优缺点。 (四)教学方法与手段 课堂讲授 第六章 约束规划 (一)目的与要求 介绍约束规划问题的最优性条件,可行方向法,罚函数法,梯度投影法, Frank-Wolf 方法,起作用集方法。 (二)教学内容 第一节 最优性条件 1.主要内容 介绍线性约束和非线性约束的 KT 条件,LICQ 2.基本概念和知识点 一阶条件,二阶条件,LICQ。 3.问题与应用(能力要求) 掌握 KT 点的求法 第二节 可行方向法 1.主要内容 介绍可行方向,线性,非线性情形的 Zoutendijk 迭代方法 2.基本概念和知识点 可行方向,Zoutendijk 方法 3.问题与应用(能力要求) 掌握 Zoutendijk 方法的计算步骤 第三节 罚函数法 1.主要内容 介绍内点法,外点法,乘子法 2.基本概念和知识点
内点法,外点法,乘子法 3.问题与应用(能力要求) 掌握内点法,外点法,乘子法的计算步骤,明白三种罚函数的适用范围 第四节梯度投影法 1.主要内容 介绍投影矩阵,梯度投影法的原理和计算步骤 2.基本概念和知识点 投影矩阵,梯度投影法 3.问题与应用(能力要求) 掌握梯度投影法的计算方法,适用领域 第五节Frank--Wolf方法 1.主要内容 介绍Frank-Wolfe方法的计算步骤,优缺点,适用范围 2.基本概念和知识点 Frank-Wolfe方法 3.问题与应用(能力要求) 掌握Frank--olfe的计算方法,迭代步骤 (三)思考与实践 思考约束规划问题的各种迭代方法:可行方向法,罚函数法,梯度投影法 Frank--Wolfe方法的区别和原理。 (四)教学方法与手段 课堂进授 五 各教学环节学时分配 教学环节 必 习 其他教 小 教学时数 题 实验 学环节 课程内容 第一章 2/1周 0 课堂随 时讨论 2/1周 0 课堂随 第二章 时讨论 第三章 9/3周 0 1米里过 时讨论 9/3周 0 课堂随 第四章 时讨论 8
8 内点法,外点法,乘子法 3.问题与应用(能力要求) 掌握内点法,外点法,乘子法的计算步骤,明白三种罚函数的适用范围 第四节 梯度投影法 1.主要内容 介绍投影矩阵,梯度投影法的原理和计算步骤 2.基本概念和知识点 投影矩阵,梯度投影法 3.问题与应用(能力要求) 掌握梯度投影法的计算方法,适用领域 第五节 Frank-Wolf 方法 1.主要内容 介绍 Frank-Wolfe 方法的计算步骤,优缺点,适用范围 2.基本概念和知识点 Frank-Wolfe 方法 3.问题与应用(能力要求) 掌握 Frank-Wolfe 的计算方法,迭代步骤 (三)思考与实践 思考约束规划问题的各种迭代方法:可行方向法,罚函数法,梯度投影法, Frank-Wolfe 方法的区别和原理。 (四)教学方法与手段 课堂讲授 五、各教学环节学时分配 教学环节 教学时数 课程内容 讲 课 习 题 课 讨 论 课 实验 其他教 学环节 小 计 第一章 2/1 周 0 课堂随 时讨论 第二章 2/1 周 0 课堂随 时讨论 第三章 9/3 周 0 课堂随 时讨论 第四章 9/3 周 0 课堂随 时讨论
12/4周 0 第五章 课堂随 时讨论 第六章 144周 0 课堂随 时讨论 合计 48/16周 六、推荐教材和教学参考资源 1陈宝林,最优化理论与算法(第二板).清华大学出版社,2005. 2.Mokhtar S.Bazaraa (Author),Hanif D.Sherali(Author),C.M.Shetty(Author),Nonlinear Programming:Theory and Algorithms,John Wiley&Sons Ine.3rd edition,2006. 3.杨庆之,最优化方法,科学出版社,2020 七、其他说明 大纲修订人:蔡佳 修订日期:2020年12月30日 大纲审定人: 审定日期:
9 第五章 12/4 周 0 课堂随 时讨论 第六章 14/4 周 0 课堂随 时讨论 合计 48/16 周 六、推荐教材和教学参考资源 1.陈宝林,最优化理论与算法 (第二版). 清华大学出版社,2005. 2.Mokhtar S. Bazaraa (Author), Hanif D. Sherali (Author), C. M. Shetty (Author), Nonlinear Programming: Theory and Algorithms, John Wiley & Sons Inc; 3rd edition, 2006. 3.杨庆之,最优化方法, 科学出版社, 2020. 七、其他说明 大纲修订人: 蔡佳 修订日期:2020 年 12 月 30 日 大纲审定人: 审定日期: