勒让德变换

定义

勒让德变换（Legendre Transform，LT）或称作凸共轭（Convex Conjugate，CC）

勒让德变换是凸分析中的一个基本工具，广泛用于优化理论中，它将一个函数 f(x) 映射为另一个凸函数 f^*(t)

在进行 LT 之前，我们需要确保原函数 f 满足以下两个条件:

• 严格凸性（strictly convex）： 函数 f(x) 是严格凸的。
• 可导性（differentiability）： 函数 f(x) 至少一次可导（一般要二次导）。

因此通过 勒让德变换，我们就可以得到一个新的函数 f^{*}

其中，\sup 表示取上确界（supremum），也就是取x t - f(x) 的最大值，因此我们可以得到:

说明 f^ *(t) 是所有 x t - f(x) 的上界

我们再将 f(x) 移到右边，可得:

这体现了 f^ *(t) 和 f(x) 的对偶性

性质

我们现在关注勒让德变换在函数的横向伸缩（dilatation）、平移（shift）、以及纵向平移和伸缩的情况下的性质变化

(a) 横向伸缩 (Horizontal Dilatation):

设 \gamma > 0 是横向伸缩系数，定义一个新函数 g(x) ：

对应的勒让德变换为：

横向缩放（乘以 \gamma ）会导致勒让德共轭中的自变量 t 被缩放为 \frac{t}{\gamma}

注意

证明

我们有:

g(x) = f(\gamma x)

目标是推导 g^ *(t) 的表达式，根据勒让德变换的定义，我们可得：

代入 g(x) = f(\gamma x)：

g^*(t) = \sup_{x \in \mathbb{R}} \big[ x t - f(\gamma x) \big]

我们给 xt 这部分配项，乘 \gamma 除 \gamma ，可得

g^*(t) = \sup_{x \in \mathbb{R}} \left[ \frac{\gamma x}{\gamma} t - f(\gamma x) \right]

将 \gamma x 保存好，得到 f(\gamma x) 的 LT 变换 g^ *(t) 等于:

我们发现，

f^ *\left(\frac{t}{\gamma}\right) =\sup_{u \in \mathbb{R}} \bigg[ u \cdot \frac{t}{\gamma} - f(u) \bigg]

不用管 u 是什么，只要一样就可以了，所以我们对比两个形式，观察到 \sup _{x \in \mathbb{R}} \big[ \gamma x \cdot \frac{t}{\gamma} - f(\gamma x) \big] 正是函数 f^ *\left(\frac{t}{\gamma}\right) 的定义，因此:

注意一点，\gamma > 0 的条件是必要的，这是为了保证变换方向和凸性不改变。

(b) 横向平移 (Horizontal Shift):

设 x_0 \in \mathbb{R} 是横向平移的位移量，定义：

对应的勒让德变换为：

对 x 进行平移，相当于在勒让德共轭中增加一项线性修正 x_0 t 。

注意

证明

定义:

g(x) = f(x - x_0)

目标是推导 g^*(t) 的表达式，根据勒让德变换的定义：

g^*(t) = \sup_{x \in \mathbb{R}} \big[ x t - f(x - x_0) \big]

换元，令

u = x - x_0

因此

x = u + x_0

并且当 x \in \mathbb{R} 时，u \in \mathbb{R}（无约束变化范围）。将 x = u + x_0 带入原式：

展开括号：

g^*(t) = \sup_{u \in \mathbb{R}} \big[ u t + x_0 t - f(u) \big]

注意到 x_0 t 是与 u 无关的常数，因此可以从 \sup 中提取出来：

g^*(t) = \sup_{u \in \mathbb{R}} \big[ u t - f(u) \big] + x_0 t

我们注意到，其中的 \sup_{u \in \mathbb{R}} \big[ u t - f(u) \big] 就是 f^ *(t) 的定义:

因此可以得到：

证毕

(c) 纵向平移和伸缩 (Vertical Shift-Dilatation):

设 \alpha \in \mathbb{R} 和 \beta > 0 ，定义新的函数 g(x) ：

对应的勒让德变换为：

纵向伸缩 \beta 会缩放勒让德变换的自变量 t ，并乘以 \beta 。纵向平移 \alpha 直接导致勒让德共轭函数的值减去 \alpha

注意

证明

其中:

因此:

由于 \alpha 与 x 无关:

将 sup 里面表达式 乘 \beta 除 \beta ，可得:

我们注意到 \sup_{x \in \mathbb{R}} \left[ \frac{t}{\beta} x - f(x) \right] 就是 f^*\left( \frac{t}{\beta} \right) 的定义，即：

得到：

证毕

举例

下面我们以一个二次函数为例，详细计算推导它的勒让德变换（Legendre Transform, LT）

其中：

• \alpha \in \mathbb{R} 是一个常数，表示垂直偏移；
• \beta > 0 是参数，控制二次项的系数；
• x_0 是偏移中心。

目标是找到其勒让德变换：

推导过程

我们先看里面 x t - f(x) 这一项，因此定义辅助函数：

将 f(x) 代入得到：

展开：

所以，原式等于:

我们希望再次基础上更进一步，也就是拿掉 sup 符号。为了完成这一点，需要找到内层函数 g_t(x) 的极大值。

对 g_t(x) 求导数并找到极值点

计算 g_t(x) 的一阶导数：

令 g_t^{\prime}(x) = 0 解出极值点：

计算 g_t(x) 的二阶导数：

由于 \beta > 0 ，说明 g_t(x) 是一个严格concave函数，因此在 \bar{x} 处确实取得最大值。

将极值点代回 g_t(x)

将 \bar{x} = x_0 + \frac{t}{\beta} 代入 g_t(x) ：

具体代入：

展开化简：

进一步整理：

最终结果：

具体过程是：

1. 定义辅助函数 g_t(x) = x t - f(x)
2. 求导数 g_t^{\prime}(x) = t - f^{\prime}(x)
3. 找到零点 \bar{x} = \chi(t)
4. 代回 g_t( \bar{x}) 得到 f^*(t)

求导

勒让德变换通用表达式为：

其中： \chi(t) 是 f^{\prime}(x) 的反函数，即 \chi(t) = (f^{\prime})^{-1}(t) 。

一阶导数

为了求 f^ *(t) 的一阶导数，对 f^ *(t) 进行求导：

利用链式法则，得到：

由于 \chi(t) = f^{\prime-1}(t) ，并且 f^{\prime}[\chi(t)] = t ，代入后有：

因此，一阶导数结果为：

勒让德变换的二阶导数

对 f^ { *\prime}(t) = \chi(t) 再求导：

由于 \chi(t) = f^{\prime-1}(t) ，求导得到：

因此，勒让德变换的二阶导数为：

由于 f^{\prime\prime}(x) > 0 （f(x) 是严格凸函数），所以 f^ {*\prime\prime}(t) > 0 ，从而证明 f^ *(t) 始终是凸函数。

clear; close all; clc;

%% 参数设置 (用于勒让德变换及半二次分解示例)
alpha = 1.0;  % f(x)的垂直偏移
beta = 2.0;   % f(x)中二次项系数 > 0
x0 = 0.5;     % f(x)中心偏移

% 定义原函数 f(x)
f = @(x) alpha + (beta/2)*(x - x0).^2;

% 理论勒让德共轭 f*(t)
f_star_analytic = @(t) (t.^2)/(2*beta) + t*x0 - alpha;

% 定义 t 和 x 的取值范围用于数值求解
t_vals = linspace(-5,5,200);
x_vals = linspace(-5,5,200);

%% 数值求勒让德变换 f*(t)
f_star_numeric = zeros(size(t_vals));
for i = 1:length(t_vals)
    t = t_vals(i);
    g_t = @(x) x*t - f(x);
    neg_g_t = @(x) -g_t(x);
    [~, fval_neg] = fminbnd(neg_g_t, min(x_vals), max(x_vals));
    f_star_numeric(i) = -fval_neg;
end

%% 对比数值结果和解析解
figure; 
plot(t_vals, f_star_numeric, 'r', 'LineWidth',2); hold on;
plot(t_vals, f_star_analytic(t_vals), 'b--', 'LineWidth',2);
xlabel('t','Interpreter','none'); 
ylabel('f*(t)','Interpreter','none');
legend({'Numerical f*(t)','Analytical f*(t)'},'Interpreter','none','Location','best');
title('Legendre transform: numerical vs analytical','Interpreter','none');

双重共轭恢复原函数

勒让德变换的一个关键性质，即双重共轭恢复原函数

注意

证明

双重共轭函数定义为：

定义辅助函数 h_t(x) ：

对 h_t(x) 求导，计算 h_t^{\prime}(x) ：

根据勒让德变换的性质：

因此：

h_t^{\prime}(x) = t - \chi(x)

令导数 h_t^{\prime}(x) = 0 ，得：

t - \chi(\bar{x}) = 0 \quad \implies \quad \bar{x} = \chi(t)

将极值点代入

将 \bar{x} = \chi(t) 代入 h_t(x) ：

根据勒让德变换的定义 f^*(\bar{x}) = \bar{x} \chi(t) - f[\chi(t)] ，可以展开为：

化简得到：

由于 \chi(t) = f^{\prime-1}(t) ，因此:

f[\chi(t)] = f(f^{\prime-1}(t))

因此：

双重共轭性质表明，严格凸且下半连续的函数在进行两次勒让德变换后会恢复原函数。这一性质保证了勒让德变换的对偶性，因此在在优化问题中构造对偶关系来解决问题。

%% 双重共轭验证 f^{**}(x) = f(x)
x_test = linspace(-1,2,200);
f_dd_star = zeros(size(x_test));
for i = 1:length(x_test)
    x_val = x_test(i);
    h_xt = @(tau) x_val*tau - f_star_analytic(tau);
    neg_h_xt = @(tau) -h_xt(tau);
    [~, h_min_val] = fminbnd(neg_h_xt, -10, 10);
    f_dd_star(i) = -h_min_val;
end

figure; 
plot(x_test, f(x_test), 'b', 'LineWidth',2); hold on;
plot(x_test, f_dd_star, 'r--','LineWidth',2);
xlabel('x','Interpreter','none'); 
ylabel('Function value','Interpreter','none');
legend({'f(x)','f**(x)'},'Interpreter','none','Location','best');
title('Double conjugate check: f**(x) vs f(x)','Interpreter','none');

半二次优化方法的原理和实现

原始准则（Criterion）

定义的优化目标函数 \mathcal{J}(x) 为：

• 第一项 \| \mathbf{y} - \mathbf{H} \mathbf{x} \|^2 是数据拟合项，用来度量 \mathbf{x} 和观测数据 \mathbf{y} 之间的误差

• 第二项 \mu \sum_{p \sim q} \varphi(x_p - x_q) 是正则化项，用于惩罚相邻变量（如图像像素邻点）间的差异

半二次优化的核心是将非二次函数 \varphi(\delta) 转化为带有辅助变量 a 的二次形式，因此我们为每个 x_p - x_q 引入辅助变量 a_{pq} ，使得：

其中， \zeta(a) 是一个自定义构造的函数，这种引入将非二次函数 \varphi(\delta) 分解为关于变量 a 的优化问题。

引入辅助变量后，原始准则扩展为：

新准则 \widetilde{\mathcal{J}}(\mathbf{x}, \mathbf{a}) 现在是关于 \mathbf{x} 和辅助变量 \mathbf{a} 的联合优化问题。

原始准则和扩展准则之间有如下关系：

这说明通过优化 \widetilde{\mathcal{J}}(\mathbf{x}, \mathbf{a}) 的辅助变量 \mathbf{a} ，可以间接得到原始问题的解。

这里一定有一个疑问，为什么一定要引入一个辅助变量呢？直接对原式进行运算不好吗？问题就在非二次函数 φ(δ) 上面，非二次的优化问题可能要处理复杂的非线性和非凸问题，很难求解。通过引入一个辅助变量，将非二次函数 φ(δ) 分解为二次形式和一个新的函数 ζ(a) ，这样就好优化多了，多引入一个变量 a 也不要紧，可以分离 \mathbf{x} 和 \mathbf{a} ，固定一个，优化另一个，并且优化交替进行，通过迭代逐步收敛到全局最优解。

%% 半二次分解示例 (Huber函数)
% 设置Huber函数阈值参数 s
s = 0.5; 
varphi = @(delta) (abs(delta)<=s).* (delta.^2/2) + (abs(delta)>s).*(s*abs(delta)-s^2/2);

% g(delta) = (delta^2)/2 - varphi(delta)
g = @(delta) (delta.^2)/2 - varphi(delta);

% 数值上计算g*(a)
a_vals = linspace(-3,3,200);
g_star_vals = zeros(size(a_vals));
for i=1:length(a_vals)
    a_ = a_vals(i);
    h_a_delta = @(delta) g(delta)-a_*delta; 
    [~,h_min_val] = fminbnd(h_a_delta, -5,5);
    g_star_vals(i) = -h_min_val; 
end

% 定义zeta(a)=g*(a)-a^2/2
zeta = @(a) interp1(a_vals,g_star_vals,a,'linear','extrap') - a.^2/2;

% 检验半二次分解 varphi(delta)=inf_a[(delta - a)^2/2 + zeta(a)]
delta_test = linspace(-3,3,100);
varphi_recons = zeros(size(delta_test));
for i=1:length(delta_test)
    delta_ = delta_test(i);
    Phi = @(a) ((delta_-a).^2)/2 + zeta(a);
    [~,Phi_min] = fminbnd(Phi,-5,5);
    varphi_recons(i) = Phi_min;
end

figure;
plot(delta_test,varphi(delta_test),'b','LineWidth',2); hold on;
plot(delta_test,varphi_recons,'r--','LineWidth',2);
xlabel('delta','Interpreter','none'); 
ylabel('varphi(delta)','Interpreter','none');
legend({'varphi(delta)','Half-quadratic decomposition'},'Interpreter','none','Location','best');
title('Half-quadratic decomposition check','Interpreter','none');

disp('Legendre transform and half-quadratic decomposition demonstrations completed.');

在半二次优化中引入勒让德变换

我们刚刚的思路非常美好，现在只需要分开优化就好了，但是现在我们有两个前置问题

• \varphi(\delta) = \inf_a \left[ \frac{1}{2} (\delta - a)^2 + \zeta(a) \right] 怎么构建的？

• \zeta(a) 怎么构建？

我们现在推导证明:

注意

证明

引入一个新的辅助函数 g(\delta) ，定义为：

g(\delta) = \frac{\delta^2}{2} - \varphi(\delta).

这里 g(\delta) 被设计为一个严格凸函数（二次项 \frac{\delta^2}{2} 保证了凸性）。

我们对 g(\delta) 应用勒让德变换 g^*(a) ：

代入 g(\delta) = \frac{\delta^2}{2} - \varphi(\delta) ，勒让德变换展开为：

将辅助函数 \zeta(a) 定义为：

代入 g^*(a) 的表达式，得：

\zeta(a) = \sup_{\delta \in \mathbb{R}} \left[ \varphi(\delta) - \frac{ (\delta - a)^2 }{2} \right]

这表明 \zeta(a) 是由 \varphi(\delta) 和二次项 \frac{ (\delta - a)^2 }{2} 的优化分解所定义的。

利用双重勒让德变换的性质 g = g^{**} 的性质，我们可以写出

结合 g(\delta) = \frac{\delta^2}{2} - \varphi(\delta) ，可以进一步推导出：

由上述方程，可以得到：

进一步等价为：

将 g^*(a) 的定义代入：

\varphi(\delta) = \frac{\delta^2}{2} + \inf_{a} \left[ \zeta(a) + \frac{a^2}{2} - a \delta \right]

重新整理：

\varphi(\delta) = \inf_{a} \left[ \frac{ (\delta - a)^2 }{2} + \zeta(a) \right]

这就得到了半二次分解的基本形式。

为了进一步分析辅助变量 a，考虑优化问题：

对优化准则求导：

解出最优 a = \bar{a}：

结合 \zeta^{\prime}(a) = g^{\prime}(a) ，可以进一步得到：

或简化为：

通过上述推导，我们得到：

1. 半二次分解的标准形式：

其中 \zeta(a) = g^*(a) - \frac{a^2}{2} 是辅助函数。

2. 最优辅助变量的表达式：

这个理论保证了对于任何给定的 \varphi(\delta)，我们都能通过构造辅助变量 a 来优化原始函数。

总结

原始优化问题的目标函数为：

为了解决非二次项 \varphi(x_p - x_q) ，引入辅助变量 a_{pq} ，将原始准则扩展为：

• a_{pq} 是辅助变量，用于解耦 x_p 和 x_q 。 \zeta(a_{pq}) 是通过勒让德变换定义的辅助函数。

算法策略：交替优化（Alternating Minimization）

(1) 对 \mathbf{x} 固定 \mathbf{a} 进行优化

在固定 \mathbf{a} 的情况下，优化目标函数变为关于 \mathbf{x} 的二次问题：

这是一个标准的二次优化问题，可以通过解析解（如线性代数方法）或数值方法高效求解。

(2) 对 \mathbf{a} 固定 \mathbf{x} 进行优化

在固定 \mathbf{x} 的情况下，优化目标函数变为关于 \mathbf{a} 的问题：

这个优化问题也可以通过显式公式解出，因为 \zeta(a) 是预定义的。

通过在这两个步骤之间交替迭代，逐步接近全局最优解。

• 变量的相互作用（Interacting Variables）：

  • 原始问题中的变量 x_p 和 x_q 存在耦合关系（通过 \varphi(x_p - x_q)）。
  • 扩展准则通过引入 a_{pq} ，解耦了变量 \mathbf{x} 和 \mathbf{a} ，从而简化了优化问题。

• 优化问题的本质：

  • 原始问题是非二次的，且变量相互作用；
  • 扩展后，尽管存在交互，但问题本质上是二次的，因此易于求解。

%% 半二次优化示例
% 注意：我们已定义 s 和 varphi，上述 s=0.5 也适用于此
% 新增phi_prime定义(在之前未定义，需新增)
phi_prime = @(delta) (abs(delta)<=s).*delta + (abs(delta)>s).*s.*sign(delta);

% 以下半二次优化1D信号示例

% 参数设置(对于优化问题)
N = 100;            % 信号长度
mu = 1;           % 正则化参数
maxIter = 50;       % 最大迭代次数

% 生成观测数据 y (用 x_true 加噪声)
x_true = sin(linspace(0,2*pi,N))'; % 真值
noise = 0.1 * randn(N,1); 
y = x_true + noise; 

% 定义算子H为单位映射，这里H = I
H = eye(N);

% 定义初始值
x = y;              % 初始解
a = zeros(N-1,1);   % 辅助变量

% 构造差分矩阵 R (N-1 x N)
R = spdiags([ones(N-1,1), -ones(N-1,1)], [0,1], N-1, N);

% 系数矩阵A_x = 2I + mu R'R
A_x = 2*speye(N) + mu*(R'*R);

% 迭代求解
for iter = 1:maxIter
    % Step 1: 固定 a 更新 x
    rhs = 2*y + mu*R'*a;
    x = A_x\rhs; 
    
    % Step 2: 固定 x 更新 a
    delta = R*x; 
    a = delta - phi_prime(delta);
    
    % 显示进度(每10次迭代显示一次)
    if mod(iter,10)==0
        phi_val = zeros(N-1,1);
        for k=1:(N-1)
            d = delta(k);
            if abs(d)<=s
                phi_val(k) = d^2/2;
            else
                phi_val(k) = s*abs(d)-s^2/2;
            end
        end
        J_val = norm(y - x)^2 + mu*sum(phi_val);
        fprintf('Iter %d, J = %f\n', iter, J_val);
    end
end

% 结果展示
figure; 
plot(x_true, 'k-', 'LineWidth',2); hold on;
plot(y, 'b:', 'LineWidth',1); 
plot(x, 'r--', 'LineWidth',2);
legend('True x','Noisy y','Reconstructed x','Interpreter','none');
xlabel('Index','Interpreter','none');
ylabel('Amplitude','Interpreter','none');
title('Half-Quadratic Optimization with Huber Regularization','Interpreter','none');
grid on;

半二次优化和相关问题中变量更新的可能方法

1. 直接计算（Direct Calculus）

这类方法通过解析表达式或直接矩阵操作更新变量，常用技术包括：

• 闭式解（Compact or Closed Form）：当问题有解析解时，可以通过直接计算得到。例如，二次优化问题可以通过矩阵代数方法解决。
• 矩阵求逆（Matrix Inversion）：对于线性系统，可以通过求解方程 \mathbf{A} \mathbf{x} = \mathbf{b} 来更新 \mathbf{x}，如通过矩阵求逆或其他方法。

适用场景：

• 问题规模较小，或系统稀疏，矩阵求逆的成本可接受。

2. 线性系统的算法（Algorithms for Linear Systems）

这部分涵盖了经典的线性系统求解算法，适用于优化问题中涉及的线性方程组：

• 高斯消元法（Gauss）和高斯-约当法（Gauss-Jordan）：通过消元法求解线性系统。
• 代入法（Substitution）：在某些特定的线性系统中，可以逐步代入解。
• 三角分解（Triangularisation）：将矩阵分解为上下三角矩阵以加速求解。

适用场景：

• 当优化目标是二次形式，且涉及线性方程组时。

3. 数值优化（Numerical Optimization）

针对非线性或复杂目标函数，使用数值优化技术逐步更新变量：

• 梯度下降（Gradient Descent）及其变种：
  • 标准梯度下降法通过计算梯度逐步逼近最优解；
  • 可以结合动量、学习率调整等技术加速收敛。
• 逐像素更新（Pixel-Wise Update）：
  • 在图像处理问题中，逐像素优化是常用策略，尤其是涉及稀疏正则化的场景。

适用场景：

• 问题非线性或不可微，梯度信息可用但解析解不可得。

4. 对角化（Diagonalization）

通过对矩阵的对角化或循环近似来加速计算：

• 循环矩阵近似（Circulant Approximation）：在某些场景下，可以将矩阵近似为循环矩阵，从而通过快速傅里叶变换（FFT）简化运算。
• 通过快速傅里叶变换（Diagonalization by FFT）：对角化操作可以通过 FFT 快速实现，极大加速求解过程。

适用场景：

• 当系统是周期性或卷积形式，FFT 是高效的选择。

5. 特殊算法（Special Algorithms for 1D Cases）

针对一维情况，可以利用特别设计的算法：

• 递归最小二乘法（Recursive Least Squares, RLS）：
  • 适用于时间序列数据或动态系统建模。
• 卡尔曼滤波或平滑（Kalman Smoother/Filter）：
  • 经典算法，用于估计动态系统的状态，可以扩展到快速变种以适应实时应用。

适用场景：

• 动态系统、一维优化问题，尤其是涉及时间序列数据的场景。

辅助变量的更新策略 或者说 辅助变量的分离性

扩展的准则为：

这表明该问题：

• 非二次：因为 \zeta(a_{pq}) 的形式可能不是二次的；
• 可分离：由于各 a_{pq} 之间无交互，因此可以并行计算 a_{pq}。

2. 第二个优化优势：增强特性

通过对辅助变量的分离优化，得到以下特性：

• 并行计算（Parallel Computation）：每个 a_{pq} 可以独立更新，无需遍历或循环。
• 显式更新（Explicit Updates）：辅助变量的更新可以通过解析公式完成，无需进一步的内层迭代。

这使得优化过程高效且适合并行处理硬件，如 GPU。

3. 辅助变量的更新公式

通过优化准则对 a_{pq} 求导，得到更新公式：

其中：

• \delta_{pq} = x_p - x_q 表示当前变量 x_p 和 x_q 的差异；
• \varphi^{\prime}(\delta_{pq}) 是正则化函数 \varphi(\delta_{pq}) 的导数。

Huber 函数特例

对于 Huber 函数：

其导数为：

对应的辅助变量更新为：

总结与扩展

• 图像反卷积（Image Deconvolution）：

  主要目标是通过正则化方法恢复原始图像。

• 边缘保持与非二次正则化（Edge Preserving and Non-Quadratic Penalties）：

  • 包括灰度梯度（如边缘检测）的惩罚；
  • 支持凸或部分非凸的正则化。

• 数值计算与半二次方法（Numerical Computations: Half-Quadratic Approach）：

  • 迭代优化策略结合分离性质；
  • 使用循环矩阵近似（Circulant Approximation）或快速傅里叶变换（FFT）加速计算。

下一步研究方向包括：

• 加入约束条件以提高图像分辨率；
• 自动估计超参数（正则化参数）或设备参数。