大数据分析中的算法 (2023年春季)

  • 本课程考核包括平时作业和程序,期中大项目,期末大项目,请谨慎选课

  • 上课地点:理教402

  • 外院系本科生未选上课的同学请邮件和微信告知学号

  • 2020年春季课程回放视频

  • 课程代码:00136720 (本科生),00100863 (本研合)

  • 课程内容: 侧重数据分析中的数值代数和最优化算法

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

  • 助教信息: 彭永力,柯志发

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

150px 
  • 作业和课程项目,重要日期和提交内容:

  • 课程项目

    • 课程项目二: 请见下面课程项目二细节

  • 成绩评定

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

    • 大作业,包括习题和程序: 40%

    • 课程项目一: 30%

    • 课程项目二: 30%

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

期末课程项目

  • 分组: 自由组合, 不超过2人一组,可以一个人

  • 课题: 国铁集团列车排班整数规划求解

  • 课题具体描述文件,具体内容会持续更新

  • 评分准则

    • 完成要求的任务。

    • 鼓励提出原创性算法和分析。

    • 书面报告: 每一组提交一份读书报告 (包括latex源文件 )。

    • 6月22日晚12点(不接受晚交报告),书面报告 (包括latex源文件,程序等等)打包, 发email给助教 (pkuopt@163.com)
      提交的文件请全部打包,文件名为 “proj2-name1-name2.zip”.

可选加分项目

  • 数学优化软件的开发

  • “大数据分析中的算法”教材编写草稿

    • 将课程PPT扩展成更加详细的文字版本,添加具体的问题介绍,典型算法介绍,典型的理论结果,详细的案例分析和数值结果。

挑战项目 (持续更新)

  • 实现线性规划单纯形法,能成功求解netlib测试集里所有问题:
    LP test problems from netlib
    成功求解:判断是否有可行解,是否无界,最优性条件(primal and dual infeasibility, duality gap)的违反度是否达到1e-6以下。参考 SDPT3 user guide 里sec. 3.3(第11-12页).
    故事:You have to figure out who your customer is going to be – An interview with Bob Bixby

  • 实现线性规划内点法,能成功求解netlib测试集里所有问题(标准如上题)。

  • 设计能充分利用GPU并行的线性规划单纯形法或内点法,测试性能是否有显著提升。可以挑一个大规模线性规划例子测试。

  • 选择一个问题:压缩感知,低秩矩阵恢复,鲁棒主成分分析,相位恢复,社区检测,读懂凸优化模型跟原始问题解的等价性证明

  • 选择一个问题:低秩矩阵恢复,鲁棒主成分分析,相位恢复,社区检测,考虑其非凸模型,读懂其局部极小点性质相关问题论文

  • 证明ADAM 算法的收敛性性质

  • 证明policy gradient 方法的收敛性质

  • 选择一个线性代数问题,设计随机算法

  • 选择一个机器学习模型或算法,建立半定规划模型,分析理论性质

  • 利用深度学习/强化学习求解一些超大规模的连续优化问题

  • 利用深度学习/强化学习求解离散优化问题