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

字数 3098 2025-10-26 21:06:54

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

题目描述
考虑非线性规划问题：
最小化 \(f(x) = (x_1 - 2)^2 + (x_2 - 1)^2\)
满足约束：
\(g_1(x) = x_1 + x_2 - 2 \leq 0\)
\(g_2(x) = x_1^2 - x_2 \leq 0\)
初始点为 \(x^{(0)} = (0, 0)\)。

要求使用序列二次规划（SQP）法求解该问题，详细展示第一次迭代的计算步骤。

解题过程

SQP法通过求解一系列二次规划子问题来逼近原问题。每个子问题基于当前迭代点的拉格朗日函数二阶近似和约束一阶近似构建。

问题重构
- 目标函数 \(f(x)\) 和约束 \(g_1(x), g_2(x)\) 均为二次函数，但SQP法将其视为一般非线性函数处理。
- 拉格朗日函数：\(L(x, \lambda) = f(x) + \lambda_1 g_1(x) + \lambda_2 g_2(x)\)，其中 \(\lambda = (\lambda_1, \lambda_2)\) 为拉格朗日乘子。
初始点设置
- \(x^{(0)} = (0, 0)\)，初始乘子 \(\lambda^{(0)} = (0, 0)\)（通常假设为0）。
- 计算初始点函数值：
  - \(f(x^{(0)}) = (0-2)^2 + (0-1)^2 = 4 + 1 = 5\)
  - \(g_1(x^{(0)}) = 0 + 0 - 2 = -2 \leq 0\)（满足）
  - \(g_2(x^{(0)}) = 0^2 - 0 = 0 \leq 0\)（满足，为积极约束）
构建第一次迭代的二次规划子问题
- 子问题形式：最小化 \(\nabla f(x^{(0)})^T d + \frac{1}{2} d^T H^{(0)} d\)
  满足 \(\nabla g_i(x^{(0)})^T d + g_i(x^{(0)}) \leq 0 \quad (i=1,2)\)
  其中 \(d = x - x^{(0)}\) 为搜索方向，\(H^{(0)}\) 为拉格朗日函数海森矩阵的近似（初始常取单位矩阵）。
- 计算梯度：
  - \(\nabla f(x) = [2(x_1 - 2), 2(x_2 - 1)]^T\)，在 \(x^{(0)}\) 处：\(\nabla f(x^{(0)}) = [-4, -2]^T\)
  - \(\nabla g_1(x) = [1, 1]^T\)（常数）
  - \(\nabla g_2(x) = [2x_1, -1]^T\)，在 \(x^{(0)}\) 处：\([0, -1]^T\)
- 海森矩阵近似：取 \(H^{(0)} = I\)（单位矩阵）作为初始近似。
- 子问题具体形式：
  最小化 \([-4, -2] d + \frac{1}{2} d^T I d\)
  满足约束：
  \([1, 1] d - 2 \leq 0\)（来自 \(g_1\)）
  \([0, -1] d + 0 \leq 0\)（来自 \(g_2\)）
  化简目标函数：\(-4d_1 - 2d_2 + \frac{1}{2} (d_1^2 + d_2^2)\)
  约束：
  \(d_1 + d_2 \leq 2\)
  \(-d_2 \leq 0\) 即 \(d_2 \geq 0\)
求解二次规划子问题
- 子问题为凸二次规划（因 \(H^{(0)} = I \succ 0\)）。
- 通过拉格朗日法或KKT条件求解：
  - 拉格朗日函数：\(\mathcal{L}(d, \mu) = -4d_1 - 2d_2 + \frac{1}{2}(d_1^2 + d_2^2) + \mu_1(d_1 + d_2 - 2) + \mu_2(-d_2)\)
  - KKT条件：
    - 梯度条件：\(\frac{\partial \mathcal{L}}{\partial d_1} = -4 + d_1 + \mu_1 = 0\)
      \(\frac{\partial \mathcal{L}}{\partial d_2} = -2 + d_2 + \mu_1 - \mu_2 = 0\)
    - 互补松弛：\(\mu_1(d_1 + d_2 - 2) = 0\), \(\mu_2(-d_2) = 0\)
    - 可行性：\(d_1 + d_2 \leq 2\), \(d_2 \geq 0\)
    - 非负性：\(\mu_1, \mu_2 \geq 0\)
- 试探约束活跃情况：
  - 若 \(\mu_2 > 0\)，则 \(d_2 = 0\)；若 \(\mu_1 > 0\)，则 \(d_1 + d_2 = 2\)。
  - 尝试仅 \(g_2\) 积极（即 \(d_2 = 0\), \(\mu_1 = 0\)）：
    梯度条件1：\(-4 + d_1 + 0 = 0 \Rightarrow d_1 = 4\)
    梯度条件2：\(-2 + 0 + 0 - \mu_2 = 0 \Rightarrow \mu_2 = -2 < 0\)（违反非负性，舍去）
  - 尝试 \(g_1\) 和 \(g_2\) 均积极（即 \(d_2 = 0\), \(d_1 + 0 = 2 \Rightarrow d_1 = 2\)）：
    梯度条件1：\(-4 + 2 + \mu_1 = 0 \Rightarrow \mu_1 = 2 > 0\)
    梯度条件2：\(-2 + 0 + 2 - \mu_2 = 0 \Rightarrow \mu_2 = 0\)
    检查可行性：\(d_1 + d_2 = 2 + 0 = 2 \leq 2\)（紧），\(d_2 = 0 \geq 0\)（紧）。满足所有条件。
  - 解为：\(d^{(1)} = (2, 0)\), \(\mu_1 = 2\), \(\mu_2 = 0\)。
更新迭代点
- 搜索方向 \(d^{(1)} = (2, 0)\)。
- 新点 \(x^{(1)} = x^{(0)} + d^{(1)} = (0+2, 0+0) = (2, 0)\)。
- 乘子更新：\(\lambda^{(1)} = \mu = (2, 0)\)（子问题的乘子作为原问题乘子的新估计）。
第一次迭代结果
- \(x^{(1)} = (2, 0)\), \(\lambda^{(1)} = (2, 0)\)
- 函数值：\(f(x^{(1)}) = (2-2)^2 + (0-1)^2 = 0 + 1 = 1\)
- 约束：\(g_1(x^{(1)}) = 2 + 0 - 2 = 0\)（积极），\(g_2(x^{(1)}) = 2^2 - 0 = 4 > 0\)（违反！）

说明

第一次迭代后约束 \(g_2\) 被违反，这是因为子问题中海森矩阵近似（单位矩阵）不准确，且约束线性化在非凸区域可能失效。
实际SQP中需通过线搜索或信赖域策略保证收敛，并更新海森矩阵（如BFGS公式）。本例展示了SQP法的基本步骤和潜在问题。

非线性规划中的序列二次规划法基础题题目描述考虑非线性规划问题：最小化 \( f(x) = (x_ 1 - 2)^2 + (x_ 2 - 1)^2 \) 满足约束： \( g_ 1(x) = x_ 1 + x_ 2 - 2 \leq 0 \) \( g_ 2(x) = x_ 1^2 - x_ 2 \leq 0 \) 初始点为 \( x^{(0)} = (0, 0) \)。要求使用序列二次规划（SQP）法求解该问题，详细展示第一次迭代的计算步骤。解题过程 SQP法通过求解一系列二次规划子问题来逼近原问题。每个子问题基于当前迭代点的拉格朗日函数二阶近似和约束一阶近似构建。问题重构目标函数 \( f(x) \) 和约束 \( g_ 1(x), g_ 2(x) \) 均为二次函数，但SQP法将其视为一般非线性函数处理。拉格朗日函数：\( L(x, \lambda) = f(x) + \lambda_ 1 g_ 1(x) + \lambda_ 2 g_ 2(x) \)，其中 \( \lambda = (\lambda_ 1, \lambda_ 2) \) 为拉格朗日乘子。初始点设置 \( x^{(0)} = (0, 0) \)，初始乘子 \( \lambda^{(0)} = (0, 0) \)（通常假设为0）。计算初始点函数值： \( f(x^{(0)}) = (0-2)^2 + (0-1)^2 = 4 + 1 = 5 \) \( g_ 1(x^{(0)}) = 0 + 0 - 2 = -2 \leq 0 \)（满足） \( g_ 2(x^{(0)}) = 0^2 - 0 = 0 \leq 0 \)（满足，为积极约束）构建第一次迭代的二次规划子问题子问题形式：最小化 \( \nabla f(x^{(0)})^T d + \frac{1}{2} d^T H^{(0)} d \) 满足 \( \nabla g_ i(x^{(0)})^T d + g_ i(x^{(0)}) \leq 0 \quad (i=1,2) \) 其中 \( d = x - x^{(0)} \) 为搜索方向，\( H^{(0)} \) 为拉格朗日函数海森矩阵的近似（初始常取单位矩阵）。计算梯度： \( \nabla f(x) = [ 2(x_ 1 - 2), 2(x_ 2 - 1)]^T \)，在 \( x^{(0)} \) 处：\( \nabla f(x^{(0)}) = [ -4, -2 ]^T \) \( \nabla g_ 1(x) = [ 1, 1 ]^T \)（常数） \( \nabla g_ 2(x) = [ 2x_ 1, -1]^T \)，在 \( x^{(0)} \) 处：\( [ 0, -1 ]^T \) 海森矩阵近似：取 \( H^{(0)} = I \)（单位矩阵）作为初始近似。子问题具体形式：最小化 \( [ -4, -2 ] d + \frac{1}{2} d^T I d \) 满足约束： \( [ 1, 1] d - 2 \leq 0 \)（来自 \( g_ 1 \)） \( [ 0, -1] d + 0 \leq 0 \)（来自 \( g_ 2 \)）化简目标函数：\( -4d_ 1 - 2d_ 2 + \frac{1}{2} (d_ 1^2 + d_ 2^2) \) 约束： \( d_ 1 + d_ 2 \leq 2 \) \( -d_ 2 \leq 0 \) 即 \( d_ 2 \geq 0 \) 求解二次规划子问题子问题为凸二次规划（因 \( H^{(0)} = I \succ 0 \)）。通过拉格朗日法或KKT条件求解：拉格朗日函数：\( \mathcal{L}(d, \mu) = -4d_ 1 - 2d_ 2 + \frac{1}{2}(d_ 1^2 + d_ 2^2) + \mu_ 1(d_ 1 + d_ 2 - 2) + \mu_ 2(-d_ 2) \) KKT条件：梯度条件：\( \frac{\partial \mathcal{L}}{\partial d_ 1} = -4 + d_ 1 + \mu_ 1 = 0 \) \( \frac{\partial \mathcal{L}}{\partial d_ 2} = -2 + d_ 2 + \mu_ 1 - \mu_ 2 = 0 \) 互补松弛：\( \mu_ 1(d_ 1 + d_ 2 - 2) = 0 \), \( \mu_ 2(-d_ 2) = 0 \) 可行性：\( d_ 1 + d_ 2 \leq 2 \), \( d_ 2 \geq 0 \) 非负性：\( \mu_ 1, \mu_ 2 \geq 0 \) 试探约束活跃情况：若 \( \mu_ 2 > 0 \)，则 \( d_ 2 = 0 \)；若 \( \mu_ 1 > 0 \)，则 \( d_ 1 + d_ 2 = 2 \)。尝试仅 \( g_ 2 \) 积极（即 \( d_ 2 = 0 \), \( \mu_ 1 = 0 \)）：梯度条件1：\( -4 + d_ 1 + 0 = 0 \Rightarrow d_ 1 = 4 \) 梯度条件2：\( -2 + 0 + 0 - \mu_ 2 = 0 \Rightarrow \mu_ 2 = -2 < 0 \)（违反非负性，舍去）尝试 \( g_ 1 \) 和 \( g_ 2 \) 均积极（即 \( d_ 2 = 0 \), \( d_ 1 + 0 = 2 \Rightarrow d_ 1 = 2 \)）：梯度条件1：\( -4 + 2 + \mu_ 1 = 0 \Rightarrow \mu_ 1 = 2 > 0 \) 梯度条件2：\( -2 + 0 + 2 - \mu_ 2 = 0 \Rightarrow \mu_ 2 = 0 \) 检查可行性：\( d_ 1 + d_ 2 = 2 + 0 = 2 \leq 2 \)（紧），\( d_ 2 = 0 \geq 0 \)（紧）。满足所有条件。解为：\( d^{(1)} = (2, 0) \), \( \mu_ 1 = 2 \), \( \mu_ 2 = 0 \)。更新迭代点搜索方向 \( d^{(1)} = (2, 0) \)。新点 \( x^{(1)} = x^{(0)} + d^{(1)} = (0+2, 0+0) = (2, 0) \)。乘子更新：\( \lambda^{(1)} = \mu = (2, 0) \)（子问题的乘子作为原问题乘子的新估计）。第一次迭代结果 \( x^{(1)} = (2, 0) \), \( \lambda^{(1)} = (2, 0) \) 函数值：\( f(x^{(1)}) = (2-2)^2 + (0-1)^2 = 0 + 1 = 1 \) 约束：\( g_ 1(x^{(1)}) = 2 + 0 - 2 = 0 \)（积极），\( g_ 2(x^{(1)}) = 2^2 - 0 = 4 > 0 \)（违反！）说明第一次迭代后约束 \( g_ 2 \) 被违反，这是因为子问题中海森矩阵近似（单位矩阵）不准确，且约束线性化在非凸区域可能失效。实际SQP中需通过线搜索或信赖域策略保证收敛，并更新海森矩阵（如BFGS公式）。本例展示了SQP法的基本步骤和潜在问题。