增广拉格朗日函数的三种统一公式

《Unified theory of augmented Lagrangian methods for constrained global optimization》增广拉格朗日函数统一为一下三种形式：
L P ( x , λ , c ) = { f ( x ) + 1 c ∑ i = 1 m P ( c g i ( x ) , λ i ) , x ∈ Ω c ( a ) + ∞ , x ∉ Ω c ( a ) L_P(x,\lambda,c)=\left\{\begin{aligned}&f(x)+\frac{1}{c}\sum\limits_{i=1}^mP(cg_i(x),\lambda_i),&&x\in\Omega_c(a)\\&+\infty,&&x\notin\Omega_c(a)\end{aligned}\right. LP​(x,λ,c)=⎩⎪⎪⎨⎪⎪⎧​​f(x)+c1​i=1∑m​P(cgi​(x),λi​),+∞,​​x∈Ωc​(a)x∈/​Ωc​(a)​

L R ( x , λ , c ) = { f ( x ) + 1 c ∑ i = 1 m R ( c g i ( x ) , λ i ) , x ∈ Ω c ( a ) + ∞ , x ∉ Ω c ( a ) L_R(x,\lambda,c)=\left\{\begin{aligned}&f(x)+\frac{1}{c}\sum\limits_{i=1}^mR(cg_i(x),\lambda_i),&&x\in\Omega_c(a)\\&+\infty,&&x\notin\Omega_c(a)\end{aligned}\right. LR​(x,λ,c)=⎩⎪⎪⎨⎪⎪⎧​​f(x)+c1​i=1∑m​R(cgi​(x),λi​),+∞,​​x∈Ωc​(a)x∈/​Ωc​(a)​

L p ( x , λ , c ) = { f ( x ) + 1 c ∑ i = 1 m V ( c g i ( x ) , λ i ) , x ∈ Ω c ( a ) + ∞ , x ∉ Ω c ( a ) L_p(x,\lambda,c)=\left\{\begin{aligned}&f(x)+\frac{1}{c}\sum\limits_{i=1}^mV(cg_i(x),\lambda_i),&&x\in\Omega_c(a)\\&+\infty,&&x\notin\Omega_c(a)\end{aligned}\right. Lp​(x,λ,c)=⎩⎪⎪⎨⎪⎪⎧​​f(x)+c1​i=1∑m​V(cgi​(x),λi​),+∞,​​x∈Ωc​(a)x∈/​Ωc​(a)​

下面分别介绍以上三种统一形式的增广拉格朗日函数

1 P-type 增广拉格朗日函数

L P ( x , λ , c ) = { f ( x ) + 1 c ∑ i = 1 m P ( c g i ( x ) , λ i ) , x ∈ Ω c ( a ) + ∞ , x ∉ Ω c ( a ) L_P(x,\lambda,c)=\left\{\begin{aligned}&f(x)+\frac{1}{c}\sum\limits_{i=1}^mP(cg_i(x),\lambda_i),&&x\in\Omega_c(a)\\&+\infty,&&x\notin\Omega_c(a)\end{aligned}\right. LP​(x,λ,c)=⎩⎪⎪⎨⎪⎪⎧​​f(x)+c1​i=1∑m​P(cgi​(x),λi​),+∞,​​x∈Ωc​(a)x∈/​Ωc​(a)​

其中 P ( s , t ) P(s,t) P(s,t) 在 R a × R + \mathbb R_a\times \mathbb R_+ Ra​×R+​ 对于第一个变量 s ∈ R a s\in\mathbb R_a s∈Ra​ 上连续可微

H 1 : P ( ⋅ , t ) H_1:P(\cdot,t) H1​:P(⋅,t) 对于 s s s 是单调递增，满足：
P ( 0 , t ) = 0 ,    ∀ t ∈ R + ; P ( s , 0 ) ≥ 0 ,    ∀ s ∈ R a ; P ( s , t ) → + ∞ ( t → + ∞ ) ,    f o r    s > 0. P(0,t)=0,\;\forall t\in \mathbb R_+;\\P(s,0)\ge0,\;\forall s\in \mathbb R_a;\\P(s,t)\rightarrow+\infty(t\rightarrow+\infty),\;for\;s>0. P(0,t)=0,∀t∈R+​;P(s,0)≥0,∀s∈Ra​;P(s,t)→+∞(t→+∞),fors>0.

H 2 : H_2: H2​: 存在连续的函数 r ( t ) r(t) r(t)
P ( s , t ) ≥ r ( t ) ,    ∀ ( s , t ) ∈ R a × R + P(s,t)\ge r(t),\;\forall(s,t)\in\mathbb R_a\times\mathbb R_+ P(s,t)≥r(t),∀(s,t)∈Ra​×R+​

H 3 : H_3: H3​: 如果 a = + ∞ a=+\infty a=+∞，那么 P ( s , t ) s → + ∞ ( s → − ∞ ) \frac{P(s,t)}{s}\rightarrow+\infty(s\rightarrow-\infty) sP(s,t)​→+∞(s→−∞) 对于任何 t ∈ R + t\in R_+ t∈R+​

H 4 : P s ′ ( s , t ) ≤ t , ∀ s < 0 H_4:P^\prime_s(s,t)\le t,\forall s<0 H4​:Ps′​(s,t)≤t,∀s<0 并且 P s ′ ( s , t ) → 0 ( s → − ∞ ) P^\prime_s(s,t)\rightarrow0(s\rightarrow-\infty) Ps′​(s,t)→0(s→−∞) 对于任何 t ∈ S ⊂ R + t\in S\subset \mathbb R_+ t∈S⊂R+​

其中 S S S 是一个有界集

1.1 Special case 1: Modified Courant-type augmented Lagrangian function

L P 1 ( x , λ , c ) = f ( x ) + 1 c ∑ i = 1 m P 1 ( c g i ( x ) , λ i ) , L_{P1}(x,\lambda,c)=f(x)+\frac{1} {c}\sum\limits_{i=1}^mP_1(cg_i(x),\lambda_i), LP1​(x,λ,c)=f(x)+c1​i=1∑m​P1​(cgi​(x),λi​),

( a = + ∞ ) (a=+\infty) (a=+∞) 其中 P 1 ( s , t ) = ( m a x 0 , ϕ 1 ( s ) + t ) 2 − t 2 , ( s , t ) ∈ R × R + P_1(s,t)=(max{0,\phi_1(s)+t})^2-t^2,(s,t)\in \mathbb R\times\mathbb R_+ P1​(s,t)=(max0,ϕ1​(s)+t)2−t2,(s,t)∈R×R+​ 函数 ϕ 1 ( ⋅ ) \phi_1(\cdot) ϕ1​(⋅) 满足以下条件：

1. ϕ 1 ( ⋅ ) \phi_1(\cdot) ϕ1​(⋅) 是一个二次连续可微分，并且在 R \mathbb R R 上为凸函数；
2. ϕ 1 ( 0 ) = 0 , ϕ 1 ′ ( 0 ) = 1 \phi_1(0)=0, \phi_1^\prime(0)=1 ϕ1​(0)=0,ϕ1′​(0)=1;
3. lim ⁡ s → − ∞ ϕ 1 ′ ( s ) > 0 \lim_{s\rightarrow-\infty}\phi_1^{\prime}(s)>0 lims→−∞​ϕ1′​(s)>0.

1.2 Special case 2: Essentially quadratic augmented Lagrangian function

L P 2 ( x , λ , c ) = f ( x ) + 1 c ∑ i = 1 m P 2 ( c g i ( x ) , λ i ) , L_{P2}(x,\lambda,c)=f(x)+\frac{1} {c}\sum\limits_{i=1}^mP_2(cg_i(x),\lambda_i), LP2​(x,λ,c)=f(x)+c1​i=1∑m​P2​(cgi​(x),λi​),

( a = + ∞ ) (a=+\infty) (a=+∞) 其中 P 2 ( s , t ) = min ⁡ τ ≥ s { t τ + ϕ 2 ( τ ) } , ( s , t ) ∈ R × R + P_2(s,t)=\min_{\tau\ge s}\{t\tau+\phi_2(\tau)\},(s,t)\in \mathbb R\times\mathbb R_+ P2​(s,t)=minτ≥s​{tτ+ϕ2​(τ)},(s,t)∈R×R+​ 函数 ϕ 2 ( ⋅ ) \phi_2(\cdot) ϕ2​(⋅) 满足以下条件：

1. ϕ 2 ( ⋅ ) \phi_2(\cdot) ϕ2​(⋅) 是一个二次连续可微分，并且在 R \mathbb R R 上为凸函数；
2. ϕ 2 ( 0 ) = 0 , ϕ 2 ′ ( 0 ) = 0 , ϕ 2 ′ ′ > 0 \phi_2(0)=0, \phi_2^\prime(0)=0,\phi_2^{\prime\prime}>0 ϕ2​(0)=0,ϕ2′​(0)=0,ϕ2′′​>0;
3. ϕ 2 ( s ) ∣ s ∣ → + ∞ , ( ∣ s ∣ → + ∞ ) \frac{\phi_2(s)}{|s|}\rightarrow+\infty,(|s|\rightarrow+\infty) ∣s∣ϕ2​(s)​→+∞,(∣s∣→+∞)

1.3 Special case 3: Exponential-type augmented Lagrangian

L P 3 ( x , λ , c ) = f ( x ) + 1 c ∑ i = 1 m P 3 ( c g i ( x ) , λ i ) , L_{P3}(x,\lambda,c)=f(x)+\frac{1} {c}\sum\limits_{i=1}^mP_3(cg_i(x),\lambda_i), LP3​(x,λ,c)=f(x)+c1​i=1∑m​P3​(cgi​(x),λi​),

( a = + ∞ ) (a=+\infty) (a=+∞) 其中 P 3 ( s , t ) = t ϕ 3 ( s ) + ξ ( s ) , ( s , t ) ∈ R × R + P_3(s,t)=t\phi_3(s)+\xi(s),(s,t)\in \mathbb R\times\mathbb R_+ P3​(s,t)=tϕ3​(s)+ξ(s),(s,t)∈R×R+​ 函数 ϕ 3 ( ⋅ ) \phi_3(\cdot) ϕ3​(⋅) 满足以下条件：

1. ϕ 3 ( ⋅ ) \phi_3(\cdot) ϕ3​(⋅) 是一个二次连续可微分，并且在 R \mathbb R R 上为凸函数；
2. ϕ 3 ( 0 ) = 0 , ϕ 3 ′ ( 0 ) = 0 , ϕ 3 ′ ′ > 0 \phi_3(0)=0, \phi_3^\prime(0)=0,\phi_3^{\prime\prime}>0 ϕ3​(0)=0,ϕ3′​(0)=0,ϕ3′′​>0;
3. lim ⁡ s → − ∞ ϕ 3 ( s ) > − ∞ , lim ⁡ s → − ∞ ϕ 3 ′ ( s ) = 0 \lim_{s\rightarrow-\infty}\phi_3(s)>-\infty,\lim_{s\rightarrow-\infty}\phi^{\prime}_3(s)=0 lims→−∞​ϕ3​(s)>−∞,lims→−∞​ϕ3′​(s)=0

并且 ξ ( ⋅ ) \xi(\cdot) ξ(⋅) 满足如下条件：

1. ξ ( ⋅ ) \xi(\cdot) ξ(⋅) 是二次连续可微分并且在 R \mathbb R R 上为凸函数；
2. s ≤ 0 s\le0 s≤0 时 ξ ( s ) = 0 \xi(s)=0 ξ(s)=0， s > 0 s>0 s>0 时 ξ ( s ) > 0 \xi(s)>0 ξ(s)>0
3. ξ ( s ) s → + ∞ , ( s → + ∞ ) \frac{\xi(s)}{s}\rightarrow+\infty,(s\rightarrow+\infty) sξ(s)​→+∞,(s→+∞)

1.4 Special case 4: Modified Carroll barrier-type augmented Lagrangian function

L P 4 ( x , λ , c ) = { f ( x ) + 1 c ∑ i = 1 m P 4 ( c g i ( x ) , λ i ) , x ∈ Ω c ( 1 ) + ∞ , x ∉ Ω c ( 1 ) L_{P4}(x,\lambda,c)=\left\{\begin{aligned}&f(x)+\frac{1}{c}\sum\limits_{i=1}^mP_4(cg_i(x),\lambda_i),&&x\in\Omega_c(1)\\&+\infty,&&x\notin\Omega_c(1)\end{aligned}\right. LP4​(x,λ,c)=⎩⎪⎪⎨⎪⎪⎧​​f(x)+c1​i=1∑m​P4​(cgi​(x),λi​),+∞,​​x∈Ωc​(1)x∈/​Ωc​(1)​

( a = 1 ) (a=1) (a=1) 其中 P 4 ( s , t ) = t ϕ 4 ( s ) , ( s , t ) ∈ R × R + P_4(s,t)=t\phi_4(s),(s,t)\in \mathbb R\times\mathbb R_+ P4​(s,t)=tϕ4​(s),(s,t)∈R×R+​ 函数 ϕ 4 ( ⋅ ) \phi_4(\cdot) ϕ4​(⋅) 满足以下条件：

1. ϕ 4 ( ⋅ ) \phi_4(\cdot) ϕ4​(⋅) 是一个二次连续可微分，并且在 R 1 \mathbb R_1 R1​ 上为凸函数；
2. ϕ 4 ( 0 ) = 0 , ϕ 4 ′ ( 0 ) = 1 , ϕ 4 ( 0 ) ′ ′ > 0 \phi_4(0)=0, \phi_4^\prime(0)=1,\phi_4(0)^{\prime\prime}>0 ϕ4​(0)=0,ϕ4′​(0)=1,ϕ4​(0)′′>0;
3. lim ⁡ s → − ∞ ϕ 4 ( s ) > − ∞ , lim ⁡ s → − ∞ ϕ 4 ′ ( s ) = 0 \lim_{s\rightarrow-\infty}\phi_4(s)>-\infty,\lim_{s\rightarrow-\infty}\phi^{\prime}_4(s)=0 lims→−∞​ϕ4​(s)>−∞,lims→−∞​ϕ4′​(s)=0

2 R-type 增广拉格朗日函数

L R ( x , λ , c ) = { f ( x ) + 1 c ∑ i = 1 m R ( c g i ( x ) , λ i ) , x ∈ Ω c ( a ) + ∞ , x ∉ Ω c ( a ) L_R(x,\lambda,c)=\left\{\begin{aligned}&f(x)+\frac{1}{c}\sum\limits_{i=1}^mR(cg_i(x),\lambda_i),&&x\in\Omega_c(a)\\&+\infty,&&x\notin\Omega_c(a)\end{aligned}\right. LR​(x,λ,c)=⎩⎪⎪⎨⎪⎪⎧​​f(x)+c1​i=1∑m​R(cgi​(x),λi​),+∞,​​x∈Ωc​(a)x∈/​Ωc​(a)​

其中 R ( s , t ) R(s,t) R(s,t) 在 R a × R + \mathbb R_a\times\mathbb R_+ Ra​×R+​ 是连续，并且在 s ∈ R a s\in \mathbb R_a s∈Ra​ 上是连续可微分的。

假定函数 R ( s , t ) R(s,t) R(s,t) 有以下性质：

H 1 ′ : H_1^\prime: H1′​: 和 H 1 H_1 H1​ 相同；

H 2 ′ : H_2^\prime: H2′​: 对于任意给定的 t ∈ R + , R ( s , t ) s → 0 ( s → − ∞ ) t\in \mathbb R_+,\frac{R(s,t)}{s}\rightarrow 0(s\rightarrow-\infty) t∈R+​,sR(s,t)​→0(s→−∞)

H 3 ′ : H_3^\prime: H3′​: 和 H 1 H_1 H1​ 相同；

H 4 ′ H_4^\prime H4′​ 和 H 1 H_1 H1​ 相同。

2.1 Special case 1: Modified Frish barrier augmented Lagrangian function

L R 1 ( x , λ , c ) = { f ( x ) + 1 c ∑ i = 1 m R 1 ( c g i ( x ) , λ i ) , x ∈ Ω c ( 1 ) + ∞ , x ∉ Ω c ( 1 ) L_{R1}(x,\lambda,c)=\left\{\begin{aligned}&f(x)+\frac{1}{c}\sum\limits_{i=1}^mR_1(cg_i(x),\lambda_i),&&x\in\Omega_c(1)\\&+\infty,&&x\notin\Omega_c(1)\end{aligned}\right. LR1​(x,λ,c)=⎩⎪⎪⎨⎪⎪⎧​​f(x)+c1​i=1∑m​R1​(cgi​(x),λi​),+∞,​​x∈Ωc​(1)x∈/​Ωc​(1)​

( a = 1 ) (a=1) (a=1) 其中 R 1 ( s , t ) = t φ ( s ) , ( s , t ) ∈ R × R + R_1(s,t)=t\varphi(s),(s,t)\in \mathbb R\times\mathbb R_+ R1​(s,t)=tφ(s),(s,t)∈R×R+​ 函数 φ ( ⋅ ) \varphi(\cdot) φ(⋅) 满足以下条件：

1. φ ( ⋅ ) \varphi(\cdot) φ(⋅) 是一个二次连续可微分，并且在 R 1 \mathbb R_1 R1​ 上为凸函数；
2. φ ( 0 ) = 0 , φ ′ ( 0 ) = 1 , φ ′ ′ ( 0 ) > 0 \varphi(0)=0, \varphi^\prime(0)=1,\varphi^{\prime\prime}(0)>0 φ(0)=0,φ′(0)=1,φ′′(0)>0;
3. lim ⁡ s → − ∞ φ ( s ) s = 0 , lim ⁡ s → − ∞ φ ′ ( s ) = 0 \lim_{s\rightarrow-\infty}\frac{\varphi(s)}{s}=0,\lim_{s\rightarrow-\infty}\varphi^\prime(s)=0 lims→−∞​sφ(s)​=0,lims→−∞​φ′(s)=0.

3 V-type 增广拉格朗日函数

L p ( x , λ , c ) = { f ( x ) + 1 c ∑ i = 1 m V ( c g i ( x ) , λ i ) , x ∈ Ω c ( a ) + ∞ , x ∉ Ω c ( a ) L_p(x,\lambda,c)=\left\{\begin{aligned}&f(x)+\frac{1}{c}\sum\limits_{i=1}^mV(cg_i(x),\lambda_i),&&x\in\Omega_c(a)\\&+\infty,&&x\notin\Omega_c(a)\end{aligned}\right. Lp​(x,λ,c)=⎩⎪⎪⎨⎪⎪⎧​​f(x)+c1​i=1∑m​V(cgi​(x),λi​),+∞,​​x∈Ωc​(a)x∈/​Ωc​(a)​

其中 V ( s , t ) V(s,t) V(s,t) 在 R a × R + \mathbb R_a\times\mathbb R_+ Ra​×R+​ 是连续，并且在 s ∈ R a s\in \mathbb R_a s∈Ra​ 上是连续可微分的。

假定函数 V ( s , t ) V(s,t) V(s,t) 有以下性质：

H 1 ′ ′ : V ( ⋅ , t ) H_1^{\prime\prime}:V(\cdot,t) H1′′​:V(⋅,t) 是单调递增，并且对于 s 是凸的，满足：
V ( 0 , t ) = 0 ,    ∀ t ∈ R + ; V ( s , t ) ≥ s t ,    ∀ ( s , t ) ∈ R a × R + V(0,t)=0,\;\forall t\in\mathbb R_+;V(s,t)\ge st,\;\forall(s,t)\in\mathbb R_a\times R_+ V(0,t)=0,∀t∈R+​;V(s,t)≥st,∀(s,t)∈Ra​×R+​

H 2 ′ ′ : H_2^{\prime\prime}: H2′′​: 和 H 2 H_2 H2​ 相同；

H 3 ′ ′ : H_3^{\prime\prime}: H3′′​: 如果 a = + ∞ a=+\infty a=+∞ 那么对于任意 t ∈ S ⊂ R + t\in S\subset \mathbb R_+ t∈S⊂R+​ V ( s , t ) s → + ∞ ( s → + ∞ ) \frac{V(s,t)}{s}\rightarrow+\infty(s\rightarrow+\infty) sV(s,t)​→+∞(s→+∞)，其中 S 是 R + \mathbb R_+ R+​ 的任意无界闭集(any closed unbounded set)；

H 4 ′ ′ : H_4^{\prime\prime}: H4′′​: V ′ ( s , t ) > 0 , ∀ t > 0 V^\prime(s,t)>0, \forall t>0 V′(s,t)>0,∀t>0，对于任意 t ∈ S ⊂ R + t\in S\subset \mathbb R_+ t∈S⊂R+​ V s ′ ( s , t ) → 0 ( s → − ∞ ) V^\prime_s(s,t)\rightarrow0(s\rightarrow-\infty) Vs′​(s,t)→0(s→−∞)，其中 S 是 R + \mathbb R_+ R+​ 的任意无界集。