机器学习必备知识点——凸优化_hessian矩阵判断凸性

1、计算几何是研究什么的？

计算几何研究几何模型和数据处理的学科，讨论几何形体的计算机表示、分析和综合，研究如何方便灵活、有效地建立几何形体的数学模型以及在计算机中更好地存贮和管理这些模型数据。

2、计算几何理论中（或凸集中）过两点的一条直线的表达式，是如何描述的？与初中数学中那些直线方程有什么差异？有什么好处？(按自己的体会)

1. 计算几何理论中（或凸集中）

$$x_1\ne x_2$$
且为n维空间的两个点则：
$$y=\theta x_1+(1-\theta )x_2$$

2.初中数学中

直线的两点式方程推导过程：
（1）设直线l上的两点P1、P2的坐标分别为(x1,y1)、(x2,y2)，且(x1≠x2)
所以直线l的斜率
$$K＝\frac{y_2-y_1}{x_2-x_1}$$
（2）在直线l上任意取一点P（x，y）
将直线l的斜率K，P点的坐标代入直线的点斜式方程y-y0=k(x-x0)中得
$$y-y_1=\frac{y_2-y_1}{x_2-x_1}\ast (x-x_1)$$
即$$\frac{y-y_1}{y_2-y_1}＝\frac{x-x_1}{x_2-x_1}$$为直线 l 的两点式方程。

3.二者对比与好处

3、凸集是什么？ 直线是凸集吗？是仿射集吗？

• 凸集是什么？

1. 在凸几何中
   凸集(convex set)是在凸组合下闭合的仿射空间的子集
2. 更具体地说，在欧氏空间中
   凸集是对于集合内的每一对点，连接该对点的直线段上的每个点也在该集合内。例如，立方体是凸集，但是任何中空的或具有凹痕的例如月牙形都不是凸集。

• 直线是凸集吗？
  根据凸集定义，直线是凸集。

• 仿射集是什么？
  仿射集亦称仿射流形、线性流形、仿射簇，是实线性空间中的一类子集。非空间射集 M 的维数定义为上述子空间 L 的维数。空集的维数定义为-1。维数分别为0、1，以及2的仿射集为点、直线和平面。
  根据仿射集定义，当维数为1的仿射集为直线。

4、三维空间中的一个平面，如何表达？

$$Ax+By+Cz+D=0$$平面 Ax+By+Cz+D = 0 的法向量就是 x、y、z 的系数，也即（A，B，C）。

5、更高维度的“超平面”，如何表达？

1.高维度的“超平面”定义

(1) 超平面是指n维线性空间中维度为n-1的子空间。它可以把线性空间分割成不相交的两部分。比如二维空间中，一条直线是一维的，它把平面分成了两块；三维空间中，一个平面是二维的，它把空间分成了两块。
(2) 法向量是指垂直于超平面的向量。
在$${\mathbb{R}}^3$$空间中，假如有法向量$$\omega$$过原点的平面内任意原点出发的向量x必然与之满足$$w^{T}x=0$$如果平面沿着法向量的方向上下平移了，那么这个方程就不成立了。
我们假设平移之后平面经过$$x^{\prime }(x_1^{\prime },x_2^{\prime },x_3^{\prime })$$平面内任意一点记为$$x(x_1,x_2,x_3)$$法向量记为$$\omega ({\omega }_1,{\omega }_2,{\omega }_3)$$如下图。

不难看出，$$x-x^{\prime }$$在平面内，当然也就和法向量垂直。于是我们有：
( x − x ′ ) w = 0 ( x 1 − x 1 ′ , x 2 − x 2 ′ , x 3 − x 3 ′ ) ⋅ ( ω 1 , ω 2 , ω 3 ) = 0

$$\begin{aligned} &(x-x')w=0\\ &(x_1-x_1', x_2-x_2',x_3-x_3')\cdot(\omega_1,\omega_2,\omega_3)=0 \end{aligned}$$ ​(x−x′)w=0(x1​−x1′​,x2​−x2′​,x3​−x3′​)⋅(ω1​,ω2​,ω3​)=0​
化简后得：$$x_1{\omega }_1+x_2{\omega }_2+x_3{\omega }_3={\omega }_1{x}_1^{\prime }+{\omega }_2{x}_2^{\prime }+{\omega }_3{x}_3^{\prime }$$即$${\omega }^{T}x={\omega }^T{x}^{\prime }$$由于其为常数项，令$$b=-{\omega }^T{x}^{\prime }$$于是超平面的公式可以写成：
$${\omega }^{T}x+b=0$$
这个结论同样适用于$$R^n$$空间；
无论超平面如何平移，系数始终是法向量$$\omega$$

• 这个我参考了如何理解超平面？

6、什么是“凸函数”？什么是Hessen矩阵? 如何判别一个函数是凸函数？f(x)=x^3 函数是凸函数吗？

1.什么是“凸函数”？

凸函数是一个定义在某个向量空间的凸子集C上的实值函数f，而且对于凸子集C中任意两个向量x1、x2有$$\frac{f(x_1+x_2)}{(f(x_1)+f(x_2))/2}$$成立。

2.什么是Hessen矩阵?

Hessen矩阵是是一个多元函数的二阶偏导数构成的方阵，描述了函数的局部曲率，利用黑塞矩阵可判定多元函数的极值问题

3.如何判别一个函数是凸函数？

判定方法：
1.对于一元函数f(x)f(x)，我们可以通过其二阶导数f′′(x)f″(x) 的符号来判断。如果函数的二阶导数总是非负，即f′′(x)≥0f″(x)≥0 ，则f(x)f(x)是凸函数
2.对于多元函数f(X)f(X)，我们可以通过其Hessian矩阵（Hessian矩阵是由多元函数的二阶导数组成的方阵）的正定性来判断。如果Hessian矩阵是半正定矩阵，则是f(X)f(X)凸函数

• 参考文献 什么是凸函数及如何判断一个函数是否是凸函数

4.f(x)=x^3 函数是凸函数吗？

对f(x)求二阶导
$$y=x^3;y^{\prime }=3x^2;y^{\prime \prime }=6x$$
所以
x>0 函数是凹函数；
x<0 函数是凸函数。

7、什么是“凸规划”？如何判别一个规划问题是凸规划问题。举例说明？

1.什么是“凸规划”？

设f(x)及gi(x)，i=1…m均为$$R^n$$上的凸函数，则称最优化问题
s . t = { m a x f ( x ) a j T ( x ) = b j , j = 1...... p g i ( x ) ≤ 0 , i = 1 , 2 , . . . . . . m s.t=

$$\begin{cases} max f(x)\\\\ a_j^T(x)= b_j ,j=1......p\\\\ g_i(x)\leq0 ,i=1,2,......m \end{cases}$$ s.t=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​maxf(x)ajT​(x)=bj​,j=1......pgi​(x)≤0,i=1,2,......m​
为凸规划。

• 参考文献 凸规划

2.如何判别一个规划问题是凸规划问题?（举例说明）

例子
{ m i n f ( X ) = x 1 2 + x 2 2 − 4 x 1 + 4 g 1 ( X ) = − x 1 + x 2 − 2 ≤ 0 g 2 ( X ) = + x 1 2 − x 2 + 1 ≤ 0 x 1 , x 2 ≥ 0

$$\begin{cases} min f(X)=x_1^2+x_2^2-4x_1+4\\\\ g_1(X)=-x_1+x_2-2\leq0 \\\\ g_2(X)=+x_1^2-x_2+1\leq0 \\\\ x_1,x_2\geq0\\\\ \end{cases}$$ ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​minf(X)=x12​+x22​−4x1​+4g1​(X)=−x1​+x2​−2≤0g2​(X)=+x12​−x2​+1≤0x1​,x2​≥0​
手工求解过程如下

8、总结

学习了凸优化，理解了它的一些概念和基本思想算法，为后面学习机器学习奠定基础！在机器学习各种优化问题中，凸集、凸函数和凸优化等概念经常出现，因此认识其性质对于优化问题的理解尤为重要。