EE364A Homework 1

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

这次回顾凸优化Homework 1。

2.1

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

此时的条件为

$$\sum_{i=1}^{n+1}\theta_i =1$$

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

$$\begin{aligned} \sum_{i=1}^{n}\theta_i &=1 -\theta_{n+1} \\ \sum_{i=1}^{n}\frac{\theta_i}{1-\theta_{n+1}} &=1 \end{aligned}$$

所以

$$\begin{aligned} \sum_{i=1}^{n+1} \theta_i x_i &= \sum_{i=1}^{n} \theta_i x_i + \theta_{n+1} x_{n+1}\\ &= (1-\theta_{n+1}) \left(\sum_{i=1}^{n}\frac{\theta_i}{1-\theta_{n+1}} x_i \right) +\theta_{n+1} \left( x_i\right) \end{aligned}$$

由归纳假设（$k=n$）可得

$$\sum_{i=1}^{n}\frac{\theta_i}{1-\theta_{n+1}} x_i \triangleq x \in C$$

再利用归纳假设（$k=2$）可得

$$(1-\theta_{n+1}) \left(\sum_{i=1}^{n}\frac{\theta_i}{1-\theta_{n+1}} x_i \right) +\theta_{n+1} \left( x_i\right)= (1-\theta_{n+1}) x +\theta_{n+1} \left( x_i\right) \in C$$

所以

$$\sum_{i=1}^{n+1} \theta_i x_i \in C$$

$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$，不妨设

$$\begin{aligned} y_1 &= \theta_1 x_1 +(1-\theta_1) x_2\\ y_2 &= \theta_2 x_1 +(1-\theta_2) x_2 \end{aligned}$$

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

$$\theta_3 y_1 +(1-\theta_3) y_2 = \left(\theta_1 \theta_3 + \theta_2(1-\theta_3) \right) y_1 +\left((1-\theta_1) \theta_3 +(1-\theta_2) (1-\theta_3) \right) y_2 \in C$$

又因为

$$\theta_1 \theta_3 + \theta_2(1-\theta_3) +(1-\theta_1) \theta_3 +(1-\theta_2) (1-\theta_3) =1$$

所以

$$\theta_3 y_1 +(1-\theta_3) y_2 \in A$$

即

$$\theta_3 y_1 +(1-\theta_3) y_2 \in A\cap C$$

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

$\Leftarrow$：

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

$$A=\{y |y = \theta y_1 +(1-\theta) y_2 \}$$

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

$$y = \theta y_1 +(1-\theta) y_2 \in A\cap C \subset C$$

因此$C$是凸集。

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

2.5

$\forall x_1, x_2$满足

$$\begin{aligned} a^T x_1 &= b_1\\ a^T x_2 &= b_2 \end{aligned}$$

距离为

$$\begin{aligned} d&= \frac{|a^T (x_1-x_2) |}{\| a\|_2}\\ &=\frac{|b_1 -b_2|}{\| a\|_2} \end{aligned}$$

2.7

$$\begin{aligned} \|x-a\|_{2} &\le \|x-b\|_{2} \Leftrightarrow \\ \|x-a\|_{2}^2 &\le \|x-b\|_{2}^2 \Leftrightarrow \\ (x-a)^T(x-a) &\le (x-b)^T(x-b)\Leftrightarrow \\ x^T x -2a^T x +a^T a & \le x^T x -2b^T x +b^T b \Leftrightarrow \\ 2(b-a)^T x & \le b^T b-a^T a \end{aligned}$$

即

$$\begin{aligned} c&=2(b-a)\\ d&= b^T b-a^T a \end{aligned}$$

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$为如下名片的交集

$$v_{k}^{T} x=0, \quad k=1, \ldots, n-2$$

$S_2$：定义

$$c_{1}=a_{1}-\frac{a_{1}^{T} a_{2}}{\left\|a_{2}\right\|_{2}^{2}} a_{2}$$

那么

$$c_1^T a_2 =0$$

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

$$-\left|c_{1}^{T} a_{1}\right| \leq c_{1}^{T} x \leq\left|c_{1}^{T} a_{1}\right|$$

$S_3$：定义

$$c_{2}=a_{2}-\frac{a_{2}^{T} a_{1}}{\left\|a_{1}\right\|_{2}^{2}} a_{1}$$

那么

$$c_2^T a_1 =0$$

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

$$-\left|c_{2}^{T} a_{2}\right| \leq c_{2}^{T} x \leq\left|c_{2}^{T} a_{2}\right|$$

(b)是，其中

$$\begin{aligned} A &= -I_n\\ b&= 0\\ F&= \left[ \begin{matrix} 1 & \ldots & 1 \\ a_1 &\ldots & a_n\\ a_1^2 &\ldots & a_n^2 \end{matrix} \right]\\ g&=\left[ \begin{matrix} 1 \\ b_1\\ b_2 \end{matrix} \right] \end{aligned}$$

(c)不是

(d)是，其中

$$\begin{aligned} A&= \left[ \begin{matrix} -I_n \\ I_n \end{matrix} \right]\\ b&= \left[ \begin{matrix} 0 \\ 1 \end{matrix} \right] \end{aligned}$$

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

$$A x \preceq b$$

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

$$0\le x_i \le 1$$

所以

$$x^{T} y \le \sum_{i=1}^n|y_i| \le 1$$

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

$$x_i > 1或x_i <0$$

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

$$x^T y =x_i y_i >1$$

这就与条件矛盾。

2.11

记

$$S= \left\{ \mathbf{R}_{+}^{n}\Big|\prod_{i=1}^{n} x_{i} \geqslant 1 \right\}$$

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

$$\theta x +(1-\theta )y \ge x^\theta y^ {(1-\theta )} \ge 1$$

所以如果

$$\begin{aligned} \prod_{i=1}^{n} x_{i} \ge 1 && \prod_{i=1}^{n} y_{i} \ge 1 \end{aligned}$$

令

$$z_i =\theta x_i +(1-\theta) y_i$$

那么

$$\begin{aligned} \prod_{i=1}^n z_i &=\prod_{i=1}^n \left(\theta x_i +(1-\theta) y_i \right)\\ &\ge \left(\prod_{i=1}^n x_i\right)^{\theta}\left(\prod_{i=1}^n y_i\right)^{1-\theta}\\ &\ge 1 \end{aligned}$$

2.12

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

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

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

(d)是凸集，因为

$$\begin{aligned} \|x-x_0\|_{2} &\le \|x-y\|_{2} \Leftrightarrow \\ \|x-x_0\|_{2}^2 &\le \|x-y\|_{2}^2 \Leftrightarrow \\ (x-x_0)^T(x-x_0) &\le (x-y)^T(x-y)\Leftrightarrow \\ x^T x -2x_0^T x +x_0^T x_0& \le x^T x -2y^T x +y^Ty\Leftrightarrow \\ 2(y-x_0)^T x & \le y^T y-x_0^T x_0 \end{aligned}$$

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

$$\bigcap_{y\in S}\left\{x |\left\|x-x_{0}\right\|_{2} \leqslant\|x-y\|_{2}, \forall y \in S\right\}$$

凸集的交任然为凸集。

(e)不是凸集

将原集合转化，注意到

$$\operatorname{dist}(x, S) \le \operatorname{dist}(x, T)$$

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

$$\|x-y\|_{2} \le \operatorname{dist}(x, T)$$

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

$$\|x-y\|_{2} \le \|x-z\|_{2}$$

记

$$F(y, z)= \{x | \|x-y\|_{2} \le \|x-z\|_{2}\}$$

所以

$$\{x | \operatorname{dist}(x, S) \leqslant \operatorname{dist}(x, T)\} =\bigcup_{y\in S} \bigcap_{x\in T} F(y, z)$$

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

(f)是凸集

记

$$S\triangleq \left\{x | x+S_{2} \subseteq S_{1}\right\}$$

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

$$x_1 +z, x_2 +z\in S_1$$

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

$$\theta(x_1 +z)+(1-\theta)(x_2 +z) =\theta x_1 +(1-\theta)x_2 +z \in S_1$$

所以

$$\theta x_1 +(1-\theta)x_2 \in S$$

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

$$\begin{aligned} \|x-a\|_{2} &\le \theta\|x-b\|_{2} \Leftrightarrow \\ \|x-a\|_{2}^2 &\le \theta^2\|x-b\|_{2}^2 \Leftrightarrow \\ (x-a)^T(x-a) &\le \theta^2(x-b)^T(x-b)\Leftrightarrow \\ x^T x -2a^T x +a^T a & \le \theta^2 x^T x -2 \theta^2b^T x + \theta^2b^T b \Leftrightarrow \\ (1- \theta^2) x^T x +2( \theta^2 b-a)^T x +a^T a- \theta^2b^T b & \le 0\Leftrightarrow \\ x^T x +2\left(\frac{ \theta^2 b-a}{1- \theta^2} \right)^T x +\frac{a^T a- \theta^2b^T b}{1- \theta^2 } &\le 0 \end{aligned}$$

记

$$\begin{aligned} u&= \frac{ \theta^2 b-a}{1- \theta^2}\\ v&= \frac{a^T a- \theta^2b^T b}{1- \theta^2 } \end{aligned}$$

那么原不等式等价于

$$\begin{aligned} x^T x +2 u^T x +v &\le 0\Leftrightarrow \\ (x+u)^T (x+u) &\le u^T u -v \\ \|x+u \|_2^2 &\le u^T u -v \end{aligned}$$

所以原集合是凸集。

2.15

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

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

$$\alpha \leq \sum_{i=1}^{n} p_{i} f\left(a_{i}\right) \leq \beta$$

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

$$\operatorname{prob}(x>\alpha) = \sum_{x_i > \alpha} p_i\le \beta$$

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

$$\sum_{i=1}^{n} p_{i}\left(\left|a_{i}^{3}\right|-\alpha\left|a_{i}\right|\right) \leq 0$$

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

$$\sum_{i=1}^{n} p_{i} a_{i}^{2} \le (\ge) \alpha$$

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

$$\begin{aligned} n&=2,x_1 = 1, x_2 =0\\ p^{(1)}_1 &= 1 , p^{(1)}_2 = 0\\ p^{(2)}_1 &= 0 , p^{(2)}_2 = 1\\ \alpha & =0 \end{aligned}$$

那么

$$\begin{aligned} \operatorname{var_{p^{(1)}}}(x) \le \alpha \\ \operatorname{var_{p^{(2)}}}(x) \le \alpha \end{aligned}$$

取

$$p =\frac 1 2 p^{(1)} + \frac 1 2 p^{(2)}$$

显然

$$\operatorname{var_{p}}(x) > \alpha =0$$

(g)注意到

$$\operatorname{var}(x)=\mathbf{E}(x-\mathbf{E} x)^{2} =\mathbf E[x^2] - \left(\mathbf E[x]\right)^2$$

所以

$$\begin{aligned} \operatorname{var}_{\theta p^{(1)} +(1-\theta) p^{(2)}}(x) &= \mathbf E_{\theta p^{(1)} +(1-\theta) p^{(2)}}[x^2] - \left(\mathbf E_{\theta p^{(1)} +(1-\theta) p^{(2)}}[x]\right)^2 \\ &= \sum\theta p^{(1)}_i x_i^2 +\sum(1-\theta) p^{(2)} _i x_i^2 -\left(\sum\theta p^{(1)}_i x_i +\sum(1-\theta) p^{(2)} _i x_i \right)^2\\ &= \theta \mathbf E_{p^{(1)}} [x_i^2] +(1-\theta )\mathbf E_{p^{(2)}} [x_i^2] -\left(\theta \mathbf E_{p^{(1)}} [x_i] +(1-\theta )\mathbf E_{p^{(2)}}[ x_i]\right)^2 \\ &\ge \theta \mathbf E_{p^{(1)}} [x_i^2] +(1-\theta )\mathbf E_{p^{(2)}} [x_i^2] -\theta \left(\mathbf E_{p^{(1)}} [x_i] \right)^2 - (1-\theta ) \left(\mathbf E_{p^{(2)}}[ x_i] \right)^2\\ &=\theta \operatorname{var}_{p^{(1)}} [x] +(1-\theta) \operatorname{var}_{p^{(2)}} [x]\\ &\ge \theta \alpha +(1-\theta) \alpha \\ &= \alpha \end{aligned}$$

其中第一个不等号是因为

$$\begin{aligned} -\left(\theta a+ (1-\theta)b \right) ^2 - \left(- \theta a^2 -(1-\theta) b^2\right) &= -\theta^2 a^2 - 2\theta (1-\theta) ab -(1-\theta)^2 b^2 +\theta a^2 +(1-\theta) b^2 \\ &= \theta(1-\theta) a^2 +\theta(1-\theta) b^2 -2\theta (1-\theta)ab \\ &=\theta(1-\theta) (a-b)^2 \\ &\ge 0 \end{aligned}$$

记

$$\text{quartile}_p(x)=\inf \{\beta | \text {prob}_p(x \le \beta) = \sum_{\alpha_i \le \beta} p_i \ge0.25\}$$

即

$$\begin{aligned} \sum_{\alpha_i \le \beta} p_i &\ge 0.25\\ \sum_{\alpha_i \le \beta'} p_i &< 0.25(\forall \beta' <\beta) \end{aligned}$$

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

$$\begin{aligned} \sum_{\alpha_i \le \beta}\left ( \theta p^{(1)}_i +(1-\theta) p^{(2)}_i \right) & = \theta \sum_{\alpha_i \le \beta} p^{(1)}_i + (1-\theta) \sum_{\alpha_i \le \beta} p^{(2)}_i \\ &\ge 0.25 \theta + 0.25 (1-\theta)\\ &= 0.25\\ \sum_{\alpha_i \le \beta'}\left ( \theta p^{(1)}_i +(1-\theta) p^{(2)}_i \right) &=\theta \sum_{\alpha_i \le \beta'} p^{(1)}_i + (1-\theta) \sum_{\alpha_i \le \beta'} p^{(2)}_i \\ &< 0.25 \theta + 0.25 (1-\theta)\\ &= 0.25 \end{aligned}$$

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

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

$$\operatorname{prob}(x \leq \beta)<0.25$$

定义

$$k =\max_i \{i | a_i < \alpha\}$$

所以原命题等价于

$$\operatorname{prob}(x \leq \alpha_k)=\sum_{i=1}^k p_i <0.25$$

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

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

$$\operatorname{prob}(x \leq \beta)\ge 0.25$$

定义

$$k =\max_i \{i | a_i \le \alpha\}$$

那么原命题等价于

$$\operatorname{prob}(x \leq \alpha_k)=\sum_{i=1}^k p_i \ge 0.25$$

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