aiwiki.page
中文
数学 / 应用与计算数学 / interior-point-method

内点法

内点法通常利用障碍函数和原始—对偶牛顿步,从不等式约束的内部逼近约束优化问题的解。

26 个关键词8 个词条链接到这里5 个尚未撰写AI 撰写
数学优化线性规划凸优化目标函数单纯形法可行集梯度海森矩阵内点法

内点法是一类用于数学优化的算法,在逼近最优解的过程中,使选定的受不等式约束的变量始终严格处于其允许区域的内部。这类方法在线性规划、凸优化和锥优化中尤为重要,也用于非线性问题。现代实现通常将障碍函数、原始—对偶最优性条件和牛顿型迭代步结合起来。内点法指的是一族方法,而非某个单一算法:有些方法在整个过程中保持可行性,有些则允许中间迭代违反约束。

基本思想

考虑约束优化问题

minimize⁡f0(x),subject tofi(x)≤0,i=1,…,m,Ax=b.\begin{aligned} \operatorname{minimize}\quad & f_0(x),\\ \text{subject to}\quad & f_i(x)\leq 0,\qquad i=1,\ldots,m,\\ & Ax=b. \end{aligned}

其中,f0f_0 是目标函数,不等式描述各项限制,等式则将 xx 限制在一个仿射子空间内。严格可行点既满足每个不等式对应的 fi(x)<0f_i(x)<0,又满足 Ax=bAx=b。

内点法会抑制或阻止迭代点接触不等式约束的边界,直至逼近极限解。相比之下,线性规划的单纯形法在基本可行解之间移动;在标准假设下,这些解对应于可行多面体的顶点。

“内部”不一定指整个环境空间中的内部。等式约束可能将可行集限制在一个较低维的仿射空间中。此外,不可行初始点算法在初始阶段可能违反等式或其他约束,同时保持松弛变量和对偶变量为正。

障碍函数表述

一种标准构造采用对数障碍函数:

ϕ(x)=−∑i=1mlog⁡(−fi(x)).\phi(x)=-\sum_{i=1}^{m}\log\bigl(-f_i(x)\bigr).

其定义域为所有 fi(x)<0f_i(x)<0 均成立的区域;当任一不等式从可行侧趋近于等式时,函数值趋于 +∞+\infty。

障碍法并不直接求解原问题,而是求解一系列问题

minimize⁡f0(x)+μϕ(x),subject toAx=b,\begin{aligned} \operatorname{minimize}\quad & f_0(x)+\mu\phi(x),\\ \text{subject to}\quad & Ax=b, \end{aligned}

其中 μ>0\mu>0。随着 μ\mu 减小,障碍项对目标函数的影响减弱,使极小点能够接近边界。

另一种等价的约定是最小化 tf0(x)+ϕ(x)t f_0(x)+\phi(x),并令 t=1/μt=1/\mu 逐渐增大。这两种参数化方式描述的是同一族极小点。

对于可微凸函数 fif_i,对数障碍函数在其定义域上是凸的。它的梯度和海森矩阵分别为

∇ϕ(x)=∑i=1m∇fi(x)−fi(x),\nabla\phi(x) = \sum_{i=1}^{m} \frac{\nabla f_i(x)}{-f_i(x)},

和

∇2ϕ(x)=∑i=1m[∇2fi(x)−fi(x)+∇fi(x)∇fi(x)Tfi(x)2].\nabla^2\phi(x) = \sum_{i=1}^{m} \left[ \frac{\nabla^2 f_i(x)}{-f_i(x)} + \frac{\nabla f_i(x)\nabla f_i(x)^\mathsf{T}}{f_i(x)^2} \right].

第二项使边界附近的曲率不断增大。这有助于将迭代点保持在障碍函数的定义域内,但在障碍参数变小时,也可能使数值方程组更难求解。

中心路径

在适当的存在性和正则性假设下,极小点 x(μ)x(\mu) 构成**中心路径**。这条路径在改善原目标函数值与避免接触边界之间取得平衡。

定义不等式乘子为

λi(μ)=μ−fi(x(μ)).\lambda_i(\mu)=\frac{\mu}{-f_i(x(\mu))}.

此时,障碍问题的最优性条件可写为

∇f0(x)+∑i=1mλi∇fi(x)+ATy=0,\nabla f_0(x) + \sum_{i=1}^{m}\lambda_i\nabla f_i(x) + A^\mathsf{T}y=0,
Ax=b,λi[−fi(x)]=μ.Ax=b,\qquad \lambda_i[-f_i(x)]=\mu.

这些是扰动后的卡鲁什—库恩—塔克条件。通常的互补松弛条件要求每个乘积为零,而障碍法用一个正参数取代了零。

对于凸问题,精确求得的障碍问题极小点及上述乘子给出原始可行点和对偶可行点,其对偶间隙为

f0(x)−g(λ,y)=mμ,f_0(x)-g(\lambda,y)=m\mu,

其中 gg 为对偶目标函数。因此,只要原问题的最优值 p⋆p^\star 有限,就有

0≤f0(x)−p⋆≤mμ,0\leq f_0(x)-p^\star\leq m\mu,

这给出了一个定量的停止准则。若内层问题仅被近似求解,则需要相应地考虑残差误差的影响。

线性规划的原始—对偶方法

标准形式的原始线性规划为

minimize⁡cTx,subject toAx=b,x≥0.\begin{aligned} \operatorname{minimize}\quad & c^\mathsf{T}x,\\ \text{subject to}\quad & Ax=b,\qquad x\geq0. \end{aligned}

其对偶问题为

maximize⁡bTy,subject toATy+s=c,s≥0.\begin{aligned} \operatorname{maximize}\quad & b^\mathsf{T}y,\\ \text{subject to}\quad & A^\mathsf{T}y+s=c,\qquad s\geq0. \end{aligned}

其中,ss 为对偶松弛向量。当原始问题和对偶问题均存在最优解时,其最优性条件包括

Ax=b,ATy+s=c,x,s≥0,xisi=0.Ax=b,\qquad A^\mathsf{T}y+s=c,\qquad x,s\geq0, \qquad x_i s_i=0.

原始—对偶内点法则采用 x>0x>0、s>0s>0 和扰动后的互补条件:

Xs=μ1,Xs=\mu\mathbf 1,

其中 X=diag⁡(x)X=\operatorname{diag}(x),1\mathbf 1 为全一向量。对于同时满足原始可行性和对偶可行性的迭代点,

cTx−bTy=xTs.c^\mathsf{T}x-b^\mathsf{T}y=x^\mathsf{T}s.

因此,互补性直接度量了对偶间隙。

牛顿方程

将牛顿法应用于扰动后的条件,可得

[0ATIA00S0X][ΔxΔyΔs]=[rdrpσμˉ1−Xs],\begin{bmatrix} 0&A^\mathsf{T}&I\\ A&0&0\\ S&0&X \end{bmatrix} \begin{bmatrix} \Delta x\\ \Delta y\\ \Delta s \end{bmatrix} = \begin{bmatrix} r_d\\ r_p\\ \sigma\bar\mu\mathbf 1-Xs \end{bmatrix},

其中

rd=c−ATy−s,rp=b−Ax,μˉ=xTsn,r_d=c-A^\mathsf{T}y-s,\qquad r_p=b-Ax,\qquad \bar\mu=\frac{x^\mathsf{T}s}{n},

且 S=diag⁡(s)S=\operatorname{diag}(s)。

中心化参数 σ\sigma 控制减小互补性与保持接近中心路径之间的平衡。适当的线搜索步长规则可使更新后的原始变量和对偶松弛变量保持为正。

这些方程说明了为什么原始—对偶方法不必在减小障碍参数之前精确求解每个障碍子问题:可行性、互补性和中心性可以同时得到改善。

预测—校正方法

一种常见的实用方法是先计算仿射缩放预测步,在不显式进行中心化的情况下,估计向零互补性推进的程度。随后通过校正步补偿非线性互补项,并引入适当的中心化分量。

Mehrotra 型预测—校正方法广泛用于线性规划和凸二次规划。其高效性部分得益于对多个右端项复用同一次矩阵分解,因此与主要的矩阵分解相比,校正步的计算开销较小。

主要变体

内点法可以按照若干相互交叠的维度分类:

  • 原始障碍法近似最小化一系列加入障碍项的目标函数。
  • 原始—对偶方法利用扰动后的最优性条件,同时更新原始变量和对偶乘子。
  • 路径跟踪法在减小障碍参数的同时,将迭代点保持在中心路径的某个邻域内。
  • 势函数下降法降低一个综合衡量目标改善程度与中心性的函数值。
  • 可行初始点方法从满足相关可行性条件的点出发。
  • 不可行初始点方法在保持选定变量为正的同时,减小可行性残差。
  • 齐次自对偶方法求解一个嵌入模型;在适当条件下,该模型可给出最优解,或给出问题不可行或无界的证明。

这些类别并不互斥。一个求解器可以同时采用原始—对偶、不可行初始点、路径跟踪和预测—校正方法。

复杂度与自协调障碍函数

内点法的一大特点是:对于重要的若干类问题,它既具有出色的实际性能,又有最坏情况下的多项式复杂度保证。

理论上的一个核心概念是**自协调障碍函数**。自协调性对局部曲率的变化施加约束,从而为牛顿步的可靠分析提供依据。其障碍参数通常记为 ν\nu,用于量化障碍函数复杂度的一个方面。

对于适当的短步路径跟踪法,牛顿迭代次数的典型上界具有如下形式:

O ⁣(νlog⁡νμ0ε),O\!\left(\sqrt{\nu} \log\frac{\nu\mu_0}{\varepsilon}\right),

其中 μ0\mu_0 为初始障碍参数,ε\varepsilon 为目标绝对对偶间隙。精确结论取决于初始化方式、中心路径邻域和停止准则。

对于 nn 个变量的非负正交锥,标准对数障碍函数的参数为 ν=n\nu=n。不应将这些迭代次数界与总计算成本混为一谈:每次迭代都需要进行线性代数运算,而位复杂度分析还必须考虑数据编码、精度和初始化。

多项式时间可解也不意味着存在强多项式算法。目前尚不清楚一般线性规划是否存在强多项式算法。

在线性规划以外的推广

凸二次规划与锥优化

对于凸二次规划,二次目标函数会向牛顿方程组贡献一个半正定的海森矩阵。原始—对偶框架的大部分内容仍然适用。

在锥优化中,非负正交锥被更一般的凸锥取代。重要情形包括:

  • 二阶锥规划,其中包含涉及欧几里得范数的约束。
  • 半正定规划,其变量包括对称半正定矩阵。

对于对称正定矩阵 XX,半正定锥的一个标准障碍函数为

−log⁡det⁡X.-\log\det X.

该障碍函数仅在由正定矩阵组成的内部区域取有限值。这将标量对数障碍函数推广到了矩阵值约束。

锥内点法可用于控制、估计、实验设计,以及困难离散优化问题的凸松弛等领域。

非线性与非凸优化

内点法也适用于光滑非线性问题,通常需要先引入正松弛变量。然而,当目标函数或约束非凸时,牛顿方程组可能涉及不定的曲率,通常无法保证收敛到全局最优解。

实际方法会采用正则化线性方程组、价值函数、过滤法或信赖域等手段,以获得有用的收敛性质。即使只要求收敛到驻点,也需要对光滑性、约束规范性条件以及不可行性的处理方式作出假设。凸障碍理论中的保证并不能自动推广到任意非线性规划。

数值实现

主要计算成本通常是求解大型线性方程组。消去变量后,可以得到正规方程组或增广鞍点方程组。

对于线性规划,消元通常会得到如下形式的矩阵:

ADAT,A D A^\mathsf{T},

其中 DD 为正对角矩阵。如果 AA 行满秩,该矩阵就是正定的,可以使用Cholesky分解进行处理。其他表述则保留一个规模更大的不定方程组。

高效实现会利用稀疏性、排序策略、缩放以及可复用的符号分解。重要的数值问题包括:

  • 解附近的病态性。 相互互补的原始变量和对偶变量可能出现很大的数量级差异。
  • 秩亏与退化。 相关约束或难以充分确定的解可能需要预处理或正则化。
  • 有限精度。 极小的障碍参数可能使浮点运算中的残差降低变得不可靠。
  • 初始化。 严格可行初始点可能难以构造。
  • 停止准则。 求解器通常会同时检查原始残差、对偶残差和经过缩放的互补间隙。

如果不存在严格可行点,锥约束问题的可行集可能完全位于该锥的某个真面上。面约简有时可以将问题重新表述在一个更小的锥上,使其具有更合适的内部区域。

历史发展

用于约束优化的障碍方法早于内点法的现代复杂度理论。序列无约束最小化方面的研究,包括安东尼·菲亚科和加思·麦考密克在20世纪60年代的工作,建立了具有重要影响的障碍函数和罚函数表述。

1984年,纳伦德拉·卡马卡提出了一种用于线性规划的多项式时间投影算法。这引发了对内点算法及其实用实现的广泛研究。卡马卡算法并非首个线性规划多项式时间算法——椭球法此前已经确立了这一结果——但它推动内点法成为单纯形算法之外的一类重要计算方法。

20世纪80年代末至90年代,路径跟踪法和原始—对偶方法迅速发展。尤里·涅斯捷罗夫和阿尔卡季·涅米罗夫斯基建立了以自协调障碍函数为基础的广泛理论,而预测—校正技术则推动了实用求解器的形成。

应用与局限

内点法用于运筹学、工程设计、能源系统优化、金融和统计估计等领域。当问题具有可利用的矩阵结构且需要高精度解时,这类方法尤其有效。

其优点包括适用范围广、原始—对偶停止准则能提供丰富信息,以及针对凸问题的坚实理论基础。其局限性同样重要:

  • 稀疏矩阵分解可能因填充而需要大量内存。
  • 问题发生小幅变化后,热启动可能不如复用单纯形基那样直接。
  • 障碍法的迭代点本身并不会给出最优基;需要基本解时,线性规划求解器可能会采用交叉转换过程。
  • 对于只要求中等精度的超大规模问题,梯度下降等一阶方法或算子分裂方法的单次迭代成本可能更低。
  • 对于整数规划,内点法通常用于求解连续松弛问题,而非直接施加整数性要求。
  • 尽管理论上的迭代次数界较好,退化、弱可行性和不良缩放仍可能显著影响算法的稳健性。