《最优化方法》教学大纲

《最优化方法》教学大纲《最优化方法》是信息与计算科学专业高等教育的重要专业选修课程。最优化方法是近几十年发展和形成的一门新兴的应用学科，它应用数学、计算机科学以及其它科学的新成就研究各种系统和实际问题的优化设计，控制和管理的途径及策略，为决策者和管理者提供科学决策的理论依据和实际操作手段与方法，是集理论性与应用性为一体的学科，它在生产管理和工程技术等许多领域中有广泛的应用背景与前景。设置本课程的目的是：通过对该课程的学习，培养学生运用数学工具解决实际问题的能力。掌握最优化的基本理论，了解求解各类最优化问题的不同算法的优缺点，了解常用算法的收敛性理论。培养学生具有比较熟练的数值计算能力和综合运用所学知识解决问题的能力，能熟练运用所学算法和Matlab工具箱求解最优化问题，为学生运用所学知识解决有关实际最优化问题奠定一定的理论基础和计算技能。同时，通过结合课程的进展，介绍学科发展前沿研究动态，开阔学生眼界，启迪他们的思维，使学生了解该学科国内外有关最新研究成果。加深他们对最优化理论和算法的理解和认识。使之有利于提高学生的科学素质和能力。并为从事最优化理论与算法研究或最优化方法解决实际问题打下坚实的基础。学习本课程的要求是：牢固地掌握最优化的基本理论，常用算法的构造途径，并能在计算机上实现。通过各教学环节，本课程应达到下列要求：理解凸集、凸函数等基本概念，了解本学科的研究内容、重要进展及发展趋势。掌握线性规划的基本性质、单纯形法、对偶理论等线性规划的基本理论和方法。理解有关算法收敛性的理论。掌握非线性最优解所应满足的必要条件和充分条件；掌握常用的一维搜索算法。掌握常用的非线性最优化问题的解析解法和直接解法，如最速下降法、共轭梯度法、牛顿法、最小二乘法、掌握可行方向法、罚函数法。了解进化计算的思想与原理，掌握遗传算法的方法和步骤，了解遗传算法的收敛性质。先修课程要求：数学分析，高等代数，数值分析，Matlab对象编程本课程计划72学时，3学分。选用教材：孙文瑜，

徐成贤，朱德通编，最优化方法，高等教育出版社，2004年07月。教学手段：多媒体讲授为主，实验演示、习题课为辅考核方法：考试教学进程安排表周次学时数教

学

主

要

内

容教学方法备注14最优化问题简介，凸集和凸函数讲课

24最优化条件，最优化方法概述，Matlab最优化工具箱简介讲课，实验演示

34线性规划的基本概念与性质讲课

44线性规划的单纯形法讲课

54线性规划的对偶与对偶单纯形法讲课

64线性规划的内点算法，例题与习题讲课、习题、实验演示

74线性搜索，0．618法和Fibonacci法，逐次插值逼近法，精确线性搜索的收敛性讲课

84不精确线性搜索方法，信赖域方法的思想、算法框架和收敛性，解信赖域子问题讲课

94线性搜索与信赖域方法习题，最速下降法讲课、习题、实验演示

104Newton法、共轭梯度法讲课

114拟Newton条件、拟Newton法，习题讲课，实验演示

124线性最小二乘问题的解法，非线性最小二乘问题的Gauss-Newton法讲课

134最小二乘问题的信赖域方法，对Gauss-Newton矩阵的拟Newton修正，习题讲课，实验演示

144二次规划，等式约束二次规划讲课

154凸二次规划的有效集方法，约束最优化问题与最优性条件讲课

164约束优化的罚函数法，内点障碍罚函数法，讲课

174序列二次规划法、遗传算法的概念、流程与实现，讲课

184模式定理，复习讲课，实验演示

第一章

基本概念

一、学习目的通过本章的学习，

了解最优化问题的一些来源，理解建立合适的数学模型的重要性。理解最优化方法的一些常见的名词术语，了解优化模型的一些常见分类。掌握最优解存在的一阶条件与二阶条件，最优化方法的一般结构。初步了解MATLAB的最优化工具箱。本章计划8学时。

二、课程内容本章主要介绍同最优化方法和技术有关的基本概念和基本的理论，共分5节．§1.1

最优化问题简介理解最优化问题一般形式的数学模型，了解这种一般形式的模型同各种具体问题模型之间的关系和相互转换；了解线性规划、二次规划、无约束最优化、等式约束最优化和不等式约束最优化问题等几种主要的最优化问题的标准形式，熟练掌握最优化问题的一些基本定义,如可行点、可行域、起作用约束、局部最优解、整体最优解等，以及它们之间的关系。§1.2

凸集和凸函数掌握凸集的定义，凸集同最优化直接相关的性质和特性，重点为在最优化理论中起重要作用的凸集分离定理。熟练掌握一个函数是凸函数的一阶充分必要条什，二阶充分和必要条件，了解目标函数为凸函数，可行域为凸集的凸规划问题，了解凸规划问题的任何最优解必为全局最优解的证明，掌握可行域是凸集的条件和要求。§1.3

最优性条件理解可行方向、下降方向的定义，熟练掌握最优化问题最优解的一阶必要条件，又称KKT条件；掌握在假定所有函数二阶连续可微的条件下给出一般最优化问题最优解的二阶必要条件和二阶充分条件．§1.4

最优化方法概述了解一般最优化方法的基本特征和要求，掌握一般方法的迭代格式、评价一个点好坏约准则和方法、终止迭代的准则，了解衡量一个方法性能的收敛性和收敛速度。§1.5

Matlab最优化工具箱简介了解Matlab最优化工具箱的基本特点和使用方法。三、重点、难点提示和教学手段（一）重点、难点1.

最优化问题一般形式的数学模型以及相关基本概念；2.凸集分离定理，函数为凸函数的一阶与二阶条件;3.最优解存在的一阶与二阶条件;4.最优化方法的一般结构。（二）教学手段课堂讲授、课堂演示和习题课相结合四、思考与练习（注：具体形式由教师可自行调整。）第二章

线性规划一、学习目的通过本章的学习，要求学生理解线性规划模型的特征、基本概念及基本理论，理解单纯形方法的基本思想,熟练掌握单纯形方法，并能用于解决实际问题；掌握对偶理论及对偶单纯形法，并会进行灵敏度分析；理解线性规划的内点算法。本章计划16学时。二、课程内容本章主要介绍在现实生活．科学管理和科学实验中最常见、最有用的最优化技术和方法——线性规划，分四节分别介绍线性规划的基本性质、以及求解线性规划的常用方法：单纯形法、对偶单纯形法和内点算法。§2.1

基本性质掌握线性规划的标准形式，了解它同各种不同形式的线性规划问题之间的关系的相互转换,

熟练掌握线性规则问题的基本性质，理解线性规划的基本解和基本可行解的概念和它们的代数表示、基本可行解和可行域顶点的等价性。§2.2

单纯形法理解用于判定最优解和确定新可行解的基本概念与方法，熟练掌握单纯形法的具体步骤以及求解过程中使用的表格形式，了解用单纯形法同计算机实现有关的三个问题和解决办法。

§2.3

线性规划的对偶与对偶单纯形法熟练掌握标准型线性规划问题的对偶问题的形式和一般形式线性规划问题的对偶问题的形式，理解原规划问题确定对偶问题的一般对偶关系和原则。掌握描述原问题和对偶问题的最优解之间关系的弱对偶定理扣强对偶定理．§2.4

线性规划的内点算法了解原始对偶内点算法的迭代序列产生的基本原理和过程，熟练掌握线性规划的内点算法，掌握确定初始可行内点的方法和算法的计算复杂性。三、重点、难点提示和教学手段（一）重点、难点1.线性规划模型的特征、基本概念及基本理论；2.单纯形方法的基本思想和方法；3.对偶理论及对偶单纯形法；4.线性规划的内点算法（二）教学手段课堂讲授、课堂演示和习题课相结合四、思考与练习P81：1(1),2(2),4（1,2），5（2），8（1，2），11（注：具体形式由教师自行掌握。）第三章

线性搜索与信赖域方法一、学习目的通过本章的学习，要求学生理解一维搜索算法的构造方法；掌握两个常用算法——0.618法和逐次插值法，能应用这些算法求解一维搜索问题。了解精确线性搜索的收敛性；掌握常用的非线性搜索方法；理解信赖域方法的构造思想，掌握信赖域方法的基本模型和算法的基本形式；了解信赖域方法的总体收敛性和解信赖域子问题。本章计划10学时。二、课程内容§3.1

线性搜索掌握线性搜索的迭代格式，理解相关基本概念，掌握确定搜索区间的进退法。§3.2

0.618法和Fibonacci法理解0.618法和Fibonacci法的基本思想，熟练掌握它们的算法步骤，了解二分法的基本思想。§3.3

逐次插值逼近法理解三点二次插值、二点二次插值法的思想，熟练掌握它们的算法步骤，了解两点二次插值的收敛速度，了解两点三次插值的思想。§3.4

精确线性搜索方法的收敛性掌握精确线性搜索的无约束最优化算法的一般形式，掌握精确线性搜索收敛的条件。§3.5

不精确线性搜索方法理解Goldstein准则，掌握Goldstein不精确线性搜索算法；理解Wolfe准则，掌握Wolfe不精确线性搜索算法；了解Armijo准则。理解不精确线性搜索的一般步骤和收敛性能。§3.6

信赖域方法的思想和算法框架理解信赖域方法的思想，掌握信赖域方法的算法§3.7

信赖域方法的收敛性理解信赖域方法模型子问题的Cauchy点、精确解和近似解的关系，掌握信赖域方法的整体收敛性。§3.8

解信赖域子问题掌握解信赖域子问题的折线法和双折线法的思想与算法。三、重点、难点提示和教学手段（一）重点、难点1.线性搜索的迭代格式和确定搜索区间的进退法；2.

0.618法和逐次插值法；3.

Goldstein不精确线性搜索法和Wolfe不精确线性搜索算法；4.信赖域方法的基本模型和算法的基本形式；5.信赖域方法的总体收敛性和解信赖域子问题。（二）教学手段课堂讲授、课堂演示和习题课相结合四、思考与练习（注：具体形式由教师自行掌握。）

第四章

无约束最优化方法一、学习目的

本章是全书最重要主要内容之一，通过学习，要求学生理解最速下降法、共轭梯度法、Newton法和拟Newton法的算法构造，熟练其掌握算法，并应用这些方法求解无约束最优化问题。本章计划10学时。

二、课程内容§4.1

最速下降法理解最速下降法的算法构造思想和算法，掌握最速下降法的总体收敛性。§4.2Newton法掌握Newton法的算法，理解Newton法的收敛定理，了解精确线性搜索和Wolfe不精确线性搜索条件下带步长因子的Newton法的收敛性，并会用Newton法求解无约束优化问题。§4.3

共轭梯度法理解共轭方向的概念，掌握共轭方向法求解无约束优化问题的算法，了解在精确线性搜索情况下共轭方向法的收敛性，掌握共轭梯度法搜索方向的确定方法和共轭梯度法求解无约束正定二次函数优化的算法，了解共轭梯度法的性质和预处理共轭梯度法，掌握求解非二次函数最优化问题的共轭梯度法，了解其收敛性。§4.4

拟牛顿法掌握拟牛顿条件和拟牛顿算法，了解拟牛顿法的优缺点，DFP校正和BFGS校正。三、重点、难点提示和教学手段（一）重点、难点1.

最速下降法的算法构造与算法；2．

共轭方向的概念及其基本性质；共轭梯度下降方法的算法；3．

牛顿法的算法构造和一些常见的修正算法；4．拟牛顿条件及拟牛顿算法的一般形式；

DFP校正公式和BFGS校正公式。（二）教学手段课堂讲授、课堂演示和习题课相结合四、思考与练习（注：具体形式由教师自行掌握。）

第五章

线性与非线性最小二乘问题一、学习目的本章主要介绍求解线性与非线性最小二乘问题的常用方法。通过本章的学习，要求学生了解最小二乘问题的来源，掌握线性最小二乘问题的解法，掌握求解非线性最小二乘问题的Gauss-Newton法、L—M算法和信赖域方法，了解对Gauss-Newton矩阵的拟牛顿修正算法。本章计划8学时。二、课程内容§5.1

线性最小二乘问题的解法复习线性最小二乘问题的解法，求线性最小二乘问题最优解的正交分解算法，理解求线性等式约束线性最小二乘问题的思想，掌握线性等式约束最小二乘问题的正交分解算法和线性等式约束线性最小二乘问题的Lagrange乘子法，了解解线性不等式约束的线性最小二乘问题的解法。§5.2

非线性最小二乘的Gauss—Newton法理解非线性最小二乘的Gauss—Newton法的求解思想，掌握解非线性最小二乘的Gauss—Newton法的算法，了解该算法的收敛性算法的具体的特征，方法适用问题的类型，以及方法的不足，了解阻尼Gauss—Newton算法。§5.3

解非线性最小二乘问题的信赖域方法了解解非线性最小二乘问题的信赖域方法的推导过程，掌握该方法的算法，理解其收敛性和收敛速度。§5.4

对Gauss—Newton矩阵的拟牛顿修正了解根据问题结构用拟牛顿法修正解非线性最小二乘问题的修正公式的推导原理和基本过程，掌握利用这些公式求解非线性最小二乘问题的拟牛顿型算法。三、重点、难点提示和教学手段（一）重点、难点1.

线性最小二乘问题最优解的正交分解算法；2.

解非线性最小二乘的Gauss—Newton法的算法；3.

解非线性最小二乘问题的信赖域方法。

（二）教学手段课堂讲授和习题课相结合四、思考与练习（注：具体形式由教师自行掌握。）

第六章

二次规划

一、学习目的本章简要介绍二次规划的基本理论与算法，通过本章的学习，要求学生了解二次规划的实际应用背景，掌握二次规划的模型和基本求解方法。本章计划6学时。二、课程内容§6.1

二次规划了解二次规划的实际应用背景，掌握二次规划的模型和相关概念。§6.2

等式约束二次规划问题了解直接消去法的基本原理和公式推导，掌握等式约束二次规划问题的KKT条件和KKT方程，熟练掌握解等式约束二次规划问题的间接消去法，并应用该方法求解实际问题。§6.3

凸二次规划的有效集方法理解不等式约束二次规划的有效集方法的原理，熟练掌握该方法的具体算法，并能用该方法求解实际问题。三、重点、难点提示和教学手段（一）重点、难点1.

二次规划模型与相关概念；2.

求解等式约束二次规划的间接消去法；3.

求解凸二次规划的有效集方法。（二）教学手段课堂讲授、课堂演示和习题课相结合

四、思考与练习（注：具体形式由教师自行掌握。）

第七章

约束最优化的理论与方法

一、学习目的本章主要研究约束优化问题的理论与求解方法，约束优化问题的理论与最优件条件是最优化算法的基础。通过本章的学习，要求学生掌握约束优化问题的基本概念和KKT条件，熟练掌握函数法、序列二次规划法解约束优化问题的算法。本章计划8学时。

二、课程内容§7.1

约束最优化问题与最优性条件理解约束最优化问题的积极约束条件（非积极约束约束）、可行性方向、非可行性方向和序列可行性方向的概念；熟练掌握约束优化问题的一阶最优性条件（KKT条件），了解约束优化问题的二阶充分条件和必要条件。

§7.2

二次罚函数方法熟练掌握次罚函数方法的原理和算法，并应用该方法求解约束优化问题，了解其收敛性能。§7.3内点障碍罚函数法了解内点障碍函数原理和适用范围，掌握内点罚函数法解约束优化问题的算法，并会用该方法求解实际约束优化问题。§7.4

序