课程代码：00130630 (数院本科)，00100887 (数院研究生)，08617040 (工学院：优化方法概论)

教师信息： 文再文，wenzw at pku dot edu dot cn

助教信息：陈一鸣，谢中林

上课地点: 理教306

线上教学方式:

请从教学网下面课程里进入classin课堂: 22231-001-00130630-1306182243-3: 最优化方法(22-23学年第1学期本研合上)

为了避免可能出现的意外情况，同时在 腾讯会议 同步，点击此链接进入会议室，会议号: 269-960-161

“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

课程信息 （大致安排）

第1周，9月6日，课程简介，最优化介绍
讲义下载，本节内容由邓展望协助准备
demo: sparse_l1_example.m

第1周，9月8日，凸集的定义和判别
讲义下载，本节内容由丁思哲协助准备
教材5.4.2 节：适当锥和广义不等式，对偶锥
read chapter 2 in the book “Convex optimization”.

第2周，9月15日，凸函数的定义和判别
讲义下载，本节内容由华奕轩协助准备
read chapter 3 in the book “Convex optimization”.

第3周，9月20日，典型的凸优化问题
讲义下载，本节内容由邓展望协助准备
read chapter 4 in in the book “Convex optimization”
Minimizing the sum of the k largest functions in linear time

第3周，9月22日，典型的凸优化问题

第4周，9月29日，线性规划，二次锥规划，半定规划简介，对偶理论: 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

第5周，10月4日，对偶理论, 凸优化最优性条件
讲义下载，本节内容由谢中林协助准备
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

第5周，10月6日， 非凸优化最优性条件
讲义下载，本节内容由谢中林协助准备

第6周，10月13日，梯度法和线搜索算法，最速下降法及其复杂度分析，线搜索算法，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

第7周，10月18日，梯度法和线搜索算法，最速下降法及其复杂度分析，线搜索算法，Barzilar-Borwein 方法

第7周，10月20日，次梯度和次梯度算法
讲义下载，本节内容由朱桢源协助准备

第8周，10月27日，牛顿法、信赖域算法
讲义下载，本节内容由陈乐恒，丁思哲，邓展望协助准备

第9周，11月1日，期中考试, 理教306和理教209

第9周，11月3日，拟牛顿法、非线性最小二乘算法
讲义下载，本节内容由丁思哲，张轩熙协助准备

第10周，11月10日，近似点算子的构造和性质
讲义下载，本节内容由陈乐恒，朱桢源协助准备

第11周，11月15日， 近似点梯度法的构造和分析，条件梯度法, 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

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

第12周，11月24日，罚函数法和增广拉格朗日函数法
讲义下载，本节内容由陈乐恒，丁思哲，邓展望协助准备

第13周，11月29日，交替方向乘子法
讲义下载，本节内容由华奕轩协助准备
“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

第13周，12月1日， 交替方向乘子法
近似点算法, 讲义下载，本节内容由陈乐恒，邓展望协助准备

第14周，12月8日，对偶算法
讲义下载，本节内容由朱桢源协助准备

第15周，12月13日， Block Coordinate Descent Methods
讲义下载，本节内容由朱桢源协助准备
Jérôme Bolte, Shoham Sabach, Marc Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems

第15周，12月15日， semi-smooth Newton methods
讲义下载，本节内容由李勇锋，邓展望协助准备

期末考试：12月29日上午8:30-10:30， 腾讯会议号：330-252-264

作业九: 习题： 8.6, 8.16, 交作业时间： 12月13日课堂上交（上课前）。

程序作业: homework5g.pdf , 完整报告和程序提交时间12月22日 ，但建议按如下时间节点完成任务:

11月10日: 1, 2

11月15日: 3 (a)

11月29日: 3 (d), (e)

12月8日: 3 (f)

12月15日: 3 (g), (h)

其它题选做

程序作业提交指南

教材配套程序

后继作业文件和上机报告可以包含之前提交的内容，建议按时间节点完成

请将完整报告和程序等等打包（文件名为 “gl-StudentID-date.zip”）发email给助教 (pkuopt@163.com)

凸优化问题定义和（线性规划、二次锥规划、半定规划）判断，能写出锥的具体形式。

弱对偶原理，强对偶，对偶理论，推导对偶问题，或者对偶的对偶问题。二次约束二次规划(QCQP)和简单整数规划的对偶，半定规划松弛的推导。Farkas 引理，利用线性规划强对偶证明Farkas 引理。

简单优化问题显式解的推导（包括但不限于利用最优性条件推导）

凸优化问题(一阶)必要和充分最优条件。必要条件注意验证Slater条件。

可微非凸优化问题一阶必要最优条件，二阶必要和充分最优条件。必要条件注意验证约束规范(LICQ, MFCQ)

2017年期中考试题目(三节课)

2018年期中考试题目(三节课)

2019年期中考试题目(两节课)

2020年期中考试题目(两节课)

2022年《最优化方法》期末练习题

可以选做课题一或者课题二或者闭卷考试。需独立完成。

闭卷考试：12月29日上午8:30-10:30， 腾讯会议号：330-252-264

课题一：期末大作业
下载期末大作业题

课题二：两层神经网络优化问题的算法和理论分析
课题二的基本要求点击此文件 。

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年12月30日晚12点（不接受晚交报告），书面报告 (包括latex源文件，程序等等打包发email给助教 (pkuopt@163.com)。
提交的文件请全部打包，文件名为见具体要求文件。

请在书面报告声明：本项目文件的主要内容没有用在其它课程做为课程项目或作业提交。