凸集/凸函数习题

《凸优化》第二/三章部分习题。

2.9

(a) 证明：

​ 考虑

$$V_i=\{x=\textbf{R}^n\mid \|x-x_0\|_2\leq\|x-x_i\|_2\}$$

作超平面 $(x_i-x_0)^Tx=(x_i-x_0)^T(x_i+x_0)/2$

​ 对超平面上每个点 $xk$ 的分量 $j$ 都有 $2(x{ij}-x{0j})x{kj}=(xi^2-x_0^2)$ ，且 $|x_k-x_0|_2=\sqrt{\sum_j{(x{kj}-x{0j})^2}}$ ，$|x_k-x_i|_2=\sqrt{\sum_j{(x{kj}-x_{0j})^2}}$ 。

​ 将第一式带入范数表达式可得对超平面上每个点 $x$ 均有 $|x-x_0|_2=|x-x_i|_2$ ，且对于超平面下方的半空间 $(x_i-x_0)^Tx\leq(x_i-x_0)^T(x_i+x_0)/2$ ，均有 $|x-x_0|_2\leq |x-x_i|_2$ ，对所有的 $i$ 均成立。即 $V$ 的边界为一系列超平面的交，$V$ 为多面体。设 $x_i-x_0=a_i$ ，$(x_i-x_0)^T(x_i+x_0)/2=b_i$ ， $V$ 可以被写作

$$V=\{x\mid Ax\preceq b\}, A=\{a_1^T,a_2^T,\cdots,a_K^T\}, b=\{b_1,b_2,\cdots,b_K\}$$

(b)

​ P总可以表达为$P={x\mid Ax\preceq b}$ 的形式，设 $A={a_1^T,a_2^T,\cdots,a_K^T}$ ，对于任意一点 $x_0\in P$ 和多面体的面 $a_i^Tx=b$，总可以找到直线 $x=x_0+ka_i, k\in\textbf{R}$ 上的一点 $x_i$ 满足对面上任意一点 $x_k$ ，有 $ |x_i-x_k|_2=|x_0-x_k|_2$ (作点 $x_0$ 关于面的对称点即可) ，这是由于 $x_0$ 在多面体内部，满足 $a^T_ix<b$ ，在直线上增大 $k$ 会使 $|x_i-x_k|_2$ 减小至0后增大，使 $|x_0-x_k|_2$ 增大。根据定义，这样的一组点就$x_0, x_1,\cdots,x_K$ 满足 $P$ 是 $x_0$ 关于 $x_1,\cdots, x_K$ 的 Voronoi 区域。

(c)

​ 并不总可以用 Voronoi 区域表示。最明显的例子是由数个无限边界多面体组成的集合，考虑 $\textbf{R}^2$ 中由三个多面体组成的集合，他们的边界超平面的法向量共面，且边界两两之间夹角小于90°，这样就有至少一个多面体真包含了一个半空间，记为A。依照之前 Voronoi 区域点的找法， $x_1,x_2,x_A$ 分属三个多面体且需要互相关于边界超平面对称，将其他两个多面体沿边界对称投影到A上，它们的交集就是 $x_A$ 的取值范围(因为 $x_A$ 需要同时与 $x_1,x_2$ 关于两条边界对称)。由于 A 真包含了一个半空间，所以两部分投影不可能有交集，即不可能找到这样的 $x_A$ 。

总结：

主要是超平面的定义。

2.26

证明：

​ 先证必要性。因为 $C=D$ ，即 $C\subseteq D, D\subseteq C$ ， ，显然它可以推得于 $S_C\leq S_D, S_D\leq S_C$， 即 $S_C=S_D$ 。

再证充分性。因为 $S_C=S_D$，设 $C\neq D$ ，不失一般性，设存在 $x_i\in C, x_i\notin D$ ，
根据凸集定义，取 $D$ 的支撑超平面集，一定存在某个方向 $a^T$ 上的 $D$ 的支撑超平面，满足 $a^Tx_i>b$ 且 $\forall x \in D, a^Tx<b$ 。
将 $a$ 取为支撑函数自变量，则

$$S_C(a)=\sup\{a^Tx\mid x\in C\}=a^Tx_i >b> \sup\{a^Tx\mid\ x\in D\}$$

即 $S_C\neq S_D$ ，矛盾。所以 $C=D$ 。

总结：

这道题说明了一个性质，即凸集能被他们的支撑函数完全表征，它们是双射关系。考虑”支撑集”定义和支撑一词的含义，能够表征凸集还是比较容易理解的。

2.33

(a) 证明:

​ $K{m+}$ 在 $\textbf{R}^n$ 中由 n 个带等号不等式约束，所以其是闭凸集，且容易知道它满足 $\theta_1 x_1+\theta_2 x_2\in K{m+}, \forall x1,x_2\in K{m+}$ 所以 $K{m+}$ 是个闭凸锥。其内部非空性质通过列举满足条件的向量同样易得。
​ 因为 $x\in K{m+}, -x\in K{m+}$ ，即 $x_1\geq x_2\geq\cdots\geq x_n\geq 0, x_1\leq x_2\leq\cdots\leq x_n\leq 0$ ，即 $x_1=x_2=\cdots=x_n=0$ ， $x=0$ 。所以 $K{m+}$ 是尖的，所以它是正常锥。

(b)

$$K^*_{m+}=\{y\mid\sum x_iy_i\geq0, \forall x\in K\}\\$$

注意到提示中恒等式，有

$$\begin{align} K^*_{m+}&=\{y\mid (x_1-x_2)y_1+(x_2-x_3)(y_1+y_2)+ (x_3-x_4)(y_1+y_2+y_3)\\&+\cdots+(x_{n-1}-x_n)(y_1+\cdots+y_{n-1})+x_n(y_1+\cdots+y_n)\geq0, \forall x\in K\}\\ K^*_{m+}&=\{y\mid\sum_{i=1}^n y_i\geq 0\} \end{align}$$

总结：

• 等号不等式约束集为闭凸集。

3.9

(a) 证明:

$\overset{-}{f}$ 为凸的二阶条件是 $\triangledown^2\overset{-}{f}$ 半正定。
即 $\bigtriangledown^2\overset{-}{f}(z)=F^T\bigtriangledown^2f(Fz+\hat{x})F\succeq 0$

(b) 证明：

即证明 $F^T\bigtriangledown^2(Fz+\hat{x})F\succeq 0 \Leftrightarrow \bigtriangledown^2 f(Fz+\hat{x})+\lambda A^TA\succeq 0$
使用引理：

总结：

这里没有写，但最后交上去的时候这里还是写了的，实际上这里是应用 (a) 中的结论， 将 $F$ 分解后仍然成立，即$\forall v,v^T\triangledown^2f(Fz+\hat{x})v\succeq0$ 。 $v$ 也在 $A$ 的零空间中。然后直接用引理就行。 用 $B=\triangledown^2f(Fz+\hat{x})$ 代换引理的话，很容易就能得出结论。

还需要注意一点是 $g(x)=f(Ax+b)$ 的二阶条件是 $\triangledown^2g$ 和 $A^T\triangledown^2fA$ 。

3.35

(a)证明：

$SB(y)=\sup{y^Tx\mid x\in B}$， $S{\textbf{conv}B}(y)=\sup{y^Tx’\mid x’\in\textbf{conv}B}$

因为 $B\subseteq\textbf{conv}B$ ，所以在 $y$ 确定时 ， 有 $y^Tx\leq y^Tx’$ 。在 $y$ 确定的情况下，若此不等式不能取严格等号，则必定存在某个 $x’$ 对任意 $x$ 都取

$$y^Tx<y^Tx'$$

根据凸包定义，$x’=\sum_i\theta_i x_i, \sum\theta_i=1, x_i\in B$ ，则有

$$y^Tx'=y^T\sum\theta_i x'>y^T\sum\theta_i x_i=y^Tx_i$$

矛盾。所以不等式可以严格取等号，即 $SB(y)=S{\textbf{conv}B}(y)$

(b)证明：

$$\begin{align} S_{A+B}(y)&=\sup\{y^Tx\mid x\in A+B\}=\sup\{y^T(a+b)\mid a\in A, b\in B\}\\ &=\sup\{y^Ta\mid a\in A\}+\sup\{y^Tb\mid b\in B\}\\ &=S_A(y)+S_B(y) \end{align}$$

(c)证明：

$$\begin{align} S_{A\cup B}(y)&=\sup\{y^Tx\mid x\in A\cup B\}\\ &=\max\{\sup\{y^Tx\mid x\in A\}, \sup\{y^Tx\mid x\in B\}\}\\ &=\max\{S_A(y)+S_B(y)\} \end{align}$$

(d)证明:

必要性易得，此处仅证充分性：

$$S_{\textbf{conv}A}(y)=S_A(y)\leq S_B(y)$$

若 $\textbf{conv}A\nsubseteq B$，即 $\exists x\in \textbf{conv}A, x\notin B$ ，则 $S{\textbf{conv}A\cup B}(y)>S_B(y)$ 。又有 $S{\textbf{conv}A\cup B}(y)=\max{S_{\textbf{conv}A}(y), S_B(y)}=S_B(y)$ 矛盾。所以 $A\subseteq \textbf{conv}A \subseteq B$。

总结：

和2.26一样，结合之前的支撑函数的例子和此题（尤其是(a)），能更好地理解支撑函数能够表征凸集的性质。这种一一对应关系由sup运算保证。

3.38

证明:

即证明 $F(x)=\underset{y\in\textbf{dom}G}{\sup}(xy-G(y))$ 。

Young 不等式的简单图示:

可以看到 $xy$ 表征一个矩形面积，可以看到阴影面积和（即 $F(x)+G(y)$）永远不小于这个矩形面积，等号在 $f(x)=y$ 时取得。因为 $xy\leq F(x)+G(y)$ ，所以 $F(x)\geq xy-G(y)$ 。因为 $y=f(x)$ 时不等式可以取等号，所以$F(x)=\underset{y\in\textbf{dom}G}{\sup}(xy-G(y))$

总结

此处无图，自行想象哈。大概就是函数过零点的函数 $f(x)$ 对 $x$ 轴和 $y$ 轴分别做 $[0,x],[0,y]$ 上的积分，这样可以把两个函数的定积分画到一个图上。

3.49

(a) 证明：

$$\begin{align} \ln f(x)=\ln\frac{e^x}{1+e^x}=x-\ln (1+e^x) \end{align}$$

其中 $x$ 是凹函数而 $-\ln(1+e^x)$ 可以看做指数和的对数取负，它是凹函数函数。所以原式是对数凹的。

(b) 证明：

$$\begin{align} \ln f(x)=-\ln\sum\frac{1}{x_i} \end{align}$$

因为 $1/xi$ 在 $x\in\textbf{dom}f=\textbf{R}^n{++}$ 上为凸函数，所以 $\sum 1/x_i$ 为其非负加权求和，也是凸函数。 $-\ln(x)$ 在定义域内为凸函数且非增。需要对复合函数求二阶导：

$$\begin{align} h(x)&=-\ln\sum\frac{1}{x_i}\\ h'(x)&= \end{align}$$

(c) 证明：

$$\begin{align} \ln f(x)=\ln x_i-\ln\sum x_i \\ f[\theta x+(1-\theta)y]=\frac{\prod[\theta x_i+(1-\theta) y_i]}{\sum[\theta x_i+(1-\theta) y_i]}\\ \frac{\prod[x_i^\theta y_i^{1-\theta}]}{(\sum x_i)^\theta(\sum y_i)^{1-\theta}} \end{align}$$

(d) 证明：

$$\begin{align} f(\theta X+(1-\theta)Y)=\frac{\det [\theta X+(1-\theta)Y]}{\textbf{tr}[\theta X+(1-\theta)Y]}\\ \frac{(\det X)^\theta(\det Y)^{1-\theta}}{\textbf{tr}X^\theta\textbf{tr}Y^{1-\theta}} \end{align}$$

总结：

实在做不下去了。。可以说一下答案大概的思路。

(b)考虑取 $\log$ 后的二阶条件，直接通过暴力（也没多暴力）算对 $x_i$ 的二次偏导和 $x_i,x_j$ 的联合偏导 ，这样可以直接写出整个 Hessian 阵的项，可以通过柯西施瓦茨不等式得出二阶条件为为负。

(c)有点麻烦按下不表。主体方法还是通过代入 $x+tv$ 的方式。

(d)同样考虑 $X=Z+tV$ ， $Z\succ 0$ 且对 $Z^{-1/2}VZ^{-1/2}$ 做特征值分解。主要行了一个比较难的代换：

$$\begin{align} h(Z+tV)=\log f(Z+tV)&=\log\det(Z+tV)-\log\textbf{tr}(Z+tV)\\ &=\log\det Z-\log\det(I+tZ^{-1/2}VZ^{-1/2})-\\ &\ \ \ \ \log\textbf{tr}(Z(I+tZ^{-1/2}VZ^{-1/2})) \end{align}$$

并用到了(c)中的条件。