P8 保凸运算

• 保凸运算
• 透视函数 Perspative Function
• 线性分数函数

保凸运算

透视函数 Perspative Function

$P: R^{n+1} \mapsto R^n \quad dom \; P=R^n*R_{++}$P:Rn+1↦RndomP=Rn∗R++​

$P(z,t) = \frac{z}{t} \quad z \in R^n \quad t \in R_{++}$P(z,t)=tz​z∈Rnt∈R++​

降维过程，将前所有元素，除以最后一维，并去掉最后一维。

任何一个函数，通过透视函数之后，还是凸集。

例：考虑 $R^{n+1}$Rn+1 线段。$x=(\tilde x,x_{n+1}) \quad \tilde x \in R^n \quad x_{n+1} \in R_{++}$x=(x~,xn+1​)x~∈Rnxn+1​∈R++​; $y=(\tilde y,y_{n+1}) \quad \tilde y \in R^n \quad y_{n+1} \in R_{++}$y=(y~​,yn+1​)y~​∈Rnyn+1​∈R++​

$\theta \geq 0$θ≥0 线段维 $\theta x + (1-\theta) y$θx+(1−θ)y

证明：线段经过透视函数P后，仍然时凸集。

$x \rightarrow ^ P P(x)$x→PP(x) $\quad$$y \rightarrow ^ P P(y)$y→PP(y)
$\theta x + (1-\theta) y \rightarrow ^ P P(\theta x + (1-\theta) y)$θx+(1−θ)y→PP(θx+(1−θ)y)

设$\mu =\frac{\theta x_{n+1}}{ \theta x_{n+1} + (1-\theta) y_{n+1} }$μ=θxn+1​+(1−θ)yn+1​θxn+1​​
$\begin{aligned} P(\theta x + (1-\theta) y) &= \frac{\theta \tilde {x} + (1-\theta) \tilde {y}}{ \theta x_{n+1} + (1-\theta) y_{n+1} } \\ &=\frac{\theta x_{n+1}}{ \theta x_{n+1} + (1-\theta) y_{n+1} } \frac{\tilde {x}}{x_{n+1}} + \frac{(1-\theta) y_{n+1}}{ \theta x_{n+1} + (1-\theta) y_{n+1} } \frac{\tilde {y}}{y_{n+1}} \\ &=\mu P(x) + (1-\mu) P(y) \end{aligned}$P(θx+(1−θ)y)​=θxn+1​+(1−θ)yn+1​θx~+(1−θ)y~​​=θxn+1​+(1−θ)yn+1​θxn+1​​xn+1​x~​+θxn+1​+(1−θ)yn+1​(1−θ)yn+1​​yn+1​y~​​=μP(x)+(1−μ)P(y)​

任意凸集的反透视映射仍是凸集。

$P^{-1}(C)=\lbrace (x,t) \in R^{n+1} | \frac{x}{t} \in c, t > 0 \rbrace$P−1(C)={(x,t)∈Rn+1∣tx​∈c,t>0}

考虑$(x,t) \in P^{-1}(C) \quad (y,s) \in P^{-1}(C) \quad 0 \leq \theta \leq 1$(x,t)∈P−1(C)(y,s)∈P−1(C)0≤θ≤1

$\frac{\theta x+(1-\theta)y}{\theta t+(1-\theta)s} \in^? C$θt+(1−θ)sθx+(1−θ)y​∈?C

$\begin{aligned} \frac{\theta t}{\theta t+(1-\theta)s}\frac{x}{t}+(1-\frac{\theta t}{\theta t+(1-\theta)s})\frac{y}{s} \end{aligned}$θt+(1−θ)sθt​tx​+(1−θt+(1−θ)sθt​)sy​​
$\frac{x}{t}$tx​ 与 $\frac{y}{s}$sy​ 都是C中的一点，C是凸集。所以结论成立。

线性分数函数

$g:R^n \mapsto R^{m+1}$g:Rn↦Rm+1 为伪仿射函数
$g(x)=\begin{bmatrix} A \\ C^T \\ \end{bmatrix} x + \begin{bmatrix} b \\ d \\ \end{bmatrix} \quad A \in R^{m+n} \quad b\in R^{m} \quad C \in R^{n} \quad d \in R$g(x)=[ACT​]x+[bd​]A∈Rm+nb∈RmC∈Rnd∈R

$P:R^{m+1} \mapsto R^{m}$P:Rm+1↦Rm
定义：
$f:R^n \mapsto R^m = P \circ g$f:Rn↦Rm=P∘g 先经过$g$g,在经过$P$P。
本质是仿射变换+透视变换。

$f(x) = \frac{Ax+b}{C^T+d} \quad dom \;f \lbrace x | C^Tx + d > 0 \rbrace$f(x)=CT+dAx+b​domf{x∣CTx+d>0}

例:两个随机变量的联合概率 $\rightarrow$→ 条件概率

$u \in \lbrace {1..n} \rbrace,v \in \lbrace {1...m} \rbrace$u∈{1..n},v∈{1...m}

$P_{ij}=P(u=i,v=j)$Pij​=P(u=i,v=j)
$f_{ij}=P(u=i|v=j)$fij​=P(u=i∣v=j)

$f_{ij}= \frac{P_{ij}}{\sum_{k=1}^n P_{kj}}$fij​=∑k=1n​Pkj​Pij​​