最优化方法 - 作业 1

习题一 T2

设 $f(x)$ 是凸函数，则 $f(x)$ 的全局最小值集合是凸集.

证明： 设全局最小值集合为 $D$ ，那么对 $x^{\ast }\in D$ ，对于任意 $x\in \mathrm{dom}(f)$ ，都有 $f(x^{\ast })⩽f(x)$ . 考虑 $\overline{x},\tilde{x}\in D$ ，取凸组合

$$x_{\lambda }=\lambda \overline{x}+(1-\lambda )\tilde{x},\lambda \in (0,1)$$

那么根据 $f(x)$ 是凸函数，于是有

$$f(x_{\lambda })⩽\lambda f(\overline{x})+(1-\lambda )f(\tilde{x})=\min f(x)$$

这就使得不等号必须取等，从而 $x_{\lambda }\in D$ ，也就是说 $D$ 中任意两点的凸组合仍在 $D$ 中. $\square$

习题一 T4

如果对 $a,b\in C$ ，有 $\frac{a+b}{2}\in C$ ，则称 $C$ 是中点凸. 证明如果 $C$ 是闭集且中点凸，则 $C$ 是凸集.

证明： 证明 $a,b\in C$ 的任意凸组合都在 $C$ 中即可，对于任意凸组合：

$$x_{\lambda }=\lambda a+(1-\lambda )b,\forall \lambda \in (0,1)$$

考虑取中点点列收敛到 $x_{\lambda }$ ，操作方法如下：首先取 $a,b$ 的中点，然后有如下的点列：

$$x_0=a,x_1=b,x_2=\frac{a+b}{2}$$

如果 $\lambda <\frac{1}{2}$ ，那么接下来取 $x_3=\frac{1}{4}a+\frac{3}{4}b$ ，否则取 $x_3=\frac{3}{4}a+\frac{1}{4}b$ . 再考虑 $\lambda$ 和 $\frac{1}{4}$ 或 $\frac{3}{4}$ 之间的大小比较，从而取 $x_4$ ，依次类推可得

$$x_n={\lambda }_{n}a+(1-{\lambda }_n)b$$

使得 ${\lambda }_n\to \lambda$ ，而由于 $C$ 是闭集，因此 $x_n\to x_{\lambda }\in C$ . 这就证明了凸组合都在集合 $C$ 当中. $\square$

习题一 T5

证明 ${\mathbb{R}}^n$ 中的下列集合是凸集：

1. $H=\left\{x\mid p^{\mathrm{T}}x=\alpha \right\}$ ；
2. $S=\left\{x\mid p^{\mathrm{T}}x⩽\alpha \right\}$ ；
3. $S=\left\{x\mid Ax⩽b\right\}$ ，其中 $A$ 为 $m\times n$ 阶矩阵；
4. $S=\left\{x\mid Ax=b,x⩾0\right\}$ ，其中 $A$ 为 $m\times n$ 阶矩阵；
5. $S$ 为线性规划问题

$$\begin{array}{rlr}& \min & c^{\mathrm{T}}x\\ & s.t.& Ax=b\\ & & x⩾0\end{array}$$

的解集.

证明：

(1) 设 $x,y\in H$ ，则凸组合 $z=\lambda x+(1-\lambda )y,\lambda \in (0,1)$ 有：

$$\begin{array}{rl}{p}^{\mathrm{T}}z& =p^{\mathrm{T}}[\lambda x+(1-\lambda )y]\\ & =\lambda p^{\mathrm{T}}x+(1-\lambda )p^{\mathrm{T}}y\\ & =\lambda \alpha +(1-\lambda )\alpha =\alpha \end{array}$$

因此 $z\in H$ .

(2) 设 $x,y\in S$ ，则凸组合 $z=\lambda x+(1-\lambda )y,\forall \lambda \in (0,1)$ 有：

$$\begin{array}{rl}{p}^{\mathrm{T}}z& =p^{\mathrm{T}}[\lambda x+(1-\lambda )y]\\ & =\lambda p^{\mathrm{T}}x+(1-\lambda )p^{\mathrm{T}}y\\ & ⩽\lambda \alpha +(1-\lambda )\alpha =\alpha \end{array}$$

因此 $z\in S$ .

(3) 设 $x,y\in S$ ，则凸组合 $z=\lambda x+(1-\lambda )y,\forall \lambda \in (0,1)$ 有：

$$\begin{array}{rl}Az& =A[\lambda x+(1-\lambda )y]\\ & =\lambda Ax+(1-\lambda )Ay\\ & ⩽\lambda b+(1-\lambda )b=b\end{array}$$

因此 $z\in S$ .

(4) 设 $x,y\in S$ ，则凸组合 $z=\lambda x+(1-\lambda )y,\forall \lambda \in (0,1)$ 有：

$$\begin{array}{rl}Az& =A[\lambda x+(1-\lambda )y]\\ & =\lambda Ax+(1-\lambda )Ay\\ & =\lambda b+(1-\lambda )b=b\end{array}$$

因此 $z\in S$ .

(5) 设 $x,y\in S$ ，则对凸组合 $z=\lambda x+(1-\lambda )y,\forall \lambda \in (0,1)$ ，根据 (4) 可知 $z$ 符合约束条件，且考虑

$$\begin{array}{rl}{c}^{\mathrm{T}}z& =c^{\mathrm{T}}[\lambda x+(1-\lambda )y]\\ & =\lambda (c^{\mathrm{T}}x)+(1-\lambda )(c^{\mathrm{T}}y)\\ & =(\lambda +1-\lambda )\min c^{\mathrm{T}}x=\min c^{\mathrm{T}}x\end{array}$$

因此 $z\in S$ . 综上，上述的所有集合都是凸集. $\square$

习题一 T6

设 $X$ 为凸集，$\mathbf{A}$ 为 $m\times n$ 阶矩阵，则 $\left\{y\mid y=\mathbf{A}x,x\in X\right\}$ 为凸集.

证明： 设 $D=\left\{y\mid y=\mathbf{A}x,x\in X\right\}$ ，那么对

$$y_{\lambda }=\lambda y_1+(1-\lambda )y_2,\forall y_1,y_2\in D,\forall \lambda \in (0,1)$$

不妨令 $y_1=\mathbf{A}{x}_1,y_2=\mathbf{A}{x}_2$ ，考虑

$$\begin{array}{rl}{y}_{\lambda }& =\lambda \mathbf{A}{x}_1+(1-\lambda )\mathbf{A}{x}_2\\ & =\mathbf{A}[\lambda x_1+(1-\lambda )x_2]\end{array}$$

而由 $X$ 为凸集，可知 $x_{\lambda }=\lambda x_1+(1-\lambda )x_2\in X$ ，于是

$$y_{\lambda }=\mathbf{A}{x}_{\lambda },x_{\lambda }\in X$$

即 $y_{\lambda }\in D$ ，这就证明了 $D$ 为凸集. $\square$

习题一 T7

设 $X_i(i=1,\cdots ,m)$ 都是凸集，则 $\bigcap _{i=1}^m{X}_i$ 为凸集.

证明： 仅需证明两个凸集的交集还是凸集，设 $X_1,X_2$ 为凸集，则考虑做交集运算取 $x^1,x^2\in X_1\cap X_2$ ，对凸组合 $\lambda x^1+(1-\lambda )x^2$ ，根据 $X_1,X_2$ 均为凸集，分别有

$$\begin{array}{rl}& \lambda x^1+(1-\lambda )x^2\in X_1\\ & \lambda x^1+(1-\lambda )x^2\in X_2\end{array}$$

于是 $\lambda x^1+(1-\lambda )x^2\in X_1\cap X_2$ ，因此 $X_1\cap X_2$ 为凸集.

对三个及以上的情形，以两个集合的情形作为归纳基础，当 $m=k$ 成立时，对 $m=k+1$ ，有

$$\bigcap _{i=1}^{k+1}{X}_i=\left(\bigcap _{i=1}^k{X}_i\right)\cap X_{k+1}$$

为两个凸集的交，于是结果仍为凸集，由此结论成立. $\square$

习题一 T8

设 $S_1,S_2$ 为凸集，则

1. $\left\{x\mid x=x^1+x^2,x^1\in S_1,x^2\in S_2\right\}$ 为凸集.
2. $\left\{x\mid x=x^1-x^2,x^1\in S_1,x^2\in S_2\right\}$ 为凸集.

证明： 即证明集合加法和减法是保凸运算，设

$$\begin{array}{rl}& x=x^1+x^2,x^1\in S_1,x^2\in S_2\\ & y=y^1+y^2,y^1\in S_1,y^2\in S_2\end{array}$$

则

$$z=\lambda x+(1-\lambda )y=[\lambda x^1+(1-\lambda )y^1]+[\lambda x^2+(1-\lambda )y^2]$$

而其中根据 $S_1,S_2$ 均为凸集， $\lambda x^1+(1-\lambda )y^1\in S_1$ 且 $\lambda x^2+(1-\lambda )y^2\in S_2$ ，那么 $z\in S_1+S_2$ ，从而 $S_1+S_2$ 为凸集.

对于 $S_1-S_2$ ，证明方法一致，同理可得 $S_1-S_2$ 为凸集. $\square$

习题一 T9

设 $C\subset {\mathbb{R}}^n$ ，证明 $C$ 的凸包 $H(C)$ 是凸集.

证明： 设 $x,y\in H(C)$ ，则根据凸包定义，二者均可表示为 $C$ 中有限个点的凸组合：

$$\begin{array}{rl}& x=\sum _{i=1}^k{\lambda }_i{x}_i,\sum _{i=1}^k{\lambda }_i=1\\ & y=\sum _{j=1}^m{\theta }_j{y}_j,\sum _{j=1}^m{\theta }_j=1\end{array}$$

那么考虑

$$\begin{array}{rl}\beta x+(1-\beta )y& =\beta \sum _{i=1}^k{\lambda }_i{x}_i+(1-\beta )\sum _{j=1}^m{\theta }_j{y}_j\\ & =\sum _{i=1}^k\beta {\lambda }_i{x}_i+\sum _{j=1}^m(1-\beta ){\theta }_j{y}_j\end{array}$$

而其中

$$\sum _{i=1}^k\beta {\lambda }_i+\sum _{j=1}^m(1-\beta ){\theta }_j=\beta +1-\beta =1$$

于是 $\beta x+(1-\beta )y$ 也可表示为 $C$ 中有限个元素的凸组合，这就说明

$$\beta x+(1-\beta )y\in H(C)$$

即 $H(C)$ 为凸集. $\square$