近似点梯度法(Proximal Gradient Method)基础题
字数 846 2025-11-07 22:14:38

近似点梯度法(Proximal Gradient Method)基础题

题目描述：
考虑非线性规划问题：min f(x) = (x₁-2)⁴ + (x₂-3)² + ∥x∥₁，其中∥x∥₁ = |x₁| + |x₂| 是非光滑的L1范数。请使用近似点梯度法求解该问题。

解题过程：

  1. 问题分析
    目标函数f(x)可分解为光滑部分g(x) = (x₁-2)⁴ + (x₂-3)²和非光滑部分h(x) = ∥x∥₁。近似点梯度法适用于此类复合优化问题。

  2. 算法原理
    近似点梯度法的迭代格式为：
    xᵏ⁺¹ = prox_{αh}(xᵏ - α∇g(xᵏ))
    其中prox是近似点算子，α是步长。

  3. 梯度计算
    光滑部分梯度：∇g(x) = [4(x₁-2)³, 2(x₂-3)]

  4. 近似点算子求解
    对于h(x) = ∥x∥₁，近似点算子有闭式解（软阈值算子）：
    prox_{αh}(z) = sign(z) ⊙ max(|z| - α, 0)
    其中⊙表示逐元素乘法。

  5. 具体迭代步骤
    (1) 选择初始点x⁰ = [0,0]，步长α = 0.1
    (2) 计算梯度：∇g(x⁰) = [4(0-2)³, 2(0-3)] = [-32, -6]
    (3) 中间点：z = x⁰ - α∇g(x⁰) = [0,0] - 0.1×[-32,-6] = [3.2, 0.6]
    (4) 近似点映射：x¹ = sign([3.2,0.6]) ⊙ max([|3.2|,|0.6|] - 0.1, 0)
    = [1,1] ⊙ max([3.2,0.6] - 0.1, 0) = [3.1, 0.5]

  6. 收敛判断
    重复上述步骤直到∥xᵏ⁺¹ - xᵏ∥ < ε（如ε=10⁻⁶）
    经过迭代，算法收敛到最优解x* ≈ [1.8, 0]，目标函数值f(x*) ≈ 0.2

  7. 算法特点

  • 适用于光滑+非光滑的复合优化
  • 收敛速度与梯度法相同（O(1/k)）
  • 可通过加速技术（如FISTA）提升收敛速度
近似点梯度法(Proximal Gradient Method)基础题 题目描述： 考虑非线性规划问题：min f(x) = (x₁-2)⁴ + (x₂-3)² + ∥x∥₁，其中∥x∥₁ = |x₁| + |x₂| 是非光滑的L1范数。请使用近似点梯度法求解该问题。 解题过程： 问题分析 目标函数f(x)可分解为光滑部分g(x) = (x₁-2)⁴ + (x₂-3)²和非光滑部分h(x) = ∥x∥₁。近似点梯度法适用于此类复合优化问题。 算法原理 近似点梯度法的迭代格式为： xᵏ⁺¹ = prox_ {αh}(xᵏ - α∇g(xᵏ)) 其中prox是近似点算子，α是步长。 梯度计算 光滑部分梯度：∇g(x) = [ 4(x₁-2)³, 2(x₂-3) ] 近似点算子求解 对于h(x) = ∥x∥₁，近似点算子有闭式解（软阈值算子）： prox_ {αh}(z) = sign(z) ⊙ max(|z| - α, 0) 其中⊙表示逐元素乘法。 具体迭代步骤 (1) 选择初始点x⁰ = [ 0,0 ]，步长α = 0.1 (2) 计算梯度：∇g(x⁰) = [ 4(0-2)³, 2(0-3)] = [ -32, -6 ] (3) 中间点：z = x⁰ - α∇g(x⁰) = [ 0,0] - 0.1×[ -32,-6] = [ 3.2, 0.6 ] (4) 近似点映射：x¹ = sign([ 3.2,0.6]) ⊙ max([ |3.2|,|0.6| ] - 0.1, 0) = [ 1,1] ⊙ max([ 3.2,0.6] - 0.1, 0) = [ 3.1, 0.5 ] 收敛判断 重复上述步骤直到∥xᵏ⁺¹ - xᵏ∥ < ε（如ε=10⁻⁶） 经过迭代，算法收敛到最优解x* ≈ [ 1.8, 0]，目标函数值f(x* ) ≈ 0.2 算法特点 适用于光滑+非光滑的复合优化 收敛速度与梯度法相同（O(1/k)） 可通过加速技术（如FISTA）提升收敛速度