非线性规划中的信赖域反射-序列线性化混合算法基础题 题目描述 考虑非线性规划问题： 最小化 f(x) = (x₁ - 2)² + (x₂ - 1)² 约束条件为： c₁(x) = x₁² - x₂ ≤ 0 c₂(x) = x₁ + x₂ - 2 ≤ 0 其中 x = [ x₁, x₂ ]ᵀ 是决策变量。 我们的目标是在满足约束条件的前提下，找到使目标函数 f(x) 最小的 x 值。这个问题结合了非线性目标函数和非线性约束，适合应用信赖域反射与序列线性化相结合的混合算法。 解题过程 第一步：算法原理介绍 信赖域反射-序列线性化混合算法结合了两种方法的优点： 序列线性化 ：在每次迭代中，将非线性约束和目标函数在当前点进行一阶泰勒展开，转化为线性约束和线性/二次目标函数的子问题。 信赖域反射 ：对线性化后的子问题求解时，引入信赖域约束，限制搜索步长，确保线性近似的有效性。当遇到约束边界时，采用反射策略调整搜索方向。 这种混合策略既能处理非线性约束，又能保证迭代的稳定性和收敛性。 第二步：初始化 选择初始点 x⁽⁰⁾ = [ 0, 0 ]ᵀ，该点满足约束条件（c₁(0,0) = 0 ≤ 0, c₂(0,0) = -2 ≤ 0）。 设定初始信赖域半径 Δ₀ = 0.5。 设定收敛容差 ε = 10⁻⁶。 迭代计数器 k = 0。 计算初始点的函数值： f(x⁽⁰⁾) = (0-2)² + (0-1)² = 4 + 1 = 5 约束值：c₁(x⁽⁰⁾) = 0, c₂(x⁽⁰⁾) = -2。 第三步：第一次迭代 (k=0) 线性化模型构建 ： 在当前点 x⁽⁰⁾ = [ 0,0 ]ᵀ 处进行一阶泰勒展开。 目标函数梯度：∇f(x) = [ 2(x₁ - 2), 2(x₂ - 1)]ᵀ，所以 ∇f(x⁽⁰⁾) = [ -4, -2 ]ᵀ。 线性化目标函数为：f(x⁽⁰⁾) + ∇f(x⁽⁰⁾)ᵀp = 5 + [ -4, -2] · [ p₁, p₂ ] = 5 - 4p₁ - 2p₂。由于常数项不影响极小点位置，子问题可简化为最小化 -4p₁ - 2p₂。 约束梯度：∇c₁(x) = [ 2x₁, -1]ᵀ，所以 ∇c₁(x⁽⁰⁾) = [ 0, -1 ]ᵀ。 线性化约束 c₁：c₁(x⁽⁰⁾) + ∇c₁(x⁽⁰⁾)ᵀp = 0 + [ 0, -1] · [ p₁, p₂ ] = -p₂ ≤ 0。 约束梯度：∇c₂(x) = [ 1, 1 ]ᵀ。 线性化约束 c₂：c₂(x⁽⁰⁾) + ∇c₂(x⁽⁰⁾)ᵀp = -2 + [ 1, 1] · [ p₁, p₂ ] = -2 + p₁ + p₂ ≤ 0。 构建并求解信赖域子问题 ： 子问题是求解步长 p = [ p₁, p₂ ]ᵀ： 最小化 q(p) = -4p₁ - 2p₂ 约束条件： l₁(p) = -p₂ ≤ 0 l₂(p) = p₁ + p₂ - 2 ≤ 0 ||p||₂ ≤ Δ₀ = 0.5 (信赖域约束) 由于目标函数是线性的，且极小化负梯度方向，最优解通常出现在信赖域边界上。同时考虑线性约束。 约束 l₁(p) 要求 p₂ ≥ 0。 约束 l₂(p) 要求 p₁ + p₂ ≤ 2（在当前点很宽松，因为初始值远小于2）。 沿着负梯度方向 d = -∇f(x⁽⁰⁾) = [ 4, 2]ᵀ 的单位向量是 [ 4/√20, 2/√20] ≈ [ 0.894, 0.447 ]ᵀ。 在信赖域边界上的点为 p = Δ₀ * d = 0.5 * [ 0.894, 0.447]ᵀ ≈ [ 0.447, 0.224 ]ᵀ。 检查约束：l₁(p): -0.224 ≤ 0 (满足)；l₂(p): 0.447+0.224-2 = -1.329 ≤ 0 (满足)。 所以，接受该步长 p⁽⁰⁾ = [ 0.447, 0.224 ]ᵀ。 计算新点并评估 ： 新点 x⁽¹⁾ = x⁽⁰⁾ + p⁽⁰⁾ = [ 0, 0]ᵀ + [ 0.447, 0.224]ᵀ = [ 0.447, 0.224 ]ᵀ。 计算新点函数值：f(x⁽¹⁾) = (0.447-2)² + (0.224-1)² ≈ 2.41 + 0.60 = 3.01。 实际函数减少量：Ared = f(x⁽⁰⁾) - f(x⁽¹⁾) = 5 - 3.01 = 1.99。 预测减少量（基于线性模型）：Pred = q(0) - q(p⁽⁰⁾) = 0 - (-4 0.447 -2 0.224) = 0 - (-1.788 - 0.448) = 2.236。 更新信赖域半径 ： 计算比值 ρ = Ared / Pred = 1.99 / 2.236 ≈ 0.89。 由于 ρ > 0.75（这是一个常见的阈值，表示近似质量很好），我们扩大信赖域半径。例如，Δ₁ = 2 * Δ₀ = 1.0。 第四步：第二次迭代 (k=1) 在新的当前点 x⁽¹⁾ = [ 0.447, 0.224]ᵀ 处重新线性化 。 梯度：∇f(x⁽¹⁾) = [ 2(0.447-2), 2(0.224-1)] ≈ [ -3.106, -1.552 ]ᵀ。 线性化目标：-3.106p₁ - 1.552p₂。 约束梯度：∇c₁(x⁽¹⁾) = [ 2* 0.447, -1]ᵀ ≈ [ 0.894, -1 ]ᵀ。 线性化约束 c₁：c₁(x⁽¹⁾) + ∇c₁(x⁽¹⁾)ᵀp = (0.447² - 0.224) + [ 0.894, -1 ]·p ≈ (0.200 - 0.224) + 0.894p₁ - p₂ = -0.024 + 0.894p₁ - p₂ ≤ 0。 约束梯度：∇c₂(x) 不变，为 [ 1,1 ]ᵀ。 线性化约束 c₂：c₂(x⁽¹⁾) + ∇c₂(x⁽¹⁾)ᵀp = (0.447+0.224-2) + p₁ + p₂ = -1.329 + p₁ + p₂ ≤ 0。 构建并求解新的信赖域子问题 (Δ₁=1.0) ： 最小化 q(p) = -3.106p₁ - 1.552p₂ 约束条件： l₁(p) = 0.894p₁ - p₂ - 0.024 ≤ 0 l₂(p) = p₁ + p₂ - 1.329 ≤ 0 ||p||₂ ≤ 1.0 同样，沿负梯度方向 d = -∇f(x⁽¹⁾) = [ 3.106, 1.552]ᵀ，单位向量约为 [ 0.894, 0.447 ]ᵀ。 在信赖域边界上的点 p = 1.0 * [ 0.894, 0.447]ᵀ = [ 0.894, 0.447 ]ᵀ。 检查约束：l₁(p): 0.894* 0.894 - 0.447 - 0.024 ≈ 0.799 - 0.447 - 0.024 = 0.328 > 0 (违反！) l₂(p): 0.894+0.447-1.329 = 1.341-1.329=0.012 > 0 (轻微违反！) 应用反射策略（关键步骤） ： 由于线性化约束被违反，不能直接接受该步长。反射策略会调整搜索方向，使其在满足线性化约束的可行域内移动。 一种简化处理是求解这个带线性约束和信赖域约束的线性规划问题（或二次规划问题，如果目标函数是二次的），找到满足所有约束且使目标函数最小的 p。 对于这个简单问题，可以直观判断。约束 l₁ 是主要矛盾。我们需要找到一个方向，在满足 ||p||₂ ≤ 1.0 的前提下，尽可能沿着投影梯度方向（即梯度在可行域上的投影）移动。 通过数值计算（例如使用二次规划求解器），可以求得一个近似解，例如 p⁽¹⁾ ≈ [ 0.6, 0.3]ᵀ。验证约束：l₁(p): 0.894 0.6 - 0.3 -0.024=0.536-0.324=0.212>0? 计算有误，重新计算：0.894 0.6=0.536, 0.536 - 0.3 = 0.236, 0.236 - 0.024 = 0.212 > 0。仍然违反。需要更精确的求解。 为了简化讲解，我们假设通过有效集法或内点法求解该二次规划子问题，得到了一个满足约束的可行解 p⁽¹⁾。 接受新点并更新 ： 假设求得 p⁽¹⁾ = [ 0.5, 0.2 ]ᵀ (此值为示意，需严格求解子问题)。 x⁽²⁾ = x⁽¹⁾ + p⁽¹⁾ = [ 0.447, 0.224] + [ 0.5, 0.2] = [ 0.947, 0.424 ]ᵀ。 计算 f(x⁽²⁾) = (0.947-2)² + (0.424-1)² ≈ 1.11 + 0.33 = 1.44。 计算 ρ 比值，并根据其值决定是否接受该点以及如何调整信赖域半径 Δ。 第五步：后续迭代与收敛 重复上述步骤： 在当前点 x⁽ᵏ⁾ 线性化目标函数和约束。 在信赖域约束 ||p|| ≤ Δₖ 下，求解线性化子问题（可能需用反射策略处理约束冲突）。 计算新点 x⁽ᵏ⁺¹⁾ = x⁽ᵏ⁾ + p⁽ᵏ⁾。 比较实际下降量与预测下降量，计算比值 ρₖ。 根据 ρₖ 调整信赖域半径 Δₖ₊₁： 如果 ρₖ 很大（如 >0.75），说明近似效果好，下次迭代可以增大信赖域。 如果 ρₖ 很小（如 <0.25），说明近似效果差，下次迭代应缩小信赖域。 如果 ρₖ 为负或非常小，可能拒绝该步长，即 x⁽ᵏ⁺¹⁾ = x⁽ᵏ⁾，并缩小信赖域。 检查收敛条件：例如，梯度范数 ||∇L(x⁽ᵏ⁾)||（其中 L 是拉格朗日函数）是否小于容差 ε，或者迭代点变化 ||x⁽ᵏ⁺¹⁾ - x⁽ᵏ⁾|| 是否足够小。 最终，算法将收敛到原问题的一个局部最优解。对于本例题，最优解在约束边界 x₁² - x₂ = 0 和 x₁ + x₂ = 2 的交点附近，通过求解可得最优解约为 x* ≈ [ 1, 1]ᵀ，此时 f(x* ) = 2。 总结 信赖域反射-序列线性化混合算法通过迭代地构建并求解线性近似子问题，结合信赖域策略控制步长，并用反射机制处理约束边界，有效地求解了带有非线性约束的非线性规划问题。其核心在于动态调整信赖域半径以保证近似的准确性，从而稳步逼近最优解。