第 2 周作业：凸集与凸函数

源文件是同学的第 2 周手写作业，只有作答过程，没有独立题面。因此本篇是根据作答过程还原题意：凡能从式子唯一恢复的题目按原意整理；具体集合或函数无法唯一辨认处，只保留方法与结论，不冒充原题。

题组一：判断集合是否为凸集

作答中第一类集合由若干线性不等式组成，例如

x_1+2x_2\ge1,\qquad x_1-x_2\ge1.

取任意 $x^{(1)},x^{(2)}$ 属于集合与 $\lambda\in[0,1]$ 。对凸组合 $x=\lambda x^{(1)}+(1-\lambda)x^{(2)}$ ：

x_1+2x_2 =\lambda(x_1^{(1)}+2x_2^{(1)}) +(1-\lambda)(x_1^{(2)}+2x_2^{(2)})\ge1,

另一条同理，所以集合凸。一般地，半空间、仿射集以及它们任意交集都是凸集。

对形如

S=\{x:\lVert x\rVert\le r\}

的集合，用三角不等式：

\lVert\lambda x+(1-\lambda)y\rVert \le\lambda\lVert x\rVert+(1-\lambda)\lVert y\rVert\le r.

故范数球凸。

若 $C$ 凸，则

S=\{Ay:y\in C\}

凸。因为 $x^{(1)}=Ay_1,x^{(2)}=Ay_2$ 时

\lambda x^{(1)}+(1-\lambda)x^{(2)} =A(\lambda y_1+(1-\lambda)y_2),

括号内仍属于 $C$ 。同理，凸集在仿射映射下的逆像也凸。

证明：若 $S$ 凸，则任意 $m$ 个点 $x^{(i)}\in S$ 与权重 $\lambda_i\ge0,\sum_i\lambda_i=1$ 满足

\sum_{i=1}^m\lambda_ix^{(i)}\in S.

用归纳法。 $m=2$ 就是定义。假设对 $m$ 成立，对 $m+1$ 个点令

\hat x=\sum_{i=1}^m\frac{\lambda_i}{1-\lambda_{m+1}}x^{(i)}.

若 $\lambda_{m+1}<1$ ，归纳假设给 $\hat x\in S$ ，再写成

(1-\lambda_{m+1})\hat x+\lambda_{m+1}x^{(m+1)}\in S.

$\lambda_{m+1}=1$ 时结论显然。

扫描中分别检查了常 Hessian、含指数项的 Hessian，以及 Hessian 不对称的表达式。规范步骤是：

例如

f(x_1,x_2)=x_1^2+x_2^2+e^{x_1+x_2}

有

\nabla^2f=2I+e^{x_1+x_2} \begin{bmatrix}1&1\\1&1\end{bmatrix}\succ0,

所以严格凸。若 Hessian 不定，则函数既非凸也非凹。

若 $f$ 严格凸并存在两个不同全局极小点 $x_1,x_2$ ，则对 $0<\lambda<1$ ：

f(\lambda x_1+(1-\lambda)x_2) <\lambda f(x_1)+(1-\lambda)f(x_2)=f^*,

与 $f^*$ 最优矛盾，所以全局极小点至多一个。