HomeBlogTopicsPublish

  • rss

  • contact

© 2025 MIT Licensed

Topics→Machine Learning→Convex

Machine Learning

Fundamentals
Decision TreeBackpropagationLinear 1Linear 2Linear 3Linear DualLinear IntroML Numerical MethodsNaive SolveLagrangian Conditions under Equality ConstraintsLagrangian Conditions under Inequality ConstraintsSupport Vector Machine 1Support Vector Machine 2Support Vector Machine 3Convex
Deep Learning Acceleration
Paper DartsPaper MobileNetsPaper ShuffleNetPaper HashingTricksPaper ShuffleNetV2Neural Architecture Search MilestonePyTorch Training Acceleration
Computer Vision
Paper RobotPaper InceptionV4Dataset Cityscapes
Reinforcement Learning
Paper Deep Q-Network

Convex

August 16, 2018

by Frank

通常认为，如果某个实际问题可以表述为凸优化问题，那么事实上已经解决了这个问题，然而凸优化问题的识别还比较困难，本文将先介绍凸集的定义与常见凸集。

通常认为，如果某个实际问题可以表述为凸优化问题，那么事实上已经解决了这个问题，然而凸优化问题的识别还比较困难，本文将先介绍凸集的定义与常见凸集。

仿射集

如果集合 C⊆RnC\subseteq R^{n}C⊆Rn 是仿射的，等价于：对于任意的 x1,x2∈Cx_{1},x_{2}\in Cx1​,x2​∈C 及 θ∈R\theta \in Rθ∈R 有 θx1+(1−θ)x2∈C\theta x_{1}+(1-\theta)x_{2}\in Cθx1​+(1−θ)x2​∈C ，即 CCC 包含了 CCC 中任意两点的系数之和为 1 的线性组合。

将其扩展到多个点的情况：如果 θ1+θ2+...+θk=1\theta_{1}+\theta_{2}+...+\theta_{k}=1θ1​+θ2​+...+θk​=1 ，我们则称具有 θ1x1+θ2x2+...+θkxk\theta_{1}x_{1}+\theta_{2}x_{2}+...+\theta_{k}x_{k}θ1​x1​+θ2​x2​+...+θk​xk​ 形式的点为 x1,x2,...,xkx_{1},x_{2},...,x_{k}x1​,x2​,...,xk​ 的仿射组合。例如线性方程组的解集 C={x∣Ax=b}C=\{x|Ax=b\}C={x∣Ax=b}是一个仿射集。

称由集合 C⊆RnC\subseteq R^{n}C⊆Rn 中点的所有仿射组合所组成的集合为 CCC 的仿射包：

aff C={θ1x1+...+θkxk∣x1,...,xk∈C,θ1+θ2+...+θk=1}\mathrm{aff}\ C=\{\theta_{1}x_{1}+...+\theta_{k}x_{k}|x_{1},...,x_{k}\in C,\theta_{1}+\theta_{2}+...+\theta_{k}=1\}aff C={θ1​x1​+...+θk​xk​∣x1​,...,xk​∈C,θ1​+θ2​+...+θk​=1}

仿射包是包含 CCC 的最小的仿射集合，即如果集合 SSS 满足 C⊆SC\subseteq SC⊆S，则 aff C⊆S\mathrm{aff}\ C\subseteq Saff C⊆S ，同时将集合 CCC 的仿射维数定义为其仿射包的维数。例如 R2R^{2}R2 上的单位圆环的维数为 1，但其仿射维数为 2，因为其仿射包为全空间 R2R^{2}R2

凸集

如果集合 CCC 为凸集，那么对于任意的 x1,x2∈Cx_{1},x_{2}\in Cx1​,x2​∈C 与0≤θ≤10\le \theta\le 10≤θ≤1都有 θx1+(1−θ)x2∈C\theta x_{1}+(1-\theta)x_{2}\in Cθx1​+(1−θ)x2​∈C，与仿射集的区别在于仿射集并没有 θ≥0\theta\ge0θ≥0 的要求，例如一条线段是凸集，而一条直线是仿射集。

扩展到多维的情况，如果有 θ1+θ2+...+θk=1,θi≥0\theta_{1}+\theta_{2}+...+\theta_{k}=1,\theta_{i}\ge0θ1​+θ2​+...+θk​=1,θi​≥0 ，则称具有 θ1x1+θ2x2+...+θkxk\theta_{1}x_{1}+\theta_{2}x_{2}+...+\theta_{k}x_{k}θ1​x1​+θ2​x2​+...+θk​xk​ 形式的点为 x1,x2,...,xkx_{1},x_{2},...,x_{k}x1​,x2​,...,xk​ 的凸组合。

称由集合 C⊆RnC\subseteq R^{n}C⊆Rn 中点的所有凸组合所组成的集合为 CCC 的凸包：

conv C={θ1x1+...+θkxk∣x1,...,xk∈C,θ1+...+θk=1,θi≥0}\mathrm{conv}\ C=\{\theta_{1}x_{1}+...+\theta_{k}x_{k}|x_{1},...,x_{k}\in C,\theta_{1}+...+\theta_{k}=1,\theta_{i}\ge0\}conv C={θ1​x1​+...+θk​xk​∣x1​,...,xk​∈C,θ1​+...+θk​=1,θi​≥0}

与仿射包同样，凸包也是包含 CCC 的最小的凸集，在一般情况下，设 C∈RnC\in R^{n}C∈Rn 是凸集，xxx 是随机变量，并且 x∈Cx\in Cx∈C 的概率为 1，那么 E x∈CE\ x\in CE x∈C

一些重要的凸集

识别出凸集对于识别凸优化问题较为重要，这里将介绍一些比较重要的凸集。

任意的仿射集和子空间都是凸集，一些比较简单的例如空集 ∅\emptyset∅ ，单点集{x0}\{x_{0}\}{x0​}，全空间 RnR^{n}Rn ，直线/射线/线段都是凸的。

还有一些比较重要的凸集如下：

  1. 超平面 {x∣aTx=b}\{x|a^{T}x=b \}{x∣aTx=b}和半空间 {x∣aTx≤b}\{x|a^{T}x\le b\}{x∣aTx≤b}
  2. Euclid 球 B(xc,r)={x∣ ∣∣x−xc∣∣2≤r}B(x_{c},r)=\{x|\ ||x-x_{c}||_{2}\le r\}B(xc​,r)={x∣ ∣∣x−xc​∣∣2​≤r}
  3. 椭球 ξ={x∣(x−xc)TP−1(x−xc)≤1}\xi=\{x|(x-x_{c})^{T}P^{-1}(x-x_{c})\le1\}ξ={x∣(x−xc​)TP−1(x−xc​)≤1}
  4. 范数球 {x∣ ∣∣x−xc∣∣≤r}\{x|\ ||x-x_{c}||\le r\}{x∣ ∣∣x−xc​∣∣≤r}，其中 ∣∣⋅∣∣||\cdot||∣∣⋅∣∣ 是 RnR^{n}Rn 中的范数
  5. 范数锥 C={(x,t)∣ ∣∣x∣∣≤t}⊆Rn+1C=\{(x,t)|\ ||x||\le t\}\subseteq R^{n+1}C={(x,t)∣ ∣∣x∣∣≤t}⊆Rn+1
  6. 多面体 P={x∣ajT≤bj,j=1,...,m,cjTx=dj,j=1,...,p}P=\{x|a_{j}^{T}\le b_{j},j=1,...,m,c_{j}^{T}x=d_{j},j=1,...,p\}P={x∣ajT​≤bj​,j=1,...,m,cjT​x=dj​,j=1,...,p}，即为有限个半空间和超平面的交集，单纯形也为凸集，是一种特殊的多面体
  7. 半正定锥 S+n={X∈Rn∗n∣X=XT,X⪰0}S_{+}^{n}=\{X\in R^{n*n}|X=X^{T},X\succeq0\}S+n​={X∈Rn∗n∣X=XT,X⪰0}，即为半正定对称矩阵的集合
←Previous: Support Vector Machine 3Next: Paper Darts→

Comments