凸优化 (2014年秋季)

• 基本信息: (教学大纲)

• 课程代码：00102906

• 教师信息： 文再文，wenzw@math.pku.edu.cn

• 助教信息： 吴磊, jiangke1990@gmail.com

• 上课地点：三教408

• 上课时间：

  • 1~16周 每周周一3~4节, 10:10am-12:00am

  • 1~16周 双周周三1~2节, 08:00am-09:50am

  • 北京大学校历, 具体单周/双周安排

• 凸优化参考材料：

  • “Convex optimization”, Stephen Boyd and Lieven Vandenberghe

  • “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

• 课程信息 （大致安排）

  • 第1周，9月15日，课程简介，凸优化问题介绍
    lecture notes, demo: sparse_l1_example.m

  • 第2周，9月22日，凸集，凸集和凸函数的定义和判别
    Prof. Stephen Boyd and Lieven Vandenberghe's lecture notes on convex sets
    read chapter 2 in the book “Convex optimization”.

  • 第2周，9月24日，凸函数
    Prof. Stephen Boyd and Lieven Vandenberghe's lecture notes on convex functions
    read chapter 3 in the book “Convex optimization”.
    多元函数梯度，Hessian矩阵，Taylor展开请读非线性规划参考材料

  • 第3周，9月29日，数值代数基础，向量，矩阵，范数，子空间，Cholesky分解，QR分解，特征值分解，奇异值分解
    Prof. Stephen Boyd and Lieven Vandenberghe's lecture notes on numerical algebra background
    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

  • 第4周，10月6日，国庆放假

  • 第4周，10月8日，典型的凸优化问题，线性规划，二次锥规划和半定规划问题
    Prof. Stephen Boyd and Lieven Vandenberghe's lecture notes on convex problems
    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”
    

  • 第5周，10月13日，二次锥规划和半定规划问题, 凸优化模型语言和算法软件，CVX, SDPT3, Mosek, CPLEX, Gruobi
    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月20日， 对偶问题的转换
    Prof. Stephen Boyd and 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

  • 第6周，10月22日， 对偶问题的转换和对偶理论, 凸优化最优性条件
    read chapter 5 in in the book “Convex optimization”
    dual of generalized inequality, multipliers in the dual cone
    weak and strongly duality, slater condition
    complementary slackness, KKT conditions
    examples on LP, SOCP and SDP
    SOCP: section 5 in “Second-order cone programming”
    SDP: section 4 in “SDP-M-J-Todd” and section 3 in “SDP-Lieven-Boyd”
    

  • 第7周，10月27日，梯度法和线搜索算法，最速下降法及其复杂度分析，线搜索算法，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周，11月3日， 次梯度及次梯度算法
    Prof. Lieven Vandenberghe's lecture notes on subgradient
    Prof. Lieven Vandenberghe's lecture notes on subgradient method

  • 第8周，11月5日， 近似点梯度法，近似点梯度法的构造和分析
    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.

  • 第9周，11月10日，APEC 停课

  • 第10周，11月17日， 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

  • 第10周，11月19日， Nesterov加速算法， Nesterov加速算法的分析和应用
    Prof. Lieven Vandenberghe's lecture notes on fast proximal gradient method
    参考文献： Amir Beck, Marc Teboulle, A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems

  • 第10周，11月24日， 交替方向乘子法及其变形，交替方向乘子法的构造，对偶方法，拆分方法
    Prof. Lieven Vandenberghe's lecture notes on ADMM
    Prof. Stephen Boyd's lecture notes on ADMM
    Prof. Wotao Yin's lecture notes on ADMM
    Prof. Wotao Yin'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

  • 第12周，12月1日，Douglas-Rachford splitting and ADMM
    Prof. Lieven Vandenberghe's lecture notes on ADMM
    

  • 第12周，12月3日， 课程报告, Distributed ADMM
    Prof. Wotao Yin's lecture notes on ADMM
    

  • 第13周，12月8日， 课程报告, Distributed ADMM
    Prof. Wotao Yin's lecture notes on Jacobi-Type ADMM
    

  • 第14周，12月15日，课程报告, Self-Equivalence of ADMM
    Prof. Wotao Yin's lecture notes on Self-Equivalence of ADMM
    

  • 第14周，12月17日，课程报告, Smoothing
    Prof. Lieven Vandenberghe's lecture notes on smoothing
    

  • 第15周，12月22日，课程报告, Smoothing
    

  • 第16周，12月29日，课程报告, Block Coordinate Descent Methods
    Prof. Wotao Yin and Yangyang Xu's lecture notes on BCD
    

  • 第16周，12月31日，课程报告, Review of first-order algorithms using matrix completion as an example
    sp06.pdf
    

• 作业

  • 作业一: 教材 “Convex optimization”，习题：2.10, 2.20, 2.31 (a), (b), (c), 3.9, 3.18, 3.26 (a), (b), 3.37. 交作业时间： 9月29日课堂上交（上课前）。

  • 作业二: 教材 “Convex optimization”，习题： 交作业时间：习题：4.2, 4.5, 4.8, 4.13, 4.24, 4.26. 交作业时间： 10月20日课堂上交（上课前）。

  • 作业三: 教材 “Convex optimization”，习题： 交作业时间：习题：4.28, 4.40, 4.43, 4.45, 4.47. 交作业时间： 10月27日课堂上交（上课前）。

  • 作业四: 教材 “Convex optimization”，习题： 交作业时间：习题：5.6, 5.7, 5.16, 5.23, 5.27, 5.30. 交作业时间： 11月5日课堂上交（上课前）。

  • 作业五: homework5.pdf Test_l1_regularized_problems.m： 交作业时间： 12月8日课堂上交（上课前）。

• 课程项目

  • 课程项目一:
    i) 自由组合2至3人一组，从课程项目文献列表中选一篇参考文献。
    ii) 准备15分钟报告 + 5分钟提问。 每个组员均需讲差不多长度的时间。成绩评定： 50% 其中小组之间相互评定和教师意见各 50% .
    小组之间相互评定，评分为1-10。 请每组填写presentation_evaluation.xlsx发给助教.
    每组负责收集自己组的评分。如果B组课堂上没有给A组评分，则A组收集B组的评分填写为10*（请标注*号），而B组计算平均分后将减1分，扣完为止。
    iii) 每一组提交一份ppt （课堂报告文件）和一份读书报告 (包括latex源文件 )。如果文章中有数值算例，请写程序复制数值实验结果。
    提交时间： 2014 年12月31日课堂前。 成绩评定：占该项目的 50%
    iv) 分组情况请于11月1日前发email给助教，信息如下： 姓名，学号，文章题目，两个做报告的时间。
    分组情况及时间安排请查看此链接
    

  • 课程项目二: project-opt-2014-fall.pdf 交作业时间： 2014年12月22日课堂上交（上课前）。

• 成绩评定
  

  • 4-5次大作业，包括习题和程序： 50%

  • 课程项目： 50%

  • 作业要求：可以同学间讨论或者找助教答疑，但不准抄袭。计算题要求写出必要的推算步骤，证明题要写出关键推理和论证。

课程项目报告文件

• Mingyi Hong, Zhiquan Luo, On the Linear Convergence of the Alternating Direction Method of Multipliers
  吴昌晶, 何迪 presentation

• Damek Davis, Wotao Yin, Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
  秦雪, 黄卫杰, 崔金杰 presentation

• Panos Parpas, Duy V. N. Luong, Daniel Rueckert, Berc Rustem, A Multilevel Proximal Algorithm for Large Scale Composite Convex Optimization
  温见培, 潘欣 presentation

• Ji Liu, Stephen J. Wright, Srikrishna Sridhar, An Asynchronous Parallel Randomized Kaczmarz Algorithm
  冯宇婷, 魏小倩, 韩华云 presentation

• Aleksandr Aravkin, Michael P. Friedlander, Felix J. Herrmann, Tristan van Leeuwen, Robust inversion, dimensionality reduction, and randomized sampling
  方聪, 游山, 郑凯 presentation 1 presentation 2 presentation 3

• M. Soltanolkotabi, E. Elhamifar and E. J. Candès. Robust subspace clustering
  万晟, 张弛昱, 元玉慧 presentation

• Bo Jiang, Shiqian Ma, Shuzhong Zhang, Tensor Principal Component Analysis via Convex Optimization
  乔晗, 柏园超, 王轶楠 presentation

• Alexandre d'Aspremont, Noureddine El Karoui, A Stochastic Smoothing Algorithm for Semidefinite Programming
  郝彬, 周攀 presentation

• Richard H. Byrd, Gillian M. Chin, Jorge Nocedal, Yuchen Wu, Sample size selection in optimization methods for machine learning
  窦夏良, 张明睿 , 黄东明 presentation 1 presentation 2 presentation 3

• Wei Shi, Qing Ling, Gang Wu, and Wotao Yin, EXTRA: an Exact First-Order Algorithm for Decentralized Consensus Optimization
  张静茹, 孙鑫伟 presentation

• Zhaosong Lu, Lin Xiao, On the Complexity Analysis of Randomized Block-Coordinate Descent Methods
  邱韫哲, 刘泽琨 presentation

• Martin S. Andersen, Joachim Dahl, Lieven Vandenberghe, Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones
  苏奇, Lin Christy, 段高鹏 presentation

• Xin-Yuan Zhao, Defeng Sun, and Kim-Chuan Toh, A Newton-CG Augmented Lagrangian Method for Semidefinite Programming
  彭秀辉, 王琦少, 王鹏昊 presentation

课程项目文献

• Algorithms for Convex Optimization Problems

  • Panos Parpas, Duy V. N. Luong, Daniel Rueckert, Berc Rustem, A Multilevel Proximal Algorithm for Large Scale Composite Convex Optimization

  • Ji Liu, Stephen J. Wright, Srikrishna Sridhar, An Asynchronous Parallel Randomized Kaczmarz Algorithm

  • Zhaosong Lu, Lin Xiao, On the Complexity Analysis of Randomized Block-Coordinate Descent Methods

  • Wei Shi, Qing Ling, Gang Wu, and Wotao Yin, EXTRA: an Exact First-Order Algorithm for Decentralized Consensus Optimization

  • Richard H. Byrd, Gillian M. Chin, Jorge Nocedal, Yuchen Wu, Sample size selection in optimization methods for machine learning

  • Aleksandr Aravkin, Michael P. Friedlander, Felix J. Herrmann, Tristan van Leeuwen, Robust inversion, dimensionality reduction, and randomized sampling

  • M. Soltanolkotabi, E. Elhamifar and E. J. Candès. Robust subspace clustering

• Analysis of ADMM

  • Mingyi Hong, Zhiquan Luo, On the Linear Convergence of the Alternating Direction Method of Multipliers

  • Damek Davis, Wotao Yin, Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions

• Algorithms for Semidefinite Programming

  • Xin-Yuan Zhao, Defeng Sun, and Kim-Chuan Toh, A Newton-CG Augmented Lagrangian Method for Semidefinite Programming

  • Martin S. Andersen, Joachim Dahl, Lieven Vandenberghe, Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones

  • C. Helmberg and F. Rendl, A Spectral Bundle Method for Semidefinite Programming

  • Alexandre d'Aspremont, Noureddine El Karoui, A Stochastic Smoothing Algorithm for Semidefinite Programming

• Semidefinite Programming Relaxation

  • Emmanuel J. Candès, Yonina C. Eldar, Thomas Strohmer, and Vladislav Voroninski, Phase Retrieval via Matrix Completion

  • A. Singer and Y. Shkolnisky, Three-Dimensional Structure Determination from Common Lines in Cryo-EM by Eigenvectors and Semidefinite Programming

  • Afonso S. Bandeira, Christopher Kennedy, Amit Singer, Approximating the Little Grothendieck Problem over the Orthogonal and Unitary Groups

  • Kunal N. Chaudhury, Yuehaw Khoo, Amit Singer, Global registration of multiple point clouds using semidefinite programming

  • Bo Jiang, Shiqian Ma, Shuzhong Zhang, Tensor Principal Component Analysis via Convex Optimization