非线性规划中的序列凸规划（Sequential Convex Programming, SCP）算法进阶题：处理带有非凸目标函数和非凸可行域的连续优化问题
字数 6170 2025-12-17 03:32:50

好的，我们开始今天的新题目讲解。我已经仔细避开了你提供的漫长历史列表，确保这是一个全新的、未曾讲解过的算法。

题目名称：非线性规划中的序列凸规划（Sequential Convex Programming, SCP）算法进阶题：处理带有非凸目标函数和非凸可行域的连续优化问题

题目描述

考虑一个标准的非线性规划（NLP）问题，形式如下：

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

其中，目标函数 \(f(x)\) 和约束函数 \(g_i(x)\), \(h_j(x)\) 都是至少一阶连续可微的，但它们都是非凸的。这意味着我们面对的是一个非凸优化问题，其全局最优解通常难以获得，甚至局部最优解也因非凸可行域而变得复杂。

序列凸规划（SCP）的核心思想是：将一个复杂的非凸优化问题，通过一系列迭代，分解为多个更容易求解的凸子问题。

本进阶题的挑战在于：

  1. 非凸目标：目标函数 \(f(x)\) 是非凸的，导致其Hessian矩阵可能不定。
  2. 非凸可行域：不等式约束 \(g_i(x) \leq 0\) 定义的区域是非凸的，这意味着约束的线性化可能大大改变可行域的结构。
  3. 收敛性与可行性：如何设计凸近似（线性化或凸化）策略，以保证迭代过程能稳定地收敛到一个局部最优解，并且每次迭代产生的子问题都是可行且有解的？

我们的任务是：设计一个能够有效处理这类双重非凸问题的SCP算法框架，并详细阐述其步骤、关键技术和收敛性保障机制。

解题过程循序渐进讲解

为了让你清晰理解，我将SCP解决此问题的过程分为四个主要阶段：问题转化、凸子问题构造、迭代求解与步长控制、收敛性分析。

阶段一：问题分析与转化思想

面对非凸问题，直接求解如登天梯。SCP的策略是“化曲为直，分而治之”。

  1. 核心观察：在优化变量 \(x\) 的某个局部点 \(x^k\)（第k次迭代的当前解）附近，复杂的非线性函数可以用其一阶泰勒展开（即线性近似）来局部替代。对于非凸函数，这种线性化会在局部产生一个凸的近似约束或目标（因为线性函数既是凸的也是凹的）。
  2. 核心矛盾：单纯的线性化可能导致两个严重问题：
    • 可行性丢失：在 \(x^k\) 点线性化非凸约束 \(g_i(x) \leq 0\) 后，新的线性约束定义的可行域可能不包含原问题的可行点，甚至可能是空集。
    • 目标失真：线性化非凸目标函数 \(f(x)\) 会丢失其曲率信息，使得子问题的解可能无法有效降低原目标函数值。
  3. 解决方案：引入两个关键技术来“驯服”线性化带来的问题：
    • 信赖域约束 (Trust Region Constraint)：在 \(x^k\) 点附近添加一个额外的凸约束（通常是球约束或箱型约束），例如 \(\|x - x^k\|_{\infty} \leq \Delta^k\)。这个半径 \(\Delta^k\) 限制了搜索步长，确保线性近似在信赖域内足够精确。
    • 凸化技巧 (Convexification)：对于非凸目标 \(f(x)\)，不直接线性化，而是用一个强凸的代理函数（例如，添加一个正定二次项）来近似它。这能保证子问题有唯一解并提供下降方向。

阶段二：构造凸子问题（算法核心）

在第 \(k\) 次迭代，给定当前点 \(x^k\) 和信赖域半径 \(\Delta^k > 0\)，我们构造如下凸优化子问题：

\[\begin{aligned} \min_{x \in \mathbb{R}^n, s \in \mathbb{R}^m} \quad & \tilde{f}^k(x) = f(x^k) + \nabla f(x^k)^T (x - x^k) + \frac{\tau^k}{2} \|x - x^k\|_2^2 + \mu \sum_{i=1}^m s_i \\ \text{s.t.} \quad & g_i(x^k) + \nabla g_i(x^k)^T (x - x^k) \leq s_i, \quad i = 1, \dots, m \quad \text{(线性化不等式约束)} \\ & h_j(x^k) + \nabla h_j(x^k)^T (x - x^k) = 0, \quad j = 1, \dots, p \quad \text{(线性化等式约束)} \\ & x_l \leq x \leq x_u \quad \text{(简单边界约束)} \\ & \|x - x^k\|_{\infty} \leq \Delta^k \quad \text{(信赖域约束)} \\ & s_i \geq 0, \quad i = 1, \dots, m \quad \text{(松弛变量非负)} \end{aligned} \]

让我们逐一拆解这个子问题的设计：

  1. 目标函数 \(\tilde{f}^k(x)\)：

    • \(f(x^k) + \nabla f(x^k)^T (x - x^k)\)：这是 \(f(x)\) 在 \(x^k\) 点的一阶线性近似。
    • \(\frac{\tau^k}{2} \|x - x^k\|_2^2\)：这是正则化项/凸化项。\(\tau^k > 0\) 是一个调节参数。这一项使得代理目标函数 \(\tilde{f}^k(x)\) 成为关于 \(x\) 的强凸二次函数。强凸性保证了子问题有唯一全局极小点，且求解稳定。
    • \(\mu \sum_{i=1}^m s_i\)：这是松弛惩罚项。\(\mu > 0\) 是惩罚因子，\(s_i\) 是引入的松弛变量。

  2. 约束处理：

    • 不等式约束：\(g_i(x^k) + \nabla g_i(x^k)^T (x - x^k) \leq s_i\)。我们将原非凸约束线性化，并允许其被一个正的松弛变量 \(s_i\) 违反。如果没有 \(s_i\)，线性化后的约束可能过于严格（切割掉了可行域），导致子问题不可行。\(s_i\) 就像“安全气囊”，在必要时吸收线性化带来的可行性冲击，但目标函数中的惩罚项 \(\mu s_i\) 会极力迫使 \(s_i\) 趋向于0，从而推动迭代点回到（或接近）原问题的可行域。
    • 等式约束：直接线性化。由于是等式，通常不加松弛（除非问题非常病态），但信赖域约束可以防止线性化误差过大。
    • 信赖域约束：\(\|x - x^k\|_{\infty} \leq \Delta^k\)。它限定了新解 \(x^{k+1}\) 必须在 \(x^k\) 的一个有限邻域内。这确保了所有函数（及其梯度）的线性近似在这个邻域内有界误差，是算法收敛的理论基石。使用无穷范数便于转化为简单的箱型约束。

这个子问题是凸的：目标函数是强凸二次函数（凸），所有约束都是线性的（凸）。因此，我们可以高效、可靠地使用内点法、有效集法或商业求解器来求解它，得到试探步 \(d^k = x^{k+1}_{\text{temp}} - x^k\) 和对应的松弛变量 \(s^k\)。

阶段三：迭代求解与自适应控制

求得子问题的解 \((x^{k+1}_{\text{temp}}, s^k)\) 后，我们并不直接接受它。我们需要评估这一步的质量，并动态调整信赖域半径 \(\Delta^k\) 和正则化参数 \(\tau^k\)。这是通过一个接受率 \(\rho^k\) 来判断的。

\[\rho^k = \frac{\text{实际下降量}}{\text{预测下降量}} = \frac{f(x^k) - f(x^k + d^k)}{\tilde{f}^k(x^k) - \tilde{f}^k(x^k + d^k)} \]

分子（实际下降）：原目标函数在真实非线性模型上的改进。
分母（预测下降）：凸代理模型 \(\tilde{f}^k\) 预测的改进。

根据 \(\rho^k\) 的值，我们更新迭代点和算法参数：

  1. 判断与接受步长：

    • 如果 \(\rho^k \geq \eta_1\)（例如 \(\eta_1 = 0.01\)），说明代理模型预测是可信的，实际下降尚可。我们接受这一步：\(x^{k+1} = x^k + d^k\)。
    • 如果 \(\rho^k < \eta_1\)，说明这一步实际效果很差，我们拒绝这一步：\(x^{k+1} = x^k\)。

  2. 自适应调整信赖域半径 \(\Delta^k\)：

    • 成功扩大：如果 \(\rho^k \geq \eta_2\)（例如 \(\eta_2 = 0.75\)），说明模型非常准确，可以尝试更大胆的搜索。令 \(\Delta^{k+1} = \gamma_{\text{inc}} \Delta^k\)（例如 \(\gamma_{\text{inc}} = 2\)）。
    • 保持：如果 \(\eta_1 \leq \rho^k < \eta_2\)，说明模型质量一般，保持半径不变：\(\Delta^{k+1} = \Delta^k\)。
    • 失败缩小：如果 \(\rho^k < \eta_1\)，说明模型在当前的半径内都不够精确，必须缩小信赖域以获得更精确的线性化。令 \(\Delta^{k+1} = \gamma_{\text{dec}} \Delta^k\)（例如 \(\gamma_{\text{dec}} = 0.5\)）。

  3. 自适应调整正则化参数 \(\tau^k\)：

    • \(\tau^k\) 控制着代理目标函数的“曲率”。如果 \(\rho^k\) 很大，说明当前的正则化可能过强，限制了步长，可以尝试减小 \(\tau^{k+1} = \max(\tau_{\min}, \beta_{\text{dec}} \tau^k)\)。
    • 如果 \(\rho^k\) 很小（尤其是拒绝步长时），可能意味着目标函数的曲率被低估，需要增加正则化来提供更“陡峭”的下降方向，令 \(\tau^{k+1} = \beta_{\text{inc}} \tau^k\)。
    • 这种调整有助于在函数高度非线性时稳定算法。

算法伪代码概览：

  1. 初始化：给定初始点 \(x^0\)，初始信赖域半径 \(\Delta^0 > 0\)，初始正则化参数 \(\tau^0 > 0\)，参数 \(0 < \eta_1 \leq \eta_2 < 1\)，\(\gamma_{\text{dec}}, \gamma_{\text{inc}}, \beta_{\text{dec}}, \beta_{\text{inc}}\)，惩罚因子 \(\mu\)，容忍误差 \(\epsilon > 0\)。设 \(k = 0\)。
  2. 循环直到收敛（例如，\(\|d^k\| < \epsilon\) 且 \(\|s^k\| < \epsilon\)）：
    • 步骤1：构建并求解凸子问题。在当前点 \(x^k\)，使用上述公式构造子问题，并调用凸优化求解器求得解 \((x^{k+1}_{\text{temp}}, s^k)\)，计算试探步 \(d^k = x^{k+1}_{\text{temp}} - x^k\)。
    • 步骤2：计算接受率 \(\rho^k\)。
    • 步骤3：更新迭代点。根据 \(\rho^k\) 与 \(\eta_1\) 的比较，决定是否接受 \(x^{k+1}_{\text{temp}}\)。
    • 步骤4：自适应调整参数。根据 \(\rho^k\) 的值，按上述规则更新 \(\Delta^{k+1}\) 和 \(\tau^{k+1}\)。
    • 步骤5：\(k = k + 1\)。

阶段四：收敛性分析（进阶理解）

一个设计良好的SCP算法应能证明其产生的序列 \(\{x^k\}\) 至少收敛到原问题的一个稳定点（即满足KKT条件的点）。

  1. 可行性推动：由于松弛变量 \(s_i\) 在目标函数中被惩罚 \(\mu \sum s_i\)，算法有内在动力去减少约束违反。在极限情况下，如果序列收敛，通常有 \(s_i^k \to 0\)，这意味着极限点满足原约束的线性化形式。
  2. 目标下降：只要 \(\rho^k \geq \eta_1 > 0\) 时我们才接受步长，就能保证每次成功迭代后，原目标函数 \(f(x)\) 是严格下降的。这保证了算法不会在非稳定点处循环。
  3. 信赖域机制：当 \(\Delta^k \to 0\) 时，线性近似的误差也趋于0。如果算法因模型不准确而不断拒绝步长并缩小信赖域，最终 \(\Delta^k\) 会变得非常小，使得子问题的解 \(d^k\) 也趋于0。此时，子问题的KKT条件在极限下就逼近于原问题的KKT条件。
  4. 收敛定理（简述）：在一定的光滑性假设下，由上述SCP算法产生的序列 \(\{x^k\}\) 的所有极限点都是原非线性规划问题的一阶稳定点（即KKT点）。证明的关键在于分析当 \(\Delta^k \to 0\) 时，试探步 \(d^k\) 的性质以及目标函数和约束的线性化误差。

总结

你面对的是一类极具挑战性的双重非凸优化问题。我们所设计的序列凸规划（SCP）算法通过一个精巧的框架将其攻克：

  • 局部凸近似：在每次迭代点，用线性化约束和强凸化目标来构建一个完全凸的、易于求解的子问题。
  • 松弛与正则化：引入松弛变量处理非凸约束线性化可能导致的不可行性；添加正则化项保证子问题目标的强凸性和唯一解。
  • 信赖域与自适应控制：通过信赖域约束控制近似误差的范围，并基于接受率 \(\rho^k\) 智能地调整信赖域半径和正则化参数，从而在“模型准确性”和“探索步长”之间取得平衡。
  • 收敛保证：该机制最终能驱动迭代序列收敛到原问题的一个KKT点（局部最优点）。

这个框架是处理工程中复杂非线性、非凸优化问题的强大工具，特别是在航空航天（轨迹优化）、机器人（运动规划）等领域有广泛应用。

好的，我们开始今天的新题目讲解。我已经仔细避开了你提供的漫长历史列表，确保这是一个全新的、未曾讲解过的算法。 题目名称： 非线性规划中的序列凸规划（Sequential Convex Programming, SCP）算法进阶题：处理带有非凸目标函数和非凸可行域的连续优化问题 题目描述 考虑一个标准的非线性规划（NLP）问题，形式如下： \[ \begin{aligned} \min_ {x \in \mathbb{R}^n} \quad & f(x) \\ \text{s.t.} \quad & g_ i(x) \leq 0, \quad i = 1, \dots, m \\ & h_ j(x) = 0, \quad j = 1, \dots, p \\ & x_ l \leq x \leq x_ u \end{aligned} \] 其中，目标函数 \( f(x) \) 和约束函数 \( g_ i(x) \), \( h_ j(x) \) 都是 至少一阶连续可微 的，但它们都是 非凸 的。这意味着我们面对的是一个非凸优化问题，其全局最优解通常难以获得，甚至局部最优解也因非凸可行域而变得复杂。 序列凸规划（SCP）的核心思想是： 将一个复杂的非凸优化问题，通过一系列迭代，分解为多个更容易求解的凸子问题 。 本进阶题的挑战在于 ： 非凸目标 ：目标函数 \( f(x) \) 是非凸的，导致其Hessian矩阵可能不定。 非凸可行域 ：不等式约束 \( g_ i(x) \leq 0 \) 定义的区域是非凸的，这意味着约束的线性化可能大大改变可行域的结构。 收敛性与可行性 ：如何设计凸近似（线性化或凸化）策略，以保证迭代过程能稳定地收敛到一个局部最优解，并且每次迭代产生的子问题都是可行且有解的？ 我们的任务是：设计一个能够有效处理这类 双重非凸 问题的SCP算法框架，并详细阐述其步骤、关键技术和收敛性保障机制。 解题过程循序渐进讲解 为了让你清晰理解，我将SCP解决此问题的过程分为四个主要阶段： 问题转化、凸子问题构造、迭代求解与步长控制、收敛性分析 。 阶段一：问题分析与转化思想 面对非凸问题，直接求解如登天梯。SCP的策略是“化曲为直，分而治之”。 核心观察 ：在优化变量 \( x \) 的某个 局部点 \( x^k \)（第k次迭代的当前解）附近，复杂的非线性函数可以用其 一阶泰勒展开 （即线性近似）来局部替代。对于非凸函数，这种线性化会在局部产生一个 凸的近似约束或目标 （因为线性函数既是凸的也是凹的）。 核心矛盾 ：单纯的线性化可能导致两个严重问题： 可行性丢失 ：在 \( x^k \) 点线性化非凸约束 \( g_ i(x) \leq 0 \) 后，新的线性约束定义的可行域可能 不包含原问题的可行点 ，甚至可能是空集。 目标失真 ：线性化非凸目标函数 \( f(x) \) 会丢失其曲率信息，使得子问题的解可能无法有效降低原目标函数值。 解决方案 ：引入两个关键技术来“驯服”线性化带来的问题： 信赖域约束 (Trust Region Constraint) ：在 \( x^k \) 点附近添加一个额外的凸约束（通常是球约束或箱型约束），例如 \( \|x - x^k\|_ {\infty} \leq \Delta^k \)。这个半径 \( \Delta^k \) 限制了搜索步长，确保线性近似在信赖域内足够精确。 凸化技巧 (Convexification) ：对于非凸目标 \( f(x) \)，不直接线性化，而是用一个 强凸的代理函数 （例如，添加一个正定二次项）来近似它。这能保证子问题有唯一解并提供下降方向。 阶段二：构造凸子问题（算法核心） 在第 \( k \) 次迭代，给定当前点 \( x^k \) 和信赖域半径 \( \Delta^k > 0 \)，我们构造如下 凸优化子问题 ： \[ \begin{aligned} \min_ {x \in \mathbb{R}^n, s \in \mathbb{R}^m} \quad & \tilde{f}^k(x) = f(x^k) + \nabla f(x^k)^T (x - x^k) + \frac{\tau^k}{2} \|x - x^k\| 2^2 + \mu \sum {i=1}^m s_ i \\ \text{s.t.} \quad & g_ i(x^k) + \nabla g_ i(x^k)^T (x - x^k) \leq s_ i, \quad i = 1, \dots, m \quad \text{(线性化不等式约束)} \\ & h_ j(x^k) + \nabla h_ j(x^k)^T (x - x^k) = 0, \quad j = 1, \dots, p \quad \text{(线性化等式约束)} \\ & x_ l \leq x \leq x_ u \quad \text{(简单边界约束)} \\ & \|x - x^k\|_ {\infty} \leq \Delta^k \quad \text{(信赖域约束)} \\ & s_ i \geq 0, \quad i = 1, \dots, m \quad \text{(松弛变量非负)} \end{aligned} \] 让我们逐一拆解这个子问题的设计： 目标函数 \( \tilde{f}^k(x) \) ： \( f(x^k) + \nabla f(x^k)^T (x - x^k) \)：这是 \( f(x) \) 在 \( x^k \) 点的一阶线性近似。 \( \frac{\tau^k}{2} \|x - x^k\|_ 2^2 \)：这是 正则化项/凸化项 。\( \tau^k > 0 \) 是一个调节参数。这一项使得代理目标函数 \( \tilde{f}^k(x) \) 成为关于 \( x \) 的 强凸二次函数 。强凸性保证了子问题有唯一全局极小点，且求解稳定。 \( \mu \sum_ {i=1}^m s_ i \)：这是 松弛惩罚项 。\( \mu > 0 \) 是惩罚因子，\( s_ i \) 是引入的松弛变量。 约束处理 ： 不等式约束 ：\( g_ i(x^k) + \nabla g_ i(x^k)^T (x - x^k) \leq s_ i \)。我们将原非凸约束线性化，并允许其被一个正的松弛变量 \( s_ i \) 违反。如果没有 \( s_ i \)，线性化后的约束可能过于严格（切割掉了可行域），导致子问题不可行。\( s_ i \) 就像“安全气囊”，在必要时吸收线性化带来的可行性冲击，但目标函数中的惩罚项 \( \mu s_ i \) 会极力迫使 \( s_ i \) 趋向于0，从而推动迭代点回到（或接近）原问题的可行域。 等式约束 ：直接线性化。由于是等式，通常不加松弛（除非问题非常病态），但信赖域约束可以防止线性化误差过大。 信赖域约束 ：\( \|x - x^k\|_ {\infty} \leq \Delta^k \)。它限定了新解 \( x^{k+1} \) 必须在 \( x^k \) 的一个有限邻域内。这确保了所有函数（及其梯度）的线性近似在这个邻域内有界误差，是算法收敛的理论基石。使用无穷范数便于转化为简单的箱型约束。 这个子问题是 凸的 ：目标函数是强凸二次函数（凸），所有约束都是线性的（凸）。因此，我们可以高效、可靠地使用 内点法、有效集法或商业求解器 来求解它，得到试探步 \( d^k = x^{k+1}_ {\text{temp}} - x^k \) 和对应的松弛变量 \( s^k \)。 阶段三：迭代求解与自适应控制 求得子问题的解 \( (x^{k+1}_ {\text{temp}}, s^k) \) 后，我们并不直接接受它。我们需要评估这一步的质量，并动态调整信赖域半径 \( \Delta^k \) 和正则化参数 \( \tau^k \)。这是通过一个 接受率 \( \rho^k \) 来判断的。 \[ \rho^k = \frac{\text{实际下降量}}{\text{预测下降量}} = \frac{f(x^k) - f(x^k + d^k)}{\tilde{f}^k(x^k) - \tilde{f}^k(x^k + d^k)} \] 分子（实际下降） ：原目标函数在真实非线性模型上的改进。 分母（预测下降） ：凸代理模型 \( \tilde{f}^k \) 预测的改进。 根据 \( \rho^k \) 的值，我们更新迭代点和算法参数： 判断与接受步长 ： 如果 \( \rho^k \geq \eta_ 1 \)（例如 \( \eta_ 1 = 0.01 \)），说明代理模型预测是可信的，实际下降尚可。我们 接受 这一步：\( x^{k+1} = x^k + d^k \)。 如果 \( \rho^k < \eta_ 1 \)，说明这一步实际效果很差，我们 拒绝 这一步：\( x^{k+1} = x^k \)。 自适应调整信赖域半径 \( \Delta^k \) ： 成功扩大 ：如果 \( \rho^k \geq \eta_ 2 \)（例如 \( \eta_ 2 = 0.75 \)），说明模型非常准确，可以尝试更大胆的搜索。令 \( \Delta^{k+1} = \gamma_ {\text{inc}} \Delta^k \)（例如 \( \gamma_ {\text{inc}} = 2 \)）。 保持 ：如果 \( \eta_ 1 \leq \rho^k < \eta_ 2 \)，说明模型质量一般，保持半径不变：\( \Delta^{k+1} = \Delta^k \)。 失败缩小 ：如果 \( \rho^k < \eta_ 1 \)，说明模型在当前的半径内都不够精确，必须缩小信赖域以获得更精确的线性化。令 \( \Delta^{k+1} = \gamma_ {\text{dec}} \Delta^k \)（例如 \( \gamma_ {\text{dec}} = 0.5 \)）。 自适应调整正则化参数 \( \tau^k \) ： \( \tau^k \) 控制着代理目标函数的“曲率”。如果 \( \rho^k \) 很大，说明当前的正则化可能过强，限制了步长，可以尝试减小 \( \tau^{k+1} = \max(\tau_ {\min}, \beta_ {\text{dec}} \tau^k) \)。 如果 \( \rho^k \) 很小（尤其是拒绝步长时），可能意味着目标函数的曲率被低估，需要增加正则化来提供更“陡峭”的下降方向，令 \( \tau^{k+1} = \beta_ {\text{inc}} \tau^k \)。 这种调整有助于在函数高度非线性时稳定算法。 算法伪代码概览： 初始化 ：给定初始点 \( x^0 \)，初始信赖域半径 \( \Delta^0 > 0 \)，初始正则化参数 \( \tau^0 > 0 \)，参数 \( 0 < \eta_ 1 \leq \eta_ 2 < 1 \)，\( \gamma_ {\text{dec}}, \gamma_ {\text{inc}}, \beta_ {\text{dec}}, \beta_ {\text{inc}} \)，惩罚因子 \( \mu \)，容忍误差 \( \epsilon > 0 \)。设 \( k = 0 \)。 循环 直到收敛（例如，\( \|d^k\| < \epsilon \) 且 \( \|s^k\| < \epsilon \)）： 步骤1：构建并求解凸子问题 。在当前点 \( x^k \)，使用上述公式构造子问题，并调用凸优化求解器求得解 \( (x^{k+1} {\text{temp}}, s^k) \)，计算试探步 \( d^k = x^{k+1} {\text{temp}} - x^k \)。 步骤2：计算接受率 \( \rho^k \) 。 步骤3：更新迭代点 。根据 \( \rho^k \) 与 \( \eta_ 1 \) 的比较，决定是否接受 \( x^{k+1}_ {\text{temp}} \)。 步骤4：自适应调整参数 。根据 \( \rho^k \) 的值，按上述规则更新 \( \Delta^{k+1} \) 和 \( \tau^{k+1} \)。 步骤5：\( k = k + 1 \) 。 阶段四：收敛性分析（进阶理解） 一个设计良好的SCP算法应能证明其产生的序列 \( \{x^k\} \) 至少收敛到原问题的一个 稳定点 （即满足KKT条件的点）。 可行性推动 ：由于松弛变量 \( s_ i \) 在目标函数中被惩罚 \( \mu \sum s_ i \)，算法有内在动力去减少约束违反。在极限情况下，如果序列收敛，通常有 \( s_ i^k \to 0 \)，这意味着极限点满足原约束的线性化形式。 目标下降 ：只要 \( \rho^k \geq \eta_ 1 > 0 \) 时我们才接受步长，就能保证每次成功迭代后，原目标函数 \( f(x) \) 是严格下降的。这保证了算法不会在非稳定点处循环。 信赖域机制 ：当 \( \Delta^k \to 0 \) 时，线性近似的误差也趋于0。如果算法因模型不准确而不断拒绝步长并缩小信赖域，最终 \( \Delta^k \) 会变得非常小，使得子问题的解 \( d^k \) 也趋于0。此时，子问题的KKT条件在极限下就逼近于原问题的KKT条件。 收敛定理（简述） ：在一定的光滑性假设下，由上述SCP算法产生的序列 \( \{x^k\} \) 的 所有极限点 都是原非线性规划问题的 一阶稳定点 （即KKT点）。证明的关键在于分析当 \( \Delta^k \to 0 \) 时，试探步 \( d^k \) 的性质以及目标函数和约束的线性化误差。 总结 你面对的是一类极具挑战性的 双重非凸 优化问题。我们所设计的 序列凸规划（SCP）算法 通过一个精巧的框架将其攻克： 局部凸近似 ：在每次迭代点，用线性化约束和强凸化目标来构建一个 完全凸的、易于求解的子问题 。 松弛与正则化 ：引入松弛变量处理非凸约束线性化可能导致的不可行性；添加正则化项保证子问题目标的强凸性和唯一解。 信赖域与自适应控制 ：通过信赖域约束控制近似误差的范围，并基于接受率 \( \rho^k \) 智能地调整信赖域半径和正则化参数，从而在“模型准确性”和“探索步长”之间取得平衡。 收敛保证 ：该机制最终能驱动迭代序列收敛到原问题的一个KKT点（局部最优点）。 这个框架是处理工程中复杂非线性、非凸优化问题的强大工具，特别是在航空航天（轨迹优化）、机器人（运动规划）等领域有广泛应用。