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

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

  • 上课地点:理教306

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

  • 2020年春季课程回放视频

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

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

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

  • 助教信息: 柳伊扬: yiyang.liu at pku dot edu dot cn,金泽宇

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

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

  • 课程项目

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

  • 成绩评定

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

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

    • 课程项目一: 30%

    • 课程项目二: 30%

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

期末课程项目

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

  • 课题: Exploiting fast algorithms for solving networking resource allocation problems
    课题具体描述文件

  • 测试数据:

    • 测试数据点击本链接 MCF问题的具体例子可以参考测试数据网页中“The AerTranspo problems”的8个例子和“The JLF problems”中的例子。这里面的MCF问题用了node-arc Formulation,里面的问题定义用到四个文件:arc, sup, nod mut四个后缀的文件。其中arc文件包含了traffic和网络link的关系,sup是flow的相关信息,mul是链路相关信息,nod是对整体问题规模的描述。

    • MCF格式文档点击本链接。虽然文档中这个formulation是基于node-arc,可以将node-arc formulation等价转化成arc-path formulation,适用于本作业中的问题

  • 评分准则

    • 任选一个子课题,任务包括但不限于:实现算法,分析理论性质,在大量测试问题上数值试验。

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

  • 重要日期和提交内容:

    • 5月13日晚12点(不接受晚交报告), 中期报告请点击此链接上传
      中期报告不超过3页纸(单面)。需要描述你们组的选题,已经完成的工作,你们将要做哪些事情
      提交的文件名为 “proj2rep1-name1-name2.pdf”. 比如如果成员为Pengyu Qian 和 Junzi Zhang,则文件名为 proj2rep2-PengyuQian-JunziZhang.pdf

    • 6月22日晚12点(不接受晚交报告),书面报告 (包括latex源文件,程序等等打包, 请点击此链接上传
      提交的文件请全部打包,文件名为 “proj2-name1-name2.zip”. 比如如果成员为Pengyu Qian 和 Junzi Zhang,则文件名为 proj2-PengyuQian-JunziZhang.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 方法的收敛性质

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

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

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

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