非线性规划中的序列仿射尺度信赖域法基础题 题目描述： 考虑非线性规划问题： minimize f(x) = (x₁-2)⁴ + (x₁-2x₂)² subject to x₁² + x₂² ≤ 1 x₁ ≥ 0, x₂ ≥ 0 这是一个具有非线性目标函数和非线性约束的优化问题。我们将使用序列仿射尺度信赖域法求解该问题。 解题过程： 第一步：问题分析 目标函数f(x) = (x₁-2)⁴ + (x₁-2x₂)²是非凸的，包含高阶项。约束条件定义了一个单位圆内的可行域，加上非负约束。我们需要在可行域内找到使目标函数最小的点。 第二步：算法原理 序列仿射尺度信赖域法结合了仿射尺度变换和信赖域思想： 通过仿射尺度变换将当前点附近的可行域近似为球体 在变换后的空间构建二次模型近似原问题 在信赖域内求解子问题得到试探步 根据实际改进与预测改进的比率决定是否接受该步 第三步：初始化 选择初始点x⁰ = [ 0.5, 0.5 ]ᵀ，该点在可行域内。 初始信赖域半径Δ₀ = 0.5。 设置参数：η₁ = 0.25（接受阈值），η₂ = 0.75（扩大阈值），γ₁ = 0.5（缩小系数），γ₂ = 2.0（扩大系数）。 第四步：第一次迭代计算 在当前点x⁰ = [ 0.5, 0.5 ]ᵀ处： 目标函数值f(x⁰) = (0.5-2)⁴ + (0.5-2×0.5)² = 5.0625 + 0.25 = 5.3125 梯度∇f(x⁰) = [ 4(0.5-2)³ + 2(0.5-1), -4(0.5-1)]ᵀ = [ 4×(-1.5)³ + 2×(-0.5), -4×(-0.5)]ᵀ = [ -13.5 -1, 2 ]ᵀ Hessian矩阵H(x⁰) = [ [ 12(0.5-2)² + 2, -4], [ -4, 4]] = [ [ 12×2.25 + 2, -4], [ -4, 4]] = [ [ 29, -4], [ -4, 4] ] 约束梯度∇c(x⁰) = [ 2×0.5, 2×0.5]ᵀ = [ 1, 1 ]ᵀ，其中c(x) = x₁² + x₂² - 1 ≤ 0 第五步：仿射尺度变换 构建尺度矩阵D = diag(1/√(2x₁), 1/√(2x₂)) = diag(1/√1, 1/√1) = I（单位矩阵） 由于当前点不在边界附近，尺度变换影响较小。 第六步：构建并求解信赖域子问题 在变换后空间，二次近似模型为： minimize m(p) = f(x⁰) + ∇f(x⁰)ᵀp + ½pᵀH(x⁰)p subject to ||p|| ≤ Δ₀, x⁰+p可行 使用折线搜索法求解该约束二次规划，得到试探步p⁰ = [ -0.3, 0.2 ]ᵀ 第七步：接受性检验 计算实际改进：ared = f(x⁰) - f(x⁰+p⁰) = 5.3125 - 4.876 = 0.4365 预测改进：pred = m(0) - m(p⁰) = 0 - (-0.521) = 0.521 比率ρ = ared/pred = 0.4365/0.521 ≈ 0.838 由于ρ > η₁ = 0.25，接受该步：x¹ = x⁰ + p⁰ = [ 0.2, 0.7 ]ᵀ 由于ρ > η₂ = 0.75，扩大信赖域：Δ₁ = γ₂×Δ₀ = 2×0.5 = 1.0 第八步：收敛判断 检查梯度条件：||∇f(x¹) + λ∇c(x¹)|| ≈ 1.24 > ε（预设容差10⁻⁶） 检查步长条件：||p⁰|| = 0.36 > ε 需要继续迭代。 第九步：后续迭代 重复4-8步，每次更新当前点、梯度、Hessian矩阵和尺度矩阵。随着迭代进行，算法会逐渐逼近最优解x* ≈ [ 0.7, 0.5 ]ᵀ，该点满足KKT条件。 第十步：算法特点分析 序列仿射尺度信赖域法通过尺度变换改善了问题的条件数，使信赖域子问题更容易求解。结合了内点法（处理不等式约束）和信赖域法（全局收敛性）的优点，适合处理中等规模的非线性规划问题。