EE364A Homework 2

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

这次回顾凸优化Homework 2。

2.28

利用顺序主子式即可。

一阶：

$$x_1 \ge 0$$

二阶：

$$\begin{aligned} x_1 &\ge 0 \\ x_1 x_3 &\ge x_2^2 \end{aligned}$$

三阶：

$$\begin{aligned} x_1 &\ge 0\\ x_1 x_4 &\ge x_2^2 \\ x_1 x_4x_6 + 2x_2 x_3 x_5&\ge x_1x_5^2 +x_6x_2^2+x_4x_3^2 \end{aligned}$$

2.33

(a)凸：

$\forall x^{(1)}, x^{(2)}\in K_{\mathrm{m}+}, \theta\in [0, 1]$，对于$i > j$，我们有

$$\begin{aligned} \left(\theta x^{(1)} + (1-\theta)x^{(2)}\right)_i &= \theta x^{(1)}_i+(1-\theta)x^{(2)}_i\\ &\ge \theta x^{(1)}_j+(1-\theta)x^{(2)}_j\\ &=\left(\theta x^{(1)} + (1-\theta)x^{(2)}\right)_j \end{aligned}$$

所以

$$\theta x^{(1)} + (1-\theta)x^{(2)} \in K_{\mathrm{m}+}$$

$K_{\mathrm{m}+}$是闭和实的显然。

尖：

如果$x \in K_{\mathrm{m}+}, -x\in K_{\mathrm{m}+}$，那么

$$\begin{aligned} x_{1} \ge x_{2} \ge \cdots \ge x_{n} \ge 0 \\ -x_{1} \ge -x_{2} \ge \cdots \ge -x_{n} \ge 0 \end{aligned}$$

从而$x_i =0, x=0$，因此尖性得证。

(b)因为

$$\begin{aligned} \sum_{i=1}^{n} x_{i} y_{i}=&\left(x_{1}-x_{2}\right) y_{1}+\left(x_{2}-x_{3}\right)\left(y_{1}+y_{2}\right)+\left(x_{3}-x_{4}\right)\left(y_{1}+y_{2}+y_{3}\right)+\cdots \\ &+\left(x_{n-1}-x_{n}\right)\left(y_{1}+\cdots+y_{n-1}\right)+x_{n}\left(y_{1}+\cdots+y_{n}\right) \end{aligned}$$

注意到关于$y$的项前面的系数非负，所以要使得上式非负，必然有

$$\sum_{i=1}^k y_i \ge 0, k=1,\ldots ,n$$

3.2

左图：

不是凸函数，两点连线上的值大于端点的加权和。

不是凹函数或拟凹函数，因为上水平集不是凸集。

是拟凸函数，因为下水平集是凸集。

右图：

可能是凹函数（拟凹函数），因为两点连线上的值大于端点的加权和。

不是凸函数或拟凸函数，因为下水平集不是凸集。

3.5

令$t=sx$，那么

$$\begin{aligned} dt&= xd s\\ F(x) &=\frac 1 x \int_0^1 f(sx) xds\\ &=\int_0^1 f(sx) ds \end{aligned}$$

因为固定$s$，$f(sx)$是凸函数，所以

$$F(x) =\int_0^1 f(sx) ds$$

是凸函数。

3.6

如果上镜图是半平面，即

$$\{(x,t) | f(x)\le t\} = \{x^Ta +bt +c \ge 0 \}$$

对比后不难发现$f(x)$此时为仿射函数。

如果上镜图是凸锥，此时$f(x)$必然可以表示为分段仿射函数。

如果上镜凸是多面体，除非该多面体为锥，否则不存在满足条件的锥。

3.15

(a)

$$\begin{aligned} \lim _{\alpha \rightarrow 0} u_{\alpha}(x) &=\lim _{\alpha \rightarrow 0} \frac{x^{\alpha}-1}{\alpha}\\ &= \frac{d x^{\alpha}}{d\alpha} \big| _{\alpha=0}\\ &=(x^{\alpha} \log x)\big| _{\alpha=0}\\ &= \log x \end{aligned}$$

(b)

$$u_{\alpha}(1)=\frac{1^{\alpha}-1}{\alpha} =0$$

求导可得

$$\begin{aligned} \frac{d u_{\alpha}(x)}{dx} &= x^{\alpha -1}\\ \frac{d^2 u_{\alpha}(x)}{dx^2} &= (\alpha -1)x^{\alpha -2} \\ &\le 0 \end{aligned}$$

所以$u_{\alpha}$是凹函数。

3.16(b-e)

(b)

$$\begin{aligned} \nabla^2 f &= \left[ \begin{matrix} 0 & 1\\ 1 & 0 \end{matrix} \right] \end{aligned}$$

该矩阵不定，所以不是凸函数和凹函数。

事实上，$f$是拟凹函数，即

$$\left\{x \in \mathbf{R}_{+}^{2} | x_{1} x_{2} \ge \alpha\right\}$$

是凸集，下面证明这点：

$\forall x^{(1)}, x^{(2)} \in \mathbf{R}_{+}^{2},\theta\in [0, 1]$，我们有

$$\begin{aligned} (\theta x^{(1)}+(1-\theta) x^{(2)})_1(\theta x^{(1)}+(1-\theta) x^{(2)})_2 &= (\theta x^{(1)}_1+(1-\theta) x^{(2)}_1)(\theta x^{(1)}_2+(1-\theta) x^{(2)}_2)\\ &=\theta^2 x^{(1)}_1 x^{(1)}_2 +(1-\theta)^2 x^{(2)}_1 x^{(2)}_2+ \theta(1-\theta)( x^{(1)}_1x^{(2)}_2 + x^{(2)}_1x^{(1)}_2) \\ &\ge \left(\theta^2 +(1-\theta)^2\right) \alpha + 2\theta(1-\theta) \sqrt{x^{(1)}_1x^{(2)}_2 x^{(2)}_1x^{(1)}_2}\\ &= \left(\theta^2 +(1-\theta)^2+2\theta(1-\theta)\right) \alpha\\ &=\alpha \end{aligned}$$

(c)

$$\begin{aligned} \nabla^2 f &= \left[ \begin{matrix} \frac{2}{x_1^3 x_2} & \frac{1}{x_1^2x_2^2}\\ \frac{1}{x_1^2x_2^2}& \frac{2}{ x_1x_2^3} \end{matrix} \right] \end{aligned}$$

利用主子式可得上述矩阵正定，所以$f$是凸函数。

同样$f$是拟凸函数，因为

$$\left\{x \in \mathbf{R}_{+}^{2} | x_{1} x_{2} \le \alpha\right\}=\left\{x \in \mathbf{R}_{+}^{2} | x_{1} x_{2} \ge \frac 1 \alpha\right\}$$

是凸集。

(d)

$$\begin{aligned} \nabla^2 f &= \left[ \begin{matrix} 0 & -\frac{1}{x_2^2}\\ -\frac{1}{x_2^2}& \frac{2x_1}{ x_2^3} \end{matrix} \right] \end{aligned}$$

该矩阵不定，所以不是凸函数和凹函数。

实际上该函数既是拟凸函数，又是拟凹函数，因为

$$\begin{aligned} \left\{x \in \mathbf{R}_{+}^{2} | \frac{x_{1}} {x_{2}} \ge \alpha\right\} &=\left\{x \in \mathbf{R}_{+}^{2} | x_{1} \ge \alpha x_{2}\right\} \\ \left\{x \in \mathbf{R}_{+}^{2} | \frac{x_{1}} {x_{2}} \le \alpha\right\} &=\left\{x \in \mathbf{R}_{+}^{2} | x_{1} \le \alpha x_{2}\right\} \end{aligned}$$

均为凸集。

(e)

$$\begin{aligned} \nabla^2 f &= \left[ \begin{matrix} \frac{2}{x_2} & -\frac{2 x_1}{x_2^2}\\ -\frac{2 x_1}{x_2^2}& \frac{2x_1^2}{ x_2^3} \end{matrix} \right] \end{aligned}$$

利用主子式可得上述矩阵半正定，所以$f$是凸函数。

同样$f$是拟凸函数，因为

$$\left\{x \in \mathbf{R} \times \mathbf{R}_{++} | x_{1}^2/ x_{2} \le \alpha\right\} =\left\{x \in \mathbf{R} \times \mathbf{R}_{++} | x_{1}^2 \le \alpha x_{2}\right\}$$

是凸集，下面证明这点：

$\forall x^{(1)}, x^{(2)} \in \mathbf{R}_{+}^{2},\theta\in [0, 1]$，我们有

$$\begin{aligned} \left(\theta x^{(1)} +(1-\theta) x^{(2)} \right)_1^2 &=\left(\theta x^{(1)}_1 +(1-\theta) x^{(2)}_1 \right)^2\\ &= \theta^2 (x^{(1)}_1)^2 + (1-\theta)^2(x^{(2)}_1 )^2 +2\theta (1-\theta) ( x^{(1)}_1 x^{(2)}_1)\\ &\le \theta^2\alpha x^{(1)}_2+ (1-\theta)^2\alpha x^{(2)}_2+ \theta (1-\theta) \left((x^{(1)}_1)^2+(x^{(2)}_1 )^2 \right) \\ &\le \theta^2\alpha x^{(1)}_2+ (1-\theta)^2\alpha x^{(2)}_2+\theta (1-\theta) \alpha \left(x^{(1)}_2+ x^{(2)}_2\right) \\ &\le \alpha \left(\theta x^{(1)}_2 +(1-\theta) x^{(2)}_2\right) \end{aligned}$$

3.18(b)

令$X= Z+tV$，其中$Z,Z+tV \in \mathbf{S}_{++}^{n},V \in \mathbf{S}^{n}$，那么

$$\begin{aligned} g(t) &=(\operatorname{det} X)^{1 / n} \\ &=(\operatorname{det} (Z+tV))^{1 / n} \\ &= \left(\operatorname{det}\left(Z^{1 / 2}\left(I+t Z^{-1 / 2} V Z^{-1 / 2}\right) Z^{1 / 2}\right) \right)^{1 / n}\\ &=\left(\operatorname{det}Z^{1 / 2} \times \operatorname{det}\left(I+t Z^{-1 / 2} V Z^{-1 / 2}\right) \times \operatorname{det}Z^{1 / 2} \right)^{1 / n}\\ &=\left(\operatorname{det}Z \times \prod_{i=1}^n(1+t\lambda_i) \right)^{1 / n}\\ &= \exp\left(\frac 1 n \left(\sum_{i=1}^{n} \log \left(1+t \lambda_{i}\right)+\log \operatorname{det} Z\right) \right) \end{aligned}$$

其中$\lambda_i $是矩阵$Z^{-1 / 2} V Z^{-1 / 2}$的特征值，对上式关于$t$求导可得

$$\begin{aligned} g'(t) &= \exp\left(\frac 1 n \left(\sum_{i=1}^{n} \log \left(1+t \lambda_{i}\right)+\log \operatorname{det} Z\right) \right) \left(\frac 1 n\sum_{i=1}^{n} \frac{\lambda_{i}}{1+t \lambda_{i}}\right)\\ g''(t)&= \exp\left(\frac 1 n \left(\sum_{i=1}^{n} \log \left(1+t \lambda_{i}\right)+\log \operatorname{det} Z\right) \right) \left( -\frac 1 n\sum_{i=1}^{n} \frac{\lambda_{i}^{2}}{\left(1+t \lambda_{i}\right)^{2}}\right) \\ &+\exp\left(\frac 1 n \left(\sum_{i=1}^{n} \log \left(1+t \lambda_{i}\right)+ \log \operatorname{det} Z\right) \right)\left(\frac 1 n\sum_{i=1}^{n} \frac{\lambda_{i}}{1+t \lambda_{i}}\right)^2\\ &= \frac 1 {n^2}\exp\left(\frac 1 n \left(\sum_{i=1}^{n} \log \left(1+t \lambda_{i}\right)+\log \operatorname{det} Z\right) \right) \left(\left(\sum_{i=1}^{n} \frac{\lambda_{i}}{1+t \lambda_{i}}\right)^2-n\sum_{i=1}^{n} \frac{\lambda_{i}^{2}}{\left(1+t \lambda_{i}\right)^{2}} \right)\\ &\le 0 \end{aligned}$$

其中不等号是因为柯西不等式。

3.24(f-h)

(f)由作业1可得其上水平集以及下水平集为凸集，所以该函数为拟凸函数以及拟凹函数。

注意该函数不连续，所以不是凸函数以及凹函数。

(g)该函数取值于整数集上，所以显然不连续，因此不是凸函数也不是凹函数。

考虑其下水平集，$\forall \alpha$，定义

$$k=\max \{i=1, \ldots, n | i<\alpha\}$$

那么

$$f(x) \ge \alpha$$

当且仅当

$$\sum_{i=1}^{k} p_{[i]}<0.9$$

注意$\sum_{i=1}^{k} p_{[i]}$为凸函数，所以上述集合为凸集，因此该函数为拟凹函数。

(h)设

$$\begin{aligned} \alpha_{j-1} < \alpha \le \alpha_j \\ \alpha_{k-1} \le \beta < \alpha_{k} \end{aligned}$$

那么

$$\begin{aligned} \operatorname{prob}(\alpha \leq x \leq \beta) &= \sum_{i=j}^{k-1}p_i\\ f(x)&= \alpha_{k-1} -\alpha_j \end{aligned}$$

不难看出该函数不连续，所以不是凸函数，也不是凹函数。

考虑下水平集，

$$f(x) \ge \gamma$$

上式成立当且仅当对于任意的

$$\begin{aligned} \alpha_{k-1} -\alpha_j < \gamma \end{aligned}$$

我们有

$$\operatorname{prob}(\alpha \leq x \leq \beta) = \sum_{i=j}^{k-1}p_i <0.9$$

因为$\sum_{i=j}^{k-1}p_i $是凸函数，所以上述集合为凸集，从而原函数为拟凹函数。

3.36(a,d)

(a)

$$f^{*}(y)=\left\{\begin{array}{ll}{0} & {y \succeq 0, \quad 1^{T} y=1} \\ {\infty} & {其他} \end{array}\right.$$

下面证明上述结论。

如果存在$i$，使得$y_i < 0$，那么取

$$x _j =\begin{cases} -t<0 & j =i\\ 0 & j\neq i \end{cases}$$

此时

$$y^T x -f(x) = -y_i t \to\infty$$

如果$1^T y <1$，那么取

$$x _j = -a <0, j=1,\ldots, n$$

此时

$$y^Tx -f(x) = -a 1^Ty +a= a(1-1^Ty) \to \infty$$

如果$1^T y >1$，那么取

$$x _j =a>0, j=1,\ldots, n$$

此时

$$y^Tx -f(x) = a 1^Ty -a= a(1^Ty - 1) \to \infty$$

如果$1^T y =1$，那么

$$y^T x -f(x) \le f(x)y^T 1 -f(x) =0$$

所以结论得证。

(d)考虑

$$yx - f(x) =yx -x^p$$

关于$x$求导可得

$$\left(yx - f(x) \right)'=y - p x^{p-1}$$

如果$y \le 0$，那么最大值在$x=0$处取到；否则在

$$x = \left(\frac {y}{p}\right)^{1/ (p-1)}$$

处取到，此时

$$\begin{aligned} f^*(y)&=yx -f(x)\\ &= y \left(\frac {y}{p}\right)^{1/ (p-1)} - \left(\frac {y}{p}\right)^{p/ (p-1)}\\ &= y^{p/ (p-1)} \left( \frac 1 {p^{1/ (p-1)}} - \frac 1 {p^{p/ (p-1)}}\right) \end{aligned}$$

所以

$$\begin{aligned} f^*(y)&=\begin{cases} 0 & y \le 0\\ y^{p/ (p-1)} \left( \frac 1 {p^{1/ (p-1)}} - \frac 1 {p^{p/ (p-1)}}\right) & y > 0 \end{cases} \end{aligned}$$

如果$p < 0$，那么当$y \ge 0$时，原函数递增，$f^*(y) \to \infty$，所以此时定义域为$y < 0$，令导数为$0$，得到

$$x = \left(\frac {y}{p}\right)^{1/ (p-1)}$$

由单调性可得函数在该点取极大值，所以

$$\begin{aligned} f^*(y)&=\begin{cases} \infty & y \ge 0\\ y^{p/ (p-1)} \left( \frac 1 {p^{1/ (p-1)}} - \frac 1 {p^{p/ (p-1)}}\right) & y < 0 \end{cases} \end{aligned}$$