b站凌青老师凸优化课程1-6课笔记。
什么是优化
优化就是从一个可行解的集合中，寻找出最优的元素。写成数学形式：
minimize
f
0
(
x
)
subject to
f
i
(
x
)
≤
b
i
i
=
1
,
⋯
,
M
\begin{aligned} &\text{minimize }f_0(x)\\ &\text{subject to }f_i(x)\le b_i\quad i=1,\cdots,M \end{aligned}
minimize f0(x)subject to fi(x)≤bii=1,⋯,M
其中
x
=
[
x
1
,
⋯
,
x
n
]
T
x=[x_1,\cdots,x_n]^T
x=[x1,⋯,xn]T 称为优化变量，
f
0
:
R
n
→
R
f_0:\R^n\to \R
f0:Rn→R 称为目标函数，
f
i
:
R
n
→
R
f_i:\R^n\to \R
fi:Rn→R 称为不等式约束。
优化问题的分类
优化问题一般有如下分类，其中前者通常较简单，后者通常较难。
线性规划 / 非线性规划
称 f f f 为线性函数如果 f ( α x + β y ) = α f ( x ) + β f ( y ) f(\alpha x+\beta y)=\alpha f(x)+\beta f(y) f(αx+βy)=αf(x)+βf(y)。
若限制函数和目标函数均为线性函数，则称该问题为线性规划，否则称其为非线性规划。
凸规划 / 非凸规划
称 f f f 是凸函数如果 f ( α x + β y ) ≤ α f ( x ) + β f ( y ) f(\alpha x+\beta y)\le \alpha f(x)+\beta f(y) f(αx+βy)≤αf(x)+βf(y)。
若限制函数和目标函数均为凸函数，则称该问题为凸规划，否则称其为非凸规划。
通常还有光滑 / 非光滑，连续 / 离散，单目标 / 多目标等分类。
凸集
直线和线段
对于
x
1
≠
x
2
∈
R
n
x_1\neq x_2\in \R^n
x1=x2∈Rn，定义过
x
1
,
x
2
x_1,x_2
x1,x2 的直线为
{
θ
x
1
+
(
1
−
θ
)
x
2
∣
θ
∈
R
}
\{\theta x_1+(1-\theta)x_2|\theta\in \R\}
{θx1+(1−θ)x2∣θ∈R}
定义
x
1
,
x
2
x_1,x_2
x1,x2 构成的线段为
{
θ
x
1
+
(
1
−
θ
)
x
2
∣
θ
∈
[
0
,
1
]
}
\{\theta x_1+(1-\theta)x_2|\theta\in [0,1]\}
{θx1+(1−θ)x2∣θ∈[0,1]}
仿射集
定义
定义1 称集合 C C C 是仿射集，若 ∀ x 1 , x 2 ∈ C \forall x_1,x_2\in C ∀x1,x2∈C，连接 x 1 x_1 x1 与 x 2 x_2 x2 的直线都在 C C C 内。
仿射组合 设 x 1 , ⋯ , x k x_1,\cdots,x_k x1,⋯,xk，称 θ 1 x 1 + ⋯ + θ k x k \theta_1x_1+\cdots+\theta_kx_k θ1x1+⋯+θkxk 为其仿射组合，其中 θ 1 , ⋯ , θ k ∈ R \theta_1,\cdots,\theta_k\in \R θ1,⋯,θk∈R，且 θ 1 + ⋯ + θ k = 1 \theta_1+\cdots+\theta_k=1 θ1+⋯+θk=1。
定义2 称集合 C C C 是仿射集，若 ∀ x 1 , ⋯ , x k ∈ c \forall x_1,\cdots,x_k\in c ∀x1,⋯,xk∈c，它们的所有仿射组合都在 C C C 内。
定理
上述两个定义等价。
证明 由定义2显然可以推出定义1。往证由定义1可推出定义2。
假设有仿射集
C
C
C，先证任意三个元素的仿射组合都在
C
C
C 中。取
x
1
,
x
2
,
x
3
∈
c
x_1,x_2,x_3\in c
x1,x2,x3∈c，
θ
1
,
θ
2
,
θ
3
∈
R
\theta_1,\theta_2,\theta_3\in \R
θ1,θ2,θ3∈R 且
θ
1
+
θ
2
+
θ
3
=
1
\theta_1+\theta_2+\theta_3=1
θ1+θ2+θ3=1，根据定义1可知
θ
1
θ
1
+
θ
2
x
1
+
θ
2
θ
1
+
θ
2
x
2
∈
C
\frac{\theta_1}{\theta_1+\theta_2}x_1+\frac{\theta_2}{\theta_1+\theta_2}x_2\in C
θ1+θ2θ1x1+θ1+θ2θ2x2∈C
那么有
(
θ
1
+
θ
2
)
(
θ
1
θ
1
+
θ
2
x
1
+
θ
2
θ
1
+
θ
2
x
2
)
+
(
1
−
θ
1
−
θ
2
)
x
3
∈
C
(\theta_1+\theta_2)\left(\frac{\theta_1}{\theta_1+\theta_2}x_1+\frac{\theta_2}{\theta_1+\theta_2}x_2\right)+(1-\theta_1-\theta_2)x_3\in C
(θ1+θ2)(θ1+θ2θ1x1+θ1+θ2θ2x2)+(1−θ1−θ2)x3∈C
展开即可得到
θ
1
x
1
+
θ
2
x
2
+
θ
3
x
3
∈
C
\theta_1x_1+\theta_2x_2+\theta_3x_3\in C
θ1x1+θ2x2+θ3x3∈C。由归纳法可知两个定义等价。
关于仿射集的子空间
假设
C
C
C 是仿射集，
x
1
,
x
2
∈
C
x_1,x_2\in C
x1,x2∈C。把 令
γ
=
α
x
1
+
β
x
2
\gamma=\alpha x_1+\beta x_2
γ=αx1+βx2，则当
α
+
β
≠
1
\alpha+\beta\neq 1
α+β=1 时
γ
\gamma
γ 未必在
C
C
C 中。构造新集合：
V
=
c
−
x
0
=
{
x
−
x
0
∣
x
∈
c
}
∀
x
0
∈
c
V=c-x_0=\{x-x_0|x\in c\}\quad \forall x_0\in c
V=c−x0={x−x0∣x∈c}∀x0∈c
称
V
V
V 为与
C
C
C 相关的子空间。那么对于
∀
v
1
,
v
2
∈
V
\forall v_1,v_2\in V
∀v1,v2∈V，
∀
α
,
β
∈
R
\forall \alpha,\beta\in \R
∀α,β∈R，都有
α
v
1
+
β
v
2
∈
V
\alpha v_1+\beta v_2\in V
αv1+βv2∈V。因为
α
(
v
1
+
x
0
)
+
β
(
v
2
+
x
0
)
+
(
1
−
α
−
β
)
x
0
∈
C
\alpha(v_1+x_0)+\beta(v_2+x_0)+(1-\alpha-\beta)x_0\in C
α(v1+x0)+β(v2+x0)+(1−α−β)x0∈C
从而
α
v
1
+
β
v
2
+
x
0
∈
C
\alpha v_1+\beta v_2+x_0\in C
αv1+βv2+x0∈C
注意到子空间必须经过原点。
仿射包
定义集合
C
C
C 的仿射包为
aff
C
=
{
θ
x
1
+
⋯
+
θ
k
x
k
∣
∀
x
1
,
⋯
,
x
k
∈
C
,
∀
θ
1
+
⋯
+
θ
k
=
1
}
\text{aff }C=\{\theta x_1+\cdots+\theta_kx_k|\forall x_1,\cdots,x_k\in C,\forall \theta_1+\cdots+\theta_k=1\}
aff C={θx1+⋯+θkxk∣∀x1,⋯,xk∈C,∀θ1+⋯+θk=1}
那么
aff
C
\text{aff }C
aff C 为包含
C
C
C 的最小仿射集。
凸集
定义
定义1 称集合 C C C 是凸集，如果任意两点之间的线段都在 C C C 内。形式化描述：对于 ∀ x 1 , x 2 ∈ C \forall x_1,x_2\in C ∀x1,x2∈C， ∀ θ ∈ [ 0 , 1 ] \forall\theta\in [0,1] ∀θ∈[0,1]，都有 θ x 1 + ( 1 − θ ) x 2 ∈ C \theta x_1+(1-\theta)x_2\in C θx1+(1−θ)x2∈C。
注意到仿射集是凸集的特例。
凸组合 对于 x 1 , ⋯ , x k x_1,\cdots,x_k x1,⋯,xk，称 θ 1 x 1 + ⋯ + θ k x k \theta_1x_1+\cdots+\theta_kx_k θ1x1+⋯+θkxk 为其凸组合，其中 θ 1 , ⋯ , θ k ∈ [ 0 , 1 ] \theta_1,\cdots,\theta_k\in [0,1] θ1,⋯,θk∈[0,1] 且 θ 1 + ⋯ + θ k = 1 \theta_1+\cdots+\theta_k=1 θ1+⋯+θk=1。
定义2 称集合 C C C 是凸集，如果 C C C 中任意元素的凸组合都在 C C C 内。
用跟仿射集相同的方法可证两个定义等价。
凸包
对于集合
C
C
C，定义其凸包为
Conv
C
=
{
θ
1
x
1
+
⋯
+
θ
k
x
k
∣
∀
x
1
,
⋯
,
x
k
∈
C
,
∀
θ
1
,
⋯
,
θ
k
∈
[
0
,
1
]
,
θ
1
+
⋯
+
θ
k
=
1
}
\text{Conv }C=\{\theta_1x_1+\cdots+\theta_kx_k|\forall x_1,\cdots,x_k\in C,\forall \theta_1,\cdots,\theta_k\in [0,1],\theta_1+\cdots+\theta_k=1\}
Conv C={θ1x1+⋯+θkxk∣∀x1,⋯,xk∈C,∀θ1,⋯,θk∈[0,1],θ1+⋯+θk=1}
C
C
C 的凸包为包含
C
C
C 的最小凸集。
凸锥
定义
称集合 C C C 是锥，如果 ∀ x ∈ C \forall x\in C ∀x∈C， ∀ θ ≥ 0 \forall\theta\ge 0 ∀θ≥0，有 θ x ∈ C \theta x\in C θx∈C。
定义1 称集合 C C C 是凸锥，如果 ∀ x 1 , x 2 ∈ C \forall x_1,x_2\in C ∀x1,x2∈C， ∀ θ 1 , θ 2 ≥ 0 \forall\theta_1,\theta_2\ge 0 ∀θ1,θ2≥0，有 x 1 θ 1 + x 2 θ 2 ∈ C x_1\theta_1+x_2\theta_2\in C x1θ1+x2θ2∈C。
凸锥的定义等价于凸的锥。首先凸锥必然是凸的。反过来，若锥
C
C
C 是凸的，那么
∀
x
1
,
x
2
∈
C
\forall x_1,x_2\in C
∀x1,x2∈C，
∀
θ
1
,
θ
2
≥
0
\forall \theta_1,\theta_2\ge 0
∀θ1,θ2≥0，由凸性可知
θ
1
θ
1
+
θ
2
x
1
+
θ
2
θ
1
+
θ
2
x
2
∈
C
\frac{\theta_1}{\theta_1+\theta_2}x_1+\frac{\theta_2}{\theta_1+\theta_2}x_2\in C
θ1+θ2θ1x1+θ1+θ2θ2x2∈C
由锥性可知
θ
1
x
1
+
θ
2
x
2
∈
C
\theta_1x_1+\theta_2x_2\in C
θ1x1+θ2x2∈C。
凸锥组合 对于 x 1 , ⋯ , x k x_1,\cdots,x_k x1,⋯,xk，称 θ 1 x 1 + ⋯ + θ k x k \theta_1x_1+\cdots+\theta_kx_k θ1x1+⋯+θkxk 为其凸锥组合，其中 θ 1 , ⋯ , θ k ≥ 0 \theta_1,\cdots,\theta_k\ge 0 θ1,⋯,θk≥0。
定义2 称集合 C C C 是凸锥，如果 C C C 中任意元素的凸锥组合都在 C C C 内。
单点和空集
对于一个点的集合 C = { x } C=\{x\} C={x}，其必然是仿射集或凸集，但未必是凸锥。空集既是仿射集，又是凸集，也是凸锥。
一些重要的凸集
R n \R^n Rn 空间， R n \R^n Rn 空间的子空间，任意直线，任意线段。
超平面 { x ∣ a T x = b } \{x|a^Tx=b\} {x∣aTx=b}，其中 x , a ∈ R n x,a\in \R^n x,a∈Rn， b ∈ R b\in \R b∈R， a ≠ 0 a\neq 0 a=0。
半空间 { x ∣ a T x ≥ b } \{x|a^Tx\ge b\} {x∣aTx≥b}，其中 x , a ∈ R n x,a\in \R^n x,a∈Rn， b ∈ R b\in \R b∈R， a ≠ 0 a\neq 0 a=0。
球和椭球
球 B ( x c , r ) = { x ∣ ∥ x − x c ∥ 2 ≤ r } B(x_c,r)=\{x\big|\Vert x-x_c\Vert_2\le r\} B(xc,r)={x∣∣∥x−xc∥2≤r}。
证明球是凸集：对于
∀
x
1
,
x
2
∈
B
\forall x_1,x_2\in B
∀x1,x2∈B，
∥
x
1
−
x
c
∥
2
≤
r
\Vert x_1-x_c\Vert_2\le r
∥x1−xc∥2≤r，
∥
x
2
−
x
c
∥
≤
r
\Vert x_2-x_c\Vert\le r
∥x2−xc∥≤r，
∀
0
≤
θ
≤
1
\forall 0\le\theta\le 1
∀0≤θ≤1，有
∥
θ
x
1
+
(
1
−
θ
)
x
2
−
x
c
∥
2
=
∥
θ
(
x
1
−
x
c
)
+
(
1
−
θ
)
(
x
2
−
x
c
)
∥
2
≤
∥
θ
(
x
1
−
x
c
)
∥
2
+
∥
(
1
−
θ
)
(
x
2
−
x
c
)
∥
2
=
θ
∥
x
1
−
x
c
∥
2
+
(
1
−
θ
)
∥
x
2
−
x
c
∥
2
≤
r
\begin{aligned} &\Vert \theta x_1+(1-\theta)x_2-x_c\Vert_2\\ =&\Vert \theta(x_1-x_c)+(1-\theta)(x_2-x_c)\Vert_2\\ \le &\Vert\theta(x_1-x_c)\Vert_2+\Vert(1-\theta)(x_2-x_c)\Vert_2\\ =&\theta\Vert x_1-x_c\Vert_2+(1-\theta)\Vert x_2-x_c\Vert_2\\ \le &r \end{aligned}
=≤=≤∥θx1+(1−θ)x2−xc∥2∥θ(x1−xc)+(1−θ)(x2−xc)∥2∥θ(x1−xc)∥2+∥(1−θ)(x2−xc)∥2θ∥x1−xc∥2+(1−θ)∥x2−xc∥2r
椭球 ϵ ( x c , P ) = { x ∣ ( x − x c ) T P − 1 ( x − x c ) ≤ 1 } \epsilon(x_c,P)=\{x|(x-x_c)^TP^{-1}(x-x_c)\le 1\} ϵ(xc,P)={x∣(x−xc)TP−1(x−xc)≤1}。其中 x c ∈ R n x_c\in \R^n xc∈Rn， P ∈ S + + n P\in S^n_{++} P∈S++n 是一个 n n n 维正定对称矩阵。这里 ( x − x c ) T P − 1 ( x − x c ) (x-x_c)^TP^{-1}(x-x_c) (x−xc)TP−1(x−xc) 可以看成是一个加权二范数。
多面体和单纯形
多面体 P = { x ∣ a j T x ≤ b j ( j = 1 , ⋯ , m ) , c j T x = d j ( j = 1 , ⋯ , p ) } P=\{x|a_j^Tx\le b_j(j=1,\cdots,m),c_j^Tx=d_j(j=1,\cdots,p)\} P={x∣ajTx≤bj(j=1,⋯,m),cjTx=dj(j=1,⋯,p)}。即若干个半空间和超平面的交集。多面体可能是*的。
单纯形
R
n
\R^n
Rn 空间中选择
v
0
,
⋯
,
v
k
v_0,\cdots,v_k
v0,⋯,vk 共
k
+
1
k+1
k+1 个点，
v
1
−
v
0
,
⋯
,
v
k
−
v
0
v_1-v_0,\cdots,v_k-v_0
v1−v0,⋯,vk−v0 线性无关，则与上述点相关的单纯形为
C
=
Conv
{
v
0
,
⋯
,
v
k
}
=
{
θ
0
v
0
+
⋯
+
θ
k
v
k
∣
θ
≥
0
,
1
T
θ
=
1
}
C=\text{Conv}\{v_0,\cdots,v_k\}=\{\theta_0v_0+\cdots+\theta_kv_k|\theta\ge 0,1^T\theta=1\}
C=Conv{v0,⋯,vk}={θ0v0+⋯+θkvk∣θ≥0,1Tθ=1}
证明单纯形是多面体的一种：
对于 x ∈ C ⊆ R n x\in C\subseteq \R^n x∈C⊆Rn， C C C 是单纯形等价于 x = θ 0 v 0 + ⋯ + θ k v k ∈ C x=\theta_0v_0+\cdots+\theta_kv_k\in C x=θ0v0+⋯+θkvk∈C，其中 1 T θ = 1 1^T\theta=1 1Tθ=1， θ ≥ 0 \theta\ge 0 θ≥0 且 v 1 − v 0 , ⋯ , v k − v 0 v_1-v_0,\cdots,v_k-v_0 v1−v0,⋯,vk−v0 线性无关。
定义
[
θ
1
,
⋯
,
θ
k
]
T
=
y
[\theta_1,\cdots,\theta_k]^T=y
[θ1,⋯,θk]T=y，那么
y
≥
0
y\ge 0
y≥0，
1
T
y
=
1
1^Ty=1
1Ty=1。
[
v
1
−
v
0
,
⋯
,
v
k
−
v
0
]
=
B
∈
R
n
×
k
[v_1-v_0,\cdots,v_k-v_0]=B\in \R^{n\times k}
[v1−v0,⋯,vk−v0]=B∈Rn×k。那么
x
∈
C
x\in C
x∈C 等价于
x
=
θ
0
v
0
+
⋯
+
θ
k
v
k
=
v
0
+
θ
1
(
v
1
−
v
0
)
+
⋯
+
θ
k
(
v
k
−
v
0
)
=
v
0
+
B
y
x=\theta_0v_0+\cdots+\theta_kv_k=v_0+\theta_1(v_1-v_0)+\cdots+\theta_k(v_k-v_0)=v_0+By
x=θ0v0+⋯+θkvk=v0+θ1(v1−v0)+⋯+θk(vk−v0)=v0+By
由于
B
B
B 中列向量线性无关，有
r
a
n
k
(
B
)
=
k
rank(B)=k
rank(B)=k。则存在线性变换
A
=
[
A
1
A
2
]
∈
R
n
×
n
A=\begin{bmatrix}A_1\\ A_2\end{bmatrix}\in \R^{n\times n}
A=[A1A2]∈Rn×n 将其变为
A
B
=
[
A
1
A
2
]
B
=
[
I
k
0
]
AB=\begin{bmatrix} A_1\\ A_2 \end{bmatrix}B =\begin{bmatrix} I_k\\ 0 \end{bmatrix}
AB=[A1A2]B=[Ik0]
A
A
A 满足为非奇异矩阵，即所有奇异值非零。在
x
=
v
0
+
B
y
x=v_0+By
x=v0+By 两侧同乘
A
A
A，得到
x
=
v
0
+
B
y
⇔
A
x
=
A
x
0
+
A
B
y
⇔
[
A
1
A
2
]
x
=
[
A
1
A
2
]
v
0
+
[
A
1
B
A
2
B
]
y
⇔
{
A
1
x
=
A
1
v
0
+
y
A
2
x
=
A
2
v
0
⇔
{
A
1
x
≥
A
1
v
0
1
T
A
1
x
=
1
+
1
T
A
1
v
0
A
2
x
=
A
2
v
0
\begin{aligned} &x=v_0+By\\ \Leftrightarrow &Ax=Ax_0+ABy\\ \Leftrightarrow &\begin{bmatrix} A_1\\ A_2 \end{bmatrix}x= \begin{bmatrix} A_1\\ A_2 \end{bmatrix}v_0+ \begin{bmatrix} A_1B\\ A_2B \end{bmatrix}y\\ \Leftrightarrow & \begin{cases} A_1x=A_1v_0+y\\A_2x=A_2v_0 \end{cases}\\ \Leftrightarrow &\begin{cases} A_1x\ge A_1v_0\\ 1^TA_1x=1+1^TA_1v_0\\ A_2x=A_2v_0 \end{cases} \end{aligned}
⇔⇔⇔⇔x=v0+ByAx=Ax0+ABy[A1A2]x=[A1A2]v0+[A1BA2B]y{A1x=A1v0+yA2x=A2v0⎩⎪⎨⎪⎧A1x≥A1v01TA1x=1+1TA1v0A2x=A2v0
其中第三个等价是因为
A
2
v
0
=
0
A_2v_0=0
A2v0=0，第四个等价是代入了
y
≥
0
,
1
T
y
=
1
y\ge 0,1^Ty=1
y≥0,1Ty=1 的两个限制。表明单纯性可由上述若干个等式和不等式约束来描述。
矩阵凸集
对称矩阵集合 S n = { x ∈ R n × n ∣ x = x T } S^n=\{x\in \R^{n\times n}|x=x^T\} Sn={x∈Rn×n∣x=xT}。
对称半正定矩阵集合 S + n = { x ∈ R n × n ∣ x = x T , x ⪰ 0 } S^n_+=\{x\in \R^{n\times n}|x=x^T,x\succeq 0\} S+n={x∈Rn×n∣x=xT,x⪰0}，其中 X ⪰ 0 X\succeq 0 X⪰0 表示 X X X 的所有奇异值均非负。
对称正定矩阵集合 S + + n = { x ∈ R n × n ∣ x = x T , x ≻ 0 } S_{++}^n=\{x\in \R^{n\times n}|x=x^T,x\succ 0\} S++n={x∈Rn×n∣x=xT,x≻0}。
证明
S
+
n
S_+^n
S+n 是凸锥：
∀
θ
1
,
θ
2
≥
0
\forall \theta_1,\theta_2\ge 0
∀θ1,θ2≥0，
∀
A
,
B
∈
S
+
n
\forall A,B\in S_+^n
∀A,B∈S+n，往证
θ
1
A
+
θ
2
B
∈
S
+
n
\theta_1A+\theta_2B\in S_+^n
θ1A+θ2B∈S+n。由于
∀
x
∈
R
n
\forall x\in \R^n
∀x∈Rn，
x
T
A
x
≥
0
,
x
T
B
x
≥
0
x^TAx\ge 0,x^TBx\ge 0
xTAx≥0,xTBx≥0，有
x
T
(
θ
1
A
+
θ
2
B
)
x
=
x
T
θ
1
A
x
+
x
T
θ
2
B
x
≥
0
x^T(\theta_1A+\theta_2B)x=x^T\theta_1Ax+x^T\theta_2Bx\ge 0
xT(θ1A+θ2B)x=xTθ1Ax+xTθ2Bx≥0
因此
S
+
n
S_+^n
S+n 是凸锥。
显然对称矩阵集合是凸锥。
但 S + + n S_{++}^n S++n 不是凸锥。当 n = 1 n=1 n=1 时， S + n = R + S_+^n=\R_+ S+n=R+， S + + n = R + + S_{++}^n=\R_{++} S++n=R++， S n = R S^n=\R Sn=R。显然 R + + R_{++} R++ 不是凸锥。考虑 n n n 更大的时候，在 S n = S_n^= Sn= 是凸锥的证明中最后一步不能用大于号，因为 θ 1 , θ 2 \theta_1,\theta_2 θ1,θ2 可以同时为 0 0 0。