Skip to main content

机器学习 - 凸优化

· 7 min read
PuQing
AI, CVer, Pythoner, Half-stack Developer
定义

凸优化问题 (OPT,convex optimization problem) 指定义在凸集中的凸函数最优化的问题。

数学概念

凸集

定义

假设 CC 是向量空间的集。若对于任意 x,yCx,y\in C 和任意的 θR\theta\in \mathbb{R},满足 0θ10\le \theta \le 1 时,θx+(1θ)yC\theta x+(1-\theta)y \in C 恒成立。则称 CC凸集1

从几何上来看,就是 CC 中的任意两点之间的直线段都属于 CC

下面举几个例子:

info

image.png

  1. 是凸集 (集合中的任意两个点连线段中的所有点,都在集合中)
  2. 不是凸集,有空隙
  3. 不是凸集,有些边不在集合中

凸函数

定义

定义在 RnR\mathbb{R}^n \to \mathbb{R} 上的函数 ff 是凸函数,如果它的定义域 D(f)\mathbb{D}(f) 是一个凸集且对任意的 x,yDx,y \in \mathbb{D}0θ1,f(θx+(1θy))θf(x)+(1θ)f(y)0\le \theta \le 1, f(\theta x+(1-\theta y))\le \theta f(x)+(1-\theta)f(y) 恒成立 2

直观来看:

image.png

info

在函数图形上,任意两点连成的线段,皆位于图形的上方

凸函数的一阶充要条件

tip

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

f(y)f(x)+f(x)(yx)f(y)\ge f(x) + \nabla f(x)^\top(y-x)
info

从几何上来看,即定义域内图形都大于等于该点的切线 (切平面)

image.png

公式的理解

对于二元函数 f(x,y)f(x,y)

我们知道,函数在某一点 (x0,y0)(x_{0},y_{0}) 处的切平面为

z=fx(x0,y0)(xx0)+fy(x0,y0)(yy0)+f(x0,y0)z=f_{x}(x_{0},y_{0})(x-x_{0})+f_{y}(x_{0},y_{0})(y-y_{0}) + f(x_{0},y_{0})

其中的 fx(x0,y0),fy(x0,y0)f_{x}(x_{0},y_{0}),f_{y}(x_{0},y_{0})ff(x0,y0)(x_{0},y_{0}) 处的偏导数的值,我们可以使用 \nabla 算子 进行表示,并且将自变量视为向量,则:

z=f(x0)(xx0)+f(x0)z = \nabla f(x_{0})^\top(x-x_{0})+f(x_{0})

所以有上面几何理解

凸函数的二阶充要条件

记函数的一阶导数和二阶导数分别为 ggHH

g=f=[fx1fx2fxn]H=2f=[2fx122fx1x22fx1xn2fx2x12fx222fx2xn2fxnx12fxnx22fxn2]g=\nabla f=\left[\begin{array}{c} \frac{\partial f}{\partial x_{1}} \\ \frac{\partial f}{\partial x_{2}} \\ \vdots \\ \frac{\partial f}{\partial x_{n}} \end{array}\right] \quad H=\nabla^{2} f=\left[\begin{array}{cccc} \frac{\partial^{2} f}{\partial x_{1}^{2}} & \frac{\partial^{2} f}{\partial x_{1} \partial x_{2}} & \cdots & \frac{\partial^{2} f}{\partial x_{1} \partial x_{n}} \\ \frac{\partial^{2} f}{\partial x_{2} \partial x_{1}} & \frac{\partial^{2} f}{\partial x_{2}^{2}} & \cdots & \frac{\partial^{2} f}{\partial x_{2} \partial x_{n}} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^{2} f}{\partial x_{n} \partial x_{1}} & \frac{\partial^{2} f}{\partial x_{n} \partial x_{2}} & \cdots & \frac{\partial^{2} f}{\partial x_{n}^{2}} \end{array}\right]

假设定义在 RnR\mathbb{R}^n \to \mathbb{R} 上的函数 ff 二阶可微(即海赛矩阵 2f(x)\nabla^2f(x) 存在)。则函数 ff 是凸函数当且仅当函数定义域 D(f)\mathbb{D}(f) 是一个凸集,且对于所有 xD(f)x \in \mathbb{D}(f) 均满足:

2f(x)0\nabla^2f(x)\succeq 0
info

这里的 0\succeq 0 表示是半正定的

正定矩阵(This page is not published)

凸优化问题

定义
minf(x)s.t.gi(x)0,i=1,2,,mhj(x)=0,j=1,2,,n\begin{array}{cl} \min & f(x) \\ s . t . & g_{i}(x) \leq 0, i=1,2, \ldots, m \\ & h_{j}(x)=0, j=1,2, \ldots, n \end{array}

f(x)f(x)gi(x)g_{i}(x) 均为凸函数,而 hj(x)h_{j}(x) 均为 仿射变换与仿射函数 时,上述的优化问题即凸优化问题

常见的凸优化问题

线性规划(LP,Linear Program)
mincTx+d s.t. G(x)hA(x)=b\begin{array}{cl} \min & c^{T} x+d \\ \text { s.t. } & G(x) \preceq h \\ & A(x)=b \end{array}

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

二次规划(QP,Quadratic Program)
min12xTPx+cTx+d s.t. G(x)hA(x)=b\begin{array}{ll} \min & \frac{1}{2} x^{T} P x+c^{T} x+d \\ \text { s.t. } & G(x) \preceq h \\ & A(x)=b \end{array}

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

利用 Python 进行凸优化

下面是几段例程

给定一个普通的线性规划问题

minz=2x1+3x2+x3{x1+4x2+2x383x1+2x26x1,x2,x30\begin{array}{c} \min z=2 x_{1}+3 x_{2}+x_{3} \\ \left\{\begin{array}{l} x_{1}+4 x_{2}+2 x_{3} \geq 8 \\ 3 x_{1}+2 x_{2} \geq 6 \\ x_{1}, x_{2}, x_{3} \geq 0 \end{array}\right. \end{array}
import numpy as np

z = np.array([2, 3, 1])

a = np.array([[1, 4, 2], [3, 2, 0]])

b = np.array([8, 6])

x1_bound = x2_bound = x3_bound =(0, None)

from scipy import optimize

res = optimize.linprog(z, A_ub=-a, b_ub=-b,bounds=(x1_bound, x2_bound, x3_bound))

print(res)

#output:
# fun: 7.0
# message: 'Optimization terminated successfully.'
# nit: 2
# slack: array([0., 0.])
# status: 0
# success: True
# x: array([0.8, 1.8, 0. ])

参考资料

Footnotes

  1. 凸集 - 维基百科,自由的百科全书

  2. 凸函数 - 维基百科,自由的百科全书