最优化方法 - 作业 3

习题一 T26

设 $A$ 为 $m\times n$ 实矩阵，$b$ 是 $m$ 维实向量且 $b\in R(A)$ . 证明系统 $x>0,Ax=b$ 有解的充要条件是系统

$$A^{\mathrm{T}}\lambda ⩾0,A^{\mathrm{T}}\lambda \ne 0,b^{\mathrm{T}}\lambda ⩽0$$

无解.

证明：先证明如下命题：

所有满足 $Ax=b$ 的 $x$ 都有 $c^{\mathrm{T}}x=d$ 的充要条件是：存在向量 $\lambda$ 使得 $c=A^{\mathrm{T}}\lambda ,d=b^{\mathrm{T}}\lambda$ .

命题充分性：由于 $c=A^{\mathrm{T}}\lambda$ 存在 $\lambda$ 使其成立，则对满足 $Ax=b$ 的 $x$ 有：

$$d=(Ax{)}^{\mathrm{T}}\lambda =x^{\mathrm{T}}{A}^{\mathrm{T}}\lambda =x^{\mathrm{T}}c=c^{\mathrm{T}}x$$

这说明充分性成立.

命题必要性：对 $Ax=b$ ，如果不存在 $x$ ，则命题前提不能成立，取使得 $Ax=b$ 的 $x$ ，则对方程组 $c=A^{\mathrm{T}}\lambda$ ，有

$$x^{\mathrm{T}}c=x^{\mathrm{T}}{A}^{\mathrm{T}}\lambda =b^{\mathrm{T}}\lambda =d$$

因此命题中有关 $\lambda$ 的向量如果有解，则同时有解.

下面说明 $c=A^{\mathrm{T}}\lambda$ 当中 $\lambda$ 的存在性，$Ax=b$ 有解且设矩阵 $A$ 的秩满足 $r=\mathrm{rank}(A)$，设矩阵 $F\in {\mathbb{R}}^{n\times (n-r)}$ 满足

$$\mathcal{R}(F)=\mathcal{N}(A)$$

令 $x_0$ 为 $Ax=b$ 的解，那么 $x$ 满足 $Ax=b$ 当且仅当存在 $y$ 使得

$$x=Fy+x_0$$

即 $x$ 可以 $x_0$ 作为特解，那么有

$$c^{\mathrm{T}}x=c^{\mathrm{T}}Fy+c^{\mathrm{T}}{x}_0=d$$

那么 $c^{\mathrm{T}}Fy=0$ ，且 $y$ 可以取 ${\mathbb{R}}^{n-r}$ 当中的任意向量，于是 $F^{\mathrm{T}}c=0$ 必须成立. 而考虑到 $\mathcal{R}(A^{\mathrm{T}})=\mathcal{N}(F^{\mathrm{T}})$ . 于是

$$A^{\mathrm{T}}\lambda =c$$

有解. 因此结论成立.

---

再利用上述命题证明本题.

必要性：假设 $A^{\mathrm{T}}\lambda ⩾0,A^{\mathrm{T}}\lambda \ne 0,b^{\mathrm{T}}\lambda ⩽0$ 有解，那么令 $A^{\mathrm{T}}\lambda =c⩾0$ ，$b^{\mathrm{T}}\lambda =d⩽0$ ，则根据引理， $c^{\mathrm{T}}x=d$ . 但是 $x>0$ ，这就在正负性上出现了矛盾.

充分性：根据 $b\in R(A)$ ，说明 $Ax=b$ 有解，如果 $x>0,Ax=b$ 无解，说明对 $Ax=b$ 的解 $x_0$ 必有分量 $⩽0$ ，考虑构造 $d=0\in {\mathbb{R}}^n$ ，从 $c^{\mathrm{T}}{x}_0=0$ 解出 $c^{\mathrm{T}}⩾0,c^{\mathrm{T}}\ne 0$ ，则根据引理，存在 $\lambda$ 使得

$$c=A^{\mathrm{T}}\lambda ⩾0,b^{\mathrm{T}}\lambda =0⩾0$$

这就出现了矛盾. 于是 $x>0,Ax=b$ 有解. $\square$

习题一 T27

设 $f(x):{\mathbb{R}}^n\to {\mathbb{R}}^1$ 和 $\phi (t):{\mathbb{R}}^1\to {\mathbb{R}}^1$ 都是凸函数，$\phi (t)$ 还是单增函数，证明复合函数 $h(x)=\phi (f(x))$ 是凸函数.

证明：首先 $f$ 是凸函数且 $\phi$ 单增，因此：

$$\begin{array}{rl}h(\lambda x^1+(1-\lambda )x^2)& =\phi (f(\lambda x^1+(1-\lambda )x^2))\\ & ⩽\phi (\lambda f(x^1)+(1-\lambda )f(x^2))\end{array}$$

然后考虑设 $y^1=f(x^1),y^2=f(x^2)$ . 因此

$$=\phi (\lambda y^1+(1-\lambda )y^2)⩽\lambda \phi (y^1)+(1-\lambda )\phi (y^2)$$

因此

$$h(\lambda x^1+(1-\lambda )x^2)⩽\lambda h(x^1)+(1-\lambda )h(x^2)$$

即 $h$ 是凸函数. $\square$

习题一 T28

若函数 $\psi :{\mathbb{R}}^n\to {\mathbb{R}}^n$ ，对任意 $x,y\in \mathrm{dom}(\psi )$ ，

$$(\psi (x)-\psi (y){)}^{\mathrm{T}}(x-y)⩾0$$

都称 $\psi$ 是单调映射，设 $f:{\mathbb{R}}^n\to \mathbb{R}$ 是可微凸函数，则 $\nabla f$ 是单调映射，反过来，每个单调映射都是某个凸函数的梯度，对吗？

证明：我们首先证明前一个命题，若 $f$ 为可微凸函数，则

$$\nabla f(x)(y-x{)}^{\mathrm{T}}⩽f(y)-f(x)$$

同时

$$\nabla f(y)(y-x{)}^{\mathrm{T}}⩾f(y)-f(x)$$

相减可得

$$(\nabla f(y)-\nabla f(x){)}^{\mathrm{T}}(y-x)⩾0$$

即 $\nabla f$ 是单调映射.

反过来不一定成立，在 $n=1$ 时，凸函数的导数由 Darboux 定理可知必须由介值性，但单调函数不一定具有介值性，取一个不连续，没有介值性的单调映射即可. $\square$

习题一 T29

设

$$q(x)=\frac{1}{2}{x}^{\mathrm{T}}Bx+b^{\mathrm{T}}x+c$$

其中 $B\in {\mathbb{R}}^{n\times n}$ 为对称矩阵，$b\in {\mathbb{R}}^n,c\in \mathbb{R}$ ，证明 $q(x)$ 有唯一极小点的充分必要条件是矩阵 $B$ 正定.

证明：设 $B=(b_{ij})$ 以及 $b=({\beta }_1,\cdots ,{\beta }_n{)}^{\mathrm{T}}$，那么

$$q(x)=\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{b}_{ij}{x}_i{x}_j+\sum _{i=1}^n{\beta }_i{x}_i+c$$

先对 $x_m$ 求导：

$$\frac{\partial }{\partial x_m}q(x)={\beta }_m+b_{mm}{x}_m+\sum _{i=1,i\ne m}^n{b}_{mi}{x}_i+\sum _{j=1,j\ne m}^n{b}_{im}{x}_j$$

再对 $x_k$ 求导

$$\frac{\partial }{\partial x_k}\left(\frac{\partial }{\partial x_m}q(x)\right)=b_{mk}=b_{km}$$

于是 $B$ 即为 $q(x)$ 的 Hesse 矩阵.

对于充分性，$B$ 正定说明只有在 $x=0$ 时 $q(x)$ 的 Hesse 矩阵才为零矩阵，从而 $0$ 是唯一极小点.

对于必要性，$q(x)$ 仅有一个唯一极小点，说明在极小点之外的其它地方 Hesse 矩阵均大于 $0$ ，也就是 $B>0$ . $\square$

习题一 T30

设 $f:\mathbb{R}\to \mathbb{R}$ 是凸函数，$a<b$ ：

1. 证明：

$$f(x)⩽\frac{b-x}{b-a}f(a)+\frac{x-a}{b-a}f(b),\forall x\in [a,b]$$

2. 证明

$$\frac{f(x)-f(a)}{x-a}⩽\frac{f(b)-f(a)}{b-a}⩽\frac{f(b)-f(x)}{b-x},\forall x\in [a,b]$$

3. 设 $f$ 是可微的，由 2 证明

$$f^{\prime }(a)⩽\frac{f(b)-f(a)}{b-a}⩽f^{\prime }(b)$$

4. 设 $f$ 是二次可微的，由 3 证明 $f^{\prime \prime }(a)⩾0,f^{\prime \prime }(b)⩾0$ .

证明： (1) 设

$$\lambda =\frac{b-x}{b-a}$$

于是根据凸函数定义：

$$f(x)=f(\lambda a+(1-\lambda )b)⩽\lambda f(a)+(1-\lambda )f(b)$$

即题中不等式.

(2) 将 (1) 中不等式转化为

$$(b-a)f(x)⩽(b-x)f(a)+(x-a)f(b)$$

两侧减去 $(b-a)f(a)$ ，那么有

$$(b-a)[f(x)-f(a)]⩽(x-a)[f(b)-f(a)]$$

这就得到了第一个不等号. 两侧减去 $(b-a)f(b)$ 可得

$$(b-a)[f(x)-f(b)]⩽(b-x)[f(a)-f(b)]$$

因此题中不等式成立.

(3) 第一个不等号由 (2) 不等式，令 $x\downarrow a$ ，可得

$$f^{\prime }(a)=f^{\prime }(a+0)⩽\frac{f(b)-f(a)}{b-a}$$

令 $x\uparrow b$ 可得

$$\frac{f(b)-f(a)}{b-a}⩽f^{\prime }(b-0)=f^{\prime }(b)$$

(4) (3) 说明对于任意的 $a<b$ 都有 $f^{\prime }(a)⩽f^{\prime }(b)$ ，这就说明

$$f^{\prime \prime }(a)=\underset{b\to a}{\lim }\frac{f^{\prime }(b)-f^{\prime }(a)}{b-a}⩾0$$

对 $f^{\prime }(b)⩾0$ 证明同理. $\square$

习题一 T31

证明函数

$$f(x)=-{\left(\prod _{i=1}^n{x}_i\right)}^{\frac{1}{n}}$$

在 ${\mathbb{R}}_{+}^n$ 中是凸函数.

证明：考虑

$$-f(\lambda x+(1-\lambda )y)={\left(\prod _{i=1}^n(\lambda x_i+(1-\lambda )y_i)\right)}^{\frac{1}{n}}$$

以及

$$-\lambda f(x)-(1-\lambda )f(y)=\lambda {\left(\prod _{i=1}^n{x}_i\right)}^{\frac{1}{n}}+(1-\lambda ){\left(\prod _{i=1}^n{y}_i\right)}^{\frac{1}{n}}$$

之间的大小关系，注意到

$$\begin{array}{rl}\lambda {\left(\prod _{i=1}^n{x}_i\right)}^{\frac{1}{n}}+(1-\lambda ){\left(\prod _{i=1}^n{y}_i\right)}^{\frac{1}{n}}& ={\left(\prod _{i=1}^n\lambda x_i\right)}^{\frac{1}{n}}+{\left(\prod _{i=1}^n(1-\lambda )y_i\right)}^{\frac{1}{n}}\\ & ⩽\prod _{i=1}^n\left({\lambda }^{\frac{1}{n}}{x}_i^{\frac{1}{n}}+(1-\lambda {)}^{\frac{1}{n}}{y}_i^{\frac{1}{n}}\right)\\ & ⩽{\left(\prod _{i=1}^n(\lambda x_i+(1-\lambda )y_i)\right)}^{\frac{1}{n}}\end{array}$$

从而

$$-\lambda f(x)-(1-\lambda )f(y)⩽-f(\lambda x+(1-\lambda )y)$$

即 $f(x)$ 是凸函数. $\square$