非线性规划中的序列二次规划-乘子法-积极集-过滤器混合算法基础题

字数 3272 2025-11-05 23:45:49

非线性规划中的序列二次规划-乘子法-积极集-过滤器混合算法基础题

题目描述
考虑一个非线性规划问题：
最小化 \(f(x) = (x_1 - 2)^2 + (x_2 - 1)^2\)
约束条件为：
\(g_1(x) = x_1^2 - x_2 \leq 0\)
\(g_2(x) = x_1 + x_2 - 2 \leq 0\)
初始点为 \(x^{(0)} = (0, 0)\)。
要求使用序列二次规划-乘子法-积极集-过滤器混合算法求解该问题，确保在迭代中平衡约束违反与目标函数下降。

解题过程
1. 算法框架理解
该混合算法结合以下组件：

序列二次规划（SQP）：在每步用二次模型近似目标函数，线性化约束。
乘子法：通过拉格朗日乘子处理约束，避免罚函数数值病态。
积极集法：动态识别起作用的约束，减少计算量。
过滤器法：替代传统罚函数，允许迭代在目标下降和约束违反之间权衡。

核心思想：每步求解一个二次规划子问题，其目标函数基于拉格朗日函数的二阶近似，约束为原约束的线性化。乘子法更新拉格朗日乘子，积极集法确定有效约束，过滤器法决定是否接受新迭代点。

2. 初始化

初始点 \(x^{(0)} = (0, 0)\)，乘子估计 \(\lambda^{(0)} = (0, 0)\)，过滤器 \(\mathcal{F} = \emptyset\)（空集）。
计算初始约束违反度 \(h(x^{(0)}) = \max(0, g_1(x^{(0)}), g_2(x^{(0)})) = \max(0, 0, -2) = 0\)。
拉格朗日函数 \(L(x, \lambda) = f(x) + \lambda_1 g_1(x) + \lambda_2 g_2(x)\)。

3. 第k次迭代步骤
步骤3.1 构建二次规划子问题
在当前点 \(x^{(k)}\) 和乘子 \(\lambda^{(k)}\) 下：

目标函数近似：
\(Q^{(k)}(d) = \nabla f(x^{(k)})^T d + \frac{1}{2} d^T B^{(k)} d\)，
其中 \(B^{(k)}\) 是拉格朗日函数Hessian的近似（本例中精确Hessian为常数矩阵：
\(\nabla^2 L = \begin{bmatrix} 2 + 2\lambda_1 & 0 \\ 0 & 2 \end{bmatrix}\)，初始时 \(\lambda_1=0\)，故 \(B^{(0)} = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}\)。
约束线性化：
\(\nabla g_1(x^{(k)})^T d + g_1(x^{(k)}) \leq 0\)，
\(\nabla g_2(x^{(k)})^T d + g_2(x^{(k)}) \leq 0\)。

步骤3.2 积极集识别
检查约束违反程度：

若 \(g_i(x^{(k)}) \geq -\epsilon\)（例如 \(\epsilon = 10^{-6}\)），则标记为积极约束。
在 \(x^{(0)} = (0,0)\)：
\(g_1(0,0) = 0\)（积极），\(g_2(0,0) = -2\)（非积极）。
子问题仅包含积极约束的线性化。

步骤3.3 求解二次规划子问题
求解 \(\min_d Q^{(k)}(d)\) 满足线性化积极约束。

在 \(x^{(0)}\)：
\(\nabla f(0,0) = (-4, -2)\)，
\(\nabla g_1(0,0) = (0, -1)\)，线性化约束为 \(-d_2 + 0 \leq 0\)。
子问题：
\(\min_d [-4, -2] d + \frac{1}{2} d^T \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} d\)
约束： \(d_2 \geq 0\)。
解此凸二次规划得 \(d^{(0)} = (2, 0)\)（忽略约束时无约束极小点为 \((2,1)\)，但需满足 \(d_2 \geq 0\)）。

步骤3.4 更新乘子（乘子法）
使用子问题的解更新乘子：
\(\lambda_i^{(k+1)} = \max(0, \lambda_i^{(k)} + \mu g_i(x^{(k)} + d^{(k)}))\)，
其中 \(\mu > 0\) 为罚参数（例如 \(\mu = 1\)）。
计算 \(x^{(1)} = x^{(0)} + d^{(0)} = (2, 0)\)：
\(g_1(2,0) = 4\)（违反），\(g_2(2,0) = 0\)（积极）。
更新：
\(\lambda_1^{(1)} = \max(0, 0 + 1 \cdot 4) = 4\)，
\(\lambda_2^{(1)} = \max(0, 0 + 1 \cdot 0) = 0\)。

步骤3.5 过滤器判断
定义两指标：

目标函数值 \(f(x)\)
约束违反度 \(h(x) = \max(0, g_1(x), g_2(x))\)
新点 \(x^{(1)}\) 的 \(f = (2-2)^2 + (0-1)^2 = 1\)，\(h = \max(0, 4, 0) = 4\)。
检查是否被过滤器 \(\mathcal{F}\) 支配（即存在旧点 \((f_j, h_j)\) 满足 \(f_j \leq f\) 且 \(h_j \leq h\) 且至少一个严格不等）。
初始过滤器为空，接受 \(x^{(1)}\)，加入过滤器： \(\mathcal{F} = \{ (f=1, h=4) \}\)。

4. 迭代继续
重复步骤3，更新二次规划子问题：

在 \(x^{(1)} = (2,0)\)，Hessian需加入乘子项： \(B = \begin{bmatrix} 2+2\lambda_1 & 0 \\ 0 & 2 \end{bmatrix} = \begin{bmatrix} 10 & 0 \\ 0 & 2 \end{bmatrix}\)。
积极约束： \(g_1\) 和 \(g_2\) 均积极（因 \(g_1=4>0\)，\(g_2=0\)）。
线性化约束：
\(\nabla g_1 = (4, -1) \Rightarrow 4d_1 - d_2 + 4 \leq 0\)
\(\nabla g_2 = (1, 1) \Rightarrow d_1 + d_2 + 0 \leq 0\)。
求解子问题得 \(d^{(1)}\)，更新 \(x^{(2)}\)，调整乘子和过滤器。
经数次迭代后，收敛至满足KKT条件的点 \(x^* \approx (1, 1)\)（实际解： \(g_1(1,1)=0\)，\(g_2(1,1)=0\)，\(f=1\)）。

5. 收敛判断
当 \(\| d^{(k)} \| < \delta\)（如 \(\delta = 10^{-6}\)）且约束违反度 \(h(x^{(k)}) < \epsilon\) 时停止。
最终解满足一阶必要性条件： \(\nabla f + \lambda_1 \nabla g_1 + \lambda_2 \nabla g_2 = 0\)，\(\lambda_i \geq 0\)。

非线性规划中的序列二次规划-乘子法-积极集-过滤器混合算法基础题题目描述考虑一个非线性规划问题：最小化 \( f(x) = (x_ 1 - 2)^2 + (x_ 2 - 1)^2 \) 约束条件为： \( g_ 1(x) = x_ 1^2 - x_ 2 \leq 0 \) \( g_ 2(x) = x_ 1 + x_ 2 - 2 \leq 0 \) 初始点为 \( x^{(0)} = (0, 0) \)。要求使用序列二次规划-乘子法-积极集-过滤器混合算法求解该问题，确保在迭代中平衡约束违反与目标函数下降。解题过程 1. 算法框架理解该混合算法结合以下组件：序列二次规划（SQP）：在每步用二次模型近似目标函数，线性化约束。乘子法：通过拉格朗日乘子处理约束，避免罚函数数值病态。积极集法：动态识别起作用的约束，减少计算量。过滤器法：替代传统罚函数，允许迭代在目标下降和约束违反之间权衡。核心思想：每步求解一个二次规划子问题，其目标函数基于拉格朗日函数的二阶近似，约束为原约束的线性化。乘子法更新拉格朗日乘子，积极集法确定有效约束，过滤器法决定是否接受新迭代点。 2. 初始化初始点 \( x^{(0)} = (0, 0) \)，乘子估计 \( \lambda^{(0)} = (0, 0) \)，过滤器 \( \mathcal{F} = \emptyset \)（空集）。计算初始约束违反度 \( h(x^{(0)}) = \max(0, g_ 1(x^{(0)}), g_ 2(x^{(0)})) = \max(0, 0, -2) = 0 \)。拉格朗日函数 \( L(x, \lambda) = f(x) + \lambda_ 1 g_ 1(x) + \lambda_ 2 g_ 2(x) \)。 3. 第k次迭代步骤步骤3.1 构建二次规划子问题在当前点 \( x^{(k)} \) 和乘子 \( \lambda^{(k)} \) 下：目标函数近似： \( Q^{(k)}(d) = \nabla f(x^{(k)})^T d + \frac{1}{2} d^T B^{(k)} d \)，其中 \( B^{(k)} \) 是拉格朗日函数Hessian的近似（本例中精确Hessian为常数矩阵： \( \nabla^2 L = \begin{bmatrix} 2 + 2\lambda_ 1 & 0 \\ 0 & 2 \end{bmatrix} \)，初始时 \( \lambda_ 1=0 \)，故 \( B^{(0)} = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} \)。约束线性化： \( \nabla g_ 1(x^{(k)})^T d + g_ 1(x^{(k)}) \leq 0 \)， \( \nabla g_ 2(x^{(k)})^T d + g_ 2(x^{(k)}) \leq 0 \)。步骤3.2 积极集识别检查约束违反程度：若 \( g_ i(x^{(k)}) \geq -\epsilon \)（例如 \( \epsilon = 10^{-6} \)），则标记为积极约束。在 \( x^{(0)} = (0,0) \)： \( g_ 1(0,0) = 0 \)（积极），\( g_ 2(0,0) = -2 \)（非积极）。子问题仅包含积极约束的线性化。步骤3.3 求解二次规划子问题求解 \( \min_ d Q^{(k)}(d) \) 满足线性化积极约束。在 \( x^{(0)} \)： \( \nabla f(0,0) = (-4, -2) \)， \( \nabla g_ 1(0,0) = (0, -1) \)，线性化约束为 \( -d_ 2 + 0 \leq 0 \)。子问题： \( \min_ d [ -4, -2 ] d + \frac{1}{2} d^T \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} d \) 约束： \( d_ 2 \geq 0 \)。解此凸二次规划得 \( d^{(0)} = (2, 0) \)（忽略约束时无约束极小点为 \( (2,1) \)，但需满足 \( d_ 2 \geq 0 \)）。步骤3.4 更新乘子（乘子法）使用子问题的解更新乘子： \( \lambda_ i^{(k+1)} = \max(0, \lambda_ i^{(k)} + \mu g_ i(x^{(k)} + d^{(k)})) \)，其中 \( \mu > 0 \) 为罚参数（例如 \( \mu = 1 \)）。计算 \( x^{(1)} = x^{(0)} + d^{(0)} = (2, 0) \)： \( g_ 1(2,0) = 4 \)（违反），\( g_ 2(2,0) = 0 \)（积极）。更新： \( \lambda_ 1^{(1)} = \max(0, 0 + 1 \cdot 4) = 4 \)， \( \lambda_ 2^{(1)} = \max(0, 0 + 1 \cdot 0) = 0 \)。步骤3.5 过滤器判断定义两指标：目标函数值 \( f(x) \) 约束违反度 \( h(x) = \max(0, g_ 1(x), g_ 2(x)) \) 新点 \( x^{(1)} \) 的 \( f = (2-2)^2 + (0-1)^2 = 1 \)，\( h = \max(0, 4, 0) = 4 \)。检查是否被过滤器 \( \mathcal{F} \) 支配（即存在旧点 \( (f_ j, h_ j) \) 满足 \( f_ j \leq f \) 且 \( h_ j \leq h \) 且至少一个严格不等）。初始过滤器为空，接受 \( x^{(1)} \)，加入过滤器： \( \mathcal{F} = \{ (f=1, h=4) \} \)。 4. 迭代继续重复步骤3，更新二次规划子问题：在 \( x^{(1)} = (2,0) \)，Hessian需加入乘子项： \( B = \begin{bmatrix} 2+2\lambda_ 1 & 0 \\ 0 & 2 \end{bmatrix} = \begin{bmatrix} 10 & 0 \\ 0 & 2 \end{bmatrix} \)。积极约束： \( g_ 1 \) 和 \( g_ 2 \) 均积极（因 \( g_ 1=4>0 \)，\( g_ 2=0 \)）。线性化约束： \( \nabla g_ 1 = (4, -1) \Rightarrow 4d_ 1 - d_ 2 + 4 \leq 0 \) \( \nabla g_ 2 = (1, 1) \Rightarrow d_ 1 + d_ 2 + 0 \leq 0 \)。求解子问题得 \( d^{(1)} \)，更新 \( x^{(2)} \)，调整乘子和过滤器。经数次迭代后，收敛至满足KKT条件的点 \( x^* \approx (1, 1) \)（实际解： \( g_ 1(1,1)=0 \)，\( g_ 2(1,1)=0 \)，\( f=1 \)）。 5. 收敛判断当 \( \| d^{(k)} \| < \delta \)（如 \( \delta = 10^{-6} \)）且约束违反度 \( h(x^{(k)}) < \epsilon \) 时停止。最终解满足一阶必要性条件： \( \nabla f + \lambda_ 1 \nabla g_ 1 + \lambda_ 2 \nabla g_ 2 = 0 \)，\( \lambda_ i \geq 0 \)。