Optimality condition analysis of the second-order cone coupled constrained variational inequalities

WANG Bin; WANG Li; SUN Juhe; SUN Yining; YUAN Yanhong

doi:10.3969/j.issn.2095-1248.2023.04.008

Journal of Shenyang Aerospace University >

2023 , Vol. 40 >Issue 4: 60 - 66

DOI: https://doi.org/10.3969/j.issn.2095-1248.2023.04.008

Fundamental Science and Engineering

Optimality condition analysis of the second-order cone coupled constrained variational inequalities

WANG Bin ^,¹ ,
WANG Li ^,¹ ,
SUN Juhe ¹ ,
SUN Yining ¹ ,
YUAN Yanhong ²

Expand

^1. College of Sciences，Shenyang Aerospace University，Shenyang 110136，China
^2. College of Economics and Management，Taiyuan University of Technology，Taiyuan 030024，China

Received date: 2023-03-31

Online published: 2023-11-09

Fold

Abstract

In order to study the optimality conditions of the second order cone coupled constrained variational inequalities， after equivalent transformation of the original problem， a minimax problem model was established by using the generalized saddle point problem， which was equivalent to a system of variational inequalities problem. The karush-kuhn-tucker （abbreviated as KKT） conditions of this system of variational inequalities were obtained. The Lagrange duality theory was applied to obtain the first-order necessity condition for the second-order cone coupled constrained variational inequalities. Based on the tangent cone of the constrained sets， the formula of the second-order tangent set and the duality theory， the second-order sufficiency condition of the second-order cone coupled constrained variational inequalities was derived. The analysis of the optimality condition for the second-order cone coupled constrained variational inequalities provides theoretical support for the study of the existence and convergence of the solution to the second-order cone coupled constrained variational inequalities.

Key words： second-order cone coupled constrained; variational inequality; minimax problem; saddle point; Lagrange duality theory; second order tangent set

Cite this article

WANG Bin , WANG Li , SUN Juhe , SUN Yining , YUAN Yanhong . Optimality condition analysis of the second-order cone coupled constrained variational inequalities[J]. Journal of Shenyang Aerospace University, 2023 , 40(4) : 60 -66 . DOI: 10.3969/j.issn.2095-1248.2023.04.008

本文研究二阶锥双约束变分不等式问题，即求解

x * ∈ Ω

，使得

F x *, y - x * ≥ 0, ∀ y ∈ C

（1）

其中

C = y ∈ Ω | - g x *, y ∈ K m

。

式中：

为单调的向量值映射；

为连续可微映射；

< ⋅, ⋅ >

为欧氏内积；

K = K m 1 × K m 2 × ⋯ × K m p

，且

m 1 + m 2 + ⋯ m p = m

，

m i ≥ 1

，

i = 1,2, ⋯, p

，每个

K m i

都是

m i

维的二阶锥，集合

Ω ⊆ R n

为一闭凸集。双约束条件是形如

- g x *, y ∈ K m

的约束，该条件与经典问题的不同主要在于它将问题的参量与其自身变量联系在一起，这给双约束优化问题的研究带来了难度和挑战。

作为数学规划领域一个重要的分支，借助变分不等式问题及其特例互补问题可以构造出多种数学模型和均衡规划模型，因此对于其数值解的研究具有一定的理论价值和实际意义。2000年，Antipin^［1］首先提出了具有双约束条件的变分不等式问题，它在许多数学问题中都有应用，如：带有成本预算的经济均衡模型^［2］、双人博弈问题^［3］、双层规划及层次规划^［4］等。Antipin^［5］研究了双约束的均衡规划问题，讨论了对称和反对称函数的性质，提出了微分反馈控制梯度法，并证明了该方法的全局收敛性。基于变分不等式理论的广泛应用，经典变分不等式和广义变分不等式都已被深入研究，Facchinei等^［6］的专著囊括了有限维空间中互补问题与变分不等式几乎所有的基础成果，为该领域的进一步研究提供了理论支持。

最优性条件是最优化问题的目标函数和约束函数在最优点所满足的必要条件和充分条件。最优性条件在优化算法的终止判定以及优化理论的证明中有着重要作用。在最优化理论中，Robinson约束规范条件是最著名的约束规范条件之一，在进行优化问题的最优性条件以及稳定性分析的研究中有着重要作用，相关介绍可参阅文献［7-9］。学者Bonnans等^［10-11］对非线性二阶锥优化问题所做的一阶必要性、二阶充分性条件、约束非退化条件等内容的描述与分析，对本文相关结论的推导有很大帮助。张立卫^［12］全面介绍了非线性锥约束优化的最优性理论，其中第3、4章详细论述了一些具体的约束优化问题的最优性理论，还介绍了不同类型的优化问题的Robinson约束规范、约束非退化条件、最优解的一阶必要性条件、二阶充分性条件等内容。

本文提出了双约束二阶锥变分不等式问题，并对该问题进行最优性条件分析。通过对原始问题进行等价转换后，借助所得出的广义鞍点问题，建立极小极大问题模型，将其转换为变分不等式组问题，得到该变分不等式组对应的KKT条件，应用Lagrange对偶理论得到所研究双约束二阶锥变分不等式问题的一阶必要性条件。基于约束集合的切锥、二阶切集公式以及对偶理论，推导出双约束二阶锥变分不等式问题的二阶充分性条件，从而实现双约束二阶锥变分不等式问题的解的最优性条件的研究。

1 预备知识

为了求解双约束二阶锥变分不等式问题的一阶最优性条件，首先介绍推导过程中所用到的概念与相关性质。

定义1 ^［1］称向量值函数

→

在

上是对称的，若有式（2）成立

g x, y = g y, x, ∀ x, y ∈ Ω

（2）

对称向量值函数的具体应用可以体现在带有成本限制的经济均衡模型中，如：

g v, w = v, w

或者

g v, w = A v, w

，式中

: A

为对称矩阵；

v 、 w

为

n

维列向量。

性质1 ^［1］向量值对称函数

→

关于变量

x

和

y

的梯度在集合

Ω × Ω

上的值相等，即有式（3）成立

∇ y Τ g x, x = ∇ x Τ g x, x, ∀ x ∈ Ω

（3）

证明：对式（2）中等号左侧关于第二元

y

求导，等号右侧关于第二元

x

求导可得

∇ y Τ g x, y = ∇ x Τ g y, x, ∀ x, y ∈ Ω

在上式中，令

y = x

可得等号左右两侧的

m × n

矩阵相等，即得式（3），证毕。

性质2 ^［1］算子

2 ∇ y Τ g x, y | x = y

与对称函数

g x, y | x = y

在集合

Ω × Ω

上的梯度是一致的，即有下述关系成立

2 ∇ y Τ g x, y x = y = ∇ Τ g x, x, ∀ x, y ∈ Ω

（4）

证明：由可微的定义对

g x, y

作展开，即

g x + h, y + k = g x, y + ∇ x Τ g x, y h + ∇ y Τ g x, y k + ω x, y, h, k

当

h 2 + k 2 → 0

时，有

ω x, y, h, k / h 2 + k 2 1 / 2 → 0

。

在上式中，令

y = x

，

h = k

，结合性质1及其证明可得下述展开形式

g x + h, x + h = g x, x + 2 ∇ y Τ g x, x h + ω x, h

当

h → 0

时有

ω x, h / h → 0

。

该式可以看作是对

g x, y

作Taylor展开的一种特殊情形，式中

g x, x

可视为

g x, y

在

y = x (x, y ∈ Ω)

时的函数，其梯度为

∇ Τ g x, x

，即式（4）成立，证毕。

定义2 若

K n ∈ R n n ≥ 1

满足

K n = x 0; x ¯

x 0 ∈ R, x ¯ ∈ R n - 1, x 0 ≥ x ¯

则称

K n

为

n

维的二阶锥，又称冰激凌锥。它是自对偶的闭凸锥，且其内点集int

K n

与边界点集bd

K n

表述如下

i n t K n = x = x 0; x ¯ ∈ R × R n - 1 : x 0 > x ¯,

b d K n = x = x 0; x ¯ ∈ R × R n - 1 : x 0 = x ¯

。

可以发现，当

n = 1

时，

K n

退化为非负实数集

R +

，因此Antipin^［1］提出的具有双约束条件的变分不等式问题是本文的双约束二阶锥变分不等式问题（1）的特殊情形。

为了研究双约束二阶锥变分不等式的二阶必要性条件，下面给出二阶锥的切锥与二阶切集公式。

引理1 ^［8］

二阶锥

K n

上任意一点

x = (x 0, x ¯)

处的切锥为

（5）

K n

上任意一点

x

处沿方向

d ∈ T 𝒦 n x

的二阶切集为

（6）

定义3 ^［9］设

Κ X ⊂ X

与

Κ Y ⊂ Y

是任意非空集合，与函数

L : Κ X × Κ Y → R -

相联系的原始与对偶问题定义为

P L m i n x ∈ Κ X s u p y ∈ Κ Y L x, y, D L m a x y ∈ Κ Y i n f x ∈ Κ X L x, y

称

L

为上述极小极大对偶性Lagrange函数，称

x ¯, y ¯ ∈ Κ X × Κ Y

是函数

L x, y

的鞍点。若

L x ¯, y ¯ ∈ R

且

∀ x, y ∈ Κ X × Κ Y

L x ¯, y ≤ L x ¯, y ¯ ≤ L x, y ¯

其中：

R - = R ⋃ + ∞ ⋃ - ∞

。

定义4 ^［13］集合

C ⊂ X

的指示函数记为

I C

，定义为

I C = 0, x ∈ C ∞, x ∉ C

并约定

I R n = 0

，

I ∅ = ∞

。

2 双约束二阶锥变分不等式的等价转换

本文所研究的双约束二阶锥变分不等式问题（1）对应的最优化问题

m i n f y s . t . - g x *, y ∈ K m y ∈ C

（7）

式中：函数

f y = F x *, y - x * ≥ 0

，

x *

为上述优化问题的最优解。

优化问题（7）对应的Lagrange函数为

L x *, y, λ = F x *, y - x * + λ, g x *, y,

∀ y ∈ C, λ ∈ Κ m

（8）

式中：

x *

是原始问题的最优解；

y 、 λ

分别为原始变量与对偶变量。由于

x *

是

f y

在集合Ω上的最小值点，在一定正则条件下（如Slater条件成立），点对

x *, λ *

是Lagrange函数

L x *, y, λ

的鞍点，根据鞍点定义3可知，有以下鞍点不等式成立

L x *, x *, λ ≤ L x *, x *, λ * ≤ L x *, y, λ *

，

∀ y ∈ C, λ ∈ Κ m

（9）

定理1 双约束二阶锥变分不等式问题（1）等价转化为变分不等式问题（10）

∇ y L x *, z * - ∇ λ L x *, z *, z - z * ≥ 0

，（10）

式中：

z = y λ

及

G z = - g x *, y λ

证明：原问题（1）可以视作线性函数

f y = F x *, y - x * ≥ 0

在可行集

C = y ∈ Ω | - g x *, y ∈ K m

上的极小化问题，

x *

作为极小化问题（7）的最小值点，点对

x *, λ *

是Lagrange函数

L x *, y, λ

的鞍点，根据鞍点定义4可知，其满足不等式

F x *, x * - x * + λ, g x *, x * ≤ F x *, x * - x * + λ, g x *, x * ≤ F x *, x * - y + λ, g x *, y *

（11）

上述不等式说明

x *, λ *

满足下面关系

x * ∈ a r g m i n F x *, y - x * + λ *, g x *, y,

λ * ∈ a r g m a x λ, g x *, x * | λ ∈ Κ m

（12）

对于鞍点不等式（11），运用极小极大问题模型^［14］，可做如下推导

考虑极小极大问题

m i n y ∈ Ω m a x λ ∈ 𝒦 m L x *, y, λ

（13）

x * λ * ∈ C × K m

是Lagrange函数

L x *, y, λ

的鞍点的必要条件为

∇ y Τ L x *, y *, λ * y - x * ≥ 0 - ∇ λ Τ L x *, y *, λ * λ - λ * ≥ 0

（14）

即

F x * + ∇ y g x *, x * λ *, y - x * ≥ 0, ∀ y ∈ C,

- g x *, x *, λ - λ * ≥ 0, ∀ λ ∈ Κ m

（15）

根据对称函数的性质2及向量值函数

g x, x

的各分量的凸性，式（15）中第一个表达式中关于函数

g x, x

的运算可以有下面的形式

λ *, ∇ y Τ g x *, x * y - x * = 12 λ *, ∇ Τ g x *, x * y - x *

则双约束二阶锥变分不等式（1）可等价转化为鞍点问题（16）

F x * + 12 ∇ g x *, x * λ *, y - x * ≥ 0, ∀ y ∈ C

，

- g x *, x *, λ - λ * ≥ 0, ∀ λ ∈ Κ m

（16）

因此，问题（16）可以表述为下面的形式

F x * + 12 ∇ g x *, x * λ * - g x *, x * y λ - x * λ * ≥ 0,

∀ y λ ∈ C × Κ m

（17）

若令

Y = C × Κ m

，

，其中参量

z = y λ

，约束条件为

G z = - g x *, y λ

，证毕。

3 一阶必要性条件

本节研究问题（10）对应的优化问题（18）的Lagrange对偶理论，由此分析出其最优解同时也包括原变分不等式的解需要满足的一阶必要条件，并对相关性质加以研究。

双约束二阶锥变分不等式问题（10）可以看作下述优化问题的等价形式

（P）

m i n f z : s . t . G z ∈ K 2 m, z ∈ Y

（18）

其中函数

f z = ∇ y L x *, z * - ∇ λ L x *, z * z - z * ≥ 0

且

是一连续可微函数，约束条件中的

是一连续可微的向量值函数，

K 2 m ⊂

为一闭凸锥。

优化问题（18）对应的Lagrange函数为

L z, p = f z - p Τ G z

（19）

因此，问题（18）的Lagrange对偶问题为

（D）

m a x p ∈ 𝒦 2 m m i n z ∈ Y L z, p

（20）

由于最优值

v a l P ≥ v a l D

，若对于点对

z *, p * ∈ Y × Κ 2 m

，使得原始与对偶目标函数值相等，即

f z * + I G z * = m i n z ∈ Y L z, p *

式中

: I

为指示函数，则有

v a l P = v a l D

。进一步若其公共值是有限的，则

z * ∈ Y

与

p * ∈ K 2 m

分别为最优化问题（18）与对偶问题（20）的最优解。由鞍点定理可知，原始对偶问题的解

z, p

可由下述系统刻画

L z, p = m i n z' ∈ Y L z', p, p, G z = 0, p ∈ K 2 m, G z ∈ K 2 m

（21）

总结上述关系，借助Lagrange对偶理论^［9］，可以得到下述结论。

定理 2 令

v a l P

与

v a l D

分别表示原始问题（18）与对偶问题（20）的最优值，则有

v a l P ≥ v a l D

。进一步可推出，

v a l P = v a l D

，且该公共值是有限的，则

z * ∈ Y

与

p * ∈ K 2 m

分别为原始问题

P

与对偶问题

D

的最优解的充分必要条件是式（21）成立。

称点对

z *, p *

为问题（18）的KKT点，若

z *, p *

满足KKT条件（22）

∇ z L z *, p * = 0 p *, G z * = 0 p * ∈ K 2 m, G z * ∈ K 2 m

（22）

上述系统即为一般情形的一阶必要性条件，是从代数角度推导出的，K-T乘子

p *

也称为Lagrange乘子，

z *

为问题（18）的局部最优解，可将其进一步总结为下述定理。

定理3 设

z *

是双约束二阶锥优化问题（18）的局部最优解，且满足Robinson约束规范

∇ Τ G z * R n + m + Τ K 2 m G z * = R 2 m

（23）

则在

z *

处的Lagrange乘子集合

Λ z *

是非空紧致凸集合。

证明：设

z *, p *

为问题（18）相应的Lagrange对偶问题的最优解对，其中

p *

为Lagrange乘子，则

z *, p *

满足KKT条件（22）。由于能够保证（22）的Lagrange乘子集合是紧致集的充分必要条件正是Robinson约束规范条件，即

（24）

由文献［15］知，式（24）的等价表达为

显示原图|下载原图ZIP|生成PPT

证毕。

假设

z *

是双约束二阶锥优化问题（18）的稳定点，即点对

z *, p *

满足KKT条件（22）。若在

z *

处有下述约束非退化条件成立

显示原图|下载原图ZIP|生成PPT

式中：

l i n Τ K 2 m G z *

是二阶锥

K 2 m

在

G z *

的切锥的线性化空间。则可得出约束非退化条件与Lagrange乘子的唯一性关系。

定理4 假设

z *

是双约束二阶锥优化问题（18）的一个稳定点，若

z *

是约束非退化的，则存在唯一的Lagrange乘子

p *

；反之，若

z *, p *

满足严格互补条件

G z * + p * ∈ i n t K 2 m

，且

p *

是唯一对应

z *

的Lagrange乘子，则

z *

是非退化的最优解。

4 二阶充分性条件

本节讨论双约束二阶锥变分不等式问题（18）的二阶充分性条件。设映射

f z

与

G z

是二阶连续可微的。下述定理给出了问题（18）在稳定点

z *

处的临界锥的定义。

定理5 设

z *

是问题（18）的一个稳定点，Lagrange乘子

p ∈ Λ z *

。给定方向

，借助引理1中的公式，可推出如式（25）的临界锥的结论

C z * = h ∈ R n + m ∇ Τ G z * h ∈ T K 2 m G z *, p = 0 ∇ Τ G z * h = 0, ∇ Τ G z * h = 0 ∇ Τ G z * h ∈ R + p 0; - p ¯ 0, p ∈ b d K 2 m \ 0, G z * = 0 ∇ Τ G z * h, p = 0, p, G z * ∈ b d K 2 m \ 0

（25）

定理6 设

z *

是问题（18）的一个稳定点，且满足Robinson约束规范条件（23），则在

z *

处二阶增长条件成立当且仅当式（26）的二阶条件成立

s u p p ∈ Λ z * ∇ z z 2 L z *, p h, h + H z *, p h, h > 0, ∀ h ∈ C z * \ 0,

（26）

式中：

H z *, p = ∑ i = 1 I H i z *, p, i = 1, ⋯, I

，

H i z *, p = - p 0 i G 0 i z * ∇ Τ G i z * 1 0 Τ 0 - I 2 m - 1 ∇ G i z *, ∇ G i z * ∈ b d K 2 m \ 0 0, 其他 情形

证明：假设定理条件成立，则由文献［9］可知二阶锥是二阶正则的，在

z *

处二阶增长条件成立当且仅当下述条件成立

s u p p ∈ Λ z * h Τ ∇ z z 2 L z *, p h - σ - p; ϒ 2 > 0, ∀ h ∈ C z * \ 0,

（27）

其中

ϒ 2 : = Τ 𝒦 2 m 2 G z *, ∇ Τ G z * h

表示在

G z *

处沿方向

∇ Τ G z * h

的二阶切集，

σ ⋅, ϒ 2

为集合

ϒ 2

的支撑函数。

该定理只需证明式（26）是式（27）的具体表述形式即可。考虑在

G z *

处沿着

∇ Τ G z * h

方向的二阶切集形式如下：

ϒ 2 = Τ K 2 m 2 G z *, ∇ Τ G z * h = R 2 m, ∇ Τ G z * h ∈ i n t Τ K 2 m G z * Τ K 2 m ∇ Τ G z * h G z * = 0 w = w 0; w ¯ | w ¯ Τ G z * ¯ - w 0 G z * 0 ≤ ∇ Τ G z * h 02 - ∇ Τ G z * h ¯ 2, 其他 情形

（28）

由于二阶锥是卡式积运算，故可以计算支撑函数

σ - p, ϒ 2

如下。

（1）由

h ∈ C z *

知，

∇ Τ G z * h ∈ T K 2 m G z *

，又由

- p * ∈ N K 2 m G z *

且

G z * ∈ K 2 m

，由二阶切集的定义知，

σ - p, ϒ 2 ≤ 0

。

若

0 ∈ ϒ 2

，则

σ - p; ϒ 2 = 0

。由式（28）可知，若

∇ Τ G z * h ∈ i n t T K 2 m G z *

或者

G z * = 0

或者

∇ Τ G z * h = 0

时，都有

0 ∈ ϒ 2

。

（2）若

∇ Τ G z * h, G z * ∈ b d K 2 m \ 0

，记满足该情形的指标集合为

I

，由式（28）可得

σ - p, ϒ 2 = s u p w ∈ R 2 m - w 0 p 0 + w ¯ Τ p ¯ | w ¯ Τ G z * ¯ - w 0 G z * 0 ≤ ∇ Τ G z * h 02 - ∇ Τ G z * h ¯ 2

由KKT条件

p, G z * = 0

知

p ¯ = - p 0 / G z * 0 G z * ¯

，从而可推出

- w 0 p 0 + w ¯ Τ p ¯ = p 0 / G z * 0 w ¯ Τ G z * ¯ - w 0 G z * 0

故在此情形下，有

σ - p; ϒ 2 = p 0 G z * 0 ∇ Τ G z * h 02 - ∇ Τ G z * h ¯ 2

综合上述情况，可推出

σ - p; ϒ 2 = ∑ i ∈ I p 0 i G i z * 0 ∇ Τ G i z * h 02 - ∇ Τ G i z * h ¯ 2

证毕。

5 结论

Antipin^［1］所研究的双约束变分不等式是双约束二阶锥变分不等式的特殊情形，本文讨论了双约束二阶锥变分不等式问题的一阶必要性条件和二阶充分性条件。首先对原始双约束二阶锥变分不等式问题进行极小化问题转化后得出了广义鞍点不等式，借助极小极大问题模型，可以将其等价于一个变分不等式组。进一步对所得出的等价变分不等式组分析，应用Lagrange对偶理论得出其有解的一阶必要性条件。然后借助约束集合的二阶切集与对偶理论，得到双约束二阶锥变分不等式问题的二阶充分性条件。双约束二阶锥变分不等式问题的最优性条件的分析对该问题的解的存在性及收敛性的研究给出了理论支持。

References

Publishing order | Descend order by publishing year | Descend order by cited within

1	Antipin A S.Solution methods for variational inequalities with coupled constraints ［J］.Computational Mathematics and Mathematical Physics，2000，40（9）：1239-1254.

2	Polterovich V M.Economic Equilirium and Economic Mechanism ［M］.Moscow：Nauka，1990.

3	Garcia C B， Zangwill W I.Pathways to Solutions，Fixed Points，and Equilibria ［M］.New York：Prentice Hall，1981.

4	Antipin A S.The convergence of proximal methods to fixed points of extremal mappings and estimates of their rate of convergence ［J］.Zh.Vychisl.Mat.Mat.Fiz.，1995，35（5）：688-704.

5	Antipin A S.Differential equations for equilibrium problems with coupled constraints ［J］.Nonlinear Analysis：Theory，Methods and Applications，2001，47（3）：1833-1844.

6	Facchinei F， Pang J S.Finite-dimensional Variational Inequalities and Complementarity Problems ［M］.New York：Springer Verlag，2003.

7	Robinson S M.First order conditions for general nonlinear optimization ［J］.SIAM Journal on Applied Mathematics，1976（30）：597-607.

8	Robinson S M.Strongly regular generalized equations ［J］.Mathematics of Operations Research，1980，5（1）：43-62.

9	Robinson S M.Local structure of feasible sets in nonlinear programming，part III：stability and sensitivity ［J］.Mathematical Programming Study，1987（30）：45-66.

10	Robinson S M.Local structure of feasible sets in nonlinear programming，part II：nondegeneracy ［J］.Mathematical Programming Study，1984，（22）： 217-230.

11	Bonnans J F， Ramírez H C.Perturbation analysis of second-order cone programming problems ［J］.Mathematical Programming，2005，104（2-3）：205-227.

12	张立卫.锥约束优化：最优性理论与增广Lagrange方法［M］.北京：科学出版社，2010.

13	张立卫，吴佳，张艺.变分分析与优化［M］.北京：科学出版社，2013.

14	侯剑，张立卫.广义纳什均衡问题求解的极小极大方法［J］.大连理工大学学报，2013，53（6）：924-929.

15	Bonnans J F， Shapiro A.Perturbation Analysis of Optimization Problems ［M］.New York：Springer，2000.

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article

1 预备知识

2 双约束二阶锥变分不等式的等价转换

3 一阶必要性条件

4 二阶充分性条件

5 结论

References