障碍函数

制约函数

障碍函数(barrier function)亦称内惩罚函数、围墙函数或碰壁函数，是一类制约函数。

介绍

障碍函数(barrier function)亦称内惩罚函数、围墙函数或碰壁函数，是一类制约函数。

在数学领域约束优化中，障碍函数是一个连续函数，其中点的值随着点到达优化问题的可行区域的边界而增加到无穷大。这些函数用于通过更容易处理的目标函数中的惩罚项来代替不等式约束。

两种最常见的屏障功能类型是反向屏障功能和对数屏障功能。恢复对数屏障功能的兴趣是由于它们与原始双重内点方法的联系。

障碍函数法

（内点法）

原理

设有纯不等式约束问题minf(X)：s.t.gi(X)≤0,i=1,2,…,m，设原问题内部非空，初始点X0选为内点。障碍函数法（内点法）构造的增广目标函数形为F(X,γ)=f(X)+γB(X)，其中，γ>0,B(X)>0（当X为内点），且当X在边界时，B(X)的值为无穷大。这样，可阻止F(X,γ)的极小点穿越边界，而必定被限制为可行点。

下面再讨论障碍因子γ的结构。先看一个简单的例子，设原问题为：

minf(X)

s.t.–x+1≤0

其增广目标函数为

F(x,γ)=f(x)+γB(x)=x+γ(x–1)

原问题的精确极小正好是x=1。

在一般条件下，可以证明，F(X,γ)的无约束极小点Xγ恒为可行域的内点，且当γ→0时，Xγ趋于原问题的约束极小点。

障碍函数法（内点法）

算法过程

（1）取X0为内点，γ0>0（通常，取γ0=0），障碍因子缩小系数d,00；

（2）构造增广目标函数F(X,γk)=f(X)+γkB(X)

（3）以Xk为初始点，求解无约束优化问题minF(X,γk)

设其无约束极小点为Xk+1；

（4）如果0<γkB(Xk+1)≤ε，输出Xk+1，计算停止；

否则，γk+1=dγk，k=k+1转（2）。

注：从理论上讲，Xk一定是可行域的内点，但是在实际计算过程中，由于步长是取离散数值，以及舍入误差等原因，使Xk有可能取为非可行点，在这种情况下，应选用优于Xk+1的内点来取代Xk。

罚函数法

（外点法）

罚函数是指在求解最优化问题(无线性约束优化及非线性约束优化)时，在原有目标函数中加上一个障碍函数，而得到一个增广目标函数，罚函数的功能是对非可行点或企图穿越边界而逃离可行域的点赋予一个极大的值，即将有约束最优化问题转化为求解无约束最优化问题。

基本思想

把非线性约束优化问题转化为无线性优化约束问题。依据如何将目标函数和约束函数进行组合，人们导出了许多不同形式的罚函数。由于这些早期方法均需要求解一系列无约束的罚函数极小化问题，故通常称之为序列无约束极小化方法(Sequential Unconstrained Minimization Technique)，简称SUMT。

基本思路：通过引进一个乘法因子把约束条件连接到目标函数上，从而将有约束的最优化问题转化为无约束条件的问题。合理的罚函数可以在当搜索到不可行点时，是目标函数值变得很大，离约束条件越远惩罚越大。

分类

（1）外罚函数法

根据约束的特点，构造某种惩罚函数，然后加到目标函数中去，将约束问题求解转化为一系列的无约束问题。这种“惩罚策略”，对于无约束问题求解过程中的那些企图违反约束条件的目标点给予惩罚。

通过上述方法，我们可以把有约束的问题化为无约束问题求解。也就是所谓的外罚函数法。

但是外罚函数的原理主要是应用了近似最优并且近似可行的，近似最优可以接受，但是近似可行在实际运用中让人无法接受。这一点可以由内罚函数解决。

（2）内罚函数法

相比于外罚函数法在不可行区域加惩罚，内罚函数法在可行域边界筑起高墙，让目标函数无法穿过，就把目标函数挡在可行域内了。

但是这种惩罚策略只适用于不等式约束问题，并要求可行域的内点集非空，否则，每个可行点都是边界点，都加上无穷大惩罚，惩罚也就失去意义了。

优缺点对比

1）由于无约束最优化问题的解法目前已有许多很有效的算法，如DFP，BFGS等，所以在求解复杂得多的约束优化问题是，工程技术人员一般会采用罚函数法——SUMT外点法和内点法。

2）内点法适用于解含不等式约束问题，并且每次迭代的点都是可行点，这是设计人员所希望的。但要求初始点为可行域的内点，需要相当的工作量，同时它不能处理等式约束；外点法适于解既含等式约束又含不等式约束的优化问题，初始点可以是可行域之外的点，却不能保证近似最优解是可行的。

3）罚函数法对于增广的目标函数的Hessian矩阵的条件数随罚因子增大或减小而增大，造成在求解无约束最优化问题时的困难，如何选择罚因子往往进退维谷。如外罚函数法，欲使得无约束问题接近于原约束问题，应该选择尽可能大的罚因子；但为了减轻求解无约束问题的困难，又应选取较小的罚因子，否则增广矩阵病态。这也是罚函数法的固有弱点。

对数屏障功能

对于对数屏障功能，当x

这引入了一个梯度给优化的函数，它有利于x（在这种情况下值低于b））的极限值，同时对远离这些极端的函数的影响相对较小。

取决于所优化的功能，对数屏障功能可能比较少计算昂贵的反屏障功能有利。

更高的维度

扩展到更高的维度是很简单的，只要每个维度是独立的。对于应限制为严格低于bi的每个变量xi，添加

正式定义

在上最小化CTx

假设下式可行：

定义对数屏障

与障碍函数法

罚函数法与障碍函数法是求解约束极小化问题的较好的算法，其基本原理是在原目标函数中加上一个罚（障碍）函数，而得到一个增广目标函数。罚（障碍）函数的功能是对非可行或企图穿越边界而逃离可行域的点赋予一个极大的函数值。可以作一个形象的比喻：在约束极小化问题中，约束条件是一条“法律”，凡是不服从这条“法律”的点被处以“罚款”的“经济制裁”，而且“罚款”的数额极高。这样，在对新的目标函数进行无约束极小化的过程中，就会迫使迭代点逐步逼近（当迭代点在可行域外时）或者不能离开可行域（当迭代点在可行域内时），这样所得的关于增广目标函数的无约束极小化的解就会逼近于原目标函数的约束极小化的解。也就是说，可以将约束极小化问题通过增广目标函数而化成无约束极小化问题，而后者可以用前几节所介绍的算法来求解。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省