非线性规划中的交替变量线性化与信赖域混合策略（Alternating Variable Linearization with Trust Region Strategy， AVL-TR）基础题
字数 7138 2025-12-20 08:14:23

好的，我注意到列表中有“自适应移动渐近线法（Adaptive Method of Moving Asymptotes, AMMA）”相关的题目（基础和进阶题），因此我将避免重复。我将随机选择一个不在列表中的算法：非线性规划中的交替变量线性化与信赖域混合策略（Alternating Variable Linearization with Trust Region Strategy， AVL-TR）基础题。

非线性规划中的交替变量线性化与信赖域混合策略（AVL-TR）基础题

题目描述

考虑以下非线性规划问题：
Minimize: \(f(\mathbf{x}) = x_1^2 + x_2^2 + (x_1 x_2 - 1)^2\)
Subject to: \(g(\mathbf{x}) = x_1^2 + 4x_2^2 - 4 \le 0\)

其中， \(\mathbf{x} = [x_1, x_2]^T \in \mathbb{R}^2\)。
给定初始点 \(\mathbf{x}^{(0)} = [1.5, 0.5]^T\)， 初始信赖域半径 \(\Delta_0 = 0.8\)， 参数 \(\eta = 0.1\)（用于判断是否接受新点）， 常数 \(c_1 = 0.25\)， \(c_2 = 2.0\)（用于调整信赖域半径）。

我们要求使用 交替变量线性化与信赖域混合策略 (AVL-TR) 进行一次迭代计算，以更新当前点。

解题过程与讲解

交替变量线性化（AVL）是一种处理多变量问题的策略，其核心思想是在每次迭代中，只对一个或一部分变量进行线性化近似和优化，而将其他变量暂时固定。这样可以将一个复杂的多变量子问题简化为一个或多个更易求解的单（少）变量子问题。结合信赖域（TR）策略，可以为每个子问题提供一个安全的搜索范围（信赖域半径），确保近似的有效性。

第一步：理解当前迭代的AVL-TR框架流程

对于当前点 \(\mathbf{x}^{(k)}\)， AVL-TR的一次完整迭代通常包含以下子步骤：

  1. 变量分组与选择： 决定本轮迭代优化哪个（或哪些）变量。在最简单的形式中，我们可以交替优化每个变量。假设我们有两个变量 \(x_1, x_2\)， 那么一次AVL迭代包含两个子迭代：先固定 \(x_2\) 优化 \(x_1\)， 再固定新的 \(x_1\) 优化 \(x_2\)。
  2. 子问题构建： 对于选中的变量，在固定其他变量的前提下，将目标函数 \(f\) 和约束函数 \(g\) 在该点附近进行一阶泰勒展开（即线性化）。
  3. 信赖域子问题求解： 在给定的信赖域半径 \(\Delta_k\) 内，求解这个带线性约束的信赖域子问题（通常是一个简单的二次或线性问题），得到该变量的候选位移。
  4. 接受性判断与半径更新： 计算实际函数下降量与模型预测下降量的比值 \(\rho\)。根据 \(\rho\) 决定是否接受这个候选位移，并更新信赖域半径 \(\Delta_k\) 用于下一个子问题或主迭代。
  5. 切换到下一个变量： 用更新后的点，对下一个变量重复步骤2-4。

第二步：初始化与第一次子迭代（优化 \(x_1\)， 固定 \(x_2\)）

给定：
初始点 \(\mathbf{x}^{(0)} = [x_1^{(0)}, x_2^{(0)}]^T = [1.5, 0.5]^T\)
初始信赖域半径 \(\Delta_0 = 0.8\)

  • 1. 构建关于 \(x_1\) 的子问题（固定 \(x_2 = 0.5\)）：
    我们需要将原问题在 \(\mathbf{x}^{(0)}\) 处，针对变量 \(x_1\) 进行线性化。令 \(s_1\) 为 \(x_1\) 的位移，即新点 \(x_1^+ = x_1^{(0)} + s_1\)， \(x_2\) 保持为 \(0.5\)。

    首先计算在 \(\mathbf{x}^{(0)}\) 处的函数值和梯度：

    • \(f^{(0)} = f(1.5, 0.5) = (1.5)^2 + (0.5)^2 + (1.5*0.5 - 1)^2 = 2.25 + 0.25 + (0.75 - 1)^2 = 2.5 + 0.0625 = 2.5625\)
    • \(\nabla f(\mathbf{x}) = [\frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}]^T = [2x_1 + 2(x_1 x_2 - 1)x_2, \ 2x_2 + 2(x_1 x_2 - 1)x_1]^T\)
    • \(g_1^{(0)} = \frac{\partial f}{\partial x_1}(1.5, 0.5) = 2*1.5 + 2*(1.5*0.5-1)*0.5 = 3 + 2*(-0.25)*0.5 = 3 - 0.25 = 2.75\)
    • \(g(\mathbf{x}^{(0)}) = (1.5)^2 + 4*(0.5)^2 - 4 = 2.25 + 1 - 4 = -0.75\)（满足约束，为内部点）
    • \(\nabla g(\mathbf{x}) = [2x_1, 8x_2]^T\)
    • \(\nabla_x g(\mathbf{x}^{(0)}) = [3, 4]^T\)（注意：这里梯度是二维的，但当我们只对 \(x_1\) 线性化时，只关心 \(x_1\) 方向的偏导，即第一个分量 3）。

    现在，构建关于变量 \(s_1\) 的线性化模型子问题：

    • 模型目标函数： \(m_1(s_1) = f^{(0)} + g_1^{(0)} \cdot s_1\) （一阶泰勒近似，注意这里 \(s_1\) 是标量，所以就是梯度分量乘以位移）
    • 模型约束： \(g(\mathbf{x}^{(0)}) + \nabla_x g(\mathbf{x}^{(0)})_1 \cdot s_1 \le 0\) （约束的线性化）。即 \(-0.75 + 3 \cdot s_1 \le 0\)。
    • 信赖域约束： \(|s_1| \le \Delta_0 = 0.8\)（因为我们只优化 \(x_1\)，所以信赖域是 \(s_1\) 的一维区间）。

    所以，第一个子问题是：
    Minimize \(m_1(s_1) = 2.5625 + 2.75 s_1\)
    Subject to:
    \(-0.75 + 3 s_1 \le 0\) => \(s_1 \le 0.25\)
    \(|s_1| \le 0.8\)

  • 2. 求解子问题：
    这是一个一维线性规划问题。目标函数是 \(2.75 s_1\)， 系数为正，所以要最小化它， \(s_1\) 应该尽可能小（取负值）。
    约束条件： \(s_1 \le 0.25\) 和 \(-0.8 \le s_1 \le 0.8\)。
    为了最小化 \(2.75 s_1\)， 我们希望在可行域内取最小的 \(s_1\)， 即 \(s_1^* = -0.8\)。

  • 3. 接受性判断与更新（对于这个子迭代）：
    计算候选点： \(x_1^+ = 1.5 + (-0.8) = 0.7\)， 所以候选点为 \(\mathbf{x}_{candidate} = [0.7, 0.5]^T\)。
    计算实际下降量： \(\text{Ared}_1 = f(\mathbf{x}^{(0)}) - f(\mathbf{x}_{candidate}) = 2.5625 - f(0.7, 0.5)\)
    \(f(0.7, 0.5) = 0.49 + 0.25 + (0.35 - 1)^2 = 0.74 + 0.4225 = 1.1625\)
    \(\text{Ared}_1 = 2.5625 - 1.1625 = 1.4\)

    计算模型预测下降量： \(\text{Pred}_1 = m_1(0) - m_1(s_1^*) = 0 - (2.5625 + 2.75 * (-0.8)) = - (2.5625 - 2.2) = -0.3625\)？ 等等，这里要小心。

    更准确的计算是：模型在位移前的值是 \(m_1(0) = 2.5625\)， 位移后的模型值是 \(m_1(-0.8) = 2.5625 + 2.75*(-0.8) = 2.5625 - 2.2 = 0.3625\)。所以模型预测的下降量 \(\text{Pred}_1 = m_1(0) - m_1(-0.8) = 2.5625 - 0.3625 = 2.2\)。

    计算比值： \(\rho_1 = \frac{\text{Ared}_1}{\text{Pred}_1} = \frac{1.4}{2.2} \approx 0.636\)

    判断： 由于 \(\rho_1 > \eta (=0.1)\)， 接受这个位移。更新当前点为 \(\mathbf{x}^{(0.5)} = [0.7, 0.5]^T\)（这里用 (0.5) 表示完成了一半的AVL迭代）。
    更新信赖域半径？通常在AVL中，一个变量更新后，信赖域半径可以保持不变用于下一个变量的优化，或者根据 \(\rho\) 调整。根据题目给定的 \(c_1, c_2\)， 常见规则是：若 \(\rho\) 很小（如 <0.25），则缩小半径；若 \(\rho\) 很大（如 >0.75）且位移达到了信赖域边界，则增大半径；否则保持。这里 \(\rho_1 \approx 0.636\)， 且位移 \(|s_1^*|=0.8\) 达到了边界，但 \(\rho_1\) 未超过0.75，所以我们保持半径 \(\Delta_{0.5} = \Delta_0 = 0.8\) 用于下一个子问题。

第三步：第二次子迭代（优化 \(x_2\)， 固定 \(x_1 = 0.7\)）

当前点： \(\mathbf{x}^{(0.5)} = [0.7, 0.5]^T\)， 信赖域半径 \(\Delta_{0.5} = 0.8\)。

  • 1. 构建关于 \(x_2\) 的子问题（固定 \(x_1 = 0.7\)）：
    令 \(s_2\) 为 \(x_2\) 的位移， \(x_2^+ = 0.5 + s_2\)。

    计算在当前点 \(\mathbf{x}^{(0.5)}\) 处的函数值和梯度分量：

    • \(f^{(0.5)} = f(0.7, 0.5) = 1.1625\)（已计算）
    • \(g_2^{(0.5)} = \frac{\partial f}{\partial x_2}(0.7, 0.5) = 2*0.5 + 2*(0.7*0.5-1)*0.7 = 1 + 2*(-0.65)*0.7 = 1 - 0.91 = 0.09\)
    • \(g(\mathbf{x}^{(0.5)}) = (0.7)^2 + 4*(0.5)^2 - 4 = 0.49 + 1 - 4 = -2.51\)
    • \(\nabla_x g(\mathbf{x}^{(0.5)}) = [2*0.7, 8*0.5]^T = [1.4, 4]^T\)。关于 \(x_2\) 的偏导是 4。

    构建子问题：
    Minimize \(m_2(s_2) = f^{(0.5)} + g_2^{(0.5)} \cdot s_2 = 1.1625 + 0.09 s_2\)
    Subject to:
    \(g(\mathbf{x}^{(0.5)}) + \nabla_x g(\mathbf{x}^{(0.5)})_2 \cdot s_2 \le 0\) => \(-2.51 + 4 s_2 \le 0\) => \(s_2 \le 0.6275\)
    \(|s_2| \le \Delta_{0.5} = 0.8\)

  • 2. 求解子问题：
    目标函数是 \(0.09 s_2\)， 系数为正。要最小化它， \(s_2\) 应尽可能小。
    约束条件： \(s_2 \le 0.6275\) 和 \(-0.8 \le s_2 \le 0.8\)。
    可行域内最小的 \(s_2\) 是 \(s_2^* = -0.8\)。

  • 3. 接受性判断与更新（完成本次AVL迭代）：
    计算候选点： \(x_2^+ = 0.5 + (-0.8) = -0.3\)， 所以候选点为 \(\mathbf{x}_{candidate} = [0.7, -0.3]^T\)。
    计算实际下降量： \(\text{Ared}_2 = f(\mathbf{x}^{(0.5)}) - f(\mathbf{x}_{candidate}) = 1.1625 - f(0.7, -0.3)\)
    \(f(0.7, -0.3) = 0.49 + 0.09 + (0.7*(-0.3) - 1)^2 = 0.58 + (-0.21 - 1)^2 = 0.58 + (-1.21)^2 = 0.58 + 1.4641 = 2.0441\)
    \(\text{Ared}_2 = 1.1625 - 2.0441 = -0.8816\) （注意：实际函数值增加了！）

    计算模型预测下降量： \(\text{Pred}_2 = m_2(0) - m_2(s_2^*) = 1.1625 - [1.1625 + 0.09*(-0.8)] = 1.1625 - (1.1625 - 0.072) = 0.072\)

    计算比值： \(\rho_2 = \frac{\text{Ared}_2}{\text{Pred}_2} = \frac{-0.8816}{0.072} \approx -12.24\)

    判断： 由于 \(\rho_2 < \eta (=0.1)\) 且为负数（表示模型预测下降，但实际函数值反而上升，模型非常不准确），拒绝这个位移。
    因此，对于变量 \(x_2\) 的更新被拒绝。我们保持 \(x_2\) 不变。
    最终更新点为 \(\mathbf{x}^{(1)} = [0.7, 0.5]^T\)。

    更新信赖域半径：因为 \(\rho_2\) 非常小（负值），我们需要大幅缩小信赖域半径，以确保下一步的线性模型更准确。根据规则，若 \(\rho \le c_1\)（这里 \(c_1 = 0.25\)），则缩小半径： \(\Delta_1 = c_1 \cdot \Delta_{0.5} = 0.25 * 0.8 = 0.2\)。

本次迭代总结

经过一次完整的AVL-TR迭代（依次优化 \(x_1\) 和 \(x_2\)）：

  • 初始点： \(\mathbf{x}^{(0)} = [1.5, 0.5]^T\)， \(f = 2.5625\)， \(\Delta = 0.8\)
  • 优化 \(x_1\)： 成功，点更新为 \([0.7, 0.5]^T\)， \(f\) 降至 1.1625。信赖域半径保持 0.8。
  • 优化 \(x_2\)： 失败，因为线性模型在边界处 (\(s_2 = -0.8\)) 的预测严重偏离真实情况（目标函数非凸性在固定 \(x_1\) 时可能更明显）。点回退到 \([0.7, 0.5]^T\)。
  • 最终点： \(\mathbf{x}^{(1)} = [0.7, 0.5]^T\)， \(f = 1.1625\)
  • 新信赖域半径： \(\Delta_1 = 0.2\)

这个例子清晰地展示了AVL-TR的工作流程和特点：

  1. 分解简化：将复杂问题分解为一系列简单的一维搜索问题。
  2. 信赖域控制：通过信赖域约束防止因线性化不准确导致的过大、无效的位移。
  3. 自适应机制：根据模型预测精度（\(\rho\) 值）动态调整信赖域半径，在模型准确时允许大步长，不准确时缩小步长以保证可靠性。
  4. 潜在缺点：由于变量被交替固定，当变量间耦合很强时（如本例目标函数中的 \(x_1 x_2\) 项），对单个变量的线性化模型可能在远离当前点的地方误差很大，导致子问题的最优解（在信赖域边界）并不是整体好的移动方向，从而被拒绝。这要求算法可能需要更多的迭代或更谨慎的半径调整策略。
好的，我注意到列表中有“自适应移动渐近线法（Adaptive Method of Moving Asymptotes, AMMA）”相关的题目（基础和进阶题），因此我将避免重复。我将随机选择一个不在列表中的算法： 非线性规划中的交替变量线性化与信赖域混合策略（Alternating Variable Linearization with Trust Region Strategy， AVL-TR）基础题 。 非线性规划中的交替变量线性化与信赖域混合策略（AVL-TR）基础题 题目描述 考虑以下非线性规划问题： Minimize: \( f(\mathbf{x}) = x_ 1^2 + x_ 2^2 + (x_ 1 x_ 2 - 1)^2 \) Subject to: \( g(\mathbf{x}) = x_ 1^2 + 4x_ 2^2 - 4 \le 0 \) 其中， \( \mathbf{x} = [ x_ 1, x_ 2 ]^T \in \mathbb{R}^2 \)。 给定初始点 \( \mathbf{x}^{(0)} = [ 1.5, 0.5]^T \)， 初始信赖域半径 \( \Delta_ 0 = 0.8 \)， 参数 \( \eta = 0.1 \)（用于判断是否接受新点）， 常数 \( c_ 1 = 0.25 \)， \( c_ 2 = 2.0 \)（用于调整信赖域半径）。 我们要求使用 交替变量线性化与信赖域混合策略 (AVL-TR) 进行一次迭代计算，以更新当前点。 解题过程与讲解 交替变量线性化（AVL）是一种处理多变量问题的策略，其核心思想是 在每次迭代中，只对一个或一部分变量进行线性化近似和优化，而将其他变量暂时固定 。这样可以将一个复杂的多变量子问题简化为一个或多个更易求解的单（少）变量子问题。结合信赖域（TR）策略，可以为每个子问题提供一个安全的搜索范围（信赖域半径），确保近似的有效性。 第一步：理解当前迭代的AVL-TR框架流程 对于当前点 \( \mathbf{x}^{(k)} \)， AVL-TR的一次完整迭代通常包含以下子步骤： 变量分组与选择 ： 决定本轮迭代优化哪个（或哪些）变量。在最简单的形式中，我们可以 交替优化 每个变量。假设我们有两个变量 \( x_ 1, x_ 2 \)， 那么一次AVL迭代包含两个子迭代：先固定 \( x_ 2 \) 优化 \( x_ 1 \)， 再固定新的 \( x_ 1 \) 优化 \( x_ 2 \)。 子问题构建 ： 对于选中的变量，在固定其他变量的前提下，将目标函数 \( f \) 和约束函数 \( g \) 在该点附近进行一阶泰勒展开（即线性化）。 信赖域子问题求解 ： 在给定的信赖域半径 \( \Delta_ k \) 内，求解这个带线性约束的信赖域子问题（通常是一个简单的二次或线性问题），得到该变量的候选位移。 接受性判断与半径更新 ： 计算实际函数下降量与模型预测下降量的比值 \( \rho \)。根据 \( \rho \) 决定是否接受这个候选位移，并更新信赖域半径 \( \Delta_ k \) 用于下一个子问题或主迭代。 切换到下一个变量 ： 用更新后的点，对下一个变量重复步骤2-4。 第二步：初始化与第一次子迭代（优化 \( x_ 1 \)， 固定 \( x_ 2 \)） 给定： 初始点 \( \mathbf{x}^{(0)} = [ x_ 1^{(0)}, x_ 2^{(0)}]^T = [ 1.5, 0.5 ]^T \) 初始信赖域半径 \( \Delta_ 0 = 0.8 \) 1. 构建关于 \( x_ 1 \) 的子问题（固定 \( x_ 2 = 0.5 \)）： 我们需要将原问题在 \( \mathbf{x}^{(0)} \) 处，针对变量 \( x_ 1 \) 进行线性化。令 \( s_ 1 \) 为 \( x_ 1 \) 的位移，即新点 \( x_ 1^+ = x_ 1^{(0)} + s_ 1 \)， \( x_ 2 \) 保持为 \( 0.5 \)。 首先计算在 \( \mathbf{x}^{(0)} \) 处的函数值和梯度： \( f^{(0)} = f(1.5, 0.5) = (1.5)^2 + (0.5)^2 + (1.5* 0.5 - 1)^2 = 2.25 + 0.25 + (0.75 - 1)^2 = 2.5 + 0.0625 = 2.5625 \) \( \nabla f(\mathbf{x}) = [ \frac{\partial f}{\partial x_ 1}, \frac{\partial f}{\partial x_ 2}]^T = [ 2x_ 1 + 2(x_ 1 x_ 2 - 1)x_ 2, \ 2x_ 2 + 2(x_ 1 x_ 2 - 1)x_ 1 ]^T \) \( g_ 1^{(0)} = \frac{\partial f}{\partial x_ 1}(1.5, 0.5) = 2 1.5 + 2 (1.5 0.5-1) 0.5 = 3 + 2* (-0.25)* 0.5 = 3 - 0.25 = 2.75 \) \( g(\mathbf{x}^{(0)}) = (1.5)^2 + 4* (0.5)^2 - 4 = 2.25 + 1 - 4 = -0.75 \)（满足约束，为内部点） \( \nabla g(\mathbf{x}) = [ 2x_ 1, 8x_ 2 ]^T \) \( \nabla_ x g(\mathbf{x}^{(0)}) = [ 3, 4]^T \)（注意：这里梯度是二维的，但当我们只对 \( x_ 1 \) 线性化时，只关心 \( x_ 1 \) 方向的偏导，即第一个分量 3 ）。 现在，构建关于变量 \( s_ 1 \) 的 线性化模型子问题 ： 模型目标函数 ： \( m_ 1(s_ 1) = f^{(0)} + g_ 1^{(0)} \cdot s_ 1 \) （一阶泰勒近似，注意这里 \( s_ 1 \) 是标量，所以就是梯度分量乘以位移） 模型约束 ： \( g(\mathbf{x}^{(0)}) + \nabla_ x g(\mathbf{x}^{(0)})_ 1 \cdot s_ 1 \le 0 \) （约束的线性化）。即 \( -0.75 + 3 \cdot s_ 1 \le 0 \)。 信赖域约束 ： \( |s_ 1| \le \Delta_ 0 = 0.8 \)（因为我们只优化 \( x_ 1 \)，所以信赖域是 \( s_ 1 \) 的一维区间）。 所以，第一个子问题是： Minimize \( m_ 1(s_ 1) = 2.5625 + 2.75 s_ 1 \) Subject to: \( -0.75 + 3 s_ 1 \le 0 \) => \( s_ 1 \le 0.25 \) \( |s_ 1| \le 0.8 \) 2. 求解子问题： 这是一个 一维线性规划 问题。目标函数是 \( 2.75 s_ 1 \)， 系数为正，所以要最小化它， \( s_ 1 \) 应该尽可能小（取负值）。 约束条件： \( s_ 1 \le 0.25 \) 和 \( -0.8 \le s_ 1 \le 0.8 \)。 为了最小化 \( 2.75 s_ 1 \)， 我们希望在可行域内取最小的 \( s_ 1 \)， 即 \( s_ 1^* = -0.8 \)。 3. 接受性判断与更新（对于这个子迭代）： 计算候选点： \( x_ 1^+ = 1.5 + (-0.8) = 0.7 \)， 所以候选点为 \( \mathbf{x}_ {candidate} = [ 0.7, 0.5 ]^T \)。 计算实际下降量： \( \text{Ared} 1 = f(\mathbf{x}^{(0)}) - f(\mathbf{x} {candidate}) = 2.5625 - f(0.7, 0.5) \) \( f(0.7, 0.5) = 0.49 + 0.25 + (0.35 - 1)^2 = 0.74 + 0.4225 = 1.1625 \) \( \text{Ared}_ 1 = 2.5625 - 1.1625 = 1.4 \) 计算模型预测下降量： \( \text{Pred}_ 1 = m_ 1(0) - m_ 1(s_ 1^ ) = 0 - (2.5625 + 2.75 (-0.8)) = - (2.5625 - 2.2) = -0.3625 \)？ 等等，这里要小心。 更准确的计算是：模型在位移前的值是 \( m_ 1(0) = 2.5625 \)， 位移后的模型值是 \( m_ 1(-0.8) = 2.5625 + 2.75* (-0.8) = 2.5625 - 2.2 = 0.3625 \)。所以 模型预测的下降量 \( \text{Pred}_ 1 = m_ 1(0) - m_ 1(-0.8) = 2.5625 - 0.3625 = 2.2 \)。 计算比值： \( \rho_ 1 = \frac{\text{Ared}_ 1}{\text{Pred}_ 1} = \frac{1.4}{2.2} \approx 0.636 \) 判断： 由于 \( \rho_ 1 > \eta (=0.1) \)， 接受这个位移。更新当前点为 \( \mathbf{x}^{(0.5)} = [ 0.7, 0.5 ]^T \)（这里用 (0.5) 表示完成了一半的AVL迭代）。 更新信赖域半径？通常在AVL中，一个变量更新后，信赖域半径可以保持不变用于下一个变量的优化，或者根据 \( \rho \) 调整。根据题目给定的 \( c_ 1, c_ 2 \)， 常见规则是：若 \( \rho \) 很小（如 <0.25），则缩小半径；若 \( \rho \) 很大（如 >0.75）且位移达到了信赖域边界，则增大半径；否则保持。这里 \( \rho_ 1 \approx 0.636 \)， 且位移 \( |s_ 1^* |=0.8 \) 达到了边界，但 \( \rho_ 1 \) 未超过0.75，所以我们 保持 半径 \( \Delta_ {0.5} = \Delta_ 0 = 0.8 \) 用于下一个子问题。 第三步：第二次子迭代（优化 \( x_ 2 \)， 固定 \( x_ 1 = 0.7 \)） 当前点： \( \mathbf{x}^{(0.5)} = [ 0.7, 0.5]^T \)， 信赖域半径 \( \Delta_ {0.5} = 0.8 \)。 1. 构建关于 \( x_ 2 \) 的子问题（固定 \( x_ 1 = 0.7 \)）： 令 \( s_ 2 \) 为 \( x_ 2 \) 的位移， \( x_ 2^+ = 0.5 + s_ 2 \)。 计算在当前点 \( \mathbf{x}^{(0.5)} \) 处的函数值和梯度分量： \( f^{(0.5)} = f(0.7, 0.5) = 1.1625 \)（已计算） \( g_ 2^{(0.5)} = \frac{\partial f}{\partial x_ 2}(0.7, 0.5) = 2 0.5 + 2 (0.7 0.5-1) 0.7 = 1 + 2* (-0.65)* 0.7 = 1 - 0.91 = 0.09 \) \( g(\mathbf{x}^{(0.5)}) = (0.7)^2 + 4* (0.5)^2 - 4 = 0.49 + 1 - 4 = -2.51 \) \( \nabla_ x g(\mathbf{x}^{(0.5)}) = [ 2 0.7, 8 0.5]^T = [ 1.4, 4]^T \)。关于 \( x_ 2 \) 的偏导是 4 。 构建子问题： Minimize \( m_ 2(s_ 2) = f^{(0.5)} + g_ 2^{(0.5)} \cdot s_ 2 = 1.1625 + 0.09 s_ 2 \) Subject to: \( g(\mathbf{x}^{(0.5)}) + \nabla_ x g(\mathbf{x}^{(0.5)}) 2 \cdot s_ 2 \le 0 \) => \( -2.51 + 4 s_ 2 \le 0 \) => \( s_ 2 \le 0.6275 \) \( |s_ 2| \le \Delta {0.5} = 0.8 \) 2. 求解子问题： 目标函数是 \( 0.09 s_ 2 \)， 系数为正。要最小化它， \( s_ 2 \) 应尽可能小。 约束条件： \( s_ 2 \le 0.6275 \) 和 \( -0.8 \le s_ 2 \le 0.8 \)。 可行域内最小的 \( s_ 2 \) 是 \( s_ 2^* = -0.8 \)。 3. 接受性判断与更新（完成本次AVL迭代）： 计算候选点： \( x_ 2^+ = 0.5 + (-0.8) = -0.3 \)， 所以候选点为 \( \mathbf{x}_ {candidate} = [ 0.7, -0.3 ]^T \)。 计算实际下降量： \( \text{Ared} 2 = f(\mathbf{x}^{(0.5)}) - f(\mathbf{x} {candidate}) = 1.1625 - f(0.7, -0.3) \) \( f(0.7, -0.3) = 0.49 + 0.09 + (0.7* (-0.3) - 1)^2 = 0.58 + (-0.21 - 1)^2 = 0.58 + (-1.21)^2 = 0.58 + 1.4641 = 2.0441 \) \( \text{Ared}_ 2 = 1.1625 - 2.0441 = -0.8816 \) （ 注意：实际函数值增加了！ ） 计算模型预测下降量： \( \text{Pred}_ 2 = m_ 2(0) - m_ 2(s_ 2^ ) = 1.1625 - [ 1.1625 + 0.09 (-0.8) ] = 1.1625 - (1.1625 - 0.072) = 0.072 \) 计算比值： \( \rho_ 2 = \frac{\text{Ared}_ 2}{\text{Pred}_ 2} = \frac{-0.8816}{0.072} \approx -12.24 \) 判断： 由于 \( \rho_ 2 < \eta (=0.1) \) 且为负数（表示模型预测下降，但实际函数值反而上升，模型非常不准确）， 拒绝这个位移 。 因此，对于变量 \( x_ 2 \) 的更新被拒绝。我们保持 \( x_ 2 \) 不变。 最终更新点 为 \( \mathbf{x}^{(1)} = [ 0.7, 0.5 ]^T \)。 更新信赖域半径：因为 \( \rho_ 2 \) 非常小（负值），我们需要 大幅缩小 信赖域半径，以确保下一步的线性模型更准确。根据规则，若 \( \rho \le c_ 1 \)（这里 \( c_ 1 = 0.25 \)），则缩小半径： \( \Delta_ 1 = c_ 1 \cdot \Delta_ {0.5} = 0.25 * 0.8 = 0.2 \)。 本次迭代总结 经过一次完整的AVL-TR迭代（依次优化 \( x_ 1 \) 和 \( x_ 2 \)）： 初始点 ： \( \mathbf{x}^{(0)} = [ 1.5, 0.5 ]^T \)， \( f = 2.5625 \)， \( \Delta = 0.8 \) 优化 \( x_ 1 \) ： 成功，点更新为 \( [ 0.7, 0.5 ]^T \)， \( f \) 降至 1.1625。信赖域半径保持 0.8。 优化 \( x_ 2 \) ： 失败，因为线性模型在边界处 (\( s_ 2 = -0.8 \)) 的预测严重偏离真实情况（目标函数非凸性在固定 \( x_ 1 \) 时可能更明显）。点回退到 \( [ 0.7, 0.5 ]^T \)。 最终点 ： \( \mathbf{x}^{(1)} = [ 0.7, 0.5 ]^T \)， \( f = 1.1625 \) 新信赖域半径 ： \( \Delta_ 1 = 0.2 \) 这个例子清晰地展示了AVL-TR的工作流程和特点： 分解简化 ：将复杂问题分解为一系列简单的一维搜索问题。 信赖域控制 ：通过信赖域约束防止因线性化不准确导致的过大、无效的位移。 自适应机制 ：根据模型预测精度（\( \rho \) 值）动态调整信赖域半径，在模型准确时允许大步长，不准确时缩小步长以保证可靠性。 潜在缺点 ：由于变量被交替固定，当变量间耦合很强时（如本例目标函数中的 \( x_ 1 x_ 2 \) 项），对单个变量的线性化模型可能在远离当前点的地方误差很大，导致子问题的最优解（在信赖域边界）并不是整体好的移动方向，从而被拒绝。这要求算法可能需要更多的迭代或更谨慎的半径调整策略。