最优化方法

课程简介：最优化方法广泛应用于各类工程、公共管理、经济管理、国防等各个领域，是许多工程技术人员、管理人员和研究工作者的重要工具。当前，由于科学技术的快速发展、图像处理、
信号恢复、大数据研究等领域的广泛应用，学习和掌握常用的最优化方法及相关的基础理论知识，已成为运筹学与控制论方向的一个重要内容。

课程代码：MAS33600C

教师信息： 卢越，jinjin403@sina.com

上课地点:

上课时间：

参考教材：

• “非线性规划”，[美] 博塞克斯（Dimitri P.Bertsekas） 著；宋士吉，张玉利，贾庆山译，清华大学出版社，2013

• “最优化理论与方法”，袁亚湘，孙文瑜，科学出版社，2003

• “最优化方法”, 解可新，韩立兴，林友联，天津大学出版社，1997

• “最优化方法及其MATLAB程序设计”, 马昌凤，科学出版社，2009

• “Numerical Optimization”, Jorge Nocedal and Stephen Wright, Springer

教学内容：

理论部分：

• 数学基础知识（6学时）
  内容：介绍最优化问题的实例、模型、基本概念和分类及最优化方法的一些预备知识，包括数值代数基础，多元函数基础和凸分析基础。 要求：了解最优化方法所研究的对象及分类，掌握最优化方法中的一些基础知识，如向量范数和矩阵范数定义，方向导数的计算，链式法则的应用，凸集合和凸函数的定义及等价刻画等。

• 最优性条件（15学时）
  内容：介绍优化问题中解的分类和相应的最优性条件，介绍凸集约束优化问题的形式，凸集上投影的刻画，约束优化问题KKT系统的定义。 要求：了解无约束优化最优性条件，掌握凸集上投影的性质，约束优化局部最优解和全局最优解的定义，掌握约束一阶最优性条件和二阶最优性条件的结论，能够写出给定约束优化问题对应的KKT系统和使用二阶充分性条件分析问题。

• 无约束优化算法（18学时）
  内容：介绍无约束优化问题中解的分类，最优性条件，无约束优化线搜索算法的结构，算法收敛速度的比较，线搜索原则，步长选择策略及下降算法的收敛性分析。介绍求解无约束优化问题梯度方法的迭代格式，证明此类算法的收敛性并分析其收敛速度。介绍求解无约束优化问题的牛顿法的迭代格式，证明此类算法的收敛性，分析其收敛速度，了解牛顿法的几类应用。介绍共轭方向法的基本思想，分析共轭方向的性质，构建共轭梯度法的迭代格式，分析共轭梯度法的全局收敛性和收敛速度。介绍拟牛顿法的基本思想，拟牛顿方程的重要性质，几类拟牛顿法的迭代格式及性质，分析拟牛顿法的全局收敛性和收敛速度。 要求：了解无约束优化局部最优解和全局最优解的定义，掌握无约束一阶最优性条件和二阶最优性条件的结论，能够使用二阶充分性条件分析问题；理解精确线搜索和非精确线搜索的基本原理，学会分析比较算法的收敛速度及证明给定下降算法的收敛性。了解梯度方法的一般形式，能够写出算法的迭代步骤，简单证明算法的全局收敛性，并了解该方法具有全局收敛性和局部线性收敛速度。了解牛顿法的一般形式，能够写出算法的迭代步骤，证明算法的收敛性，并能够证明该方法局部二次收敛速度。了解共轭方向的定义，掌握共轭方向的简单性质，能够写出几类共轭梯度法的迭代格式，了解共轭梯度法的收敛性结论。能够写出拟牛顿方程，DFP算法和BFGS算法的迭代格式，了解该算法的全局收敛性和局部超线性收敛速度。

• 约束优化算法（12学时）
  内容：可行方向法和投影梯度法的设计思想，介绍求解约束优化问题的罚函数方法及收敛性结论，介绍求解约束优化问题的乘子法，乘子法的性质，乘子法求解约束优化的收敛性结论。 要求：了解可行方向法和投影梯度法的设计思想，能够写出两类算法的迭代格式。了解内外罚函数方法的性质，能够利用内外罚函数方法求解约束优化问题的局部最优解。了解乘子法的性质，能够利用乘子法求解约束优化问题的局部最优解。

上机部分：

• Julia基础（4学时）
  内容：了解Julia的语法基础，利用Julia进行基础编程。 要求：熟悉Julia的集成环境，编写Julia基础程序（jl文件和画图）。

• 精确线搜索准则及其Julia实现(4学时)
  内容：黄金分割法和抛物线法的Julia编程 要求：（1）了解Julia程序设计的基本原则；（2）掌握函数的编写和调用；（3）黄金分割法和抛物线法的Julia编程；（4）掌握Julia数值计算的基本方法。

• 非精确线搜索准则及其Julia实现(4学时)
  内容：Armijo准则的Julia实现;Goldstein准则的Julia实现;Wolfe-Powell准则的Julia实现（选做） 要求：（1）实现Armijo准则的Julia程序；（2）实现Goldstein准则的Julia程序；（3）实现Wolfe-Powell准则的Julia实现（选做）；（4）进行数值结果分析，提交实验报告。

• 求解无约束优化问题的最速下降法和牛顿法(6学时)
  内容：了解最速下降法和牛顿法设计思想简介，掌握无约束优化线搜索框架的一般迭代步骤并进行Julia编程。 要求：（1）实现最速下降法的Julia程序；（2）实现牛顿法的Julia程序；（3）进行数值结果分析，提交实验报告。

• 求解无约束优化问题的共轭梯度法(6学时)
  内容：了解各类共轭梯度法的迭代公式;编写各类共轭梯度法的Julia求解程序。 要求：（1）了解各类共轭梯度法的设计思路；（2）实现FR和PRP共轭梯度法的Julia程序；（3）进行数值结果分析，提交实验报告。

• 求解无约束优化问题的拟牛顿法(6学时)
  内容：了解各类拟牛顿法的迭代公式;编写各类拟牛顿法的Julia求解程序。 要求：（1）了解各类拟牛顿法的设计思路；（2）实现BFGS和DFP拟牛顿法的Julia程序；（3）进行数值结果分析，提交实验报告。

• JuMP优化包介绍（4学时）
  内容：了解JuMP并利用其对所给出模型的进行求解练习 要求：利用JuMP优化包对无约束和约束优化问题进行求解。