非线性规划中的序列仿射尺度信赖域反射混合算法基础题 题目描述 考虑非线性规划问题： minimize f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² subject to x₁² + x₂² ≤ 1 x₁ ≥ 0, x₂ ≥ 0 该问题包含非线性目标函数和非线性约束。我们将使用序列仿射尺度信赖域反射混合算法求解，该算法结合了仿射尺度变换、信赖域策略和反射技术来处理边界约束。 算法原理 这个混合算法的核心思想是： 通过仿射尺度变换改善问题条件 使用信赖域方法控制步长 采用反射技术处理边界约束 序列求解一系列变换后的子问题 解题过程 步骤1：问题重构与标准化 首先将问题转化为标准形式： 目标函数：f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² 不等式约束：g₁(x) = x₁² + x₂² - 1 ≤ 0 边界约束：x₁ ≥ 0, x₂ ≥ 0 引入松弛变量将不等式约束转化为等式约束： g₁(x) + s₁² = 0，其中s₁为松弛变量 步骤2：初始点选择 选择可行初始点x⁰ = [ 0.5, 0.5 ]ᵀ 计算初始函数值：f(x⁰) = (0.5-2)⁴ + (0.5-1)² = 5.0625 + 0.25 = 5.3125 验证可行性：0.5² + 0.5² = 0.5 ≤ 1，满足约束 步骤3：仿射尺度变换 在当前点xᵏ处，构建尺度矩阵Dᵏ： Dᵏ = diag(1/|x₁ᵏ|, 1/|x₂ᵏ|) ≈ diag(1/0.5, 1/0.5) = diag(2, 2) 定义变换变量：y = Dᵏ(x - xᵏ) 变换后的问题在y空间求解，改善了问题的条件数 步骤4：信赖域子问题构建 在当前迭代点，构建二次近似模型： mᵏ(p) = f(xᵏ) + ∇f(xᵏ)ᵀp + ½pᵀBᵏp 其中p为试探步长，Bᵏ为Hessian近似矩阵 计算梯度： ∇f(x) = [ 4(x₁-2)³ + 2(x₁-2x₂), -4(x₁-2x₂) ]ᵀ 在x⁰处：∇f(x⁰) = [ 4(-1.5)³ + 2(-0.5), -4(-0.5)] = [ -13.5 -1, 2]ᵀ = [ -14.5, 2 ]ᵀ 步骤5：边界约束处理 当试探点接近边界时，采用反射技术： 如果xᵢ + pᵢ < 0，则令pᵢ = -xᵢ - α(xᵢ + pᵢ)，其中α为反射系数 这保证迭代点保持在可行域内 步骤6：子问题求解 求解信赖域子问题： minimize mᵏ(p) = -14.5p₁ + 2p₂ + ½pᵀBᵏp subject to ||p|| ≤ Δᵏ ||Dᵏp|| ≤ Δᵏ（考虑尺度变换） 使用折线算法或狗腿法求解该二次规划问题 步骤7：接受性检验 计算实际下降量：Δf_ actual = f(xᵏ) - f(xᵏ + p) 预测下降量：Δf_ pred = mᵏ(0) - mᵏ(p) 比值：ρ = Δf_ actual / Δf_ pred 如果ρ > 0.1，接受该步长：xᵏ⁺¹ = xᵏ + p 否则拒绝，缩小信赖域半径：Δᵏ⁺¹ = 0.5Δᵏ 步骤8：矩阵更新 采用BFGS公式更新Hessian近似： Bᵏ⁺¹ = Bᵏ + (y yᵀ)/(yᵀs) - (Bᵏs sᵀBᵏ)/(sᵀBᵏs) 其中s = xᵏ⁺¹ - xᵏ，y = ∇f(xᵏ⁺¹) - ∇f(xᵏ) 步骤9：收敛判断 检查收敛条件： ||∇f(xᵏ)|| ≤ ε₁（梯度足够小） ||xᵏ - xᵏ⁻¹|| ≤ ε₂（迭代点变化小） |f(xᵏ) - f(xᵏ⁻¹)| ≤ ε₃（函数值变化小） 迭代过程示例 经过数次迭代后，算法收敛到近似最优解： x* ≈ [ 0.5, 0.5 ]ᵀ（在边界约束下） f(x* ) ≈ 5.3125 验证约束：0.5² + 0.5² = 0.5 ≤ 1，满足所有约束 算法特点 仿射尺度变换改善问题条件数 信赖域机制保证全局收敛 反射技术有效处理边界约束 序列求解确保收敛到局部最优解 该混合算法特别适用于中等规模的非线性规划问题，能够有效处理非凸目标函数和非线性约束。