非线性规划中的信赖域法基础题 题目描述 考虑非线性约束优化问题： 最小化 \( f(x) = (x_ 1 - 1)^2 + (x_ 2 - 2.5)^2 \) 满足约束 \( g_ 1(x) = x_ 1 - 2x_ 2 + 2 \geq 0 \)，\( g_ 2(x) = -x_ 1 - 2x_ 2 + 6 \geq 0 \)，\( g_ 3(x) = -x_ 1 + 2x_ 2 + 2 \geq 0 \)，且 \( x_ 1, x_ 2 \geq 0 \)。 要求使用信赖域法求解该问题，初始点选为 \( x^{(0)} = (2, 0) \)，初始信赖域半径 \( \Delta_ 0 = 0.5 \)。 解题过程 1. 问题分析 目标函数 \( f(x) \) 是二次凸函数，约束为线性不等式，构成凸优化问题。信赖域法通过迭代求解子问题逼近最优解：每步在当前点 \( x^{(k)} \) 用二次模型近似目标函数，并在半径 \( \Delta_ k \) 的球内求解该模型，根据实际改进与预测改进的比例调整信赖域半径。 2. 构建二次近似模型 在点 \( x^{(k)} \) 处，目标函数的二次近似为： \[ m_ k(d) = f(x^{(k)}) + \nabla f(x^{(k)})^T d + \frac{1}{2} d^T B_ k d, \] 其中 \( d \) 为步长，\( B_ k \) 为Hessian矩阵或其近似。本题中 \( f(x) \) 是二次函数，Hessian矩阵恒定： \[ \nabla^2 f(x) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}. \] 因此取 \( B_ k = \nabla^2 f(x) \)。梯度为： \[ \nabla f(x) = [ 2(x_ 1 - 1),\ 2(x_ 2 - 2.5) ]^T. \] 3. 子问题定义 第 \( k \) 步的子问题为： \[ \min_ d m_ k(d) = f(x^{(k)}) + \nabla f(x^{(k)})^T d + \frac{1}{2} d^T B_ k d, \] 满足 \( \|d\| \leq \Delta_ k \) 和线性约束（需在 \( x^{(k)} + d \) 处满足原问题约束）。 由于约束是线性的，子问题仍是二次规划，但信赖域约束 \( \|d\| \leq \Delta_ k \) 为球形边界，需用数值方法（如折线法或Dogleg法）求解。 4. 迭代步骤（以第一步为例） 初始点 ：\( x^{(0)} = (2, 0) \)，\( \Delta_ 0 = 0.5 \)。 计算梯度 ： \[ \nabla f(x^{(0)}) = [ 2(2-1),\ 2(0-2.5)]^T = [ 2,\ -5 ]^T. \] 子问题 ： \[ m_ 0(d) = f(2,0) + [ 2,\ -5 ] d + \frac{1}{2} d^T \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} d. \] 其中 \( f(2,0) = (2-1)^2 + (0-2.5)^2 = 7.25 \)。 约束需满足 \( x^{(0)} + d \) 在原问题可行域内，且 \( \|d\| \leq 0.5 \)。 求解子问题 ：由于信赖域半径小，可近似为线性搜索。忽略约束时，最优步长为 \( d^* = -B_ k^{-1} \nabla f(x^{(0)}) = [ -1,\ 2.5 ]^T \)，但范数超界，需投影到信赖域内。实际需用数值工具求解，假设解得 \( d^{(0)} = (-0.34,\ 0.34) \)（示例值）。 新点 ：\( x^{(1)} = x^{(0)} + d^{(0)} = (1.66,\ 0.34) \)。 评估改进比例 ： \[ \rho_ k = \frac{f(x^{(k)}) - f(x^{(k)}+d)}{m_ k(0) - m_ k(d)}. \] 若 \( \rho_ k \) 接近1，接受步长并扩大 \( \Delta_ {k+1} \)；若过小则缩小信赖域。 5. 收敛判断 重复以上步骤，直到梯度在约束边界满足KKT条件（例如梯度与约束梯度线性相关，且步长变化小于阈值）。本题最优解在 \( x^* = (1.4,\ 1.7) \) 处（通过解析验证），\( f(x^* ) = 0.8 \)。 关键点总结 信赖域法通过控制步长范围保证模型可靠性； 子问题需同时处理信赖域边界和线性约束； 半径调整策略基于实际改进与预测改进的比例。