Skip to content

最优化算法

最优化算法是人工智能、数据科学等相关领域的必修课程。 本课程从优化问题的建模出发，主要介绍不同优化模型的求解思想，求解算法，也兼顾对基本的优化理论学习。 课程内容包括了连续和离散优化，以无约束优化，线性规划和整数优化为重点内容。 本课程亦可是学生未来学习数据和决策分析等的高级技术的基础。

大纲

  1. 一维无约束优化
    • Goldsection, 斐波那契法，二分法
    • 牛顿法，割线法，二次拟合法
  2. 多维无约束规划-案例及最优性条件
    • 案例：统计回归
    • 最优性条件
    • 下降法，Wolf近似条件
    • 梯度法，共轭法
    • 牛顿法，拟牛顿法
  3. 有约束规划
    • 案例：SVM
    • 拉格朗日对偶、最优性条件-KKT，
    • 线性约束：投影法
    • 外点法，内点法
  4. 线性规划
    • 案例：调度、回归等
    • 单纯形法
    • 对偶问题及对偶性质
    • 对偶单纯形(optional)
  5. 整数规划
    • 案例:选址问题
    • 线性松弛、完全幺模矩阵、网络流.
    • Gomory割平面法
    • 分支定界
    • Rounding和其他算法
  6. 组合优化
    • TBD

课程要求

基本的微积分和线性代数基础； 最好会一门编程语言。

教学ppt

日期 课程内容 课堂PPT 作业下载
2024年9月2日 绪论 PPT 无
2024年9月4日 24ch02-1-简单优化问题-一维搜索-不可导 PPT 无
2024年9月9日 24ch02-2-简单优化问题-一维搜索-可导 PPT 习题：教科书P88-P89页： 7.1, 7.2-b,c, 7.7, 7.9
2024年9月11日 24ch03-1-基础知识-多维函数概念 PPT 无
2024年9月14日(按照9.16周一上课) 24ch03-2-基础知识-凸集、凸函数和凸优化 PPT 习题：教科书P369, 22.6, 22.8, 22.20
2024年9月18日 24ch04-1-无约束规划-案例及最优性条件 PPT 习题：教科书P65, 6.8, 6.9, 6.30
2024年9月18日-23日 24ch04-2-无约束规划-下降法 PPT 无
2024年9月23日 24ch04-3-无约束规划-一阶方法-梯度 + 共轭法 共轭法PPT 习题：教科书8.1，8.8，8.16, 10.5,10.7,10.9
2024年9月25日 24ch04-4-无约束规划- 牛顿法 牛顿法PPT 无
2024年9月30日 24ch04-4-无约束规划-拟牛顿法1 拟牛顿法PPT 无
2024年10月9日 24ch04-4-拟牛顿法 2 -- 无
2024年10月12日 （按照国庆假期10.7日周一上课） 24ch05-1-有约束规划-案例, SVM PPT 无
2024年10月14日 24ch05-2-有约束优化-拉格朗日对偶，等式约束的一阶最优性条件 拉格朗日对偶,等式约束一阶必要条件，KKT等，PPT 无
2024年10月16日 有约束优化-KKT条件 -- 无
2024年10月21-22日 （调课）无课程 -- 无
2024年10月28日 有约束优化算法，投影法，罚函数法 PPT 无
2024年10月30日 有约束优化算法内点法，习题课1 -- 无
2024年11月4日 习题课2， 线性优化案例介绍 PPT 无
2024年11月6日 线性优化基本概念 PPT 无
2024年11月11日-11月13日 线性优化-单纯形法，二阶段 PPT 无
2024年11月18日 线性优化-对偶 PPT 无
2024年11月20日 对偶单纯形*，线性规划求解器 PPT 习题：教科书15.1,15.5,16.3,16.4,16.9,17.4,17.6,17.15
2024年11月25日 整数规划基础 PPT 无
2024年11月27日 Gomory切平面 PPT 无

课程答疑

一般情况下，助教会在群内回复各位同学的疑问。任课老师会根据助教反馈将大家都存在的问题在课堂上解释。 教师办公室：科研4号楼545

课程资源