Q1. 最小值的存在性和唯一性
存在性分析
根据第一章关于极小值点存在性的理论，我需要验证以下条件：
目标函数：
f(x) = \frac{1}{2}x^{\top}Hx + v^{\top}x
这是一个连续函数，且函数 f 是严格凸的（因为 H 正定）
约束集：
C = \{x \in \mathbb{R}^n : x^{\top}L^{\top}Lx \leq 1\}
由于 L 是满秩矩阵，L^{\top}L 是正定矩阵，因此 C 是一个椭球体，椭球体是有界闭集，即紧集。
根据Weierstrass定理，连续函数在紧集上必定达到其最小值。因此，问题 (\mathcal{P}_0) 的最小值存在。
唯一性分析
由于目标函数 f(x) 是严格凸函数，且约束集 C 是凸集，严格凸函数在凸集上的极小值点（如果存在）是唯一的，因此问题 (\mathcal{P}_0) 存在唯一的最小值点
Q2. 问题的重新表述
为了将 (\mathcal{P}_0) 转化为 (\mathcal{P}_1)，需要进行变量替换。
步骤1：分析矩阵 L^{\top}L
由于 L 是满秩矩阵，L^{\top}L 是对称正定矩阵。设其特征值分解为：
L^{\top}L = Q\Lambda Q^{\top}
- Q 是正交矩阵（Q^{\top}Q = I）
- \Lambda = \text{diag}(\lambda_1, \ldots, \lambda_n)，且 \lambda_i > 0
步骤2：变量替换
令：
y = \Lambda^{1/2}Q^{\top}x
则逆变换为：
x = Q\Lambda^{-1/2}y
步骤3：转换约束条件
原约束 x^{\top}L^{\top}Lx \leq 1 变为：
\begin{align}
x^{\top}L^{\top}Lx &= y^{\top}\Lambda^{-1/2}Q^{\top} \cdot Q\Lambda Q^{\top} \cdot Q\Lambda^{-1/2}y \\
&= y^{\top}\Lambda^{-1/2}\Lambda\Lambda^{-1/2}y \\
&= y^{\top}y \leq 1
\end{align}
步骤4：转换目标函数
将 x = Q\Lambda^{-1/2}y 代入目标函数：
\begin{align}
f(x) &= \frac{1}{2}x^{\top}Hx + v^{\top}x \\
&= \frac{1}{2}y^{\top}\Lambda^{-1/2}Q^{\top}HQ\Lambda^{-1/2}y + v^{\top}Q\Lambda^{-1/2}y
\end{align}
设 \tilde{H} = \Lambda^{-1/2}Q^{\top}HQ\Lambda^{-1/2}，这是一个对称正定矩阵。
步骤5：变量替换
对 \tilde{H} 进行特征值分解：
\tilde{H} = PDP^{\top}
- P 是正交矩阵
- D = \text{diag}(d_1, \ldots, d_n)，且 d_i > 0
令 z = P^{\top}y，则目标函数变为：
\begin{align}
f &= \frac{1}{2}z^{\top}P^{\top}\tilde{H}Pz + (P^{\top}\Lambda^{-1/2}Q^{\top}v)^{\top}z \\
&= \frac{1}{2}z^{\top}Dz + w^{\top}z \\
&= \frac{1}{2}\sum_{k=1}^{n}z_k^2 d_k + w^{\top}z
\end{align}
综上所述，问题 (\mathcal{P}_1) 中 d_k 和向量 w 的表达式为:
d_k = \left( \Lambda^{-1/2} Q^{\top} H Q \Lambda^{-1/2} \right)_{(k)}
即 d_k 是矩阵 \Lambda^{-1/2}Q^{\top}HQ\Lambda^{-1/2} 的第 k 个特征值
w = P^{\top}\Lambda^{-1/2}Q^{\top}v
其中 \Lambda 和 Q 来自 L^{\top}L 的特征值分解，P 和 D 来自 \tilde{H} 的特征值分解。
Q3. 强对偶性和拉格朗日函数
强对偶性的验证
对于问题 (\mathcal{P}_1)：
\min_{z \in \mathbb{R}^n} \frac{1}{2} \sum_{k=1}^{n} z_k^2 d_k + w^{\top} z \quad \text{约束条件：} \quad z^{\top} z \leq 1
根据强对偶性条件，我们需要目标函数和约束函数都是凸函数，且满足Slater条件，
凸函数的证明
(1) 目标函数
f(z) = \frac{1}{2}z^{\top}Dz + w^{\top}z
根据凸函数判定定理，对于二次可微函数，如果其Hessian矩阵半正定，则函数是凸的
一阶导数
\nabla f(z) = \frac{\partial}{\partial z}\left(\frac{1}{2}z^{\top}Dz + w^{\top}z\right) = Dz + w
Hessian矩阵
\nabla^2 f(z) = \frac{\partial}{\partial z}(Dz + w) = D = \begin{pmatrix}
d_1 & 0 & \cdots & 0 \\
0 & d_2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & d_n
\end{pmatrix}
对于任意非零向量 h \in \mathbb{R}^n：
h^{\top} \nabla^2 f(z) h = h^{\top} D h = \sum_{k=1}^n d_k h_k^2
由于 d_k > 0 对所有 k 成立，且至少有一个 h_k \neq 0（因为 h \neq 0），所以：
h^{\top} D h = \sum_{k=1}^n d_k h_k^2 > 0
因此 Hessian矩阵 \nabla^2 f(z) = D 是正定的，因此 f(z) 是严格凸函数。
(2) 约束函数
h(z) = z^{\top}z - 1
由于是二次型，因此Hessian矩阵是 2I_n ，对于任意非零向量 v \in \mathbb{R}^n：
v^{\top} \nabla^2 h(z) v = v^{\top} (2I_n) v = 2v^{\top}v = 2\|v\|^2 > 0
因此目标函数和约束函数都是凸函数
Slater条件证明
即需要存在 \bar{z} \in \text{dom } f 使得 h(\bar{z}) < 0 ，因此我们取取 \bar{z} = 0，则
h(0) = 0^{\top}0 - 1 = -1 < 0
可见Slater条件满足。
因此强强对偶性成立，对偶间隙为零。
拉格朗日函数
对应的拉格朗日函数形式为：
\mathcal{L}(z, \lambda) = f(z) + \lambda h(z) = \frac{1}{2} \sum_{k=1}^{n} z_k^2 d_k + w^{\top} z + \lambda(z^{\top}z - 1)
- 其中 \lambda \geq 0 是拉格朗日乘子。
重新整理：
\mathcal{L}(z, \lambda) = \frac{1}{2} z^{\top}(D + 2\lambda I)z + w^{\top}z - \lambda
对偶拉格朗日函数
根据定义，对偶函数公式为：
\underline{\mathcal{L}}(\lambda) = \inf_{z \in \mathbb{R}^n} \mathcal{L}(z, \lambda)
求最小值，令梯度为零：
\nabla_z \mathcal{L}(z, \lambda) = (D + 2\lambda I)z + w = 0
由于 d_k > 0 且 \lambda \geq 0，矩阵 (D + 2\lambda I) 可逆，因此：
z^*(\lambda) = -(D + 2\lambda I)^{-1}w = -\begin{pmatrix} \frac{w_1}{d_1 + 2\lambda} \\ \vdots \\ \frac{w_n}{d_n + 2\lambda} \end{pmatrix}
将 z^*(\lambda) 代入拉格朗日函数：
\underline{\mathcal{L}}(\lambda) = -\frac{1}{2} \sum_{k=1}^{n} \frac{w_k^2}{d_k + 2\lambda} - \lambda
对偶问题为：
\max_{\lambda \geq 0} \underline{\mathcal{L}}(\lambda) = \max_{\lambda \geq 0} \left( -\frac{1}{2} \sum_{k=1}^{n} \frac{w_k^2}{d_k + 2\lambda} - \lambda \right)
Q4. 数值应用（Matlab实现）
Q5. 前向-后向算法
问题的重新表述
为了使用前向-后向算法，我们需要把约束优化问题转换为无约束问题。
原问题 (\mathcal{P}_1) 是：
\min_{z \in \mathbb{R}^n} \frac{1}{2} \sum_{k=1}^{n} z_k^2 d_k + w^{\top} z \quad \text{约束条件：} \quad z^{\top} z \leq 1
重写为无约束形式：
\min_{z \in \mathbb{R}^n} f(z) + g(z)
其中 f(z) 是光滑函数（可微），g(z) 是约束变成指数函数后的形式，其本质还是约束条件，他们对应公式为
f(z) = \frac{1}{2} \sum_{k=1}^{n} z_k^2 d_k + w^{\top} z
g(z) = \iota_C(z)
指示函数定义为：
\iota_C(z) = \begin{cases}
0 & \text{如果 } z \in C \\
+\infty & \text{如果 } z \notin C
\end{cases}
- 其中，C = \{z \in \mathbb{R}^n : z^{\top}z \leq 1\} 是单位球
综上所述，因此我们可将原公式写为
\min_{z \in \mathbb{R}^n} \left[ \underbrace{\frac{1}{2} \sum_{k=1}^{n} z_k^2 d_k + w^{\top} z}_{f(z)} + \underbrace{\iota_C(z)}_{g(z)} \right]
近端算子
但是由于指示函数在边界处不可微，因此我们无法直接求梯度，因此我们用近端算子代替梯度:
- 对于光滑函数 f，使用梯度步 z - \gamma \nabla f(z)
- 对于非光滑函数 g，使用近端算子 \text{prox}_{\gamma g}(v)
因此在FB算法中，前向步处理函数 f，后向步处理函数 g
根据函数 g 的近端算子定义为：
\text{prox}_{\gamma g}(v) = \arg\min_{z \in \mathbb{R}^n} \left\{ g(z) + \frac{1}{2\gamma}\|z - v\|^2 \right\}
代入 g(z) = \iota_C(z)：
\begin{align}
\text{prox}_{\gamma \iota_C}(v) &= \arg\min_{z \in \mathbb{R}^n} \left\{ \iota_C(z) + \frac{1}{2\gamma}\|z - v\|^2 \right\} \\
&= \arg\min_{z \in C} \frac{1}{2\gamma}\|z - v\|^2 \\
&= P_C(v)
\end{align}
可以得到函数 g 的近端算子就是投影
\text{prox}_{\gamma \iota_C}(v) = P_C(v)
投影到单位球
根据投影的理论，点 v 在闭凸集 C 上的投影 P_C(v) 是满足以下条件的唯一点：
P_C(v) = \arg\min_{z \in C} \|z - v\|
对于单位球 C = \{z : \|z\| \leq 1\}，投影公式为：
P_C(v) = \begin{cases}
v & \text{如果 } \|v\| \leq 1 \\
\frac{v}{\|v\|} & \text{如果 } \|v\| > 1
\end{cases}
如果点 v 在单位球内或边界上，它的投影就是它自己，如果点 v 在单位球外，投影是从原点到 v 的射线与单位球面的交点
前向-后向算法推导
在FB算法中，交替进行两个步骤：
前向步：处理函数 f，沿着 f 的负梯度方向移动（梯度下降）
后向步：处理函数 g
根据最优性条件，\hat{z} 是最优解当且仅当:
0 \in \nabla f(\hat{z}) + \partial g(\hat{z})
即在最优点，光滑部分的负梯度必须在非光滑部分的次梯度集合中
即：
-\nabla f(\hat{z}) \in \partial g(\hat{z})
两边同乘 \gamma：
-\gamma \nabla f(\hat{z}) \in \gamma \partial g(\hat{z})
加上 \hat{z}：
\hat{z} - \gamma \nabla f(\hat{z}) \in \hat{z} + \gamma \partial g(\hat{z})
左边是从 \hat{z} 出发沿负梯度方向走一步，右边是 \hat{z} 加上次梯度的集合。
根据凸分析理论，以下三个条件等价：
v \in z + \gamma \partial g(z)
z - v \in -\gamma \partial g(z)
z = \text{prox}_{\gamma g}(v)
令 v = \hat{z} - \gamma \nabla f(\hat{z})，则：
\hat{z} - \gamma \nabla f(\hat{z}) \in \hat{z} + \gamma \partial g(\hat{z})
根据上面的等价关系，这等价于：
\hat{z} = \text{prox}_{\gamma g}(\hat{z} - \gamma \nabla f(\hat{z}))
FB算法根据这个不动点方程的迭代求解
前向-后向算法流程
进行迭代
步骤1：计算梯度
\nabla f(z^k) = D z^k + w
- 其中 D = \text{diag}(d_1, \ldots, d_n)
\nabla f(z^k) = \begin{pmatrix}
d_1 z_1^k + w_1 \\
d_2 z_2^k + w_2 \\
\vdots \\
d_n z_n^k + w_n
\end{pmatrix}
步骤2：前向步（梯度下降）
y^{k+1} = z^k - \gamma \nabla f(z^k) = z^k - \gamma (D z^k + w)
步骤3：后向步（投影）
z^{k+1} = P_C(y^{k+1})
根据投影 P_C(v) 的公式，可得:
z^{(k+1)} =
\begin{cases}
y^{(k+1)}, & \text{如果 } \|y^{(k+1)}\| \le 1 \\[6pt]
\dfrac{y^{(k+1)}}{\|y^{(k+1)}\|}, & \text{如果 } \|y^{(k+1)}\| > 1
\end{cases}
参数选择
步长选择
为保证收敛，步长必须满足：
0 < \gamma < \frac{2}{L_f}
- 其中 L_f 是 \nabla f 的Lipschitz常数。
对于我们的函数 f(z) = \frac{1}{2}z^{\top}Dz + w^{\top}z，有：
\|\nabla f(z_1) - \nabla f(z_2)\| = \|D(z_1 - z_2)\| \leq \|D\| \cdot \|z_1 - z_2\|
因此 L_f = \|D\|。对于对角矩阵：
L_f = \|D\| = \max_{k=1,\ldots,n} |d_k| = \max_{k=1,\ldots,n} d_k
因此理论上最优的步长是：
\gamma_{\text{opt}} = \frac{1}{L_f} = \frac{1}{\max_k d_k}
