最优化方法 - 作业 2

习题一 T11

证明凸集的内部和闭包还都是凸集.

证明：对凸集 $D$ ，对于其闭包 $\overline{D}$ ，若 $x,y\in \overline{D}$ ，取

$$z=\lambda x+(1-\lambda )y,\lambda \in (0,1)$$

根据闭包为闭集，存在点列 $x_n\to x$ 以及 $y_n\to y$ ，其中 $\left\{x_n\right\},\left\{y_n\right\}\subset D$ ，于是

$$z_n=\lambda x_n+(1-\lambda )y_n\in D$$

因此 $z_n\to z$ ，从而 $z\in \overline{D}$ .

对于其内部 $D^{\circ }$ ，假设其不为凸集，则存在 $\lambda$ 以及 $x,y\in D^{\circ }$ 使得

$$z=\lambda x+(1-\lambda )y\in D$$

不在 $D$ 的内部，考虑取 $r>0$ 使得 $B_r(x),B_r(y)\subset D$ ，此时可取

$$z_0\in B_r(z)\setminus D\text{\hspace{1em}(1.1)}$$

那么考虑 $\Vert z-z_0{\Vert }_2<r$ ，我们有

$$x+(z_0-z)\in B_r(x),y+(z_0-z)\in B_r(y)$$

因此

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

为 $D$ 中元素的凸组合，所以 $z_0\in D$ ，这就出现了矛盾！$\square$

习题一 T21

证明连续函数 $f:{\mathbb{R}}^n\to \mathbb{R}$ 是凸函数当且仅当：对任意 $x,y\in {\mathbb{R}}^n$ ，

$${\int }_0^{1}f(x+\lambda (y-x))\mathrm{d}\lambda ⩽\frac{f(x)+f(y)}{2}$$

证明：必要性：由于 $f$ 是凸函数，可知

$$\begin{array}{rl}{\int }_0^{1}f((1-\lambda )x+\lambda y)\mathrm{d}\lambda & ⩽{\int }_0^1[(1-\lambda )f(x)+\lambda f(y)]\mathrm{d}\lambda \\ & =\frac{f(x)+f(y)}{2}\end{array}$$

充分性：假设 $f$ 不是凸函数，则存在 ${\lambda }_0,x,y$ 使得

$$f({\lambda }_{0}x+(1-{\lambda }_0)y)>{\lambda }_{0}f(x)+(1-{\lambda }_0)f(y)$$

设

$$g(\lambda )=f(\lambda x+(1-\lambda )y)-\lambda f(x)-(1-\lambda )f(y),\lambda \in [0,1]$$

由于 $f$ 是连续函数，$g({\lambda }_0)>0$ 表明存在 $[c,d]\subset [0,1]$ 使得 $g(\lambda )>0,\forall \lambda \in [c,d]$ ，则令

$$x^{\prime }=cx+(1-c)y,y^{\prime }=dx+(1-d)y$$

设

$$G(\lambda )=f(\lambda x^{\prime }+(1-\lambda )y^{\prime })-\lambda f(x^{\prime })-(1-\lambda )f(y^{\prime }),\lambda \in [0,1]$$

那么

$$\begin{array}{rl}{\int }_0^{1}G(\lambda )\mathrm{d}\lambda & ={\int }_0^{1}f(\lambda x^{\prime }+(1-\lambda )y^{\prime })\mathrm{d}\lambda -\frac{f(x^{\prime })+f(y^{\prime })}{2}\\ & >0\end{array}$$

这和题设条件矛盾，因此 $f$ 是凸函数. $\square$

习题一 T22

设 $f:{\mathbb{R}}^n\to \mathbb{R}$ 是凸函数，$\mathrm{dom}(f)={\mathbb{R}}^n$ ，并且 $f$ 在 ${\mathbb{R}}^n$ 上有上界，证明 $f$ 是常数.

证明：假设 $f$ 不为常数，则存在 $a\ne b$ 使得 $f(a)>f(b)$ . 此时考虑

$$a=\lambda a^{\prime }+(1-\lambda )b^{\prime },b=b^{\prime }$$

那么根据凸函数定义

$$f(\lambda a^{\prime }+(1-\lambda )b^{\prime })⩽\lambda f(a^{\prime })+(1-\lambda )f(b^{\prime })$$

代入有

$$f(a)⩽\lambda f\left(\frac{a-(1-\lambda )b}{\lambda }\right)+(1-\lambda )f(b)$$

从而

$$f\left(\frac{a-(1-\lambda )b}{\lambda }\right)⩾\frac{f(a)-(1-\lambda )f(b)}{\lambda }=f(b)+\frac{f(a)-f(b)}{\lambda }$$

当 $\lambda \to 0^{+}$ 时，右侧趋于无穷，左侧是 $f$ 的函数值，这就与 $f$ 为常数相矛盾！$\square$

习题一 T23

设 $A$ 为 $m\times n$ 阶矩阵，$c$ 为 $n$ 维向量，则不等式组

$$\{\begin{array}{l}Ax⩽0\\ x⩾0\\ c^{\mathrm{T}}x>0\end{array}$$

与不等式组

$$\{\begin{array}{l}{A}^{\mathrm{T}}y⩾c\\ y⩾0\end{array}$$

有且只有一个有解.

证明：如果将第一个不等式组化为：

$$\left(\begin{array}{c}A\\ -I\end{array}\right)x⩽0,c^{\mathrm{T}}x>0$$

第二个不等式组化为

$$(A^{\mathrm{T}},-I)\left(\begin{array}{c}y\\ u\end{array}\right)=c,\left(\begin{array}{c}y\\ u\end{array}\right)⩾0$$

其中 $u=A^{\mathrm{T}}y-c⩾0$ ，则根据 Farkas 引理，上述两个不等式组有且仅有一组有解. $\square$

习题一 T24

设 $A$ 为 $m\times n$ 阶矩阵，$B$ 为 $l\times n$ 阶矩阵，$c$ 为 $n$ 维向量，则不等式组

$$\{\begin{array}{l}Ax⩽0\\ Bx=0\\ c^{\mathrm{T}}x>0\end{array}$$

与不等式组

$$\{\begin{array}{l}{A}^{\mathrm{T}}y+B^{\mathrm{T}}z=c\\ y⩾0\end{array}$$

有且仅有一个有解.

证明：对于第一个问题，有

$$Bx=0⟺\{\begin{array}{l}Bx⩽0\\ Bx⩾0\end{array}$$

从而可化为

$$\left(\begin{array}{c}A\\ B\\ -B\end{array}\right)x⩽0,c^{\mathrm{T}}x>0$$

第二个问题考虑

$$(A^{\mathrm{T}},B^{\mathrm{T}},-B^{\mathrm{T}})\left(\begin{array}{c}y\\ u\\ v\end{array}\right)=c,\left(\begin{array}{c}y\\ u\\ v\end{array}\right)⩾0$$

其中 $z=u-v$ ，根据 Farkas 引理上述两个不等式组有且仅有一个有解. $\square$