非线性规划中的信赖域反射-梯度投影-序列凸近似混合算法基础题
题目描述：
考虑如下非线性规划问题：
\[\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t.} \quad c_i(x) \leq 0, \ i=1,\dots,m, \quad Ax = b, \]
其中目标函数 \(f: \mathbb{R}^n \to \mathbb{R}\) 连续可微但不一定凸，不等式约束 \(c_i\) 光滑但可能非凸，等式约束 \(A \in \mathbb{R}^{p \times n}, b \in \mathbb{R}^p\) 为线性。要求设计一种混合算法，结合信赖域反射（Trust-Region Reflection, TRR）、梯度投影（Gradient Projection, GP）和序列凸近似（Sequential Convex Approximation, SCA）三种技术，在每次迭代中：
- 用SCA对非凸约束进行凸近似，得到局部凸子问题；
- 在信赖域内用梯度投影处理近似后的约束，确保迭代点可行；
- 利用信赖域反射框架控制步长并保证全局收敛。
给定具体函数形式：
\[f(x) = (x_1 - 2)^2 + (x_2 - 3)^2 + \sin(x_1 x_2), \quad c_1(x) = x_1^2 + x_2^2 - 4 \leq 0, \quad c_2(x) = e^{-x_1} - x_2 \leq 0, \quad x_1 + x_2 = 1. \]
初始点 \(x^0 = (0, 0)\)，信赖域初始半径 \(\Delta_0 = 1\)。请详细推导算法步骤，并展示第一次迭代的完整计算过程。
解题步骤详解
步骤1：算法框架设计
混合算法的核心思想是：
- 序列凸近似 (SCA)：将非凸约束在当前点 \(x^k\) 处用一阶泰勒展开近似为凸约束，使子问题易于求解。
- 梯度投影 (GP)：在信赖域内，将迭代点投影到线性化约束的可行集上，保持可行性。
- 信赖域反射 (TRR)：控制步长，通过实际下降与预测下降之比调整信赖域半径，保证收敛。
算法迭代格式：
在第 \(k\) 次迭代，当前点 \(x^k\)，信赖域半径 \(\Delta_k\)：
- 对每个非凸约束 \(c_i(x) \leq 0\) 在 \(x^k\) 处线性化：
\[ \tilde c_i(x; x^k) = c_i(x^k) + \nabla c_i(x^k)^\top (x - x^k) \leq 0. \]
注意：线性化后的约束是线性的（因此凸），原问题转化为局部凸优化子问题。
2. 在信赖域 \(\|x - x^k\| \leq \Delta_k\) 和线性等式约束 \(Ax = b\) 下，求解凸子问题：
\[ \min_{x} f(x) \quad \text{s.t.} \quad \tilde c_i(x; x^k) \leq 0,\ Ax = b,\ \|x - x^k\| \leq \Delta_k. \]
- 由于目标 \(f(x)\) 仍非凸，在子问题中采用梯度投影法求解：
- 计算梯度 \(\nabla f(x^k)\)，沿负梯度方向试探步进，然后投影到线性化约束的可行集上，得到候选点 \(x_\text{cand}\)。
- 计算实际下降与预测下降之比：
\[ \rho_k = \frac{f(x^k) - f(x_\text{cand})}{\hat f(x^k) - \hat f(x_\text{cand})}, \]
其中 \(\hat f\) 是 \(f\) 在 \(x^k\) 处的二阶近似或线性模型（这里采用线性模型 \(\hat f(x) = f(x^k) + \nabla f(x^k)^\top (x - x^k)\)）。
5. 根据比率 \(\rho_k\) 更新信赖域半径和迭代点（标准信赖域规则）。
步骤2：第一次迭代计算（\(k=0\)）
给定初始点 \(x^0 = (0,0)\)，初始信赖域半径 \(\Delta_0 = 1\)。
2.1 计算函数值与梯度
目标函数：
\[f(x) = (x_1 - 2)^2 + (x_2 - 3)^2 + \sin(x_1 x_2). \]
梯度：
\[\nabla f(x) = \begin{bmatrix} 2(x_1 - 2) + x_2 \cos(x_1 x_2) \\ 2(x_2 - 3) + x_1 \cos(x_1 x_2) \end{bmatrix}. \]
在 \(x^0 = (0,0)\) 处：
\[f(x^0) = (0-2)^2 + (0-3)^2 + \sin(0) = 4 + 9 + 0 = 13, \]
\[\nabla f(x^0) = \begin{bmatrix} 2(0-2) + 0 \cdot \cos(0) \\ 2(0-3) + 0 \cdot \cos(0) \end{bmatrix} = \begin{bmatrix} -4 \\ -6 \end{bmatrix}. \]
约束：
\[c_1(x) = x_1^2 + x_2^2 - 4 \leq 0, \quad \nabla c_1(x) = \begin{bmatrix} 2x_1 \\ 2x_2 \end{bmatrix}, \quad \nabla c_1(x^0) = \begin{bmatrix} 0 \\ 0 \end{bmatrix}. \]
\[c_2(x) = e^{-x_1} - x_2 \leq 0, \quad \nabla c_2(x) = \begin{bmatrix} -e^{-x_1} \\ -1 \end{bmatrix}, \quad \nabla c_2(x^0) = \begin{bmatrix} -1 \\ -1 \end{bmatrix}. \]
等式约束：
\[x_1 + x_2 = 1 \quad \Leftrightarrow \quad A = [1, 1],\ b = 1. \]
2.2 构造线性化约束（SCA步骤）
在 \(x^0\) 处线性化：
\[\tilde c_1(x; x^0) = c_1(0) + \nabla c_1(0)^\top (x - 0) = (0+0-4) + [0, 0] x = -4 \leq 0. \]
该约束自动满足（是不起作用的约束）。
\[\tilde c_2(x; x^0) = (e^0 - 0) + [-1, -1]^\top (x - 0) = 1 - x_1 - x_2 \leq 0. \]
因此，线性化后的不等式约束为：
\[-4 \leq 0 \quad (\text{冗余}), \quad 1 - x_1 - x_2 \leq 0. \]
再加上原始线性等式约束 \(x_1 + x_2 = 1\) 和信赖域约束 \(\|x - 0\| \leq 1\)。
2.3 梯度投影法求解子问题
子问题为：
\[\min_x f(x) \quad \text{s.t.} \quad 1 - x_1 - x_2 \leq 0,\ x_1 + x_2 = 1,\ x_1^2 + x_2^2 \leq 1. \]
注意：信赖域约束 \(\|x\|^2 \leq 1\) 与原约束可能有交集。
梯度投影法的迭代（在子问题内部）：
由于子问题规模小，我们可直接用解析法求解。实际上，梯度投影法在此处的含义是：在可行集上沿负梯度方向投影。但这里为清晰，我们直接求解该凸子问题（因为约束均为线性或球约束，且目标可用一阶近似简化）。
采用简化策略：在信赖域框架下，我们用线性模型 \(\hat f(x) = f(x^0) + \nabla f(x^0)^\top x = 13 - 4x_1 - 6x_2\) 近似目标，则子问题变为：
\[\min_{x} -4x_1 - 6x_2 \quad \text{s.t.} \quad 1 - x_1 - x_2 \leq 0,\ x_1 + x_2 = 1,\ x_1^2 + x_2^2 \leq 1. \]
（常数项不影响优化）
观察约束：
- 等式 \(x_1 + x_2 = 1\) 代入不等式 \(1 - x_1 - x_2 \leq 0\) 得 \(0 \leq 0\)，即不等式自动成立。
- 问题简化为：
\[\min -4x_1 - 6x_2 \quad \text{s.t.} \quad x_1 + x_2 = 1,\ x_1^2 + x_2^2 \leq 1. \]
代入 \(x_2 = 1 - x_1\)，则球约束变为：
\[x_1^2 + (1 - x_1)^2 \leq 1 \ \Rightarrow\ 2x_1^2 - 2x_1 + 1 \leq 1 \ \Rightarrow\ 2x_1^2 - 2x_1 \leq 0 \ \Rightarrow\ 2x_1(x_1 - 1) \leq 0. \]
解为 \(x_1 \in [0, 1]\)。目标函数变为：
\[-4x_1 - 6(1 - x_1) = 2x_1 - 6. \]
在 \(x_1 \in [0,1]\) 上最小化，最小值在 \(x_1 = 0\) 处取到，此时 \(x_2 = 1\)。但需检查是否在信赖域内：\(\|(0,1)\| = 1 \leq 1\)，满足。
因此子问题的最优解为 \(x_\text{sub} = (0, 1)\)。
2.4 计算候选点与预测下降
在子问题中我们最小化线性模型，得到 \(x_\text{cand} = (0, 1)\)。
计算线性模型在该点的值：
\[\hat f(x_\text{cand}) = 13 - 4\cdot 0 - 6\cdot 1 = 7. \]
预测下降为：
\[\text{pred} = \hat f(x^0) - \hat f(x_\text{cand}) = 13 - 7 = 6. \]
2.5 计算实际下降
真实目标函数在候选点的值：
\[f(x_\text{cand}) = (0-2)^2 + (1-3)^2 + \sin(0\cdot 1) = 4 + 4 + 0 = 8. \]
实际下降：
\[\text{ared} = f(x^0) - f(x_\text{cand}) = 13 - 8 = 5. \]
2.6 计算比率并更新信赖域
\[\rho_0 = \frac{\text{ared}}{\text{pred}} = \frac{5}{6} \approx 0.833. \]
标准信赖域规则：若 \(\rho > 0.75\)，接受步长（\(x^1 = x_\text{cand}\)），并扩大信赖域半径 \(\Delta_1 = 1.5 \Delta_0 = 1.5\)；若 \(\rho < 0.25\)，缩小半径。这里接受并扩大。
因此第一次迭代结果：
- 新迭代点 \(x^1 = (0, 1)\)，
- 新信赖域半径 \(\Delta_1 = 1.5\)，
- 目标函数值从 13 降至 8。
总结与后续迭代
以上完成了第一次迭代的详细计算。后续迭代重复相同步骤：
- 在当前点线性化非凸约束。
- 建立线性模型子问题，结合梯度投影思想求解。
- 根据实际下降与预测下降的比率调整信赖域半径，决定是否接受新点。
该混合算法利用了SCA处理非凸约束，GP确保可行性，TRR控制步长可靠性，适合中小规模非凸约束问题。