1. 凸集
Def:Set
X
X
X\ in
R
n
R^n
Rnis convex iff
α
x
1
+
(
1
−
α
)
x
2
∈
X
∀
x
1
,
x
2
∈
X
,
∀
α
∈
[
0
,
1
]
\alpha x_1+(1-\alpha)x_2\in X \ \forall x_1,x_2\in X,\forall\alpha\in[0,1]
αx1+(1−α)x2∈X ∀x1,x2∈X,∀α∈[0,1]
凸集意味着：凸集中的任意两点之间的连线上的点也是凸集中的点。
2. 超平面
超平面被定义为一个点集
X
=
{
x
∣
c
T
x
=
z
}
X=\{x|c^Tx=z\}
X={x∣cTx=z}
其中c是一个非零向量z是一个标量
3. 凸集的支撑面(特殊的超平面)
给出一个凸集 X X X的边界点 w w w，超平面 c T x = z c^Tx=z cTx=z被称为 w w w的支撑超平面，满足下列条件：
- w w w过这个超平面 c T w = z c^Tw=z cTw=z
- 集合 X X X的所有点都在超平面的一侧
4. 凸函数
**DEF：
X
X
Xa convex set in
R
n
R^n
Rn.
f
(
x
)
:
X
−
>
R
f(x):X->R
f(x):X−>Ris convex iff
f
(
α
x
1
+
(
1
−
α
)
x
2
)
≤
α
f
(
x
1
)
+
(
1
−
α
)
f
(
x
2
)
f(\alpha x_1+(1- \alpha)x_2)\leq\alpha f(x_1)+(1-\alpha) f(x_2)
f(αx1+(1−α)x2)≤αf(x1)+(1−α)f(x2)
∀
x
1
,
x
2
∈
X
,
∀
α
∈
[
0
,
1
]
\forall x_1,x_2 \in X,\forall \alpha\in [0,1]
∀x1,x2∈X,∀α∈[0,1]
注意事项：
- 凸函数要定义在凸集中
- 该定义不需要 f ( x ) f(x) f(x)是连续的或者可微分的
- 如果 − f ( x ) -f(x) −f(x)是凸的，是、则 f ( x ) f(x) f(x)是凸的
- 当 ≤ \leq ≤被 < < <代替，凸集是严格凸的当 a l p h a ∈ ( 0 , 1 ) ， x 1 ≠ x 2 alpha \in(0,1)，x_1\neq x_2 alpha∈(0,1)，x1=x2
5. 梯度
什么是
∇
f
(
x
)
,
∇
2
f
(
x
)
\nabla f(x),\nabla^2 f(x)
∇f(x),∇2f(x)：
∇
f
(
x
)
=
(
∂
f
(
x
)
∂
x
1
,
∂
f
(
x
)
∂
x
2
,
∂
f
(
x
)
∂
x
3
.
.
.
∂
f
(
x
)
∂
x
n
)
\nabla f(x)=\left(\frac{\partial f(x)}{\partial x_1},\frac{\partial f(x)}{\partial x_2},\frac{\partial f(x)}{\partial x_3}...\frac{\partial f(x)}{\partial x_n} \right)
∇f(x)=(∂x1∂f(x),∂x2∂f(x),∂x3∂f(x)...∂xn∂f(x))
hessian阵：
H
(
x
)
=
∇
2
f
(
x
)
≡
(
∂
f
(
x
)
∂
x
1
2
.
.
.
∂
f
(
x
)
∂
x
1
∂
x
n
.
.
.
.
.
.
.
.
.
∂
f
(
x
)
∂
x
n
∂
x
1
.
.
.
∂
f
(
x
)
∂
x
n
2
)
H(x)=\nabla^2f(x)\equiv\begin{pmatrix} \frac{\partial f(x)}{\partial x_1^2}&...&\frac{\partial f(x)}{\partial x_1 \partial x_n}\\ ...&...&...\\ \frac{\partial f(x)}{\partial x_n\partial x_1}&...&\frac{\partial f(x)}{\partial x_n^2}\\ \end{pmatrix}
H(x)=∇2f(x)≡⎝⎜⎛∂x12∂f(x)...∂xn∂x1∂f(x).........∂x1∂xn∂f(x)...∂xn2∂f(x)⎠⎟⎞
- 海森矩阵是 n × n n\times n n×n的矩阵
- 海森矩阵是对称阵 H T = H H^T=H HT=H
- 一维的情况： ∇ f ( x ) = f ′ ( x ) , ∇ 2 f ( x ) = f ′ ′ ( x ) \nabla f(x)=f'(x),\nabla^2f(x)=f''(x) ∇f(x)=f′(x),∇2f(x)=f′′(x)
6. 方向导数
如果
u
u
u是一个单位向量，那么
f
(
x
)
f(x)
f(x)的方向导数为：
lim
a
→
0
f
(
x
+
a
u
)
−
f
(
x
)
a
=
∇
f
(
x
)
T
u
\lim_{a \to0}\frac{f(x+au)-f(x)}{a}=\nabla f(x)^Tu
a→0limaf(x+au)−f(x)=∇f(x)Tu
梯度和单位向量
u
u
u的内积
7. 微分函数的凸性质
对于微分函数，下列定理可以用来确定 f ( x ) f(x) f(x)是凸的。
- 定理1：
另 f ( x ) f(x) f(x)是凸集 x x x上的可微函数，当且仅当
f ( x 2 ) − f ( x 1 ) ≥ ∇ f ( x 1 ) T ( x 2 − x 1 ) , ∀ x 1 , x 2 ∈ X f(x_2)-f(x_1)\geq \nabla f(x_1)^T(x_2-x_1),\forall x_1,x_2 \in X f(x2)−f(x1)≥∇f(x1)T(x2−x1),∀x1,x2∈X
直观的理解：微分定义： Δ y = f ′ ( x ) Δ x + o ( Δ x ) \Delta y =f'(x)\Delta x +o(\Delta x) Δy=f′(x)Δx+o(Δx)如果 f ( x ) f(x) f(x)是凸函数的话，那么 Δ y ≥ f ′ ( x ) Δ x \Delta y\geq f'(x)\Delta x Δy≥f′(x)Δx（充要条件） - 定理2：
另 f ( x ) f(x) f(x)是一个二阶微分函数在一个开集 X X X上。当且仅当Hessian矩阵 H ( x ) H(x) H(x)是半正定的对于 ∀ x ∈ X \forall x\in X ∀x∈X, f ( x ) f(x) f(x)在 X X X上是凸的。（充要条件）- 半正定
H ( x ) H(x) H(x)是半正定，有 H ( x ) H(x) H(x)是对称的； ∀ ≠ 0 , x T H x ≥ 0 \forall \neq 0,\ x^THx\geq0 ∀=0, xTHx≥0 - 正定：
H ( x ) H(x) H(x)是半正定，有 H ( x ) H(x) H(x)是对称的； ∀ ≠ 0 , x T H x > 0 \forall \neq 0,\ x^THx>0 ∀=0, xTHx>0 - 定理2的证明：
∀ x ∈ X ∀ ， x ^ ∈ R n , X 是 开 集 \forall x \in X\forall，\hat x\in R^n,X是开集 ∀x∈X∀，x^∈Rn,X是开集， ∃ δ > 0 \exists \delta>0 ∃δ>0使得 λ ∈ [ − δ , δ ] , x + λ x ^ ∈ X \lambda\in [-\delta,\delta],x+\lambda \hat x \in X λ∈[−δ,δ],x+λx^∈X
根据定理1，有： f ( x + λ x ^ ) ≥ f ( x ) + λ f ′ ( x ) x ^ f(x+\lambda \hat x ) \geq f(x)+\lambda f'(x)\hat x f(x+λx^)≥f(x)+λf′(x)x^
根据泰勒展开： f ( x + λ x ^ ) = f ( x ) + λ ∇ f ( x ) T x ^ + λ 2 2 x ^ T ∇ 2 f ( x ) x ^ + o ( λ 2 ) f(x+\lambda \hat x)=f(x)+\lambda \nabla f(x)^T \hat x+\frac{\lambda^2}{2}\hat x^T \nabla^2 f(x)\hat x+o(\lambda^2) f(x+λx^)=f(x)+λ∇f(x)Tx^+2λ2x^T∇2f(x)x^+o(λ2)
将上面第二个式子代入到第一个式子里，有：
x ^ T ∇ 2 f ( x ) x ^ ≥ 0 \hat x^T\nabla^2 f(x)\hat x\geq 0 x^T∇2f(x)x^≥0
在学最优化的时候就有疑问，多元泰勒展开为什么是上面那样，答案在这里：知乎推导（就是正常多元求导，然后转成矩阵形式）
- 半正定
- 定理3：
另 f ( x ) f(x) f(x)是一个二阶微分函数在开集并且是凸集 X X X。如果海森矩阵 H ( x ) H(x) H(x)是正定的对于每个 x ∈ X x\in X x∈X，那么 f ( x ) f(x) f(x)是严格凸的在 X X X上（充分不必要的） - 补充知识点：泰勒展开：
一元函数的泰勒展开
f ( x ) = f ( x k ) + ( x − x k ) f ′ ( x k ) + 1 2 ! ( x − x k ) 2 f ′ ′ ( x k ) + o n f(x)=f(x_k)+(x-x_k)f'(x_k)+\frac{1}{2!}(x-x_k)^2f''(x_k)+o^n f(x)=f(xk)+(x−xk)f′(xk)+2!1(x−xk)2f′′(xk)+on
f ( x + p ) = f ( x ) + p f ′ ( x ) + 1 2 ! p 2 f ′ ′ ( x ) + o n f(x+p)=f(x)+pf'(x)+\frac{1}{2!}p^2f''(x)+o^n f(x+p)=f(x)+pf′(x)+2!1p2f′′(x)+on
多元转成矩阵形式：
f ( x + p ) = f ( x ) + ∇ f ( x ) T p + 1 2 ! p T ∇ 2 f ( x ) p + o n f(x+p)=f(x)+\nabla f(x)^Tp+\frac{1}{2!}p^T\nabla^2 f(x)p+o^n f(x+p)=f(x)+∇f(x)Tp+2!1pT∇2f(x)p+on