优化理论10----约束优化的惩罚外点和内点法

文章目录

• 优化理论10----约束优化的惩罚外点和内点法
• • 1约束最优化问题
  • • 1.1 约束最优化问题的基本结构
  • 惩罚函数法的类型
  • 2 外点法(Penalty method）
  • • 2.1 不等式约束惩罚法
    • • 外点法步骤：
    • 收敛性分析
    • • 例子
    • 2.2不等式和等式约束的惩罚方法
    • • 例子：
    • 实例代码
    • 外点法中的KKT乘数
  • 3 内点法（**Barrier Methods**）
  • • 计算步骤
    • 具体案例
    • 收签性分析
    • 内点罚函数法几点说明
  • 3、混合惩罚函数法
  • 参考资料
  • 3、混合惩罚函数法
  • 参考资料

1约束最优化问题

1.1 约束最优化问题的基本结构

在无约束最优化问题中，我们默认了可行域为 R n R^n Rn ，然而在约束最优化问题中，我们需要为可行域做出一些限制，因此衍生出了一些与无约束最优化问题不同的、独有的性质。

一般约束最优化问题 P P P 的表达为：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ P : minimize …

其中 g ( x ) g(x) g(x) 被称为不等式约束，而 h ( x ) h(x) h(x) 被称为等式约束。这些约束限定了 f ( x ) f(x) f(x) 的可行域为 S = { x ∈ R n ∣ g i ( x ) ≤ 0 , i = 1 , ⋯   , m ; h j ( x ) = 0 , i = 1 , ⋯   , k } S=\{x \in R^n |g_i(x)\leq 0,i=1, \cdots, m;h_j(x)=0,i=1, \cdots, k\} S={x∈Rn∣gi​(x)≤0,i=1,⋯,m;hj​(x)=0,i=1,⋯,k}

解决约束最优化问题的方法主要有惩罚函数法和拉格朗日乘子法。其中惩罚函数法较为简单，基本思想是将约束最优化问题转化为无约束最优化问题再用为无约束最优化问题的方法求解。

惩罚函数法的类型

在惩罚法(Penalty method）中，扩展了 P P P 的可行域从 S S S 到 R n R^n Rn ,但是，对于原可行域 F F F 之外的点，目标函数会增加很大的代价或“惩罚”。（外点法）

在障碍法（Barrier Methods）,给定初始点 x 0 x_0 x0​ ,位于可行域 S S S 的内部,我们将非常大的代价加在离 F F F 边界越来越近的可行点上，从而为点要离开可行区域创造了一个“障碍”。 （内点法）

2 外点法(Penalty method）

2.1 不等式约束惩罚法

对可行域外的点（即违反约束的点）施加惩罚，内部的点不惩罚，从而使可行域外的初始点通过迭代向可行域 S S S逼近。

只考虑不等式约束的优化问题：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ P : minimize …

定 义 \large\color{magenta}{\boxed{\color{brown}{定义 } }} 定义​ 函数 p ( x ) : R n → R p(x) : R^n → R p(x):Rn→R 称为 P P P 的惩罚函数,满足如下规则：
{ p ( x ) = 0    ,     x ∈ F p ( x ) = + ∞    ,     x ∉ F \begin{cases} p(x)=0 \ \ ,\ \ \ x ∈F\\ p(x)=+∞\ \ ,\ \ \ x∉F \end{cases}\\ {p(x)=0  ,   x∈Fp(x)=+∞  ,   x∈/​F​

例如： p ( x ) = ∑ i = 1 m [ m a x { 0 , g i ( x ) } ] 2 p(x) =\sum_{i=1}^{m}{[max\{0,g_i(x)\}]^2} p(x)=∑i=1m​[max{0,gi​(x)}]2

然后我们考虑解决以下惩罚函数方案:
P ( σ ) : m i n i m i z e    f ( x ) + σ p ( x ) P(\sigma): minimize \ \ f(x) + \sigma p(x)\\ P(σ):minimize  f(x)+σp(x)
也就是最小化 F ( x , σ ) = f ( x ) + σ p ( x ) = f ( x ) + σ ∑ i = 1 m [ m a x { 0 , g i ( x ) } ] 2 F(x,\sigma)=f(x) + \sigma p(x)=f(x)+\sigma\sum_{i=1}^{m}{[max\{0,g_i(x)\}]^2} F(x,σ)=f(x)+σp(x)=f(x)+σ∑i=1m​[max{0,gi​(x)}]2 。

其中常数 σ \sigma σ 的递增序列 σ k → + ∞ \sigma_k →+∞ σk​→+∞ 。注意，在 P ( σ ) P(\sigma) P(σ) 中，我们给违反的约束分配了一个惩罚。标量 σ \sigma σ 称为惩罚参数。

函数 F ( x , σ ) F(x,\sigma) F(x,σ)在可行域 S S S的内部的取值与问题(2)的目标函数 f f f的取值相等,而在可行域的外部取值远远大于目标函数 f f f的值.换言之,对可行域外部点的目标函数值加以惩罚,使得无约束问题 m i n    F ( x , σ ) min~~F(x,\sigma) min  F(x,σ)的解是约束问题(2)的近似解.且当 σ → + ∞ \sigma →+∞ σ→+∞时,问题 m i n    F ( x , σ ) min~~F(x,\sigma) min  F(x,σ)的解 x ( σ ) x(\sigma) x(σ)趋于约束问题的解.即随着 σ \sigma σ 不断变大，可行域外的函数值越往可行域边界折叠，像是形成了一堵墙壁，阻止向外迭代。若最优点不在可行域内，最优点也越靠近边界。

外点法步骤：

• Step 0 :选定初始点 x 0 ∈ R n x^{0} \in R^{n} x0∈Rn, 初始罚因子 σ 0 > 0 \sigma_{0}>0 σ0​>0, 放大系数 β > 1 \beta>1 β>1, 误差精度 ϵ > 0 \epsilon>0 ϵ>0, k = 0 k=0 k=0

• Step 1 ：在 x k x^{k} xk 初始点求解无约束惩罚规划:

  P ( σ k ) : m i n i m i z e    f ( x ) + σ k p ( x )  s.t.  x ∈ R n \begin{aligned} &P(\sigma_k): minimize \ \ f(x) + \sigma_k p(x)\\ & \text { s.t. } \quad x \in R^{n} \end{aligned} ​P(σk​):minimize  f(x)+σk​p(x) s.t. x∈Rn​

  得到极小值点 x k + 1 x^{k+1} xk+1.

• Step 2： 如果 σ k p ( x k + 1 ) < ϵ , \sigma_{k} p\left(x^{k+1}\right)<\epsilon, σk​p(xk+1)<ϵ, 停止迭代，输出 x k + 1 x^{k+1} xk+1 ；否则：

  σ k + 1 = β σ k , k = k + 1 \sigma_{k+1}=\beta \sigma_{k}, k=k+1 σk+1​=βσk​,k=k+1
  返回 Step 1

收敛性分析

设 F ( x , σ ) = f ( x ) + σ p ( x ) F(x,\sigma)=f(x) + \sigma p(x) F(x,σ)=f(x)+σp(x)， x k + 1 x^{k+1} xk+1是 ( P ( σ k ) ) (P(\sigma_k)) (P(σk​))的精确解， x ∗ x^∗ x∗表示§的最优解。

引 理 \large\color{magenta}{\boxed{\color{brown}{引理 } }} 引理​

1. F ( σ k , x k ) ≤ F ( σ k + 1 , x k + 1 ) F\left(\sigma_{k}, x^{k}\right) \leq F\left(\sigma_{k+1}, x^{k+1}\right) F(σk​,xk)≤F(σk+1​,xk+1)
2. p ( x k ) ≥ p ( x k + 1 ) p\left(x^{k}\right) \geq p\left(x^{k+1}\right) p(xk)≥p(xk+1)
3. f ( x k ) ≤ f ( x k + 1 ) f\left(x^{k}\right) \leq f\left(x^{k+1}\right) f(xk)≤f(xk+1)
4. f ( x ∗ ) ≥ F ( σ k , x k ) ≥ f ( x k ) f\left(x^{*}\right) \geq F\left(\sigma_{k}, x^{k}\right) \geq f\left(x^{k}\right) f(x∗)≥F(σk​,xk)≥f(xk)

收 签 性 定 理 : \large\color{magenta}{\boxed{\color{brown}{收签性定理:} }} 收签性定理:​ 假设 f ( x ) ， g ( x ) ， f(x)， g(x)， f(x)，g(x)，和 p ( x ) ， p(x)， p(x)，是连续函数。设 { x k } , k = 1 , ⋯   , ∞ , \left\{x^{k}\right\}, k=1, \cdots, \infty, {xk},k=1,⋯,∞,是 P ( σ k ) P\left(\sigma_{k}\right) P(σk​) 的一个解的序列，那么 { x k } \left\{x^{k}\right\} {xk}的任意极限点 x ˉ \bar{x} xˉ是 P P P的解。

例子

min ⁡ f ( x ) = x 2  s.t.  g ( x ) = − x − 1 ≥ 0 \min f(x)=x^{2}\\ \text { s.t. } \quad g(x)=-x-1 \geq 0 minf(x)=x2 s.t. g(x)=−x−1≥0
该问题的可行域S= ( − ∞ , − 1 ] , (-\infty,-1], (−∞,−1], 最优解 x ∗ = − 1 x^{*}=-1 x∗=−1
 令    F ( x , σ ) = f ( x ) + 1 2 σ ∑ i = 1 m ( max ⁡ { 0 , − g i ( x ) } ) 2 = x 2 + 1 2 σ ( max ⁡ { 0 , x + 1 } ) 2 \begin{aligned} \begin{aligned} \text { 令 }~~F(x, \sigma) &=f(x)+\frac{1}{2} \sigma \sum_{i=1}^{m}\left(\max \left\{0,-g_{i}(x)\right\}\right)^{2} \\ &=x^{2}+\frac{1}{2} \sigma(\max \{0, x+1\})^{2} \end{aligned} \end{aligned}  令   F(x,σ)​=f(x)+21​σi=1∑m​(max{0,−gi​(x)})2=x2+21​σ(max{0,x+1})2​​
⇒ min ⁡ F ( x , σ ) \Rightarrow \min F(x, \sigma) ⇒minF(x,σ) 的解为 x ( σ ) = − σ 2 + σ x(\sigma)=-\frac{\sigma}{2+\sigma} x(σ)=−2+σσ​
⇒ x ( σ ) = − σ 2 + σ → − 1 = x ∗ , σ → + ∞ \Rightarrow x(\sigma)=-\frac{\sigma}{2+\sigma} \rightarrow-1=x^{*}, \sigma \rightarrow+\infty ⇒x(σ)=−2+σσ​→−1=x∗,σ→+∞

2.2不等式和等式约束的惩罚方法

KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ P : minimize …

这类一般问题的惩罚函数的主要类型如下:

p ( x ) = ∑ i = 1 m [ m a x { 0 , g i ( x ) } ] q + ∑ i = 1 k ∣ h i ( x ) ∣ q , q ≥ 1 p(x) =\sum_{i=1}^{m}{[max\{0,g_i(x)\}]^q}+\sum_{i=1}^{k}|h_i(x)|^q, q ≥ 1\\ p(x)=i=1∑m​[max{0,gi​(x)}]q+i=1∑k​∣hi​(x)∣q,q≥1

• p ( x ) = 0    i f    g ( x ) ≤ 0    a n d    h ( x ) = 0 p(x)=0\ \ if\ \ g(x) ≤ 0 \ \ and\ \ h(x)=0 p(x)=0  if  g(x)≤0  and  h(x)=0
• p ( x ) > 0    i f    g ( x ) > 0    o r    h ( x ) ≠ 0 p(x) > 0\ \ if\ \ g(x) > 0\ \ or\ \ h(x) \ne 0 p(x)>0  if  g(x)>0  or  h(x)​=0.

通常取 q = 2 q=2 q=2可定义辅助函数
F ( x , σ ) = f ( x ) + σ p ( x ) F(x,\sigma)=f(x)+\sigma p(x) F(x,σ)=f(x)+σp(x)
其中参数 σ \sigma σ 是很大的正数,把(3)转化为无约束的问题
m i n     F ( x , σ ) (4) min~~~F(x,\sigma) \tag{4} min   F(x,σ)(4)
显然，（4）的最优解使得 h i ( x ) h_i(x) hi​(x) 接近零，因为如果不这样的话，问题（4）中 的 σ ∑ i = 1 l h i 2 ( x ) \sigma\sum_{i=1}^{l}{h^2_i(x)} σ∑i=1l​hi2​(x) 项将是很大的正数，现行点必不是极小点。由此可见，求解问题（4）就能够得到问题(3)的近似解。

例子：

m i n     x  s.t.  x − 2 ≥ 0 (4) \begin{aligned} & min ~~~x \\ & \text { s.t. } \quad x-2\geq0 \end{aligned}\tag{4} ​min   x s.t. x−2≥0​(4)

P ( x ) = [ m a x { 0 , − g ( x ) } ] 2 = { 0    x ≥ 2 − g i ( x )    x ≺ 2 P(x) = [max\{0,-g(x)\}]^2=\begin{cases} 0 \space\space x\geq2\\[2ex] -g_i(x)\space\space x\prec2\\[2ex] \end{cases} P(x)=[max{0,−g(x)}]2=⎩⎪⎨⎪⎧​0  x≥2−gi​(x)  x≺2​

罚函数 F ( x , σ ) = x + σ P ( x ) F(x,\sigma)=x+\sigma P(x) F(x,σ)=x+σP(x)

可通过求解下列无约束问题，求得（4）的近似解：

m i n   x + σ P ( x ) min\space x+\sigma P(x) min x+σP(x)

用解析方法求解无约束问题：

d F d x = { 1    x ≥ 2 1 + 2 σ ( x − 2 )    x ≺ 2 \frac{dF}{dx}=\begin{cases}1 \space\space &x\geq2\\ 1+2\sigma(x-2)\space\space &x\prec2\\ \end{cases} dxdF​={1  1+2σ(x−2)  ​x≥2x≺2​
令 d F d x = 0 \frac{dF}{dx}=0 dxdF​=0 ,解得 x σ ˉ = 2 − 1 2 σ \bar{x_\sigma}=2-\frac{1}{2\sigma} xσ​ˉ​=2−2σ1​

显然， σ \sigma σ 越大， x σ ˉ \bar{x_\sigma} xσ​ˉ​ 越接近问题（4）得最优解，当 σ → \sigma\rightarrow σ→+ 无穷大时， x σ ˉ → x ˉ = 2 \bar{x_\sigma}\rightarrow\bar{x}=2 xσ​ˉ​→xˉ=2 。

实例代码

工厂在每种原料有限的情况下，如果每种材料需要满足一定配比，如何规划生产可以使得开销最小

1. 开销函数 ( ( ( 最优化的目标函数 ) : y = ( x 1 − 1 ) 2 + ( x 1 − x 2 ) 2 + ( x 2 − x 3 ) 2 ): y=\left(x_{1}-1\right)^{2}+\left(x_{1}-x_{2}\right)^{2}+\left(x_{2}-x_{3}\right)^{2} ):y=(x1​−1)2+(x1​−x2​)2+(x2​−x3​)2
2. 配比限制 (等式约束) ： x 1 ( 1 + x 2 2 ) + x 3 4 − 4 − 3 2 = 0 ： x_{1}\left(1+x_{2}^{2}\right)+x_{3}^{4}-4-3 \sqrt{2}=0 ：x1​(1+x22​)+x34​−4−32 ​=0
3. 原料限制 (不等式约束) ： x i ≤ 10 , i = 1 , 2 , 3 ： x_{i} \leq 10, i=1,2,3 ：xi​≤10,i=1,2,3

x 1 , x 2 , x 3 x_1,x_2,x_3 x1​,x2​,x3​的初值均在 [ 0 , 4 ] [ 0 , 4 ] [0,4]的范围内随机生成，总共生成100组起点。统计迭代成功（在1000步内得到最优解且单次步长搜索迭代次数不超过1000次）的样本的平均迭代步数、平均迭代时间和得到的最优解及开销函数最小值。

使用共轭梯度PRP+法的外点罚函数法

import numpy as np
from scipy import linalg

n=3 #x的长度
sigma1 =2 #sigma的初值

def func(x):
    return #函数

def hj(x):
	#构造数组h，第j位是第j+1个等式限制条件计算的值
    return h

def gi(x):
    #构造数组g，第i位是第i+1个不等式限制条件计算的值
    return g

def p(x):
    h=hj(x)
    g=gi(x)
    return np.sum(np.power(h,2))+np.sum(np.power(np.where(g<0,0,g),2))

def myFunc(x):
    return  func(x)+p(x)*sigma1

beta=1.5	#放大因子
epsilon =0.001 #精度
x=np.array([2.0,2.0,2.0])	#初值点
k1=0
while sigma1*p(x)>=epsilon:
    e=0.001
    beta1=1
    sigma=0.4
    rho=0.55
    tar=Function(myFunc)
    k=0
    d=-tar.grad(x)
    while tar.norm(x)>e:
        a=1
        if not (tar.value(x+a*d)<=tar.value(x)+rho*a*dot(turn(tar.grad(x)),d) and \
            np.abs(dot(turn(tar.grad(x+a*d)),d))>=sigma*dot(turn(tar.grad(x)),d)):
            a=beta1
            while tar.value(x+a*d)>tar.value(x)+rho*a*dot(turn(tar.grad(x)),d):
                a*=rho
            while np.abs(dot(turn(tar.grad(x+a*d)),d))<sigma*dot(turn(tar.grad(x)),d):
                a1=a/rho
                da=a1-a
                while tar.value(x+(a+da)*d)>tar.value(x)+rho*(a+da)*dot(turn(tar.grad(x)),d):
                    da*=rho
                a+=da
        lx=x
        x=x+a*d
        beta=np.max((dot(turn(tar.grad(x)),tar.grad(x)-tar.grad(lx))/(tar.norm(lx)**2),0))	#PRP+
        d=-tar.grad(x)+beta*d
        k+=1
        print(k1,k)
    sigma1*=beta
    k1+=1
print(x)

外点法中的KKT乘数

表示
g + ( x ) = ( max ⁡ { 0 , g 1 ( x ) } , ⋯   , max ⁡ { 0 , g m ( x ) } ) T g^{+}(x)=\left(\max \left\{0, g_{1}(x)\right\}, \cdots, \max \left\{0, g_{m}(x)\right\}\right)^{T} g+(x)=(max{0,g1​(x)},⋯,max{0,gm​(x)})T
则罚函数可以写成
p ( x ) = γ ( g + ( x ) ) p(x)=\gamma\left(g^{+}(x)\right) p(x)=γ(g+(x))
其中 γ ( y ) \gamma(y) γ(y)是 y ∈ ( R m ) + y \in\left(R^{m}\right)^{+} y∈(Rm)+ 的函数。 例如: γ ( y ) = ∑ i = 1 m y i , \gamma(y)=\sum_{i=1}^{m} y_{i}, γ(y)=∑i=1m​yi​, 或 γ ( y ) = ∑ i = 1 m y i 2 \gamma(y)=\sum_{i=1}^{m} y_{i}^{2} γ(y)=∑i=1m​yi2​

如果假设
∂ γ ( y ) ∂ y i = 0 , y i = 0 , i = 1 , ⋯   , m \frac{\partial \gamma(y)}{\partial y_{i}}=0, y_{i}=0, i=1, \cdots, m ∂yi​∂γ(y)​=0,yi​=0,i=1,⋯,m
那么 p ( x ) p(x) p(x)是可微的，并且
∇ p ( x ) = ∑ i = 1 m ∂ γ ( g + ( x ) ) ∂ y i ∇ g i ( x ) \nabla p(x)=\sum_{i=1}^{m} \frac{\partial \gamma\left(g^{+}(x)\right)}{\partial y_{i}} \nabla g_{i}(x) ∇p(x)=i=1∑m​∂yi​∂γ(g+(x))​∇gi​(x)
设 x k x^{k} xk 是 P ( σ k − 1 ) . P\left(\sigma_{k-1}\right) . P(σk−1​). 的一个解
∇ f ( x k ) + σ k − 1 ∇ p ( x k ) = 0 \nabla f\left(x^{k}\right)+\sigma_{k-1} \nabla p\left(x^{k}\right)=0 ∇f(xk)+σk−1​∇p(xk)=0
就是说
∇ f ( x k ) + σ k − 1 ∑ i = 1 m ∂ γ ( g + ( x k ) ) ∂ y i ∇ g i ( x k ) = 0 \nabla f\left(x^{k}\right)+\sigma_{k-1} \sum_{i=1}^{m} \frac{\partial \gamma\left(g^{+}\left(x^{k}\right)\right)}{\partial y_{i}} \nabla g_{i}\left(x^{k}\right)=0 ∇f(xk)+σk−1​i=1∑m​∂yi​∂γ(g+(xk))​∇gi​(xk)=0
定义
u i k = σ k − 1 ∂ γ ( g + ( x k ) ) ∂ y i u_{i}^{k}=\sigma_{k-1} \frac{\partial \gamma\left(g^{+}\left(x^{k}\right)\right)}{\partial y_{i}} uik​=σk−1​∂yi​∂γ(g+(xk))​
则
∇ f ( x k ) + ∑ i = 1 m u i k ∇ g i ( x k ) = 0 \nabla f\left(x^{k}\right)+\sum_{i=1}^{m} u_{i}^{k} \nabla g_{i}\left(x^{k}\right)=0 ∇f(xk)+i=1∑m​uik​∇gi​(xk)=0

3 内点法（Barrier Methods）

优化问题解的迭代过程是从约束域内部出发，沿着中心路径逐步走到边界.当 x x x趋于边界时，那么障碍函数趋于无穷； 在可行域内时，障碍函数值很小，增广目标函数与原始目标函数等价了；

内点法产生的点列从可行域的内部逼近问题的解，因此此方法活用于下列不等式约束的问题:
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ P : minimize …

记可行域为
S = { x ∣ g i ( x ) ≤ 0 , i = 1 , 2 , … m } S 0 = { x ∣ g i ( x ) < 0 , i = 1 , 2 , … m } S=\left\{x \mid g_{i}(x) \leq 0, i=1,2, \ldots m\right\}\\ S_{0}=\left\{x \mid g_{i}(x)<0, i=1,2, \ldots m\right\} S={x∣gi​(x)≤0,i=1,2,…m}S0​={x∣gi​(x)<0,i=1,2,…m}
S 0 S_{0} S0​ 是严格可行域。

内点罚函数法的基本思想:构造辅助(光滑)函数 F ( x , σ ) F(x,\sigma) F(x,σ)该函数在严格可行域 S 0 S_{0} S0​ 以外的取值为无穷大,且当点 x x x从 S 0 S_{0} S0​ 趋于 S S S的边界时,函数值趋于无穷大.这样,无约束问题 m i n   F ( x , σ ) min~F(x,\sigma) min F(x,σ)的解一定在 S 0 S_{0} S0​内。我们希望当 σ → 0 \sigma→0 σ→0时,上述无约束问题的解 x ( σ ) x(\sigma) x(σ)趋于问题(5)的解.辅助函数 F ( x , σ ) F(x,\sigma) F(x,σ)在S的边界筑起了一道很高的墙,把无约束问题 m i n   F ( x , σ ) min~F(x,\sigma) min F(x,σ)的解挡住了可行域 S S S的内部。因此,内点法也称为障碍函数法．

障碍法的思想是劝阻点 x x x不要接近可行域的边界，我们解决障碍函数问题:
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ B(\sigma) : …
对于序列 σ k \sigma_k σk​ σ k > 0 , \sigma_k>0, σk​>0, 且 σ 1 > σ 2 > … > σ k > r k + 1 > … , σ k → 0 \sigma_{1}>\sigma_{2}>\ldots>\sigma_{k}>r_{k+1}>\ldots, \sigma_{k} \rightarrow 0 σ1​>σ2​>…>σk​>rk+1​>…,σk​→0。注意，约束“ g ( x ) < 0 g(x) < 0 g(x)<0”在 B ( σ ) B(\sigma) B(σ) 中实际上不重要，因为它们在 B ( σ ) B(\sigma) B(σ)中从不绑定。

定 义 \large\color{magenta}{\boxed{\color{brown}{定义 } }} 定义​ 函数 b ( x ) : R n → R b(x) : R^n → R b(x):Rn→R 称为 P P P 的障碍函数,满足如下规则：

• $当 g(x) < 0\qquad {b }(x) \geq 0, $
• 当 lim ⁡ x max ⁡ i { g i ( x ) } → 0 \lim_{x}{\max_i \left\{ g_i(x)\right\}} → 0 limx​maxi​{gi​(x)}→0 也就是当 x x x趋向可行域的边界时， b ( x ) → ∞ , {b }(x) \rightarrow \infty , \qquad b(x)→∞,

b ( x ) b(x) b(x) 函数的两个重要的形式：

• b ( x ) = ∑ i m 1 − g i ( x ) b(x) = \sum_{i}^{m}{\frac{1}{-g_{i}(x)}} b(x)=∑im​−gi​(x)1​
• b ( x ) = − ∑ i m l n { − g i ( x ) } b(x) =-\sum_{i}^{m}{ln \left\{ -g_{i}(x) \right\}} b(x)=−∑im​ln{−gi​(x)}

假设 g ( x ) = ( x − 4 , 1 − x ) T , x ∈ R 1 g(x)=(x − 4, 1 − x)^T , x ∈ R^1 g(x)=(x−4,1−x)T,x∈R1 .则 b ( x ) = 1 4 − x + 1 x − 1 b(x)=\frac{1}{4-x}+\frac{1}{x-1} b(x)=4−x1​+x−11​

让
F ( σ , x ) = f ( x ) + σ b ( x ) (7) F(\sigma,x) =f(x)+{\sigma} b(x)\tag{7} F(σ,x)=f(x)+σb(x)(7)
则 解决（6）问题等同于 m i n   F ( σ k , x ) = f ( x ) + σ k b ( x ) min \ F(\sigma_k,x)=f(x)+{\sigma_k} b(x) min F(σk​,x)=f(x)+σk​b(x) ,

令序列 { σ k } \left\{ {\sigma_k } \right\} {σk​} 满足 σ k + 1 > σ k \sigma_{k+1}>\sigma_k σk+1​>σk​ ,当 k → ∞ k\rightarrow \infty k→∞ ,有 σ k → ∞ \sigma_k \rightarrow \infty σk​→∞ ， 则 x k x^k xk 表示 B ( σ k ) B(\sigma^k) B(σk) 的精确解

σ \sigma σ 是很小的正数。这样，当 x x x趋向边界时，函数 F ( σ , x ) → F(\sigma,x) \rightarrow F(σ,x)→ +无穷大；否则， x x x 在可行域内时，由于 σ \sigma σ很小，则函数 F ( σ , x ) F(\sigma,x) F(σ,x)的取值近似 f ( x ) f(x) f(x) 。由于 b ( x ) b(x) b(x)的存在，在可行域形成“围墙”，因此 m i n   F ( σ , x ) min \ F(\sigma,x) min F(σ,x) 的解含于可行域的内部.

计算步骤

• 显然， σ {\sigma} σ 取值越小， r ( σ , x ) r(\sigma,x) r(σ,x) 的最优解越接近 (2) 的最优解。但是，如果 σ {\sigma} σ太小，则将给 (5) 的计算带来很大的困难。

• 因此，仍采取序列无约束极小化方法 (SUMT) ，取一个严格单调减且趋于零的罚因子。（也叫障碍因子）数列{ σ k {\sigma_k} σk​ },对于每一个 k k k ,从内部出发，求解问题：
  P ( σ k ) : m i n   F ( σ k , x )  s.t.  x ∈ R n \begin{aligned} &P(\sigma_k): min \ F(\sigma_k ,x) \\ & \text { s.t. } \quad x \in R^{n} \end{aligned} ​P(σk​):min F(σk​,x) s.t. x∈Rn​

1. 给定初始内点 x 0 x_{0} x0​ ,允许误差 ε ≻ 0 \varepsilon\succ0 ε≻0 ，初始参数 σ 1 \sigma_1 σ1​ ，缩小系数 β ∈ ( 0 , 1 ) \beta\in(0,1) β∈(0,1) ,令 k=1

2. 以 x ( k − 1 ) x^{(k-1)} x(k−1) 为初始点，求解无约束问题 m i n    f ( x ) + σ k b ( x ) min \ \ f(x)+{\sigma_k} b(x) min  f(x)+σk​b(x)

   设其极小点为 x k x_{k} xk​

3. 若 σ k b ( x k ) < ε {\sigma_k} b(x_{k} ) <\varepsilon σk​b(xk​)<ε ,则停止计算，得到点 x k x_{k} xk​ ;否则，令 σ k + 1 = β σ k {\sigma_{k+1}}=\beta {\sigma_{k}} σk+1​=βσk​ ,令 k = k + 1 k=k+1 k=k+1 ,返回步2

具体案例

m i n     1 12 ( x 1 + 1 ) 3 + x 2  s.t.  x 1 − 1 ≥ 0     x 2 ≥ 0 \begin{aligned} min ~~~&\frac{1}{12}(x_{1}+1)^3+x_{2}\\ \text { s.t. } \quad &x_{1}-1 \geq0 \\~~~ &x_{2}\geq0 \end{aligned} min    s.t.    ​121​(x1​+1)3+x2​x1​−1≥0x2​≥0​

令
F ( x , σ k ) = 1 12 ( x 1 + 1 ) 3 + x 2 + σ k ( 1 x 1 − 1 + 1 x 2 ) F(x,\sigma_{k})=\frac{1}{12}(x_{1}+1)^3+x_{2}+\sigma_{k}(\frac{1}{x_{1}-1}+\frac{1}{x_{2}}) F(x,σk​)=121​(x1​+1)3+x2​+σk​(x1​−11​+x2​1​)
用解析法求解：
m i n   F ( σ k , x )  s.t.  x ∈ R n \begin{aligned} min \ F(\sigma_k ,x) \\ \text { s.t. } \quad x \in R^{n} \end{aligned} min F(σk​,x) s.t. x∈Rn​

∂ F ( x ) ∂ x 1 = 1 4 ( x 1 + 1 ) 2 − σ k x 1 − 1 = 0         ( 2 ) ∂ F ( x ) ∂ x 2 = 1 − σ k x 2 2 = 0         ( 3 ) \frac{∂F(x)}{∂x_1}=\frac{1}{4}(x_{1}+1)^2-\frac{\sigma_{k}}{x_{1}-1}=0 ~~~~~~~ (2)\\ \frac{∂F(x)}{∂x_2}=1-\frac{\sigma_{k}}{x^2_{2}} = 0 ~~~~~~~ (3) ∂x1​∂F(x)​=41​(x1​+1)2−x1​−1σk​​=0       (2)∂x2​∂F(x)​=1−x22​σk​​=0       (3)
由 (2) 式可得， x 1 = 1 + 2 σ k x_1 = \sqrt{1+2\sqrt{\sigma_k}} x1​=1+2σk​ ​ ​ ; 由 (3) 式可得， x 2 = σ k x_2 = \sqrt{\sigma_k} x2​=σk​ ​ ,故：

x r k ‾ = ( x 1 , x 2 ) = ( 1 + 2 σ k , σ k ) \overline {x_{r_{k}}} = (x_{1},x_{2}) = (\sqrt{1+2\sqrt{\sigma_k}},\sqrt{\sigma_k}) xrk​​​=(x1​,x2​)=(1+2σk​ ​ ​,σk​ ​)
当 σ k → 0 \sigma_k\rightarrow0 σk​→0 时， x r k ‾ → x ˉ = ( 1 , 0 ) \overline{x_{r_k}}\rightarrow\bar{x}=(1,0) xrk​​​→xˉ=(1,0) , x ˉ \bar{x} xˉ 就是原问题的最优解。

收签性分析

引 理 \large\color{magenta}{\boxed{\color{brown}{引理 } }} 引理​: 对于由内点罚函数法产生的点列 { x k } , k ≥ 1 , \left\{x^{k}\right\}, k \geq 1, {xk},k≥1, 总有:

(1) F ( x k + 1 , σ k + 1 ) ≤ F ( x k , σ k ) F\left(x^{k+1}, \sigma_{k+1}\right) \leq F\left(x^{k}, \sigma_{k}\right) F(xk+1,σk+1​)≤F(xk,σk​)
(2) b ( x k + 1 ) ≥ b ( x k ) b\left(x^{k+1}\right) \geq b\left(x^{k}\right) b(xk+1)≥b(xk)
(3) f ( x k + 1 ) ≤ f ( x k ) f\left(x^{k+1}\right) \leq f\left(x^{k}\right) f(xk+1)≤f(xk)

收 签 性 定 理 : \large\color{magenta}{\boxed{\color{brown}{收签性定理:} }} 收签性定理:​ 设在问题（5）中，可行域 S S S 的内点集非空，
 int  S = { x ∈ R n ∣ g i ( x ) < 0 , i = 1 , 2 , … , m } ≠ Φ \text { int } S=\left\{x \in R^{n} \mid g_{i}(x)<0, i=1,2, \ldots, m\right\} \neq \Phi  int S={x∈Rn∣gi​(x)<0,i=1,2,…,m}​=Φ
f ( x ) f(x) f(x) 在 S S S 上存在最优解 x ∗ , x^{*}, x∗, 对严格单减正数列 { σ k } : σ k + 1 < σ k σ k → 0 , \left\{\sigma_{k}\right\}: \sigma_{k+1}<\sigma_{k} \quad \sigma_{k} \rightarrow 0, \quad {σk​}:σk+1​<σk​σk​→0, 由（7）定义的 F ( x , σ k ) F\left(x, \sigma_{k}\right) F(x,σk​)在 i n t   S int~S int S内存在极小点， 则由内点法产生的点列 { x k } \left\{x^{k}\right\} {xk}的任何聚点 x ~ \tilde{x} x~ 是约束问题的最优解。

【证明】 : 先 证 { F ( x ( k ) , σ k ) } \left\{F\left(x^{(k)}, \sigma_{\mathrm{k}}\right)\right\} {F(x(k),σk​)} 是 单 调 减有下界的序列.
设 x ( k ) , x ( k + 1 ) ∈ x^{(k)}, x^{(k+1)} \in x(k),x(k+1)∈ int S S S 分 别 为 F ( x , σ k ) F\left(x, \sigma_{k}\right) F(x,σk​) 和 F ( x , σ k + 1 ) F\left(x, \sigma_{k+1}\right) F(x,σk+1​) 极小点，由于 σ k + 1 < σ k , \sigma_{k+1}<\sigma_{k}, σk+1​<σk​, 则
F ( x ( k + 1 ) , σ k + 1 ) = f ( x ( k + 1 ) ) + σ k + 1 b ( x ( k + 1 ) ) ≤ f ( x ( k ) ) + σ k + 1 b ( x ( k ) ) ≤ f ( x ( k ) ) + σ k b ( x ( k ) ) = F ( x ( k ) , σ k ) (8) \begin{aligned} F\left(x^{(k+1)}, \sigma_{k+1}\right)&=f\left(x^{(k+1)}\right)+\sigma_{k+1} b\left(x^{(k+1)}\right) \\ & \leq f\left(x^{(k)}\right)+\sigma_{k+1} b\left(x^{(k)}\right) \\ & \leq f\left(x^{(k)}\right)+\sigma_{k} b\left(x^{(k)}\right) \\ &=F\left(x^{(k)}, \sigma_{k}\right) \end{aligned}\tag{8} F(x(k+1),σk+1​)​=f(x(k+1))+σk+1​b(x(k+1))≤f(x(k))+σk+1​b(x(k))≤f(x(k))+σk​b(x(k))=F(x(k),σk​)​(8)
设 x ∗ x^* x∗ 是问题(5)的最优解.由于 x ( k ) x^{(k)} x(k) 是 可 行 点,则 f ( x ( k ) ) ≥ f ( x ∗ ) \quad f\left(x^{(k)}\right) \geq f\left(x^{*}\right) f(x(k))≥f(x∗)
又知
F ( x ( k ) , σ k ) ≥ f ( x ( k ) ) F\left(x^{(k)}, \sigma_{k}\right) \geq f\left(x^{(k)}\right) F(x(k),σk​)≥f(x(k))
故有
F ( x ( k ) , σ k ) ≥ f ( x ∗ ) (9) F\left(x^{(k)}, \sigma_{k}\right) \geq f\left(x^{*}\right)\tag{9} F(x(k),σk​)≥f(x∗)(9)
从而 { F ( x ( k ) , σ k ) } \left\{F\left(x^{(k)}, \sigma_{k}\right)\right\} {F(x(k),σk​)} 为单调减有下界序列.从而存在极限：
G ^ ≥ f ( x ∗ ) \hat{G} \geq f\left(x^{*}\right) G^≥f(x∗)
下证 G ^ = f ( x ∗ ) \hat{G}=f\left(x^{*}\right) G^=f(x∗)
如若不然 , G ^ > f ( x ∗ ) , \hat{G}>f\left(x^{*}\right) ,G^>f(x∗).由于 f ( x ) f(x) f(x) 是 连续 函数,故存在 正数 δ , \delta, δ, 使 得当 ∥ x − x ∗ ∥ < δ \|x-x ^*\|<\delta ∥x−x∗∥<δ 且 x ∈ x \in x∈ int S S S 时有
f ( x ) − f ( x ∗ ) ≤ 1 2 ( G ^ − f ( x ∗ ) ) f(x)-f\left(x^{*}\right) \leq \frac{1}{2}\left(\hat{G}-f\left(x^{*}\right)\right) f(x)−f(x∗)≤21​(G^−f(x∗))
即
f ( x ) ≤ 1 2 ( G ^ + f ( x ∗ ) ) (10) f(x) \leq \frac{1}{2}\left(\hat{G}+f\left(x^{*}\right)\right)\tag{10} f(x)≤21​(G^+f(x∗))(10)
任 取一 点 x ^ ∈ \hat{x} \in x^∈ int S , S, S, 使 ∥ x ^ − x ∗ ∥ < δ \|\hat{x}-x^ *\|<\delta ∥x^−x∗∥<δ. 由于 σ k → 0 \sigma_{\mathrm{k}} \rightarrow 0 σk​→0,
因此存在 K , K, K, 当 k > K k>K k>K 时，
σ k b ( x ^ ) < 1 4 ( G ^ − f ( x ∗ ) ) \sigma_{\mathrm{k}} b(\hat{x})<\frac{1}{4}\left(\hat{G}-f\left(x^{*}\right)\right) σk​b(x^)<41​(G^−f(x∗))
于 是, 当 k > K k>K k>K 时,根据 F ( x ( k ) , σ k ) F\left(x^{(k)}, \sigma_{\mathrm{k}}\right) F(x(k),σk​) 的定义及式 ( 10 ) , (10), (10),故有
F ( x ( k ) , σ k ) = f ( x ( k ) ) + σ k b ( x ( k ) ) ≤ f ( x ^ ) + σ k b ( x ^ ) ≤ 1 2 ( G ^ + f ( x ∗ ) ) + 1 4 ( G ^ − f ( x ∗ ) ) = G ^ − 1 4 ( G ^ − f ( x ∗ ) ) \begin{aligned} F\left(x^{(k)}, \sigma_{k}\right) &=f\left(x^{(k)}\right)+\sigma_{k} b\left(x^{(k)}\right) \\ & \leq f(\hat{x})+\sigma_{k} b(\hat{x}) \\ & \leq \frac{1}{2}\left(\hat{G}+f\left(x^{*}\right)\right)+\frac{1}{4}\left(\hat{G}-f\left(x^{*}\right)\right) \\ &=\hat{G}-\frac{1}{4}\left(\hat{G}-f\left(x^{*}\right)\right) \end{aligned} F(x(k),σk​)​=f(x(k))+σk​b(x(k))≤f(x^)+σk​b(x^)≤21​(G^+f(x∗))+41​(G^−f(x∗))=G^−41​(G^−f(x∗))​
上式与 F ( x ( k ) , σ k ) → G ^ F\left(x^{(k)}, \sigma_{k}\right) \rightarrow \hat{G} F(x(k),σk​)→G^ 相矛盾.故必有
G ^ = f ( x ∗ ) \hat{G}=f\left(x^{*}\right) G^=f(x∗)
下 证 x ˉ \bar{x} xˉ 是 最优解.

设 { x ( k j ) } \left\{x^{\left(k_{j}\right)}\right\} {x(kj​)} 是 { x ( k ) } \left\{x^{(k)}\right\} {x(k)} 的收签子列,且
lim ⁡ k j → ∞ x ( k j ) = x ˉ \lim _{k_{j} \rightarrow \infty} x^{\left(k_{j}\right)}=\bar{x} kj​→∞lim​x(kj​)=xˉ
由于 x ( k j ) x^{\left(k_{j}\right)} x(kj​) 是可行域 S S S 的 内 点,即满足
g i ( x ( k j ) ) > 0 , i = 1 , … , m g_{i}\left(x^{\left(k_{j}\right)}\right)>0, i=1, \ldots, m gi​(x(kj​))>0,i=1,…,m
g i ( x ) g_{i}(x) gi​(x) 连续,故
lim ⁡ k j → ∞ g i ( x ( k j ) ) = g i ( x ˉ ) , i = 1 , … , m (11) \lim _{k_{j} \rightarrow \infty} g_{i}\left(x^{\left(k_{j}\right)}\right)=g_{i}(\bar{x}), i=1, \ldots, m\tag{11} kj​→∞lim​gi​(x(kj​))=gi​(xˉ),i=1,…,m(11)
由此可知, x ˉ \bar{x} xˉ 是可行点.又 x x x *是 ( 5 ) (5) (5) 的 最优解,故
f ( x ∗ ) ≤ f ( x ˉ ) f\left(x^{*}\right) \leq f(\bar{x}) f(x∗)≤f(xˉ)
上式必为等式.如若不然, f ( x ∗ ) < f ( x ˉ ) f\left(x^{*}\right)<f(\bar{x}) f(x∗)<f(xˉ),则
lim ⁡ k j → ∞ { f ( x ( k j ) ) − f ( x ∗ ) } = f ( x ˉ ) − f ( x ∗ ) > 0 \lim _{k_{j} \rightarrow \infty}\left\{f\left(x^{\left(k_{j}\right)}\right)-f\left(x^{*}\right)\right\}=f(\bar{x})-f\left(x^{*}\right)>0 kj​→∞lim​{f(x(kj​))−f(x∗)}=f(xˉ)−f(x∗)>0
于是当 k j → ∞ k_{j} \rightarrow \infty kj​→∞ 时
F ( x ( k j ) , μ k ) − f ( x ∗ ) = f ( x ( k j ) ) − f ( x ∗ ) + μ k j B ( x ( k j ) ) ≥ f ( x ( k j ) ) − f ( x ∗ ) \begin{aligned} F\left(x^{\left(k_{j}\right)}, \mu_{k}\right)-f\left(x^{*}\right) &=f\left(x^{\left(k_{j}\right)}\right)-f\left(x^{*}\right)+\mu_{k_{j}} B\left(x^{\left(k_{j}\right)}\right) \\ & \geq f\left(x^{\left(k_{j}\right)}\right)-f\left(x^{*}\right) \end{aligned} F(x(kj​),μk​)−f(x∗)​=f(x(kj​))−f(x∗)+μkj​​B(x(kj​))≥f(x(kj​))−f(x∗)​
不趋于0, 此与
lim ⁡ k → ∞ F ( x ( k ) , μ k ) = G ˉ = f ( x ∗ ) ,  矛盾。  \lim _{k \rightarrow \infty} F\left(x^{(k)}, \mu_{k}\right)=\bar{G}=f\left(x^{*}\right), \quad \text { 矛盾。 } k→∞lim​F(x(k),μk​)=Gˉ=f(x∗), 矛盾。 
故
f ( x ∗ ) = f ( x ˉ ) f\left(x^{*}\right)=f(\bar{x}) f(x∗)=f(xˉ)
从而 x ˉ \bar{x} xˉ 是(5)的最优解.

内点罚函数法几点说明

1. 初始点 x 0 x^0 x0 的选取

   使用内点法时，初始点应选择一个离约束边界较远的可行点。如果太靠近某一约束边界，求解无约束优化问题时可能会发生困难。

2. 初始罚因子 σ 1 \sigma_{1} σ1​ 的选取

   惩罚因子的初值应适当，否则会影响迭代计算的正常 进行，太大将增加迭代次数：太小会使惩罚函数的性 态变坏，其至难以收签到极值点。对全不同的问题， 都要经过多次试算，才能决定一个适当 σ 1 \sigma_{1} σ1​

3. 罚因子的缩减系数 β \beta β的选取

   σ k + 1 = β σ k ( k = 1 , 2 , … ) \quad \sigma_{k+1}=\beta \sigma_{k} \quad(k=1,2, \ldots) σk+1​=βσk​(k=1,2,…) , β \beta β值的大小在迭代过程中不起决定性作用，通常的取 值范围在0.1~ 0.7之间。

4. 由于无约束优化问题的解法目前已经有许多很有效的算法，如DFP算法，BFGS法等，所以在求解复杂的约束优化问题时，工程技术人员一般乐于采用罚函数法。简单、易懂。

5. 为求解约束优化问题，需要求解一系列的无约束优化问题，计算量大，且罚因子的选取方法对收敛速度的影响比较大。并且罚因子的增大（外点法）与缩小(内点法）使得问题的求解变得很困难。常常会使增广目标函数趋于病态。这是罚函数法固有的弱点，使其使用受到限制。这正是乘子法所要解决的问题。

3、混合惩罚函数法

混合惩罚函数法及其算法步骤

由于内点法容易处理不等式约束优化设计问题，而外点法又容易处理等式约束优化设计问题,因而可将内点法与外点法结合起来,处理同时具有等式约束和不等式约束的优化设计问题。在构造惩罚函数时,可以同时包括障碍项与惩罚项，并将惩罚因子统一用r r ( k ) r^{(\mathrm{k})} r(k) 表示：
ϕ ( x , r ) = f ( x ) − r ∑ j = 1 m 1 g j ( x ) + 1 r ∑ k = 1 l [ h k ( x ) ] 2 \phi(x, r)=f(x)-r \sum_{j=1}^{m} \frac{1}{g_{j}(x)}+\frac{1}{\sqrt{r}} \sum_{k=1}^{l}\left[h_{k}(x)\right]^{2} ϕ(x,r)=f(x)−rj=1∑m​gj​(x)1​+r ​1​k=1∑l​[hk​(x)]2
这种同时处理等式和不等式约束的惩罚函数法称 为混合惩罚函数法。混合惩罚函数法与前述内点法 和外点法一样，也属于序列无约束极小化(SUMT)方 法中的一种方法。

参考资料

MIT凸优化课程

Stephen Boyd的Convex Optimization

《凸优化》，Stephen Boyd等著，王书宁等译

“最优化理论与算法”北京邮电大学数学系

其使用受到限制。这正是乘子法所要解决的问题。

3、混合惩罚函数法

混合惩罚函数法及其算法步骤

由于内点法容易处理不等式约束优化设计问题，而外点法又容易处理等式约束优化设计问题,因而可将内点法与外点法结合起来,处理同时具有等式约束和不等式约束的优化设计问题。在构造惩罚函数时,可以同时包括障碍项与惩罚项，并将惩罚因子统一用r r ( k ) r^{(\mathrm{k})} r(k) 表示：
ϕ ( x , r ) = f ( x ) − r ∑ j = 1 m 1 g j ( x ) + 1 r ∑ k = 1 l [ h k ( x ) ] 2 \phi(x, r)=f(x)-r \sum_{j=1}^{m} \frac{1}{g_{j}(x)}+\frac{1}{\sqrt{r}} \sum_{k=1}^{l}\left[h_{k}(x)\right]^{2} ϕ(x,r)=f(x)−rj=1∑m​gj​(x)1​+r ​1​k=1∑l​[hk​(x)]2
这种同时处理等式和不等式约束的惩罚函数法称 为混合惩罚函数法。混合惩罚函数法与前述内点法 和外点法一样，也属于序列无约束极小化(SUMT)方 法中的一种方法。

参考资料

MIT凸优化课程

Stephen Boyd的Convex Optimization

《凸优化》，Stephen Boyd等著，王书宁等译

“最优化理论与算法”北京邮电大学数学系