非线性规划中的序列凸规划(SCP)与自适应步长结合的基础题

字数 4685 2025-12-06 20:52:39

非线性规划中的序列凸规划(SCP)与自适应步长结合的基础题

题目描述
我们考虑如下形式的非线性规划问题：

\[\begin{aligned} \min_{x \in \mathbb{R}^n} \quad & f(x) \\ \text{s.t.} \quad & g_i(x) \le 0, \quad i = 1, \dots, m, \\ & h_j(x) = 0, \quad j = 1, \dots, p, \end{aligned} \]

其中，目标函数 \(f(x)\) 和约束函数 \(g_i(x), h_j(x)\) 均为非线性、非凸的，但一阶和二阶信息（梯度、Hessian 矩阵）在可行域内可计算。为高效求解该问题，我们将序列凸规划（SCP）与自适应步长控制结合。在每一步迭代，我们用当前迭代点 \(x^k\) 处的凸近似（例如，通过一阶泰勒展开构造局部凸模型）替代原非凸函数，形成一个凸子问题，求解该子问题得到搜索方向 \(d^k\)。之后，通过一个自适应步长 \(\alpha_k \in (0,1]\) 更新迭代点：\(x^{k+1} = x^k + \alpha_k d^k\)。步长 \(\alpha_k\) 通过一个简单的回溯线搜索条件自适应调整，确保目标函数有“充分下降”，并尽可能保持可行性。该方法避免了直接求解大规模非凸问题，通过一系列凸优化逐步逼近局部最优解。

解题过程

我们将解题过程分解为以下步骤，并逐步详细说明。

步骤1：理解算法框架
序列凸规划的核心思想是“序列凸逼近”，即在每个迭代点 \(x^k\) 处，用凸模型近似原非凸函数。常用的凸模型包括：

目标函数 \(f(x)\) 用其在 \(x^k\) 处的二阶泰勒展开近似，但需保证 Hessian 矩阵是正定的（若非正定，可修正为 \(B^k \succ 0\)，例如用拟牛顿法更新 \(B^k\)）。
对于非线性约束 \(g_i(x) \le 0\) 和 \(h_j(x) = 0\)，用一阶泰勒展开近似，从而得到线性约束。

这样，每一步的子问题是一个凸优化问题（通常是二次规划或线性约束凸问题），易于求解。但为了确保逼近的精度和收敛性，需要限制迭代步长，因此引入“信任域”或“移动限制”。本题中，我们用自适应步长 \(\alpha_k\) 来控制步进幅度。

步骤2：构造第 k 步的凸子问题
在迭代点 \(x^k\) 处，构造如下凸子问题（以二次规划为例）：

\[\begin{aligned} \min_{d \in \mathbb{R}^n} \quad & \nabla f(x^k)^\top d + \frac{1}{2} d^\top B^k d \\ \text{s.t.} \quad & g_i(x^k) + \nabla g_i(x^k)^\top d \le 0, \quad i = 1, \dots, m, \\ & h_j(x^k) + \nabla h_j(x^k)^\top d = 0, \quad j = 1, \dots, p, \\ & \|d\|_\infty \le \Delta_k. \end{aligned} \]

这里：

\(d = x - x^k\) 是搜索方向。
\(B^k\) 是正定矩阵，可以是 \(f(x)\) 在 \(x^k\) 处的 Hessian 矩阵，或通过 BFGS 等拟牛顿法得到的正定近似。
不等式约束和等式约束通过一阶线性化近似，保证了子问题是凸的（因为目标函数是凸二次函数，约束是线性的）。
额外增加一个“移动限制” \(\|d\|_\infty \le \Delta_k\)，其中 \(\Delta_k > 0\) 是信任域半径，用以控制每一步的移动范围，保证近似模型的准确性。本题中，我们用自适应步长 \(\alpha_k\) 间接控制移动范围，因此在子问题中可不显式包含 \(\|d\|_\infty \le \Delta_k\)，而是通过步长 \(\alpha_k\) 在更新时缩放 \(d^k\)。

为简化，我们考虑子问题中不显式包含移动限制，但通过求解得到方向 \(d^k\) 后，再用步长 \(\alpha_k\) 缩放。那么子问题简化为：

这是一个标准的凸二次规划（QP），可以用内点法、积极集法等有效求解。

步骤3：求解凸子问题得到搜索方向
对上述 QP 求解，得到最优解 \(d^k\)。如果子问题不可行，说明当前点 \(x^k\) 附近无可行下降方向，算法可能需要调整信任域半径或采用可行性恢复策略。在基础题中，我们假设子问题总是可行的。

步骤4：自适应步长选择
得到 \(d^k\) 后，我们不直接取 \(x^{k+1} = x^k + d^k\)，而是用步长 \(\alpha_k \in (0,1]\) 缩放更新：

\[ x^{k+1} = x^k + \alpha_k d^k. \]

步长 \(\alpha_k\) 的选择需要满足两个条件：

充分下降条件：确保目标函数值下降足够多，即

\[ f(x^k + \alpha_k d^k) \le f(x^k) + c_1 \alpha_k \nabla f(x^k)^\top d^k, \]

其中 \(c_1 \in (0,1)\) 是一个常数（例如 \(c_1 = 10^{-4}\)）。该条件称为 Armijo 条件，保证目标函数值下降比例不小于方向导数乘以步长的一个比例。
2. 可行性条件：尽量不破坏约束。由于子问题的约束是线性近似，实际非线性约束在 \(x^k + \alpha d^k\) 处可能被违反。因此，我们要求步长 \(\alpha_k\) 满足：

\[ g_i(x^k + \alpha_k d^k) \le 0 + \epsilon_{\text{feas}}, \quad h_j(x^k + \alpha_k d^k) = 0 \pm \epsilon_{\text{feas}}, \]

其中 \(\epsilon_{\text{feas}} > 0\) 是一个小的可行性容差。在实际中，我们可定义一个“可行性违背度”函数：

\[ \Phi(x) = \sum_{i=1}^m \max(0, g_i(x)) + \sum_{j=1}^p |h_j(x)|, \]

并希望 \(\Phi(x^{k+1}) \le \eta_k\)，其中 \(\eta_k\) 是逐步收紧的可行性容忍度。

自适应步长的选取通过回溯线搜索进行：初始步长设为 \(\alpha = 1\)，若上述两个条件不满足，则令 \(\alpha := \beta \alpha\)（其中 \(\beta \in (0,1)\)，如 \(\beta=0.5\)），重复检查直到条件满足。在基础题中，我们重点关注充分下降条件，对可行性条件可放宽，即允许轻微违反，但最终需趋于可行。

步骤5：更新迭代点与算法参数
确定步长 \(\alpha_k\) 后，更新 \(x^{k+1} = x^k + \alpha_k d^k\)。然后，更新拟牛顿矩阵 \(B^{k+1}\)（例如用 BFGS 更新），以便下一次迭代构造更好的凸模型。如果步长 \(\alpha_k\) 很小（例如小于某个阈值 \(\alpha_{\min}\)），则表明当前凸模型的近似不够好，可能需要收缩信任域半径 \(\Delta_k\) 以提高近似精度。但我们这里没有显式的 \(\Delta_k\)，所以可以通过调整 \(B^k\) 的正定性来间接控制。

步骤6：收敛性检查
检查是否满足停止准则，常用准则包括：

搜索方向 \(d^k\) 的范数很小：\(\|d^k\| \le \epsilon_{\text{tol}}\)。
目标函数值变化很小：\(|f(x^{k+1}) - f(x^k)| \le \epsilon_{\text{tol}} (1 + |f(x^k)|)\)。
最优性条件违反度小：例如，KKT 条件的残差小于容差。

若不收敛，则令 \(k := k+1\)，返回步骤2。

步骤7：算法总结与注意事项
该方法本质是 SCP 与自适应步长线搜索的结合。优点：将非凸问题转化为一系列凸子问题，且自适应步长可保证稳定收敛。缺点：凸近似可能不够准确，尤其当非线性程度高时，需要较多迭代。实际实现时，需确保子问题可解（例如，用商业求解器如 Gurobi 求解凸 QP），并妥善处理可行性。

示例
考虑简单问题：

\[\min_{x \in \mathbb{R}^2} f(x) = x_1^4 + x_2^2, \quad \text{s.t.} \quad g(x) = x_1^2 + x_2 - 1 \le 0. \]

取初始点 \(x^0 = (1, 0)\)，初始 \(B^0 = I\)（单位阵）。第一步构造凸子问题：
目标近似：\(\nabla f = (4x_1^3, 2x_2) = (4, 0)\)，故 \(\nabla f^\top d = 4d_1 + 0 d_2\)，二次项为 \(\frac{1}{2} d^\top I d = \frac{1}{2}(d_1^2 + d_2^2)\)。
约束近似：\(g(x^0)=1+0-1=0\)，\(\nabla g = (2x_1, 1) = (2, 1)\)，故约束为 \(0 + (2,1)^\top d \le 0\)，即 \(2d_1 + d_2 \le 0\)。
子问题为：

\[\min_{d} 4d_1 + \frac{1}{2}(d_1^2 + d_2^2) \quad \text{s.t.} \quad 2d_1 + d_2 \le 0. \]

求解得最优方向 \(d^0 = (-2, 1)\)（通过 KKT 条件可解）。然后进行步长搜索：检验 \(\alpha=1\) 时，\(x^1 = (-1, 1)\)，计算 \(f(-1,1)=2\)，而 \(f(1,0)=1\)，不满足下降条件，故回溯减小步长，最终选 \(\alpha_0\) 使得满足 Armijo 条件。后续迭代类似，直至收敛到局部最优解 \(x^* \approx (0,1)\)。

通过以上步骤，我们完成了序列凸规划与自适应步长结合的基础算法的详细解释。这个方法在工程优化中应用广泛，因为它结合了凸优化的高效性和自适应步长的鲁棒性。

非线性规划中的序列凸规划(SCP)与自适应步长结合的基础题题目描述我们考虑如下形式的非线性规划问题： \[\begin{aligned} \min_ {x \in \mathbb{R}^n} \quad & f(x) \\ \text{s.t.} \quad & g_ i(x) \le 0, \quad i = 1, \dots, m, \\ & h_ j(x) = 0, \quad j = 1, \dots, p, \end{aligned}\] 其中，目标函数 \(f(x)\) 和约束函数 \(g_ i(x), h_ j(x)\) 均为非线性、非凸的，但一阶和二阶信息（梯度、Hessian 矩阵）在可行域内可计算。为高效求解该问题，我们将序列凸规划（SCP）与自适应步长控制结合。在每一步迭代，我们用当前迭代点 \(x^k\) 处的凸近似（例如，通过一阶泰勒展开构造局部凸模型）替代原非凸函数，形成一个凸子问题，求解该子问题得到搜索方向 \(d^k\)。之后，通过一个自适应步长 \(\alpha_ k \in (0,1]\) 更新迭代点：\(x^{k+1} = x^k + \alpha_ k d^k\)。步长 \(\alpha_ k\) 通过一个简单的回溯线搜索条件自适应调整，确保目标函数有“充分下降”，并尽可能保持可行性。该方法避免了直接求解大规模非凸问题，通过一系列凸优化逐步逼近局部最优解。解题过程我们将解题过程分解为以下步骤，并逐步详细说明。步骤1：理解算法框架序列凸规划的核心思想是“序列凸逼近”，即在每个迭代点 \(x^k\) 处，用凸模型近似原非凸函数。常用的凸模型包括：目标函数 \(f(x)\) 用其在 \(x^k\) 处的二阶泰勒展开近似，但需保证 Hessian 矩阵是正定的（若非正定，可修正为 \(B^k \succ 0\)，例如用拟牛顿法更新 \(B^k\)）。对于非线性约束 \(g_ i(x) \le 0\) 和 \(h_ j(x) = 0\)，用一阶泰勒展开近似，从而得到线性约束。这样，每一步的子问题是一个凸优化问题（通常是二次规划或线性约束凸问题），易于求解。但为了确保逼近的精度和收敛性，需要限制迭代步长，因此引入“信任域”或“移动限制”。本题中，我们用自适应步长 \(\alpha_ k\) 来控制步进幅度。步骤2：构造第 k 步的凸子问题在迭代点 \(x^k\) 处，构造如下凸子问题（以二次规划为例）： \[\begin{aligned} \min_ {d \in \mathbb{R}^n} \quad & \nabla f(x^k)^\top d + \frac{1}{2} d^\top B^k d \\ \text{s.t.} \quad & g_ i(x^k) + \nabla g_ i(x^k)^\top d \le 0, \quad i = 1, \dots, m, \\ & h_ j(x^k) + \nabla h_ j(x^k)^\top d = 0, \quad j = 1, \dots, p, \\ & \|d\|_ \infty \le \Delta_ k. \end{aligned}\] 这里： \(d = x - x^k\) 是搜索方向。 \(B^k\) 是正定矩阵，可以是 \(f(x)\) 在 \(x^k\) 处的 Hessian 矩阵，或通过 BFGS 等拟牛顿法得到的正定近似。不等式约束和等式约束通过一阶线性化近似，保证了子问题是凸的（因为目标函数是凸二次函数，约束是线性的）。额外增加一个“移动限制” \(\|d\| \infty \le \Delta_ k\)，其中 \(\Delta_ k > 0\) 是信任域半径，用以控制每一步的移动范围，保证近似模型的准确性。本题中，我们用自适应步长 \(\alpha_ k\) 间接控制移动范围，因此在子问题中可不显式包含 \(\|d\| \infty \le \Delta_ k\)，而是通过步长 \(\alpha_ k\) 在更新时缩放 \(d^k\)。为简化，我们考虑子问题中不显式包含移动限制，但通过求解得到方向 \(d^k\) 后，再用步长 \(\alpha_ k\) 缩放。那么子问题简化为： \[\begin{aligned} \min_ {d \in \mathbb{R}^n} \quad & \nabla f(x^k)^\top d + \frac{1}{2} d^\top B^k d \\ \text{s.t.} \quad & g_ i(x^k) + \nabla g_ i(x^k)^\top d \le 0, \quad i = 1, \dots, m, \\ & h_ j(x^k) + \nabla h_ j(x^k)^\top d = 0, \quad j = 1, \dots, p. \end{aligned}\] 这是一个标准的凸二次规划（QP），可以用内点法、积极集法等有效求解。步骤3：求解凸子问题得到搜索方向对上述 QP 求解，得到最优解 \(d^k\)。如果子问题不可行，说明当前点 \(x^k\) 附近无可行下降方向，算法可能需要调整信任域半径或采用可行性恢复策略。在基础题中，我们假设子问题总是可行的。步骤4：自适应步长选择得到 \(d^k\) 后，我们不直接取 \(x^{k+1} = x^k + d^k\)，而是用步长 \(\alpha_ k \in (0,1 ]\) 缩放更新： \[ x^{k+1} = x^k + \alpha_ k d^k. \] 步长 \(\alpha_ k\) 的选择需要满足两个条件：充分下降条件：确保目标函数值下降足够多，即 \[ f(x^k + \alpha_ k d^k) \le f(x^k) + c_ 1 \alpha_ k \nabla f(x^k)^\top d^k, \] 其中 \(c_ 1 \in (0,1)\) 是一个常数（例如 \(c_ 1 = 10^{-4}\)）。该条件称为 Armijo 条件，保证目标函数值下降比例不小于方向导数乘以步长的一个比例。可行性条件：尽量不破坏约束。由于子问题的约束是线性近似，实际非线性约束在 \(x^k + \alpha d^k\) 处可能被违反。因此，我们要求步长 \(\alpha_ k\) 满足： \[ g_ i(x^k + \alpha_ k d^k) \le 0 + \epsilon_ {\text{feas}}, \quad h_ j(x^k + \alpha_ k d^k) = 0 \pm \epsilon_ {\text{feas}}, \] 其中 \(\epsilon_ {\text{feas}} > 0\) 是一个小的可行性容差。在实际中，我们可定义一个“可行性违背度”函数： \[ \Phi(x) = \sum_ {i=1}^m \max(0, g_ i(x)) + \sum_ {j=1}^p |h_ j(x)|, \] 并希望 \(\Phi(x^{k+1}) \le \eta_ k\)，其中 \(\eta_ k\) 是逐步收紧的可行性容忍度。自适应步长的选取通过回溯线搜索进行：初始步长设为 \(\alpha = 1\)，若上述两个条件不满足，则令 \(\alpha := \beta \alpha\)（其中 \(\beta \in (0,1)\)，如 \(\beta=0.5\)），重复检查直到条件满足。在基础题中，我们重点关注充分下降条件，对可行性条件可放宽，即允许轻微违反，但最终需趋于可行。步骤5：更新迭代点与算法参数确定步长 \(\alpha_ k\) 后，更新 \(x^{k+1} = x^k + \alpha_ k d^k\)。然后，更新拟牛顿矩阵 \(B^{k+1}\)（例如用 BFGS 更新），以便下一次迭代构造更好的凸模型。如果步长 \(\alpha_ k\) 很小（例如小于某个阈值 \(\alpha_ {\min}\)），则表明当前凸模型的近似不够好，可能需要收缩信任域半径 \(\Delta_ k\) 以提高近似精度。但我们这里没有显式的 \(\Delta_ k\)，所以可以通过调整 \(B^k\) 的正定性来间接控制。步骤6：收敛性检查检查是否满足停止准则，常用准则包括：搜索方向 \(d^k\) 的范数很小：\(\|d^k\| \le \epsilon_ {\text{tol}}\)。目标函数值变化很小：\(|f(x^{k+1}) - f(x^k)| \le \epsilon_ {\text{tol}} (1 + |f(x^k)|)\)。最优性条件违反度小：例如，KKT 条件的残差小于容差。若不收敛，则令 \(k := k+1\)，返回步骤2。步骤7：算法总结与注意事项该方法本质是 SCP 与自适应步长线搜索的结合。优点：将非凸问题转化为一系列凸子问题，且自适应步长可保证稳定收敛。缺点：凸近似可能不够准确，尤其当非线性程度高时，需要较多迭代。实际实现时，需确保子问题可解（例如，用商业求解器如 Gurobi 求解凸 QP），并妥善处理可行性。示例考虑简单问题： \[ \min_ {x \in \mathbb{R}^2} f(x) = x_ 1^4 + x_ 2^2, \quad \text{s.t.} \quad g(x) = x_ 1^2 + x_ 2 - 1 \le 0. \] 取初始点 \(x^0 = (1, 0)\)，初始 \(B^0 = I\)（单位阵）。第一步构造凸子问题：目标近似：\(\nabla f = (4x_ 1^3, 2x_ 2) = (4, 0)\)，故 \(\nabla f^\top d = 4d_ 1 + 0 d_ 2\)，二次项为 \(\frac{1}{2} d^\top I d = \frac{1}{2}(d_ 1^2 + d_ 2^2)\)。约束近似：\(g(x^0)=1+0-1=0\)，\(\nabla g = (2x_ 1, 1) = (2, 1)\)，故约束为 \(0 + (2,1)^\top d \le 0\)，即 \(2d_ 1 + d_ 2 \le 0\)。子问题为： \[ \min_ {d} 4d_ 1 + \frac{1}{2}(d_ 1^2 + d_ 2^2) \quad \text{s.t.} \quad 2d_ 1 + d_ 2 \le 0. \] 求解得最优方向 \(d^0 = (-2, 1)\)（通过 KKT 条件可解）。然后进行步长搜索：检验 \(\alpha=1\) 时，\(x^1 = (-1, 1)\)，计算 \(f(-1,1)=2\)，而 \(f(1,0)=1\)，不满足下降条件，故回溯减小步长，最终选 \(\alpha_ 0\) 使得满足 Armijo 条件。后续迭代类似，直至收敛到局部最优解 \(x^* \approx (0,1)\)。通过以上步骤，我们完成了序列凸规划与自适应步长结合的基础算法的详细解释。这个方法在工程优化中应用广泛，因为它结合了凸优化的高效性和自适应步长的鲁棒性。