凸优化 (2016年秋季)

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

• 课程代码：00102906 (研究生），00136660 (本科）

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

• 助教信息： 户将， jianghu@pku.edu.cn

• 上课地点： 三教505

• 上课时间：

  • 每周周一7~9节, 15:10pm - 18:00pm

  • 答疑时间：单独和老师联系或者每次课后18:00pm-18:30pm

  • 北京大学校历

• 课程微信群（下面二维码9月18日失效）

• 凸优化参考材料：

  • “Convex optimization”, Stephen Boyd and Lieven Vandenberghe

  • 凸优化 (2014年秋季)

  • 凸优化 (2015年秋季)

• 参考材料：

  • “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日， 近似点梯度法，近似点梯度法的构造和分析
    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.

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

  • 第11周，11月21日，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
    参考文献： Amir Beck, Marc Teboulle, A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems

  • 第12周，11月28日，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

  • 第13周，12月5日， 交替方向乘子法及其变形，交替方向乘子法的构造, Distributed ADMM
    Prof. Wotao Yin's lecture notes on ADMM
    

  • 第14周，12月12日， 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
    

  • 第15周，12月19日，Barrier functions, Path-following methods
    Prof. Lieven Vandenberghe's lecture notes on barrier functions
    Prof. Lieven Vandenberghe's lecture notes on path following methods
    

  • 第16周，12月26日，Primal-dual interior-point methods
    Prof. Lieven Vandenberghe's lecture notes on primal-dual methods
    

• 成绩评定
  

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

  • 课程项目： 70%

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

• 作业

  • 作业一: 教材 “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 (选做)

• 课程项目

  • 课程项目一: 请见下面课程项目一细节。交作业日期：2016年12月26日晚12点前（不接受晚交报告）

  • 课程项目二: project-opt-2016-fall.pdf 交作业时间： 2017年1月9日晚上12点前。

课程项目一细节

• 分组: 自由组合一般2至3人一组，可以一个人

• 选题

  • 大致分为文献综述，模型项目，算法项目，理论问题

  • 从课程项目文献列表中选一篇参考文献或者跟文老师沟通

  • 文献综述： 挑选一篇感兴趣的文献，写文献综述

  • 模型项目: 挑选你感兴趣的应用问题，探索用最优化算法或数值代数算法解决。

  • 算法项目: 挑选一个或者一类问题，提出新的算法或者已有算法的变形

  • 理论问题： 分析一些模型或算法的理论性质

• 评分准则

  • 评分由三部分组成： 中期报告，书面报告

  • 书面报告： 每一组提交一份ppt （课堂报告文件）和一份读书报告 (包括latex源文件 )。如果文章中有数值算例，请写程序复制数值实验结果。

• 重要日期和提交内容：

  • 分组情况: 请于9月26日前填写调查问卷，需提供的信息： 姓名，学号，文章或项目题目

  • 课程项目分组情况

  • 中期报告请于10月31日前发email给助教 (pkuopt@163.com, wendouble@gmail.com)
    中期报告不超过3页纸（单面）。需要描述你们组的选题，已经完成的工作，你们将要做哪些事情
    提交的文件名为 “proj1rep1-name1-name2.pdf”. 比如如果成员为Pengyu Qian 和 Junzi Zhang，则文件名为 proj1rep1-PengyuQian-JunziZhang.pdf

  • 2016年12月26日晚12点（不接受晚交报告），课堂报告文件和书面报告 (包括latex源文件，程序等等打包发email给助教 (pkuopt@163.com, wendouble@gmail.com)。
    提交的文件请全部打包，文件名为 “proj1-name1-name2.zip”. 比如如果成员为Pengyu Qian 和 Junzi Zhang，则文件名为 proj1-PengyuQian-JunziZhang.zip

课程项目文献

• Programming related

  • J. Poulson, B. Marker, R. van de Geijn, J. Hammond, and N. Romero (2013). Elemental: A new framework for distributed memory dense matrix computations, ACM Transactions on Mathematical Software. Implement some optimization algorithms based on elemental

  • Solve one practical application based on Google's Tensorflow

• Algorithms for Convex Optimization Problems

  • John Duchi, Elad Hazan, Yoram Singer, Adaptive subgradient methods for online learning and stochastic optimization

  • Diederik Kingma, Jimmy Ba, Adam: A Method for Stochastic Optimization

  • Peng Xu, Jiyan Yang, Farbod Roosta-Khorasani, Christopher Re, Michael W. Mahoney, Sub-sampled Newton Methods with Non-uniform Sampling

  • Haishan Ye, Luo Luo, Zhihua Zhang, Revisiting Sub-sampled Newton Methods

  • Stephen Tu, Rebecca Roelofs, Shivaram Venkataraman, Benjamin Recht, Large Scale Kernel Learning using Block Coordinate Descent

  • Karol Gregor and Yann LeCun, Learning Fast Approximations of Sparse Coding

  • Ruxin Wang and Dacheng Tao, Non-Local Auto-Encoder With Collaborative Stabilization for Image Restoration

  • Gavin Taylor, Ryan Burmeister, Zheng Xu, Bharat Singh, Ankit Patel, Tom Goldstein, Training Neural NetworksWithout Gradients: A Scalable ADMM Approach

  • Chris J. Li, Mengdi Wang, Han Liu, Tong Zhang, Near-Optimal Stochastic Approximation for Online Principal Component Estimation

  • Rong Ge, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, Aaron Sidford, Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis

  • Robert M. Freund, Paul Grigas, New analysis and results for the Frank–Wolfe method

  • Deanna Needell, Nathan Srebro, Rachel Ward, Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm

  • A. Y. Aravkin, J. V. Burke, D. Drusvyatskiy, M. P. Friedlander, S. Roy, Level-set methods for convex optimization

  • Stephen J. Wright, Coordinate descent algorithms

  • Zirui Zhou, Anthony Man-Cho So. A Unified Approach to Error Bounds for Structured Convex Optimization Problems

  • Ji Liu, Stephen J Wright, Asynchronous stochastic coordinate descent: Parallelism and convergence properties

  • Guanghui Lan, Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization

  • Ruoyu Sun, Zhi-Quan Luo, Guaranteed Matrix Completion via Non-convex Factorization

  • Rong Ge, Furong Huang, Chi Jin, Yang Yuan, Escaping From Saddle Points  —  Online Stochastic Gradient for Tensor Decomposition

  • Rong Ge, James Zou, Intersecting Faces: Non-negative Matrix Factorization With New Guarantees

  • Rong Ge, Jason D. Lee, Tengyu Ma, Matrix Completion has No Spurious Local Minimum

  • Ju Sun, Qing Qu, John Wright, Complete Dictionary Recovery over the Sphere

  • Ju Sun, Qing Qu, John Wright, A Geometric Analysis of Phase Retrieval

  • Nicolas Boumal, P.-A. Absil, Coralia Cartis, Global rates of convergence for nonconvex optimization on manifolds

• Algorithms for Semidefinite Programming

  • Liuqin Yang, Defeng Sun, Kim-Chuan Toh, SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints

  • Nicolas Boumal, A Riemannian low-rank method for optimization over semidefinite matrices with block diagonal constraints

  • Manuel Gräf and Ralf Hielscher, Fast Global Optimization on the Torus, the Sphere, and the Rotation Group

  • 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

  • M. P. Friedlander, I. Macedo, and T. K. Pong, Gauge optimization and duality

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

  • Chao Ding, Defeng Sun, Kim-Chuan Toh, An introduction to a class of matrix cone programming

  • Chao Ding, Defeng Sun, Jie Sun, Kim-Chuan Toh, Spectral Operators of Matrices

  • 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

• see the list under “Papers / Topics, grouped for presentation”