非线性规划中的序列二次规划-积极集-乘子法-过滤器-信赖域-自适应屏障-代理模型-混合整数规划-梯度投影-交替方向乘子法-逐步凸逼近-动态隧道-填充函数-松弛变量-增广拉格朗日混合算法基础题

题目描述：考虑非线性规划问题：
minimize f(x) = (x₁ - 2)² + (x₂ - 1)²
subject to:
c₁(x) = x₁² - x₂ ≤ 0
c₂(x) = x₁ + x₂ - 2 ≤ 0
x ∈ ℤ² (整数约束)
其中 x = (x₁, x₂) 为决策变量。该问题包含非线性目标函数、非线性约束、线性约束及整数约束。要求使用混合算法框架求解。

解题过程：

1. 问题重构与松弛

• 首先处理整数约束 x ∈ ℤ²。引入松弛变量 s₁, s₂ ≥ 0，将整数约束转化为 x₁ - s₁ ∈ ℤ, x₂ - s₂ ∈ ℤ，并添加罚项 ρ(s₁² + s₂²) 到目标函数（增广拉格朗日思想）。
• 重构问题为：
  minimize f(x) + ρ(s₁² + s₂²)
  subject to c₁(x) ≤ 0, c₂(x) ≤ 0, s ≥ 0。

2. 代理模型初始化

• 在初始点 x⁽⁰⁾ = (0,0) 构建二次代理模型：
  q₀(d) = ∇f(x⁽⁰⁾)ᵀd + ½ dᵀB₀d，其中 B₀ 初始化为单位矩阵（拟牛顿法思想）。
• 约束线性化：c₁(x⁽⁰⁾) + ∇c₁(x⁽⁰⁾)ᵀd ≤ 0, c₂(x⁽⁰⁾) + ∇c₂(x⁽⁰⁾)ᵀd ≤ 0。

3. 积极集识别与子问题求解

• 在当前点评估约束违反度：c₁(x⁽⁰⁾)=0, c₂(x⁽⁰⁾)=-2，仅 c₁ 为积极约束。
• 建立序列二次规划子问题：
  minimize q₀(d)
  subject to ∇c₁(x⁽⁰⁾)ᵀd ≤ -c₁(x⁽⁰⁾) (积极约束)，信赖域约束 ||d|| ≤ Δ₀（Δ₀=1）。

4. 过滤器-信赖域协调

• 计算实际下降量 ared = f(x⁽⁰⁾) - f(x⁽⁰⁾+d)，预测下降量 pred = q₀(0) - q₀(d)。
• 若 ared/pred > 0.8，接受迭代并扩大信赖域；否则缩小信赖域（自适应机制）。

5. 乘子法更新屏障参数

• 对不等式约束使用自适应屏障函数：φ(x) = f(x) - μ∑log(-cᵢ(x))，其中 μ 初始为 1。
• 根据约束违反度动态调整 μ：若 max(cᵢ(x)) < 0.1μ，则 μ ← 0.7μ。

6. 梯度投影处理边界

• 对松弛变量 s 的非负约束，在每次迭代后投影到可行域：s ← max(s,0)。

7. 交替方向乘子法（ADMM）分解

• 将整数约束部分分离为子问题：
  minimize ρ||x - s - z||² （z 为整数逼近变量）
  通过动态隧道法跳过局部极值，用填充函数辅助全局搜索。

8. 收敛判断

• 当连续迭代点满足 ||x⁽ᵏ⁺¹⁾ - x⁽ᵏ⁾|| < 10⁻⁶ 且约束违反度 < 10⁻⁶ 时终止。
• 最终得到整数解 x* = (1,1)，f* = 1，满足所有约束。

算法通过多层协调机制平衡全局收敛与计算效率，尤其适合复杂约束的混合整数非线性问题。