最优化方法 (2024年秋季)

  • 本课程考核包括平时作业和程序,期中考试和期末考试

  • 课程代码:00130630 (数院本科),00100887 (数院研究生),08617040 (工学院:优化方法概论)

  • 教师信息: 文再文,wenzw at pku dot edu dot cn

  • 助教信息:聂涵韬,王崇宇

  • 上课地点: 理教309

  • 上课时间:

    • 每周周一1~2节(8:00am - 9:50am),单周周四1~2节(8:00am - 9:50am)

    • 老师答疑时间:单独和老师联系或者每次课后

    • 助教答疑时间:待定

    • 北京大学校历

  • 课程微信群 (下面二维码9月14日失效)

120px 
  • 成绩评定

    • 迟交一天(24小时)打折10%, 不接受晚交4天的作业和项目

    • 每一周或者两周有少量作业,包括习题和程序: 40%

    • 期中闭卷考试:30%.

    • 期末闭卷考试: 30%

    • 作业要求:i) 计算题要求写出必要的推算步骤,证明题要写出关键推理和论证。数值试验题应该同时提交书面报告和程序,其中书面报告有详细的推导和数值结果及分析。 ii) 可以同学间讨论或者找助教答疑,但不允许在讨论中直接抄袭,应该过后自己独立完成。 iii) 严禁从其他学生,从互联网,从往年的答案,其它课程等等任何途径直接抄袭。iv) 如果有讨论或从其它任何途径取得帮助,请列出来源。

  • 平时作业 (具体内容会持续更新,根据课程情况调整)

    • 下面习题选自教材:“最优化:建模、算法与理论”,刘浩洋, 户将, 李勇锋,文再文,大部分习题有参考答案

    • 作业一: 习题1.4, 2.7, 交作业时间: 9月16日课堂上交(上课前)。

    • 作业二: 习题2.8, 例题2.9, 交作业时间: 9月23日课堂上交(上课前)。

    • 作业三: 习题4.9, 4.12, 交作业时间:9月30日课堂上交(上课前)。

    • 作业四: 习题5.3, 写出习题4.12中半定规划的对偶问题,以及对偶的对偶问题, 交作业时间: 10月14日课堂上交(上课前)。

    • 作业五: 习题5.10, 5.14, 交作业时间: 10月21日课堂上交(上课前)。

    • 作业六: 最优化练习题2, 9, 交作业时间: 10月28日课堂上交(上课前)。

    • 作业七: 推论6.2, 习题6.4, 交作业时间: 11月4日课堂上交(上课前)。

    • 作业八: 习题6.6, 最优化练习题19, 交作业时间: 11月11日课堂上交(上课前)。

    • 作业九: 最优化练习题11, 16, 交作业时间: 11月18日课堂上交(上课前)。

    • 作业十: 习题8.1, 8.2(b) (c), 交作业时间: 11月21日课堂上交(上课前)。

    • 作业十一: 习题8.6, 最优化练习题20(a)-(e), 交作业时间: 11月25日课堂上交(上课前)。

    • 作业十二: 习题8.16, 最优化练习题20, 交作业时间: 12月23日课堂上交(上课前)。

    • 程序作业: homework5g.pdf, 完整报告和程序提交时间12月23日,但建议按如下时间节点完成任务:

      • 11月4日: 1, 2

      • 11月11日: 3 (a), (b)

      • 12月2日: 3 (d), (e)

      • 12月9日: 3 (f)

      • 12月16日: 3 (g), (h)

      • 其它题选做

      • 程序作业提交指南

      • 教材配套程序

      • 后继作业文件和上机报告可以包含之前提交的内容,建议按时间节点完成

      • 请将完整报告和程序等等打包(文件名为 “gl-StudentID-date.zip”)发email给助教 (pkuopt@163.com)

期中考试

  • 考试范围:教材第2,4,5章课上讲过的相关内容,包括但可能不限于以下典型内容。

    • 凸集的定义和判断,对偶锥的定义和推导

    • 凸函数的定义和不同条件下的判断

    • 凸优化问题定义和(线性规划、二次锥规划、半定规划)判断,能写出锥的具体形式。

    • 弱对偶原理,强对偶,对偶理论,推导对偶问题,或者对偶的对偶问题。二次约束二次规划(QCQP)和简单整数规划的对偶,半定规划松弛的推导。Farkas 引理,利用线性规划强对偶证明Farkas 引理。

    • 简单优化问题显式解的推导(包括但不限于利用最优性条件推导)

    • 凸优化问题(一阶)必要和充分最优条件。必要条件注意验证Slater条件。

    • 可微非凸优化问题一阶必要最优条件,二阶必要和充分最优条件。必要条件注意验证约束规范(LICQ, MFCQ)

  • 2017年期中考试题目(三节课)

  • 2018年期中考试题目(三节课)

  • 2019年期中考试题目(两节课)

  • 2020年期中考试题目(两节课)

  • 2022年期中考试题目(两节课)

期末考试

  • 最优化练习题,持续更新

  • *闭卷考试:

  • 考试范围:教材第6,7,8章课上讲过的相关内容,包括但可能不限于以下典型内容。

    • 线搜索条件、线搜索回退法

    • 梯度下降算法、一般凸函数固定步长情形下复杂度分析、强凸函数收敛性分析、Barzilar-Borwein方法

    • 次梯度定义和计算、次梯度算法、典型步长的取法及其复杂度分析

    • 牛顿法及其收敛性分析、拟牛顿公式、有限内存拟牛顿法(L-BFGS)、信赖域算法、信赖域子问题最优性条件及其求解算法

    • 二次罚函数法、增广拉格朗日函数的构造、增广拉格朗日函数算法(乘子的更新格式)

    • 近似点算子(常见函数的近似点的计算)、近似点梯度法、复杂度分析

    • Nesterov加速算法、复杂度分析

    • 交替方向乘子法(ADMM):拆分方式的选择、子问题的构造、典型问题的ADMM、

    • 对偶问题推导(利用共轭函数)、对偶梯度法、对偶近似点梯度法、min-max (saddle point) 问题推导、PDHG和CP算法

数学形式化计划

  • 3+X讨论班
    近年来,人工智能赋能科学研究的AI for Science新范式蓬勃发展,然而人工智能在数学领域,特别是在定理证明方面仍充满挑战。传统上数学形式化和定理证明由数学家完成,但是这种方式需要花费大量时间和精力,并且存在人为疏漏和错误的风险。人工智能的发展给数学形式化和定理证明带来了新的机遇。我们将于2024年秋季学期开设形式化讨论班,旨在探索利用人工智能技术推动数学形式化和定理证明的发展,进一步提高定理证明的效率和准确性,帮助验证一些相关领域中关键定理证明。

  • 2024年10月底前完成Lean提供的tutorial中10道练习题。

  • 2024年12月底前完成指定的1-2道数学定理的形式化证明。

  • Documentation of Lean

  • Theorem Proving in Lean 4