非线性规划中的自适应步长梯度投影法基础题 题目描述 考虑非线性规划问题： 最小化 f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² 满足约束条件： g₁(x) = x₁² - x₂ ≤ 0 g₂(x) = x₁² + x₂² - 2 ≤ 0 初始点 x⁰ = [ 0, 1 ]ᵀ 本题要求使用自适应步长梯度投影法求解该约束优化问题。该算法结合梯度下降思想与投影操作，通过自适应调整步长来保证收敛性。 基本概念 梯度投影法的核心思想是：在每次迭代中，先沿目标函数负梯度方向移动，然后将得到的新点投影回可行域。自适应步长机制通过线性搜索自动确定合适的步长。 解题步骤 验证初始点可行性 计算约束函数值： g₁(x⁰) = 0² - 1 = -1 ≤ 0 ✓ g₂(x⁰) = 0² + 1² - 2 = -1 ≤ 0 ✓ 初始点满足所有约束条件。 计算梯度信息 目标函数梯度：∇f(x) = [ 4(x₁ - 2)³ + 2(x₁ - 2x₂), -4(x₁ - 2x₂) ]ᵀ 在x⁰处：∇f(x⁰) = [ 4(0-2)³ + 2(0-2), -4(0-2)]ᵀ = [ 4(-8) + 2(-2), 8]ᵀ = [ -32 -4, 8]ᵀ = [ -36, 8 ]ᵀ 确定有效约束集 计算约束函数值及梯度： ∇g₁(x) = [ 2x₁, -1]ᵀ，在x⁰处为[ 0, -1 ]ᵀ ∇g₂(x) = [ 2x₁, 2x₂]ᵀ，在x⁰处为[ 0, 2 ]ᵀ 由于g₁(x⁰) = -1 < 0，g₂(x⁰) = -1 < 0，所有约束都不紧，有效约束集为空。 第一次迭代（k=0） 投影矩阵P = I（单位矩阵，因无有效约束） 搜索方向d⁰ = -P∇f(x⁰) = -[ 1,0;0,1][ -36,8]ᵀ = [ 36, -8 ]ᵀ 自适应步长选择 使用Armijo条件进行线性搜索： 令α₀ = 1，ρ = 0.5，c = 0.1 检查f(x⁰ + α₀d⁰) ≤ f(x⁰) + cα₀∇f(x⁰)ᵀd⁰ 计算右端：f(x⁰) = (0-2)⁴ + (0-2)² = 16 + 4 = 20 ∇f(x⁰)ᵀd⁰ = [ -36,8]·[ 36,-8 ] = -1296 - 64 = -1360 右端 = 20 + 0.1×1×(-1360) = 20 - 136 = -116 计算x¹ = x⁰ + α₀d⁰ = [ 0,1]ᵀ + [ 36,-8]ᵀ = [ 36,-7 ]ᵀ 但该点不可行（g₂(36,-7) = 1296+49-2=1343>0），需要投影。 投影到可行域 将x¹投影到可行域： 求解最小化||x - [ 36,-7 ]ᵀ||²，满足g₁(x)≤0，g₂(x)≤0 通过数值方法（如二次规划）求得投影点x̂¹ ≈ [ 1.0, 1.0 ]ᵀ 步长调整和接受条件 计算实际下降量：Δf = f(x̂¹) - f(x⁰) = [ (1-2)⁴+(1-2)²] - 20 = [ 1+1 ] - 20 = -18 预测下降量：∇f(x⁰)ᵀ(x̂¹ - x⁰) ≈ [ -36,8]·[ 1,-0 ] = -36 若Δf < 0.1×(-36) = -3.6，接受该点。 由于-18 < -3.6，接受x¹ = [ 1.0,1.0 ]ᵀ 第二次迭代（k=1） 在x¹ = [ 1.0,1.0 ]ᵀ处： ∇f(x¹) = [ 4(1-2)³+2(1-2), -4(1-2)] = [ 4(-1)+2(-1), 4] = [ -6,4 ]ᵀ 约束情况：g₁(x¹)=1-1=0（紧约束），g₂(x¹)=1+1-2=0（紧约束） 投影矩阵计算 有效约束梯度：∇g₁(x¹)=[ 2, -1]ᵀ，∇g₂(x¹)=[ 2, 2 ]ᵀ 构造活动约束梯度矩阵A = [ 2,-1; 2,2 ] 投影矩阵P = I - Aᵀ(AAᵀ)⁻¹A 经计算P = [ 0,0; 0,0 ]（在可行域边界时投影矩阵为零） 收敛判断 由于投影矩阵为零，且当前点满足一阶最优性条件（梯度可表示为约束梯度的线性组合），算法终止。 最终结果 最优解x* ≈ [ 1.0, 1.0]ᵀ，最优值f(x* ) = 2 该点满足KKT条件，为局部最优解。