非对称锥优化问题KKT函数的B次微分非奇异性与非退化性条件

赵金阳,王诗云

(沈阳航空航天大学 理学院，沈阳 110136)

考虑下面的一类非对称锥

K={(s,s0)∈Rn×R:eTs≤ks0,0≤s≤s0e}

其中k>0,e表示所有元素为1的向量。在以前的工作中，已经得到了K上投影算子的闭形式[1]、变分几何性质[2]以及投影算子的B次微分[3]。本文考虑如下的优化问题:

minf(x)

G(x)∈K.

(1)

其中函数f:Rm→R和G:Rm→Rn×R是二次连续可微的。为了方便起见，令

K=:={(s,s0)∈Rn×R:eTs=ks0,0≤s≤s0e}.

本文研究KKT函数的强二阶充分条件、约束非退化性、B次微分非奇点与KKT点强正则性之间的关系。

K上的投影算子有着广泛的应用，可以参考。其中Liu等[1]得到了该投影算子的闭形式。本文用∏K(·,·)来表示K上的投影算子。

最优解的灵敏度和稳定性分析是优化问题中最重要的研究领域之一，它与最优条件和增广拉格朗日方法有着密切的联系。对于多面体的情况，许多学者取得了优秀的研究成果，例如， Rockafellar[11]，Kojima[12]，Robinson[13]，latte等[14]，Bonnans等[15]。然而，这些成果并没有建立起最优解与KKT系统之间的联系。Sun[16]和Chan[17]在研究非线性半正定的规划问题时，研究了KKT函数的强二阶充分条件、约束不变性、B次微分非奇异性与KKT点强正则性之间的关系。此后出现了许多类似的结果:二阶锥的线性规划情形可参考文献[18]；一般对称锥的线性规划情形可参考文献[21]；非对称锥的线性规划情形可参考文献[22]。

基于在K上的投影算子的广泛应用以及灵敏度分析在优化问题中的重要性，本文侧重建立最优化问题(1)的强二阶充分条件、约束不变性、KKT函数的B次微分非奇异性和局部最优解的强正则性的联系。

1 符号说明和预备知识

B={z∈Rn:0≤z≤e,eTz≤k},

(2)

α:={i∈[1:n]:xi≤σ},

β:=[1:n](α∪β)

(3)

(4)

其中σ是(x,x0)的参数，它的值可参照文献1中，命题2.2和算法3.1。

(5)

其中i∈[1:n],

(6)

定理2[2]集合K的对偶锥和极锥可分别计算为

(7)

设π是在[1:n]上的一对一映射，而且xπ(i)≤xπ(i+1)，i∈[1:n-1].令

I=(x)={i∈[1:n]:xi=(xπ(⎣k」+1))-},

J=(x)={i∈[1:n]:xi=(xπ(n-⎣k」))+},

I<(x)={i∈[1:n]:xi<(xπ(⎣k」+1))-},

J<(x)={i∈[1:n]:xi<(xπ(n-⎣k」))+},

I>(x)={i∈[1:n]:xi>(xπ(⎣k」+1))-},

J>(x)={i∈[1:n]:xi>(xπ(n-⎣k」))+}.

则

(c)否则

(8)

(c)否则

(9)

(b)如果(x,x0)∈bd(Ko){(0,0)},则max{xTz:z∈B}+x0=0且

∑i∈J=(x)di≤(k-|J>(x)|)d0当xπ(n-k)≤0;

(10)

∑i∈J=(x)di=(k-|J>(x)|)d0当xπ(n-k)>0}.

(c)如果(x,x0)∈int(Ko),则C((x,x0),K)={(0,0)};

(d)否则，C((x,x0),K)计算如下

C((x,x0),K)=

(11)

(a)如果(x,x0)∈K,则aff(C((x,x0),K))=Rn×R;

(b)如果(x,x0)∈bd(Ko){(0,0)},则aff(C((x,x0),K))为

(i)当xπ(n-k)≤0,

aff(C((x,x0),K))=

{(d,d0)∈Rn×R:dJ>(x)=d0e;dJ<(x)=0};

(ii)当xπ(n-k)>0,

aff(C((x,x0),K))=

{(d,d0)∈Rn×R:dJ>(x)=d0e;dJ<(x)=0;

(c)如果(x,x0)∈int(Ko),则aff(C((x,x0),K))={(0,0)};

(d)否则，

aff(C((x,x0),K))=

(12)

2 问题(1)的临界锥

这一节，考虑问题(1)的KKT点。令x∈Rm是问题(1)的可行点，则拉格朗日函数为

L(x,Λ)=f(x)-〈G(x),Λ〉

(13)

其中Λ∈Rn×R是拉格朗日乘子，为讨论方便，G(x)记为

G(x)=(g(x),g0(x)),g(x)=(g1(x),…,gn(x))T,

并且Λ记为

Λ=(λ,λ0),λ=(λ1,…,λn)T.

(14)

则

K*

(15)

及

(16)

考虑式(16)，根据定理1，可得：

(17)

结合式(17)和式(18)，Ω、Δ和Γ可记为

与α≠,α=,γ≠,γ=的定义与式(4)类似，我们定义Ω≠,Ω=,Γ≠和Γ=:

(20)

根据式(14)有

这意味着

相比式(20)，只需要证明这一点

(21)

(22)

当d0>0

}.

这意味着

(23)

和

(24)

根据式(23)有:

和

(25)

(26)

和

(27)

(28)

和

(29)

通过式(27)和式(28)有

≥-σ*(∑i∈Ω≠di+∑i∈Γ≠(di-d0))+∑i∈Ω=di+∑i∈Γ=di+∑i∈Δdi-(k-|Γ≠|)d0)

=-σ*(eTd-|Γ≠|)d0-(k-|Γ≠|)d0)

=-σ*(eTd-kd0)

=σ*(kd0-eTd)

≥0,

这表明

dΓ≠=d0e,dΩ≠=0,dΩ=≥0,dΩ=≤d0e}.

3 强二阶条件,非退化性约束和B次微分的非奇异性

本节讨论问题(1)的二阶条件，约束非退化性条件和KKT函数的B次微分的非奇异性。为此定义

(30)

(31)

(32)

考虑定理4、定理5和式(21)，非退化约束强于严格约束规范。

(33)

(34)

如果t足够大，再次运用定理5和式(20)有

(35)

因为K是多面体，Sigma项等于0，因此问题(1)的二阶条件可以刻画为如下定理。

(36)

接下来将讨论B次微分非奇异性与约束非退化性之间的关系。定义KKT函数为

然后，这种情况(14)等价于

(37)

或者等价于下面的广义方程

(38)

有(a)⟹(b)⟹(c)成立

PΔΩΓ表明一个排列有

(39)

(40)

(41)

(42)

(43)

(44)

根据式(42)有

(45)

(46)

令eQ3×(44) -(43)，有

(47)

这意味着

(48)

现在，把式(46)和式(48)代入式(44)有

(49)

结合式(42)和式(48)，有

(50)

根据式(40)中第一个和第二个等式，结合W的对称性有W,I-W为投影的广义雅可比矩阵，且

(51)

(52)

“(b)⟹(c)”.同理[16, 命题3.2].

(53)

(54)

(55)

(56)

4 结论

本文给出了KKT系统的强二阶充分条件、非退化约束性、B次微分非奇性与KKT点的强正则性之间的联系。在以后的工作中将研究增广拉格朗日方法。