近似梯度法在非光滑优化中的应用进阶题 题目描述 考虑以下非光滑优化问题： 最小化 f(x) = |x₁ - 1| + |x₂ - 2| + max(0, x₁² + x₂² - 4) 其中 x = (x₁, x₂) ∈ R² 这是一个典型的非光滑优化问题，目标函数包含绝对值项和最大值项，在特定点不可微。我们需要使用近似梯度法来求解该问题。 解题过程 第一步：理解问题特性 目标函数f(x)由三部分组成： |x₁ - 1| - 在x₁=1处不可微 |x₂ - 2| - 在x₂=2处不可微 max(0, x₁² + x₂² - 4) - 在x₁² + x₂² = 4处不可微 这些不可微点构成了问题的"扭结"点，传统梯度法无法直接应用。 第二步：近似梯度的概念 对于非光滑函数，我们使用次梯度概念。函数f在点x的次梯度集合∂f(x)包含所有满足以下条件的向量g： f(y) ≥ f(x) + gᵀ(y - x) 对所有y成立 对于我们的函数： |xᵢ - a|的次梯度：当xᵢ > a时为1，当xᵢ < a时为-1，当xᵢ = a时为[ -1,1 ]区间 max(0, h(x))的次梯度：当h(x) > 0时为∇h(x)，当h(x) < 0时为0，当h(x)=0时为[ 0,1 ]·∇h(x) 第三步：计算具体次梯度 对于f(x) = |x₁ - 1| + |x₂ - 2| + max(0, x₁² + x₂² - 4)： ∂|x₁ - 1| = {1} 如果 x₁ > 1 {-1} 如果 x₁ < 1 [ -1,1 ] 如果 x₁ = 1 ∂|x₂ - 2| = {1} 如果 x₂ > 2 {-1} 如果 x₂ < 2 [ -1,1 ] 如果 x₂ = 2 ∂max(0, x₁² + x₂² - 4) = {2x₁, 2x₂} 如果 x₁² + x₂² > 4 {0,0} 如果 x₁² + x₂² < 4 {α·2x₁, α·2x₂ | α ∈ [ 0,1 ]} 如果 x₁² + x₂² = 4 第四步：近似梯度法迭代格式 采用次梯度法进行迭代： xᵏ⁺¹ = xᵏ - αₖgᵏ 其中gᵏ ∈ ∂f(xᵏ)是f在xᵏ处的一个次梯度，αₖ > 0是步长。 我们采用可调节步长：αₖ = 1/(k+1) 第五步：选择初始点和迭代 设初始点x⁰ = (0,0)，α₀ = 1 第一次迭代(k=0)： x⁰ = (0,0)，f(x⁰) = |0-1| + |0-2| + max(0,0+0-4) = 1 + 2 + 0 = 3 计算次梯度： ∂|0-1| = {-1} (取g₁ = -1) ∂|0-2| = {-1} (取g₂ = -1) ∂max(0,0-4) = {0,0} (取g₃ = (0,0)) 总次梯度g⁰ = (-1,-1) + (0,0) = (-1,-1) x¹ = (0,0) - 1×(-1,-1) = (1,1) 第六步：继续迭代过程 第二次迭代(k=1)： x¹ = (1,1)，f(x¹) = |1-1| + |1-2| + max(0,1+1-4) = 0 + 1 + 0 = 1 α₁ = 1/2 计算次梯度： ∂|1-1| = [ -1,1 ] (取g₁ = 0) ∂|1-2| = {-1} (取g₂ = -1) ∂max(0,1+1-4) = {0,0} (取g₃ = (0,0)) 总次梯度g¹ = (0,-1) + (0,0) = (0,-1) x² = (1,1) - 0.5×(0,-1) = (1,1.5) 第七步：收敛性分析 继续迭代若干次后，序列会收敛到最优解附近。对于这个凸问题，次梯度法能保证收敛到最优值。 最优解分析：函数在圆x₁² + x₂² = 4内最小，最小值点应在(1,2)附近，因为这样可以最小化前两项。 第八步：算法改进 基本次梯度法收敛较慢，可以考虑： 动态步长调整 投影操作（如果约束） 捆绑法（bundle method）加速收敛 这种方法的核心思想是用广义的梯度概念（次梯度）来处理非光滑性，使梯度类方法能应用于更广泛的问题类别。