凸优化 (2021年秋季)

本课程考核包括平时作业和程序，期中考试和期末大项目，请谨慎选课
课程代码：00102906 (研究生），00136660 (本科）
教师信息：文再文，wenzw at pku dot edu dot cn
助教信息：朱桢源，陈一鸣
上课地点: 理教306
上课时间：
- 每周周二1~2节，双周周四1~2节， 8:00am - 9:50am
- 老师答疑时间：单独和老师联系或者每次课后
- 助教答疑时间：待定
- 北京大学校历
课程微信群（下面二维码9月20日失效）

教材：
- “最优化：建模、算法与理论”，刘浩洋, 户将, 李勇锋，文再文
- 凸优化 (2020年秋季)
参考材料：
- “Introductory Lectures on Convex Optimization. A Basic Course”, Yu. Nesterov, (2004)
- “Convex optimization”, Stephen Boyd and Lieven Vandenberghe
- “Numerical Optimization”, Jorge Nocedal and Stephen Wright, Springer
- “最优化理论与方法”，袁亚湘，孙文瑜，科学出版社，2003
- “Optimization Theory and Methods”, Wenyu Sun, Ya-Xiang Yuan
- The Matrix Cookbook, Kaare Brandt Petersen, Michael Syskind Pedersen
课程信息（大致安排）
- 第1周，9月14日，课程简介，凸优化问题介绍
  讲义下载，本节内容由邓展望协助准备
   demo: sparse_l1_example.m
- 第2周，9月21日，中秋节放假
- 第2周，9月23日，凸集的定义和判别
  讲义下载，本节内容由丁思哲协助准备
  read chapter 2 in the book “Convex optimization”.
- 第3周，9月28日，凸函数的定义和判别
  讲义下载，本节内容由华奕轩协助准备
  read chapter 3 in the book “Convex optimization”.
- 第4周，10月5日，国庆节放假
- 第4周，10月7日，国庆节放假
- 第5周，10月12日，数值代数基础，向量，矩阵，范数，子空间，Cholesky分解，QR分解，特征值分解，奇异值分解
  讲义下载，本节内容由张轩熙协助准备
  numerical algebraic background 请读非线性规划参考材料
  demo: demo_linalg.m
  Demo: Sparse matrix-dense vector products using intel MKL
  BLAS (Basic Linear Algebra Subprograms)
  LAPACK (Linear Algebra PACKage)
  Intel Math Kernel Library – Documentation
  Call LAPACK and BLAS Functions in Matlab
- 第6周，10月19日，典型的凸优化问题
  讲义下载，本节内容由邓展望协助准备
  read chapter 4 in in the book “Convex optimization”
- 第6周，10月21日，线性规划，二次锥规划，半定规划简介: lecture notes
  线性规划，二次锥规划，半定规划例子: lecture notes
  凸优化模型语言和算法软件，CVX, SDPT3, Mosek, CPLEX, Gruobi
  Prof. Boyd lecture notes on Disciplined convex programming and CVX
  read chapter 4 in in the book “Convex optimization”
  Introduction on Linear Programming (LP), read Chapter 1 in “Introduction to Linear Optimization” by Dimitris Bertsimas and John N. Tsitsiklis.
  Second-order Cone Programming (SOCP), read section 2 in “Second-order cone programming”
  Semidefinite Programming (SDP), read section 3 in “SDP-M-J-Todd” and section 2 in “SDP-Lieven-Boyd”
  The max cut paper by Goemans and Williamson
  模型语言： CVX, YALMIP
  LP, SOCP, SDP典型算法软件: SDPT3, MOSEK, CPLEX, GUROBI
  NLP 典型算法软件: Ipopt, KNITRO
  Decision Tree for Optimization Software
- 第7周，10月26日，对偶理论, 凸优化最优性条件
  讲义下载，本节内容由谢中林协助准备
  read chapter 5 in in the book “Convex optimization”
  Lagrangian function, Lagrangian dual problem, examples
  max cut problem: dual of nonconvex problem, SDP relaxation: the dual of the dual
  duality using problem reformulation
- 第8周，11月2日，对偶理论, 凸优化最优性条件
- 第8周，11月4日，梯度法和线搜索算法，最速下降法及其复杂度分析，线搜索算法，Barzilar-Borwein 方法
  讲义下载，本节内容由谢中林协助准备
  Complexity analysis: Yu. Nesterov, Introductory Lectures on Convex Optimization. A Basic Course (2004), section 2.1.
  Line search: “Numerical Optimization”, Jorge Nocedal and Stephen Wright, chapter 3: 3.1, 3.5
  Barzilar-Borwein Method: “Optimization Theory and Methods”, Wenyu Sun, Ya-Xiang Yuan, section 3.1.3
  Matlab code on the BB method with nonmonotone line search
- 第9周，11月9日，次梯度
  讲义下载，本节内容由朱桢源协助准备
- 第10周，11月16日，次梯度算法，讲义下载，本节内容由朱桢源协助准备
- 第10周，11月18日，期中考试
- 第11周，11月23日，近似点算子的构造和性质
  讲义下载，本节内容由陈乐恒，朱桢源协助准备
- 第12周，11月30日，近似点梯度法的构造和分析，条件梯度法, inertial proximal method
  讲义下载，本节内容由陈乐恒，朱桢源协助准备
   “Proximal Algorithms”, N. Parikh and S. Boyd, Foundations and Trends in Optimization, 1(3):123-231, 2014.
  条件梯度法参考：王奇超,文再文,蓝光辉,袁亚湘, 优化算法复杂度分析简介, (paper)
  Peter Ochs, Yunjin Chen, Thomas Brox, and Thomas Pock, iPiano: Inertial Proximal Algorithm for Nonconvex Optimization, SIAM J. IMAGING SCIENCES, Vol. 7, No. 2
- 第12周，12月2日， Nesterov加速算法和分析
  讲义下载，本节内容由李煦恒协助准备
   Prof. Lieven Vandenberghe's lecture notes on smoothing
  王奇超,文再文,蓝光辉,袁亚湘, 优化算法复杂度分析简介, (paper)
  Paul Tseng, Approximation accuracy, gradient methods, and error bound for structured convex optimization, Math. Program., Ser. B (2010) 125:263–295
  参考文献： Amir Beck, Marc Teboulle, A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
  Weijie Su, Stephen Boyd, E. Candes, A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
- 第13周，12月7日，增广拉格朗日函数法
  讲义下载，本节内容由陈乐恒，丁思哲协助准备
- 第14周，12月14日，近似点算法
  讲义下载，本节内容由陈乐恒，邓展望协助准备
- 第14周，12月16日，对偶算法
  讲义下载，本节内容由朱桢源协助准备
- 第15周，12月21日，交替方向乘子法
  讲义下载，本节内容由华奕轩协助准备
   “Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers”, S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Foundations and Trends in Machine Learning, 3(1):1–122, 2011
  Daniel O'Connor, Lieven Vandenberghey, On the equivalence of the primal-dual hybrid gradient method and Douglas-Rachford splitting
- 第16周，12月28日， Block Coordinate Descent Methods
  讲义下载，本节内容由朱桢源协助准备
   Jérôme Bolte, Shoham Sabach, Marc Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems
- 第16周，12月30日， semi-smooth Newton methods
  讲义下载，本节内容由李勇锋，邓展望协助准备

成绩评定
- 迟交一天(24小时）打折10%，不接受晚交4天的作业和项目（任何时候理由都不接受）
- 7次大作业，包括习题和程序： 40%
- 期中闭卷考试：30%.
- 期末课程项目： 30%
- 作业要求：i) 计算题要求写出必要的推算步骤，证明题要写出关键推理和论证。数值试验题应该同时提交书面报告和程序，其中书面报告有详细的推导和数值结果及分析。 ii) 可以同学间讨论或者找助教答疑，但不允许在讨论中直接抄袭，应该过后自己独立完成。 iii) 严禁从其他学生，从互联网，从往年的答案，其它课程等等任何途径直接抄袭。iv) 如果有讨论或从其它任何途径取得帮助，请列出来源。

平时作业（具体内容会持续更新）
- 下面习题选自教材：“最优化：建模、算法与理论”，刘浩洋, 户将, 李勇锋，文再文
- 作业一: 习题：1.4, 2.4, 2.6, 2.7, 交作业时间： 9月28日课堂上交（上课前）。
- 作业二: 习题： 2.8, 2.9, 2.11, 交作业时间： 10月12日课堂上交（上课前）。
- 作业三: 习题：3.7, 3.14, 4.3, 4.4, 4.5, 交作业时间：10月21日课堂上交（上课前）。
- 作业四: 习题：4.8, 4.9, 4.10, 4.12, 交作业时间： 11月2日课堂上交（上课前）。
- 作业五: 习题：5.3, 5.7, 5.10, 5.14, 5.16, 交作业时间： 11月16日课堂上交（上课前）。
- 作业六: homework5g.pdf 交作业时间:
  - 11月23日: 1, 2
  - 12月2日: 3 (a), (b)
  - 12月14日: 3 (c), (d), (e)
  - 12月28日: 3 (f), (g), (h)
  - 选做题: (i), (j)
  - 作业5提交指南
  - 后继作业文件和上机报告可以包含之前提交的内容
  - 报告和程序等等打包（文件名为 “gl-StudentID-date.zip”）发email给助教 (pkuopt@163.com)
- 作业七: 习题：2.13， 2.14， 6.5, 8.4, 交作业时间： 12月7日课堂上交（上课前）。

期中考试

考试范围：凸集，凸函数，凸优化问题，对偶理论。教材第2，4，5章。书 “Convex optimization” 的chapters 2,3,4,5
2019年期中考试题目

期末课程项目（具体内容会持续更新，下面是去年的内容）

分组: 自由组合, 不超过2人一组，可以一个人
课题一：Software implementaion for the proximal gradient methods
2021年课题一的基本要求点击此文件。
课题二：两层神经网络优化问题的算法和理论分析
课题二的基本要求点击此文件。
Reference on matrix calculus and backpropagation:
Stanford: CS224n, Christopher Manning, Gradients by hand (matrix calculus) and algorithmically (the backpropagation algorithm)
Stanford: CS224n: Natural Language Processing with DeepLearning
Kevin Clark, Computing Neural Network Gradients
评分准则
- 任选一个课题，任务包括但不限于：实现算法，分析理论性质，在大量测试问题上数值试验。
- 鼓励提出原创性算法和分析。

重要日期和提交内容：
- 2022年1月13日晚12点（不接受晚交报告），书面报告 (包括latex源文件，程序等等打包发email给助教 (pkuopt@163.com)。
  提交的文件请全部打包，文件名为见具体要求文件。
- 请在书面报告声明：本项目文件的主要内容没有用在其它课程做为课程项目或作业提交。
- 如果是多人组队，请明确说明每人负责的部分和内容。