罚函数法求解约束问题最优解

问题描述：

约束问题的最优解可以描述为：

s.t. minf(x)gi(x)≥0,i=1,⋯,mhj(x)=0,j=1,⋯,l

考虑约束问题： ，其中，f(x),gi(x),hj(x) 连续。

或者

s.t. minf(x)g(x)≥0,h(x)=0, ，
其中， g(x)=(g1(x),⋯,gm(x))Th(x)=(h1(x),⋯,hl(x))T

令问题的可行域是：

D={x|gi(x)hj(x)≥0,i=1,⋯,m.≥0,j=1,⋯,l.} ，

如何求解约束问题？？？

罚函数法是序列无约束问题算法的典型代表。罚函数法的基本思想是构造辅助函数F,把原来的约束问题转化为求极小化辅助函数的无约束问题。
如何构造辅助函数，是求解问题首要问题。

一、外点罚函数法

基本思想：构造辅助函数Fμ:Rn→R   (μ>0) 。构造函数在可行域内部与原问题的取值相同，在可行域外部，其取值远远大于目标函数的取值。
1、对于约束问题：

s.t.minf(x)hj(x)=0,j=1,⋯,l ，

可定义辅助函数：

F(x,μ)=f(x)+μ∑j=1lh2j(x)

2、对于约束问题：

s.t. minf(x)gi(x)≥0,i=1,⋯,m ，

可定义辅助函数：

F(x,μ)=f(x)+μ∑i=1m(max{0,gj(x)})2

3、对于一般问题：
可定义辅助函数：

F(x,μ)=f(x)+μP(x)

其中， P(x)=∑mi=1ϕ(gi(x))+∑lj=1ψ(hj(x))， ϕ{=>0,y≥00,y<0， ψ{=>0,y≥00,y≠0，

典型的取法有： ϕ=(max{0,−gi(x)})α， ψ=|hj(x)|β   (α≥1,β≥1)

通过这些辅助函数，可以把约束问题转换为无约束问题：

minF(x,μ)=f(x)+μQ(x)

其中 μ 是很大的数，通常取一个趋向于无穷大的严格递增正数列 {μk}，Q(x) 是连续函数。

具体步骤：

1、给定初始点、初始罚因子，放大系数，允许误差 x(0),μ1,c>1,ϵ>0，设 k=1

2、以 x(k−1)为初点，求解无约束问题： minF(x,μ)=f(x)+μkQ(x)，得极小点 x(k)

3、若 μkQ(x(k))<ϵ，停止，得极小点 x(k)；否则，令 μk+1=cμk，置 K:=k+1，转步骤（2）

二、内点罚函数法

基本思想：内点法产生的点列从可行域的内部逼近问题的解。构造辅助(光滑)函数，该函数在严格可行域外无穷大，且当自变量趋于可行域边界时，函数值趋于无穷大。

适合类型：

s.t. minf(x)gi(x)≥0,i=1,⋯,m ，
定义域： S={x|gi(x)≥0,i=1,2,⋯,m}
当 μ→0时，无约束问题 minFμ=F(x,μ) 的解趋于原有约束问题的解。

定义障碍函数：

F(x,μ)=f(x)+μB(x)
其中，当自变量趋于可行域边界时，连续函数 B(x)→0,μ是很小的正数。

可通过求解：

minF(x,μ)s.t.x∈int S 得到原问题的近似解。

辅助函数：

B(x)=∑i=1m1gi(x)
B(x)=−∑log gi(x)

具体步骤：
1、给定初始点、初始罚因子，缩小系数，允许误差 x(0),μ1,β∈(0,1),ϵ>0，设 k=1

2、以 x(k−1)为初点，求解无约束问题： minF(x,μ)=f(x)+μkB(x)，得极小点 x(k)

3、若 μkB(x(k))<ϵ，停止，得极小点 x(k)；否则，令 μk+1=βμk，置 K:=k+1，转步骤（2）

总结

以上是生活随笔为你收集整理的罚函数法求解约束问题最优解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。