【差分隐私相关概念】一个问题的对偶转换

原始问题（7）转换为对偶形式（8）的详细解释

1. 问题转换的动机

ADMM（交替方向乘子法）适用于可分解的优化问题，通过引入辅助变量将复杂约束拆解为多个简单子问题。原始问题（7）包含L1目标函数、线性等式约束和非负约束，直接求解可能困难。通过变量分裂和约束重写，将其转化为ADMM友好的形式（8）。

2. 变量分裂与约束引入

步骤1：分离L1目标函数

• 引入辅助变量$\mathbf{y}$：将目标函数$\parallel \mathbf{x}-\tilde{\mathbf{x}}{\parallel }_1$拆分为$\parallel \mathbf{y}{\parallel }_1$，并添加等式约束$\mathbf{y}=\mathbf{x}-\tilde{\mathbf{x}}$。
• 数学等价性：若$\mathbf{y}=\mathbf{x}-\tilde{\mathbf{x}}$，则$\parallel \mathbf{y}{\parallel }_1=\parallel \mathbf{x}-\tilde{\mathbf{x}}{\parallel }_1$，二者目标值一致。

步骤2：处理非负约束

• 引入辅助变量$\mathbf{z}$：将非负约束$\mathbf{x}\succcurlyeq 0$转换为$\mathbf{z}\succcurlyeq 0$，并添加等式约束$\mathbf{z}=\mathbf{x}$。
• 数学等价性：若$\mathbf{z}=\mathbf{x}$且$\mathbf{z}\succcurlyeq 0$，则$\mathbf{x}\succcurlyeq 0$，二者约束等价。

步骤3：保留原等式约束

• 原约束$\mathbf{Ax}=\mathbf{b}$直接保留为$\mathbf{Ax}-\mathbf{b}=0$。

3. 对偶形式的构建（增广拉格朗日方法）

通过拉格朗日乘数法，将等式约束合并到目标函数中，构造增广拉格朗日函数：

$$\begin{array}{rl}L(\mathbf{x},\mathbf{y},\mathbf{z},\mu ,\nu ,\eta )& =\parallel \mathbf{y}{\parallel }_1+{\mathbb{I}}_{\mathcal{C}}(\mathbf{z})\\ & +\frac{\rho }{2}\parallel \mathbf{x}-\tilde{\mathbf{x}}-\mathbf{y}+\mu {\parallel }_2^2\\ & +\frac{\rho }{2}\parallel \mathbf{x}-\mathbf{z}+\nu {\parallel }_2^2\\ & +\frac{\rho }{2}\parallel \mathbf{Ax}-\mathbf{b}+\eta {\parallel }_2^2,\end{array}$$

其中：

• $\mu ,\nu ,\eta$是对偶变量（缩放后的拉格朗日乘子）。
• $\rho >0$是惩罚参数，控制约束违反的惩罚强度。
• ${\mathbb{I}}_{\mathcal{C}}(\mathbf{z})$是指示函数，强制$\mathbf{z}\succcurlyeq 0$。

4. ADMM的交替优化步骤

通过交替优化原始变量和对偶变量，逐步逼近最优解：

1. 优化$\mathbf{y}$（子问题9）：
   $${\mathbf{y}}^{k+1}=\arg \underset{\mathbf{y}}{\min }\left(\parallel \mathbf{y}{\parallel }_1+\frac{\rho }{2}\parallel {\mathbf{x}}^k-\tilde{\mathbf{x}}-\mathbf{y}+{\mu }^k{\parallel }_2^2\right).$$

   • 闭合解：通过软阈值（soft-thresholding）求解，处理L1范数。

2. 优化$\mathbf{z}$（子问题10）：
   $${\mathbf{z}}^{k+1}=\arg \underset{\mathbf{z}}{\min }\left({\mathbb{I}}_{\mathcal{C}}(\mathbf{z})+\frac{\rho }{2}\parallel {\mathbf{x}}^k-\mathbf{z}+{\nu }^k{\parallel }_2^2\right).$$

   • 闭合解：将${\mathbf{x}}^k+{\nu }^k$投影到非负象限，即${\mathbf{z}}^{k+1}=\max ({\mathbf{x}}^k+{\nu }^k,0)$。

3. 优化$\mathbf{x}$（子问题11）：
   $${\mathbf{x}}^{k+1}=\arg \underset{\mathbf{x}}{\min }\left(\frac{1}{2}\parallel \mathbf{x}-\tilde{\mathbf{x}}-{\mathbf{y}}^{k+1}+{\mu }^k{\parallel }_2^2+\frac{1}{2}\parallel \mathbf{x}-{\mathbf{z}}^{k+1}+{\nu }^k{\parallel }_2^2+\frac{1}{2}\parallel \mathbf{Ax}-\mathbf{b}+{\eta }^k{\parallel }_2^2\right).$$

   • 闭合解：通过解线性方程组（例如最小二乘）更新$\mathbf{x}$。

4. 更新对偶变量：
   $$\begin{array}{rl}{\mu }^{k+1}& ={\mu }^k+{\mathbf{x}}^{k+1}-\tilde{\mathbf{x}}-{\mathbf{y}}^{k+1},\\ {\nu }^{k+1}& ={\nu }^k+{\mathbf{x}}^{k+1}-{\mathbf{z}}^{k+1},\\ {\eta }^{k+1}& ={\eta }^k+{\mathbf{Ax}}^{k+1}-\mathbf{b}.\end{array}$$

5. 转换的数学等价性

• 必要性：通过变量分裂，确保问题（8）与（7）的解集一致。若$\mathbf{y}=\mathbf{x}-\tilde{\mathbf{x}}$且$\mathbf{z}=\mathbf{x}$，则目标函数和约束条件等价。
• 充分性：任何满足问题（8）的解必然满足原问题（7）的约束，反之亦然。

6. 示例说明

场景：设$\mathbf{x}\in {\mathbb{R}}^2$，$\mathbf{A}=[11]$，$\mathbf{b}=300$，$\tilde{\mathbf{x}}=[101,202]$，需满足$\mathbf{x}\ge 0$且$\mathbf{Ax}=300$。

转换后的形式：

• $\mathbf{y}=\mathbf{x}-\tilde{\mathbf{x}}$，目标为$\parallel \mathbf{y}{\parallel }_1$。
• $\mathbf{z}=\mathbf{x}$，约束$\mathbf{z}\ge 0$。
• 等式约束$\mathbf{Ax}=300$。

ADMM迭代：

1. 初始化${\mathbf{x}}^0=\tilde{\mathbf{x}}$，${\mu }^0={\nu }^0={\eta }^0=0$。
2. 更新$\mathbf{y}$：软阈值处理${\mathbf{y}}^1=\text{sign}({\mathbf{x}}^0-\tilde{\mathbf{x}}+{\mu }^0)\cdot \max (|{\mathbf{x}}^0-\tilde{\mathbf{x}}+{\mu }^0|-\frac{1}{\rho },0)$。
3. 更新$\mathbf{z}$：投影到非负象限${\mathbf{z}}^1=\max ({\mathbf{x}}^0+{\nu }^0,0)$。
4. 更新$\mathbf{x}$：解线性方程组满足所有约束。
5. 更新对偶变量，重复直至收敛。

总结

• 转换逻辑：通过变量分裂将原问题分解为多个简单子问题，利用ADMM交替优化。
• 等价性保证：引入的辅助变量和等式约束确保解的一致性。
• 计算优势：每个子问题可高效求解（如软阈值、投影、线性最小二乘），适合大规模优化。