非线性规划中的序列二次规划-乘子法-积极集-过滤器-信赖域混合算法基础题
字数 2111 2025-11-06 12:40:15

非线性规划中的序列二次规划-乘子法-积极集-过滤器-信赖域混合算法基础题

题目描述
考虑非线性规划问题：
最小化 \(f(x) = (x_1 - 2)^2 + (x_2 - 1)^2\)
约束条件：
\(g_1(x) = x_1^2 - x_2 \leq 0\)
\(g_2(x) = x_1 + x_2 - 2 \leq 0\)
初始点 \(x^{(0)} = (0, 0)\)，要求使用序列二次规划（SQP）框架，结合乘子法处理约束、积极集识别有效约束、过滤器确保收敛性、信赖域控制步长，逐步求解该问题。

解题过程

  1. 算法框架概述

    • 混合算法核心：在SQP迭代中，每步构建二次规划（QP）子问题，用乘子法增强拉格朗日函数，积极集识别活动约束，过滤器判断是否接受新迭代点，信赖域限制步长范围。
    • 优势：乘子法改善约束处理，积极集降低计算量，过滤器避免罚参数调整，信赖域增强稳定性。

  2. 初始化参数

    • 设当前点 \(x^{(0)} = (0, 0)\)，乘子估计 \(\lambda^{(0)} = (0, 0)\)，信赖域半径 \(\Delta_0 = 0.5\)，过滤器为空集，容忍误差 \(\epsilon = 10^{-6}\)。
    • 计算初始目标值 \(f(x^{(0)}) = 4\)，约束违反度 \(\theta^{(0)} = \max(0, g_1(x^{(0)}), g_2(x^{(0)})) = 0\)（因 \(g_1(0,0)=0, g_2(0,0)=-2\)，违反度为0）。

  3. 构建QP子问题

    • 拉格朗日函数：\(L(x, \lambda) = f(x) + \lambda_1 g_1(x) + \lambda_2 g_2(x)\)。
    • 在当前点 \(x^{(k)}\)，QP子问题为：
      最小化 \(\nabla f(x^{(k)})^T d + \frac{1}{2} d^T B_k d\)
      约束：\(\nabla g_i(x^{(k)})^T d + g_i(x^{(k)}) \leq 0 \quad (i=1,2)\)，
      其中 \(d = x - x^{(k)}\)，\(B_k\) 为拉格朗日函数Hessian近似（初始用单位矩阵）。
    • 第0次迭代：
      \(\nabla f(0,0) = (-4, -2)\)，\(\nabla g_1(0,0) = (0, -1)\)，\(\nabla g_2(0,0) = (1, 1)\)，
      QP问题：最小化 \(-4d_1 - 2d_2 + \frac{1}{2} d^T I d\)，约束 \(-d_2 \leq 0\)（因 \(g_1=0\)），\(d_1 + d_2 - 2 \leq 0\)（因 \(g_2=-2\)）。

  4. 求解QP子问题（结合积极集与乘子法）

    • 识别积极约束：在 \(x^{(0)}\)，\(g_1\) 为等式约束（边界活动），\(g_2\) 为非活动约束。
    • 求解简化QP：仅保留活动约束 \(-d_2 \leq 0\)，得解 \(d^{(0)} = (4, 0)\)（无约束最小化二次函数结果）。
    • 乘子更新：解QP得乘子估计 \(\lambda^{(1)}\)，用于下一步Hessian修正。

  5. 过滤器与信赖域判断

    • 候选点 \(x_c = x^{(0)} + d^{(0)} = (4, 0)\)，计算 \(f(x_c) = 4\)，\(\theta(x_c) = \max(0, g_1(4,0)=16, g_2(4,0)=2) = 16\)。
    • 过滤器规则：若 \((f(x_c), \theta(x_c))\) 不被过滤集中点支配（即非劣解），则接受；否则缩小信赖域。
      • 此处 \(\theta\) 增大，需检查：若 \(f\) 或 \(\theta\) 下降足够，可接受。这里违反度大增，触发信赖域调整。
    • 缩小 \(\Delta_0\) 至 0.2，重新求解QP（限制 \(\|d\| \leq 0.2\)），得新步长 \(d^{(0)} = (0.2, 0)\)，候选点 \(x_c = (0.2, 0)\)。

  6. 迭代收敛

    • 重复步骤3-5，更新 \(x^{(k)}\)、乘子、过滤器集和信赖域半径。
    • 终止条件：步长 \(\|d^{(k)}\| < \epsilon\) 且约束违反度 \(\theta < \epsilon\)。
    • 最终逼近解 \(x^* \approx (1, 1)\)，对应 \(f^* = 1\)，约束满足（ \(g_1(1,1)=0, g_2(1,1)=0\)）。

关键点

  • 乘子法改善QP子问题的约束逼近精度。
  • 积极集减少有效约束数，提升计算效率。
  • 过滤器避免传统罚函数的参数敏感问题。
  • 信赖域确保迭代稳定性，尤其在非凸区域。
非线性规划中的序列二次规划-乘子法-积极集-过滤器-信赖域混合算法基础题 题目描述 考虑非线性规划问题： 最小化 \( f(x) = (x_ 1 - 2)^2 + (x_ 2 - 1)^2 \) 约束条件： \( g_ 1(x) = x_ 1^2 - x_ 2 \leq 0 \) \( g_ 2(x) = x_ 1 + x_ 2 - 2 \leq 0 \) 初始点 \( x^{(0)} = (0, 0) \)，要求使用序列二次规划（SQP）框架，结合乘子法处理约束、积极集识别有效约束、过滤器确保收敛性、信赖域控制步长，逐步求解该问题。 解题过程 算法框架概述 混合算法核心：在SQP迭代中，每步构建二次规划（QP）子问题，用乘子法增强拉格朗日函数，积极集识别活动约束，过滤器判断是否接受新迭代点，信赖域限制步长范围。 优势：乘子法改善约束处理，积极集降低计算量，过滤器避免罚参数调整，信赖域增强稳定性。 初始化参数 设当前点 \( x^{(0)} = (0, 0) \)，乘子估计 \( \lambda^{(0)} = (0, 0) \)，信赖域半径 \( \Delta_ 0 = 0.5 \)，过滤器为空集，容忍误差 \( \epsilon = 10^{-6} \)。 计算初始目标值 \( f(x^{(0)}) = 4 \)，约束违反度 \( \theta^{(0)} = \max(0, g_ 1(x^{(0)}), g_ 2(x^{(0)})) = 0 \)（因 \( g_ 1(0,0)=0, g_ 2(0,0)=-2 \)，违反度为0）。 构建QP子问题 拉格朗日函数：\( L(x, \lambda) = f(x) + \lambda_ 1 g_ 1(x) + \lambda_ 2 g_ 2(x) \)。 在当前点 \( x^{(k)} \)，QP子问题为： 最小化 \( \nabla f(x^{(k)})^T d + \frac{1}{2} d^T B_ k d \) 约束：\( \nabla g_ i(x^{(k)})^T d + g_ i(x^{(k)}) \leq 0 \quad (i=1,2) \)， 其中 \( d = x - x^{(k)} \)，\( B_ k \) 为拉格朗日函数Hessian近似（初始用单位矩阵）。 第0次迭代： \( \nabla f(0,0) = (-4, -2) \)，\( \nabla g_ 1(0,0) = (0, -1) \)，\( \nabla g_ 2(0,0) = (1, 1) \)， QP问题：最小化 \( -4d_ 1 - 2d_ 2 + \frac{1}{2} d^T I d \)，约束 \( -d_ 2 \leq 0 \)（因 \( g_ 1=0 \)），\( d_ 1 + d_ 2 - 2 \leq 0 \)（因 \( g_ 2=-2 \)）。 求解QP子问题（结合积极集与乘子法） 识别积极约束：在 \( x^{(0)} \)，\( g_ 1 \) 为等式约束（边界活动），\( g_ 2 \) 为非活动约束。 求解简化QP：仅保留活动约束 \( -d_ 2 \leq 0 \)，得解 \( d^{(0)} = (4, 0) \)（无约束最小化二次函数结果）。 乘子更新：解QP得乘子估计 \( \lambda^{(1)} \)，用于下一步Hessian修正。 过滤器与信赖域判断 候选点 \( x_ c = x^{(0)} + d^{(0)} = (4, 0) \)，计算 \( f(x_ c) = 4 \)，\( \theta(x_ c) = \max(0, g_ 1(4,0)=16, g_ 2(4,0)=2) = 16 \)。 过滤器规则：若 \( (f(x_ c), \theta(x_ c)) \) 不被过滤集中点支配（即非劣解），则接受；否则缩小信赖域。 此处 \( \theta \) 增大，需检查：若 \( f \) 或 \( \theta \) 下降足够，可接受。这里违反度大增，触发信赖域调整。 缩小 \( \Delta_ 0 \) 至 0.2，重新求解QP（限制 \( \|d\| \leq 0.2 \)），得新步长 \( d^{(0)} = (0.2, 0) \)，候选点 \( x_ c = (0.2, 0) \)。 迭代收敛 重复步骤3-5，更新 \( x^{(k)} \)、乘子、过滤器集和信赖域半径。 终止条件：步长 \( \|d^{(k)}\| < \epsilon \) 且约束违反度 \( \theta < \epsilon \)。 最终逼近解 \( x^* \approx (1, 1) \)，对应 \( f^* = 1 \)，约束满足（ \( g_ 1(1,1)=0, g_ 2(1,1)=0 \)）。 关键点 乘子法改善QP子问题的约束逼近精度。 积极集减少有效约束数，提升计算效率。 过滤器避免传统罚函数的参数敏感问题。 信赖域确保迭代稳定性，尤其在非凸区域。