非线性规划中的逐步凸逼近算法进阶题
题目描述
考虑非线性规划问题：
\[\min f(x) \quad \text{s.t.} \quad g_i(x) \leq 0, \quad i = 1, \dots, m, \]
其中目标函数 \(f(x)\) 和约束函数 \(g_i(x)\) 均为非凸且可能不可微。逐步凸逼近（Sequential Convex Approximation, SCA）算法通过迭代求解一系列凸子问题来逼近原问题。本题要求：
- 设计SCA算法的迭代框架，包括凸近似子问题的构建。
- 分析算法的收敛条件。
- 针对具体函数 \(f(x) = \log(1 + x^2)\) 和 \(g(x) = x^2 - 4x + 3 \leq 0\)，从初始点 \(x_0 = 0\) 开始，执行两次SCA迭代。
解题过程
1. 算法框架设计
SCA的核心思想是将非凸问题转化为一系列凸子问题。在第 \(k\) 次迭代中：
-
凸近似构建：
对目标函数和约束函数在当前点 \(x_k\) 附近构造凸替代函数 \(\tilde{f}(x; x_k)\) 和 \(\tilde{g}_i(x; x_k)\)，满足：- 替代函数是凸的。
- 函数值匹配：\(\tilde{f}(x_k; x_k) = f(x_k)\)，\(\tilde{g}_i(x_k; x_k) = g_i(x_k)\)。
- 梯度匹配（若可微）：\(\nabla \tilde{f}(x_k; x_k) = \nabla f(x_k)\)，\(\nabla \tilde{g}_i(x_k; x_k) = \nabla g_i(x_k)\)。
- 全局上界或下界条件（例如，替代函数是原函数的上界或下界）。
-
子问题求解：
求解凸优化问题：
\[ \min_x \tilde{f}(x; x_k) \quad \text{s.t.} \quad \tilde{g}_i(x; x_k) \leq 0. \]
得到下一步迭代点 \(x_{k+1}\)。
- 收敛条件：
当 \(\|x_{k+1} - x_k\| < \epsilon\) 或迭代次数达到上限时停止。
2. 收敛性分析
SCA的收敛性需满足以下条件：
- 替代函数性质：替代函数需一致强凸且梯度 Lipschitz 连续，确保子问题有唯一解。
- 目标下降：每次迭代需满足 \(f(x_{k+1}) \leq f(x_k) + \alpha \nabla f(x_k)^\top (x_{k+1} - x_k)\)（充分下降条件）。
- 约束处理：替代约束需满足 \(\tilde{g}_i(x; x_k) \geq g_i(x)\)，确保子问题的可行域包含于原问题可行域。
3. 实例计算
给定问题：
\[\min f(x) = \log(1 + x^2) \quad \text{s.t.} \quad g(x) = x^2 - 4x + 3 \leq 0. \]
- 初始点：\(x_0 = 0\)。
- 凸近似构建：
对 \(f(x)\)，使用一阶泰勒展开（线性化）作为凸替代：
\[ \tilde{f}(x; x_k) = \log(1 + x_k^2) + \frac{2x_k}{1 + x_k^2}(x - x_k). \]
对 \(g(x)\)，因其为凸函数（二次项系数为正），可直接用作替代函数：\(\tilde{g}(x; x_k) = g(x)\)。
- 第一次迭代（k=0）：
- 计算梯度：\(f'(x) = \frac{2x}{1 + x^2}\)，在 \(x_0 = 0\) 处有 \(f'(0) = 0\)。
- 子问题：
\[ \min_x \tilde{f}(x; 0) = \log(1) + 0 \cdot (x - 0) = 0 \quad \text{s.t.} \quad x^2 - 4x + 3 \leq 0. \]
目标函数恒为0，约束为 $ (x-1)(x-3) \leq 0 $，即 $ x \in [1, 3] $。任意 $ x \in [1, 3] $ 均为解，选择最小范数点 $ x_1 = 1 $。
- 第二次迭代（k=1）：
- 在 \(x_1 = 1\) 处，梯度 \(f'(1) = \frac{2}{2} = 1\)。
- 子问题：
\[ \min_x \tilde{f}(x; 1) = \log(2) + 1 \cdot (x - 1) \quad \text{s.t.} \quad x^2 - 4x + 3 \leq 0. \]
目标函数为线性函数 $ x + (\log 2 - 1) $，在区间 $ [1, 3] $ 上最小化，最小值在 $ x = 1 $ 处取得。因此 $ x_2 = 1 $。
- 结果：两次迭代后 \(x_2 = 1\)，满足约束且目标函数值为 \(\log(2)\)。
4. 关键点总结
- SCA通过凸近似将非凸问题转化为可求解的子问题。
- 替代函数需满足匹配条件和凸性，收敛性依赖替代函数的构造和初始点选择。
- 本例中，由于目标函数非凸但约束为凸，算法快速收敛到可行解 \(x = 1\)。