半定锥约束变分不等式的二阶充分性条件

Second-Order Sufficient Conditions for Semi-Definite Constrained Variational Inequalities

摘要: 半定锥约束变分不等式问题是目前研究热门话题——锥约束变分不等式问题的其中一部分，在优化理论、经济学和工程应用中具有重要意义。在本文中，我们给出了半定锥约束变分不等式问题的二阶充分性条件。我们首先回顾了变分不等式的基本理论概念及其在半定锥约束下的具体形式，然后通过构造相应的拉格朗日函数，将问题的解与二阶充分性条件关联起来，最后我们给出了相关定理的具体内容及其证明，确保在给定约束条件下解的存在性与最优性。

Abstract: The semi-definite cone-constrained variational inequality problem is currently a hot topic of research and is a part of the broader cone-constrained variational inequality issues, which hold significant importance in optimization theory, economics, and engineering applications. In this paper, we present the second-order sufficient conditions for the semi-definite cone-constrained variational inequality problem. We first review the fundamental theoretical concepts of variational inequalities and their specific forms under semi-definite cone constraints. Then, by constructing the corresponding Lagrangian function, we establish a connection between the solutions of the problem and the second-order sufficient conditions. Finally, we provide the specific content and proof of the relevant theorems to ensure the existence and optimality of the solutions under the given constraints.

1. 引言

变分不等式(Variational Inequalities, VI)是一类重要的数学问题，自20世纪60年代起，Lions、Browder、Stampacchia、KyFan、Lemke、Cottle和Dantzing等人提出并创立变分不等式问题及其相关基本理论，此后经过许多数学家所进行的杰出工作，使变分不等式问题的相关理论取得了重要发展，并广泛应用于博弈论、金融学和力学等许多领域。随着半定编程的发展，研究者们开始关注涉及半定约束的变分不等式问题，根据中国运筹学会编著[1]一文，上个世纪九十年代，二阶锥规划和半定规划成为国际优化领域的主要研究热点之一。这表明了半定锥约束变分不等式问题在那个时期开始受到广泛关注。进一步地，[2]一文详细介绍了半定规划的发展与研究现状、基本理论、相关算法以及变分不等式问题的相关知识与投影类算法。文章还提到，在半定规划问题满足严格可行的约束条件下，利用得到的KKT条件，将求解半定规划问题等价地转化为求解变分不等式问题。这说明了半定锥约束变分不等式问题的研究不仅涉及理论基础，还包括具体的算法实现。这些研究内容进一步丰富了半定锥约束变分不等式问题的算法研究领域。综上所述，半定锥约束变分不等式问题的发展历程可以追溯到上个世纪九十年代，并且在随后的研究中，不仅涉及了理论基础的探讨，还包括了多种算法的开发和应用。这些研究为解决实际问题提供了重要的理论和技术支持。

本文旨在研究半定锥约束变分不等式问题的二阶充分性条件，这是因为在解决这类问题时，我们常常需要考虑解的性质，尤其是在最优性条件的研究中。二阶充分性条件为我们提供了一种更为严格的解的性质判定方式，尤其是在存在多重解的情形下。二阶充分性条件能够有效地帮助我们筛选处真正的最优解。因此，本文旨在研究半定锥约束变分不等式问题的二阶充分性条件具有重要的理论意义和应用价值。

2. 预备知识

2.1. 半定锥约束变分不等式问题

用$S^p$ 表示$p\times p$ 阶的实对称矩阵空间，在$S^p$ 中定义内积$\langle A,B\rangle =Tr\left(AB\right),\forall A,B\in S^p$ ，此内积引导的范数即Frobenius范数$\Vert A\Vert ={\left({\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^n{a}_{ij}^2}}\right)}^{1/2}$ 。用$S_{+}^p$ 表示$p\times p$ 阶的对称半正定矩阵构成的锥，记$S_{-}^p$ 表示$p\times p$ 阶的对称半负定矩阵构成的锥，可以验证：$S_{-}^p=-S_{+}^p$ 。

非线性半定规划问题：$\underset{x\in Q}{\min }f\left(x\right)$ ，$\text{s}\text{.t}.G\left(x\right)\in S_{+}^p$ ，其中$f:R^n\to R$ 是实值函数，$G:R^n\to S^p$ 是一矩阵值函数，$Q\in R^n$ 是一闭凸集。

基于上述描述，我们可定义SDCCVI问题。

定义2.1 半定锥约束变分不等式问题(SDCCVIP)：给定一个映射$F:R^n\to R^n$ ，对于给定的子集$C$ 与半定锥$S_{+}^p$ ，要找到一点$x\in C$ ，使得对$\forall y\in C$ ，满足$\langle F\left(x\right),y-x\rangle \ge 0$ ，其中$C=\left\{x\in R^n|G\left(x\right)\in S_{+}^P\right\}$ 。

2.2. 切锥与二阶切锥

定义2.2 本文用$T_{S_{+}^p}\left(x^{*}\right)=\{\begin{array}{ll}{S}^p,\hfill & \text{if}x\in \mathrm{int}{S}_{+}^p\hfill \\ S_{+}^p,\hfill & \text{if}x=0\hfill \\ \left\{\langle w,x^{*}\rangle \ge 0|w\in S^p\right\},\hfill & \text{if}x\in bd{S}_{+}^p\backslash \left\{0\right\}\hfill \end{array}$ 来描述$S_{+}^p$ 在$x^{*}\in S_{+}^p$ 处的切锥；用$T_{S_{+}^p}^2\left(x^{*},d\right)=\{\begin{array}{ll}{S}^p,\hfill & \text{if}x\in T_{S_{+}^p}\left(x^{*}\right)\hfill \\ T_{S_{+}^p}\left(x^{*}\right),\hfill & \text{if}x=0\hfill \\ \left\{\langle w,d\rangle \ge {\Vert d\Vert }^2|w\in S^p\right\},\hfill & \text{otherwise}\hfill \end{array}=T^2$ 来描述$S_{+}^p$ 在$x^{*}\in S_{+}^p$ 处沿方向d的二阶切锥。见[3] [4]。

2.3. 二阶正则

定义2.3.1 称集合K在点$y\in K$ 沿方向$d\in T_k\left(y\right)$ 关于线性映射$M:X\to Y$ 是二阶正则的：

若对任何具有下述形式的$y_n\in K:y_n=y+t_{n}d+\frac{1}{2}{t}_n^2{r}_n$ ，其中$t_n\downarrow 0$ ，$r_n=M{w}_n+a_n$ ，其中$\left\{a_n\right\}$ 是Y中的收敛序列，$\left\{w_n\right\}$ 是X中的满足$t_n{w}_n\to 0$ 的序列，则下述条件成立：$\underset{n\to \infty }{\lim }d\left(r_n,T_{S_{+}^p}^2\left(y,d\right)\right)=0$ 。见[3]。

3. 二阶充分性条件定理及其证明

接下来我们来描述SDCCVI问题的二阶充分性条件定理及其证明，该证明同Sun在[4]中定理2类似。

给出定理之前，补充以下定义。

定义3.1 点$x^{*}$ 到$S_{+}^P$ 的距离：$dist\left(x^{*},S_{+}^p\right):=\inf \left\{\Vert x^{*}-y\Vert ,\forall y\in S_{+}^P\right\}$ 。

定义3.2 支撑函数：记$\sigma \left(x,C\right)=\max \left\{\langle x,v\rangle :v\in C\right\}$ 为集合C的支撑函数。

定义3.3 本文用$\wedge \left(x^{*}\right)$ 记作满足kkt条件的Lagrange乘子，将$t_n\downarrow 0$ 表示$\left\{t_n\right\}$ 是单调递减趋于0的序列。

定义3.4 $x^{*}$ 处的临界锥与极限法锥：$C\left(x^{*}\right)=\left\{d|d\in T_C\left(x^{*}\right),d\perp F\left(x^{*}\right)\right\}$ ；$N_{S_{+}^P}\left(x^{*}\right):=\underset{x\stackrel{S_{+}^p}{\to }{x}^{*}}{\lim \sup }{\widehat{N}}_{S_{+}^p}\left(x\right)$ ，其中${\widehat{N}}_{S_{+}^p}\left(x^{*}\right):=\left\{v\in S^p|\langle v,y-x^{*}\rangle \le o\left(\Vert y-x^{*}\Vert \right),\forall y\in S_{+}^p\right\}$ 。

定理3.1 设$x^{*}$ 为SDCCVI的一个可行解，$\Lambda \left(x^{*}\right)=\left\{\lambda \right\}$ 是非空且紧的，若$JF\left(x^{*}\right)$ 正半定且 $0\in \mathrm{int}\left\{G\left(x^{*}\right)+JG\left(x^{*}\right)R^n-S_{+}^p\right\}$ ，则$\underset{\lambda \in N\left(x^{*}\right)}{\sup }\left\{\langle J_{x}L\left(x^{*},\lambda \right)d,d\rangle +d^{\text{T}}H\left(x^{*},\lambda \right)d\right\}\succ 0,\forall d\in C\left(x^{*}\right)\backslash \left\{0\right\}$ 为SDCCVI的二阶充分性条件。

其中$\otimes$ 是Kronecker积，$H\left(x^{*},\lambda \right)=-2{\left(\frac{\partial G\left(x^{*}\right)}{\partial x}\right)}^{\text{T}}\left(\lambda \otimes G{\left(x^{*}\right)}^{\text{T}}\right)\left(\frac{\partial G{\left(x^{*}\right)}^{\text{T}}}{\partial x}\right)$ ，$\frac{\partial G\left(x^{*}\right)}{\partial x}$ 为$P^2\times n$ Jacobi矩阵，$\frac{\partial G\left(x^{*}\right)}{\partial x}:=\left[vec{G}_1\left(x^{*}\right),\cdots ,vec{G}_n\left(x^{*}\right)\right]$ ，$G_i\left(x^{*}\right)=\frac{\partial G\left(x^{*}\right)}{\partial x_i}$ ，$vec\left(A\right)$ 记由A的列拉直得到的向量。

证明：

设$x^{*}$ 是问题SDCCVI的一个可行解，由$JF\left(x^{*}\right)$ 正半定的，则存在$\epsilon >0$ 使得$\langle F\left(x^{*}\right),x-x^{*}\rangle \ge 0$ ，$\forall x\in {{\rm B}}_{\epsilon }\left(x^{*}\right)\cap C$ ，其中${{\rm B}}_{\epsilon }\left(x^{*}\right)$ 为$x^{*}$ 的$\epsilon$ 邻域。

这等价于

$x\in \arg \min \left\{\langle F\left(x^{*}\right),x-x^{*}\rangle |x\in {{\rm B}}_{\epsilon }\left(x^{*}\right)\cap C\right\}$ (1)

由于$JF\left(x^{*}\right)$ 正半定则

(1)成立当且仅当

$x\in \arg \min \left\{\langle F\left(x^{*}\right),x-x^{*}\rangle +JF\left(x^{*}\right)\left(x-x^{*}\right),\left(x-x^{*}\right)|x\in {{\rm B}}_{\epsilon }\left(x^{*}\right)\cap C\right\}$ (2)

成立。

考虑这样的一个优化问题

$\{\begin{array}{l}\min \langle F\left(x^{*}\right),x-x^{*}\rangle +\frac{1}{2}\langle JF\left(x^{*}\right)\left(x-x^{*}\right),x-x^{*}\rangle \\ \text{s}\text{.t}.x\in {{\rm B}}_{\epsilon }\left(x^{*}\right)\cap C\end{array}$ (3)

显然

$x^{*}$ 为(3)的稳定点当且仅当

$0\in F\left(x^{*}\right)+JF\left(x^{*}\right)\left(x-x^{*}\right)+N_{{{\rm B}}_{\epsilon }\left(x^{*}\right)\cap C\left(x^{*}\right)}$ (4)

其中

$N_{{{\rm B}}_{\epsilon }\left(x^{*}\right)\cap C\left(x^{*}\right)}=N_{{{\rm B}}_{\epsilon }\left(x^{*}\right)}\left(x^{*}\right)+N_{C\left(x^{*}\right)}=N_{C\left(x^{*}\right)}$ (5)

由(4)和(5)知$0\in F\left(x^{*}\right)+N_C\left(x^{*}\right)$ 。

因此当$x^{*}$ 为SDCCVI问题的可行解时，$x^{*}$ 也是(3)的稳定点。

接下来考虑(3)的临界锥$C_p\left(x^{*}\right)$ 与SDCCVI的临界锥$C\left(x^{*}\right)$ 之间的关系：事实上$C\left(x^{*}\right)=C_p\left(x^{*}\right)$ 。

这是因为

$C_p\left(x^{*}\right)=\left\{d\in R^n|\left(\begin{array}{c}JG\left(x^{*}\right)d\\ d\end{array}\right)\in T_{S_{+}^p\times {{\rm B}}_{\epsilon }\left(x^{*}\right)}\left(G\left(x^{*}\right),x^{*}\right),\langle d,F\left(x^{*}\right)+JF\left(x^{*}\right)\left(x-x^{*}\right)\rangle =0\right\}$

且$T_{S_{+}^p\times {{\rm B}}_{\epsilon }\left(x^{*}\right)}\left(G\left(x^{*}\right),x^{*}\right)=T_{S_{+}^p}\left(G\left(x^{*}\right)\right)\times T_{{{\rm B}}_{\epsilon }\left(x^{*}\right)}\left(x^{*}\right)=T_{S_{+}^p}\left(G\left(x^{*}\right)\right)\times R^n$ 。

因此$C_p\left(x^{*}\right)=\left\{d\in R^n|\left(JG\left(x^{*}\right)d\right)\in T_{S_{+}^p}\left(G\left(x^{*}\right)\right),\langle d,F\left(x^{*}\right)\rangle =0\right\}=C\left(x^{*}\right)$ 。

易知(3)的Lagrange函数为

$L\left(x^{*},\lambda ,\mu \right)=\langle F\left(x^{*}\right),x-x^{*}\rangle +\frac{1}{2}\langle JF\left(x^{*}\right)\left(x-x^{*}\right),x-x^{*}\rangle +\langle -G\left(x\right),\lambda \rangle +\langle x,\mu \rangle$

则

${\nabla }_{x}L\left(x^{*},\lambda ,\mu \right)=F\left(x^{*}\right)+JF\left(x^{*}\right)\left(x-x^{*}\right)+JG\left(x^{*}\right)\lambda +\mu$ ；

${\nabla }_{xx}L\left(x^{*},\lambda \right)=JF\left(x^{*}\right)+J_{x}G\left(x^{*}\right)\lambda$ ，此处记${\nabla }_{xx}L\left(x^{*},\lambda \right)=J_{x}L\left(x^{*},\lambda \right)$ 。

又$S_{+}^p$ 在$G\left(x^{*}\right)$ 沿着$JG\left(x^{*}\right)d$ 方向对于映射$JG\left(x^{*}\right),\forall d\in C\left(x^{*}\right)$ 是二阶正则的，

这是因为利用二阶正则性定义

$y_n=G\left(x^{*}\right)+t_n\left(JG\left(x^{*}\right)d\right)+\frac{1}{2}{t}_n^2{r}_n,\forall y_n\in S_{+}^p$

其中$t_n\downarrow 0$ ，$r_n=JG\left(x^{*}\right)w_n+a_n$ ，$a_n$ 为一收敛序列以及$t_n{w}_n\to 0\left(n\to +\infty \right)$ 使得 $\underset{n\to \infty }{\lim }dist\left(r_n,T_{S_{+}^p}^2\left(G\left(x^{*}\right),JG\left(x^{*}\right)d\right)\right)=0$ 。

基于以上所述，知对于$\forall P_n\in S_{+}^p\times {{\rm B}}_{\epsilon }\left(x^{*}\right)$ ，$P_n=\left(\begin{array}{c}G\left(x^{*}\right)\\ x^{*}\end{array}\right)+t_n\left(\begin{array}{c}JG\left(x^{*}\right)d\\ d\end{array}\right)+\frac{1}{2}{t}_n^2\left(\begin{array}{c}{r}_n\\ q_n\end{array}\right)$ 。

其中$\left(\begin{array}{c}{r}_n\\ q_n\end{array}\right)=\left(\begin{array}{c}JG(x^{*})w_n\\ w_n\end{array}\right)+\left(\begin{array}{c}{a}_n\\ b_n\end{array}\right)$ ，$\left(\begin{array}{c}{a}_n\\ b_n\end{array}\right)$ 是一个收敛序列以及$t_n{w}_n\to 0\left(n\to +\infty \right)$ ，

因此我们得到

$\underset{n\to \infty }{\lim }dist\left(r_n,T_{S_{+}^p}^2\left(G\left(x^{*}\right),JG\left(x^{*}\right)d\right)\right)=0$

且

$\begin{array}{l}\underset{n\to \infty }{\lim }dist\left(\left(\begin{array}{c}{r}_n\\ q_n\end{array}\right),T_{S_{+}^p\times {{\rm B}}_{\epsilon }\left(x^{*}\right)}^2\left(\left(G\left(x^{*}\right),x^{*}\right)\left(JG\left(x^{*}\right)d,d\right)\right)\right)\\ =\underset{n\to \infty }{\lim }dist\left(\left(\begin{array}{c}{r}_n\\ q_n\end{array}\right),T_{S_{+}^p}^2\left(G\left(x^{*}\right),JG\left(x^{*}\right)d\right)\times T_{{{\rm B}}_{\epsilon }\left(x^{*}\right)}^2\left(x^{*},d\right)\right)\\ =\underset{n\to \infty }{\lim }dist\left(r_n,T_{S_{+}^p}^2\left(G\left(x^{*}\right),JG\left(x^{*}\right)d\right)\right)=0.\end{array}$

因此$S_{+}^p$ 在$G\left(x^{*}\right)$ 沿着$JG\left(x^{*}\right)d$ 方向对于映射$JG\left(x^{*}\right),\forall d\in C\left(x^{*}\right)$ 是二阶正则的。

因此$\underset{\lambda \in \wedge \left(x^{*}\right)}{\sup }\left\{{\nabla }_{xx}^{2}L\left(x^{*},\lambda \right)-{\delta }^{*}\times (\left(\lambda ,\mu \right),T_{S_{+}^p\times {{\rm B}}_{\epsilon }\left(x^{*}\right)}^2\left(G\left(x^{*}\right),x^{*}\right),\left(JG\left(x^{*}\right)d,d\right)\right\}>0,\forall d\in C_p\left(x^{*}\right)\backslash \left\{0\right\}$ 。

我们可以进一步化简

$\begin{array}{l}\underset{\lambda \in \wedge \left(x^{*}\right)}{\sup }\left\{{\nabla }_{xx}^{2}L\left(x^{*},\lambda \right)\left(d,d\right)-{\delta }^{*}\times (\left(\lambda ,\mu \right),T_{S_{+}^p\times {{\rm B}}_{\epsilon }\left(x^{*}\right)}^2\left(G\left(x^{*}\right),x^{*}\right),\left(JG\left(x^{*}\right)d,d\right)\right\}\\ =\underset{\lambda \in \wedge \left(x^{*}\right)}{\sup }\left\{{\nabla }_{xx}^{2}L\left(x^{*},\lambda \right)\left(d,d\right)-{\delta }^{*}\times (\left(\lambda ,\mu \right),T_{S_{+}^p}^2\left(G\left(x^{*}\right),JG\left(x^{*}\right)d\right)\times T_{{{\rm B}}_{\epsilon }\left(x^{*}\right)}^2\left(x^{*},d\right)\right\}\\ =\underset{\lambda \in \wedge \left(x^{*}\right)}{\sup }\left\{{\nabla }_{xx}^{2}L\left(x^{*},\lambda \right)\left(d,d\right)-{\delta }^{*}\times (\left(\lambda ,\mu \right),T_{S_{+}^p}^2\left(G\left(x^{*}\right),JG\left(x^{*}\right)d\times R^n\right)\right\}\\ =\underset{\lambda \in \wedge \left(x^{*}\right)}{\sup }\left\{J_{x}L\left(x^{*},\lambda \right)\left(d,d\right)-{\delta }^{*}\left(\lambda |T_{S_{+}^p}^2\left(G\left(x^{*}\right)+JG\left(x^{*}\right)d\right)\right)\right\}.\end{array}$

综上所述，SDCCVI问题的二阶充分性条件为

$\underset{\lambda \in \wedge \left(x^{*}\right)}{\sup }\left\{J_{x}L\left(x^{*},\lambda \right)\left(d,d\right)-{\delta }^{*}\left(\lambda |T_{S_{+}^p}^2\left(G\left(x^{*}\right)+JG\left(x^{*}\right)d\right)\right)\right\},\forall d\in C\left(x^{*}\right)\backslash \left\{0\right\}$

即

$\underset{\lambda \in N\left(x^{*}\right)}{\sup }\left\{\langle J_{x}L\left(x^{*},\lambda \right)d,d\rangle +d^{\text{T}}H\left(x^{*},\lambda \right)d\right\}\succ 0,\forall d\in C\left(x^{*}\right)\backslash \left\{0\right\}$

其中$H\left(x^{*},\lambda \right)=-2{\left(\frac{\partial G\left(x^{*}\right)}{\partial x}\right)}^{\text{T}}\left(\lambda \otimes G{\left(x^{*}\right)}^{\text{T}}\right)\left(\frac{\partial G{\left(x^{*}\right)}^{\text{T}}}{\partial x}\right)$ ，$\frac{\partial G\left(x^{*}\right)}{\partial x}$ 为$P^2\times n$ Jacobi矩阵。

4. 结论

1) 重要性：本论文详细描述并证明了半定锥约束变分不等式二阶充分性条件定理及其相关证明，提供了一种有效的方法来验证该类问题局部最优解的性质。这在许多领域(如控制系统、资源分配、线性回归及金融投资组合优化)中尤为重要，能够帮助决策者在多维空间中找到最优解。

2) 先进性：本文结合拉格朗日乘数法和Hessian矩阵的分析为优化理论提供了坚实的基础。这种理论框架使得半定锥约束变分不等式问题的求解过程变得更加系统化、更方便。此外，论文中所涉及的数值分析与计算方法还能够帮助提高相关算法的收敛性与效率，对获得更加精确的数值解有重要意义。

3) 局限性：虽然二阶条件能有效判断局部最优性，但在某些特定情况下，如非凸问题中，仅依赖于此条件可能会导致无法找到全局最优解。因此，在实际应用中需结合其他方法一同使用，以确保结果的全局最优性。

致 谢

本人感谢我的导师张教授对本论文的指导，在研究过程中提供了宝贵的建议和支持，他严谨的治学态度和深厚的专业知识使我创作了这篇论文并收益颇丰。