首页课程笔记自动化系凸优化

# 定义与例子

  1. 范数：满足以下四个条件的任意函数 f:V→Rf: V \to \mathbb{R} 称为范数：

    • 非负性：∀x∈V,f(x)≥0\forall x \in V, f(x) \geq 0，且 f(x)=0  ⟺  x=0f(x) = 0 \iff x = 0；
    • 齐次性：∀x∈V,∀α∈R,f(αx)=∣α∣f(x)\forall x \in V, \forall \alpha \in \mathbb{R}, f(\alpha x) = |\alpha| f(x)；
    • 三角不等式：∀x,y∈V,f(x+y)≤f(x)+f(y)\forall x, y \in V, f(x + y) \leq f(x) + f(y)。

  2. 仿射 affine

    • 仿射子空间：给定矩阵 A∈Rm×nA \in \mathbb{R}^{m \times n} 和向量 b∈Rmb \in \mathbb{R}^m，集合 {x∈Rn∣Ax=b}\{x \in \mathbb{R}^n | Ax = b\} 称为仿射子空间。
    • 仿射变换：从 Rn\mathbb{R}^n 到 Rm\mathbb{R}^m 的映射 f(x)=Ax+bf(x) = Ax + b，其中 A∈Rm×nA \in \mathbb{R}^{m \times n}，b∈Rmb \in \mathbb{R}^m。
    • 仿射函数：仿射变换的一种特殊情况，当 m=1m = 1 时，AA 是行向量，y,by, b 是标量，称为仿射函数。
    • 线性函数：当 b=0b = 0 时，仿射函数退化为线性函数。

  3. 点与线

    • 点 Point：{x}\{x\}，其中 x∈Rnx \in \mathbb{R}^n。
    • 线 Line：L={x∣λx1+(1−λ)x2,λ∈R}L = \{x | \lambda x_1 + (1 - \lambda) x_2, \lambda \in \mathbb{R}\}，其中 x1,x2∈Rnx_1, x_2 \in \mathbb{R}^n。
    • 线段 Line Segment：LS={x∣λx1+(1−λ)x2,λ∈[0,1]}LS = \{x | \lambda x_1 + (1 - \lambda) x_2, \lambda \in [0, 1]\}，其中 x1,x2∈Rnx_1, x_2 \in \mathbb{R}^n。
    • 射线 Ray：R={x∣x1+λ(x2−x1),λ∈R+}R = \{x | x_1 + \lambda (x_2 - x_1), \lambda \in \mathbb{R}_+\}，其中 x1,x2∈Rnx_1, x_2 \in \mathbb{R}^n。

  4. 仿射集 Affine Set：对于任意 x1,x2∈Cx_1, x_2 \in C 和 ∀λ∈R\forall \lambda \in \mathbb{R}，都有 λx1+(1−λ)x2∈C\lambda x_1 + (1 - \lambda) x_2 \in C。

    • 定理：任意仿射子空间都是仿射集（证明）
    • 定理：任意仿射集都可以被表示为某个线性方程的解（证明）

  5. 凸集 Convex Set：对于任意 x1,x2∈Cx_1, x_2 \in C 和 ∀λ∈[0,1]\forall \lambda \in [0, 1]，都有 λx1+(1−λ)x2∈C\lambda x_1 + (1 - \lambda) x_2 \in C。

    • 典型的凸集：
      • 点（Point）、线（Line）、射线（Ray）、仿射子空间（Affine Subspace）
      • 超平面（Hyperplane）、半空间（Half Space）、多面体（Polyhedral）、凸包（Convex Hull）
      • 锥（Cone）、锥包（Conic Hull）、半正定矩阵锥（SDP Cone）
      • 球（Ball）、椭球（Ellipsoid）
    • 定理：有限个凸集的交集仍然是凸集（证明）

  6. 球 Ball

    • 开球 OpenBall： B(xc,r)={x∣∥x−xc∥2<r}B(x_c, r) = \{x | \|x - x_c\|_2 < r\}，其中 xc∈Rnx_c \in \mathbb{R}^n 是球心，r>0r > 0 是半径。
    • 闭球 ClosedBall： Bˉ(xc,r)={x∣∥x−xc∥2≤r}\bar{B}(x_c, r) = \{x | \|x - x_c\|_2 \leq r\}，其中 xc∈Rnx_c \in \mathbb{R}^n 是球心，r>0r > 0 是半径。
    • 定理：球是凸集（证明）

  7. 超平面 Hyperplane：H={x∣hTx=b}H = \{x | h^T x = b\}，其中 h∈Rn\{0}h \in \mathbb{R}^n \backslash \{0\} 是法向量，b∈Rb \in \mathbb{R}。

    • 定理：法线方向 hh 与超平面 HH 上所有直线正交（证明）
    • 定理：超平面是凸集（证明）

  8. 半空间 Half Space

    • 开半空间 Open Half Space：H={x∣hTx<b}H = \{x | h^T x < b\}，其中 h∈Rn\{0}h \in \mathbb{R}^n \backslash \{0\}，b∈Rb \in \mathbb{R}。
    • 闭半空间 Closed Half Space：H={x∣hTx≤b}H = \{x | h^T x \leq b\}，其中 h∈Rn\{0}h \in \mathbb{R}^n \backslash \{0\}，b∈Rb \in \mathbb{R}。
    • 定理：半空间是凸集（证明）

  9. 边界点 Boundary Point：对于任意 ϵ>0\epsilon > 0，开球 B(x,ϵ)B(x, \epsilon) 同时包含 CC 中的点和 Rn\C\mathbb{R}^n \backslash C 中的点，则称 xx 是 CC 的边界点。

    • ∂C\partial C：CC 的边界点集合。
    • 闭集 Closed Set：∂C⊆C\partial C \subseteq C。
    • 开集 Open Set：∂C∩C=∅\partial C \cap C = \emptyset，即 Rn\C\mathbb{R}^n \backslash C 是闭集。
    • 闭包 Closure：CC 的闭包 Cˉ=C∪∂C\bar{C} = C \cup \partial C。
      • CC 是闭集   ⟺  Cˉ=C\iff \bar{C} = C。
    • 内部 Interior：CC 的内部 C∘=C\∂CC^\circ = C \backslash \partial C。
      • CC 是开集   ⟺  C=C∘\iff C = C^\circ。
    • 内点 Interior Point：属于 C∘C^\circ 的点称为内点。

  10. 极点/顶点 Extreme Point：x∈Cx \in C 是极点当且仅当不存在两个不同的点 x1,x2∈Cx_1, x_2 \in C 和 λ∈(0,1)\lambda \in (0, 1) 使得 x=λx1+(1−λ)x2x = \lambda x_1 + (1 - \lambda) x_2。

  11. 多面体 Polyhedron：由有限个仿射不等式的解集构成的集合，P={x∣aiTx≤bi,i=1,…,m}P = \{x | a_i^T x \leq b_i, i = 1, \ldots, m\}，其中 ai∈Rna_i \in \mathbb{R}^n，bi∈Rb_i \in \mathbb{R}

    • 一个多面体可以视为有限个闭半空间的交集。
    • 也可记为 P={x∣Ax≤b}P = \{x | Ax \leq b\}，其中 A∈Rm×nA \in \mathbb{R}^{m \times n}，b∈Rmb \in \mathbb{R}^m。
    • 定理：多面体是凸集（证明）

  12. 锥 Cone：对于任意 x∈Cx \in C 和 ∀λ≥0\forall \lambda \geq 0，都有 λx∈C\lambda x \in C。

    • 凸锥：对于任意 x1,x2∈Cx_1, x_2 \in C 和 ∀λ1,λ2≥0\forall \lambda_1, \lambda_2 \geq 0，都有 λ1x1+λ2x2∈C\lambda_1 x_1 + \lambda_2 x_2 \in C。
    • 锥的交集仍然是锥（证明）
    • 0 是锥 CC 的极点，当且仅当 rank(C)=nrank(C) = n（证明）

  13. 正常锥 Proper Cone，当且仅当

    • K\mathcal{K} 是凸集 Convex
    • K\mathcal{K} 是闭集 Closed
    • K\mathcal{K} 是实心 Solid，即 K\mathcal{K} 有非空的内部
    • K\mathcal{K} 是尖的 Pointed，即 K\mathcal{K} 不包含任何直线（若 x∈Kx \in \mathcal{K} 且 −x∈K-x \in \mathcal{K}，则 x=0x = 0）

  14. 凸组合与凸包

    • 凸组合 Convex Combination：对于 x1,…,xk∈Rnx_1, \ldots, x_k \in \mathbb{R}^n，其凸组合定义为 ∑i=1kθixi\sum_{i=1}^k \theta_i x_i，其中 θi≥0,i=1,…,k\theta_i \geq 0, i = 1, \ldots, k 且 ∑i=1kθi=1\sum_{i=1}^k \theta_i = 1。
    • 凸包 Convex Hull：给定集合 CC，其凸包定义为包含 CC 的所有凸集的交集，记为 conv(C)conv(C)，即包含 CC 的最小凸集。
    • 凸组合和凸包等价（证明）

  15. 锥组合与锥包

    • 锥组合 Conic Combination：对于 x1,…,xk∈Rnx_1, \ldots, x_k \in \mathbb{R}^n，其锥组合定义为 ∑i=1kλixi\sum_{i=1}^k \lambda_i x_i，其中 λi≥0,i=1,…,k\lambda_i \geq 0, i = 1, \ldots, k。
    • 锥包 Conic Hull：给定集合 CC，其锥包定义为包含 CC 的所有凸锥的交集，记为 cone(C)cone(C)，即包含 CC 的最小凸锥。
    • 锥组合和锥包等价（证明）

  16. 仿射组合与仿射包

    • 仿射组合 Affine Combination：对于 x1,…,xk∈Rnx_1, \ldots, x_k \in \mathbb{R}^n，其仿射组合定义为 ∑i=1kθixi\sum_{i=1}^k \theta_i x_i，其中 ∑i=1kθi=1\sum_{i=1}^k \theta_i = 1。
    • 仿射包 Affine Hull：给定集合 CC，其仿射包定义为包含 CC 的所有仿射集的交集，记为 aff(C)aff(C)，即包含 CC 的最小仿射集。
    • 仿射组合和仿射包等价（证明）
    • 仿射包是凸的（证明）

  17. 单纯型 Simplex：对 Rn\mathbb{R}^n 中的 n+1n + 1 个仿射无关点 x0,x1,…,xnx_0, x_1, \ldots, x_n，其凸包称为单纯型

  18. 有界多面体 Polytope：即有界的多面体 bounded polyhedron

  19. 半正定矩阵 PSD Matrice：记 n×nn \times n 的实对称矩阵的集合为 SnS^n，则 S+nS^n_+ 表示所有半正定矩阵的集合。以下表述等价（证明）：

    • A∈SnA \in S^n 是半正定的
    • xTAx≥0,∀x∈Rnx^T A x \geq 0, \forall x \in \mathbb{R}^n
    • AA 的所有特征值非负
    • AA 的所有主子式 Principal Minor 非负
    • 存在矩阵 BB 使得 A=BTBA = B^T B

  20. 正定矩阵：记 n×nn \times n 的实对称矩阵的集合为 SnS^n，则 S++nS^n_{++} 表示所有正定矩阵的集合。以下表述等价（证明）：

    • A∈SnA \in S^n 是正定的
    • xTAx>0,∀x∈Rn,x≠0x^T A x > 0, \forall x \in \mathbb{R}^n, x \neq 0
    • AA 的所有特征值均为正
    • AA 的所有主子式 Principal Minor 均为正
    • 存在矩阵 BB 使得 A=BTBA = B^T B，且 BB 是可逆的

  21. 实对称矩阵可以通过正交变换对角化（证明）

  22. 半正定锥 Positive Semidefinite Cone：{X∈Sn∣X⪰0}\{X \in S^n | X \succeq 0\}，原因在于任意两个半正定矩阵相加，得到的仍然是一个半正定矩阵；一个半正定矩阵乘以一个非负数，得到的也仍然是半正定矩阵，这满足锥的定义。

    • 注意：半正定锥是所有半正定矩阵的集合，意味着仅需满足对称半正定，不存在额外的约束条件。
    • 半正定锥是凸的

  23. 线性矩阵不等式 LMI：F(x)=F0+∑i=1mxiFi⪰0F(x) = F_0 + \sum_{i=1}^m x_i F_i \succeq 0，其中 Fi∈Sn,i=0,1,…,mF_i \in S^n, i = 0, 1, \ldots, m。

    • 任意半正定锥都可以写成 LMI 的形式
    • 如果附加了其它约束，需要考虑是否仍然是凸集。当附加约束是线性的，则相当于对半正定锥进行线性切割，仍然是凸集，例如对 R2\mathbb{R}^2 表示的 3D 半正定锥附加线性约束 x1+x2=1x_1 + x_2 = 1，将得到 2D 的椭圆等；如果附加约束是非线性的，则需要具体问题具体分析

  24. 相限 Orthant

    • 正相限 Positive Orthant：R+n={x∈Rn∣xi>0,i=1,…,n}\mathbb{R}^n_+ = \{x \in \mathbb{R}^n | x_i > 0, i = 1, \ldots, n\}。
    • 非负相限 Nonnegative Orthant：R+n={x∈Rn∣xi≥0,i=1,…,n}\mathbb{R}^n_+ = \{x \in \mathbb{R}^n | x_i \geq 0, i = 1, \ldots, n\}。

  25. 洛伦兹锥 Lorentz Cone：xn≥x12+x22+…+xn−12x_n \geq \sqrt{x_1^2 + x_2^2 + \ldots + x_{n-1}^2}，其中 x=(x1,x2,…,xn)∈Rnx = (x_1, x_2, \ldots, x_n) \in \mathbb{R}^n。

    • 3D 空间中的洛伦兹锥也称为冰淇淋锥 Ice-Cream Cone。

  26. 半正定矩阵和椭球 Ellipoid：任意一个 PSD 矩阵 AA 对应一个椭圆 xTAx≤1x^T A x \leq 1

# 广义不等式

  1. 序结构与偏序关系 Partial Ordering

    • 序结构是布尔巴基学派“三大结构”之一，由集合及其上的序关系组成。
    • 偏序关系（Partial Ordering）满足以下性质：
      • 加法封闭性（Additive）：若 x⪯yx \preceq y 且 u⪯vu \preceq v，则 x+u⪯y+vx + u \preceq y + v。
      • 传递性（Transitive）：若 x⪯yx \preceq y 且 y⪯zy \preceq z，则 x⪯zx \preceq z。
      • 非负标量封闭性（Non-negative Scaling）：若 x⪯yx \preceq y，则 θx⪯θy\theta x \preceq \theta y，∀θ≥0\forall \theta \geq 0。
      • 自反性（Reflexive）：x⪯xx \preceq x。
      • 反对称性（Antisymmetric）：若 x⪯yx \preceq y 且 y⪯xy \preceq x，则 x=yx = y。

  2. 锥与偏序关系

    • 对于某些凸集，尤其是凸锥，可以借助锥的结构在集合上引入偏序关系。
    • 任意 Rn\mathbb{R}^n 上的适当凸锥 (proper cone) KK 都可以诱导出广义不等式（generalized inequalities）。记作 ⪰K\succeq_K:

      a⪰Kb  ⟺  a−b∈Ka \succeq_K b \iff a - b \in K

    • 如果 KK 是正正交锥（positive orthant）R+n={x∣xi≥0}\mathbb{R}^n_+=\{x | x_i\geq 0\}，则诱导出分量上的不等式（坐标逐分量不等式）：

      x⪰y  ⟺  xi≥yi,∀ix \succeq y \iff x_i \geq y_i, \quad \forall i

  3. 常见的广义不等式

    • 坐标分量不等式：R+n\mathbb{R}^n_+ 上 x⪰yx \succeq y 表示 xx 每个分量都不小于 yy。
    • Löwner偏序（Löwner Partial Order）：用于实对称矩阵集合 SnS^n 上，定义如下：

      A⪰B  ⟺  A−B⪰0A \succeq B \iff A - B \succeq 0

      其中 A⪰0A \succeq 0 表示 AA 是半正定矩阵，即对于任意 x∈Rnx\in \mathbb{R}^n，xT(A−B)x≥0x^T (A-B)x \geq 0。

# 保凸运算

# 分析集合凸性的常用实际方法

判断集合 CC 是否为凸集，常用的实用方法主要有以下两类：

  1. 直接利用定义检验
    检查集合是否满足凸集定义：对于任意 x1,x2∈Cx_1, x_2 \in C 及任意 0≤θ≤10 \leq \theta \leq 1，都有

    θx1+(1−θ)x2∈C\theta x_1 + (1-\theta)x_2 \in C

    对于简单集合或低维情形可以直接操作验证。

  2. 通过保凸运算间接证明
    许多常见集合可以通过 “原子” 凸集（如超平面、半空间、单位球、椭球等）经过一系列保凸运算得到，这些保凸运算会保留凸性：

    • 任意多个凸集的交 仍为凸集。
    • 仿射变换的像和原象 保持凸性：
      • 设 f(x)=Ax+bf(x) = Ax+b 是仿射变换 (A∈Rm×nA\in\mathbb{R}^{m\times n})，若 S⊂RnS\subset\mathbb{R}^n 是凸集，则 f(S)={Ax+b ∣ x∈S}f(S)=\{Ax+b\,|\,x\in S\} 也是凸集。
      • C⊂RmC\subset\mathbb{R}^m 是凸集，则 f−1(C)={x∈Rn ∣ Ax+b∈C}f^{-1}(C)=\{x\in\mathbb{R}^n\,|\,Ax+b\in C\} 也是凸集。
      • 例如缩放、平移、投影、线性约束等。
    • 投影：凸集的投影（对某些变量积分掉）仍为凸集。
    • perspective 函数 P(x,t)=x/t, t>0P(x, t) = x / t,\, t > 0 的像和原象都保持凸性。
    • 线性分式变换 f(x)=Ax+bcTx+df(x) = \frac{Ax + b}{c^Tx + d} 的像和原象也都保持凸性（cTx+d>0c^Tx + d > 0 时）。
    • 线性矩阵不等式集 {x ∣ x1A1+⋯+xmAm⪯B}\{x\,|\,x_1A_1+\dots+x_mA_m \preceq B\} 这样的集合也是凸集。
    • 双曲锥 {x ∣ xn≥x12+⋯+xn−12}\{x\,|\,x_n \geq \sqrt{x_1^2+\dots+x_{n-1}^2}\} 也是凸集，可通过保凸运算证明其凸性。

# 证明举例

  • 设 A∈Rm×nA\in\mathbb{R}^{m\times n}，若 S⊂RmS\subset\mathbb{R}^m 是凸集，则 A−1(S):={x∈Rn∣Ax∈S}A^{-1}(S):=\{x\in\mathbb{R}^n|Ax\in S\} 也是凸集。

    证明：任取 x,y∈A−1(S)x, y \in A^{-1}(S)，则 Ax,Ay∈SAx, Ay \in S。对任意 t∈[0,1]t\in[0,1]，有 A(tx+(1−t)y)=tAx+(1−t)Ay∈SA(tx + (1-t)y) = tAx + (1-t)Ay \in S，因 SS 是凸集。于是 tx+(1−t)y∈A−1(S)tx + (1-t)y \in A^{-1}(S)。

    这种原象集的证明方法也适用于线性矩阵不等式的解集等。

  • 设 Bi,Ai∈S+nB_i, A_i \in S^n_+，则 {x ∣ ∑i=1kxiAi⪯B}\{x\,|\,\sum_{i=1}^k x_iA_i \preceq B\} 是凸集。原理：这个集合是关于仿射映射的原象集。

  • perspective 函数 P(x,t)=x/t, t>0P(x,t) = x/t,\,t>0 以及其逆的像、原象都能保持凸性。这意味着如归一化、投影等操作下凸性得以保留。

  • 线性分式变换 f(x)=Ax+bcTx+df(x) = \frac{Ax+b}{c^Tx+d} （定义域 cTx+d>0c^Tx+d > 0）可以将凸集映射到凸集（像/原象）。

结合这些保凸运算和“凸集构建树”，常遇复杂集合可分解为上述基本集合与这些操作，间接证明其凸性。

常用技巧总结：

  • 若集合可表达为已知凸集的交或仿射变换像/原象，则直接引用保凸运算即可断定其凸性，无须手工逐点检验。
  • 针对线性矩阵不等式、投影、比例缩放、归一化、线性分式变换等，经常可以转化为“已知凸集+保凸运算”的套路。
  • 复杂集合可尝试分解为以上保凸运算的组合。

# 凸集分离

# 测试问题