非线性规划中的序列仿射内点法基础题

字数 4775 2025-12-11 17:30:21

非线性规划中的序列仿射内点法基础题

我们先来看一个可以用序列仿射内点法求解的典型问题。

问题描述

考虑以下带不等式约束的非线性规划问题：
最小化目标函数: $f(x) = (x_1 - 3)^2 + (x_2 - 2)^2$
约束条件为：

\[g_1(x) = x_1^2 + x_2^2 - 1 \leq 0 \]

\[ g_2(x) = -x_1 - x_2 + 0.5 \leq 0 \]

其中， $x = (x_1, x_2) \in \mathbb{R}^2$。

目标是在满足不等式约束的前提下，找到点 $x^*$ 使 $f(x)$ 最小。

解题过程

步骤1：理解核心思路

序列仿射内点法是一种障碍函数法。它的核心思想是将不等式约束通过一个“障碍项”整合到目标函数中，从而将一个约束优化问题转化为一系列无约束优化问题来求解。

这个方法如何运作？

构建障碍函数：对于一个约束 $g_i(x) \leq 0$，我们引入一个形式为 $-\mu \ln(-g_i(x))$ 的项，其中 $\mu > 0$ 称为障碍参数。这个项的特点是什么？当 $x$ 在可行域内部（即 $g_i(x) < 0$），特别是当 $x$ 接近约束边界（即 $g_i(x) \to 0^-$）时， $-\ln(-g_i(x)) \to +\infty$。这个巨大的正值像一个“屏障”或“障碍”，阻止迭代点违反约束。
求解一系列子问题：我们不直接求解原问题，而是构造一个依赖于 $\mu$ 的辅助函数——障碍问题 $P(\mu)$： $\min_x f(x) - \mu \sum_{i=1}^{m} \ln(-g_i(x))$，其中 $m$ 是不等式约束的个数。这里，我们固定一个 $\mu_k$，求解 $P(\mu_k)$ 得到一个解 $x(\mu_k)$。
序列更新：逐渐减小障碍参数 $\mu$，使其趋向于0（即 $\mu_{k+1} = \tau \mu_k, \ 0 < \tau < 1$），并求解一系列新的障碍问题。当 $\mu \to 0$ 时，障碍项的影响越来越小，障碍问题的解 $x(\mu)$ 就越来越逼近原约束问题的解 $x^*$。

为什么叫“仿射内点法”？ 在求解每个障碍子问题（一个无约束问题）时，常用牛顿法。而牛顿法的搜索方向推导，在特定条件下（如对障碍函数做变换和近似）会得到一个与“仿射尺度”变换相关的线性系统，故得名。其关键在于，迭代点始终严格保持在可行域内部（$g_i(x) < 0$）。

步骤2：为给定问题构造障碍函数

我们的问题有两个不等式约束（$m=2$），障碍参数为 $\mu > 0$。
构造障碍问题 $P(\mu)$：

\[\min_{x \in \mathbb{R}^2} \phi_{\mu}(x) = f(x) - \mu \sum_{i=1}^{2} \ln(-g_i(x)) \]

即：

\[\phi_{\mu}(x) = (x_1 - 3)^2 + (x_2 - 2)^2 - \mu [\ln(1 - x_1^2 - x_2^2) + \ln(x_1 + x_2 - 0.5)] \]

注意：$\ln$ 内的自变量必须是正的，这要求：

\[1 - x_1^2 - x_2^2 > 0 \quad (在单位圆内) \]

\[ x_1 + x_2 - 0.5 > 0 \quad (在直线 $ x_1 + x_2 = 0.5 $ 上方) \]

因此，迭代的初始点必须选在同时满足这两个条件的严格可行内点。

步骤3：求解单个障碍子问题（以固定 $\mu_k$ 为例）

假设当前障碍参数为 $\mu = \mu_k$。我们需要最小化 $\phi_{\mu_k}(x)$。这通常用牛顿法求解，因为我们可以解析地计算梯度和海森矩阵。

计算梯度 $\nabla \phi_{\mu}(x)$：

\[\frac{\partial \phi_{\mu}}{\partial x_1} = 2(x_1 - 3) - \mu \left[ \frac{-2x_1}{1 - x_1^2 - x_2^2} + \frac{1}{x_1 + x_2 - 0.5} \right] \]

\[ \frac{\partial \phi_{\mu}}{\partial x_2} = 2(x_2 - 2) - \mu \left[ \frac{-2x_2}{1 - x_1^2 - x_2^2} + \frac{1}{x_1 + x_2 - 0.5} \right] \]

计算海森矩阵 $\nabla^2 \phi_{\mu}(x)$（为牛顿法准备）：
这是一个2x2矩阵，元素是二阶偏导数。计算较为繁琐但直接，例如：

\[\frac{\partial^2 \phi_{\mu}}{\partial x_1^2} = 2 - \mu \left[ \frac{-2(1 - x_1^2 - x_2^2) + (2x_1)(-2x_1)}{(1 - x_1^2 - x_2^2)^2} - \frac{1}{(x_1 + x_2 - 0.5)^2} \right] \]

（其他元素同理，此处为展示原理，不展开全部）

牛顿步：在迭代点 $x^{(j)}$，牛顿方向 $d_N$ 通过求解线性方程组得到：

\[\nabla^2 \phi_{\mu}(x^{(j)}) \ d_N = -\nabla \phi_{\mu}(x^{(j)}) \]

线搜索：由于 $\phi_{\mu}(x)$ 可能非凸，纯粹的牛顿步可能导致函数值增加。我们需要沿牛顿方向进行阻尼牛顿法（或回溯线搜索），确保每次迭代后 $\phi_{\mu}(x)$ 下降，并且新点 $x^{(j+1)} = x^{(j)} + \alpha d_N$ 仍在严格可行域内（即所有 $g_i(x) < 0$）。

重复牛顿迭代，直到 $\|\nabla \phi_{\mu}(x^{(j)})\|$ 小于某个容忍度，我们就得到了当前 $\mu_k$ 下障碍问题的一个近似解 $x^*(\mu_k)$。

步骤4：序列更新与整体算法流程

初始化：选择一个严格的初始内点 $x^{(0)}$（例如 $x = (0.2, 0.2)$，在单位圆内且在直线 $x_1+x_2=0.5$ 上方），初始障碍参数 $\mu_0 > 0$（例如 $\mu_0 = 1$），缩小因子 $\tau \in (0, 1)$（例如 $\tau = 0.5$），以及精度容忍度 $\epsilon > 0$。
主循环：对于 $k = 0, 1, 2, ...$ 直到满足收敛条件：
- 内循环：以 $x^{(k)}$ 为起点，用阻尼牛顿法求解障碍子问题 $P(\mu_k)$，得到解 $x^{(k+1)}$。
- 更新障碍参数：$\mu_{k+1} = \tau \mu_k$。
- 检查收敛：常用判据是对偶间隙的估计。对于对数障碍函数，在解 $x^{(k+1)}$ 处，有近似关系 $-\mu_k \approx \lambda_i g_i(x^{(k+1)})$，其中 $\lambda_i$ 是第 $i$ 个约束对应的拉格朗日乘子估计。我们可以用 $m \mu_k$（即约束个数乘以当前 $\mu_k$）来估计对偶间隙。当 $m \mu_k < \epsilon$ 时，算法停止。
输出：最终的 $x^{(k+1)}$ 作为原约束优化问题的最优解 $x^*$ 的近似。

步骤5：对本题的直观解释与预期结果

我们来直观理解这个问题的解：

目标函数 $f(x)$ 是一个以 $(3,2)$ 为圆心的圆的半径平方。无约束最小值点在 $(3,2)$。
约束 $g_1(x) \leq 0$ 是单位圆盘内（包括边界）， $g_2(x) \leq 0$ 是直线 $x_1+x_2=0.5$ 下方的半平面。
无约束最优点 $(3,2)$ 不满足 $g_1(x) \leq 0$（它在单位圆外）。所以最优解必定在约束边界上。
从几何上看，可行域是单位圆与半平面 $x_1+x_2 \leq 0.5$ 的交集。目标是在这个交集上找到距离点 $(3,2)$ 最近的点。可以想象，这个点很可能在单位圆的边界上，并且比较靠近点 $(3,2)$ 到单位圆的投影点附近。

序列仿射内点法的求解路径会如何？

当 $\mu$ 较大时（如 $\mu_0=1$），障碍项影响很大，障碍问题的解 $x(\mu)$ 会远离约束边界，停留在可行域内部深处，更侧重于最小化 $f(x)$ 和障碍项之间的平衡。
随着 $\mu$ 逐渐减小，障碍项的“排斥力”变弱，解 $x(\mu)$ 会逐渐被“推”向约束边界，同时越来越接近 $f(x)$ 的真实极小点。
最终，当 $\mu \to 0$ 时， $x(\mu)$ 会趋近于原问题的最优解，并且满足一阶必要最优性条件（KKT条件），即存在拉格朗日乘子 $\lambda_1^*, \lambda_2^* \geq 0$ 使得：

\[\nabla f(x^*) + \lambda_1^* \nabla g_1(x^*) + \lambda_2^* \nabla g_2(x^*) = 0 \]

\[ \lambda_1^* g_1(x^*) = 0, \quad \lambda_2^* g_2(x^*) = 0 \]

通过求解KKT条件（或使用优化软件验证），我们可以找到这个问题的理论最优解大约在 $x^* \approx (0.7071, 0.7071)$（单位圆边界上，且 $g_1(x^*)=0$），对应的 $\lambda_1^* > 0, \lambda_2^* = 0$。序列仿射内点法产生的迭代点列将从可行域内部逐渐逼近这个边界点。

总结

序列仿射内点法通过将对数障碍函数与序列无约束最小化技术（SUMT）结合，将约束问题转化为一系列更容易处理的无约束子问题。每个子问题用牛顿法求解，并随着障碍参数 $\mu$ 趋近于零，子问题的解序列收敛到原约束问题的解。这种方法的关键优势是迭代点始终保持可行性，且对中等规模的非线性凸规划问题非常有效。对于这个具体例子，算法会从内点出发，沿着一条“中心路径”最终到达边界上的最优点。

非线性规划中的序列仿射内点法基础题我们先来看一个可以用序列仿射内点法求解的典型问题。问题描述考虑以下带不等式约束的非线性规划问题：最小化目标函数: $ f(x) = (x_ 1 - 3)^2 + (x_ 2 - 2)^2 $ 约束条件为： \[ g_ 1(x) = x_ 1^2 + x_ 2^2 - 1 \leq 0 \] \[ g_ 2(x) = -x_ 1 - x_ 2 + 0.5 \leq 0 \] 其中， $ x = (x_ 1, x_ 2) \in \mathbb{R}^2 $。目标是在满足不等式约束的前提下，找到点 $ x^* $ 使 $ f(x) $ 最小。解题过程步骤1：理解核心思路序列仿射内点法是一种障碍函数法。它的核心思想是将不等式约束通过一个“障碍项”整合到目标函数中，从而将一个约束优化问题转化为一系列无约束优化问题来求解。这个方法如何运作？构建障碍函数：对于一个约束 $ g_ i(x) \leq 0 $，我们引入一个形式为 $ -\mu \ln(-g_ i(x)) $ 的项，其中 $ \mu > 0 $ 称为障碍参数。这个项的特点是什么？当 $ x $ 在可行域内部（即 $ g_ i(x) < 0 $），特别是当 $ x $ 接近约束边界（即 $ g_ i(x) \to 0^- $）时， $ -\ln(-g_ i(x)) \to +\infty $。这个巨大的正值像一个“屏障”或“障碍”，阻止迭代点违反约束。求解一系列子问题：我们不直接求解原问题，而是构造一个依赖于 $ \mu $ 的辅助函数——障碍问题 $ P(\mu) $： $ \min_ x f(x) - \mu \sum_ {i=1}^{m} \ln(-g_ i(x)) $，其中 $ m $ 是不等式约束的个数。这里，我们固定一个 $ \mu_ k $，求解 $ P(\mu_ k) $ 得到一个解 $ x(\mu_ k) $。序列更新：逐渐减小障碍参数 $ \mu $，使其趋向于0（即 $ \mu_ {k+1} = \tau \mu_ k, \ 0 < \tau < 1 $），并求解一系列新的障碍问题。当 $ \mu \to 0 $ 时，障碍项的影响越来越小，障碍问题的解 $ x(\mu) $ 就越来越逼近原约束问题的解 $ x^* $。为什么叫“仿射内点法”？在求解每个障碍子问题（一个无约束问题）时，常用牛顿法。而牛顿法的搜索方向推导，在特定条件下（如对障碍函数做变换和近似）会得到一个与“仿射尺度”变换相关的线性系统，故得名。其关键在于，迭代点始终严格保持在可行域内部（$ g_ i(x) < 0 $）。步骤2：为给定问题构造障碍函数我们的问题有两个不等式约束（$ m=2 $），障碍参数为 $ \mu > 0 $。构造障碍问题 $ P(\mu) $： \[ \min_ {x \in \mathbb{R}^2} \phi_ {\mu}(x) = f(x) - \mu \sum_ {i=1}^{2} \ln(-g_ i(x)) \] 即： \[ \phi_ {\mu}(x) = (x_ 1 - 3)^2 + (x_ 2 - 2)^2 - \mu [ \ln(1 - x_ 1^2 - x_ 2^2) + \ln(x_ 1 + x_ 2 - 0.5) ] \] 注意：$ \ln $ 内的自变量必须是正的，这要求： \[ 1 - x_ 1^2 - x_ 2^2 > 0 \quad (在单位圆内) \] \[ x_ 1 + x_ 2 - 0.5 > 0 \quad (在直线 $ x_ 1 + x_ 2 = 0.5 $ 上方) \] 因此，迭代的初始点必须选在同时满足这两个条件的严格可行内点。步骤3：求解单个障碍子问题（以固定 $ \mu_ k $ 为例）假设当前障碍参数为 $ \mu = \mu_ k $。我们需要最小化 $ \phi_ {\mu_ k}(x) $。这通常用牛顿法求解，因为我们可以解析地计算梯度和海森矩阵。计算梯度 $ \nabla \phi_ {\mu}(x) $ ： \[ \frac{\partial \phi_ {\mu}}{\partial x_ 1} = 2(x_ 1 - 3) - \mu \left[ \frac{-2x_ 1}{1 - x_ 1^2 - x_ 2^2} + \frac{1}{x_ 1 + x_ 2 - 0.5} \right ] \] \[ \frac{\partial \phi_ {\mu}}{\partial x_ 2} = 2(x_ 2 - 2) - \mu \left[ \frac{-2x_ 2}{1 - x_ 1^2 - x_ 2^2} + \frac{1}{x_ 1 + x_ 2 - 0.5} \right ] \] 计算海森矩阵 $ \nabla^2 \phi_ {\mu}(x) $ （为牛顿法准备）：这是一个2x2矩阵，元素是二阶偏导数。计算较为繁琐但直接，例如： \[ \frac{\partial^2 \phi_ {\mu}}{\partial x_ 1^2} = 2 - \mu \left[ \frac{-2(1 - x_ 1^2 - x_ 2^2) + (2x_ 1)(-2x_ 1)}{(1 - x_ 1^2 - x_ 2^2)^2} - \frac{1}{(x_ 1 + x_ 2 - 0.5)^2} \right ] \] （其他元素同理，此处为展示原理，不展开全部）牛顿步：在迭代点 $ x^{(j)} $，牛顿方向 $ d_ N $ 通过求解线性方程组得到： \[ \nabla^2 \phi_ {\mu}(x^{(j)}) \ d_ N = -\nabla \phi_ {\mu}(x^{(j)}) \] 线搜索：由于 $ \phi_ {\mu}(x) $ 可能非凸，纯粹的牛顿步可能导致函数值增加。我们需要沿牛顿方向进行阻尼牛顿法（或回溯线搜索），确保每次迭代后 $ \phi_ {\mu}(x) $ 下降，并且新点 $ x^{(j+1)} = x^{(j)} + \alpha d_ N $ 仍在严格可行域内（即所有 $ g_ i(x) < 0 $）。重复牛顿迭代，直到 $ \|\nabla \phi_ {\mu}(x^{(j)})\| $ 小于某个容忍度，我们就得到了当前 $ \mu_ k $ 下障碍问题的一个近似解 $ x^* (\mu_ k) $。步骤4：序列更新与整体算法流程初始化：选择一个严格的初始内点 $ x^{(0)} $（例如 $ x = (0.2, 0.2) $，在单位圆内且在直线 $ x_ 1+x_ 2=0.5 $ 上方），初始障碍参数 $ \mu_ 0 > 0 $（例如 $ \mu_ 0 = 1 $），缩小因子 $ \tau \in (0, 1) $（例如 $ \tau = 0.5 $），以及精度容忍度 $ \epsilon > 0 $。主循环：对于 $ k = 0, 1, 2, ... $ 直到满足收敛条件：内循环：以 $ x^{(k)} $ 为起点，用阻尼牛顿法求解障碍子问题 $ P(\mu_ k) $，得到解 $ x^{(k+1)} $。更新障碍参数：$ \mu_ {k+1} = \tau \mu_ k $。检查收敛：常用判据是对偶间隙的估计。对于对数障碍函数，在解 $ x^{(k+1)} $ 处，有近似关系 $ -\mu_ k \approx \lambda_ i g_ i(x^{(k+1)}) $，其中 $ \lambda_ i $ 是第 $ i $ 个约束对应的拉格朗日乘子估计。我们可以用 $ m \mu_ k $（即约束个数乘以当前 $ \mu_ k $）来估计对偶间隙。当 $ m \mu_ k < \epsilon $ 时，算法停止。输出：最终的 $ x^{(k+1)} $ 作为原约束优化问题的最优解 $ x^* $ 的近似。步骤5：对本题的直观解释与预期结果我们来直观理解这个问题的解：目标函数 $ f(x) $ 是一个以 $ (3,2) $ 为圆心的圆的半径平方。无约束最小值点在 $ (3,2) $。约束 $ g_ 1(x) \leq 0 $ 是单位圆盘内（包括边界）， $ g_ 2(x) \leq 0 $ 是直线 $ x_ 1+x_ 2=0.5 $ 下方的半平面。无约束最优点 $ (3,2) $ 不满足 $ g_ 1(x) \leq 0 $（它在单位圆外）。所以最优解必定在约束边界上。从几何上看，可行域是单位圆与半平面 $ x_ 1+x_ 2 \leq 0.5 $ 的交集。目标是在这个交集上找到距离点 $ (3,2) $ 最近的点。可以想象，这个点很可能在单位圆的边界上，并且比较靠近点 $ (3,2) $ 到单位圆的投影点附近。序列仿射内点法的求解路径会如何？当 $ \mu $ 较大时（如 $ \mu_ 0=1 $），障碍项影响很大，障碍问题的解 $ x(\mu) $ 会远离约束边界，停留在可行域内部深处，更侧重于最小化 $ f(x) $ 和障碍项之间的平衡。随着 $ \mu $ 逐渐减小，障碍项的“排斥力”变弱，解 $ x(\mu) $ 会逐渐被“推”向约束边界，同时越来越接近 $ f(x) $ 的真实极小点。最终，当 $ \mu \to 0 $ 时， $ x(\mu) $ 会趋近于原问题的最优解，并且满足一阶必要最优性条件（KKT条件），即存在拉格朗日乘子 $ \lambda_ 1^ , \lambda_ 2^ \geq 0 $ 使得： \[ \nabla f(x^ ) + \lambda_ 1^ \nabla g_ 1(x^ ) + \lambda_ 2^ \nabla g_ 2(x^ ) = 0 \] \[ \lambda_ 1^ g_ 1(x^ ) = 0, \quad \lambda_ 2^ g_ 2(x^* ) = 0 \] 通过求解KKT条件（或使用优化软件验证），我们可以找到这个问题的理论最优解大约在 $ x^* \approx (0.7071, 0.7071) $（单位圆边界上，且 $ g_ 1(x^ )=0 $），对应的 $ \lambda_ 1^ > 0, \lambda_ 2^* = 0 $。序列仿射内点法产生的迭代点列将从可行域内部逐渐逼近这个边界点。总结序列仿射内点法通过将对数障碍函数与序列无约束最小化技术（SUMT）结合，将约束问题转化为一系列更容易处理的无约束子问题。每个子问题用牛顿法求解，并随着障碍参数 $ \mu $ 趋近于零，子问题的解序列收敛到原约束问题的解。这种方法的关键优势是迭代点始终保持可行性，且对中等规模的非线性凸规划问题非常有效。对于这个具体例子，算法会从内点出发，沿着一条“中心路径”最终到达边界上的最优点。