非线性规划中的内点法（Interior-Point Method）进阶题：带非线性等式与不等式约束的凸优化问题

字数 4746 2025-12-19 12:11:49

非线性规划中的内点法（Interior-Point Method）进阶题：带非线性等式与不等式约束的凸优化问题

题目描述

考虑如下凸优化问题：

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

其中目标函数 \(f: \mathbb{R}^n \to \mathbb{R}\) 是凸函数，等式约束 \(h_i: \mathbb{R}^n \to \mathbb{R}\) 是线性或非线性凸函数，不等式约束 \(g_j: \mathbb{R}^n \to \mathbb{R}\) 是凸函数。假设问题满足Slater约束规格（即存在一个可行内点，使所有不等式约束严格成立）。请用内点法（也称障碍法）来求解该问题，详细解释如何将不等式约束转化为对数障碍函数，并结合等式约束的拉格朗日乘子，通过牛顿法迭代求解。要求分析算法的收敛性、步长选择策略，并说明如何保证迭代点始终保持在可行域内部。

解题过程

第一步：构造障碍函数，处理不等式约束

内点法的核心思想是通过一个“障碍”项，将不等式约束 \(g_j(x) \leq 0\) 吸收进目标函数，使得迭代点被阻挡在可行域的边界内部（即严格满足 \(g_j(x) < 0\)）。

定义对数障碍函数为：

\[\Phi(x) = -\sum_{j=1}^{m} \ln(-g_j(x)). \]

该函数在 \(g_j(x) < 0\) 时有定义，当 \(g_j(x) \to 0^{-}\) 时，\(\Phi(x) \to +\infty\)，形成一道“屏障”，阻止迭代点越界。

引入障碍参数 \(\mu > 0\)，将原问题转化为一系列无约束子问题（或仅含等式约束的问题）：

\[\min_{x \in \mathbb{R}^n} \; f(x) + \mu \Phi(x) \quad \text{s.t.} \quad h_i(x) = 0, \; i=1,\ldots,p. \]

当 \(\mu \to 0^{+}\) 时，上述问题的解应趋近于原问题的最优解。

第二步：构造增广拉格朗日函数，处理等式约束

对于带有等式约束的子问题，可使用拉格朗日乘子法。定义拉格朗日函数：

\[L_{\mu}(x, \lambda) = f(x) + \mu \Phi(x) + \sum_{i=1}^{p} \lambda_i h_i(x), \]

其中 \(\lambda_i\) 是对应等式约束的拉格朗日乘子。注意，这里我们没有为不等式约束引入乘子，因为它们已经被障碍函数隐式处理了。

第三步：写出最优性条件（KKT 条件）

对凸问题，最优解满足 Karush–Kuhn–Tucker (KKT) 条件。对上述子问题，KKT 条件为：

\[\begin{aligned} \nabla_x L_{\mu}(x, \lambda) &= \nabla f(x) - \mu \sum_{j=1}^{m} \frac{\nabla g_j(x)}{g_j(x)} + \sum_{i=1}^{p} \lambda_i \nabla h_i(x) = 0, \\ h_i(x) &= 0, \quad i=1,\ldots,p, \\ g_j(x) &< 0, \quad j=1,\ldots,m. \end{aligned} \]

注意，这里不等式约束严格成立，这是内点法迭代中必须保持的性质。

第四步：引入松弛变量，便于推导迭代格式

为更清晰地推导牛顿步，可引入松弛变量 \(s_j > 0\)，使得 \(g_j(x) + s_j = 0\)。于是障碍函数可写为 \(\Phi(x) = -\sum_{j=1}^{m} \ln s_j\)。对应的 KKT 系统可写为：

\[\begin{aligned} \nabla f(x) + \sum_{i=1}^{p} \lambda_i \nabla h_i(x) + \sum_{j=1}^{m} z_j \nabla g_j(x) &= 0, \\ h_i(x) &= 0, \quad i=1,\ldots,p, \\ g_j(x) + s_j &= 0, \quad j=1,\ldots,m, \\ z_j s_j &= \mu, \quad j=1,\ldots,m, \\ z_j, s_j &> 0, \quad j=1,\ldots,m, \end{aligned} \]

其中 \(z_j = \mu / s_j > 0\) 可视为不等式约束的“近似”拉格朗日乘子（在 \(\mu \to 0\) 时趋近于真实乘子）。最后一组条件 \(z_j s_j = \mu\) 称为“中心路径条件”，定义了中心路径，是内点法的核心。

第五步：牛顿法求解 KKT 系统

在给定当前迭代点 \((x^k, \lambda^k, z^k, s^k)\) 和障碍参数 \(\mu^k > 0\) 时，我们对上述非线性方程组应用牛顿法。将方程写为 \(F(x, \lambda, z, s) = 0\)，其雅可比矩阵为：

\[J = \begin{bmatrix} H & A_h^T & A_g^T & 0 \\ A_h & 0 & 0 & 0 \\ A_g & 0 & 0 & I \\ 0 & 0 & S & Z \end{bmatrix}, \]

其中：

\(H = \nabla^2 f(x) + \sum_i \lambda_i \nabla^2 h_i(x) + \sum_j z_j \nabla^2 g_j(x)\) 是拉格朗日函数的 Hessian 矩阵。
\(A_h = [\nabla h_1(x), \ldots, \nabla h_p(x)]^T\) 是等式约束的雅可比矩阵。
\(A_g = [\nabla g_1(x), \ldots, \nabla g_m(x)]^T\) 是不等式约束的雅可比矩阵。
\(S = \text{diag}(s_1, \ldots, s_m)\)，\(Z = \text{diag}(z_1, \ldots, z_m)\)。

牛顿步 \((\Delta x, \Delta \lambda, \Delta z, \Delta s)\) 通过求解以下线性系统得到：

\[\begin{bmatrix} H & A_h^T & A_g^T & 0 \\ A_h & 0 & 0 & 0 \\ A_g & 0 & 0 & I \\ 0 & 0 & S & Z \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta \lambda \\ \Delta z \\ \Delta s \end{bmatrix} = - \begin{bmatrix} r_d \\ r_h \\ r_g \\ r_c \end{bmatrix}, \]

其中残差为：

\[\begin{aligned} r_d &= \nabla f(x) + A_h^T \lambda + A_g^T z, \\ r_h &= h(x), \\ r_g &= g(x) + s, \\ r_c &= S z - \mu e, \quad e = [1, \ldots, 1]^T. \end{aligned} \]

第六步：迭代更新与步长选择

更新迭代点：

\[\begin{aligned} x^{+} &= x + \alpha \Delta x, \\ \lambda^{+} &= \lambda + \alpha \Delta \lambda, \\ z^{+} &= z + \alpha \Delta z, \\ s^{+} &= s + \alpha \Delta s, \end{aligned} \]

其中步长 \(\alpha \in (0,1]\) 需选择以保证 \(s^{+} > 0\) 和 \(z^{+} > 0\)。

步长选择策略通常包括：

最大步长：计算 \(\alpha_{\max} = \max\{\alpha \in (0,1] : s + \alpha \Delta s \geq (1-\tau)s\}\)，其中 \(\tau \in (0,1)\) 是安全系数（如 0.995），避免触及边界。
回溯直线搜索：在区间 \((0, \alpha_{\max}]\) 内，通过回溯（如 Armijo 条件）选择 \(\alpha\)，使某个效益函数（如 KKT 残差的范数）充分下降。
固定分数步长：直接取 \(\alpha = 0.99 \alpha_{\max}\)，简单有效。

第七步：障碍参数更新

每次迭代后，需更新障碍参数 \(\mu\)，以逐渐逼近原问题。常用更新规则为：

\[\mu^{+} = \sigma \mu, \]

其中 \(\sigma \in (0,1)\) 是衰减因子（如 0.1）。也可根据当前对偶间隙（duality gap）\(s^T z\) 来设置 \(\mu = (s^T z) / m\) 的某个比例。

第八步：收敛性判断

算法在以下条件满足时终止：

\[\|r_d\| \leq \epsilon_1, \quad \|r_h\| \leq \epsilon_2, \quad |s^T z| \leq \epsilon_3, \]

其中 \(\epsilon_1, \epsilon_2, \epsilon_3\) 是预设的容差。

第九步：收敛性分析

在凸性假设和 Slater 条件下，内点法具有全局收敛性：

当 \(\mu \to 0\) 时，迭代点沿中心路径收敛到原问题的最优点。
牛顿步是局部二次收敛的，但全局收敛性需通过步长选择保证。
通常需要 \(O(\sqrt{m} \log(1/\epsilon))\) 次外层迭代（\(\mu\) 更新次数）达到精度 \(\epsilon\)，每次外层迭代内牛顿法迭代次数有限。

第十步：算法总结与讨论

初始化：选择初始内点 \(x^0\) 满足 \(g(x^0) < 0\) 和 \(h(x^0)=0\)，初始乘子 \(\lambda^0, z^0 > 0\)，初始障碍参数 \(\mu^0 > 0\)。
迭代：直到满足收敛条件：
a. 求解牛顿步线性系统。
b. 计算步长 \(\alpha\)，更新迭代点。
c. 更新障碍参数 \(\mu\)。
输出：近似最优解 \(x^*\) 和对应的乘子 \(\lambda^*, z^*\)。

该方法的关键在于始终维持严格可行性（\(g(x) < 0, z > 0\)），从而避免边界上的奇异性，并利用牛顿法快速逼近中心路径。对于大规模问题，线性系统的求解可借助稀疏矩阵技术或迭代法加速。

非线性规划中的内点法（Interior-Point Method）进阶题：带非线性等式与不等式约束的凸优化问题题目描述考虑如下凸优化问题： \[ \begin{aligned} \min_ {x \in \mathbb{R}^n} \quad & f(x) \\ \text{s.t.} \quad & h_ i(x) = 0, \quad i = 1, \ldots, p, \\ & g_ j(x) \leq 0, \quad j = 1, \ldots, m, \end{aligned} \] 其中目标函数 \(f: \mathbb{R}^n \to \mathbb{R}\) 是凸函数，等式约束 \(h_ i: \mathbb{R}^n \to \mathbb{R}\) 是线性或非线性凸函数，不等式约束 \(g_ j: \mathbb{R}^n \to \mathbb{R}\) 是凸函数。假设问题满足 Slater约束规格（即存在一个可行内点，使所有不等式约束严格成立）。请用内点法（也称障碍法）来求解该问题，详细解释如何将不等式约束转化为对数障碍函数，并结合等式约束的拉格朗日乘子，通过牛顿法迭代求解。要求分析算法的收敛性、步长选择策略，并说明如何保证迭代点始终保持在可行域内部。解题过程第一步：构造障碍函数，处理不等式约束内点法的核心思想是通过一个“障碍”项，将不等式约束 \(g_ j(x) \leq 0\) 吸收进目标函数，使得迭代点被阻挡在可行域的边界内部（即严格满足 \(g_ j(x) < 0\)）。定义对数障碍函数为： \[ \Phi(x) = -\sum_ {j=1}^{m} \ln(-g_ j(x)). \] 该函数在 \(g_ j(x) < 0\) 时有定义，当 \(g_ j(x) \to 0^{-}\) 时，\(\Phi(x) \to +\infty\)，形成一道“屏障”，阻止迭代点越界。引入障碍参数 \(\mu > 0\)，将原问题转化为一系列无约束子问题（或仅含等式约束的问题）： \[ \min_ {x \in \mathbb{R}^n} \; f(x) + \mu \Phi(x) \quad \text{s.t.} \quad h_ i(x) = 0, \; i=1,\ldots,p. \] 当 \(\mu \to 0^{+}\) 时，上述问题的解应趋近于原问题的最优解。第二步：构造增广拉格朗日函数，处理等式约束对于带有等式约束的子问题，可使用拉格朗日乘子法。定义拉格朗日函数： \[ L_ {\mu}(x, \lambda) = f(x) + \mu \Phi(x) + \sum_ {i=1}^{p} \lambda_ i h_ i(x), \] 其中 \(\lambda_ i\) 是对应等式约束的拉格朗日乘子。注意，这里我们没有为不等式约束引入乘子，因为它们已经被障碍函数隐式处理了。第三步：写出最优性条件（KKT 条件）对凸问题，最优解满足 Karush–Kuhn–Tucker (KKT) 条件。对上述子问题，KKT 条件为： \[ \begin{aligned} \nabla_ x L_ {\mu}(x, \lambda) &= \nabla f(x) - \mu \sum_ {j=1}^{m} \frac{\nabla g_ j(x)}{g_ j(x)} + \sum_ {i=1}^{p} \lambda_ i \nabla h_ i(x) = 0, \\ h_ i(x) &= 0, \quad i=1,\ldots,p, \\ g_ j(x) & < 0, \quad j=1,\ldots,m. \end{aligned} \] 注意，这里不等式约束严格成立，这是内点法迭代中必须保持的性质。第四步：引入松弛变量，便于推导迭代格式为更清晰地推导牛顿步，可引入松弛变量 \(s_ j > 0\)，使得 \(g_ j(x) + s_ j = 0\)。于是障碍函数可写为 \(\Phi(x) = -\sum_ {j=1}^{m} \ln s_ j\)。对应的 KKT 系统可写为： \[ \begin{aligned} \nabla f(x) + \sum_ {i=1}^{p} \lambda_ i \nabla h_ i(x) + \sum_ {j=1}^{m} z_ j \nabla g_ j(x) &= 0, \\ h_ i(x) &= 0, \quad i=1,\ldots,p, \\ g_ j(x) + s_ j &= 0, \quad j=1,\ldots,m, \\ z_ j s_ j &= \mu, \quad j=1,\ldots,m, \\ z_ j, s_ j &> 0, \quad j=1,\ldots,m, \end{aligned} \] 其中 \(z_ j = \mu / s_ j > 0\) 可视为不等式约束的“近似”拉格朗日乘子（在 \(\mu \to 0\) 时趋近于真实乘子）。最后一组条件 \(z_ j s_ j = \mu\) 称为“中心路径条件”，定义了中心路径，是内点法的核心。第五步：牛顿法求解 KKT 系统在给定当前迭代点 \((x^k, \lambda^k, z^k, s^k)\) 和障碍参数 \(\mu^k > 0\) 时，我们对上述非线性方程组应用牛顿法。将方程写为 \(F(x, \lambda, z, s) = 0\)，其雅可比矩阵为： \[ J = \begin{bmatrix} H & A_ h^T & A_ g^T & 0 \\ A_ h & 0 & 0 & 0 \\ A_ g & 0 & 0 & I \\ 0 & 0 & S & Z \end{bmatrix}, \] 其中： \(H = \nabla^2 f(x) + \sum_ i \lambda_ i \nabla^2 h_ i(x) + \sum_ j z_ j \nabla^2 g_ j(x)\) 是拉格朗日函数的 Hessian 矩阵。 \(A_ h = [ \nabla h_ 1(x), \ldots, \nabla h_ p(x) ]^T\) 是等式约束的雅可比矩阵。 \(A_ g = [ \nabla g_ 1(x), \ldots, \nabla g_ m(x) ]^T\) 是不等式约束的雅可比矩阵。 \(S = \text{diag}(s_ 1, \ldots, s_ m)\)，\(Z = \text{diag}(z_ 1, \ldots, z_ m)\)。牛顿步 \((\Delta x, \Delta \lambda, \Delta z, \Delta s)\) 通过求解以下线性系统得到： \[ \begin{bmatrix} H & A_ h^T & A_ g^T & 0 \\ A_ h & 0 & 0 & 0 \\ A_ g & 0 & 0 & I \\ 0 & 0 & S & Z \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta \lambda \\ \Delta z \\ \Delta s \end{bmatrix} = - \begin{bmatrix} r_ d \\ r_ h \\ r_ g \\ r_ c \end{bmatrix}, \] 其中残差为： \[ \begin{aligned} r_ d &= \nabla f(x) + A_ h^T \lambda + A_ g^T z, \\ r_ h &= h(x), \\ r_ g &= g(x) + s, \\ r_ c &= S z - \mu e, \quad e = [ 1, \ldots, 1 ]^T. \end{aligned} \] 第六步：迭代更新与步长选择更新迭代点： \[ \begin{aligned} x^{+} &= x + \alpha \Delta x, \\ \lambda^{+} &= \lambda + \alpha \Delta \lambda, \\ z^{+} &= z + \alpha \Delta z, \\ s^{+} &= s + \alpha \Delta s, \end{aligned} \] 其中步长 \(\alpha \in (0,1 ]\) 需选择以保证 \(s^{+} > 0\) 和 \(z^{+} > 0\)。步长选择策略通常包括：最大步长：计算 \(\alpha_ {\max} = \max\{\alpha \in (0,1 ] : s + \alpha \Delta s \geq (1-\tau)s\}\)，其中 \(\tau \in (0,1)\) 是安全系数（如 0.995），避免触及边界。回溯直线搜索：在区间 \((0, \alpha_ {\max} ]\) 内，通过回溯（如 Armijo 条件）选择 \(\alpha\)，使某个效益函数（如 KKT 残差的范数）充分下降。固定分数步长：直接取 \(\alpha = 0.99 \alpha_ {\max}\)，简单有效。第七步：障碍参数更新每次迭代后，需更新障碍参数 \(\mu\)，以逐渐逼近原问题。常用更新规则为： \[ \mu^{+} = \sigma \mu, \] 其中 \(\sigma \in (0,1)\) 是衰减因子（如 0.1）。也可根据当前对偶间隙（duality gap）\(s^T z\) 来设置 \(\mu = (s^T z) / m\) 的某个比例。第八步：收敛性判断算法在以下条件满足时终止： \[ \|r_ d\| \leq \epsilon_ 1, \quad \|r_ h\| \leq \epsilon_ 2, \quad |s^T z| \leq \epsilon_ 3, \] 其中 \(\epsilon_ 1, \epsilon_ 2, \epsilon_ 3\) 是预设的容差。第九步：收敛性分析在凸性假设和 Slater 条件下，内点法具有全局收敛性：当 \(\mu \to 0\) 时，迭代点沿中心路径收敛到原问题的最优点。牛顿步是局部二次收敛的，但全局收敛性需通过步长选择保证。通常需要 \(O(\sqrt{m} \log(1/\epsilon))\) 次外层迭代（\(\mu\) 更新次数）达到精度 \(\epsilon\)，每次外层迭代内牛顿法迭代次数有限。第十步：算法总结与讨论初始化：选择初始内点 \(x^0\) 满足 \(g(x^0) < 0\) 和 \(h(x^0)=0\)，初始乘子 \(\lambda^0, z^0 > 0\)，初始障碍参数 \(\mu^0 > 0\)。迭代：直到满足收敛条件： a. 求解牛顿步线性系统。 b. 计算步长 \(\alpha\)，更新迭代点。 c. 更新障碍参数 \(\mu\)。输出：近似最优解 \(x^ \) 和对应的乘子 \(\lambda^ , z^* \)。该方法的关键在于始终维持严格可行性（\(g(x) < 0, z > 0\)），从而避免边界上的奇异性，并利用牛顿法快速逼近中心路径。对于大规模问题，线性系统的求解可借助稀疏矩阵技术或迭代法加速。