EE364A Homework 2

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

这次回顾凸优化Homework 2。

2.28

利用顺序主子式即可。

一阶:

二阶:

三阶:

2.33

(a)凸:

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

所以

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

尖:

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

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

(b)因为

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

3.2

左图:

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

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

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

右图:

可能是凹函数(拟凹函数),因为两点连线上的值大于端点的加权和。

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

3.5

令$t=sx$,那么

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

是凸函数。

3.6

如果上镜图是半平面,即

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

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

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

3.15

(a)

(b)

求导可得

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

3.16(b-e)

(b)

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

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

是凸集,下面证明这点:

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

(c)

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

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

是凸集。

(d)

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

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

均为凸集。

(e)

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

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

是凸集,下面证明这点:

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

3.18(b)

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

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

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

3.24(f-h)

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

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

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

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

那么

当且仅当

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

(h)设

那么

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

考虑下水平集,

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

我们有

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

3.36(a,d)

(a)

下面证明上述结论。

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

此时

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

此时

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

此时

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

所以结论得证。

(d)考虑

关于$x$求导可得

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

处取到,此时

所以

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

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

本文标题:EE364A Homework 2

文章作者:Doraemonzzz

发布时间:2019年08月23日 - 16:55:00

最后更新:2019年10月09日 - 23:23:09

原始链接:http://doraemonzzz.com/2019/08/23/EE364A Homework 2/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。