No results matching ""

简单介绍处理不等式约束问题的内点法的算法流程。

不等式约束的极小化问题

min⁡f0(x)\min f_0(x)minf0​(x)

s.t.fi(x)≤0s.t.\quad f_i(x)\le0s.t.fi​(x)≤0

Ax=bAx=bAx=b

假设该问题可解，即存在最优的x⋆x^\starx⋆，用p⋆p^\starp⋆表示最优值f0(x⋆)f_0(x^\star)f0​(x⋆)。

用内点法求解问题，主要分为两种：

用Newton方法或者求解一系列等式约束问题

求解一系列KKT条件的修改形式

这里只讨论一种特殊的内点法--障碍法。

对数障碍函数和中心路径

一种尝试是将不等式约束问题近似转化为等式约束问题，从而应用Newton方法求解。 因此，可以将原问题写成：

min⁡f0(x)+∑i=1mI(fi(x))\min f_0(x)+\sum_{i=1}^m I(f_i(x))minf0​(x)+i=1∑m​I(fi​(x))

s.t.Ax=bs.t.\quad Ax= bs.t.Ax=b

其中I()I()I()是非正实数的示性函数：

I(u){0u≤0∞u>0

I(u)\left\{\begin{array}{ll}

0 & u \leq 0 \\

\infty & u>0

\end{array}\right.

I(u){0∞​u≤0u>0​

这样，我们就成功转化为等式约束，可以，目标函数一般情况下不可微，因此不能运用Newton方法。

对数障碍

既然示性函数不可微，我们很自然的想法就是找一个近似的可微函数来代替：

I^(u)=−(1/t)log⁡(−u)

\hat{I}(u)=-(1 / t) \log (-u)

I^(u)=−(1/t)log(−u)

我们可以画出对数障碍函数的图像发现，是非减函数，并且当u>0u>0u>0时取值为∞\infty∞，符合我们的要求。

我们将函数ϕ(x)=−∑i=1mlog⁡(−fi(x))\phi (x) = -\sum_{i=1}^m \log (-f_i(x))ϕ(x)=−∑i=1m​log(−fi​(x))称为对数障碍函数。可以将等式约束问题重写为：

min⁡f0(x)+∑i=1m−(1/t)log⁡(−fi(x))

\min f_{0}(x)+\sum_{i=1}^{m}-(1 / t) \log \left(-f_{i}(x)\right)

minf0​(x)+i=1∑m​−(1/t)log(−fi​(x))

s.t.Ax=b

s.t.\quad Ax= b

s.t.Ax=b

既然对数障碍只是原问题的近似，因此需要回答的问题就是其解的效果与最优解差距多大？这个问题将在中心路径中解决。

先给出对数障碍的梯度和Hessian矩阵：

∇ϕ(x)=∑i=1m1−fi(x)∇fi(x)

\nabla \phi(x)=\sum_{i=1}^{m} \frac{1}{-f_{i}(x)} \nabla f_{i}(x)

∇ϕ(x)=i=1∑m​−fi​(x)1​∇fi​(x)

∇2ϕ(x)=∑i=1m1fi(x)2∇fi(x)∇fi(x)T+∑i=1m1−fi(x)∇2fi(x)

\nabla^{2} \phi(x)=\sum_{i=1}^{m} \frac{1}{f_{i}(x)^{2}} \nabla f_{i}(x) \nabla f_{i}(x)^{T}+\sum_{i=1}^{m} \frac{1}{-f_{i}(x)} \nabla^{2} f_{i}(x)

∇2ϕ(x)=i=1∑m​fi​(x)21​∇fi​(x)∇fi​(x)T+i=1∑m​−fi​(x)1​∇2fi​(x)

中心路径

考虑等价问题：

min⁡tf0(x)+ϕ(x)\min tf_0(x)+\phi (x)mintf0​(x)+ϕ(x)

s.t.Ax=bs.t.\quad Ax= bs.t.Ax=b

这里只是多乘了一个ttt，对最优解没有影响。

对任意t>0t>0t>0，我们用x⋆(t)x^\star(t)x⋆(t)表示问题的最优解，ttt为中心点，将这些点的集合定义为问题的中心路径。

所有中心路径上的点满足以下充要条件：

Ax⋆(t)=b,fi(x⋆(t))<0Ax^\star(t)=b,\quad f_i(x^\star(t))<0Ax⋆(t)=b,fi​(x⋆(t))<0

t▽f0(x⋆(t))+▽ϕ(x⋆(t))+ATv^=0t\triangledown f_{0}(x^\star(t))+\triangledown \phi (x^\star(t))+A^T \hat{v} = 0 t▽f0​(x⋆(t))+▽ϕ(x⋆(t))+ATv^=0

中心路径的对偶点

g(λ⋆(t),v⋆(t))=f0(x⋆(t))−m/t≤p⋆g(\lambda^\star(t),v^\star(t)) = f_0(x^\star(t)) - m/t \le p^\starg(λ⋆(t),v⋆(t))=f0​(x⋆(t))−m/t≤p⋆

证明了x⋆(t)x^\star(t)x⋆(t)随着t⇒∞t \Rightarrow \inftyt⇒∞而收敛于最优解。