Convex Optimization

Siliang Zhang (slzhang at ecnu dot edu dot cn)

Spring 2022

Spring 2023

教材

Convex Optimization by S. Boyd and L. Vandenberghe, Cambridge University Press, 2004

参考材料

课程简介

近些年来,机器学习与计算统计学发展迅速,几乎其中的每个问题都可被转化成特定约束下某些函数的优化问题。但不是所有的机器学习问题都可被很好的解决,这意味着没有一般性的方法解决优化问题。然而,很多我们感兴趣的问题可被看作具有独特性质的优化问题,这些特性包含凸性、光滑、稀疏、可分性等,这些特性使得标准化的高效求解成为可能。

本课程旨在提供研究生阶段优化问题的背景知识,包括基本特性和这些特性在优化中所起作用。更广泛地,学生将学习利用这些特性的经典优化算法。课程将重点讨论凸优化问题(根据课程进度也会涉及少部分非凸优化内容)。本课程的教学中将重新审视机器学习和统计学中很多重要的应用问题。基于本课程的学习,学生将能够从整体的理解优化问题,并将其思想与技巧应用到机器学习或统计为背景的具体问题中。本课程面向统计、金融、工程、心理测量等研究生。

In recent years, machine learning and computational statistics have developed rapidly, and almost every problem in it can be formulated as an optimization problem of some functions under certain constraints. Obviously, not all machine learning problems can be solved well, which means that we cannot solve the corresponding optimization problems in general. However, many interesting problems in statistics and machine learning can be viewed as optimization problems with unique properties, such as convexity, smoothness, sparsity, separability, etc. It is these properties that permitting standardized and efficient solutions.

This course is designed to provide students with a background in optimization problems at the graduate-level, including the fundamental properties and the role these properties play in optimization, and more generally, students will learn classical algorithms that exploit these properties. The course will focus on convex optimization problems (additionally, a small amount of non-convex optimization will be covered depending on the course progresses). Many important application problems in machine learning and statistics will be revisited during the teaching. Upon completing of this course, students will be able to understand optimization problems as a whole and apply the key ideas and techniques to specific problems with machine learning or statistics background. This course is aimed at graduated students in statistics, finance, management, psychometrics etc.

课程目标

课程内容

章节 主题
第一章 凸优化基本概念与理论 Intro, 凸集与凸函数 1-2
第一章 凸优化基本概念与理论 优化基本概念 2
第一章 凸优化基本概念与理论 ❖典型问题形式❖ 3
第二章 算法1:一阶方法 梯度下降(GD) 4
第二章 算法1:一阶方法 次梯度与次梯度方法 5
第二章 算法1:一阶方法 ❖近段梯度下降及加速❖ 6
第二章 算法1:一阶方法 随机梯度下降(SGD) 6
第三章 对偶与最优性 线性规划中的对偶性 7
第三章 对偶与最优性 ❖一般规划问题中的对偶性❖ 8
第三章 对偶与最优性 ❖KKT条件❖ 9
第三章 对偶与最优性 对偶性应用 9
第四章 算法2:二阶方法 牛顿法 10
第四章 算法2:二阶方法 内点方法 11
高级优化主题选讲 拟牛顿法、对偶分解、ADMM、非凸优化等 12