凸优化 (2015年秋季)

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

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

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

• 助教信息： 王超, 1401110035@pku.edu.cn

• 上课地点： 二教501

• 上课时间： 每周周四7~9节, 15:10pm - 18:00pm

• 凸优化参考材料：

  • “Convex optimization”, Stephen Boyd and Lieven Vandenberghe

  • 凸优化 (2014年秋季)

• 参考材料：

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

• 课程信息 （大致安排）

  • 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月17日，课程简介，凸优化问题介绍
    lecture notes on introduction, lecture notes on convex sets, demo: sparse_l1_example.m

  • 第2周，9月24日，凸集，凸集和凸函数的定义和判别
    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周，10月1日，国庆节放假 （补课日期待定）
    

  • 第4周，10月8日，数值代数基础，向量，矩阵，范数，子空间，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
    

  • 第5周，10月15日，线性规划，二次锥规划，半定规划简介: 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月22日，对偶理论, 凸优化最优性条件 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月29日，梯度法和线搜索算法，最速下降法及其复杂度分析，线搜索算法，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月5日， 次梯度及次梯度算法, smoothing
    Prof. Lieven Vandenberghe's lecture notes on subgradient
    Prof. Lieven Vandenberghe's lecture notes on subgradient method

  • 第9周，11月12日， 近似点梯度法，近似点梯度法的构造和分析
    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月19日， 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月26日，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
    参考文献： Amir Beck, Marc Teboulle, A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems

  • 第12周，12月3日，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月10日， 交替方向乘子法及其变形，交替方向乘子法的构造, Distributed ADMM
    Prof. Wotao Yin's lecture notes on ADMM
    

  • 第14周，12月17日， Block Coordinate Descent Methods
    Prof. Wotao Yin and Yangyang Xu's lecture notes on BCD
    

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

  • 第15周，12月26日下午3点－6点，课程报告， 理科1号楼1114 教室
    

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

• 成绩评定
  

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

  • 课程项目： 65%

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

  • 准备课件： 5%

• 准备课件

  • 请在如下网页提交选择

  • 下载 latex模版

  • 问卷截止日期9月24日

  • 根据选择调整后的课件准备任务列表

  • 准备好的slides请于10月15日前发给助教 (pkuopt@163.com, wendouble@gmail.com)

• 作业

  • 作业一: 教材 “Convex optimization”，习题：2.9, 2.15 (a), (b), (c), 2.33, 3.11, 3.17, 3.20, 3.35 交作业时间： 10月8日课堂上交（上课前）。

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

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

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

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

• 课程项目

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

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

课程项目一细节

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

• 选题

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

  • 从课程项目文献列表中选一篇参考文献择

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

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

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

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

• 评分准则

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

  • 课程课堂报告： 准备15分钟报告 + 5分钟提问。 每个组员均需讲差不多长度的时间。成绩评定： 50% 其中小组之间相互评定和教师意见各 50% .
    小组之间相互评定，评分为1-10。 请每组填写presentation_evaluation.xlsx发给助教 (pkuopt@163.com, wendouble@gmail.com).
    每组负责收集自己组的评分。如果B组课堂上没有给A组评分，则A组收集B组的评分填写为10*（请标注*号），而B组计算平均分后将减1分，扣完为止。
    

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

• 重要日期和提交内容：

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

  • 课程项目分组情况

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

  • 11月5日前选择课堂报告的时间

  • 12月3日至12月31日，课堂报告
    分组情况及时间安排请查看此链接 presentation_schedule.xlsx

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

课程项目文献

• Programming related

  • Parallel implementation of “Zaiwen Wen, Yin Zhang, Block algorithms with augmented Rayleigh-Ritz projections for large-scale eigenpair computation”

  • 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

  • Implement some optimization algorithms based on the Julia Language

• Algorithms for Convex Optimization Problems

  • Stephen J. Wright, Coordinate descent algorithms

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

  • Richard H. Byrd, Jorge Nocedal, Figen Oztoprak, An inexact successive quadratic approximation method for L-1 regularized optimization

  • Zhimin Peng, Yangyang Xu, Ming Yan, Wotao Yin, ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates

  • Yuyuan Ouyang, Yunmei Chen, Guanghui Lan, and Eduardo Pasiliao, An Accelerated Linearized Alternating Direction Method of Multipliers

  • Saeed Ghadimi, Guanghui Lan, Hongchao Zhang, Generalized Uniformly Optimal Methods for Nonlinear Programming

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

  • Joel A Tropp, The Expected Norm of a Sum of Independent Random Matrices: An Elementary Approach

  • Joel A Tropp, An introduction to matrix concentration inequalities

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

  • Chow, Shui-Nee; Yang, Tzi-Sheng; Zhou, Hao-Min, Global Optimizations by Intermittent Diffusion

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

• Algorithms for Semidefinite Programming

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

  • M. P. Friedlander and I. Macedo, Low-rank spectral optimization

  • 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