2025-2026学年下学期期中_含答案

2025-2026学年下学期期中试卷

第一题 选择题（每小题 4 分，共 20 分）

1. 下列集合中一定是凸集的是 ________.

   A. $\{x \in \mathbb{R}^n : \|x\|_2 = 1\}$
   B. $\{x \in \mathbb{R}^n : a^\top x \le b\}$
   C. $\{x \in \mathbb{R} : x \le -1\} \cup \{x \in \mathbb{R} : x \ge 1\}$
   D. $\{x \in \mathbb{R}^2 : x_1^2 + x_2^2 \ge 1\}$

   解：

   B

   半空间 $\{x \in \mathbb{R}^n : a^\top x \le b\}$ 是凸集。事实上，若 $a^\top x \le b$，$a^\top y \le b$，且 $0 \le \theta \le 1$，则

   $$a^\top(\theta x + (1 - \theta)y) = \theta a^\top x + (1 - \theta)a^\top y \le \theta b + (1 - \theta)b = b.$$

   其余选项一般不是凸集：单位球面、两个区间的并以及单位圆盘外部都不满足两点连线仍在集合内。

   ---

2. 设 $f : \mathbb{R}^n \to \mathbb{R}$ 为可微凸函数，则 $x^\star$ 是无约束问题 $\min_x f(x)$ 的全局最优解当且仅当 ________.

   A. $\nabla^2 f(x^\star) \succ 0$
   B. $f(x^\star) = 0$
   C. $\nabla f(x^\star) = 0$
   D. $\|\nabla f(x^\star)\|_2 = 1$

   解：

   C

   可微凸函数满足一阶凸性不等式

   $$f(y) \ge f(x) + \nabla f(x)^\top (y - x), \quad \forall y.$$

   若 $\nabla f(x^\star) = 0$，则 $f(y) \ge f(x^\star)$ 对任意 $y$ 成立，因此 $x^\star$ 是全局最优解。反过来，若 $x^\star$ 是无约束全局最优解，则一阶必要条件给出 $\nabla f(x^\star) = 0$。

   ---

3. 设 $A \in \mathbb{R}^{n \times n}$ 对称正定，$b \in \mathbb{R}^n$，则二次函数 $f(x) = \frac{1}{2}x^\top Ax - b^\top x$ 的唯一极小点 $x^\star$ 满足 ________.

   A. $Ax^\star = b$
   B. $x^\star = Ab$
   C. $A^{-1}x^\star = b$
   D. $Ax^\star = -b$

   解：

   A

   对

   $$f(x) = \frac{1}{2}x^\top Ax - b^\top x$$

   求梯度得

   $$\nabla f(x) = Ax - b.$$

   因为 $A$ 对称正定，所以 $f$ 严格凸，驻点就是唯一极小点。令 $\nabla f(x^\star) = 0$，得 $Ax^\star = b$。

   ---

4. 对可微函数 $f$，若在点 $x$ 处有 $\nabla f(x)^\top d < 0$，则 $d$ 是 $f$ 在 $x$ 处的 ________.

   A. 上升方向
   B. 可行方向
   C. 下降方向
   D. 零方向

   解：

   C

   方向导数为

   $$f'(x; d) = \nabla f(x)^\top d.$$

   若 $\nabla f(x)^\top d < 0$，则沿 $d$ 方向作足够小的正步长移动时，函数值的一阶变化为负，因此 $d$ 是下降方向。

   ---

5. 设 $F(x) = \mathbb{E}_{\xi}[f(x;\xi)]$，随机梯度下降法中使用 $g_k = \nabla f(x_k;\xi_k)$。为使 $g_k$ 成为 $\nabla F(x_k)$ 的无偏估计，通常要求 ________.

   A. $g_k = 0$
   B. $\mathbb{E}[g_k \mid x_k] = 0$
   C. $\|g_k\|_2 = 1$
   D. $\mathbb{E}[g_k \mid x_k] = \nabla F(x_k)$

   解：

   D

   随机梯度 $g_k$ 是 $\nabla F(x_k)$ 的无偏估计，正是指在给定当前迭代点 $x_k$ 的条件下，

   $$\mathbb{E}[g_k \mid x_k] = \nabla F(x_k).$$

   这保证随机梯度的平均方向等于真实目标函数的梯度方向。

---

第二题 填空题（每小题 4 分，共 20 分）

1. 设 $f(x, y) = x^2 + xy + 2y^2$，则 $\nabla f(1, 1) =$ ________.

   解：

   $$\nabla f(1, 1) = \begin{pmatrix} 3\\ 5 \end{pmatrix}$$

   因为

   $$\nabla f(x, y) = \begin{pmatrix} 2x + y\\ x + 4y \end{pmatrix},$$

   所以

   $$\nabla f(1, 1) = \begin{pmatrix} 3\\ 5 \end{pmatrix}.$$

   ---

2. 向量 $v = (1, -2, 2)^\top$ 的二范数 $\|v\|_2 =$ ________.

   解：

   $3$

   由二范数定义，

   $$\|v\|_2 = \sqrt{1^2 + (-2)^2 + 2^2} = \sqrt{9} = 3.$$

   ---

3. 设 $h(x_1, x_2) = |x_1| + |x_2|$，则 $h$ 在点 $(0, 2)$ 处的次微分 $\partial h(0, 2) =$ ________.

   解：

   $$\partial h(0, 2) = \left\{ \begin{pmatrix} s\\ 1 \end{pmatrix} : -1 \le s \le 1 \right\}.$$

   因为

   $$h(x_1, x_2) = |x_1| + |x_2|,$$

   所以其每个分量可以分别求次微分。对第一项，$x_1 = 0$，有

   $$\left.\partial |x_1|\right|_{x_1 = 0} = [-1, 1].$$

   对第二项，$x_2 = 2 > 0$，有

   $$\left.\partial |x_2|\right|_{x_2 = 2} = \{1\}.$$

   因此得到上式。

   ---

4. 设 $f$ 可微且梯度 Lipschitz 常数为 $L = 4$。令 $x^+ = x - \frac{1}{4}\nabla f(x)$，则由二次上界引理可得 $f(x^+) \le f(x) -$ ________.

   解：

   $$\frac{1}{8}\|\nabla f(x)\|_2^2$$

   由二次上界引理，对任意步长 $\alpha > 0$ 有

   $$f(x - \alpha \nabla f(x)) \le f(x) - \alpha \|\nabla f(x)\|_2^2 + \frac{L\alpha^2}{2}\|\nabla f(x)\|_2^2.$$

   因此

   $$f(x - \alpha \nabla f(x)) \le f(x) - \left(\alpha - \frac{L\alpha^2}{2}\right) \|\nabla f(x)\|_2^2.$$

   本题中 $L = 4$，$\alpha = \frac{1}{4}$，所以

   $$\alpha - \frac{L\alpha^2}{2} = \frac{1}{4} - \frac{4}{2} \cdot \frac{1}{16} = \frac{1}{8}.$$

   故应填 $\frac{1}{8}\|\nabla f(x)\|_2^2$。

   ---

5. 在次梯度法或随机梯度下降法的基本收敛性分析中，常用的递减步长条件为 $\sum_{k=0}^{\infty}\alpha_k =$ ________，且 $\sum_{k=0}^{\infty}\alpha_k^2$ ________.

   解：

   两个空依次填 $+\infty$ 和“收敛”（或 $< +\infty$）。

   常用的递减步长条件为

   $$\sum_{k=0}^{\infty}\alpha_k = +\infty, \qquad \sum_{k=0}^{\infty}\alpha_k^2 < +\infty.$$

---

第三题（10 分）

设 $A \in \mathbb{R}^{m \times n}$，$b \in \mathbb{R}^{m}$，$\lambda > 0$，考虑正则化最小二乘模型

$$\min_{x \in \mathbb{R}^n}\ \phi(x) := \frac{1}{2}\|Ax - b\|_2^2 + \frac{\lambda}{2}\|x\|_2^2.$$

判断该问题是否为凸优化问题，求 $\nabla \phi(x)$，并写出 $x^\star$ 为全局最优解的一阶充要条件。

解：

函数 $x \mapsto \frac{1}{2}\|Ax - b\|_2^2$ 是凸二次函数，因为其海瑟矩阵为 $A^\top A \succeq 0$；函数 $x \mapsto \frac{\lambda}{2}\|x\|_2^2$ 也是凸函数。因此 $\phi$ 是凸函数，该问题是无约束凸优化问题。

进一步地，

$$\nabla^2 \phi(x) = A^\top A + \lambda I \succeq \lambda I \succ 0,$$

所以 $\phi$ 严格凸，最优解唯一。

由链式法则，

$$\nabla \left(\frac{1}{2}\|Ax - b\|_2^2\right) = A^\top(Ax - b), \qquad \nabla \left(\frac{\lambda}{2}\|x\|_2^2\right) = \lambda x.$$

故

$$\nabla \phi(x) = A^\top(Ax - b) + \lambda x.$$

由于 $\phi$ 可微且凸，$x^\star$ 为全局最优解当且仅当

$$\nabla \phi(x^\star) = 0.$$

也就是

$$A^\top(Ax^\star - b) + \lambda x^\star = 0,$$

等价于

$$(A^\top A + \lambda I)x^\star = A^\top b.$$

---

第四题（10 分）

求无约束优化问题

$$\min_{(x,y) \in \mathbb{R}^2}\ f(x, y) = x^2 + xy + y^2 - 2x - y$$

的最优解和最优值，并说明该最优解是否唯一。

解：

有

$$\nabla f(x, y) = \begin{pmatrix} 2x + y - 2\\ x + 2y - 1 \end{pmatrix}, \qquad \nabla^2 f(x, y) = \begin{pmatrix} 2 & 1\\ 1 & 2 \end{pmatrix}.$$

下面判断二次项对应的海瑟矩阵是否正定。记

$$H = \nabla^2 f(x, y) = \begin{pmatrix} 2 & 1\\ 1 & 2 \end{pmatrix}.$$

由于 $H$ 是实对称矩阵，可用顺序主子式判别正定性：

$$\Delta_1 = 2 > 0,\qquad \Delta_2 = \det(H) = \begin{vmatrix} 2 & 1\\ 1 & 2 \end{vmatrix} = 4 - 1 = 3 > 0.$$

因此 $H \succ 0$。所以二次型

$$\begin{pmatrix}u & v\end{pmatrix} H \begin{pmatrix}u\\v\end{pmatrix} = 2u^2 + 2uv + 2v^2$$

对任意 $(u, v) \ne (0, 0)$ 均为正，即 $f$ 是严格凸二次函数，最优解唯一。

令 $\nabla f(x, y) = 0$，得到

$$\begin{cases} 2x + y = 2,\\ x + 2y = 1, \end{cases}$$

解得 $x = 1,\ y = 0$。

最优值为

$$f(1, 0) = 1 - 2 = -1.$$

故唯一最优解为 $(1, 0)$，最优值为 $-1$。

---

第五题（10 分）

对函数

$$f(x, y) = \frac{1}{2}(x^2 + 4y^2),$$

从初始点 $x_0 = (2, 1)^\top$ 出发，取负梯度方向 $d_0 = -\nabla f(x_0)$，并用精确线搜索确定步长

$$\alpha_0 = \arg\min_{\alpha \ge 0} f(x_0 + \alpha d_0).$$

求 $d_0$、$\alpha_0$ 和下一步迭代点 $x_1$。

解：

由

$$\nabla f(x, y) = \begin{pmatrix} x\\ 4y \end{pmatrix},$$

得

$$\nabla f(x_0) = \begin{pmatrix} 2\\ 4 \end{pmatrix}, \qquad d_0 = -\nabla f(x_0) = \begin{pmatrix} -2\\ -4 \end{pmatrix}.$$

令

$$\varphi(\alpha) = f(x_0 + \alpha d_0) = \frac{1}{2}\left[(2 - 2\alpha)^2 + 4(1 - 4\alpha)^2\right].$$

化简得

$$\varphi(\alpha) = 4 - 20\alpha + 34\alpha^2.$$

因此

$$\varphi'(\alpha) = -20 + 68\alpha = 0 \quad \Longrightarrow \quad \alpha_0 = \frac{5}{17}.$$

于是

$$x_1 = x_0 + \alpha_0 d_0 = \begin{pmatrix} 2\\ 1 \end{pmatrix} + \frac{5}{17} \begin{pmatrix} -2\\ -4 \end{pmatrix} = \begin{pmatrix} \frac{24}{17}\\ -\frac{3}{17} \end{pmatrix}.$$

---

第六题（10 分）

设函数

$$f(x, y) = e^x + y^2.$$

证明 $f$ 是凸函数，并利用可微凸函数的一阶不等式，在点 $(0, 1)$ 处给出 $f$ 的一个全局线性下界。

证明：

先证明 $f$ 是凸函数。计算海瑟矩阵：

$$\nabla^2 f(x, y) = \begin{pmatrix} e^x & 0\\ 0 & 2 \end{pmatrix}.$$

因为 $e^x > 0$ 且 $2 > 0$，所以 $\nabla^2 f(x, y) \succeq 0$ 对任意 $(x, y)$ 成立。因此 $f$ 是凸函数。

计算点 $(0, 1)$ 处的函数值和梯度：

$$f(0, 1) = e^0 + 1^2 = 2,$$$$\nabla f(x, y) = \begin{pmatrix} e^x\\ 2y \end{pmatrix}, \qquad \nabla f(0, 1) = \begin{pmatrix} 1\\ 2 \end{pmatrix}.$$

由可微凸函数的一阶不等式，

$$f(x, y) \ge f(0, 1) + \nabla f(0, 1)^\top \begin{pmatrix} x - 0\\ y - 1 \end{pmatrix}.$$

代入上式得

$$f(x, y) \ge 2 + x + 2(y - 1) = x + 2y,\quad \forall (x, y) \in \mathbb{R}^2.$$

因此 $x + 2y$ 是 $f$ 在点 $(0, 1)$ 处给出的一个全局线性下界。

---

第七题（10 分）

考虑一维不可微凸优化问题

$$\min_{x \in \mathbb{R}} f(x) = |x|.$$

直接根据次梯度定义求 $\partial f(0)$（勿用函数图像或几何直观），并说明 $x^\star = 0$ 是该问题的全局最优解。若从 $x_0 = 2$ 出发，取次梯度 $g_0 = 1$ 和步长 $\alpha_0 = 1$，用一个次梯度步计算 $x_1$。

解：

直接根据次梯度定义推导。由定义，$g \in \partial f(0)$ 当且仅当

$$f(y) \ge f(0) + g(y - 0), \quad \forall y \in \mathbb{R}.$$

对 $f(x) = |x|$，这等价于

$$|y| \ge gy, \quad \forall y \in \mathbb{R}.$$

当 $y > 0$ 时，由 $y \ge gy$ 得 $g \le 1$；当 $y < 0$ 时，由 $-y \ge gy$ 得 $g \ge -1$。因此

$$-1 \le g \le 1.$$

反过来，若 $g \in [-1, 1]$，则对任意 $y > 0$ 有 $gy \le y = |y|$，对任意 $y < 0$ 有 $gy \le -y = |y|$，对 $y = 0$ 也显然成立。因此

$$\partial f(0) = [-1, 1].$$

因为 $0 \in \partial f(0)$，由凸函数的一阶最优性条件可知 $x^\star = 0$ 是全局最优解。也可以直接看到

$$|x| \ge 0 = |0|,\quad \forall x \in \mathbb{R},$$

所以 $x = 0$ 是全局最优解。

当 $x_0 = 2$ 时，$f$ 在该点可微，且可取次梯度

$$g_0 = 1.$$

次梯度法一步为

$$x_1 = x_0 - \alpha_0 g_0 = 2 - 1 \cdot 1 = 1.$$

---

第八题（10 分）

设 $f : \mathbb{R}^n \to \mathbb{R}$ 为凸可微函数，且 $\nabla f$ 的 Lipschitz 常数为 $L > 0$。设 $x^\star$ 是 $f$ 的一个全局最优解。考虑固定步长梯度下降法

$$x_{k+1} = x_k - \frac{1}{L}\nabla f(x_k),\quad k = 0, 1, 2, \ldots.$$

证明：

1. $f(x_{k+1}) \le f(x_k) - \frac{1}{2L}\|\nabla f(x_k)\|_2^2$；
2. 对任意 $N \ge 1$，有

$$f(x_N) - f(x^\star) \le \frac{L\|x_0 - x^\star\|_2^2}{2N}.$$

证明：

由二次上界引理，对任意 $x, y \in \mathbb{R}^n$ 有

$$f(y) \le f(x) + \nabla f(x)^\top(y - x) + \frac{L}{2}\|y - x\|_2^2.$$

取 $x = x_k$，$y = x_{k+1} = x_k - \frac{1}{L}\nabla f(x_k)$，则

$$y - x = -\frac{1}{L}\nabla f(x_k).$$

代入得

$$\begin{aligned} f(x_{k+1}) &\le f(x_k) - \frac{1}{L}\|\nabla f(x_k)\|_2^2 + \frac{L}{2}\frac{1}{L^2}\|\nabla f(x_k)\|_2^2\\ &= f(x_k) - \frac{1}{2L}\|\nabla f(x_k)\|_2^2. \end{aligned}$$

这证明了第一问。

记 $g_k = \nabla f(x_k)$。由凸性的一阶不等式，

$$f(x_k) - f(x^\star) \le g_k^\top(x_k - x^\star).$$

又因为

$$x_{k+1} = x_k - \frac{1}{L}g_k,$$

所以

$$\begin{aligned} \|x_{k+1} - x^\star\|_2^2 &= \left\|x_k - x^\star - \frac{1}{L}g_k\right\|_2^2\\ &= \|x_k - x^\star\|_2^2 - \frac{2}{L}g_k^\top(x_k - x^\star) + \frac{1}{L^2}\|g_k\|_2^2. \end{aligned}$$

整理可得

$$g_k^\top(x_k - x^\star) - \frac{1}{2L}\|g_k\|_2^2 = \frac{L}{2}\left(\|x_k - x^\star\|_2^2 - \|x_{k+1} - x^\star\|_2^2\right).$$

结合第一问与凸性不等式，

$$\begin{aligned} f(x_{k+1}) - f(x^\star) &\le f(x_k) - f(x^\star) - \frac{1}{2L}\|g_k\|_2^2\\ &\le g_k^\top(x_k - x^\star) - \frac{1}{2L}\|g_k\|_2^2\\ &= \frac{L}{2}\left(\|x_k - x^\star\|_2^2 - \|x_{k+1} - x^\star\|_2^2\right). \end{aligned}$$

将上式对 $k = 0, 1, \ldots, N - 1$ 求和，得到

$$\sum_{k=0}^{N-1}\left(f(x_{k+1}) - f(x^\star)\right) \le \frac{L}{2}\|x_0 - x^\star\|_2^2.$$

由第一问知函数值单调不增，因此

$$\begin{aligned} f(x_N) - f(x^\star) &\le \frac{1}{N}\sum_{k=0}^{N-1}\left(f(x_{k+1}) - f(x^\star)\right)\\ &\le \frac{L\|x_0 - x^\star\|_2^2}{2N}. \end{aligned}$$

这说明固定步长梯度下降法在凸且梯度 Lipschitz 的情形下有 $O(1/N)$ 的函数值收敛速度。