机器学习必知必会：凸优化_皇冠-皇冠体育少儿专业培训机构

机器学习必知必会：凸优化

发布时间：2024-04-22 15:04:33

凸优化问题（OPT，convex optimization problem）指定义在凸集中的凸函数最优化的问题。尽管凸优化的条件比较苛刻，但仍然在机器学习领域有十分广泛的应用。

凸优化问题的局部最优解就是全局最优解
很多非凸问题都可以被等价转化为凸优化问题或者被近似为凸优化问题（例如拉格朗日对偶问题）
凸优化问题的研究较为成熟，当一个具体被归为一个凸优化问题，基本可以确定该问题是可被求解的

$C$ 是凸集，如果对于任意的 $x,y\\in C$ 和任意的 $\ heta \\in \\mathbb{R}$ 满足 $0\\leq \ heta \\leq 1$ 时， $\ heta x + (1-\ heta)y \\in C$ 恒成立

直观来说，任取一个集合中的两点练成一条线段，如果这条线段完全落在该集合中，那么这个集合就是凸集。

定义在 $\\mathbb{R}^n \\rightarrow \\mathbb{R}$ 上的函数 $f$ 是凸函数，如果它的定义域 $\\mathbb{D}(f)$ 是一个凸集且对任意的 $x,y\\in \\mathbb{D}$ 和 $0\\leq \ heta \\leq 1$ , $f(\ heta x +(1-\ heta y)) \\leq \ heta f(x) + (1-\ heta)f(y)$ 恒成立

假设定义在 $\\mathbb{R}^n \\rightarrow \\mathbb{R}$ 上的函数ff可微（即对于所有 $x\\in \\mathbb{D}(f)$ ，梯度 $\ riangledown f(x)$ 均存在）。则函数 $f$ 是凸函数当且仅当函数定义域 $\\mathbb{D}(f)$ 是一个凸集，且对于所有 $x,y\\in \\mathbb{D}(f)$ 均满足：

$f(y) \\geq f(x)+\ riangledown f(x)^T(y-x)$

一阶充要条件从几何意义上讲，即定义域内所有函数值都大于等于该点的一阶近似。

记函数的一阶导数和二阶导数分别为 $g$ 和 $H$ ：

$g=\ riangledown f=\\begin{bmatrix}\\frac{\\partial f}{\\partial x_1}\\\\ \\frac{\\partial f}{\\partial x_2}\\\\ \\vdots \\\\ \\frac{\\partial f}{\\partial x_n}\\end{bmatrix}\\quad H=\ riangledown^2f=\\begin{bmatrix}\\frac{\\partial^2f}{\\partial x_1^2}& \\frac{\\partial^2f}{\\partial x_1 \\partial x_2}& \\cdots & \\frac{\\partial^2f}{\\partial x_1 \\partial x_n}\\\\ \\frac{\\partial^2f}{\\partial x_2 \\partial x_1}& \\frac{\\partial^2f}{\\partial x_2^2}& \\cdots & \\frac{\\partial^2f}{\\partial x_2 \\partial x_n}\\\\ \\vdots & \\vdots & \\ddots & \\vdots\\\\ \\frac{\\partial^2f}{\\partial x_n \\partial x_1}& \\frac{\\partial^2f}{\\partial x_n \\partial x_2}& \\cdots & \\frac{\\partial^2f}{\\partial x_n^2}\\end{bmatrix}$

假设定义在 $\\mathbb{R}^n \\rightarrow \\mathbb{R}$ 上的函数 $f$ 二阶可微（即对于所有 $x\\in \\mathbb{D}(f)$ ，海森矩阵 $\ riangledown^2 f(x)$ 均存在）。则函数 $f$ 是凸函数当且仅当函数定义域 $\\mathbb{D}(f)$ 是一个凸集，且对于所有 $x\\in \\mathbb{D}(f)$ 均满足：

$\ riangledown^2f(x) \\succeq 0$

注意：这里的 $\\succeq$ 表示的是半正定。

正定矩阵的概念是从正定二次型引入的，对称矩阵 $A$ 为正定的充要条件即该矩阵的特征值全为正数。

为方便理解正定/半正定矩阵，我们引入二次型 $f(x)=x^TAx$ ，对于含有 $n$ 个变量的二次齐次函数，我们可以一般化地写为：

$f(x_1,x_2,...,x_n)=a_{11}x_1^2 + a_{22}x_2^2+...+a_{nn}x_n^2+2a_{12}x_1x_2+...+2a_{n-1,n}x_{n-1}x_{n}$

$f(x_1,x_2,...,x_n)=\\sum_{i=1}^{n}a_{ii}x_i^2 + 2\\sum_{i=1}^{n}\\sum_{j=1}^{n}a_{ij}x_ix_j$

同时，对于所有的二次齐次式我们都可以写成矩阵形式：

$f(x_1,x_2,...,x_n)=x^TAx$

如果对任意的 $x\ eq 0$ 均有 $f(x) > 0$ ，则称 $f(x)$ 为正定二次型，同时称 $A$ 为正定矩阵。

因为对于任意的二次型，我们都能将其写为矩阵形式，且矩阵 $A$ 的形式为：
$\\begin{bmatrix}a_{11}& a_{12}& \\cdots & a_{1n}\\\\ a_{21}& a_{22}& \\cdots & a_{2n}\\\\ \\vdots & \\vdots & \\ddots & \\vdots \\\\ a_{n1}& a_{n2}& \\cdots & a_{nn}\\end{bmatrix}$
因此二次型矩阵和对称矩阵是一一对应的关系。

对于最简单的一元二次函数 $f(x)=x^2$ ，当 $x\ eq 0$ 时 $f(x)>0$ 恒成立。即一元正定二次型对应的图像是开口向上，顶点在原点的抛物线，同理二元正定二次型 $f(x,y)=x^2 + y^2$ 对应的图像是开口向上，顶点在原点的抛物面。

扩展到 $n$ 元正定二次型的图像也对应着一个抛物线，保证当自变量取值非零向量时，对应的函数值大于0恒成立。

同样我们可以给出二元半正定二次型的图像，即某个自变量的特征值为 $0$ 从而保证当自变量取值为非零向量时，对应的函数值大于等于 $0$ 恒成立。

$\\begin{aligned}\\min &\\quad f(x) \\\\ s.t. &\\quad g_i(x) \\leq 0, i=1,2,...,m \\\\ &\\quad h_j(x)=0, j=1,2,...,n \\end{aligned}$

当 $f(x)$ 和 $g_i(x)$ 均为凸函数，而 $h_j(x)$ 均为仿射函数时, 上述的优化问题即凸优化问题。

$\\begin{aligned}\\min &\\quad c^Tx+d \\\\ s.t. &\\quad G(x) \\preceq h \\\\ &\\quad A(x)=b \\end{aligned}$ ?

其中目标函数和不等式约束都是仿射函数，且 $\\preceq$ 表示按元素小于等于。

$\\begin{aligned}\\min &\\quad \\frac{1}{2}x^TPx+c^Tx+d \\\\ s.t. &\\quad G(x) \\preceq h \\\\ &\\quad A(x)=b \\end{aligned}$

其中目标函数为凸二次型，不等式约束为仿射函数。

$\\begin{aligned}\\min &\\quad \\frac{1}{2}x^TPx+c^Tx+d \\\\ s.t. &\\quad \\frac{1}{2}x^TQ_ix + r_ix + s_i \\leq 0, i=1,2,....m \\\\ &\\quad A(x)=b \\end{aligned}$