相关概念

仿射集（Affine set）：

通过集合C中任意两个不同点的直线仍然在集合C内，则称集合C为仿射集。

比如：

• 直线、平面、超平面

类似于线性变换 。
n维空间的n-1维仿射集为n-1维超平面。

仿射包（Affine hull）：

包含集合C的最小仿射集。

比如：

• 直线的仿射包是它自己。
• 球不是仿射集。

仿射维数：

仿射包的维数。

比如：

• 三角形的仿射维数为2；
• 线段的仿射维数为1；
• 球的仿射维数为3。

仿射——单连通，不能有洞（带洞的是复连通）

内点：

对于集合C中的某个点x，以x为中心做半径为r的球B（r>0，且足够小），若球B完全落在C的内部（即B是C的子集），则x为C的内点。

集合C的仿射包A的内点y，如果y位于C中，则称y为集合c的相对内点relint。（对于集合C中的某个点y，以y为中心做半径为r的球B（r>0，且足够小），若球B和A的交集完全落在C的内部（即B∩A是C的子集），则y为C的相对内点。）
边界 相对边界

凸集（convex set）：

集合C内任意两点间的线段均在集合C内，则称集合C为凸集。

• 所有的三角形都是凸的。
• 任何一个仿射集都是凸集。

以上两种写法其实是一致的。

凸包（convex hull）：

集合C的所有点的凸组合形成的集合，叫做集合C的凸包。

集合C的凸包是能够包含C的最小的凸集。
例题：给定n个离散点，求凸包；给定一个多边形，求凸包。

锥（cones）：

射线是一个锥，n个射线的组合也是锥。
n阶半正定方阵的集合为凸锥。

超平面：

{x|aTx=b}{x|aTx=b}<script type="math/tex" id="MathJax-Element-952">\{x|a^Tx=b\}</script>

半空间：

{x|aTx<b}{x|aTx<b}<script type="math/tex" id="MathJax-Element-953">\{x|a^Tx{x|aTx>b}{x|aTx>b}<script type="math/tex" id="MathJax-Element-954">\{x|a^Tx>b\}</script>
（法向量的方向是>0的，如3x+5y-z+6=0，法向量（3，5，-1），该向量指的方向大于零）

欧式球：

B(xc,r)={x|||x−xc||2≤r}={x|(x−xc)T(x−xc)≤r2}B(xc,r)={x|||x−xc||2≤r}={x|(x−xc)T(x−xc)≤r2}<script type="math/tex" id="MathJax-Element-955">B(x_c,r)=\{x| ||x-x_c||_2\leq r\}=\{x|(x-x_c)^T(x-x_c)\leq r^2\}</script>

椭球：

E={x|(x−xc)TP(x−xc)≤r2}E={x|(x−xc)TP(x−xc)≤r2}<script type="math/tex" id="MathJax-Element-956">E=\{x|(x-x_c)^TP(x-x_c)\leq r^2\}</script>，P为对称正定矩阵

范数

范数球

范数锥

多面体：

有限个半空间和超平面的交集。

• 仿射集、射线、线段、半空间都是多面体。
• 多面体是凸集，所以凸集的交集是凸集。
• 有界的多面体称作多胞形（polytope）

保凸运算

集合交运算 仿射变换 f(x)=Ax+b,A∈Rm×n,b∈Rmf(x)=Ax+b,A∈Rm×n,b∈Rm<script type="math/tex" id="MathJax-Element-526">f(x)=Ax+b,A \in R^{m\times n},b\in R^m </script>，伸缩、平移、投影
两个集合的和、笛卡尔积（直积）、部分和（分配率）为凸集。
透视变换：透视函数对向量进行伸缩（规范化），使得最后一维的分量为1并舍弃之。 P:Rn+1→Rn,P(z,t)=z/tP:Rn+1→Rn,P(z,t)=z/t<script type="math/tex" id="MathJax-Element-527">P:R^{n+1}\rightarrow R^n,P(z,t)=z/t</script>

直观意义：小孔成像

投射变换

投射变换（线性分式函数）：透视函数和仿射函数的复合。

分割与支撑超平面

分割超平面：设C和D为两不相交的凸集，则存在超平面P，P可以将C和D分离。

构造：两个集合间元素的最短距离为两个集合的距离，做集合C和集合D最短线段的垂直平分线。
“若两个凸集C和D的分割超平面存在，C和D不
相交”为假命题。
若两个凸集至少有一个是开集，那
么当且仅当存在分割超平面，它们不相交。

支撑超平面

凸函数

定义：

若函数f的定义域dom f 为凸集，且满足∀x,y∈domf,0≤r≤1,∀x,y∈domf,0≤r≤1,<script type="math/tex" id="MathJax-Element-910">\forall x,y\in dom f,0\leq r\leq 1,</script> 有f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)<script type="math/tex" id="MathJax-Element-911">f(\theta x+(1-\theta)y)\leq \theta f(x)+(1-\theta )f(y)</script>

直观：

• 割线位于函数那条曲线的上方。
• 若f一阶可微，函数图像位于切线图像上方，则为凸函数。

进一步的思考：

• 对于凸函数，其一阶Taylor近似本质上是该函数的全局下估计。
• 反之，如果一个函数的一阶Taylor近似总是起全局下估计，则该函数是凸函数。
• 该不等式说明从一个函数的局部信息，可以得到一定程度的全局信息。
• 若f二阶可微，则函数f为凸函数当且仅当dom为凸集，且二阶导数大于零（若f是一元函数，则二阶导大于等于0；若f是多元函数，则二阶导Hessian矩阵半正定）。

凸函数举例：

• 指数函数、幂函数（a>=1或a<=0）、负对数函数、负熵函数（xlogx）、范数函数等······
• 直线既凸且凹。

上境图（epigraph ）

一个函数是凸函数，当且仅当其上境图是凸集。

亚图（hypograph）

<script type="math/tex; mode=display" id="MathJax-Element-900">hypo f ={(x,t)|t\leq f(x)}</script>
一个函数是凹函数，当且仅当其亚图是凸集。

Jensen不等式

<script type="math/tex; mode=display" id="MathJax-Element-907">f(\theta x+(1-\theta)y)\leq \theta f(x)+(1-\theta )f(y)</script>
（两个变量和k个变量的形式表达意义一样）
若k个变量变为连续，即积分，如p(x)为一个概率密度函数。
得到重要结论如下：

应用

• EM推导用到这个
• KL散度（Kullback–Leibler divergence，相对熵），可证明D(q||p)>=0
• 变分思想：用简单的分布q去近似复杂的分布p，，用D来评估近似程度。

函数保凸：

• 凸函数的非负加权和
• 凸函数与仿射函数的复合
• 凸函数的逐点最大值、逐点上确界f(x)=max(f1(x),...fn(x)f(x)=max(f1(x),...fn(x)<script type="math/tex" id="MathJax-Element-896">f(x)=max(f_1(x),...f_n(x)</script>,f(x)=supy∈Ag(x,y)f(x)=supy∈Ag(x,y)<script type="math/tex" id="MathJax-Element-897">f(x)=sup_{y\in A} g(x,y)</script>（分别是离散情况和连续情况，y是某一维度）

一系列函数逐点上确界函数对应着这些函数上境图的交集。

共轭函数

不论凸凹函数的共轭函数都是凸函数。

Fenchel不等式

凸优化

一般优化问题的基本形式和相关概念：

某个集合X 的子集 E 的下确界(英语：infimum 或infima，记为inf E )是小于或等于的E 所有其他元素的最大元素，其不一定在E內。
x在某一个z定点的周围满足上述性质，则为局部最优。

凸优化问题

f0(x)、fi(x)f0(x)、fi(x)<script type="math/tex" id="MathJax-Element-884">f_0(x)、f_i(x)</script>为凸函数，hj(x)hj(x)<script type="math/tex" id="MathJax-Element-885">h_j(x)</script>为仿射函数。

凸优化问题的重要性质：

• 凸优化问题的可行域为凸集。
• 凸优化问题的局部最优解即为全局最优解。

对固定的x，Lagrange函数L(x,λ,v)为关于λ和v的仿射函数。

（对仿射函数求下确界，是凹的）

KKT条件

若要对偶函数的最大值即为原问题的最小值，需要满足KKT条件：