最优化方法 (2026年秋季)

• 本课程考核包括平时作业和程序，期中考试和期末考试

• 课程代码：00130630 (数院本科)，00100887 (数院研究生)

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

• 助教信息：王梓琛，袁浩然

• 上课地点: 理教106

• 上课时间：

  • 每周周一1~2节(8:00am - 9:50am)，单周周四1~2节(8:00am - 9:50am)

  • 老师答疑时间：单独和老师联系或者每次课后

  • 助教答疑时间：待定

  • 北京大学2026—2027学年校历

  • 10月1日至7日国庆节放假，全校停课

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

• 教材：

  • “最优化：建模、算法与理论”，刘浩洋, 户将, 李勇锋，文再文

  • 最优化方法 (2025年秋季)

  • 最优化方法 (2024年秋季)

• 参考材料：

  • “Introductory Lectures on Convex Optimization. A Basic Course”, Yu. Nesterov, (2004)

  • “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月7日，课程简介，最优化介绍
    讲义下载，本节内容由邓展望协助准备
    demo: sparse_l1_example.m

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

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

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

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

  • 第4周，9月28日，线性规划，二次锥规划，半定规划简介，对偶理论: 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月5日，国庆节放假，全校停课
    

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

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

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

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

  • 第9周，11月5日，期中考试（考场待定）

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

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

  • 第11周，11月19日， 近似点梯度法的构造和分析，条件梯度法, inertial proximal method
    讲义下载，本节内容由陈乐恒，朱桢源协助准备
    “Proximal Algorithms”, N. Parikh and S. Boyd, Foundations and Trends in Optimization, 1(3):123-231, 2014.
    条件梯度法参考： 王奇超,文再文,蓝光辉,袁亚湘, 优化算法复杂度分析简介, (paper)
    

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

  • 第13周，11月30日，罚函数法和增广拉格朗日函数法
    讲义下载，本节内容由陈乐恒，丁思哲，邓展望协助准备
    K. Deng, R. Wang, Z. Zhu, J. Zhang, Z. Wen, Augmented Lagrangian Methods: A Survey of Recent Advances, SIAM Review

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

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

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

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

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

• 成绩评定
  

  • 迟交一天(24小时）打折10%， 不接受晚交4天的作业和项目

  • 每一周或者两周有少量作业，包括习题和程序： 40%

  • 期中闭卷考试：30%.

  • 期末闭卷考试： 30%

  • 作业要求：i) 计算题要求写出必要的推算步骤，证明题要写出关键推理和论证。数值试验题应该同时提交书面报告和程序，其中书面报告有详细的推导和数值结果及分析。 ii) 可以同学间讨论或者找助教答疑，但不允许在讨论中直接抄袭，应该过后自己独立完成。 iii) 严禁从其他学生，从互联网，从往年的答案，其它课程等等任何途径直接抄袭。iv) 如果有讨论或从其它任何途径取得帮助，请列出来源。

• 平时作业 （具体内容会持续更新，根据课程情况调整）

  • 下面习题选自教材：“最优化：建模、算法与理论”，刘浩洋, 户将, 李勇锋，文再文，大部分习题有参考答案

    • 下载“最优化：建模、算法与理论”第二版作者版本

    • 下载“最优化：建模、算法与理论”答案

  • 作业一: 习题1.4, 2.7, 交作业时间：9月14日课堂上交（上课前）。

  • 作业二: 习题2.8, 例题2.9, 交作业时间：9月21日课堂上交（上课前）。

  • 作业三: 习题4.9, 4.12, 交作业时间：9月28日课堂上交（上课前）。

  • 作业四: 习题5.3, 写出习题4.12中半定规划的对偶问题，以及对偶的对偶问题, 交作业时间：10月12日课堂上交（上课前）。

  • 作业五: 习题5.10, 5.14, 交作业时间：10月19日课堂上交（上课前）。

  • 作业六: 最优化练习题2, 9, 交作业时间：10月26日课堂上交（上课前）。

  • 作业七: 推论6.2, 习题6.4, 交作业时间：11月2日课堂上交（上课前）。

  • 作业八: 习题6.6, 最优化练习题19, 交作业时间：11月9日课堂上交（上课前）。

  • 作业九: 最优化练习题11, 16, 交作业时间：11月16日课堂上交（上课前）。

  • 作业十: 习题8.1, 8.3(b) (c), 交作业时间：11月23日课堂上交（上课前）。

  • 作业十一: 习题8.6, 最优化练习题20(a)-(e), 交作业时间：11月30日课堂上交（上课前）。

  • 作业十二: 习题8.16, 最优化练习题20, 交作业时间：12月21日课堂上交（上课前）。

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

    • 11月2日: 1, 2

    • 11月9日: 3 (a), (b)

    • 11月30日: 3 (d), (e)

    • 12月7日: 3 (f)

    • 12月14日: 3 (g), (h)

    • 其它题选做

    • 程序作业提交指南

    • 教材配套程序

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

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

期中考试

• 闭卷考试：第9周，11月5日（考场待定）

• 考试范围：教材第2，4，5章课上讲过的相关内容，包括但可能不限于以下典型内容。

  • 凸集的定义和判断，对偶锥的定义和推导

  • 凸函数的定义和不同条件下的判断

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

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

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

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

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

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

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

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

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

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

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

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

期末考试

• 最优化练习题，持续更新

• 闭卷考试：2027年1月4日上午（具体时间和考场待定）

• 考试范围：教材第6，7，8章课上讲过的相关内容，包括但可能不限于以下典型内容。

  • 线搜索条件、线搜索回退法

  • 梯度下降算法、一般凸函数固定步长情形下复杂度分析、强凸函数收敛性分析、Barzilar-Borwein方法

  • 次梯度定义和计算、次梯度算法、典型步长的取法及其复杂度分析

  • 牛顿法及其收敛性分析、拟牛顿公式、有限内存拟牛顿法(L-BFGS)、信赖域算法、信赖域子问题最优性条件及其求解算法

  • 二次罚函数法、增广拉格朗日函数的构造、增广拉格朗日函数算法（乘子的更新格式）

  • 近似点算子(常见函数的近似点的计算)、近似点梯度法、复杂度分析

  • Nesterov加速算法、复杂度分析

  • 交替方向乘子法(ADMM)：拆分方式的选择、子问题的构造、典型问题的ADMM、

  • 对偶问题推导(利用共轭函数)、对偶梯度法、对偶近似点梯度法、min-max (saddle point) 问题推导、PDHG和CP算法

  • 分块坐标下降法(BCD)：变量分块方式和子问题的构造、非凸情形近似点算子、KL性质、收敛性证明思路

• 2024年期末考试题目(两节课)

智能数学推理引擎ReasLab

• 智能数学推理引擎ReasLab网址: https://reaslab.io
  ReasLab 是面向教育、科研与复杂决策场景的一站式智能数学推理引擎，致力于突破数学和应用研究中手工作业传统模式，构建从专家直觉驱动走向可计算、可验证的智能化基础设施。针对数学建模、算法设计与定理证明等关键环节长期相互割裂、深度依赖人工经验的问题，ReasLab 以大语言模型为基座，采用多智能体架构，融合数学模型库、算法库与定理知识库，将模型构建、算法设计、计算求解、自然语言和形式化证明及 Markdown/LaTeX 报告生成等能力纳入统一环境，实现数学对象在不同表示层次与任务环节之间的贯通协同。依托云计算，用户无需安装即可在线使用。ReasLab 已为上千位用户提供形式化、优化建模、数学建模竞赛和科学研究等支持。

解决一些开放问题

• 挑选一些与优化相关的开放问题

• 利用ReasLab，或者大模型网页端、以及QED、Rethlas等证明智能体尝试解决

华为难题揭榜

• 登录黄大年茶思屋: https://www.chaspark.com, 查看难题榜单。

• 选择一些感兴趣的问题，在ReasLab里尝试解决。

• 有了初步方案之后请与老师沟通，联系华为专家讨论

数学形式化计划

• 帮助审核ReasBook中已经形式化的书籍

• 帮助审核ReasAtlas中已经整理出来的数学百科全书章节