由于下面内容多，占服务器内存大，编辑的时候卡的和ppt一样，所以很多不准确的地方没有办法细改了，看的时候遇到感觉不对的地方要注意

练习 I —— 循环矩阵

本练习聚焦于循环矩阵的特性， 尤其是循环移位矩阵P 的特征值与特征向量分析。在实际信号与图像处理、 谱分析及去卷积问题中， 经常会遇到循环矩阵的对角化问题， 所以掌握它们的特性是后续学习和研究的基础与铺垫。

—— 循环移位矩阵 ——

首先我们研究特定的循环移位矩阵P 。该矩阵的尺寸为N \times N ， 其中p_{nm} 的定义为（n,m 分别是行与列的索引）：

P 的作用是将一个N 维向量的分量下标 向后移动 一位， 并将最后一个分量放到最前面。可将之理解为对坐标的循环平移。

特征值部分

我们用\lambda_1, \lambda_2, \ldots, \lambda_N 表示P 的特征值， 同时我们也用\Lambda = \text{diag}[\lambda_1, \lambda_2, \ldots, \lambda_N] 表示包含P 特征值的对角矩阵。我们强制要求\lambda_1 = 1

1. 以N=4 的情况为例给出P 的具体形式与性质

1a. 写出P

在这个矩阵中， 每一行的 1 向右平移一列， 最下行的 1 出现在最左侧第一列。这样的结构保证了循环移位的效果。

1b. 写出Pu 的结果， 其中u 是属于\mathbb{R}^N 的向量。

1c. 写出P 的幂次， 并解释为什么P^N = I 。

可见，\times p 代表着将矩阵向右移一位， P^N = P \cdot P^{N-1} ， multiplying by p is means to shift to the right on position

1d. 证明P^tP = PP^t = I ， 并确定P^{-1} 。

因此:

2. 现在， 我们集中精力确定P 的特征值。考虑一个特征向量f 及其对应的特征值\lambda ， 满足：Pf = \lambda f 。通过逐个成分地检查这一关系， 确定P 的特征值。

f 是矩阵P 的特征向量， 特征值为\lambda

假设:

因为:

我们可以直接对上述公式左右叠乘， 可直接得到\lambda^N = 1

因此， 这些\lambda_n 是N 阶复数单位根， 等价于在复平面上均匀分布的N 个点， 即：

下面是麻烦思路， 没用， 仅供参考

因此：

由此得：

对于非零特征向量f \neq 0 ， 这意味着：

因此， 特征值\lambda 是单位圆上的复数根， 即：

3. 与前一个问题相反， 这里我们将重点确定P 的特征向量。

3a. 考虑与特征值\lambda_1 = 1 相关的特征空间， 即在循环移位下不变的向量空间。我们用f_1 表示相关的单位特征向量。

for\lambda_1 = 1 , 特征向量满足P f_1 = f_1 。这里很重要，\lambda_1 只对f_1 对应， 和其他f_n 无关。

根据前述循环右移的作用，f_1 必须在循环移位后与自身相同

这等价于向量的所有分量都相等， 即：

然后我们要对其单位归一化， 平方和等于 1：

归一化后的单位特征向量f_1 为：

• 我们这里讨论的是\lambda_1 = 1 ， 是在\lambda_n = e^{-i \frac{2\pi (n-1)}{N}} 下n=1 得到的， 其对应的特征向量即是一个所有分量都相等的向量

• 其他的特征值\lambda_2, \lambda_3, \ldots, \lambda_N 将在下面讨论

3b. 此外， 对于特征值\lambda_n 及其对应的特征向量f_n ， 确定向量f_n 的各个分量f_n(2), f_n(3), \ldots, f_n(N) 作为\lambda_n 和第一个分量f_n(1) 的函数。因此， 确定单位特征向量f_n 的集合， 其中n = 1, 2, \ldots, N 。

对于特征值\lambda_n = e^{-i \frac{2\pi (n-1)}{N}} ， 特征向量f_n 满足P f_n = \lambda_n f_n 。

矩阵P 的作用如下：

由此得递推关系

根据递推关系， 有：

对于其每个分量:

为了对特征向量f_n 单位归一化：

将f_n(k) 代入并计算模长：

• 注意，e^{-i \frac{2\pi k}{N}} 的模长一定是1

因此：

最终归一化的单位特征向量为：

或者可以表示为：

4. 特征向量矩阵， 基变换。

4a. 矩阵F 用于收集所有特征向量。给出矩阵F 的各个元素的显式公式， 并写出对于向量x \in \mathbb{R}^N 的乘积X = Fx 。

矩阵F 是由循环移位矩阵P 的特征向量构成的：

特征向量f_n 为：

综上所述， 矩阵F 的具体值为：

因此， 矩阵F 的元素F_{mn} （F 中第m 行第n 列的元素）可以表示为：

4b. 证明F 是一个正交归一矩阵， 即：F^\dagger F = FF^\dagger = I 。

由于矩阵F 本身就是一个对称矩阵， 所以其共轭转置F^{\dagger} 只关注共轭即可：

计算(F^{\dagger} F)_{mn} ：

化简得：

当m = n 时，F^{\dagger}F 的对角元素为：

当m \neq n 时， 由于复指数函数的性质， 非对角元素为 0：

因此：

5. 找出矩阵P 、F 和\Lambda 之间的对角化公式（以矩阵形式表示）。

P 的对角化形式为：

其中，\Lambda 是包含特征值的对角矩阵：

—— 循环矩阵 ——

大小为N \times N 的循环矩阵C 是基于一组N 个标量值c_1, c_2, \ldots, c_N 定义的， 如下所示：

其中涉及矩阵P 的连续幂。

6. 写出N = 4 时的矩阵C 。

当N = 4 时， 循环矩阵C 的形式为：

其中：

因此：

该矩阵的每一行都是通过将上一行循环右移一位得到的。
这是循环矩阵的定义特性。

7. 对矩阵C 进行对角化。

7a. 从第5点的答案开始， 找到表达矩阵C 对角化的矩阵关系。

矩阵P 的对角化形式为：

对于循环矩阵C ：

由于F 是酉矩阵（即F^{\dagger}F = I ）， 可以将C 表示为：

7b. 指定哪些是特征值， 并将其与系数序列c_n 的傅里叶变换建立联系。

定义矩阵C 的特征对角矩阵为：

• 其中\Lambda 是循环矩阵P 的特征值对角矩阵， 其对角元素为P 的特征值

矩阵C 的特征值为：

特征值\widetilde{\lambda}_k 实际上是系数c_n 的离散傅里叶变换 (DFT)：

这表明循环矩阵的特征值是系数c_n 的离散傅里叶变换 (DFT) 的结果。

8. 展示如何利用矩阵C 的对角形式计算循环卷积y = Cx 和v = C^{-1}u 。

    

   综上所述， 对于循环矩阵， 可以使用离散傅里叶变换（DFT）使其对角化， 并计算其特征值。利用快速傅里叶变换（FFT）算法来计算DFT， 可以非常高效地执行上述操作。这些结果使我们能够将具有循环结构的全矩阵的求逆问题转化为对角矩阵的求逆问题， 并且只需进行几次FFT计算， 从而能够快速计算某些去卷积方法。

练习 II —— 二次函数

本练习旨在研究多变量二次函数的某些性质， 包括其梯度和Hessian矩阵的推导， 以及求解它们的最小值及最小值点。这类计算在估计器作为二次准则的最小化器的发展以及数值优化算法的开发中都会出现。上述发展在一系列不同的数据处理方法中得到了应用， 例如信号和图像去卷积。

注意

本练习的目的是提醒你应该熟悉的某些结果， 练习你在操作此类函数方面的技能……这并不是严格意义上的“数学练习”， 用于推导或证明上述性质和结果。

令\varphi 为一个函数，\varphi : \mathbb{R}^N \rightarrow \mathbb{R} ， 其输入为一个向量\mathbf{x} \in \mathbb{R}^N ， 并输出以下标量量：

其中，q_0 是一个标量，\mathbf{q} 是大小为N 的向量，Q 是大小为N \times N 的对称正定矩阵。默认情况下， 向量为列向量。

1. 让我们从\varphi 函数一般形式的两个特定场景开始。

1a. 在第一个场景中， 令\mathbf{q} = 0 。在不进行任何计算的情况下， 指出\varphi 的极小值点和最小值。

这是一个纯二次函数。由于Q 是一个对称正定矩阵， 二次函数\varphi(x) 只有一个极小值点。这个极小值点在x = 0 （因为x = 0 使得所有的二次项为零）。

• 最小化点是x = 0

• 最小值是\varphi(0) = q_0

1b. 在第二个情形中， Q 是一个对角矩阵。我们用\rho_n , \ n = 1, \dots, N \ 表示 Q 对角线上元素。求\varphi 的极小值点。还要分析当 Q 与单位矩阵成比例时的情况：Q = \rho I

函数\varphi(x) 表示为： \varphi(x) = x^T Q x + q^T x + q_0

对于n = 1, 2, \ldots, N ， 我们有： \frac{\partial \varphi(x)}{\partial x_n} = 2 \rho_n x_n + q_n = 0

解得： x_n = -\frac{q_n}{2\rho_n},\ \ n = 1, 2, \ldots, N

因此， 最小化点为： x = \begin{bmatrix}-\frac{q_1}{2\rho_1}, & -\frac{q_2}{2\rho_2}, & \ldots, & -\frac{q_N}{2\rho_N}\end{bmatrix}^T

如果Q 与单位矩阵成比例：Q = \rho I ， 则： \rho_n = \rho,\ \ \text{对所有的}\ n

因此： x_n = -\frac{q_n}{2\rho},\ \ n = 1, 2, \ldots, N

2. 我们现在关注确定 \varphi 的梯度和 Hessian 矩阵。

2a. 给定点 x_0 \in \mathbb{R}^N 和位移 \varepsilon \in \mathbb{R}^N ， 写出函数 \varphi(x_0 + \varepsilon) ， 并使之关于 \varepsilon 出现三个不同的项：一个常数项， 一个线性项和一个二次项。

考虑一个平移：x = x_0 + \varepsilon ， 我们有：\varphi(x_0 + \varepsilon) = (x_0 + \varepsilon)^T Q (x_0 + \varepsilon) + q^T (x_0 + \varepsilon) + q_0

展开并简化：

• 常数项：x_0^T Q x_0 + q^T x_0 + q_0

• 线性项：2 \varepsilon^T Q x_0 + q^T \varepsilon

• 二次项：\varepsilon^T Q \varepsilon

2b. 根据上一个问题的结果， 确定点 x_0 处 \varphi 的梯度 g(x_0) 和 Hessian 矩阵 H(x_0) 。前者是大小为 N 的向量， 后者是大小为 N \times N 的矩阵。

3. 在找到梯度和 Hessian 矩阵后， 我们将确定 \varphi 的极小值点。

3a. 使用上一个问题的结果， 确定 \varphi 的极小值点 \bar{x} 。明确指出在第 1 部分的两个特定情形下得到的极小值点。

梯度g(x) 为零：2Qx + q = 0 \Rightarrow 极小值点\bar{x} 为：\bar{x} = -\frac{1}{2} Q^{-1} q

1. 特殊情况 1a：当q = 0 时，2Qx = 0 ， 因此\bar{x} = 0

2. 特殊情况 1b：当Q = \rho I ， 且\rho > 0 时， 梯度g(x) = 2\rho x + q = 0 ， 因此\bar{x} = -\frac{q}{2\rho}

3b. 将 \varphi 重写为规范形式：\varphi(x) = (x - x_0)^t M (x - x_0) + m_0 通过识别 x_0 ， M 和 m_0 。可以使用几种方法：试探法， 辨识法等。

给定：

最小化点\bar{x} 满足：

将x^T Q x 重写为规范形式：

把\bar{x} = -\frac{1}{2} Q^{-1} q 代入

把它放回到\varphi(x) 中:

识别规范形式中的参数：

3c. 给出 N = 1 和 N = 2 时的图形表示。

当Q 为对角矩阵， 取N=1 时：

二次函数\varphi(x) 表达式为：

其极小值点为：

这是一个向上开口的抛物线， 最小值的位置为：

当Q 为对角矩阵， 取N=2 时：

二次函数\varphi(x) 表达式为：

其极小值点为：

这是一个向上开口的抛物面， 最小值的位置为：

4. 方向研究。给定点 y_0 \in \mathbb{R}^N 和非零方向 \delta \in \mathbb{R}^N ， 我们将考虑沿 \delta 方向、 幅度为 \eta 的位移从 y_0 开始。我们可以构造一个新函数 \psi 它定义在 \mathbb{R} 上， 取值为 \psi(\eta) = \varphi(y_0 + \eta \delta) 。

4a. 对 \psi 进行详细分析， 特别关注其导数。

定义：

展开计算：

这表示\psi(\eta) 是\eta 的一个二次函数， 其形式为A\eta^2 + B\eta + C ， 其中：

一阶导数为：

二阶导数为：

由于Q 是正定矩阵，\delta^T Q \delta > 0 ， 因此：

练习 III —— 信号插值

矩阵的一阶泰勒展开 — 设A 是一个大小为N \times N 的方阵，I_N 是大小为N 的单位矩阵， 则假设以下公式成立：

这一结果推广了经典的标量结果\left(1 + \varepsilon \right)^{-1} \sim_{\varepsilon=0} 1 - \varepsilon 。

我们将分析一个由信号x(t) 描述的物理现象：温度、 压力、 电压、 电流， ……。为此， 我们以采样周期T_s 对信号进行采样：x_n = x(n T_s) ， 其中n = 0, \dots, N - 1 ， 且N 是一个偶数。不幸的是， 当前的测量系统无法完美地执行所需的采样， 因为其采样周期小于T_s ， 这意味着它只能测量两个采样点中的一个。此外， 测量的样本还会受到噪声的影响。因此， 测量系统只会提供M 个带噪声的采样值y_m ， 其模型如下所示：

其中e_m 表示测量误差或噪声。在接下来的内容中， 我们将误差建模为零均值的独立随机变量的实现， 且均具有相同的方差r_e 。

假设基础的物理现象在采样周期的尺度上变化缓慢：x_n 变化缓慢， 而e_n 可能变化较快。

我们将信号x_n 、 测量值y_m 和误差分量e_m 分别组合成三个向量\mathbf{x} = \begin{bmatrix} x_0, \dots, x_{N-1} \end{bmatrix}^{\top} ,\mathbf{y} = \begin{bmatrix} y_0, \dots, y_{M-1} \end{bmatrix}^{\top} 和\mathbf{e} = \begin{bmatrix} e_0, \dots, e_{M-1} \end{bmatrix}^{\top} 。我们需要解决的问题是确定信号\mathbf{x} 的各个分量， 全部分量都需要， 起始于可用的测量值\mathbf{y} ， 且不需要知道误差\mathbf{e} 的各个实现值。

通过对m = 0, \dots, M - 1 的方程（3）使用之前介绍的向量表示法进行重写， 可以得到如下形式的问题\mathbf{y} = H \mathbf{x} + \mathbf{e} ， 其中矩阵H 具有特定的结构。例如， 对于N = 6 和M = 3 的情况：

1. 计算H^{\top} H 和H H^{\top} ， 对于N = 6 ，M = 3 的情况以及一般情况。它们是否可逆？计算H^{\top} \mathbf{y} 并对其形式进行评论。

我们可以看到，H^T H 是不可逆的（因为不满秩）， 但H H^T 是可逆的：

给定：

计算H^T y ：

这是一个6 \times 1 的向量(与x \in \mathbb{R}^6 同维度)。可以看出， 这个操作将原本3 维的\mathbf{y} “嵌入”到6 维， 在相应位置放进y_0, y_1, y_2 ， 其余位置补 0。由于H 是一个“选择(或下采样)”矩阵， 把x \in \mathbb{R}^6 的某些分量映射到y \in \mathbb{R}^3 中， 所以 H^T 则将\mathbf{y} 反向嵌回\mathbb{R}^6 ， 把多余的分量置 0。

H^T \mathbf{y} 补齐了被H 采样过的分量， 它在那些未被选中的位置填入 0， 即， 在未观测到的位置填充0。

其中：

— 经验估计 —

2. 在时域和频域中分别提出一个或两个对x 的经验估计量\hat{x}_E ：

时域估计:

线性插值是一种简单的估计方法， 根据观测值y 插值得到x ：

频域估计:

在频域中， 可以通过离散傅里叶变换（DFT）进行估计。首先对y 做 DFT：

对丢失的频率分量， 假设这些频率分量为零（零填充）：

用一个合适的低通滤波器去“平滑”这些 0， 从而得到“更平滑”的插值结果。

然后通过 IDFT 恢复时域信号：

— 最小二乘估计方法 —

我们将首先尝试使用最小二乘法来解决提出的问题。因此， 我们有以下准则：

我们将定义最小二乘估计量为该准则的最小化值， 即使上述准则最小化的\mathbf{x} 值。

3. 证明上述准则没有唯一的极小值。给出其极小值集并提供适当的注释：

为了求解目标函数\mathcal{J}_{LS}(x) 的极小值， 我们令其梯度为零：

令梯度为零：

由于H^{\top} H 是不可逆矩阵， 上述方程H^{\top} H \mathbf{x} = H^{\top} \mathbf{y} 有无穷多个解。这意味着目标函数\mathcal{J}_{LS}(\mathbf{x}) 不具有唯一的极小值。

极小值集：

设\mathbf{x}_p 是方程H^{\top} H \mathbf{x} = H^{\top} \mathbf{y} 的一个特解， 则其解的全体形式为：

即极小值集为：

其中\text{Null}(H^{\top} H) 是矩阵H^{\top} H 的零空间， 使得H^{\top} H \mathbf{z} = 0 。

— 带惩罚的最小二乘估计方法 I —

我们现在将通过使用正则化的最小二乘方法来估计x 。我们通过引入x 的二次范数（平方欧几里得范数）上的惩罚项来修改之前定义的准则：

从而得到以下带惩罚的最小二乘准则：

并将带惩罚的最小二乘估计量定义为该准则的极小化：

正则化参数\mu_0 （正值）允许我们调整该准则。

4. 讨论\mathcal{J}^{0}_{\text{PLS}} 的选择及\mu_0 的作用：

引入惩罚项R_0(x) 是为了对问题进行正则化， 原始的最小二乘问题可能没有唯一解（因为H^T H 是不可逆的）， 通过引入惩罚项， 问题被转换为一个具有唯一解的优化问题， 这是因为惩罚项确保了\mathcal{J}_{\text{PLS}}^0(x) 是严格凸的。

\mu_0 是正则化参数， 用于控制惩罚项R_0(x) 的权重:

• 当\mu_0 = 0 时：目标函数\mathcal{J}_{\text{PLS}}^0(x) 简化为最小二乘准则\mathcal{J}_{\text{LS}}(x) ， 没有任何正则化。在这种情况下， 可能没有唯一解

• 当\mu_0 \to \infty 时：当\mu_0 变得非常大时， 惩罚项R_0(x) 是主导。这意味着解将趋于\mathbf{x} \to 0

需要权衡取值。

5. 计算\hat{x}_0 。通过分离奇数分量和偶数分量给出其显式表达， 并分析\mu_0 = 0 和\mu_0 \to \infty 的情况。

带惩罚的最小二乘准则为：

梯度为：

解得：

我们下面专注于分离奇数分量和偶数分量， 并给出其显式表达

我们回忆H 是M \times N 矩阵且N=2M ， 作用是从x 的偶数索引处抽取分量至y ， 即

由于H^\top H 是对角的， 对应偶数位置（从第0行列开始的）的对角元为1 ， 奇数位置的对角元为0 ， 则

其逆矩阵是

我们再继续看H^\top y 的结构， 我们之前已经得出:

• 是一个N \times 1 的向量（N=2M ）， 其偶数索引为y_m ， 奇数索引为0

将以上结果合并， 可得

1. 对偶数索引2m ：

   \hat{x}_{2m} = \frac{y_m}{\,1 + \mu_0\,}, \quad m=0,1,\dots,M-1

2. 对奇数索引2m+1 ：

   \hat{x}_{2m+1} = 0, \quad m=0,1,\dots,M-1

• 当\mu_0 = 0 时：

  \hat{x}_{2m}=\tfrac{y_m}{\,1+\mu_0\,} 在\mu_0 \to 0 的极限下， 可得到

  \lim_{\mu_0\to 0}\hat{x}_{2m}(\mu_0) = y_m, \quad \lim_{\mu_0\to 0}\hat{x}_{2m+1}(\mu_0) = 0

  等同于无惩罚的情况。

• 当\mu_0 \to \infty 时：

  \frac{1}{\,1+\mu_0\,} \;\to\; 0, \quad \frac{1}{\,\mu_0\,} \;\to\; 0.

  因此\hat{x}_{2m},\,\hat{x}_{2m+1}\to 0 ， 即所有分量均被强行收敛到零向量， 解趋于0

6. 计算\hat{x}_0 的各分量的偏差和方差， 同样分离奇数分量和偶数分量。对所获得结果的特殊性进行评论。再次分析关于两个特定情况的结果：\mu_0 = 0 和\mu_0 \rightarrow \infty 。

估计量偏差：

对于带有正则化项的最小二乘估计量\hat{x}_0 = (H^{\top} H + \mu_0 I)^{-1} H^{\top} y ， 我们需要分析其偏差和方差：

已知\mathbb{E}[y] = Hx ， 因此：

偏差定义为估计量的期望值与真实值之间的差异：

非零偏差表明引入正则化导致了偏差的出现。

估计量方差：

方差的定义为：

由\hat{x}_0 的表达式可得：

代入后得到：

由于e 是零均值独立随机变量， 且\mathbb{E}[ee^{\top}] = r_e I ， 因此：

进一步化简得：

此方差表明， 正则化参数\mu_0 和测量矩阵H 的特性决定了估计量的方差。

当\mu_0 = 0 时：

此时为无正则化问题， 回到原始的最小二乘问题：

方差为：

当\mu_0 \to \infty 时：

此时估计量收敛于零向量， 偏差最大且方差最小：

— 带惩罚的最小二乘估计方法 II —

现在我们将基于不同的惩罚项来查看结果。此新项的基本构成是x 的连续样本之间的差异：

7. 写出矩阵D ， 列出其一些性质和特点， 并计算D^{\top} D 。

矩阵D 是一个差分矩阵， 用于计算向量中相邻元素之间的差异。对于N=4 的情况：

矩阵D 的性质和特点：

• D 是一个尺寸为(N-1) \times N 的矩阵。

• D 的每一行计算向量x 相邻元素之间的差异。

• D 的秩为N-1 。

• D 是一个稀疏矩阵， 绝大多数元素为零。

计算D^{\top} D ：

矩阵D^{\top} D 的性质：

• D^{\top} D 是一个对称矩阵。

• D^{\top} D 是一个对角占优矩阵， 且对角线上的元素大于等于非对角线元素的绝对值。

• D^{\top} D 是正半定的， 因此可以用于构造凸优化问题。

我们得到新的带惩罚的最小二乘准则：

新的估计定义为：

8. 针对\mathcal{J}^{1}_{\text{PLS}} 的选择和估计量\hat{x}_1 提供适当的注释。\mu_1 的目的是什么？

引入惩罚项\mathcal{R}_1(x) 的目的是对相邻样本间的差异进行约束。其作用如下：

• 当\mu_1 = 0 时， 回到标准最小二乘问题\mathcal{J}_{\text{LS}}(x) ， 估计量\hat{x}_1 没有任何平滑约束。

• 当\mu_1 > 0 时， 目标函数\mathcal{J}^{1}_{\text{PLS}}(x) 包含平滑正则化项， 限制了x 的相邻分量间差异， 趋向于得到更加平滑的解。

• 当\mu_1 \to \infty 时， 惩罚项完全占主导地位， 此时所有分量趋于相等， 即x_1 = x_2 = \cdots = x_N

这种正则化方法特别适合处理可能存在高频噪声的数据， 因为惩罚项可以压制高频变化， 得到更加平滑的估计。

9. 计算\hat{x}_1 ：

根据带惩罚的最小二乘准则\mathcal{J}^{1}_{\text{PLS}} ， 梯度为：

化简后得到：

因此估计量为：

10. 分析当\mu_1 \to 0 和\mu_1 \to +\infty 时估计量\hat{x}_1 的情况， 并评论这两种情况下的具体形式：

• 当\mu_1 \to 0 时， 正则项的影响消失：

此时， 估计量退化为标准最小二乘解。如果矩阵H^{\top} H 是奇异的， 则解可能不存在唯一性。

• 当\mu_1 \to +\infty 时， 正则项占主导地位， 优先最小化相邻样本之间的差异：

在这种情况下， 估计量趋向于一个平滑解， 所有分量趋于相同。

11. 计算\hat{x}_1 的偏差和协方差矩阵， 并针对所得结果提供适当的评论：

期望为：

已知\mathbb{E}[y] = Hx ， 因此：

偏差为：

协方差矩阵定义为：

代入\hat{x}_1 = (H^{\top} H + \mu_1 D^{\top} D)^{-1} H^{\top} y ， 其中y = Hx + e ， 我们有：

此协方差矩阵表明， 正则化参数\mu_1 的大小直接影响估计量的方差。

12. 针对不同的正则化参数值， 提供各种解的示例说明：

• 当\mu_1 = 0 时： 无正则化， 解仅由数据驱动， 容易受噪声影响。解可能如下：

  \hat{x}_1 = (H^{\top} H)^{-1} H^{\top} y

• 当\mu_1 取适中的值（如\mu_1 = 10 ）时： 解在拟合数据与平滑之间取得平衡， 解具有适度的平滑特性。

• 当\mu_1 \to +\infty 时： 强正则化的情况下， 解趋于常数向量：

  \hat{x}_1 \to \frac{\text{mean}(H^{\top} y)}{\text{mean}(H^{\top} H)}

这种正则化的意义在于， 通过引入平滑约束， 能有效抑制高频噪声影响， 适用于信号恢复问题。

练习IV —— 傅里叶综合

 详情请看 傅立叶综合

练习 V —— 信号去噪：非线性方法

我们将分析由一个信号x(t) （如电压、 电流、 电磁波等）描述的物理现象。为此， 我们打算获取N 个测量值y_n （其中n=1,\dots,N ）。这些测量值是在等时间间隔采样下获得的， 采样间隔由采样周期T_s 给出。测量值受到（加性方式的）误差影响， 具体如下：

整体而言， 假设所研究的物理现象相对于采样频率来说变化缓慢：x_n 变化缓慢， 而b_n 可以快速变化。但有时信号会出现突然跳变或强度不连续的情况。我们将收集所有N 个x_n ,y_n , 以及b_n 分别放入三个向量中：

我们要解决的问题是：在不知道误差项b 的情况下， 仅根据测量向量y 来估计描述该物理现象的x 。如果需要， 在下文中我们会将测量误差建模为相互独立的、 零均值随机变量的样本， 每个具有相同的方差r_b 。

1a. 将(1) 式在n=1,2,\dots,N 的情况下写成向量形式。由此可见， 该问题可以视为更一般的线性问题y = H x + b 的特例。请给出此时矩阵H 的形式。

向量化后写成

若一定要写成更一般的线性形式y = H\,x + b ， 可见， 对每个分量n 来说，y_n = x_n + b_n ， 即测量y_n 与x_n 是一一对应的， 没有其它线性组合， 因此矩阵H 只能是单位矩阵I_N （大小为N \times N ）

因此：

1b. 对于为什么该去噪问题是不确定的， 请给出恰当的说明。

只知道y ， 却不知道b 。若不给x 加任何先验约束或者额外假设， 那么对任何给定的x ， 都能找到对应的b = y - x 使方程成立。也就是说， 满足y = x + b 的(x,b) 组合其实有无穷多个， 从而估计x 时并不唯一， 所以问题本身是不适定或不确定的。要想得到稳定且唯一的形式， 必须施加一些额外的先验约束或正则化。

最小二乘法 (The Method of Least Squares)

作为本问题的第一种解法， 我们将使用最小二乘法。它由下述准则定义：

最小二乘估计量定义为使该准则最小的解：

2. 求出最小二乘估计量\hat{x} 的表达式， 并就此作出恰当评论。

给定最小二乘准则

要找

对Q_{\mathrm{LS}}(x) 关于x 做梯度（或导数）求零点：

令其等于零可得

结论： 最小二乘解

这意味着在没有任何其它约束时， 最优做法就是直接取测量值本身。但这样无法去噪， 要加入正则化来获得平滑解或减少噪声影响。

二次惩罚 (Quadratic penalisation)

作为第二种解法， 我们将通过带惩罚项的最小二乘来估计x 。我们在相邻样本之间的二次范数（欧几里得范数）上引入惩罚项：

由此得到下面的带惩罚的最小二乘准则：

其最小化解（即最小化Q_2(x) ）被记为\hat{x}_2 。其中额外的正值参数\mu （即正则化参数）是一个可调参数， 用来控制方法的特性。

3. 针对Q_2 的选取给出合理的说明。额外参数\mu 有何影响？

我们在最小二乘准则的基础上， 加上一个关于相邻样本差分的二次惩罚：

即惩罚过大的相邻差分， 鼓励\{\,x_n\} 序列平滑。于是

其中\mu>0 称为 正则化参数

• \mu 越小：平滑惩罚权重低， 更关注“拟合y 的好坏”；当\mu \to 0 时就退化为普通最小二乘。

• \mu 越大：平滑惩罚权重越高， 更强调“相邻点差分应尽量小”， 让\{\,x_n\} 更平滑。

4. 求出\hat{x}_2 ， 并就实际计算该解的若干算法作出说明。

其中差分算子D 是一个(N-1)\times N 的矩阵， 例如

则

故

对Q_2(x) 做一阶导数(梯度)：

设其为零向量得

或写作

因此

我们可以将差分矩阵近似为循环差分矩阵， 再利用 FFT 进行求解。

5. 特殊情况：当\mu \sim 0 以及\mu \sim \infty 时会发生什么？

• \mu \to 0

  此时Q_2(x) \approx \sum (x_n-y_n)^2 ， 退化为普通最小二乘， 故最优解\hat{x}_2 \to y 。

• \mu \to \infty

  惩罚项占主导， 把相邻差分x_{n+1}-x_n 尽量压到 0。对二次惩罚来说， 这往往得到常数序列解：

  x_1 = x_2 = \cdots = x_N

  同时为了使\sum (x_n-y_n)^2 也尽量小， 往往取

  x_1 = x_2 = \cdots = x_N = \frac{1}{N}\sum_{n=1}^N y_n

  即测量值的平均。

非二次惩罚 (Non-Quadratic penalisation)

为了更好地保留信号x 中可能存在的跳变， 我们将通过三种不同的惩罚函数来引入惩罚项。具体定义如下：

• \varphi_1(\delta) = |\delta|

• \varphi_{2/1}(\delta) = \begin{cases} \delta^2, & \text{若 }|\delta|\le s\\ 2\,s\,|\delta| - s^2, & \text{若 }|\delta| > s \end{cases}

• \varphi_{2/0}(\delta) = \begin{cases} \delta^2, & \text{若 }|\delta|\le s\\ s^2 & \text{若 }|\delta| > s \end{cases}

  其中\varphi_1 是 1-范数惩罚，\varphi_2 是 2-范数惩罚，\varphi_{2/1} 与\varphi_{2/0} 分别是“分段二次/一次(Huber型)”与“分段二次/常数(阈值饱和)”的混合。并且为了方便记号， 我们设\varphi_2(\delta) = \delta^2

6a. 作出上述四种惩罚函数的图示， 确定它们的一阶和二阶导数并画出， 找出不连续点和/或不可导点（分别是一阶和二阶）

1. \varphi_1(\delta) = |\delta|

   一阶导数：

   \varphi_1'(\delta) = \begin{cases} +1, & \delta>0\\ -1, & \delta<0\\ \text{不可导}, & \delta=0 \end{cases}

   二阶导数：对\delta\neq 0 都为 0， 而在\delta=0 无定义

   不可导点：\delta=0 。

2. \varphi_2(\delta) = \delta^2

   一阶导数：\varphi_2'(\delta) = 2\,\delta

   二阶导数：\varphi_2''(\delta) = 2 (处处常数， 无不可导点)

   平滑：无任何不连续， 二阶可微。

3. \varphi_{2/1}(\delta) （分段二次-线性；Huber型）

   \varphi_{2/1}(\delta) = \begin{cases} \delta^2, & \text{若 }|\delta|\le s\\ 2\,s\,|\delta| - s^2, & \text{若 }|\delta| > s \end{cases}

   当|\delta|\le s ，\varphi_{2/1}(\delta)=\delta^2 ；当|\delta|>s ，\varphi_{2/1}(\delta)=2\,s\,|\delta| - s^2

   图像：s 内是抛物线，s 外是线性

   一阶导数：

   \varphi_{2/1}'(\delta) = \begin{cases} 2\,\delta, & |\delta|<s\\ 2\,s\,\mathrm{sign}(\delta), & |\delta|>s \end{cases}

   并在\delta=\pm s 连续(两边极限都等于\pm 2s )。

   二阶导数：

   \varphi_{2/1}''(\delta) = \begin{cases} 2 & |\delta|<s\\ 0 & |\delta|>s \end{cases}

   • 在\delta=\pm s 有不连续(从 2 跳到 0)。

   不可导点：无

    

4. \varphi_{2/0}(\delta) （分段二次-常数）

   \varphi_{2/0}(\delta) = \begin{cases} \delta^2, & \text{若 }|\delta|\le s\\ s^2 & \text{若 }|\delta| > s \end{cases}

   图像：门限内是抛物线， 门限外是常数s^2

   一阶导数：

   \varphi_{2/0}'(\delta) = \begin{cases} 2\,\delta, & |\delta|<s,\\ 0, & |\delta|>s, \end{cases}

   并在\delta=\pm s 处不连续(左极限为\pm2s ， 右极限为 0)。

   二阶导数：

   \varphi_{2/0}''(\delta) = \begin{cases} 2 & |\delta|<s\\ 0 & |\delta|>s \end{cases}

   • 在\delta=\pm s 处不连续跳变。

   不可导点：\delta=\pm s

6b. 对\varphi_{2/1} 和\varphi_{2/0} 而言， 在s \sim \infty 时给出相应的惩罚函数；同时对\varphi_{2/1} 而言， 在s \sim 0 时给出相应的惩罚函数。

• 对\varphi_{2/1} 而言：

  当s\to\infty ， 几乎所有实际\delta 都满足|\delta|\le s ， 故\varphi_{2/1}(\delta)\approx \delta^2 。

  当s\to 0 ， 除了\delta=0 ， 别的点都在|\delta|>0 区， 呈线性(绝对值)特性；定性地说会逼近|\delta| （忽略常数因子）。

• 对\varphi_{2/0} 而言：

  当s\to\infty ， 仍是\varphi_{2/0}(\delta)\approx \delta^2 。

  当s\to 0 ， 除\delta=0 外都进入平顶区， 数值上较为奇特， 不作深入讨论(题目主要关注\varphi_{2/1} 的s\to0 情形)。

6c. 在这四个惩罚函数中， 指出哪些是凸函数、 哪些不是凸函数。对那些凸函数， 进一步说明它们是否是严格凸。

• \varphi_1(\delta)=|\delta| ：凸， 但非严格凸(在\delta>0 和\delta<0 区间都是直线)。

• \varphi_2(\delta)=\delta^2 ：凸且严格凸(二阶导数恒为正)。

• \varphi_{2/1}(\delta) ：分段二次-一次， 也是凸函数(Huber型)， 但不严格凸(在大差分区是线性的)。

• \varphi_{2/0}(\delta) ：分段二次-常数， 也是凸函数， 但同样非严格凸(平顶部分没有曲率)。

练习 VI —— 二次函数的勒让德变换

本练习的目的是练习操控勒让德变换 (Legendre Transform, LT) 的技巧。为此， 我们将处理一个简单的标量二次函数。这是一个重要的方面， 对各种处理方法的实际实现具有重大影响， 例如在信号和图像反卷积中。

设\alpha \in \mathbb{R} ，\beta \in \mathbb{R}^+ 且x \in \mathbb{R} x_0 \in \mathbb{R} 。我们考虑从\mathbb{R} 到\mathbb{R} 的二次函数f ， 其定义为：

1. 首先， 绘制函数f(x) 以及其一阶和二阶导数的图像。然后对\alpha 、\beta 和x_0 的影响进行快速且适当的分析。讨论特殊情况\alpha = 0 、\beta = 1 和x_0 = 0 。

一阶导数：

二阶导数：

由于\beta > 0 ， 因此二阶导数恒为正， 函数f(x) 是一个凸函数。

参数影响分析：

• \alpha 的影响：\alpha 是常数项， 决定了抛物线在纵轴上的偏移。当\alpha 增大时， 函数整体向上平移；当\alpha 减小时， 函数整体向下平移。

• \beta 的影响：\beta 是二次项的系数， 影响抛物线的开口大小和方向。增大\beta 会使抛物线变窄（更陡峭）， 减小\beta 会使抛物线变宽（更平缓）。

• x_0 的影响：x_0 决定了抛物线的顶点在横轴上的位置。改变x_0 会使抛物线沿横轴平移。

特殊情况分析（\alpha = 0 、\beta = 1 、x_0 = 0 ）：

在这个特殊情况下， 函数简化为：

可见是以原点为顶点的标准抛物线， 开口向上。

• 一阶导数：

• 二阶导数：

我们现在回忆f^* 的定义， 即f 的勒让德变换。f^* 本身是一个从\mathbb{R} 到\mathbb{R} 的函数， 其表达式为：

即， 它被定义为一个函数最大化问题的结果。我们将记为g_t(x) = xt - f(x) 。

2a. 求f^* 。同时给出其一阶和二阶导数。

勒让德变换定义为：

由于f(x) 是凸函数， 我们可以通过求导找到极值点。

令g_t’(x) = 0 ， 求得：

将x^* 代入 g_t(x) 计算f^*(t)

因此， 勒让德变换为：

一阶导数：

二阶导数：

2b. 分析\alpha 、\beta 和x_0 的影响。讨论特殊情况\alpha = 0 、\beta = 1 和x_0 = 0 。

参数影响分析：

• \alpha 的影响：

  • 在f^*(t) 中，\alpha 以负号出现， 影响函数的垂直偏移。增大\alpha 会使f^*(t) 向下平移；减小\alpha 会使其向上平移。

• \beta 的影响：

  • \beta 出现在二次项的分母， 影响二次项的曲率。

  • 增大\beta ： 二次项系数\dfrac{1}{2\beta} 减小， 曲线变得更平缓。

  • 减小\beta ： 二次项系数增大， 曲线变得更陡峭。

• x_0 的影响：

  • x_0 出现在线性项x_0 t 中， 影响函数的斜率。改变x_0 会使f^*(t) 的线性部分发生变化， 从而影响整体函数的倾斜程度。

特殊情况分析（\alpha = 0 、\beta = 1 、x_0 = 0 ）：

我们发现二次函数的勒让德变换仍然是一个二次函数

练习 VII —— 勒让德变换

令f 是定义在\mathbb{R} 上、 取值于\mathbb{R} 且严格凸（strictly convex）的一个函数。给定四个实数\alpha \in \mathbb{R} 、\beta \in \mathbb{R} 、\gamma \in \mathbb{R}^+ 和x_0 \in \mathbb{R} 。通过对f 进行以下变换（竖直/水平平移或缩放）， 得到三个新函数：

• u(x) = \alpha + \beta f(x)

• v(x) = f(x - x_0)

• w(x) = f(\gamma x)

回顾勒让德变换（Legendre transform）的定义：对任意t \in \mathbb{R} ， 函数f 的勒让德变换f^*(t) 定义为

1. 求u(x) 、v(x) 和w(x) 的勒让德变换， 分别记为u^*(t) 、v^*(t) 、w^*(t) ， 并将它们表示成f^* 的函数形式。

u^*(t) 的计算

• 记u(x) = \alpha + \beta f(x)

• 根据勒让德变换的定义， 有

将常数-\alpha 提取出来：

接下来考虑

若\beta > 0 ：

令\displaystyle \frac{t}{\beta} 为一个新的自变量， 则有

括号中的\sup 恰是f^*(\tfrac{t}{\beta}) 的定义， 所以

将其代回后得

因此， 对于\beta > 0 ，

（如果\beta < 0 ， 需考虑到凸性的翻转， 但常见文献通常默认\beta > 0 ；这里给出的结论是最常见的形式

v^*(t) 的计算

• 记v(x) = f(x - x_0)

• 根据勒让德变换的定义，

做变量替换：令y = x - x_0 \;\Longrightarrow\; x = y + x_0 。显然x 取遍全实数，y 也取遍全实数。于是

把与y 无关的常数x_0 \, t 提出来：

而\sup_{y \in \mathbb{R}} [\,y \, t - f(y)\,] 就是f^*(t) ， 所以

w^*(t) 的计算

• 记w(x) = f(\gamma x) ， 其中\gamma > 0

• 根据勒让德变换的定义，

再次做变量替换：令y = \gamma x \;\Longrightarrow\; x = \frac{y}{\gamma} 。由于\gamma > 0 ， 当x 取遍全实数时，y 同样取遍全实数。于是

因此

此即

练习 VIII —— 关于绝对值惩罚的勒让德变换

本练习的目标是计算简单标量绝对值函数f(x) = |x| （定义域为实数x \in \mathbb{R} ）的勒让德变换（LT）。

首先， 画出函数f(x) 。它是凸函数吗？是一般意义上的凸函数还是严格凸函数？

该函数在x \ge 0 时是一条斜率为+1 的直线， 在x \le 0 时是斜率为-1 的直线， 且在x = 0 处“折点”相交。 是一个凸函数

凸函数的判定：对任意0 \le \lambda \le 1 以及任意x_1,\,x_2 \in \mathbb{R} ， 有

严格凸是指：对任意x_1 \neq x_2 且0 < \lambda < 1 ， 都有

对任何x_1, x_2 同在正轴或负轴内， 令0<\lambda<1 ， 则

接下来， 我们回顾一下f^* （即f 的勒让德变换）的扩展定义。它被定义为一个从\mathbb{R} 映射到\overline{\mathbb{R}} = \mathbb{R} \cup \{+\infty\} 的函数， 形式如下：

也就是说， 它是一个函数最大化问题的结果。我们令

证明对于t \in [-1, +1] ，f^* 的值为0 ， 若t 不在该区间， 则f^* 的值为+\infty 。

f(x) = |\,x\,| ， 所以

我们要证明：

1. 当t \in [-1, \,1] 时，f^*(t) = 0

2. 当t \notin [-1, \,1] 时，f^*(t) = +\infty

(a) 当|\,t\,| < 1 时， 即当-1< \,t\, < 1 时，\sup [\,x\,t - |\,x\,|\,] 的分析

为方便分析， 将x 分两种情形：x \ge 0 和x < 0 。

1. 若x \ge 0 ： 则|\,x\,| = x 。因此

   g_t(x) \;=\; x\,t \;-\; x \;=\; x\,(\,t - 1\,)

   • 因为t - 1 < 0 （t < 1 ）， 那么当x > 0 越大时，x\,(\,t-1\,) 越趋向-\infty ；

   • 如果x=0 ， 则g_t(0)=0 。

   • 因此， 在-1< \,t\, < 1 ， 且x \ge 0 时， 能取到的最大值为在x=0 处的0 。

2. 若x < 0 ： 则|\,x\,| = -\,x 。因此

   g_t(x) \;=\; x\,t \;-\;(-\,x) \;=\; x\,t \;+\; x \;=\; x\,(\,t + 1\,)

   • 因为t + 1 > 0 （t > -1 ）， 当x < 0 越“负”，x(\,t+1) 也会趋向-\infty ；

   • 如果x = 0 ， 同理就是g_t(0)=0 ；

   • 因此， 当-1< \,t\, < 1 ， 且x < 0 时， 能取到的最大值为在x=0 处的0 。

综合来看， 当-1 < t < 1 时， 对x>0 和x<0 都产生了-\infty 趋向， 只有当x=0 ， 猜得到最大值g_t(0) = 0

由此可知， 当|\,t\,| < 1 时

若进一步把边界t = \pm 1 代入， 也可以检查到结果依然是0 ， 因此把边界也加上。

故当t \in [-1,1] 时，\sup_{x \in \mathbb{R}}\,g_t(x) = 0 ， 即f^*(t)=0

(b) 当|\,t\,| > 1 时，\sup [\,x\,t - |\,x\,|\,] 的分析

这时先讨论t 的取值情况:

1. 若t > 1 ：

   g_t(x) = x \, t - |\,x\,| = \begin{cases} x \, t - x = x\,(\,t-1\,), & x \ge 0,\\[6pt] x \, t + x = x\,(\,t+1\,), & x < 0. \end{cases}

   (1) 若x \ge 0 :

   g_t(x)=x\,(\,t-1\,)

   因为其中(t-1)>0 ， 所以x 越大，x(t-1) 会越趋向+\infty ， 因此该\sup 等于+\infty 。

   (2) 若x < 0 :

   g_t(x)=x\,(\,t+1\,)

   因为其中(t+1)>0 ， 所以x \to -\infty ，x(t+1) 会越趋向-\infty ， 因此该\sup 等于-\infty 。

   我们综合(1)(2)的情况， 勒让德变换中所取的\sup 是面向整个实轴x\in\mathbb{R} 。也就是说， 我们要同时考虑x\ge 0 与x<0 的所有可能取值， 看哪个能让g_t(x) 达到最大。所以趋向于负无穷的情况我们直接就忽视了， 因为只要找到一个能趋向于正无穷的解就够了。即\sup_{x\in\mathbb{R}} g_t(x)\to +\infty

    

2. 若t < -1 ：

   根据上面的经验， 我们只关注能让g_t(x) 越趋向+\infty 即可， 在此处只关注x < 0 情况

   在x < 0 区间

   g_t(x)=x\,(\,t+1\,)

   此时t+1 < 0 ， 而x<0 ， 因此整个是大于0 的，x 越趋于-\infty ， 则g_t(x) 越趋向+\infty 。

   即\sup_{x\in\mathbb{R}} g_t(x) 同样肯定是+\infty 。

    

因此， 一旦t \notin [-1,1] （即|\,t\,|>1 ），\sup_{x\in\mathbb{R}} g_t(x)\to +\infty ， 即f^*(t)=+\infty

练习 IX —— 二次目标函数与线性约束

我们下面着重处理 构造以约束条件为准则的估计器作为最小化器的问题。

关于数值约束优化的研究理论有很多， 包括基于投影梯度法或约束梯度法、 引入障碍函数的方法以及基于拉格朗日乘子法， 我们重点关注拉格朗日乘子法来处理约束优化问题

格朗日乘子法优化步骤

设我们考虑一个关于变量x \in \mathbb{R}^P 的函数F ， 其取值为实数。同时， 假设存在Q 个等式C_q(x) = 0 ， 其中q = 1, \dots, Q 。

我们希望找到x_o ， 即在满足Q 个约束C_q(x) = 0 的情况下， 使F 最小化的x 。也就是说， 这个问题可表示为：

我们引入Q 个参数， 并将它们组成一个向量\ell = [\ell_1, \dots, \ell_Q] ， 称为拉格朗日乘子。然后构造一个扩展函数， 称为拉格朗日函数：

定义如下：

它是关于x 和\ell 的函数。我们令\mathcal{L}(x, \ell) 对x 最小化（对于固定的\ell ）， 并记x_m(\ell) 为最小化的解（它自然是\ell 的函数）：

接着， 将这个x_m(\ell) 代入拉格朗日函数中， 从而定义一个仅依赖于\ell 的函数称其为对偶函数：

为了找到满足约束条件的合适\ell 值， 需要最大化该对偶函数\widetilde{\mathcal{L}} 关于\ell ：

最终， 约束条件下的最优解可以通过将\ell_m 代入关于x 的最优解x_m(\ell) 来获得：

数学描述

设\varphi 是一个函数，\varphi: \mathbb{R}^N \to \mathbb{R} ， 它接受一个向量x \in \mathbb{R}^N 作为输入， 并产生以下标量值：

其中，q_0 是一个标量，q 是一个大小为N 的向量，Q 是大小为N \times N 的方对称矩阵， 且严格正定。

现在考虑一个大小为M \times N 的矩阵A 和一个大小为M 的向量a 。我们关注满足以下约束的x \in \mathbb{R}^N 的集合：

这个关系式表示一个向量约束， 它包含M 个标量约束， 每个约束是x 的N 个分量的线性组合。假设A 是满秩的， 即A 的秩为\min(M, N) 。通常情况下，M < N 。

本练习研究如下优化问题， 即在包含约束Ax - a = 0 的情况下， 对\varphi 进行最小化：

我们接下来通过拉格朗日乘子法得到其解。

我们先思考几个特殊情况。

特殊情况

1a. 如果没有约束

目标函数

无约束\Rightarrow 梯度\nabla \psi(x) = 0

可得：

1b. 如果M = N ，a = 0_N （零向量）， 并且A = I_N （大小为N 的单位矩阵）

约束变为：

1c. 如果M = N 且A 是可逆的

约束方程：

解得：

将\bar{x} 代入目标函数\psi(x) ， 得到：

1d. 如果是二维情况， 即N = 2 （两个变量）和M = 1 （一个约束条件）

约束方程：

整理得到： \alpha x_1 + \beta x_2 = a \quad \text{(直线)}

目标函数：

这是一个 椭圆二次曲线

拉格朗日函数\mathcal{L}(x, \ell) 的表达式

由于从第二问开始我们假设q = 0 ， 所以目标函数变为：

约束条件为:

• 其中: x \in \mathbb{R}^N，N 代表着变量数量， l \in \mathbb{R}^M,M 代表着约束数量

拉格朗日函数为：

已知:

所以， 原式等于

约束条件满足时：

• 关于x ，\mathcal{L}(x, \ell) 是二次函数（因为含有x^T Q x 和\ell^T A x 项）。

• 关于\ell ，\mathcal{L}(x, \ell) 是线性函数（因为\ell 只出现在一次方）。

• 关于(x, \ell) 联合来看，\mathcal{L}(x, \ell) 是二次函数。

求关于x 的\mathcal{L}(x, \ell) 的最小化解x_m(\ell) 。

拉格朗日函数为:

对x 求偏导 (梯度) 并令其为零：

解出x ：

因此，x_m(\ell) 是关于\ell 的线性函数。

将x_m(\ell) 代入拉格朗日函数\mathcal{L}(x, \ell)

构造对偶函数\widetilde{\mathcal{L}}(\ell) = \mathcal{L}(x_m(\ell), \ell) 。

将x_m(\ell) 代入\mathcal{L}(x, \ell) ：

求对偶函数\widetilde{\mathcal{L}}(\ell) 关于\ell 的最大化解\ell_m 。

对\ell 求偏导并令其为零：

解出\ell ：

得到约束条件下的最优解

将\ell_m 代入x_m(\ell) ：

在特殊情况M = N 且A 可逆的情况下，A Q^{-1} A^T 可逆， 且有：

因此：

这与 1c 的结果一致， 即最优解为x_o = A^{-1} a 。

思考问题: 约束下的最小值比无约束时的最小值大还是小？

约束条件限制了可行解的范围， 因此约束下的最小值一般大于或等于无约束时的最小值。我们可以通过计算函数\varphi 的两个值来对比。

无约束时的最小值：

有约束时的最小值：

由于二次型\frac{1}{2} a^T (A Q^{-1} A^T)^{-1} a \geq 0 ， 因此\varphi(x_o) \geq \varphi(x_*) 。

特殊情况M = N 且A 可逆的情况下， 验证最小值等于\varphi(A^{-1} a) 。

由于x_o 满足约束且是最优解， 因此最小值确实为\varphi(A^{-1} a) 。

习题 X —— 二元一维情形的二次目标函数与线性约束

本习题涉及一个有约束的最优化问题。更具体而言， 这是一个具有二维二次目标函数和一维线性约束的情形。

一方面， 令 \varphi 为一个函数\mathbb{R}^2 \to \mathbb{R} ， 它将一对实数(x,y) 作为输入：

另一方面， 所有实数对(x,y) 需要满足以下约束：

• 其中，s \in \mathbb{R} 是斜率 (slope)，o \in \mathbb{R} 是截距 (offset)。

本习题研究在包含约束(C) 的条件下对 \varphi 的最小化， 即以下问题：

重点探讨使用拉格朗日乘子法 (Lagrange multipliers) 及直接方法对该问题的求解。

1. 给出无约束时的极小点 (minimizer) 和无约束时的最小值。

   先不考虑约束， 最小化

   \varphi(x,y) \;=\; 1 \;+\; \frac{x^2 + y^2}{2}

   求偏导

   \frac{\partial \varphi}{\partial x} \;=\; x, \quad \frac{\partial \varphi}{\partial y} \;=\; y

   并令其为 0

   x = 0, \quad y = 0

   • 无约束极小点：(x_0,y_0)=(0,0)

   • 无约束最小值：

     \varphi(0,0) = 1 + \frac{0^2 + 0^2}{2} = 1

   因此， 无约束时最优解是(0,0) ， 最小值=1 。

    

2. 给出该问题以及它的解的图形示意。

   • 目标函数\varphi(x,y)=1 + \tfrac{x^2+y^2}{2} 是一个开口向上的抛物线， 其等值线是一族以原点(0,0) 为圆心的同心圆。

   

   • 约束y = s\,x + o 表示一条直线， 斜率为s 、 截距为o 。

   我们在这条直线上找使\varphi 最小的点， 即找与这条直线最贴近圆的交点（即同心圆从小到大渐增， 首次与该直线相交处即最优点）。

3. 通过在 \varphi 中直接替换约束(C) 来提出直接解法。

   直接将约束代入\varphi

   约束：

   y = s\,x + o

   代入\varphi(x,y) 得

   \varphi\bigl(x,\;s\,x + o\bigr) = 1 + \frac{1}{2} \Bigl[x^2 + (s\,x + o)^2\Bigr]

   展开：

   \varphi(x) = 1 + \frac{1}{2}\Bigl[x^2 + s^2\,x^2 + 2\,s\,o\,x + o^2\Bigr] = 1 + \frac{1}{2}\Bigl[(1 + s^2)\,x^2 + 2\,s\,o\,x + o^2\Bigr]

   对x 求导并令其为 0：

   \frac{d\varphi}{dx} = \frac{1}{2}\Bigl[2\,(1 + s^2)\,x + 2\,s\,o\Bigr] = (1 + s^2)\,x + s\,o

   令其=0 ， 可解得

   (1 + s^2)\,x + s\,o = 0 \quad\Longrightarrow\quad x = -\,\frac{s\,o}{\,1 + s^2\,}

   x 找到了， 再去找y ， 由y = s\,x + o

   y = s \Bigl(-\,\frac{s\,o}{1 + s^2}\Bigr) + o = -\,\frac{s^2\,o}{1 + s^2} + o = \frac{o\,\bigl(1 + s^2\bigr) - s^2\,o}{1 + s^2} = \frac{o}{\,1 + s^2\,}

   有带约束的极小点：

   x_{*} = -\,\frac{s\,o}{\,1 + s^2\,} \quad y_{*} = \frac{o}{\,1 + s^2\,}

   再算目标函数值：

   \varphi(x_{*},y_{*}) = 1 + \frac{x_{*}^2 + y_{*}^2}{2}

   其中

   x_{*}^2 + y_{*}^2 = \frac{s^2\,o^2}{(1 + s^2)^2} + \frac{o^2}{(1 + s^2)^2} = \frac{\,o^2\,(s^2 + 1)\,}{(1 + s^2)^2} = \frac{o^2}{\,1 + s^2\,}

   所以

   \varphi(x_{*},y_{*}) = 1 + \frac{1}{2} \Bigl(\frac{o^2}{\,1 + s^2\,}\Bigr) = 1 + \frac{o^2}{\,2\,(1 + s^2)\,}

    

4. 拉格朗日乘子法：

   4a. 写出拉格朗日函数 \mathcal{L}(x,y,\lambda) 。对于(x,y) 而言， 它是二次函数还是线性函数？对于\lambda 又如何？

   我们的问题是：

   \min_{x,y\in \mathbb{R}}\;\;\varphi(x,y) \quad \text{s.t.} \quad C(x,y) \;=\; y \;-\; s\,x \;-\; o \;=\; 0

   • 目标函数：

     \varphi(x,y) \;=\; 1 \;+\; \frac{x^2 + y^2}{2}

   • 约束函数：

     C(x,y) \;=\; y - s\,x - o \;=\; 0

   引入一个拉格朗日乘子\lambda \in \mathbb{R} ， 构造拉格朗日函数

   \mathcal{L}(x,y,\lambda) \;=\; \varphi(x,y) \;+\; \lambda\,\bigl[\,C(x,y)\bigr] \;=\; \underbrace{\Bigl(1 + \tfrac{x^2 + y^2}{2}\Bigr)}_{\text{关于 $(x,y)$ 为二次项}} \;+\; \underbrace{\lambda \,\bigl(y - s\,x - o\bigr)}_{\text{关于 $\lambda$ 为线性项}}

   • 对(x,y) 而言：\tfrac{x^2 + y^2}{2} 是二次形式，\,\lambda(y - s\,x) 也是关于(x,y) 的线性形式。因此，\mathcal{L}(x,y,\lambda) 在(x,y) 上是一个二次函数。

   • 对\lambda 而言：\,\lambda\,(y - s\,x - o) 在\lambda 上是线性的。因此，\mathcal{L}(x,y,\lambda) 在\lambda 上是线性函数。

    

   4b. 给出 \mathcal{L}(x,y,\lambda) 关于(x,y) 的极小值\bigl(x_{m}(\lambda),\,y_{m}(\lambda)\bigr) 。它是关于\lambda 的二次函数还是线性函数？

   我们令\lambda 固定， 在x,y 上最小化

   \mathcal{L}(x,y,\lambda) = 1 + \frac{x^2 + y^2}{2} \;+\; \lambda\,\bigl(y - s\,x - o\bigr)

对x 、y 分别求偏导并令其等于零， 就得到最优解(x_{m}(\lambda),\,y_{m}(\lambda)) ：

• 关于x 的偏导：

• 关于y 的偏导：

由此可得， 在x,y 的最小化点为

可见， 这个极小值点关于\lambda 是线性的 (即x_{m}(\lambda) 和y_{m}(\lambda) 均是\lambda 的线性函数)， 与之前所述相符。

4c. 构造对偶函数

即， 将得到的极小值点\bigl(x_{m}(\lambda),\,y_{m}(\lambda)\bigr) 代入拉格朗日函数 \mathcal{L}(x,y,\lambda) 。

具体地， 将 x_{m}(\lambda)=\lambda s 与 y_{m}(\lambda)=-\lambda 代入

可得

• 前半部分：

• 后半部分：

二者合并， 得到

将同类项合并， 可写为

这便是我们想要的对偶函数， 从中也能看出它是一个关于\lambda 的开口向下二次函数（系数为-\frac{1+s^2}{2}<0 ）， 因此可找其最大值。

4d. 给出对偶函数 \widetilde{\mathcal{L}}(\lambda) 关于\lambda 的极大值\lambda_{m} 。

现在我们要最大化

对\lambda 求导并令其等于零：

这就是能够使对偶函数\widetilde{\mathcal{L}} 达到最大值的拉格朗日乘子。

4e. 最后， 通过将\lambda_{m} 代入\bigl(x_{m}(\lambda),\,y_{m}(\lambda)\bigr) 的表达式， 推得有约束的极小点\bigl(x_{*},\,y_{*}\bigr) 。

回忆我们在 4b 中得到

现将\lambda_{m} = -\frac{o}{1 + s^2} 代入：

从而得到与我们“直接替换约束法”所得完全相同的最优解：

5. 你认为有约束时的最小值比无约束时更大还是更小？通过计算目标函数 \varphi 的两种取值来检验你的答案。

   • 无约束时： 如前所述， 最优点为(0,0) ， 最小值为

     \varphi(0,0) = 1.

   • 有约束时： 上文算得

     \varphi(x_{*},y_{*}) = 1 \;+\; \frac{1}{2}\Bigl(\frac{o^2}{\,1 + s^2\,}\Bigr) = 1 \;+\; \frac{o^2}{\,2\,(1 + s^2)\,}.

   比较可见：

   • 当o \neq 0 时，\tfrac{o^2}{2\,(1+s^2)} > 0 ， 所以\varphi(x_{*},y_{*}) > 1 ， 有约束时的最小值比无约束时更大。

   • 当o = 0 时，\varphi(x_{*},y_{*}) = 1 ， 与无约束情形的最小值相同。

6. 比较原问题中（带约束的）目标函数 \varphi 的最小值与对偶函数 \widetilde{\mathcal{L}}(\lambda) （无约束时的）最大值。

   • 原问题(Primal)的最小值：

     \varphi(x_{*},\,y_{*}) = 1 + \frac{o^2}{\,2\,(1 + s^2)\,}

   • 对偶函数(Dual)的最大值： 在前面的 4d、 4e 中， 我们找到\lambda_{m} 并可将其代入

     \widetilde{\mathcal{L}}(\lambda) = 1 \;-\; \frac{1 + s^2}{2}\,\lambda^2 \;-\; o\,\lambda

     将\lambda = \lambda_{m} = -\frac{o}{1+s^2} 代入后， 仔细合并同类项， 可得

     \widetilde{\mathcal{L}}(\lambda_{m}) = 1 \;+\; \frac{o^2}{\,2\,(1 + s^2)\,}.

   由此可见， 对偶函数的最大值恰好等于原问题目标函数在约束下的最小值。这也体现了本题中的强对偶性(strong duality)——因为目标函数是严格凸的， 约束又是线性的， 因此不存在对偶间隙(duality gap)。

    

7. 讨论特例o = 0 和s = 0 的情形。

   • o=0 特例：

   x_{*} = -\frac{s\,\cancel{o}}{1 + s^2} = 0, \quad y_{*} = \frac{\cancel{o}}{\,1 + s^2} = 0

   因而最优点是(0,0) ， 最小值等于 1（与无约束最小值相同）

    

   • s=0 特例：

   x_{*} = -\frac{0\cdot o}{\,1+0^2\,} = 0, \quad y_{*} = \frac{o}{\,1+0^2\,} = o

   从而最优点变为(0,o) 。

习题 XI —— 二元一维情形的二次目标函数与线性约束

本习题同样探讨一个有约束的最优化问题。更具体地说， 这是一个具有二维二次目标函数和一维线性约束的情形。

一方面， 令 \varphi 为一个函数 \mathbb{R}^2 \to \mathbb{R} ， 它将一对实数(x,y) 作为输入：

另一方面， 考虑满足以下约束的所有实数对(x,y) ：

• 其中，s \in \mathbb{R} 是斜率

本习题研究在包含约束(C) 的条件下对 \varphi 的最小化， 即以下问题：

并重点探讨使用拉格朗日乘子法 (Lagrange multipliers) 及直接方法对该问题的求解。

给出无约束时的极小点 (minimizer) 和无约束时的最小值。

先不考虑任何约束， 最小化

• 求偏导并令其为 0：

  分别对x 、y 求偏导(梯度)：

  \frac{\partial \varphi}{\partial x} = \tfrac{1}{2}\,\bigl[\,2(x-1)\bigr] = x \;-\; 1, \qquad \frac{\partial \varphi}{\partial y} = \tfrac{1}{2}\,\bigl[\,2\,y\bigr] = y

  令其等于 0， 得到

  x - 1 = 0 \;\;\Longrightarrow\;\; x = 1, \quad y = 0

• 无约束极小点：

  (x,y)=(1,0)

• 无约束最小值：

  \varphi(1,0) = \tfrac{1}{2}\,\Bigl[(\,1 - 1\,)^2 + 0^2\Bigr] = 0

因此， 无约束时最优解是(1,0) ， 对应的目标函数最小值为0 。

给出该问题及其解的图形示意。

• 目标函数

  \varphi(x,y) = \tfrac{1}{2}\,\bigl[(x-1)^2 + y^2\bigr]

  其等值线是一族以(1,0) 为圆心的同心圆

• 约束

  y = s\,x

  是一条经过原点、 斜率为s 的直线。

我们要在这条直线y=s\,x 上， 找与点(1,0) 最近的点——相切/相交的点。

通过在 \varphi 中直接替换约束(C) 来提出直接解法。

直接将约束y=s\,x 代入\varphi(x,y) ， 再对x 做无约束最小化。

代入

对x 求导并令其为 0：

因此

有约束极小点：

目标函数值：

先计算(x_{*}-1)^2 + y_{*}^2 ：

因而

拉格朗日乘子法：

4a. 写出拉格朗日函数 \mathcal{L}(x,y,\lambda) 。对(x,y) 而言， 它是二次函数还是线性函数？对于\lambda 又如何？

带约束：

引入乘子\lambda \in \mathbb{R} ， 拉格朗日函数记作

• 对于(x,y) 而言， \mathcal{L}(x,y,\lambda) 是二次函数

• 对\lambda 而言， \mathcal{L}(x,y,\lambda) 是线性函数

4b. 给出 \mathcal{L}(x,y,\lambda) 关于(x,y) 的极小值\bigl(x_{m}(\lambda),\,y_{m}(\lambda)\bigr) 。它是关于\lambda 的二次函数还是线性函数？

令\lambda 固定， 在x,y 上最小化\mathcal{L}(x,y,\lambda)

对x 、y 分别求偏导并设为 0：

可见(x,y) 都是关于\lambda 的线性函数：

4c. 构造对偶函数

即将\bigl(x_{m}(\lambda),\,y_{m}(\lambda)\bigr) 代入拉格朗日函数 \mathcal{L}(x,y,\lambda)

化简：

4d. 给出对偶函数 \widetilde{\mathcal{L}}(\lambda) 关于\lambda 的极大值\lambda_{m} 。

要最大化

对\lambda 求导并令 0：

因此

4e. 最后， 通过将\lambda_{m} 代入\bigl(x_{m}(\lambda),\,y_{m}(\lambda)\bigr) 的表达式， 推得有约束的极小点\bigl(x_{*},\,y_{*}\bigr)

前面我们得到过:

代入\lambda_{m}=-\,\tfrac{s}{1+s^2} ：

可见， 我们又一次得到完全相同的点

这说明拉格朗日乘子法与直接代入法所得结果一致。

5. 有约束时的最小值比无约束时更大还是更小？通过计算 \varphi 在两种情形下的值来检验你的答案。

• 无约束时： 最小值为

  \varphi(1,0) = 0

• 有约束时： 最小值为

  \varphi(x_{*},y_{*}) = \tfrac{1}{2}\,\frac{s^2}{\,1+s^2\,}

注意到对于任意有限s ， 都有

从而

因此对于s \neq 0 ， 约束最优值是严格大于 0 的， 而无约束最小值是 0；只有在s=0 这条“水平线”情况下， 与无约束最优解(1,0) 重合， 才也等于 0。

所以一般结论：有约束最小值\ge 无约束最小值， 符合直觉——增加一个约束后， 解的范围就变小了。

6. 比较原问题中（带约束的）目标函数 \varphi 的最小值与对偶函数 \widetilde{\mathcal{L}}(\lambda) （无约束时的）最大值。

如同以往的“二次目标函数 + 线性约束”情形， 这里也存在强对偶性(strong duality)。可以计算对偶函数

在\lambda=\lambda_{m}=-\tfrac{s}{1+s^2} 处取到最大值， 与原问题最小值完全相同， 即

这印证了本题不存在对偶间隙(duality gap)， 也再次说明拉格朗日乘子法的可行性。

7. 讨论特例s = 1 和s = 0 ， 以及s = +\infty 的情形。

• s=0 特例：

  约束y=0 是x 轴， 离(1,0) 最近的点恰是(1,0) 本身（它就躺在x 轴上）， 故最优值 0 与无约束时相同。通过计算也会得到相同结果。

• s=1 特例：

  约束y=x 表示一条45^\circ 直线。则

  x_{*} = \frac{1}{1+1^2} = \tfrac{1}{2}, \quad y_{*} = \tfrac{1}{2}
  \varphi\bigl(\tfrac{1}{2},\tfrac{1}{2}\bigr) = \tfrac{1}{2}\, \Bigl[ \bigl(\tfrac{1}{2}-1\bigr)^2 + \bigl(\tfrac{1}{2}\bigr)^2 \Bigr] = \tfrac{1}{2}\, \bigl[ \bigl(-\tfrac{1}{2}\bigr)^2 + \tfrac{1}{4} \bigr] = \tfrac{1}{2}\, \bigl[ \tfrac{1}{4} + \tfrac{1}{4} \bigr] = \tfrac{1}{4}

   

• s=+\infty 特例：

  从几何视角，y = s\,x 当s \to +\infty 对应“竖直线”x=0 。

  此时离(1,0) 最近的点是(0,0) ， 目标函数值

  \varphi(0,0) = \tfrac{1}{2}\,\bigl[(0-1)^2 + 0^2\bigr] = \tfrac{1}{2}

2023年考题

Exercice I — Signal Denoising（信号去噪）

回顾：梯度（gradient）和 Hessian 矩阵

设M 是一个大小为N \times N 的方阵且对称， m 是一个大小为N 的列向量。给定一个向量u \in \mathbb{R}^N，在\mathbb{R}^N 上定义了取值于\mathbb{R} 的函数\psi 和\phi，它们满足：

这两个函数都是二次可微的。它们各自的梯度如下所示：

它们各自的 Hessian 矩阵（大小为N \times N）分别为：

矩阵的一阶泰勒展开（Matrix first order Taylor expansion）

设A 是一个大小为N \times N 的方阵， I_N 表示大小为N 的单位矩阵，则有如下近似成立：

这可以被视为对经典标量情形的推广。

我们将分析由某个物理现象所描述的信号x(t)，例如电压、电流、电磁波等等。为此，我们将对该信号进行N 次测量，得到观测值y_n（ n=1,\dots,N）。这些测量在固定采样周期T 的等间隔采样时刻进行，并受到（加性）误差的影响，模型为：

其中， x_n 随采样频率缓慢变化，而e_n 可能快速变化。若有需要，在后续分析中，我们可将测量误差e_n 建模为具有相同方差\sigma^2、相互独立且同分布（i.i.d.）的随机变量。将所有观测值y_n 组成向量

同理可得

我们希望从y 中估计表征该物理现象的x，在此过程中，测量向量y 被直接使用，而并未显式地对误差项e 建模。

1. 请将式 (1) 在n=1,2,\ldots,N 的情形下写成向量形式。由此可见，我们要解决的问题可视为更一般的线性问题

在本题情形下，矩阵H 是什么？

将式(1) 在n = 1, 2, \ldots, N 的情形下写成向量形式：

其中，

由此可见，一般的线性模型形式为：

H 是一个N \times N 的单位矩阵。因此，

其中I_N 表示大小为N 的单位矩阵。

最小二乘法（The Method of Least Squares）

在第一步中，我们将用最小二乘（Least Squares, LS）方法来处理该问题。由此可得以下最小二乘准则：

2. 提供 \mathbf{x}_{\mathrm{LS}}（最小二乘估计）的表达式，即使得最小二乘准则最小化的 \mathbf{x}值。并给出适当的说明。

最小二乘准则定义为：

为了找到使J_{\mathrm{LS}}(x) 最小化的\mathbf{x}，我们对J_{\mathrm{LS}}(x) 关于x 求导并令其等于零：

解得：

最小二乘估计\mathbf{x}_{\mathrm{LS}} 直接等于观测向量y。这意味着最小二乘法的最优解\mathbf{x}_{\mathrm{LS}} 是直接取观测向量y，即简单的将观测值作为信号的最佳估计，但是这里有一个过拟合的问题，即过度拟合噪声，将其当作真实信号的一部分，因此单纯的最小二乘法无法实现重建要求

 The least squares estimatex_{LS} is directly equal to the observation vectory. This implies that the optimal solution in least squares,x_{LS}, simply takes the observed values as the best estimate of the signal. However, there has an overfitting issue here — treating noise as part of the true signal — so simple least squares method cannot meet the reconstruction requirements.

3. 求估计量 \mathbf{x}_{\mathrm{LS}}的偏差（bias）是什么？它的协方差矩阵又是什么？对每个分量 x_n的估计方差是多少？它对应的均方误差（MSE）又是多少？

 偏差（Bias）：

偏差定义为估计量的期望值与真实值之差：

由于\mathbf{x}_{\mathrm{LS}} = y = x + e，且假设测量误差e 满足\mathbb{E}[e] = 0，因此：

协方差矩阵（Covariance Matrix）：

协方差矩阵定义为：

由于\mathbf{x}_{\mathrm{LS}} = y = x + e 且\mathbb{E}[e] = 0， \mathbb{E}[\mathbf{x}_{\mathrm{LS}}] = x

误差e_n 具有相同的方差\sigma^2 且相互独立，则协方差矩阵为：

每个分量x_n 的估计方差（Variance）：

每个分量的方差就是协方差的对角元素。因此，对于每个n = 1, 2, \ldots, N：

均方误差（Mean Squared Error, MSE）：

均方误差定义为偏差的平方加上方差：

由于偏差为零：

换句话说，对于无偏估计，其 MSE 就等于方差

The Method of Penalised Least Squares I （加惩罚项的最小二乘法 I）

现在我们将注意力转向使用带有惩罚项的最小二乘法来估计 \mathbf{x}。在之前定义的准则基础上，我们额外添加一项惩罚项，用以惩罚 \mathbf{x}的平方欧几里得范数：

于是便得到如下的准则：

并将该准则最小化所对应的解定义为带惩罚项的最小二乘估计：

这里额外出现的参数 \mu被称作正则化参数（regularisation parameter），用于调节该方法。

4. 就 J_{\mathrm{nls}}的选取给出适当的说明。 \mu的作用是什么？

选取J_{\mathrm{nls}} 的原因：

最小二乘法（Least Squares, LS）虽然能够提供对信号\mathbf{x} 的估计，但是当系统中存在噪声时，最小二乘法可能会有过拟合问题，即把无用的噪声也当作真实信号，为了解决这一问题，我们引入惩罚项（Regularization Term）

Although the least squares method can provide an estimate of the signal x, but when there has noise in the system, the least square method may have overfitting issues -- treating useless noise as part of the real signals. To solve this problem, we introduce a regularization term.

因此我们在最小二乘准则J_{\mathrm{ls}}(\mathbf{x}) 的基础上，添加一个惩罚项R(\mathbf{x})，选择平方欧几里得范数作为惩罚项：

Therefore, on the basis of the least squares criterion, we add a penalty term R(x), and choose the squared Euclidean norm as the regularization term:

因此，带惩罚项的最小二乘准则为：

为什么选择欧几里得范数 作为惩罚项呢？

why we choose Euclidean norm as the penalty norm?

• 第一，他是一个严格convex的函数，保证了整个目标函数也是convex的，可以确保有解析解

It's a strictly convex function, ensuring that the entire objective function is also convex, thus guaranteeing an analytical solution.

• 第二，在拟合数据的同时，这个惩罚项会趋向于让x 变小，提高稳定性

While fitting the data, this penalty term tends to shrink x , improving stability.

• 第三，从贝叶斯角度分析，它相当于一个先验高斯分布。

Fome a Bayesian perspective, it is equivalent to imposing a Gaussian prior distribution on x.

参数\mu 的作用：

参数\mu 被称为正则化参数（Regularisation Parameter），平衡最小二乘项与惩罚项之间的权重：

Parameter \mu is regulatisation paramater, balances the weight between the least squares term and the penalty term

• 当\mu 增大时，惩罚项的权重增加，\mathbf{x} 将更小，有助于抑制噪声对估计的影响，防止过拟合。

when \mu increases, the weight of the penalty term grows, making x smaller, this helps suppress the influence of noise on the estimation and prevent overfitting.

• 当\mu 减小时，最小二乘项的权重相对增加，估计信号\mathbf{x} 将更贴近观测数据y，但有可能导致过拟合。

When \mu decreases, the weight of the least square term relatively increases, making the estimated signal x closer to the observed data, however, this may lead to overfitting.

因此， \mu 的选择需要平衡最小二乘项与惩罚项。

Therefore, the choice of \mu must balance the least suqares term and the penalty term. 

5. 求出 \mathbf{x}_{\mathrm{pls}}的显式表达式。

带惩罚项的最小二乘估计\mathbf{x}_{\mathrm{pls}} 定义为：

为了求解\mathbf{x}_{\mathrm{pls}}，我们可以对J_{\mathrm{nls}}(\mathbf{x}) 关于\mathbf{x} 求导并令其等于零：

将上述方程整理得到：

因此，带惩罚项的最小二乘估计的显式表达式为：

说明：

带惩罚项的最小二乘估计\mathbf{x}_{\mathrm{pls}} 通过缩放观测向量\mathbf{y} 来获得最优估计值。缩放因子\frac{1}{1 + \mu} 控制了估计信号的幅度，避免了过度拟合问题。

The penalized Least square estimate x_{pls} obtain the optimal estimate by scaling the observation vector y. The scaling factor \frac{1}{1 + \mu}controls the amplitude of the estimated signal, thereby avoiding overfitting.

6. 计算它的偏差和协方差矩阵，并给出相应的说明。

偏差（Bias）：

偏差定义为估计量的期望值与真实值之差：

由于\mathbf{x}_{\mathrm{pls}} = \frac{1}{1 + \mu} \mathbf{y} = \frac{1}{1 + \mu} (\mathbf{x} + \mathbf{e})，且测量误差\mathbf{e} 满足\mathbb{E}[\mathbf{e}] = 0，因此：

因此，偏差为：

协方差矩阵（Covariance Matrix）：

协方差矩阵定义为：

由于：

且\mathbb{E}[\mathbf{e}] = 0，协方差矩阵为：

假设误差\mathbf{e} 的协方差矩阵为\sigma^2 I_N，则：

综上所述，带惩罚项的最小二乘估计\mathbf{x}_{\mathrm{pls}} 相较于真实信号\mathbf{x} 存在系统性偏差，这种偏差与正则化参数\mu 成正比。如果\mu =0 则回到 LS 情况。 随着\mu 的增大，协方差矩阵的值减小，这意味着估计的方差降低，估计结果更加稳健，但会增加偏差。因此正则化参数\mu 的选择非常重要

In summary, the penalized least squares estimate x_{pls}have a systematic bias relative to the true signal x, and this bias is proportional to the regularization parameter μ.

If μ=0, we return to the LS case. As μ increases, the value of the covariance matrix deceases - meaning the estimate's variance is reduced, and the resultat of the estimation becomes more robust, but the bias grows. Therefore, the choice of the regularization parameter μ is very important.

下面是额外补充，题目未要求

每个分量x_n 的估计方差（Variance）：

协方差矩阵的对角元素表示各个分量的方差。因此，对于每个n = 1, 2, \ldots, N：

均方误差（Mean Squared Error, MSE）：

均方误差定义为偏差的平方加上方差：

由偏差和方差的计算结果：

因此：

7. 当 \mu=0 以及当 \mu \to \infty时，会发生什么情况？

当\mu = 0 时，带惩罚项的最小二乘准则退化为普通的最小二乘准则：

When\mu = 0 ，the penalized least square criterion degenerates into the standard least squares criterion:

此时，带惩罚项的最小二乘估计\mathbf{x}_{\mathrm{pls}} 为：

当\mu \to \infty 时，惩罚项的权重远大于最小二乘项：

为了最小化J_{\mathrm{nls}}(\mathbf{x})，必须使得\|\mathbf{x}\|^2 尽可能小。因此：

在极端的正则化下，估计信号被完全抑制

When \mu \to \infty, the weight of the penalized term is much greater than that of the least suqares term, to minimize the J_{\mathrm{nls}}(\mathbf{x}), \|\mathbf{x}\|^2 must be made as small as possible. Consequently, under extreme regularization, the estimated signal is completely suppressed.

The Method of Penalised Least Squares II （加惩罚项的最小二乘法 II）

我们仍然使用带惩罚项的最小二乘法，但这一次我们更换了正则化项。新的正则化项基于信号 \mathbf{x}各相邻采样点之差构造而成：

据此，我们得到新的带惩罚项最小二乘准则：

并将其最小化所对应的解定义为新准则下的带惩罚项最小二乘估计：

8. 写出矩阵 \mathbf{D}的形式。指出它的一些性质和特点。

矩阵\mathbf{D} 的形式：

在新的正则化项中， \mathbf{D} 是一个用于计算信号\mathbf{x} 各相邻采样点之差的差分矩阵。对于长度为N 的向量\mathbf{x}，矩阵\mathbf{D} 的形式为(N-1) \times N 的矩阵，其定义如下：

D is a différence matrix used to compute the differences between the adjacent sampling points of the signal.

具体而言， \mathbf{D} 的每一行对应于\mathbf{x} 的两个相邻元素之差。例如，第一行对应x_2 - x_1，第二行对应x_3 - x_2，以此类推。

如果题目说了是一个循环差分矩阵的话，即x_{N-1}=x_1 ，那么 \mathbf{D} 变成:

If it is a cyclic difference matrix, then D becomes:

\mathbf{D} 的性质和特点：

• 矩阵\mathbf{D} 尺寸(N-1) \times N ，其秩为N-1。

• \mathbf{D}^T \mathbf{D} 是一个半正定、对称的矩阵

• 矩阵\mathbf{D} 实现了对信号\mathbf{x} 的一阶差分操作，即计算相邻采样点之间的差距

• 矩阵\mathbf{D} 是一个稀疏矩阵

 Properties and characteristics of D:

• D has dimensions (N-1) \times N, and its rank is n-1

• D is a positive semidefinite, symmetric matrix.

• It implements a first-order difference operation on the signal x, i.e., it computes the differences between the adjacent sampling points of the signal.

• is a sparse matrix.

9. 就该新的 J_{\mathrm{nls}}'的选取给出适当的说明。再次说明 \mu 的作用是什么？

新的带惩罚项的最小二乘准则：

选用该惩罚项的主要目的是为了平滑信号，通过惩罚相邻采样点之间的差异，鼓励\mathbf{x} 在相邻点之间缓慢变化，抑制噪声，避免过拟合问题。

The purpose of choosing this penalty term is to smooth the signal, by penalizing the difference between adjacent sampling points, it encourages x to vary slowly between neighboring points, thereby suppressing noise and avoiding overfitting

参数\mu 的作用：

参数\mu 被称为正则化参数（Regularisation Parameter），平衡最小二乘项与惩罚项之间的权重：

• 当\mu 增大时，惩罚项的权重增加，\mathbf{x} 更加平滑，有助于抑制噪声对估计的影响，防止过拟合。但是要注意防止过度平滑。

• 当\mu 减小时，最小二乘项的权重相对增加，估计信号\mathbf{x} 将更贴近观测数据y，但有可能导致过拟合。

因此， \mu 的选择需要平衡最小二乘项与惩罚项。

The role of parameter \mu:

is called the regularization parameter, to balance the weight between the least squares terms and the penalty term:

When \mu increase, the weight of the penalty term increase, making x more smoother. This helps suppress the influence of the noise on the estimation and prevents overfitting -- though one must be cautious about over-smoothing

When \mu decreases, the weight of the least squares term relatively increases, making x closer to the observed data y. However, this may lead to overfitting.

Therefore, the choice of the \mu must balance the least squares term and the penalty term.

10. 计算 \mathbf{x}_{\mathrm{pls}}'。

带惩罚项的最小二乘估计\mathbf{x}_{\mathrm{pls}}' 的定义：

求解过程：

为了找到使J_{\mathrm{nls}}'(\mathbf{x}) 最小化的\mathbf{x}，我们对其关于\mathbf{x} 求导并令导数等于零。

1. 展开目标函数：

   J_{\mathrm{nls}}'(\mathbf{x}) = (\mathbf{y} - \mathbf{x})^T (\mathbf{y} - \mathbf{x}) + \mu \mathbf{x}^T \mathbf{D}^T \mathbf{D} \mathbf{x}

2. 对\mathbf{x} 求梯度：

   \nabla_{\mathbf{x}} J_{\mathrm{nls}}'(\mathbf{x}) = -2 (\mathbf{y} - \mathbf{x}) + 2 \mu \mathbf{D}^T \mathbf{D} \mathbf{x}

3. 设梯度为零：

   -2 (\mathbf{y} - \mathbf{x}) + 2 \mu \mathbf{D}^T \mathbf{D} \mathbf{x} = 0

   简化后：

   \mathbf{y} - \mathbf{x} = \mu \mathbf{D}^T \mathbf{D} \mathbf{x}

   即：

   (\mathbf{I}_N + \mu \mathbf{D}^T \mathbf{D}) \mathbf{x} = \mathbf{y}

4. 解得\mathbf{x}：

   \hat{\mathbf{x}}_{\mathrm{pls}}' = (\mathbf{I}_N + \mu \mathbf{D}^T \mathbf{D})^{-1} \mathbf{y}

显式表达式的进一步简化：

由于\mathbf{D}^T \mathbf{D} 是一个(N \times N) 的矩阵，且\mathbf{I}_N 是单位矩阵，因此：

11. 当 \mu' \sim 0 以及当 \mu' \to \infty 时，该准则会出现哪些简化形式？请分别给出适当的说明。

 当\mu = 0 时，带惩罚项的最小二乘准则退化为普通的最小二乘准则：

When \mu=0 the penalized least square criterion will degenerate to the standard LS criterion:

对应的估计量与普通的最小二乘估计\mathbf{x}_{\mathrm{LS}} 相同，即：

The corresponding estimator is the same as the ordinary least squares estimate x_{LS}:

 当\mu \to \infty 时，正则化项的权重远大于最小二乘项：

when \mu \to \infty , the weight of the regularization term is much larger than the least squares term:

对应的估计量：

在\mu \to \infty 的极限下，信号倾向于平滑。

随着\mu \to \infty， \hat{\mathbf{x}}_{\mathrm{pls}}' 的幅度趋近于零：

因此要适当选择\mu 来既保证平滑又能拟合y

 Under the limit \mu \to \infty , the signal tends to be smooth, the amplitude of the signal \hat{\mathbf{x}}_{\mathrm{pls}}' approaches 0, so its necessary to choose \mu to ensure both smoothness and fit y

12. 计算\hat{\mathbf{x}}_{\mathrm{LS}} 的偏差（bias）和协方差矩阵，并给出适当的说明。

偏差（Bias）：

偏差定义为估计量的期望值与真实值之差：

计算过程：

1. 计算期望值：

   \mathbb{E}[\hat{\mathbf{x}}_{\mathrm{pls}}'] = (\mathbf{I}_N + \mu \mathbf{D}^T \mathbf{D})^{-1} \mathbb{E}[\mathbf{y}] = (\mathbf{I}_N + \mu \mathbf{D}^T \mathbf{D})^{-1} (\mathbf{x} + \mathbb{E}[\mathbf{e}]) = (\mathbf{I}_N + \mu \mathbf{D}^T \mathbf{D})^{-1} \mathbf{x}

2. 计算偏差：

   \text{Bias}(\hat{\mathbf{x}}_{\mathrm{pls}}') = (\mathbf{I}_N + \mu \mathbf{D}^T \mathbf{D})^{-1} \mathbf{x} - \mathbf{x} = \left[ (\mathbf{I}_N + \mu \mathbf{D}^T \mathbf{D})^{-1} - \mathbf{I}_N \right] \mathbf{x}

   进一步简化：

   \text{Bias}(\hat{\mathbf{x}}_{\mathrm{pls}}') = -\mu (\mathbf{I}_N + \mu \mathbf{D}^T \mathbf{D})^{-1} \mathbf{D}^T \mathbf{D} \mathbf{x}

协方差矩阵（Covariance Matrix）：

协方差矩阵定义为：

计算过程：

由于(\mathbf{I}_N + \mu \mathbf{D}^T \mathbf{D}) 是对称矩阵（即(\mathbf{I}_N + \mu \mathbf{D}^T \mathbf{D})^T = \mathbf{I}_N + \mu \mathbf{D}^T \mathbf{D}），因此：

简化表达：

说明：

存在系统性偏差，其偏差与正则化参数\mu 及差分矩阵\mathbf{D} 的性质相关，当\mu = 0 时，回到普通的最小二乘估计。随着\mu 的增大，抑制噪声效果加强，但是偏差的绝对值增加，协方差减小，估计结果更加稳健。

偏差 - 协方差之间要均衡取\mu 值

Has a systematic bias, and this bias is related to the regularization parameter \mu and the properties of the difference matrix D. When μ = 0, it return to the ordinary least squares estimate. As \mu increases, noise suppression is strengthened, but the absolute value of the biais grows, the covariance decreases, and the estimation results become more robust.

So, we need to choose a balanced value of the \mu between the bias and covariance. 

14. 提出一种方法来估计正则化参数\mu。

我们调整不同的\mu 值来查看 MSE 的大小，最终我们取 令 MSE 最小的那个\mu 值。

 We adjust different values of \muto observe how the MSE changes. Ultimately, we select the value of \mu that minimizes the MSE

15. 给出解决该问题的其他可选方法。

在实验一中，我们使用了 wiener - hunt filtering 方法（二次正则化），并引入了近似循环差分矩阵的思想，并利用 DFT 来将其对角化实现求解

在实验二中，我们采用了贝叶斯方法来自动调节超参数。

在实验三中，我们采用了 Huber 作为惩罚项 （半二次正则化方法）（Half-Quadratic）

在实验四中，我们使用了ADUM算法来求解线性等式约束问题

In the TP1, we used the method of the Wiener-hunt filtering (Quadratic regularization), introduced the idea of an approximate circulant difference matrix, and used the DFT to diagonalize it for solving the problem.

In the TP2, we adopted a Bayesian method to automatically tune hyper parameters.

In the TP3, we chose the Huber function as the penalty term (half - quadratic regularization method)

In the TP4, we applied the ADUM algorithm to solve linear equality - constrained problems.

Exercice II — 绝对惩罚与二次惩罚的对比

让我们考虑如下准则：

其中， y \in \mathbb{R}， h \in \mathbb{R}^+ 都是给定的， \phi 是一个从\mathbb{R} 映射到\mathbb{R} 的函数（具体形式见下方）。这是带惩罚项的最小二乘准则在一维退化情形（one dimensional degenerated case）下的一个特例。正值参数\mu 即所谓的正则化参数（regularisation parameter）。考虑它的最小化解：

这就是带惩罚项解在一维退化情形下的特例。

Quadratic penalty（二次惩罚）

作为第一个惩罚项，我们先考虑二次惩罚：

1. 求出该情形下的最优解\hat{x}，并就此给出适当的说明。参数\mu 会如何影响该解？特别地，讨论当\mu \to 0 以及当\mu \to +\infty 时会发生什么情况？

目标函数变为

 要找到最优解\hat{x}，对\mathcal{J}(x) 关于x 求导并令其为零。

令该导数等于零：

整理可得

这就是带二次惩罚时的一维最优解

 可以看出：

• 当\mu \to 0 时，

  \hat{x} \;\to\; \frac{h\,y}{h^2 + 0} \;=\; \frac{y}{h}

  惩罚项消失，最优解恰好就是最小二乘法的无约束解\,y/h

• 当\mu \to +\infty 时，

  \hat{x} \;\to\; \frac{h\,y}{+\infty} \;=\; 0

  即当惩罚项的权重非常大时，最优解会趋向于 0。

Absolute penalty（绝对值惩罚）

作为第二个惩罚项，我们再来看绝对惩罚：

2. 求最优解\hat{x} 的显式表达式，并就其性质给出适当的说明。参数\mu 对该解有何影响？特别地，当\mu \sim 0 和当\mu \to \infty 时会分别发生什么情况？

目标函数变为

因为|x| 在x=0 处不可导，需要分段解析。我们考虑x>0、 x<0 以及x=0 三种情形分别求解，再筛选出真正的最优解。

先分别考虑x>0 和x<0 两种情况，对应的真导数为

故对于x \neq 0，设其符号为\mathrm{sgn}(x)\in\{+1,-1\}，我们有

令其为零，得到

1. x>0 时： \mathrm{sgn}(x)=+1

   2\,h\,(h x - y) = \mu \;\;\Longrightarrow\;\; h x - y = \frac{\mu}{2h} \;\;\Longrightarrow\;\; x = \frac{y}{h} \;+\; \frac{\mu}{2h^2}

   但要满足x>0，这就要求

   \frac{y}{h} + \frac{\mu}{2h^2} > 0 \;\;\Longrightarrow\;\; y > -\,\frac{\mu}{2h}

   因此当y > -\,\frac{\mu}{2h} 时，最小化器为\hat{x} = \frac{y}{h} \;+\; \frac{\mu}{2h^2}

    

2. x<0 时： \mathrm{sgn}(x)=-1

   2\,h\,(h x - y) = -\,\mu \;\;\Longrightarrow\;\; h x - y = -\frac{\mu}{2h} \;\;\Longrightarrow\;\; x = \frac{y}{h} \;-\; \frac{\mu}{2h^2}

   同理，要满足x<0，即

   \frac{y}{h} - \frac{\mu}{2h^2} < 0 \;\;\Longrightarrow\;\; y < \frac{\mu}{2h}

   因此当y < \frac{\mu}{2h} 时，最小化器为x = \frac{y}{h} \;-\; \frac{\mu}{2h^2}

    

3. x = 0 时：次梯度条件

   在x=0 处，我们用次梯度条件：

   -2h \,\bigl(y - h\cdot 0\bigr) + \mu\,s \;=\; 0, \quad \text{其中 } s \in [-1,\,1]

   即

   -2h\,y + \mu \, s = 0 \;\;\Longrightarrow\;\; \mu \, s = 2h\,y

   因为s 必须满足s \in [-1,1]，所以

   2h\,y \;\in\; [-\mu,\,\mu] \;\;\Longrightarrow\;\; y \;\in\;\bigl[-\tfrac{\mu}{2h},\;\tfrac{\mu}{2h}\bigr]

   因此当|y| \le \tfrac{\mu}{2h} 时，最小化器为 x=0

   可以忽略这部分，直接让y \;\in\;\bigl[-\tfrac{\mu}{2h},\;\tfrac{\mu}{2h}\bigr] 在这个范围内的时候最小化器为 0 即可

综合上面三种情形，最优解\hat{x} 在绝对值惩罚下具有 三段式 结构：

 这说明了L_1 惩罚（绝对值惩罚）会产生“稀疏”解，会产生一部分 0 

• 当\mu \to 0（或\mu 很小时），\Bigl[-\tfrac{\mu}{2h}, \,\tfrac{\mu}{2h}\Bigr] 会收窄到 0 附近，这意味着

  \hat{x} \;\approx\;\frac{y}{h}

  即与无惩罚时的普通最小二乘解相同。

• 当\mu \to +\infty 时，该区间会变得很大，几乎所有y 都落在\bigl[-\tfrac{\mu}{2h},\,\tfrac{\mu}{2h}\bigr] 里，故最终解会收敛到

  \hat{x}=0

3. 考虑基于以下带惩罚项准则的信号反卷积（deconvolution）问题：

推断所求信号估计所应具备的定性性质，并就稀疏性（parsimony）做出评论。 

• \ell_1 惩罚会促使许多分量x_n 在最优解处变为 0，从而产生稀疏解。

• 不平滑，由于有为 0 值的稀疏解，信号不平滑

• 对\mu 的调整困难，如果\mu 小，那么解会尽可能拟合数据，但是可能过拟合，惩罚项不明显。但是如果\mu 大，那么解的更多分量会被置为 0，稀疏程度变大

•  The \ell_1penalty can drive many components x_nto become 0 at the optimal solution, thus producing a sparse solution

• It is not smooth. Because there are solutions with zero-valued components, the signal is not smooth.

• Turning \mu is difficult, if \mu is small, the solution will try to fit the data as closely as possible and may lead to overfitting, the effect of the penalty is not very obvious. But if \mu is large, more component of the solution will be set to 0, increasing the sparsity.

 Exercice III — Legendre transform of transforms

令f 为定义在\mathbb{R} 上、取值于\mathbb{R} 的严格凸（strictly convex）函数。取x_0 \in \mathbb{R}，并定义新的函数

即通过对函数f 进行水平方向上的平移而得到。我们回顾，函数f 的 Legendre 变换（Legendre transform） f^* 也是定义在\mathbb{R} 上并取值于\mathbb{R} 的函数，它可以通过求解以下最大化问题得到：

试求v^*（即v 的 Legendre 变换），并将其写成f^* 的形式。

根据 Legendre 变换的定义

令y = x - x_0，则x = y + x_0。将此代入上式：

由于x_0\, t 与y 无关，可以作为常数提出求上确界（sup）运算之外：

而右侧的\sup_{y \in \mathbb{R}} \bigl[y\,t - f(y)\bigr] ，正是f^*(t) 的定义，即

因此

Exercice IV — Quadratic criterion and linear constraint, a two-one dimensional case

本题涉及一个带约束的优化问题。更具体地说，是一个二维的二次目标函数和一个一维线性约束。

• 一方面，定义函数\varphi: \mathbb{R}^2 \to \mathbb{R}，它接收一对实数(x,y) 作为输入，并输出如下的实数：

  \varphi(x,y) \;=\; 1 \;+\; \frac{x^2 + y^2}{2}.

• 另一方面，令我们所考虑的满足下列线性约束(C) 的实数对(x,y) 的集合为：

  (C) \;:\; y \;=\; x \;+\; o,

  其中o \in \mathbb{R} 表示一个偏移量。

本题所要求解的是在满足约束(C) 情形下最小化\varphi 的问题，即

并在此基础上，除了直接求解法以外，还要借助 Lagrange 乘子法（Lagrange multipliers）来分析该问题的解。

1. 给出无约束情形下的最优解及其对应的最小值。之后的题目都针对有约束情形展开。

若不施加任何约束，即最小化

求两个偏导等于0，其全局最优解显然是

使得x^2 + y^2 达到最小值0。对应的最小函数值为

2. 通过图示的方式，说明该问题以及它的解。

• 目标函数几何

  \varphi(x,y) = 1 + \tfrac{x^2 + y^2}{2} 在\mathbb{R}^2 上，容易看出这是一个以(x,y)=(0,0) 为中心的“抛物面”（或圆形等值线），其等值曲线是以原点为圆心的若干同心圆（半径越大， \varphi 值越大）。

• 约束几何

  约束(C): y = x + o 是一条斜率为 1、截距为o 的直线。

• 有约束最优解

  在满足y = x + o 的所有点中，我们要找到与\varphi(x,y) 之间 欧几里得距离最小 的那一个

3. 通过将约束(C) 直接代入\varphi 来给出直接解法。

由于约束是

可将其直接带入\varphi：

简化为

因此

要最小化此单变量函数，令其导数为零：

由约束y = x + o 可得

故有约束情况下的最优解为

将其带回\varphi：

4. 使用 Lagrange 乘子法进行求解。

4a. 写出拉格朗日函数L[x, y, \lambda]。它关于(x, y) 是二次函数还是线性函数？那关于\lambda 又是什么性质？

约束可写为

定义

• 关于(x,y)，它是二次函数（因为含x^2、 y^2 项） Quadratic function

• 关于\lambda，它是线性函数（系数就是y - x - o） Linear function

   

4b. 给出L[x, y, \lambda] 对(x, y) 的极小值点x_m(\lambda) 和y_m(\lambda)。它们关于\lambda 分别是二次函数还是线性函数？

先对x,y 求偏导并令其为零：

1. 对x 求导：

   \frac{\partial L}{\partial x} = x + \lambda\;\bigl(\,-1\bigr) = x - \lambda = 0 \quad\Longrightarrow\quad x = \lambda

2. 对y 求导：

   \frac{\partial L}{\partial y} = y + \lambda\;\bigl(\,1\bigr) = y + \lambda = 0 \quad\Longrightarrow\quad y = -\,\lambda

可见

• 它们均是关于\lambda 的线性函数

   

4c. 通过在拉格朗日函数L[x, y, \lambda] 中用x_m(\lambda) 和y_m(\lambda) 替换x 和y，构造对偶函数

代入

化简：

• 第一部分：

  1 + \frac{\lambda^2 + (-\lambda)^2}{2} = 1 + \frac{\lambda^2 + \lambda^2}{2} = 1 + \frac{2\lambda^2}{2} = 1 + \lambda^2

• 第二部分：

  \lambda\,\bigl[-\lambda - \lambda - o\bigr] = \lambda\,(-2\lambda - o) = -2\lambda^2 - \lambda\,o

因此

4d. 求出对偶函数\tilde{L}[\lambda] 关于\lambda 的极大值点\lambda_m。

对偶问题是

令\tfrac{d}{d\lambda}\,\tilde{L}(\lambda) = 0：

4e. 最后，通过将\lambda_m 代入(x_m(\lambda),\, y_m(\lambda)) 的表达式，得出带约束的极小值点(x_*,\, y_*)

将\lambda_m = -\tfrac{o}{2} 代入x_m(\lambda),\, y_m(\lambda)：

这与直接法所得解完全吻合

5. 你认为加了约束之后的极小值与未加约束时的极小值相比，是更大还是更小？通过分别计算函数\varphi 的这两个数值来验证你的答案。

• 无约束极小值： (0,\,0)，对应\varphi(0,0) = 1.

• 带约束极小值： \bigl(-\tfrac{o}{2},\, \tfrac{o}{2}\bigr)，对应

  \varphi\Bigl(-\tfrac{o}{2},\,\tfrac{o}{2}\Bigr) = 1 + \frac{o^2}{4}

若o \neq 0，则

也就是说，有约束之后的最优值更大（因为原本最优的点(0,0) 不再可行）。只有在o=0 的特殊情形下，取等号

That is to say, the optimal value after the constraints is larger.

The equality sign is only taken in special cases.

6. 比较原问题（原始函数\varphi）的带约束极小值与对偶问题（对偶函数\tilde{L}[\lambda]）的无约束极大值。

• 原问题（主问题）最优值

  \min_{x,y:\,y=x+o}\,\varphi(x,y) = 1 + \frac{o^2}{4}

• 对偶问题最优值

  \max_{\lambda}\,\tilde{L}(\lambda) = \tilde{L}\Bigl(-\tfrac{o}{2}\Bigr)

根据上节对\tilde{L}(\lambda) 的表达式

将\lambda_m = -\tfrac{o}{2} 带入：

这正好与主问题的带约束最优值相同，因为其 强对偶性 (strong duality)，故二者相等。

This is exactly the same as the constrained optimal value of the primal problem, because of its strong duality, so they are equal.

7. 讨论o=0 这一特殊情形。

若o=0，则线性约束y = x + o 退化成y = x。这时：

• 无约束最优点(0,0) 本身就满足y = x = 0，故它同时是有约束时的最优解。

the unconstrained optimum point (0,0) already satisfied y = x = 0, so it is also the optimal solution under the constraint.

• 直接带入计算后发现，有约束解与无约束解一致，最优值相同。

Direct substitution shows that the constrained solution is the same as the unconstrained solution, the optimal value are the same.