课程主页:https://see.stanford.edu/Course/EE364A

这次回顾凸优化Homework 1。

2.1

关于$k$做数学归纳法,$k=2$时结论显然。假设$k=n$时结论成立,下证$k=n+1$时候结论成立。

此时的条件为

总能找到$\theta_i \neq 1$,不妨设为$\theta_{i+1}$,那么

所以

由归纳假设($k=n$)可得

再利用归纳假设($k=2$)可得

所以

$k=n+1$时结论成立。

2.2

$\Rightarrow $:

假设直线为$A=\{y |y = \theta x_1 +(1-\theta) x_2 \}$,凸集为$C$。

$\forall y_1, y_2 \in A \cap C$,不妨设

因为$y_1, y_2 \in C$,所以$\forall \theta_3 \in [0, 1]$,

又因为

所以

因此$A \cap C$是凸集。

$\Leftarrow$:

假设凸集为$C$,现在$\forall y_1, y_2 \in C$,考虑直线集合

因为$A\cap C$是凸集,$y_1,y_2\in A\cap C$,所以$\forall \theta \in [0, 1]$,我们有

因此$C$是凸集。

对于仿射集的结论同理可得。

2.5

$\forall x_1, x_2$满足

距离为

2.7

2.8

(a)如果$a_1, a_2$线性相关,那么结论显然;否则考虑如下集合的交集:

  • $S_1$:$a_1$和$a_2$定义的平面
  • $S_{2}=\left\{z+y_{1} a_{1}+y_{2} a_{2} | a_{1}^{T} z=a_{2}^{T} z=0,-1 \leq y_{1} \leq 1\right\}$
  • $S_{3}=\left\{z+y_{1} a_{1}+y_{2} a_{2} | a_{1}^{T} z=a_{2}^{T} z=0,-1 \leq y_{2} \leq 1\right\}$

$S_1$:设$v_k ,k=1,\ldots,n -2$为和$a_1,a_2$正交的线性无关的向量,那么$S_1$为如下名片的交集

$S_2$:定义

那么

所以$x\in S_2$当且仅当

$S_3$:定义

那么

所以$x\in S_3$当且仅当

(b)是,其中

(c)不是

(d)是,其中

下面证明满足条件的区域即为

如果$x$满足上述条件,那么

所以

反之,如果$x$不满足上述条件,那么存在$i$,使得

后一种情况可以排除(默认$x_i\ge 0$),取$y_i=1,y_k =0, k\neq i$,那么

这就与条件矛盾。

2.11

$\forall x, y \in S, \theta\in [0, 1]$,我们有

所以如果

那么

2.12

(a)是凸集,利用定义即可。

(b)是凸集,利用定义即可。

(c)是凸集,利用定义即可。

(d)是凸集,因为

对任意$y$,上述集合为凸集,所以题意中的集合为

凸集的交任然为凸集。

(e)不是凸集

将原集合转化,注意到

等价于存在$y\in S$,使得

而上述事实等价于对任意$z\in T$,我们有

所以

尽管$F(y,z)$是凸集,但是并运算不能保凸,所以原集合不一定是凸集。

(f)是凸集

$\forall x_1, x_2 \in S $,取$z\in S_2$,那么

因为$S_1$为凸集,所以$\forall \theta \in [0, 1]$,我们有

所以

(g)$\theta =1$时结论显然;$\theta <1$时,我们有

那么原不等式等价于

所以原集合是凸集。

2.15

为了方便讨论,记相应的集合为$S$,$\forall p^{(1)}, p^{(2)}\in S,\theta \in [0, 1]$。

(a)是凸集。因为约束等价于线性不等式:

(b)是凸集。因为约束条件为

(c)是凸集。因为约束条件为

(d)(e)是凸集。因为约束条件为

(f)不是,考虑如下分布

那么

显然

(g)注意到

所以

其中第一个不等号是因为

现在考虑$\theta p^{(1)} +(1-\theta) p^{(2)}$

所以$\text{quartile}_p(x)$是凸集。

(h)$\text{quartile}_p(x)\ge \alpha$等价于,对任意$\beta <\alpha$

定义

所以原命题等价于

上式为关于$p$的半空间,所以为凸集。

(i)$\text{quartile}_p(x)\le \alpha$等价于,对任意$\beta \ge \alpha$

定义

那么原命题等价于

上式为关于$p$的半空间,所以为凸集。