非线性规划中的序列二次约束规划法基础题

字数 2443 2025-10-28 01:12:58

非线性规划中的序列二次约束规划法基础题

题目描述：
考虑非线性规划问题：

\[\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^{(0)} = (0, 0)\)。使用序列二次约束规划法求解该问题，逐步逼近最优解。

解题过程：
序列二次约束规划法通过迭代求解一系列二次约束子问题（每个子问题通过线性化约束和二次逼近目标函数构造）来逼近原问题的最优解。以下是详细步骤：

初始化
设定初始点 \(x^{(0)} = (0, 0)\)，容忍误差 \(\epsilon = 10^{-3}\)，迭代计数器 \(k = 0\)。
构造当前迭代的子问题
在点 \(x^{(k)}\) 处，对目标函数 \(f(x)\) 进行二次逼近（例如，使用二阶泰勒展开），对约束 \(g_i(x)\) 进行线性化（一阶泰勒展开）：
- 目标函数逼近：

\[ f(x) \approx f(x^{(k)}) + \nabla f(x^{(k)})^T d + \frac{1}{2} d^T B_k d, \]

 其中 $ d = x - x^{(k)} $，$ B_k $ 是Hessian矩阵 $ \nabla^2 f(x^{(k)}) $ 或其近似（本例中 $ \nabla^2 f(x) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} $ 为常数矩阵）。

约束线性化：

\[ g_i(x) \approx g_i(x^{(k)}) + \nabla g_i(x^{(k)})^T d \leq 0 \quad (i=1,2). \]

子问题形式为：

\[ \min_d \nabla f(x^{(k)})^T d + \frac{1}{2} d^T B_k d, \quad \text{s.t.} \quad g_i(x^{(k)}) + \nabla g_i(x^{(k)})^T d \leq 0. \]

求解子问题
计算当前点 \(x^{(k)}\) 的梯度与约束值：
- \(\nabla f(x) = [2(x_1 - 2), 2(x_2 - 1)]^T\)，在 \(x^{(0)}\) 处为 \(\nabla f = (-4, -2)^T\)。
- \(\nabla g_1(x) = [2x_1, -1]^T\)，在 \(x^{(0)}\) 处为 \((0, -1)^T\)；\(g_1(0,0) = 0\)。
- \(\nabla g_2(x) = [1, 1]^T\)，在 \(x^{(0)}\) 处为 \((1, 1)^T\)；\(g_2(0,0) = -2\)。
  子问题为：

\[ \min_d (-4)d_1 + (-2)d_2 + \frac{1}{2} d^T \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} d, \quad \text{s.t.} \quad 0 + (0)d_1 + (-1)d_2 \leq 0, \quad -2 + (1)d_1 + (1)d_2 \leq 0. \]

简化后：

\[ \min_d d_1^2 + d_2^2 - 4d_1 - 2d_2, \quad \text{s.t.} \quad -d_2 \leq 0, \quad d_1 + d_2 \leq 2. \]

求解得最优解 \(d^* = (1, 1)\)（通过拉格朗日法或数值工具），则新点 \(x^{(1)} = x^{(0)} + d^* = (1, 1)\)。

收敛判断
检查约束违反度或解的变化量：若 \(\|x^{(k+1)} - x^{(k)}\| < \epsilon\)，则停止；否则令 \(k = k+1\) 并返回步骤2。
本例中，\(\|x^{(1)} - x^{(0)}\| = \sqrt{2} > \epsilon\)，继续迭代。
第二次迭代
在 \(x^{(1)} = (1, 1)\) 处：
- \(\nabla f = (-2, 0)^T\)，\(g_1(1,1) = 0\)，\(\nabla g_1 = (2, -1)^T\)，\(g_2(1,1) = 0\)，\(\nabla g_2 = (1, 1)^T\)。
  子问题：

\[ \min_d d_1^2 + d_2^2 - 2d_1, \quad \text{s.t.} \quad 0 + 2d_1 - d_2 \leq 0, \quad 0 + d_1 + d_2 \leq 0. \]

求解得 \(d^* = (0.5, -0.5)\)，\(x^{(2)} = (1.5, 0.5)\)。
检查变化量 \(\|x^{(2)} - x^{(1)}\| = \sqrt{0.5} \approx 0.707 > \epsilon\)，继续迭代。

后续迭代与收敛
重复过程直至变化量小于 \(\epsilon\)。最终逼近最优解 \(x^* \approx (1, 1)\)，满足约束（\(g_1(1,1)=0\), \(g_2(1,1)=0\)），目标函数值 \(f^* = 1\)。

总结：该方法通过序列化二次约束问题，逐步线性化约束并二次逼近目标，确保每次迭代可行且收敛到局部最优解。

非线性规划中的序列二次约束规划法基础题题目描述：考虑非线性规划问题： \[ \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^{(0)} = (0, 0) \)。使用序列二次约束规划法求解该问题，逐步逼近最优解。解题过程：序列二次约束规划法通过迭代求解一系列二次约束子问题（每个子问题通过线性化约束和二次逼近目标函数构造）来逼近原问题的最优解。以下是详细步骤：初始化设定初始点 \( x^{(0)} = (0, 0) \)，容忍误差 \( \epsilon = 10^{-3} \)，迭代计数器 \( k = 0 \)。构造当前迭代的子问题在点 \( x^{(k)} \) 处，对目标函数 \( f(x) \) 进行二次逼近（例如，使用二阶泰勒展开），对约束 \( g_ i(x) \) 进行线性化（一阶泰勒展开）：目标函数逼近： \[ f(x) \approx f(x^{(k)}) + \nabla f(x^{(k)})^T d + \frac{1}{2} d^T B_ k d, \] 其中 \( d = x - x^{(k)} \)，\( B_ k \) 是Hessian矩阵 \( \nabla^2 f(x^{(k)}) \) 或其近似（本例中 \( \nabla^2 f(x) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} \) 为常数矩阵）。约束线性化： \[ g_ i(x) \approx g_ i(x^{(k)}) + \nabla g_ i(x^{(k)})^T d \leq 0 \quad (i=1,2). \] 子问题形式为： \[ \min_ d \nabla f(x^{(k)})^T d + \frac{1}{2} d^T B_ k d, \quad \text{s.t.} \quad g_ i(x^{(k)}) + \nabla g_ i(x^{(k)})^T d \leq 0. \] 求解子问题计算当前点 \( x^{(k)} \) 的梯度与约束值： \( \nabla f(x) = [ 2(x_ 1 - 2), 2(x_ 2 - 1) ]^T \)，在 \( x^{(0)} \) 处为 \( \nabla f = (-4, -2)^T \)。 \( \nabla g_ 1(x) = [ 2x_ 1, -1]^T \)，在 \( x^{(0)} \) 处为 \( (0, -1)^T \)；\( g_ 1(0,0) = 0 \)。 \( \nabla g_ 2(x) = [ 1, 1]^T \)，在 \( x^{(0)} \) 处为 \( (1, 1)^T \)；\( g_ 2(0,0) = -2 \)。子问题为： \[ \min_ d (-4)d_ 1 + (-2)d_ 2 + \frac{1}{2} d^T \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} d, \quad \text{s.t.} \quad 0 + (0)d_ 1 + (-1)d_ 2 \leq 0, \quad -2 + (1)d_ 1 + (1)d_ 2 \leq 0. \] 简化后： \[ \min_ d d_ 1^2 + d_ 2^2 - 4d_ 1 - 2d_ 2, \quad \text{s.t.} \quad -d_ 2 \leq 0, \quad d_ 1 + d_ 2 \leq 2. \] 求解得最优解 \( d^* = (1, 1) \)（通过拉格朗日法或数值工具），则新点 \( x^{(1)} = x^{(0)} + d^* = (1, 1) \)。收敛判断检查约束违反度或解的变化量：若 \( \|x^{(k+1)} - x^{(k)}\| < \epsilon \)，则停止；否则令 \( k = k+1 \) 并返回步骤2。本例中，\( \|x^{(1)} - x^{(0)}\| = \sqrt{2} > \epsilon \)，继续迭代。第二次迭代在 \( x^{(1)} = (1, 1) \) 处： \( \nabla f = (-2, 0)^T \)，\( g_ 1(1,1) = 0 \)，\( \nabla g_ 1 = (2, -1)^T \)，\( g_ 2(1,1) = 0 \)，\( \nabla g_ 2 = (1, 1)^T \)。子问题： \[ \min_ d d_ 1^2 + d_ 2^2 - 2d_ 1, \quad \text{s.t.} \quad 0 + 2d_ 1 - d_ 2 \leq 0, \quad 0 + d_ 1 + d_ 2 \leq 0. \] 求解得 \( d^* = (0.5, -0.5) \)，\( x^{(2)} = (1.5, 0.5) \)。检查变化量 \( \|x^{(2)} - x^{(1)}\| = \sqrt{0.5} \approx 0.707 > \epsilon \)，继续迭代。后续迭代与收敛重复过程直至变化量小于 \( \epsilon \)。最终逼近最优解 \( x^* \approx (1, 1) \)，满足约束（\( g_ 1(1,1)=0 \), \( g_ 2(1,1)=0 \)），目标函数值 \( f^* = 1 \)。总结：该方法通过序列化二次约束问题，逐步线性化约束并二次逼近目标，确保每次迭代可行且收敛到局部最优解。