QianQing's Blog

一阶条件

假设可微，即梯度在开集内处处存在，则函数是凸函数的充要条件：是凸集且任意，下式成立：

由得出的仿射函数即为函数在点附近的近似。

这个不等式说明从一个凸函数的局部信息可以得到一些全局信息。

同理，严格凸性也可以用一节条件刻画，只需要去掉凸性的一节条件的定义式中的取等即可。对于凹函数，只需要将改为即可。

二阶条件

假设函数二阶可导，即对于开集内的任意一点，其矩阵或者二阶导数存在，则函数是凸函数的充要条件是，其Hessian矩阵是半正定的，也即对于所有的有.

在上，这个条件退化为. 此条件说明的导数是非减的。条件从几何上可以立即为函数图像在点处有向上的曲率。

类似地，函数是凹的的充要条件是。是凸集且对于任意有.

严格凸的条件可以部分由二阶条件来刻画，如果对于任意有，则函数严格凸。反过来不一定成立，例如严格凸，但是在处其二阶导数为0.

凸函数的例子

首先，前面所有提到过的线性函数、仿射函数都为凸函数（同时也是凹函数）。

上的一些例子：

指数函数，幂函数，绝对值的幂函数

负熵：函数在其定义域上是凸函数（定义域为）

上的一些例子

范数是凸函数

最大值函数：在上是凸的。

二次-线性分式函数，例如是凸的，其定义域为

指数和的对数：在。这个函数可以看成时最大值函数的近似，因为总有：

几何平均：几何平均函数在定义域上是凹函数

凸函数的定义

函数是凸的：如果是凸集，且对于任意和任意有

从几何上看，上述不等式意味着点之间的线段（即之间的弦）在图像的上方。如果定义中的不等式当以及时严格成立，那么称时严格凸的。如果函数是凸的，那么称函数是凹的。如果是严格凸的，那么称是严格凹的。

对于仿射函数，定义中的不等式始终成立。仿射函数既凸又凹；反过来说，如果一个函数既凸又凹，则称其为仿射函数。

一个函数，当且仅当其在与其定义域相交的任何直线上都是凸的，这个函数是凸函数。换言之，当且仅当对于任意和任意向量，函数，函数是凸的。

扩展值延伸

通常定义凸函数在定义域外的值为，从而将这个凸函数延伸到。如果是凸函数，我们定义其扩展值延伸：如下：

可以从扩展值延伸之中确定原函数的定义域：

有了扩展值延伸的概念，就不需要每次都描述定义域了，以至于凸函数的定义式可以描述为：对于任意以及有：

由于定义域外的值被设定为了，则对于两个凸函数，其逐点求和函数的定义域为

类似地，对于凹函数，可以定义其定义域外部的值为.

对偶锥

定义

令为一个锥，则集合称为的对偶锥。顾名思义，是一个锥，且其总是凸的，即使不是凸锥。

从几何上看，当且仅当是在原点的一个支撑超平面的法线，如下图所示

上面的左图中，以为法向量的半平面包含锥，因此；右图中，以为内法向量的半空间不包含，因此

性质

可以导出对偶锥满足下面的性质

1. 是闭凸锥
2. 可以导出
3. 如果有非空内部，那么是尖的
4. 如果的闭包是尖的，那么有非空内部
5. 是的凸包的闭包。因此如果是凸的、闭的，那么

广义不等式的对偶

假设凸锥是正常锥，则可以导出一个广义不等式。其对偶锥也是正常的，所以也能导出一个广义不等式，称为广义不等式的对偶。

关于广义不等式及其对偶也有重要的性质

1. 当且仅当任意有
2. 当且仅当任意和有

对偶不等式定义的最小元和极小元

最小元的对偶

首先考虑最小元的性质，是上关于广义不等式的最小元的充要条件是对于，是在上极小化的唯一最优解。几何上看，这意味着对于任意，超平面是在处对的一个严格支撑超平面（严格支撑表示超平面与只相交于）。这里没有要求是凸集。

极小元的对偶性质

如果并且在上极小化，那么是极小的。

其逆定理在一般情况下不成立：上的极小元可以对于任何都不是上极小化的解。

队列（queue）是一种具有「先进入队列的元素一定先出队列」性质的表。由于该性质，队列通常也被称为先进先出（first in first out）表，简称 FIFO 表。

矩阵的建立

可以使用sympy.Matrix()建立矩阵，其中的参数可以是Python的列表，也可以是numpy的array

1
2
3
4
5
6
7
8
9
10
11
12

>>> a = [[1,1],[0,2]]
>>> b = np.array([[1,0],[1,1]])
>>> A = sympy.Matrix(a)
>>> B = sympy.Matrix(b)
>>> A
Matrix([
[1, 1],
[0, 2]])
>>> B
Matrix([
[1, 0],
[1, 1]])

最常见的矩阵是单位矩阵，建立单位矩阵需要矩阵的参数，使用sympy.eye()建立单位矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14

>>> sympy.eye(3)
Matrix([
[1, 0, 0],
[0, 1, 0],
[0, 0, 1]])
>>> sympy.eye(3,2)
Matrix([
[1, 0],
[0, 1],
[0, 0]])
>>> sympy.eye(2,3)
Matrix([
[1, 0, 0],
[0, 1, 0]])

另外还可以建立全零矩阵sympy.zeros()和全一矩阵sympy.ones()

1
2
3
4
5
6
7
8
9
10
11
12
13

>>> sympy.ones(2)	# 只有一个参数的时候默认为方阵
Matrix([
[1, 1],
[1, 1]])
>>> sympy.ones(2,3)
Matrix([
[1, 1, 1],
[1, 1, 1]])
>>> sympy.zeros(3,2)
Matrix([
[0, 0],
[0, 0],
[0, 0]])

另外还可以建立对角矩阵sympy.diag()

1
2
3
4
5

>>> sympy.diag(1,1,2)
Matrix([
[1, 0, 0],
[0, 1, 0],
[0, 0, 2]])

矩阵的运算

SymPy可以进行矩阵的加法、减法、乘法、求逆、转置、行列式。

使用之前建立的矩阵,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

>>> A+B
Matrix([
[2, 1],
[1, 3]])
>>> A-B
Matrix([
[ 0, 1],
[-1, 1]])
>>> A*B
Matrix([
[2, 1],
[2, 2]])
>>> A * B**-1
Matrix([
[ 0, 1],
[-2, 2]])
>>> B**-1
Matrix([
[ 1, 0],
[-1, 1]])
>>> A.T
Matrix([
[1, 0],
[1, 2]])
>>> A.det()
2

可以使用eigenvals(),eigenvects(),diagonalize()方法进行对角化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

>>> A
Matrix([
[1, 1],
[0, 2]])
>>> A.eigenvals()
{2: 1, 1: 1}
>>> A.eigenvects()
[(1, 1, [Matrix([
[1],
[0]])]), (2, 1, [Matrix([
[1],
[1]])])]
>>> A.diagonalize()
(Matrix([
[1, 1],
[0, 1]]), Matrix([
[1, 0],
[0, 2]]))

eigenvals()返回的结果中，第一个表示特征值，第二个表示特征值的重数。

eigenvects()返回的列表中，第一列表示特征值，第二个表示特征值的重数，第三个表示特征向量。

diagnonalize()返回的结果中，第一个矩阵表示，第二个矩阵表示，其中

在线性代数中，可以使用矩阵解线性方程组，例如求解Ax=b，以为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

>>> A = sympy.Matrix([[1,1],[0,2]])
>>> A
Matrix([
[1, 1],
[0, 2]])
>>> b = sympy.Matrix([3,5])
>>> b
Matrix([
[3],
[5]])
>>> A**-1*b
Matrix([
[1/2],
[5/2]])
>>> sympy.linsolve((A,b))
{(1/2, 5/2)}

从本篇博客开始记录机器学习的学习笔记

本篇博客介绍了频率派、贝叶斯派的观点，并且推导了一维/二维高斯分布参数的最大似然估计。

栈是 OI 中常用的一种线性数据结构。请注意，本篇博客主要讲的是栈这种数据结构，而非程序运行时的系统栈/栈空间。

栈的修改与访问是按照后进先出的原则进行的，因此栈通常被称为是后进先出（last in first out）表，简称 LIFO 表。

超平面分离定理

假设和是两个不相交的凸集，即，那么存在和使得对于所有的有、对于所有有。

换言之，仿射函数在中为非正，而在中为非负。

超平面称为和的分离超平面，或称超平面分离了集合和。

证明

这里只考虑特殊情况。使用距离，将集合和的距离定义为并且存在达到这个最小距离，即.

定义

我们将会得到一个仿射函数

在中非正而在中非负，即分离了和。这个超平面是连接之间的线段的中垂面（如同上面的图中的形状），直觉上来讲是成立的。

我们首先来证明在中非负。关于在中非正的证明是相似的。

假设存在点，且.这意味着

可以将表示为:

.

结合上面的两个式子，可以观察到

因此对于足够小的及，我们有

即比更加靠近。因为是包含的凸集，我们有，但这和我们的假设是相违背的。

严格分离

如果之前构造的分离超平面满足更强的条件，即对于任意有并且对于有，则称其为集合和的严格分离。

超平面分离定理的逆定理

超平面分离定理的逆定理（即分离超平面的存在表明和不相交）是不成立的，除非在凸性之外在给这两个集合附加其他约束。一个反例是，超平面可以分离和。

给增加条件后，可以得到超平面分离定理的一些逆定理。例如，设是凸集，是开集，若存在一个仿射函数，其在中非正而在中非负，那么不相交。

将逆定理和原定理相结合，可以得到如下结论：任何两个凸集如果其中至少有一个是开集，那么当且仅当存在分离超平面的时候，它们不相交。

在数学研究中，解方程首先需要确定解的范围，在SymPy中解方程也首先需要确定解的范围是实数集sympy.S.Reals或者复数集sympy.S.Complexes。定义域不同，得到的解集也是不同的。

在SymPy中使用函数sympy.solveset来求解方程的解集。

例如依次求解以下五个方程

1
2
3
4
5
6
7
8
9
10

>>> sympy.solveset(sympy.Eq(x**3,1),x,domain=sympy.S.Reals)
{1}
>>> sympy.solveset(sympy.Eq(x**3,1),x,domain=sympy.S.Complexes)
{1, -1/2 - sqrt(3)*I/2, -1/2 + sqrt(3)*I/2}
>>> sympy.solveset(sympy.exp(x),x)
EmptySet
>>> sympy.solveset(sympy.exp(x)-1,x,domain=sympy.S.Reals)
{0}
>>> sympy.solveset(sympy.exp(x)-1,x,domain=sympy.S.Complexes)
ImageSet(Lambda(_n, 2*_n*I*pi), Integers)

其中Lambda()表示函数，_n是自变量，Integers是自变量的定义域

在线性代数中，有多元一次方程组，可以使用sympy.solve()函数，例如

1
2
3
4

>>> sympy.solve([x+y-10,x-y-2],[x,y])
{x: 6, y: 4}
>>> sympy.solve([sympy.sin(x-y),sympy.cos(x+y)],[x,y])
[(-pi/4, 3*pi/4), (pi/4, pi/4), (3*pi/4, 3*pi/4), (5*pi/4, pi/4)]

SymPy可以进行微分、积分、极限等计算，

比如有函数，可以使用sympy.subs()进行变量代换，把代换为等其他变量或者常数。例如

1
2
3
4
5
6
7
8
9
10
11

>>> x = sympy.symbols('x')
>>> f = 1/x
>>> f
1/x
>>> y = sympy.symbols('y')
>>> f = f.subs(x,y)
>>> f
1/y
>>> ans = f.subs(y,1)
>>> ans
1

在微积分中，最基本的操作是求极限，SymPy中求极限使用函数sympy.limit()

1
2
3
4
5
6
7
8

>>> f = 1/x
>>> sympy.limit(f,x,0)
oo
>>> sympy.limit(f,x,sympy.oo)
0
>>> f = sympy.sin(x)/x
>>> sympy.limit(f,x,0)
1

也可以使用函数sympy.diff()进行求导的操作，可以在参数中设定求导的次数、变量等

1
2
3
4
5
6
7
8
9
10

>>> f = 1/x
>>> sympy.diff(f,x)
-1/x**2
>>> sympy.diff(f,x,2)	# 对f求x的二阶导
2/x**3
>>> sympy.diff(f,x,10)	# 对f求x的十阶导
3628800/x**11
>>> f = sympy.exp(x*y)*x+sympy.sin(x**2+y)
>>> sympy.diff(f,x,y,x)	# f先对x求导，再对y求导，再对x求导
x**2*y**2*exp(x*y) - 4*x**2*cos(x**2 + y) + 4*x*y*exp(x*y) + 2*exp(x*y) - 2*sin(x**2 + y)

提到导数，这里提一下泰勒级数，这里可以使用sympy.series()函数。其中包含参数expr,x,x0,n,dir；分别表示函数、展开变量、展开点、展开的最高次、方向（等）。默认情况下，x0=0,n=6.

1
2
3
4
5
6
7

>>> f = sympy.cos(x)
>>> sympy.series(f,x)
1 - x**2/2 + x**4/24 + O(x**6)
>>> sympy.series(f,x,1,10)
cos(1) - (x - 1)*sin(1) - (x - 1)**2*cos(1)/2 + (x - 1)**3*sin(1)/6 + (x - 1)**4*cos(1)/24 - (x - 1)**5*sin(1)/120 - (x - 1)**6*cos(1)/720 + (x - 1)**7*sin(1)/5040 + (x - 1)**8*cos(1)/40320 - (x - 1)**9*sin(1)/362880 + O((x - 1)**10, (x, 1))
>>> sympy.series(f,x).removeO()	# removeO()方法可以去掉余项
x**4/24 - x**2/2 + 1

SymPy的积分使用函数sympy.integrate()，可以计算不定积分、定积分、广义积分

例如

需要注意积分上下界在函数中的写法

1
2
3
4
5

>>> f = 1/x
>>> sympy.integrate(f,x)
log(x)
>>> sympy.integrate(f,(x,1,2))
log(2)

还有

1
2
3
4
5
6
7
8
9

>>> g = sympy.exp(-x**2)
>>> sympy.integrate(g,(x,-sympy.oo,0))
sqrt(pi)/2
>>> g = sympy.exp(-x)
>>> sympy.integrate(g,(x,0,sympy.oo))
1
>>> h = sympy.exp(-x**2-y**2)
>>> sympy.integrate(h,(x,-sympy.oo,sympy.oo),(y,-sympy.oo,sympy.oo))
pi