非线性规划中的自适应网格搜索算法基础题 题目描述 考虑非线性规划问题： \[ \min f(x) = (x_ 1 - 2)^2 + (x_ 2 - 1)^2 \] 满足约束： \[ g_ 1(x) = x_ 1^2 - x_ 2 \leq 0, \quad g_ 2(x) = x_ 1 + x_ 2 - 2 \leq 0 \] 其中 \(x = (x_ 1, x_ 2)\) 的搜索范围为 \(x_ 1 \in [ 0, 2], x_ 2 \in [ 0, 2]\)。要求使用 自适应网格搜索算法 找到满足约束的近似最优解。 解题步骤 1. 算法原理简介 自适应网格搜索是一种全局优化方法，通过动态调整网格密度来平衡搜索效率与精度。其核心步骤包括： 初始网格生成 ：在搜索空间内均匀划分粗网格。 局部搜索与评估 ：计算每个网格点的目标函数值，并检查约束条件。 网格细化 ：在表现较好的区域（如函数值较小的点附近）加密网格，重复搜索。 终止条件 ：当网格间距小于预设精度或达到最大迭代次数时停止。 2. 初始网格设置 设初始网格间距为 \(h_ 0 = 1\)，将区间 \([ 0,2] \times [ 0,2 ]\) 划分为4个网格点： \[ (0,0), (0,1), (1,0), (1,1), (2,0), (2,1), (0,2), (1,2), (2,2) \] （注意：实际需覆盖所有整数坐标点，此处为简化示例，仅列部分点）。 3. 第一轮网格评估 计算每个点的函数值与约束： 点 \((1,1)\)：\(f=2\)，\(g_ 1=0\)（可行），\(g_ 2=0\)（可行）→ 当前最优解。 点 \((0,0)\)：\(f=5\)，\(g_ 1=0\)（可行），但 \(g_ 2=-2\)（可行）→ 非最优。 点 \((2,2)\)：\(f=1\)，但 \(g_ 1=2>0\)（不可行）→ 淘汰。 记录可行点中的最小目标值：当前最优为 \((1,1)\)，\(f=2\)。 4. 网格自适应细化 以当前最优解 \((1,1)\) 为中心，将周围区域 \([ 0.5,1.5] \times [ 0.5,1.5]\) 细化为间距 \(h_ 1=0.5\) 的新网格。新增点包括： \[ (0.5,0.5), (0.5,1), (1,0.5), (1,1.5), (1.5,1), \dots \] 5. 第二轮评估与迭代 计算新网格点： 点 \((1.2, 0.8)\)：\(f \approx 1.28\)，\(g_ 1=0.64\)（可行），\(g_ 2=0\)（可行）→ 更新最优解。 点 \((0.8, 1.2)\)：\(f \approx 2.08\)，不如当前最优。 重复细化过程，例如在 \((1.2,0.8)\) 附近进一步加密网格，直到网格间距小于阈值（如 \(h < 0.01\)）。 6. 最终结果 通过多次迭代，算法收敛至近似最优解 \(x^* \approx (1.0, 1.0)\)，此时 \(f=2\)，且约束严格满足（\(g_ 1=0, g_ 2=0\)）。实际理论最优解为 \((1,1)\)，验证了算法的有效性。 关键细节说明 约束处理 ：不可行点直接淘汰，仅保留可行点中的最优解。 网格密度 ：初始粗网格避免计算浪费，细化阶段聚焦潜力区域。 收敛性 ：网格间距逐步缩小，确保逼近全局最优解。