凸优化 (2017年秋季)

本课程考核包括平时作业和程序，期中闭卷考试，期末大项目，请谨慎选课
基本信息: (教学大纲)
课程代码：00102906 (研究生），00136660 (本科）
教师信息：文再文，wenzw at pku dot edu dot cn
助教信息：李勇锋: pdlyf1128 at 163 dot com，刘浩洋: liuhaoyang at pku dot edu dot cn
上课地点：理教302
上课时间：
- 每周周二7~9节, 15:10pm - 18:00pm
- 老师答疑时间：单独和老师联系或者每次课后18:00pm-18:30pm
- 助教答疑时间：待定
- 北京大学校历
课程微信群（下面二维码9月18日失效）

凸优化参考材料：
参考材料：
- “Introductory Lectures on Convex Optimization. A Basic Course”, Yu. Nesterov, (2004)
- “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
课程信息（大致安排）
- Acknowledgement: I would like to thank Prof. Lieven Vandenberghe (UCLA) and Prof. Wotao Yin (UCLA). Most of the slides are motivated or even taken directly from their courses.
- 第1周，9月12日，课程简介，凸优化问题介绍
  lecture notes on introduction, lecture notes on convex sets, demo: sparse_l1_example.m
- 第2周，9月19日，凸集，凸集和凸函数的定义和判别
  Prof. Lieven Vandenberghe's lecture notes on convex sets
  read chapter 2 in the book “Convex optimization”.
  Prof. Lieven Vandenberghe's lecture notes on convex functions
  read chapter 3 in the book “Convex optimization”.
- 第3周，9月26日，数值代数基础，向量，矩阵，范数，子空间，Cholesky分解，QR分解，特征值分解，奇异值分解
  典型的凸优化问题
  Prof. Lieven Vandenberghe's lecture notes on numerical algebra background
  Prof. Lieven Vandenberghe's lecture notes on convex problems
  numerical algebraic background 请读非线性规划参考材料
  read chapter 4 in in the book “Convex optimization”
  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
- 第4周，10月3日，国庆节放假
- 第5周，10月10日，线性规划，二次锥规划，半定规划简介: 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”
  模型语言： CVX, YALMIP
  LP, SOCP, SDP典型算法软件: SDPT3, MOSEK, CPLEX, GUROBI
  NLP 典型算法软件: Ipopt, KNITRO
  Decision Tree for Optimization Software
- 第6周，10月17日，对偶理论, 凸优化最优性条件 Prof. Lieven Vandenberghe's lecture notes on duality
  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
- 第7周，10月24日，梯度法和线搜索算法，最速下降法及其复杂度分析，线搜索算法，Barzilar-Borwein 方法
  Prof. Lieven Vandenberghe's lecture notes on gradient methods
  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
- 第8周，10月31日，次梯度及次梯度算法, smoothing
  Prof. Lieven Vandenberghe's lecture notes on subgradient
  Prof. Lieven Vandenberghe's lecture notes on subgradient method
- 第9周，11月7日，期中考试
- 第10周，11月14日，近似点梯度法，近似点梯度法的构造和分析
  Prof. Lieven Vandenberghe's lecture notes on proximal mapping
  Prof. Lieven Vandenberghe's lecture notes on proximal gradient method
  “Proximal Algorithms”, N. Parikh and S. Boyd, Foundations and Trends in Optimization, 1(3):123-231, 2014.
- 第11周，11月21日， Conjugate function, 对偶分解, 对偶近似点算法
  Prof. Lieven Vandenberghe's lecture notes on conjugate function
  Prof. Lieven Vandenberghe's lecture notes on dual decomposition
  Prof. Lieven Vandenberghe's lecture notes on dual proximal gradient method
- 第12周，11月28日，Nesterov加速算法， Nesterov加速算法的分析和应用
  Prof. Lieven Vandenberghe's lecture notes on proximal point method
  Prof. Lieven Vandenberghe's lecture notes on fast proximal gradient method
  Prof. Lieven Vandenberghe's lecture notes on smoothing
  Stephen Boyd John Duchi's lecture notes on mirror descent methods
  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
- 第13周，12月5日，Douglas-Rachford splitting and ADMM
  Prof. Lieven Vandenberghe's lecture notes on ADMM
  “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
- 第14周，12月12日，交替方向乘子法及其变形，交替方向乘子法的构造, Distributed ADMM
  Prof. Wotao Yin's lecture notes on ADMM
- 第15周，12月19日， Block Coordinate Descent Methods, semi-smooth Newton methods
  Prof. Wotao Yin and Yangyang Xu's lecture notes on BCD
  lecture notes on semi-smooth methods
  Jérôme Bolte, Shoham Sabach, Marc Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems
- 第16周，12月26日，Barrier functions, Path-following methods
  Prof. Lieven Vandenberghe's lecture notes on barrier functions
  Prof. Lieven Vandenberghe's lecture notes on path following methods
  Prof. Lieven Vandenberghe's lecture notes on primal-dual methods

成绩评定
- 迟交一天(24小时）打折10%，不接受晚交4天的作业和项目（任何时候理由都不接受）
- 5-6次大作业，包括习题和程序： 40%
- 期中闭卷考试: 30%. 考试范围：凸集，凸函数，凸优化问题，对偶理论。书 “Convex optimization” 的chapters 2,3,4,5
- 期末课程项目： 30%
- 以上成绩比例可能根据实际教学情况和学生反馈意见在期末考试前一个月调整。最后方案会在11月28日课堂上确定，并会在此网页上公开。如果对方案有任何意见，请务必通过当面谈话，邮件或微信等方式及时提出。此后不再调整。
- 作业要求：i) 计算题要求写出必要的推算步骤，证明题要写出关键推理和论证。数值试验题应该同时提交书面报告和程序，其中书面报告有详细的推导和数值结果及分析。 ii) 可以同学间讨论或者找助教答疑，但不允许在讨论中直接抄袭，应该过后自己独立完成。 iii) 严禁从其他学生，从互联网，从往年的答案，其它课程等等任何途径直接抄袭。iv) 如果有讨论或从其它任何途径取得帮助，请列出来源。

平时作业（具体内容会持续更新）
- 作业一: 教材 “Convex optimization”，习题：2.9, 2.15 (a), (b), (c), 2.33, 3.11, 3.17, 3.20, 3.35 交作业时间：2.9, 2.15 (a), (b), (c), 2.33, 3.11 在 9月26日课堂上交（上课前），其它题和第二次作业一起提交。
- 作业二: 教材 “Convex optimization”，习题：4.2, 4.5, 4.8, 4.13, 4.24, 4.26. 交作业时间：10月17日课堂上交（上课前）。
- 作业三: 教材 “Convex optimization”，习题：4.28, 4.40, 4.43, 4.45, 4.47. 交作业时间： 10月31日课堂上交（上课前）。
- 作业四: 教材 “Convex optimization”，习题：5.6, 5.7, 5.16, 5.23, 5.27, 5.30. 交作业时间： 11月14日课堂上交（上课前）。
- 作业五: homework5.pdf 交作业时间:
  - 11月28日: 1, 2, 3 (a), (b)
  - 12月5日: 3 (c), (d), (e), (f)
  - 12月12日: 3 (g), (h), (i)
  - 12月19日: 4 (选做)

期末课程项目（具体内容会持续更新）

分组: 自由组合, 不超过3人一组，可以一个人
课题一：semi-smooth Newton method for linear programming
- ref1: sections 3 and 4 in Yongfeng Li, Zaiwen Wen, Chao Yang, Yaxiang Yuan, A Semi-smooth Newton Method for Solving Semidefinite Programs in Electronic Structure Calculations
课题二：algorithms for large-scale optimal transport
- ref2: Jörn Schrieber, Dominic Schuhmacher, Carsten Gottschlich, DOTmark – A Benchmark for Discrete Optimal Transport
- ref3: Samuel Gerber, Mauro Maggioni, Multiscale Strategies for Computing Optimal Transport
评分准则
- 任选一个课题，任务包括但不限于：实现算法，分析理论性质，在大量测试问题上数值试验
- 需要完成的基本课题任务文件。鼓励提出原创性算法和分析。
- 评分由两部分组成：中期报告，书面报告

重要日期和提交内容：
- 中期报告请于10月31日前发email给助教 (pkuopt@163.com)
  中期报告不超过3页纸（单面）。需要描述你们组的选题，已经完成的工作，你们将要做哪些事情
  提交的文件名为 “proj1rep1-name1-name2.pdf”. 比如如果成员为Pengyu Qian 和 Junzi Zhang，则文件名为 proj1rep1-PengyuQian-JunziZhang.pdf
- 2018年1月9日晚12点（不接受晚交报告），书面报告 (包括latex源文件，程序等等打包发email给助教 (pkuopt@163.com)。
  提交的文件请全部打包，文件名为 “proj1-name1-name2.zip”. 比如如果成员为Pengyu Qian 和 Junzi Zhang，则文件名为 proj1-PengyuQian-JunziZhang.zip