基于交替变量方向法（Alternating Variable Direction Method, AVDM）的简单非线性规划问题

题目描述
考虑一个简单的非线性规划问题：

minimize f(x, y) = x^4 + y^4 - 4x^2 - 6y^2
subject to g1(x, y) = x + y ≤ 2
           g2(x, y) = x - y ≥ 0
           x, y ∈ R

目标函数 f(x, y) 是一个非凸四次函数，约束为两个线性不等式。我们将使用交替变量方向法（AVDM）来求解这个有约束优化问题。AVDM的核心思想是每次迭代中，固定其他变量，只优化一个变量，并在每次单变量优化后施加约束，逐步逼近最优解。

解题过程

步骤1：算法原理与问题分析
交替变量方向法是一种迭代优化方法，适用于变量可分或近似可分的函数。对于问题 min f(x₁, x₂, ..., xₙ)，每次迭代中，我们依次优化每个变量，保持其他变量不变。对于约束问题，可以在每个单变量优化子问题中考虑约束，或者通过投影到可行集来保证可行性。

本问题中，变量是 x 和 y。虽然 f(x, y) 不是完全可分的（没有交叉项），但固定一个变量时，关于另一个变量的子问题是单变量四次函数优化，可解析求解。约束 g1 和 g2 是线性的，在单变量优化时容易处理。

步骤2：初始化
选择一个初始可行点。由于约束是线性的，我们可以通过简单选择满足约束的点。例如，取 (x₀, y₀) = (1, 0)，检查可行性：

• g1: 1 + 0 = 1 ≤ 2 ✔
• g2: 1 - 0 = 1 ≥ 0 ✔
  初始点可行。设当前点为 (xᵏ, yᵏ)，初始 k=0。

步骤3：AVDM迭代格式
每次迭代分为两个子步骤：

1. 固定 yᵏ，优化关于 x 的子问题，得到 xᵏ⁺¹。
2. 固定 xᵏ⁺¹，优化关于 y 的子问题，得到 yᵏ⁺¹。

每个子问题是一个带约束的单变量优化：

• 子问题Px（固定 y = yᵏ）：
  minimize f_x(x) = x⁴ - 4x² + (yᵏ)⁴ - 6(yᵏ)²
  subject to x + yᵏ ≤ 2, x - yᵏ ≥ 0, x ∈ R
• 子问题Py（固定 x = xᵏ⁺¹）：
  minimize f_y(y) = (xᵏ⁺¹)⁴ - 4(xᵏ⁺¹)² + y⁴ - 6y²
  subject to xᵏ⁺¹ + y ≤ 2, xᵏ⁺¹ - y ≥ 0, y ∈ R

注意常数项在优化中可忽略。

步骤4：单变量子问题的求解
对于单变量四次函数 φ(t) = t⁴ + a t² + c（这里 a 是系数，c 是常数），其无约束极值点来自导数零点：φ'(t) = 4t³ + 2a t = 2t(2t² + a) = 0。解为 t = 0 或 t = ±√(-a/2)（当 a < 0 时）。需比较这些点的函数值，并结合约束区间确定最小值。

对于约束，因为是不等式，我们需在区间内优化。以 Px 为例：
约束为 x ∈ [yᵏ, 2 - yᵏ]（由 g2: x ≥ yᵏ 和 g1: x ≤ 2 - yᵏ）。注意需确保区间非空，即 yᵏ ≤ 2 - yᵏ ⇒ yᵏ ≤ 1，这在后续迭代中应满足。

然后，在区间 [yᵏ, 2 - yᵏ] 上最小化 f_x(x) = x⁴ - 4x²。计算 f_x'(x) = 4x³ - 8x = 4x(x² - 2)。无约束临界点：x = 0, x = ±√2。比较区间端点 yᵏ 和 2 - yᵏ 以及临界点中落在区间内的点，选择使 f_x 最小的点作为 xᵏ⁺¹。

Py 的求解类似。

步骤5：第一次迭代（k=0）
初始点 (x⁰, y⁰) = (1, 0)。

• 固定 y⁰ = 0，解 Px：
  f_x(x) = x⁴ - 4x²，区间为 [0, 2]（因为 x ≥ 0 且 x ≤ 2）。
  无约束临界点：x = 0, x = √2 ≈ 1.414, x = -√2（不在区间内）。
  比较函数值：
  f_x(0) = 0
  f_x(√2) = (√2)⁴ - 4*(√2)² = 4 - 8 = -4
  f_x(2) = 16 - 16 = 0
  最小值在 x = √2，但 √2 ≈ 1.414 在区间 [0,2] 内，所以 x¹ = √2。

• 固定 x¹ = √2，解 Py：
  f_y(y) = y⁴ - 6y² + c，其中 c = (√2)⁴ - 4*(√2)² = 4 - 8 = -4 为常数。
  约束区间：由 g1: y ≤ 2 - √2 ≈ 0.586；由 g2: y ≤ √2（因为 x - y ≥ 0 ⇒ y ≤ x）。结合得 y ∈ (-∞, 0.586]。但 y 无下界约束，不过目标函数 y⁴ - 6y² 是偶函数，在 |y| 大时趋于正无穷，最小值应在有限区间。我们考虑有界区间 [L, 0.586]，其中 L 是一个足够小的数（如 -10）。但为简化，我们可先找无约束极值点。
  f_y'(y) = 4y³ - 12y = 4y(y² - 3) = 0 ⇒ y = 0 或 y = ±√3 ≈ ±1.732。
  比较：f_y(0) = 0 - 0 -4 = -4；f_y(√3) = 9 - 18 -4 = -13；f_y(-√3) 相同。但 y = ±√3 不在约束区间 y ≤ 0.586 内。区间 [L, 0.586] 内，导数在 y=0 处为零，且 f_y''(0) = -12 < 0，所以 y=0 是局部极大点！实际上，在 y ≤ 0.586 区间，函数 f_y(y) 在 y 负方向递减（因为导数 4y(y²-3) 当 y<0 时为负），所以最小值在边界 y=0.586 处取得。计算 f_y(0.586) ≈ (0.586)⁴ - 6*(0.586)² -4 ≈ 0.118 - 2.060 -4 = -5.942。比 f_y(0) = -4 更小。所以 y¹ = 0.586。

  更严谨地，我们在区间 (-∞, 0.586] 上最小化 f_y(y)。由于 y → -∞ 时 f_y → +∞，最小值在有限点取得。检查导数：当 y < 0 时，f_y' = 4y(y²-3)。对于 y < 0，y²-3 在 |y| < √3 时为负，乘积为正；在 |y| > √3 时为正，乘积为负？具体：若 y < -√3 ≈ -1.732，则 y²>3，所以 y²-3>0，由于 y<0，f_y'<0（递减）；若 -√3 < y < 0，则 y²-3<0，f_y'>0（递增）。所以 f_y 在 (-∞, -√3] 递减，在 [-√3, 0] 递增。全局无约束最小值在 y = ±√3，但 y = -√3 不在约束区间内（-√3 < 0.586 满足，但需检查是否 ≤0.586，是的 -1.732 ≤ 0.586）。但 y = -√3 ≈ -1.732 在约束区间内。比较 f_y(-√3) = -13，f_y(0.586) ≈ -5.942，所以最小值在 y = -√3 取得。但还需检查约束 g2: x - y ≥ 0 ⇒ y ≤ x = √2 ≈ 1.414，显然 -√3 满足。所以 y¹ = -√3 ≈ -1.732。

  但注意，此时 g1: x + y = √2 + (-√3) ≈ 1.414 - 1.732 = -0.318 ≤ 2，也满足。所以 y¹ = -√3。

  因此第一次迭代后，点变为 (x¹, y¹) = (√2, -√3) ≈ (1.414, -1.732)。

步骤6：第二次迭代（k=1）
从 (x¹, y¹) = (√2, -√3) 开始。

• 固定 y¹ = -√3，解 Px：
  约束区间：x ≥ y¹ = -√3 ≈ -1.732；x ≤ 2 - y¹ = 2 + √3 ≈ 3.732。所以 x ∈ [-1.732, 3.732]。
  f_x(x) = x⁴ - 4x² + 常数（常数来自 y¹ 的项，可忽略）。
  无约束临界点：x = 0, x = ±√2 ≈ ±1.414。
  比较区间内点：x = -1.732, 0, 1.414, 3.732 的函数值（只计算 x⁴ - 4x²）：
  f_x(-1.732) ≈ 9 - 12 = -3
  f_x(0) = 0
  f_x(1.414) = 4 - 8 = -4
  f_x(3.732) ≈ 194 - 56 = 138
  最小值在 x = √2 ≈ 1.414，该点在区间内，所以 x² = √2。

• 固定 x² = √2，解 Py：
  与第一次迭代中 Py 完全相同，因为 x 相同。所以 y² = -√3。

迭代点未变：(x², y²) = (√2, -√3)。已收敛到固定点。

步骤7：最优性检验
在收敛点 (x*, y*) = (√2, -√3)，我们检查是否满足 KKT 条件：
目标函数梯度 ∇f = [4x³ - 8x, 4y³ - 12y] = [4*(2√2) - 8√2, 4*(-3√3) - 12*(-√3)] = [8√2 - 8√2, -12√3 + 12√3] = [0, 0]。
所以无约束梯度为零。约束：g1: x + y = √2 - √3 ≈ -0.318 < 2，松弛；g2: x - y = √2 + √3 ≈ 3.146 > 0，松弛。两个约束都不活跃，且梯度为零，所以该点是无约束局部极小点。实际上，f 的无约束临界点有 (0,0), (±√2, 0), (0, ±√3), (±√2, ±√3)。通过计算 Hessian 矩阵可知 (±√2, ±√3) 是局部极小点，其中 (√2, -√3) 是其中一个。由于约束不活跃，这个点也是约束局部极小点。

步骤8：结论
AVDM 在两步内收敛到局部最优解 (x*, y*) = (√2, -√3)，对应的目标函数值 f* = (√2)⁴ + (-√3)⁴ - 4(√2)² - 6(-√3)² = 4 + 9 - 8 - 18 = -13。算法有效解决了这个简单约束非线性规划问题。