最优化：建模、算法与理论/最优化计算方法

出版信息

• 详细版： 刘浩洋, 户将, 李勇锋，文再文，最优化：建模、算法与理论, 高教出版社， ISBN：9787040550351
  H. Liu, J. Hu, Y. Li, Z. Wen, Optimization: Modeling, Algorithm and Theory (in Chinese)

• 简化版：刘浩洋, 户将, 李勇锋，文再文，最优化计算方法，高教出版社，ISBN: 978-7-04-055841-8
  H. Liu, J. Hu, Y. Li, Z. Wen, Computational Methods For Optimization (in Chinese)

本书简介

最优化计算方法是运筹学、计算数学、机器学习和数据科学与大数据技术等专业的一门核心课程。最优化问题通常需要对实际需求进行定性和定量分析，建立恰当的数学模型来描述该问题，设计合适的计算方法来寻找问题的最优解，探索研究模型和算法的理论性质，考察算法的计算性能等多方面。最优化广泛应用于科学与工程计算、数据科学、机器学习、人工智能、图像和信号处理、金融和经济、管理科学等众多领域。本书将介绍最优化的基本概念、典型案例、基本算法和理论。 通过本书的学习，掌握最优化的基本概念，最优性理论，典型的几类最优化问题（如凸优化，无约束优化，约束优化，复合优化等等）的建模或判别，相关优化问题的基本计算方法，并能熟练调用基于MATLAB或Python等语言的典型优化软件程序求解一些标准的优化问题，灵活运用所讲授的算法和理论求解一些非标准的优化问题。达到锻炼将实际问题建立合适最优化模型的能力，选择合适的现有软件包和算法的能力，遇到没有现成算法自己实现简单算法的能力。

内容简介

考虑到不同层次的需求，本教材分

• 详细版: “最优化：建模、算法与理论”

• 简化版: “最优化计算方法”
  

它们的主要区别是简化版中不涉及一些复杂的概念、详细的例子和证明等等。在第一章简要介绍最优化基本概念之后，详细版从四个方面进行讲述。

• 基础知识：第二章介绍最优化建模和算法中经常需要使用的一些基础知识，包括范数、导数、凸集、凸函数、次梯度、共轭函数等。 此外为了内容的完整性也在附录部分简要概述了一些基础知识，其中线性代数包含矩阵、特征值、广义逆、SMW公式、Schur补等，数值代数包括范数、方程组求解、矩阵分解、数值代数软件包等，概率论包含随机变量、期望、方差、条件期望、概率不等式等重要概念和结论。

• 优化建模：第三章阐述一些典型的优化建模方法，并以科学工程计算和机器学习中一些典型问题为例介绍如何建立优化模型。第四章给出了最优化问题的一些典型分类和判别技巧，如线性规划、半定规划、最小二乘问题、复合优化、矩阵优化、随机优化等等。一个实际问题根据其侧重点可以由不同的优化模型来描述，一种优化模型也可以对应很多不同的实际应用。

• 最优性理论：第五章介绍最优性理论，包括最优解的存在性和唯一性，无约束可微问题、无约束不可微问题、带约束优化问题的一阶或二阶最优性条件，对偶理论，带广义不等式（如半定规划问题）的对偶理论。

• 最优化算法：第六章介绍无约束优化算法，包括线搜索方法、梯度类算法、次梯度算法、牛顿类算法、信赖域算法、非线性最小二乘法。第七章介绍约束优化算法，包括罚函数法、增广拉格朗日函数法及其在典型凸优化问题的主问题和对偶问题上的具体应用，线性规划内点法。第八章介绍复合优化算法，包括近似点梯度法、Nesterov加速算法、近似点算法、分块坐标下降法、对偶算法、交替方向乘子法、随机优化算法。

本书主要概念基本配有详细的例子来解释。主要优化算法也都通过实际应用问题对算法细节进行详细阐述，特别是在稀疏优化和逻辑回归等等问题的典型场景下进行数值试验，给出最优性度量与迭代步数关系等数值结果，相关程序也可以在本网页下载。

本书特点

• 从优化建模和模型分类等不同侧面阐述优化问题。考虑到优化问题大多来源于实际问题，本书的详细版以一定篇幅介绍优化建模中的技术，包括压缩感知、低秩矩阵恢复、回归分析、逻辑回归、支持向量机、相位恢复、字典学习、图像处理、深度学习、强化学习等等，帮助读者理解优化问题中每一部分的具体含义。此外，本书也详细讨论了若干种典型优化问题，包括线性规划、最小二乘问题、复合优化问题、半定规划、矩阵优化问题、随机优化问题等等。着重介绍每种优化问题的特点，并列举出大量的实例。

• 系统全面地讲述了适用于大规模计算的一阶优化算法。本书除了介绍一些经典的无约束和约束优化问题的算法外，强化了增广拉格朗日函数法在凸问题中应用，特别着重讲述了带非光滑结构的复合优化问题的最优性条件和近年来发展起来的一阶优化算法及相应理论，包括近似点梯度法、Nesterov加速算法、近似点算法、分块坐标下降法、对偶算法、交替方向乘子法、随机优化算法等等。因此，本书问题和算法广泛覆盖了常用的光滑和非光滑优化，凸优化和非凸优化，线性和非线性优化，确定性优化和随机优化。

• 通过详细的应用实例和高质量代码实现强化对问题和算法的理解。本书中应用实例贯穿于各个章节中，在优化建模、优化问题举例、最优性条件、优化算法章节加入了大量实际例子来帮助读者理解相关内容。特别地，本书通过前面提到的一些重要实际应用问题对主要优化算法细节进行详细阐述，在稀疏优化和逻辑回归等问题的典型场景下进行数值试验，给出最优性度量与迭代步数关系等数值结果。

教材下载/购买信息

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

• 下载“最优化：建模、算法与理论”第二版草稿，主要增加了流形约束优化算法和半光滑牛顿算法等新内容

• 下载“最优化计算方法”第一版作者版本

• “最优化：建模、算法与理论”第一版勘误表

• “最优化计算方法”第一版勘误表

• “最优化：建模、算法与理论” 第一版出版社版本购买链接如下。出版社版本和作者版本在排版上有较大的区别。

  • 高教书城（已经可以购买）：www.hepmall.com/index.php/product-34415.html

  • 微店的地址（已经可以手机端购买）：weidian.com/item.html?itemID=4276223598

  • 京东自营链接（已经可以购买）：item.jd.com/13064530.html

  • 当当自营链接（已经可以购买）：product.dangdang.com/29185022.html

• “最优化计算方法” 第一版出版社版本购买链接如下。出版社版本和作者版本在排版上有较大的区别。

  • 高教书城（已经可以购买）：www.hepmall.com/index.php/product-35610.html

  • 微店的地址（已经可以手机端购买）：weidian.com/item.html?itemID=4388758095

  • 京东自营链接（已经可以购买）：item.jd.com/13318228.html

  • 当当自营链接（已经可以购买）：product.dangdang.com/29261079.html

• 读者调查问卷：感谢您对本书的兴趣！如果本书对您有帮助，请您帮忙反馈一些用户信息供作者参考。

• 限于作者的知识水平，书中难免有不妥和错误之处，恳请读者不吝批评和指正。
  勘误收集: 如果您发现任何不妥和错误之处，麻烦您通过此链接反馈。
  2021年6月底左右出版社将给提供反馈的老师和同学挂号信方式邮寄 “最优化计算方法”样书。

优化程序

(点击此链接访问详细代码和注释)

• 梯度类算法

• 次梯度算法

• 牛顿类算法

• 信赖域算法

• 非线性最小二乘法

• 增广拉格朗日函数法

• 近似点梯度法

• Nesterov加速算法

• 近似点算法

• 分块坐标下降法

• 对偶算法

• 交替方向乘子法

• 随机优化算法

电子教案

• 电子教案目前版本还很初略，持续更新中。
  

  • 电子教案的latex源文件目前只开放给使用本教材的任课老师，麻烦提供相关课程信息。我们会定期查看该问卷信息发送答案。
    

  • 课程任课教师请填写该链接提供课程信息
    

  • 您填写完该问卷之后请用您单位email发邮件给文再文提醒发送答案，邮件地址请见下面信息反馈。如果不是使用单位官方邮件发送，请务必说明身份信息。无法判断身份的邮件将不予回复。

• 简介，讲义下载，本节内容由邓展望协助准备

• 凸集，讲义下载，本节内容由丁思哲协助准备

• 凸函数，讲义下载，本节内容由华奕轩协助准备

• 数值代数基础，讲义下载，本节内容由张轩熙协助准备

• 优化建模，讲义下载，本节内容由华奕轩协助准备

• 典型优化问题，讲义下载，本节内容由邓展望协助准备
  北大课程版本，本节内容由邓展望协助准备
  

• 凸优化最优性理论，讲义下载，本节内容由谢中林协助准备

• 非凸优化最优性理论，讲义下载，本节内容由谢中林协助准备

• 梯度下降算法，讲义下载，本节内容由谢中林协助准备

• 次梯度，讲义下载，本节内容由朱桢源协助准备

• 次梯度算法，讲义下载，本节内容由朱桢源协助准备
  次梯度和次梯度算法，讲义下载，本节内容由朱桢源协助准备

• 牛顿类算法，讲义下载，本节内容由陈乐恒，丁思哲协助准备

• 信赖域算法，讲义下载，本节内容由邓展望协助准备
  牛顿法和信赖域法，讲义下载，本节内容由陈乐恒，丁思哲，邓展望协助准备

• 拟牛顿算法，讲义下载，本节内容由丁思哲协助准备

• 非线性最小二乘问题，讲义下载，本节内容由张轩熙协助准备

• 罚函数法，讲义下载，本节内容由陈乐恒，邓展望协助准备

• 增广拉格朗日函数法，讲义下载，本节内容由陈乐恒，丁思哲协助准备
  简略版本讲义下载

• 线性规划内点法，讲义下载，本节内容由谢中林，张轩熙协助准备

• 近似点算子，讲义下载，本节内容由陈乐恒，朱桢源协助准备

• 近似点梯度算法，讲义下载，本节内容由陈乐恒，朱桢源协助准备

• Nesterov 加速算法，讲义下载，本节内容由李煦恒协助准备

• 近似点算法，本节内容由陈乐恒，邓展望协助准备

• 分块坐标下降法，讲义下载，本节内容由朱桢源协助准备
  简略版本讲义下载

• 对偶算法，讲义下载，本节内容由朱桢源协助准备

• 交替方向乘子法，讲义下载，本节内容由华奕轩协助准备

• 随机优化算法，讲义下载，本节内容由李煦恒协助准备

• 半光滑牛顿算法，讲义下载，本节内容由李勇锋，邓展望协助准备
  简略版本讲义下载

习题答案

• 《最优化：建模、算法与理论》和《最优化计算方法》目前已经准备好答案草稿。

• 为了避免学生直接抄袭答案，完整版教材答案目前只开放给使用本教材的任课老师，麻烦提供相关课程信息。我们会定期查看该问卷信息发送答案。
  

  • 课程任课教师请填写该链接提供课程信息
    

  • 您填写完该问卷之后请用您单位官方email发邮件给文再文提醒发送答案，邮件地址请见下面信息反馈。

  • 最近出现学生冒充任课老师领答案现象，也有同一个学校同一门课多人认领答案。有些任课老师的信息也无法通过网络上公开信息确认。因此请使用学校官方email地址，并且邮件内容最好能确认您的信息，比如有您姓名的院系人员介绍网页链接等等。

• 针对同学们的需求，提供以下参考答案简化版本。

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

  • 下载“最优化计算方法”答案

考试练习题

• 2017年《凸优化》期中考试题目(三节课)

• 2018年《凸优化》期中考试题目(三节课)

• 2019年《凸优化》期中考试题目(两节课)

• 2020年《凸优化》期中考试题目(两节课)

• 2022年《最优化方法》期中考试题目(两节课)

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

课程项目

• 以下课程项目一些具体要求等信息请参考相应年份的课程网页

• 2014-2019年《凸优化》程序大作业题: LASSO, 测试接口程序, 作业提交指南

• 2020-2022年《凸优化》程序大作业题: group LASSO, 作业提交指南

• 2014年《凸优化》期末课程项目: Projection to Doubly Stochastic Matrices

• 2016年《凸优化》期末课程项目: Semismooth Newton Algorithms for LP

• 2017-2018年《凸优化》期末课程项目: Semismooth Newton Algorithms for LP, Optimal Transport

• 2019年《凸优化》期末课程项目: Optimal Transport, Algorithms and analysis for shallow neural network

• 2020-2021年《凸优化》期末课程项目: Algorithms and analysis for shallow neural network

• 2014-2019年《大数据分析中算法》程序大作业题: L1 minimization, Sparse Inverse Covariance Estimation

• 2020-2022年《大数据分析中算法》程序大作业题: L1 minimization, Low-rank Recovery

• 2020-2021年《大数据分析中算法》期末课程项目: Exploiting fast algorithms for solving networking resource allocation problems

• 2022年《大数据分析中算法》期末课程项目: 国铁集团列车排班

• 2021-2022年《大数据分析中算法》期末课程项目: Software implementaion for the proximal gradient methods

信息反馈

限于作者的知识水平，书中难免有不妥和错误之处，恳请读者不吝批评和指正。

• 文再文, wenzw at pku dot edu dot cn

• 刘浩洋, liuhaoyang at pku dot edu dot cn

• 户将, jianghu at pku dot edu dot cn

• 李勇锋, Yongfengli at pku dot edu dot cn

课程信息

• 凸优化 (2020年秋季)

• 大数据分析中的算法 (2020年春季)