6¶

习题1¶

下面的集合哪些是凸集？请说明理由。

(a) 平板，即形如 $\{x \in \mathbb{R}^n \mid \alpha \leq a^T x \leq \beta\}$ 的集合。

(b) 矩形，即形如 $\{x \in \mathbb{R}^n \mid \alpha_i \leq x_i \leq \beta_i, i = 1 \dots, n\}$ 的集合。当 n > 2 时，矩形有时也称为超矩形。

(c) 楔形，即 $ {x \in \mathbb{R}^n \mid a_1^T x \leq b_1, a_2^T x \leq b_2} $。

(d) 距离给定点比距离给定集合近的点构成的集合，即 $ {x \mid |x - x_0|_2 \leq |x - y|_2, \forall y \in S} $ 其中 $S \subseteq \mathbb{R}^n$

(e)令 $C \subseteq \mathbb{R}^n$ 为下列二次不等式的解集： $C = \{x \in \mathbb{R}^n \mid x^T A x + b^T x + c \leq 0\}$，其中 $A \in \mathbb{R}^{n \times n}$, $b \in \mathbb{R}^n$, $c \in \mathbb{R}$。如果 $A \succeq 0$（半正定），那么 $C$ 是凸集吗？

解：

(a) 平板是两个半空间的交集，因此是一个凸集。

(b) 矩形是有限个半空间的交集，因此是一个凸集。

(c) 楔形是两个半空间的交集，因此是一个凸集。

(d) 该集合可以写为： $$ \bigcap_{y \in S} {x \mid |x - x_0|_2 \leq |x - y|_2} $$

由于它是半空间的交集，因此是一个凸集。

(e) 设 $ f(x) = x^T A x + b^T x + c $，则 $\nabla^2 f(x) = 2A \succeq 0,$由此可知 $ f(x) $ 是凸函数。

对于任意 $ x_1, x_2 \in C $ 以及 $ t \in (0, 1) $，有 $f(tx_1 + (1 - t)x_2) \leq t f(x_1) + (1 - t) f(x_2) \leq 0,$

因此 $t x_1 + (1 - t)x_2 \in C,$ 说明 $ C $ 是凸集。

习题2¶

下面的函数哪些是凸函数？请说明理由。

$f(x) = e^x + 1, x \in \mathbb{R}$
$f(x) = \max(\|Ax + b\|_2, \|x^T x\|_1), A \in \mathbb{R}^{m \times n}, x \in \mathbb{R}^n, b \in \mathbb{R}^m$
$f(x) = -\cos x, x \in [-\pi/2, \pi/2]$
$f(\mathbf{x}) = \left( \sum_{i=1}^n x_i^p \right)^{1/p}$，其中 $p \in (0, 1)$，定义域为 $\mathbf{x} > 0$

解：

$f''(x) = e^x > 0$，所以是凸函数。
因为 $\|\cdot\|_2, \|\cdot\|_1$ 是凸函数，所以 $\|Ax + b\|_2, \|x^T x\|_1$ 是凸函数，$\max$ 是保凸运算，所以 $f(x)$ 是凸函数。
$f''(x) = \cos x > 0, x \in [-\pi/2, \pi/2]$，所以是凸函数。
设 $ J(x) = \text{Diag}\left(\frac{1}{x_1}, \frac{1}{x_2}, \dots, \frac{1}{x_n}\right) $，则

\[ \nabla f(x) = \left(\left(\frac{f}{x_1}\right)^{1-p}, \left(\frac{f}{x_2}\right)^{1-p}, \dots, \left(\frac{f}{x_n}\right)^{1-p} \right)^T, \]

\[ \nabla^2 f(x) = -\frac{1-p}{f} J(x) A(x) J(x), \]

其中

\[ A(x) = \begin{bmatrix} (f^p - x_1^p)x_1^p & -x_1^p x_2^p & \cdots & -x_1^p x_n^p \\ -x_2^p x_1^p & (f^p - x_2^p)x_2^p & \cdots & -x_2^p x_n^p \\ \vdots & \vdots & \ddots & \vdots \\ -x_n^p x_1^p & -x_n^p x_2^p & \cdots & (f^p - x_n^p)x_n^p \end{bmatrix}. \]

只需证明 $ A(x) $ 半正定：对任意 $ y \in \mathbb{R}^n $ 且 $ y \neq 0 $，

\[ y^T A(x) y = \left( \sum_{k=1}^n y_k^2 x_k^p \right) f^p - \left( \sum_{k=1}^n y_k x_k^p \right)^2. \]

由柯西不等式：

\[ \left( \sum_{k=1}^n y_k^2 x_k^p \right)\left( \sum_{k=1}^n x_k^p \right) \geq \left( \sum_{k=1}^n y_k x_k^p \right)^2, \]

所以

\[ y^T A(x) y \geq 0. \]

因此 $ A(x) \succeq 0 $，且 $\nabla^2 f(x) \preceq 0$ 所以该函数是凹函数。

习题3¶

用最速下降法和精确线搜索计算 $\min f(x) = x_1^2 + x_2^2 + x_3^2$，初始点 $x^{(0)} = (2, 2, 1)^T$。

当 $|f(x^{(n+1)}) - f(x^{(n)})| < 0.001$ 时迭代终止。

解：由题意得， $ f(x) = x^T x, \quad \nabla_x f(x) = 2x $ 设最速下降法的步长为 $$\lambda$$，那么
$$ f(x - \lambda \nabla_x f(x)) = (x - \lambda \nabla_x f(x))^T (x - \lambda \nabla_x f(x)) $$

\[ = x^T x - 2\lambda \nabla_x f(x)^T x + \lambda^2 \nabla_x f(x)^T \nabla_x f(x) \]

在 $$x - \lambda \nabla_x f(x)$$ 方向上，使 $$f(x)$$ 最小的 $$\lambda$$ 满足

\[ \frac{\partial f(x - \lambda \nabla_x f(x))}{\partial \lambda} = -2 \nabla_x f(x)^T x + 2\lambda \nabla_x f(x)^T \nabla_x f(x) \]

得

\[ \lambda = \frac{\nabla_x f(x)^T x}{\nabla_x f(x)^T \nabla_x f(x)} = \frac{1}{2} \]

所以，

\[ x^{(1)} = x^{(0)} - \frac{1}{2} \nabla_x f(x^{(0)}) = (0, 0, 0)^T \]

\[ f(x^{(1)}) = 0 \]

\[ x^{(2)} = x^{(1)} - \frac{1}{2} \nabla_x f(x^{(1)}) = (0, 0, 0)^T \]

\[ f(x^{(2)}) = 0 \]

同理可得，$$f(x^{(n)}) = 0 \, (n > 0)$$，因此当 $|f(x^{(n+1)}) - f(x^{(n)})| = 0 < 0.001$ 时，迭代终止。

习题4¶

使用梯度下降法和固定步长 $\lambda = 0.01$ 计算 $\min f(x) = (x_1 - 1)^2 + 16(x_2 - 2)^2$，初始点 $x^{(0)} = (2, 3)^T$，迭代两步后终止。

解：具体迭代结果：

$k$	$x^{(k)T}$	$g_k^T$	$f_k$	$\\|g_k\\|_\infty$
0	$(2, 3)$	$(2, 32)$	17	32
1	$(1.98, 2.68)$	$[1.96, 21.76]$	8.3588	21.76
2	$(1.96, 2.46)$	$[1.9208, 14.7968]$	4.3434	14.7968

习题5¶

设 $f: \mathbb{R} \to \mathbb{R}$ 递增，在其定义域 $(a, b)$ 是凸函数。令 $g$ 表示其反函数，即具有定义域 $(f(a), f(b))$，且对所有 $a < x < b$ 满足 $g(f(x)) = x$。函数 $g$ 是凸函数还是凹函数？为什么？

函数 $g$ 是凹函数。

证明：因为 $f(x)$ 是凸函数，根据定义，取 $0 \leq \lambda \leq 1$，有：

\[ f(\lambda x + (1 - \lambda)y) \leq \lambda f(x) + (1 - \lambda)f(y). \]

将下式代入上式： $$ x=g(u),y=g(v) $$ 可得： $$ \lambda u+ (1-\lambda)v \geq f(\lambda g(u)+ (1-\lambda)g(v) ) \quad (1) $$ $f$ 单调递增，则必然 $g$ 单调递增

将(1)式两边同时代入 $g$ ，可得 $$ g(\lambda u+ (1-\lambda)v) \geq g(f(\lambda g(u)+ (1-\lambda)g(v) ))=\lambda g(u)+ (1-\lambda)g(v) $$ 根据定义可知 $g$ 是凹函数

习题6¶

考虑极小化二次函数
$$ f_0(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T P \mathbf{x} + \mathbf{q}^T \mathbf{x} + r, $$ 其中，$P \in S_+^n$（$n$ 阶半正定矩阵）。给出 $\mathbf{x}$ 为 $f_0$ 最小解的充分必要条件，并说明 $\mathbf{x}$ 何时无解，何时有唯一解，有多个解。

【证明】

由于 $r$ 为常数项，与 $f_0$ 的最小解条件没有关系，所以我们只需要考虑 $f_1(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T P \mathbf{x} + \mathbf{q}^T \mathbf{x}$

结论如下：(a) $ f_1(\mathbf{x}) $ 存在全局极小值当且仅当 $P $ 半正定且 $ \mathbf{q} $ 在 $P$ 的列空间中；若 $ P $ 半正定，则满足 $ P\mathbf{x} = -\mathbf{q} $ 的 $ \mathbf{x} $ 均为 $ f_1(\mathbf{x}) $ 的全局极小值点。(b) $f_1(\mathbf{x})$ 的全局极小值唯一当且仅当 $ P $ 严格正定。

(a) 充分性：由于 $ \mathbf{q} $ 属于 $ P $ 的列空间，存在 $ v $ 使得 $ Pv = -\mathbf{q} $，任取 $ w $，有
$$ f_1(v + w) = \mathbf{q}^T (v + w) + \frac{1}{2} (v + w)^T P (v + w) $$

\[ = \left( \mathbf{q}^T v + \frac{1}{2} v^T P v \right) + \mathbf{q}^T w + (Pv)^T w + \frac{1}{2} w^T P w \]

\[ = f_1(v) + \frac{1}{2} w^T P w \geq f_1(v) \]

由 $ P $ 半正定知 $ v $ 是全局极小值点。

必要性：假设 $v$ 是全局极小值点，由 $\nabla f_1(v) = Pv + \mathbf{q} = 0$ 知 $ \mathbf{q} $ 位于 $ P $ 的列空间，借助二阶必要条件知
$$ \nabla^2 f_1(v) = P $$ 半正定。

(b) 充分性：只需注意到 (a) 中不等式，当 $ w \neq 0 $ 时 $w^T P w > 0$ 这说明了最小值点的唯一性。

必要性：若 $P$ 不正定，$ v $ 是全局极小值点，此时存在 $ w \neq 0 $ 使得 $Pw = 0,$

于是 $f_1(v + w) = f_1(v)$，这说明最小值点不唯一。

习题7¶

$f$ 为正定二次函数：
$$ f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T A \mathbf{x} + \mathbf{b}^T \mathbf{x}, $$ $\mathbf{d}^{(k)}$ 为下降方向，$\mathbf{x}^{(k)}$ 为当前迭代点。

试求出精确线搜索步长：
$$ \alpha_k = \arg\min_{\alpha > 0} f\left(\mathbf{x}^{(k)} + \alpha \mathbf{d}^{(k)}\right), $$ 并由此推导出最速下降法的步长满足公式：
$$ \alpha_k = \frac{|\nabla f(\mathbf{x}^{(k)})|^2}{\nabla f(\mathbf{x}^{(k)})^T A \nabla f(\mathbf{x}^{(k)})}. $$

证明：

此时 $ f(x^k + \alpha d^k) $ 关于 $ \alpha $ 强凸，由一阶条件知 $$ \frac{d}{d\alpha} f(x^k + \alpha_k d^k) = \alpha_k (d^k)^T A d^k + (x^k)^T A d^k + b^T d^k = 0. $$

于是精确线搜索步长为

\[ \alpha_k = - \frac{(x^k)^T A d^k + b^T d^k}{(d^k)^T A d^k} = - \frac{(A x^k + b)^T d^k}{(d^k)^T A d^k}. \]

在最速下降法中，$ d^k = -\nabla f(x^k) = -(A x^k + b) $，代入上述式即得

\[ \alpha_k = \frac{\|\nabla f(x^k)\|^2}{\nabla f(x^k)^T A \nabla f(x^k)}. \]

习题8¶

请根据本学期所学知识，针对某一知识点出一道题目并做解答。（题目涉及范围不限）

\(k\)	\(x^{(k)T}\)	\(g_k^T\)	\(f_k\)	\(\\|g_k\\|_\infty\)
0	\((2, 3)\)	\((2, 32)\)	17	32
1	\((1.98, 2.68)\)	\([1.96, 21.76]\)	8.3588	21.76
2	\((1.96, 2.46)\)	\([1.9208, 14.7968]\)	4.3434	14.7968