序列凸近似信赖域法基础题

字数 4830 2025-12-13 02:52:09

序列凸近似信赖域法基础题

我将为你讲解一个关于“序列凸近似信赖域法”的基础题目。这个方法在处理非凸约束优化问题时非常有用，特别是当目标函数和约束难以直接处理时。

题目描述

考虑以下带不等式约束的非线性规划问题：

\[\begin{aligned} \min_{x \in \mathbb{R}^2} \quad & f(x) = x_1^4 + x_2^4 - 4x_1x_2 + x_1^2 + x_2^2 \\ \text{s.t.} \quad & g_1(x) = x_1^2 + x_2^2 - 1 \le 0 \\ & g_2(x) = -x_1 - x_2 + 0.5 \le 0 \end{aligned} \]

其中 \(x = (x_1, x_2)^\top\)。该问题中，目标函数 \(f(x)\) 是非凸的（因为 \(x_1^4 + x_2^4 - 4x_1x_2\) 非凸），约束为凸（\(g_1\) 是凸二次函数，\(g_2\) 是线性函数）。任务：使用序列凸近似信赖域法（Sequential Convex Approximation Trust Region Method）求该问题的局部最优解。

解题过程循序渐进讲解

步骤1: 理解序列凸近似（SCA）的核心思想

序列凸近似法是一种迭代算法，用于求解非凸优化问题。其基本思路是：

在当前迭代点 \(x^k\) 处，构造原问题的一个凸近似子问题（通常通过对非凸函数进行一阶泰勒展开或凸替换）。
求解这个凸近似子问题，得到试探步 \(d^k\)。
结合信赖域（Trust Region）策略，限制步长大小，确保近似模型在当前邻域内足够精确。
根据实际函数下降与模型预测下降的比值，决定是否接受该步长，并更新信赖域半径。

对于本题，非凸性主要来自目标函数 \(f(x)\)。约束 \(g_1, g_2\) 已经是凸的，因此在近似子问题中可以直接保留。

步骤2: 构造凸近似子问题

在当前点 \(x^k = (x_1^k, x_2^k)^\top\)，我们需要构造 \(f(x)\) 的一个凸近似函数 \(\tilde{f}(x; x^k)\)。
观察 \(f(x) = x_1^4 + x_2^4 - 4x_1x_2 + x_1^2 + x_2^2\)。其中：

项 \(x_1^4 + x_2^4\) 是非凸的（因为四阶项非凸）。
项 \(-4x_1x_2\) 是双线性（非凸）。
项 \(x_1^2 + x_2^2\) 是凸的。

一种简单的凸近似方法是：对非凸部分进行一阶泰勒展开，并保留凸部分不变。但这里更好的做法是利用凸上界逼近：注意到 \(x_i^4\) 在任意点 \(x_i^k\) 处可以用一个凸二次函数上界来近似，例如利用二阶泰勒展开加上一个足够大的曲率修正以保证凸性。但作为基础题，我们采用更简单的线性化处理：

将 \(f(x)\) 分解为凸部分和非凸部分：

\[f(x) = \underbrace{x_1^2 + x_2^2}_{\text{凸部分}} + \underbrace{x_1^4 + x_2^4 - 4x_1x_2}_{\text{非凸部分}} \]

对非凸部分在 \(x^k\) 处进行一阶泰勒展开：

\[x_1^4 + x_2^4 - 4x_1x_2 \approx (x_1^k)^4 + (x_2^k)^4 - 4x_1^k x_2^k + \nabla h(x^k)^\top (x - x^k) \]

其中 \(h(x) = x_1^4 + x_2^4 - 4x_1x_2\)，梯度：

\[\nabla h(x) = \begin{pmatrix} 4x_1^3 - 4x_2 \\ 4x_2^3 - 4x_1 \end{pmatrix} \]

于是得到近似函数：

\[\tilde{f}(x; x^k) = x_1^2 + x_2^2 + (x_1^k)^4 + (x_2^k)^4 - 4x_1^k x_2^k + \nabla h(x^k)^\top (x - x^k) \]

这实际上是一个二次函数（因为 \(x_1^2+x_2^2\) 是二次项，其余为线性项），并且是凸的（因为二次项系数为正）。

因此，在第 \(k\) 次迭代的凸近似子问题为：

\[\begin{aligned} \min_{d \in \mathbb{R}^2} \quad & \tilde{f}(x^k + d; x^k) = f(x^k) + \nabla f(x^k)^\top d + \frac12 d^\top H_k d \\ \text{s.t.} \quad & g_1(x^k + d) \le 0 \\ & g_2(x^k + d) \le 0 \\ & \|d\|_\infty \le \Delta_k \end{aligned} \]

其中：

\(\nabla f(x^k) = \nabla h(x^k) + \begin{pmatrix} 2x_1^k \\ 2x_2^k \end{pmatrix} = \begin{pmatrix} 4(x_1^k)^3 - 4x_2^k + 2x_1^k \\ 4(x_2^k)^3 - 4x_1^k + 2x_2^k \end{pmatrix}\)。
\(H_k = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix}\) 是凸部分 \(x_1^2+x_2^2\) 的 Hessian（常数矩阵）。
\(\|d\|_\infty \le \Delta_k\) 是信赖域约束，保证步长 \(d\) 在无穷范数意义下不超过信赖域半径 \(\Delta_k\)，这是为了控制近似精度。

注意：约束 \(g_1(x^k+d) \le 0\) 和 \(g_2(x^k+d) \le 0\) 本身是凸的，因此子问题是凸二次规划（QP），可用有效算法（如积极集法、内点法）求解。

步骤3: 信赖域管理

求解凸近似子问题得到试探步 \(d^k\)。然后计算实际下降量与预测下降量的比值：

\[\rho_k = \frac{f(x^k) - f(x^k + d^k)}{\tilde{f}(x^k; x^k) - \tilde{f}(x^k + d^k; x^k)} \]

这里分母是模型预测的下降量（因为 \(\tilde{f}(x^k; x^k) = f(x^k)\)）。

根据比值 \(\rho_k\) 更新信赖域半径 \(\Delta_k\)：

如果 \(\rho_k\) 很大（例如 > 0.75），说明模型近似得很好，可以扩大信赖域： \(\Delta_{k+1} = 2\Delta_k\)。
如果 \(\rho_k\) 很小（例如 < 0.25），说明模型近似差，需要缩小信赖域： \(\Delta_{k+1} = 0.5\Delta_k\)。
否则保持半径不变： \(\Delta_{k+1} = \Delta_k\)。

同时，根据 \(\rho_k\) 决定是否接受该步：

如果 \(\rho_k > \eta\)（例如 \(\eta = 0.01\)），则接受步长： \(x^{k+1} = x^k + d^k\)。
否则拒绝步长： \(x^{k+1} = x^k\)，并在下一次迭代中用更小的信赖域重新尝试。

步骤4: 算法流程

初始化：选取初始点 \(x^0\)（例如 \(x^0 = (0.5, 0.5)\)），初始信赖域半径 \(\Delta_0 = 0.5\)，设定容忍误差 \(\epsilon = 10^{-6}\)，最大迭代次数 \(K_{\max} = 100\)。
迭代：对于 \(k=0,1,2,\dots\)：
a. 计算当前梯度 \(\nabla f(x^k)\) 和 Hessian \(H_k\)（本例中 \(H_k\) 是常数矩阵）。
b. 构造并求解凸近似子问题（QP），得到试探步 \(d^k\)。
c. 计算比值 \(\rho_k\)。
d. 根据 \(\rho_k\) 更新 \(x^{k+1}\) 和 \(\Delta_{k+1}\)。
e. 检查终止条件：如果 \(\|d^k\| < \epsilon\) 或 \(k \ge K_{\max}\)，则停止。
输出：最终点 \(x^*\) 作为局部最优解。

步骤5: 应用于本题的具体计算示例（一次迭代）

假设当前点 \(x^k = (0.5, 0.5)\)，\(\Delta_k = 0.5\)。

计算梯度：

\[ \nabla f(x^k) = \begin{pmatrix} 4(0.5)^3 - 4(0.5) + 2(0.5) \\ 4(0.5)^3 - 4(0.5) + 2(0.5) \end{pmatrix} = \begin{pmatrix} 0.5 - 2 + 1 \\ 0.5 - 2 + 1 \end{pmatrix} = \begin{pmatrix} -0.5 \\ -0.5 \end{pmatrix} \]

Hessian \(H_k = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix}\)。
子问题目标函数：

\[ \tilde{f}(x^k+d; x^k) = f(x^k) + (-0.5, -0.5) d + \frac12 d^\top \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} d = f(x^k) -0.5d_1 -0.5d_2 + d_1^2 + d_2^2 \]

约束：

\[ g_1(x^k+d) = (0.5+d_1)^2 + (0.5+d_2)^2 - 1 \le 0 \]

\[ g_2(x^k+d) = -(0.5+d_1) - (0.5+d_2) + 0.5 = -d_1 - d_2 -0.5 \le 0 \]

\[ \|d\|_\infty \le 0.5 \]

这是一个凸二次规划，可用标准QP求解器求解。假设解得 \(d^k = (0.1, 0.1)\)（仅为示例）。

计算比值：
实际下降 \(f(x^k) - f(x^k+d^k)\) 和模型下降 \(\tilde{f}(x^k; x^k) - \tilde{f}(x^k+d^k; x^k)\)（略去具体数值计算）。
根据比值更新半径和迭代点。

步骤6: 收敛性与讨论

序列凸近似信赖域法通常能收敛到一个稳定点（即满足一阶必要条件的点）。对于本题，由于目标函数非凸，可能收敛到局部极小点。可以从不同初始点尝试以避免糟糕的局部解。

此方法的关键优势是将非凸问题转化为一系列凸子问题，同时利用信赖域控制近似质量，保证全局收敛性。在工程优化中广泛应用，尤其适用于目标函数或约束复杂但可局部凸化的情况。

如果你希望，我可以进一步展示如何用编程实现该算法的伪代码或讨论更复杂的凸近似技巧。

序列凸近似信赖域法基础题我将为你讲解一个关于“序列凸近似信赖域法”的基础题目。这个方法在处理非凸约束优化问题时非常有用，特别是当目标函数和约束难以直接处理时。题目描述考虑以下带不等式约束的非线性规划问题： \[ \begin{aligned} \min_ {x \in \mathbb{R}^2} \quad & f(x) = x_ 1^4 + x_ 2^4 - 4x_ 1x_ 2 + x_ 1^2 + x_ 2^2 \\ \text{s.t.} \quad & g_ 1(x) = x_ 1^2 + x_ 2^2 - 1 \le 0 \\ & g_ 2(x) = -x_ 1 - x_ 2 + 0.5 \le 0 \end{aligned} \] 其中 \( x = (x_ 1, x_ 2)^\top \)。该问题中，目标函数 \( f(x) \) 是非凸的（因为 \( x_ 1^4 + x_ 2^4 - 4x_ 1x_ 2 \) 非凸），约束为凸（\( g_ 1 \) 是凸二次函数，\( g_ 2 \) 是线性函数）。任务：使用序列凸近似信赖域法（Sequential Convex Approximation Trust Region Method）求该问题的局部最优解。解题过程循序渐进讲解步骤1: 理解序列凸近似（SCA）的核心思想序列凸近似法是一种迭代算法，用于求解非凸优化问题。其基本思路是：在当前迭代点 \( x^k \) 处，构造原问题的一个凸近似子问题（通常通过对非凸函数进行一阶泰勒展开或凸替换）。求解这个凸近似子问题，得到试探步 \( d^k \)。结合信赖域（Trust Region）策略，限制步长大小，确保近似模型在当前邻域内足够精确。根据实际函数下降与模型预测下降的比值，决定是否接受该步长，并更新信赖域半径。对于本题，非凸性主要来自目标函数 \( f(x) \)。约束 \( g_ 1, g_ 2 \) 已经是凸的，因此在近似子问题中可以直接保留。步骤2: 构造凸近似子问题在当前点 \( x^k = (x_ 1^k, x_ 2^k)^\top \)，我们需要构造 \( f(x) \) 的一个凸近似函数 \( \tilde{f}(x; x^k) \)。观察 \( f(x) = x_ 1^4 + x_ 2^4 - 4x_ 1x_ 2 + x_ 1^2 + x_ 2^2 \)。其中：项 \( x_ 1^4 + x_ 2^4 \) 是非凸的（因为四阶项非凸）。项 \( -4x_ 1x_ 2 \) 是双线性（非凸）。项 \( x_ 1^2 + x_ 2^2 \) 是凸的。一种简单的凸近似方法是：对非凸部分进行一阶泰勒展开，并保留凸部分不变。但这里更好的做法是利用凸上界逼近：注意到 \( x_ i^4 \) 在任意点 \( x_ i^k \) 处可以用一个凸二次函数上界来近似，例如利用二阶泰勒展开加上一个足够大的曲率修正以保证凸性。但作为基础题，我们采用更简单的线性化处理：将 \( f(x) \) 分解为凸部分和非凸部分： \[ f(x) = \underbrace{x_ 1^2 + x_ 2^2} {\text{凸部分}} + \underbrace{x_ 1^4 + x_ 2^4 - 4x_ 1x_ 2} {\text{非凸部分}} \] 对非凸部分在 \( x^k \) 处进行一阶泰勒展开： \[ x_ 1^4 + x_ 2^4 - 4x_ 1x_ 2 \approx (x_ 1^k)^4 + (x_ 2^k)^4 - 4x_ 1^k x_ 2^k + \nabla h(x^k)^\top (x - x^k) \] 其中 \( h(x) = x_ 1^4 + x_ 2^4 - 4x_ 1x_ 2 \)，梯度： \[ \nabla h(x) = \begin{pmatrix} 4x_ 1^3 - 4x_ 2 \\ 4x_ 2^3 - 4x_ 1 \end{pmatrix} \] 于是得到近似函数： \[ \tilde{f}(x; x^k) = x_ 1^2 + x_ 2^2 + (x_ 1^k)^4 + (x_ 2^k)^4 - 4x_ 1^k x_ 2^k + \nabla h(x^k)^\top (x - x^k) \] 这实际上是一个二次函数（因为 \( x_ 1^2+x_ 2^2 \) 是二次项，其余为线性项），并且是凸的（因为二次项系数为正）。因此，在第 \( k \) 次迭代的凸近似子问题为： \[ \begin{aligned} \min_ {d \in \mathbb{R}^2} \quad & \tilde{f}(x^k + d; x^k) = f(x^k) + \nabla f(x^k)^\top d + \frac12 d^\top H_ k d \\ \text{s.t.} \quad & g_ 1(x^k + d) \le 0 \\ & g_ 2(x^k + d) \le 0 \\ & \|d\|_ \infty \le \Delta_ k \end{aligned} \] 其中： \( \nabla f(x^k) = \nabla h(x^k) + \begin{pmatrix} 2x_ 1^k \\ 2x_ 2^k \end{pmatrix} = \begin{pmatrix} 4(x_ 1^k)^3 - 4x_ 2^k + 2x_ 1^k \\ 4(x_ 2^k)^3 - 4x_ 1^k + 2x_ 2^k \end{pmatrix} \)。 \( H_ k = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} \) 是凸部分 \( x_ 1^2+x_ 2^2 \) 的 Hessian（常数矩阵）。 \( \|d\|_ \infty \le \Delta_ k \) 是信赖域约束，保证步长 \( d \) 在无穷范数意义下不超过信赖域半径 \( \Delta_ k \)，这是为了控制近似精度。注意：约束 \( g_ 1(x^k+d) \le 0 \) 和 \( g_ 2(x^k+d) \le 0 \) 本身是凸的，因此子问题是凸二次规划（QP），可用有效算法（如积极集法、内点法）求解。步骤3: 信赖域管理求解凸近似子问题得到试探步 \( d^k \)。然后计算实际下降量与预测下降量的比值： \[ \rho_ k = \frac{f(x^k) - f(x^k + d^k)}{\tilde{f}(x^k; x^k) - \tilde{f}(x^k + d^k; x^k)} \] 这里分母是模型预测的下降量（因为 \( \tilde{f}(x^k; x^k) = f(x^k) \)）。根据比值 \( \rho_ k \) 更新信赖域半径 \( \Delta_ k \)：如果 \( \rho_ k \) 很大（例如 > 0.75），说明模型近似得很好，可以扩大信赖域： \( \Delta_ {k+1} = 2\Delta_ k \)。如果 \( \rho_ k \) 很小（例如 < 0.25），说明模型近似差，需要缩小信赖域： \( \Delta_ {k+1} = 0.5\Delta_ k \)。否则保持半径不变： \( \Delta_ {k+1} = \Delta_ k \)。同时，根据 \( \rho_ k \) 决定是否接受该步：如果 \( \rho_ k > \eta \)（例如 \( \eta = 0.01 \)），则接受步长： \( x^{k+1} = x^k + d^k \)。否则拒绝步长： \( x^{k+1} = x^k \)，并在下一次迭代中用更小的信赖域重新尝试。步骤4: 算法流程初始化：选取初始点 \( x^0 \)（例如 \( x^0 = (0.5, 0.5) \)），初始信赖域半径 \( \Delta_ 0 = 0.5 \)，设定容忍误差 \( \epsilon = 10^{-6} \)，最大迭代次数 \( K_ {\max} = 100 \)。迭代：对于 \( k=0,1,2,\dots \)： a. 计算当前梯度 \( \nabla f(x^k) \) 和 Hessian \( H_ k \)（本例中 \( H_ k \) 是常数矩阵）。 b. 构造并求解凸近似子问题（QP），得到试探步 \( d^k \)。 c. 计算比值 \( \rho_ k \)。 d. 根据 \( \rho_ k \) 更新 \( x^{k+1} \) 和 \( \Delta_ {k+1} \)。 e. 检查终止条件：如果 \( \|d^k\| < \epsilon \) 或 \( k \ge K_ {\max} \)，则停止。输出：最终点 \( x^* \) 作为局部最优解。步骤5: 应用于本题的具体计算示例（一次迭代）假设当前点 \( x^k = (0.5, 0.5) \)，\( \Delta_ k = 0.5 \)。计算梯度： \[ \nabla f(x^k) = \begin{pmatrix} 4(0.5)^3 - 4(0.5) + 2(0.5) \\ 4(0.5)^3 - 4(0.5) + 2(0.5) \end{pmatrix} = \begin{pmatrix} 0.5 - 2 + 1 \\ 0.5 - 2 + 1 \end{pmatrix} = \begin{pmatrix} -0.5 \\ -0.5 \end{pmatrix} \] Hessian \( H_ k = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} \)。子问题目标函数： \[ \tilde{f}(x^k+d; x^k) = f(x^k) + (-0.5, -0.5) d + \frac12 d^\top \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} d = f(x^k) -0.5d_ 1 -0.5d_ 2 + d_ 1^2 + d_ 2^2 \] 约束： \[ g_ 1(x^k+d) = (0.5+d_ 1)^2 + (0.5+d_ 2)^2 - 1 \le 0 \] \[ g_ 2(x^k+d) = -(0.5+d_ 1) - (0.5+d_ 2) + 0.5 = -d_ 1 - d_ 2 -0.5 \le 0 \] \[ \|d\|_ \infty \le 0.5 \] 这是一个凸二次规划，可用标准QP求解器求解。假设解得 \( d^k = (0.1, 0.1) \)（仅为示例）。计算比值：实际下降 \( f(x^k) - f(x^k+d^k) \) 和模型下降 \( \tilde{f}(x^k; x^k) - \tilde{f}(x^k+d^k; x^k) \)（略去具体数值计算）。根据比值更新半径和迭代点。步骤6: 收敛性与讨论序列凸近似信赖域法通常能收敛到一个稳定点（即满足一阶必要条件的点）。对于本题，由于目标函数非凸，可能收敛到局部极小点。可以从不同初始点尝试以避免糟糕的局部解。此方法的关键优势是将非凸问题转化为一系列凸子问题，同时利用信赖域控制近似质量，保证全局收敛性。在工程优化中广泛应用，尤其适用于目标函数或约束复杂但可局部凸化的情况。如果你希望，我可以进一步展示如何用编程实现该算法的伪代码或讨论更复杂的凸近似技巧。