一种解决半定规划问题的投影神经网络方法

A Projection Neural Network Method for Solving Semidefinite Programming Problems

摘要: 本文研究了半定规划(SDP)问题的神经网络方法。首先提出了一种基于投影算子的神经网络方法，然后，建立了神经网络平衡点与半定规划问题最优解之间的等价性，并证明了平衡点具有Lyapunov稳定性。数值模拟进一步证明了该网络的有效性。通过利用投影映射和SDP问题的结构，该神经网络方法可以有效地解决优化任务，为解决各种半定规划问题提供了一个实用的计算框架。

Abstract: This paper studies the neural network method for semidefinite programming (SDP) problems. Firstly, a neural network method based on projection operator is proposed. Then, the equivalence between the equilibrium point of the neural network and the optimal solution of the semidefinite programming problem is established, and it is proved that the equilibrium point has Lyapunov stability. Numerical simulation further proves the effectiveness of the network. By using the structure of projection mapping and SDP problem, the neural network method can effectively solve the optimization task, and provides a practical computational framework for solving various semidefinite programming problems.

1. 引言

近年来，由于半定规划(SDP)问题在工程和组合优化中的广泛应用，已引起了广泛关注。半定规划问题包含线性规划、最小–最大特征值问题、最大行列式问题以及对数切比雪夫逼近问题等多个重要优化问题作为特例[1]，这类问题在控制理论、图论、统计学、结构优化、组合优化以及其他学科领域频繁出现[2] [3]。

神经网络方法特别适用于实时优化问题，具备多项显著优势。其类似电路的结构易于通过模拟电路或专用硬件实现，支持低功耗、高并行运算，满足高实时性需求。通过设计能量函数，该方法将约束优化转化为动态系统平衡点求解，简化了传统内点法中复杂的障碍函数设计。此外，连续时间神经网络可直接借助动态系统理论和常微分方程数值方法有效求解约束优化问题，并具有快速收敛能力，适用于实时计算场景。

本文旨在提出一种新的基于投影算子的神经网络来解决半定规划问题。首先，我们回顾了半定规划问题和神经网络的定义。然后，构建了投影神经网络，分析了所提神经网络的平衡点和半定规划问题的解是等价的，并证明了平衡点是Lyapunov稳定的，最后通过数值实验展示了所提方法的有效性。

通过本文的研究，我们希望能够为解决半定规划问题的方法研究提供新的思路。

2. 预备知识

2.1. 半定规划问题

我们考虑半定规划问题[4]：

$\begin{array}{l}\left(P\right)\text{min}\langle C,X\rangle \\ \text{ s}\text{.t}\text{.}\langle A_i,X\rangle =b_i,i=1,2,\cdots ,m,X\ge 0,\end{array}$ (1)

和其对偶问题：

$\begin{array}{l}\left(D\right)\text{max}{b}^{\text{T}}y\\ \text{ s}\text{.t}\text{. }{\displaystyle \sum _{i=1}^m{y}_i{A}_i+S=C,S\ge 0,}\end{array}$ (2)

其中，$C,A_i,X,S$ 是$n$ 阶矩阵，并且$X,S$ 是对称矩阵，$b,y\in R^m$ ，$\langle C,X\rangle ,\langle A_i,X\rangle$ 是矩阵的迹积，$\ge$ 表示半正定，也就是对于实对称矩阵$A$ 和$B$ ，$A\ge B$ 表示$A-B$ 是半正定的。

半定规划问题和对偶半定规划问题的解满足最优性条件[5]：

$\{\begin{array}{l}\langle A_i,X\rangle =b_i,i=1,2,\cdots ,m,X\ge 0,\\ {\displaystyle \sum _{i=1}^m{y}_i{A}_i+S=C,S\ge 0,}\\ \langle X,S\rangle =0.\end{array}$ (3)

令$x=vec\left(X\right)$ 并且定义$u={\left(x^{\text{T}},y^{\text{T}}\right)}^{\text{T}}$ 。如果$X^{*}$ 和$y^{*}$ 满足(3)中的最优性条件，那么称$u^{*}={\left(x^{*}{}^{\text{T}},y^{*}{}^{\text{T}}\right)}^{\text{T}}$ 是半定规划问题的一组解。

2.2. 一阶微分方程

一阶微分方程基本形式为

$\dot{y}\left(t\right)=ℱ\left(y\left(t\right)\right),y\left(t_0\right)=y_0\in {ℝ}^n,$(4)

这里$ℱ:{ℝ}^n\to {ℝ}^n$ 是一个映射。

定义1. 若点$y^{*}=y\left(t^{*}\right)$ 满足$ℱ\left(y^{*}\right)=0$ ，则称$y^{*}$ 为微分方程(4)的平衡点。若存在$y^{*}$ 的一个领域${\Omega }^{*}\subset {ℝ}^n$ ，使得$ℱ\left(y^{*}\right)=0$ ，且对所有$y\in {\Omega }^{*}\backslash \left\{y^{*}\right\}$ ，都有$ℱ\left(y\right)\ne 0$ ，则称$y^{*}$ 为孤立平衡点。

2.3. 投影算子

设$P_{\Omega }:{ℝ}^n\to \Omega$ 是一个投影算子，定义为$P_{\Omega }\left(u\right)=\arg \underset{v\in \Omega }{\min }\Vert u-v\Vert$ 。若$\Omega ={\Omega }_1\times {ℝ}^m$ ，其中$\times$ 表示笛卡尔积，${\Omega }_1\in {ℝ}^{n^2}$ ，则对任意$u={\left(x^{\text{T}},y^{\text{T}}\right)}^{\text{T}}\in {ℝ}^{n^2+m}$ ，有$P_{\Omega }=\left(\begin{array}{c}{P}_{{\Omega }_1}\left(x\right)\\ y\end{array}\right)$ 。

引理1. [6]对于任意的$\left(A,B\right)\in S_{+}^m\times S_{+}^m$ ，其中$S_{+}^m$ 为所有$m\times m$ 实对称半正定矩阵的集合，我们有$\langle A,B\rangle =0$ 当且仅当$A=P_{S_{+}^m}\left(A-B\right)$ 。

命题1. 设$S_{+}^n$ 为所有$n\times n$ 实对称半正定矩阵的集合，有以下等式成立：

$vec\left(P_{S_{+}^n}\left(X\right)\right)=P_{vec\left(S_{+}^n\right)}\left(vec\left(X\right)\right)$

命题2. 如果$\Omega$ 是一个${ℝ}^n$ 上的闭凸子集，那么在闭凸集上的投影的一个基本性质是

${\left[u-P_{\Omega }\left(u\right)\right]}^{\text{T}}\left[P_{\Omega }\left(u\right)-v\right]\ge 0,\forall u\in {ℝ}^n,v\in \Omega$ (5)

3. 投影神经网络

接下来，我们介绍所提出的投影神经网络模型

$\begin{array}{l}\frac{\text{d}u}{\text{d}t}=P_{\Omega }\left[u-\beta \left(Mu+q\right)\right]-u,\\ u\left(t_0\right)=u_0,\beta >0,\end{array}$ (6)

其中$\Omega =vec\left(S_{+}^n\right)\times {ℝ}^m$ ，

$M=\left(\begin{array}{cc}0& -{\overline{A}}^{\text{T}}\\ \overline{A}& 0\end{array}\right),\overline{A}={\left(a^1,a^2,\cdots ,a^m\right)}^{\text{T}},a^i=vec\left(A_i\right),\left(i=1,2,\cdots ,m\right),$

$q=\left(\begin{array}{c}c\\ -b\end{array}\right),c=vec\left(C\right),u_0\in \left\{u={\left(x^{\text{T}},y^{\text{T}}\right)}^{\text{T}}\in {ℝ}^{n^2+m}|x\in vec\left(S_{+}^n\right),y\in {ℝ}^m\right\},$

$\beta$ 是尺度参数，用以表征神经网络的收敛速率。为了便于我们的分析：

定理1. 设$u^{*}={\left(x^{*}{}^{\text{T}},y^{*}{}^{\text{T}}\right)}^{\text{T}}$ 是神经网络(6)的一个平衡点，则$u^{*}$ 满足半定规划问题的最优性条件(3)。反之，若$X^{*}\in S_{+}^n$ 是半定规划问题(1)的一个最优解，则存在$y^{*}\in {ℝ}^m$ ，使得$u^{*}={\left(vec{\left(X^{*}\right)}^{\text{T}},y^{*}{}^{\text{T}}\right)}^{\text{T}}$ 是神经网络(6)的一个平衡点。

证明：假设$u^{*}={\left(x^{*}{}^{\text{T}},y^{*}{}^{\text{T}}\right)}^{\text{T}}$ 是神经网络(6)的一个平衡点，那么$P_{\Omega }\left[u^{*}-\beta \left(M{u}^{*}+q\right)\right]-u^{*}=0$ ，因此

$\begin{array}{l}{u}^{\ast }-P_{\Omega }\left[u^{\ast }-\beta \left(M{u}^{\ast }+q\right)\right]\\ =\left(\begin{array}{c}{x}^{\ast }\\ y^{\ast }\end{array}\right)-P_{\Omega }\left[\left(\begin{array}{c}{x}^{\ast }\\ y^{\ast }\end{array}\right)-\beta \left(\begin{array}{c}\begin{array}{l}-vec\left({\displaystyle {\sum }_{i=1}^m{y}_i^{\ast }{A}_i}\right)+c\\ \langle A_1,X^{\ast }\rangle -b_1\\ ⋮\end{array}\\ \langle A_m,X^{\ast }\rangle -b_m\end{array}\right)\right]\\ =\left(\begin{array}{c}{x}^{\ast }\\ y^{\ast }\end{array}\right)-P_{\Omega }\left[\left(\begin{array}{c}\begin{array}{l}{x}^{\ast }-\beta \left(c-vec\left({\displaystyle {\sum }_{i=1}^m{y}_i^{\ast }{A}_i}\right)\right)\\ y_1^{\ast }-\beta \left(\langle A_1,X^{\ast }\rangle -b_1\right)\end{array}\\ \begin{array}{l}⋮\\ y_m^{\ast }-\beta \left(\langle A_m,X^{\ast }\rangle -b_m\right)\end{array}\end{array}\right)\right]\\ =\left(\begin{array}{c}{x}^{\ast }\\ y^{\ast }\end{array}\right)-\left(\begin{array}{c}{P}_{vec\left(S_{+}^n\right)}\left[x^{\ast }-\beta \left(c-vec\left({\displaystyle {\sum }_{i=1}^m{y}_i^{\ast }{A}_i}\right)\right)\right]\\ \begin{array}{l}{y}_1^{\ast }-\beta \left(\langle A_i,X^{\ast }\rangle -b_1\right)\\ ⋮\\ y_m^{\ast }-\beta \left(\langle A_m,X^{\ast }\rangle -b_m\right)\end{array}\end{array}\right)\end{array}$

根据命题1，得出

$P_{vec\left(S_{+}^n\right)}\left[x^{\ast }-\beta \left(c-vec\left({\displaystyle {\sum }_{i=1}^m{y}_i^{\ast }{A}_i}\right)\right)\right]=vec\left[P_{S_{+}^n}\left[X^{\ast }-\beta \left(C-{\displaystyle \sum _{i=1}^m{y}_i^{\ast }{A}_i}\right)\right]\right]$

代入原式得

$\begin{array}{l}{u}^{\ast }-P_{\Omega }\left[u^{\ast }-\beta \left(M{u}^{\ast }+q\right)\right]\\ =\left(\begin{array}{c}{x}^{\ast }-vec\left[P_{S_{+}^n}\left[X^{\ast }-\beta \left(C-{\displaystyle {\sum }_{i=1}^m{y}_i^{\ast }{A}_i}\right)\right]\right]\\ \begin{array}{l}\beta \left(\langle A_i,X^{\ast }\rangle -b_1\right)\\ ⋮\\ \beta \left(\langle A_m,X^{\ast }\rangle -b_m\right)\end{array}\end{array}\right)\\ =0\end{array}$

我们有

$\{\begin{array}{l}{X}^{\ast }=P_{S_{+}^n}\left[X^{\ast }-\beta \left(C-{\displaystyle {\sum }_{i=1}^m{y}_i^{\ast }{A}_i}\right)\right]\\ \langle A_i,X^{\ast }\rangle =b_i\text{, }i=1,2,3,\cdots ,m.\end{array}$

将$A=X^{\ast },B=\beta \left(C-{\displaystyle {\sum }_{i=1}^m{y}_i^{\ast }{A}_i}\right)$ 代入到引理1中，我们得到

$\{\begin{array}{l}\langle A_i,X^{\ast }\rangle =b_i\text{, }i=1,2,3,\cdots ,m,\\ C-{\displaystyle {\sum }_{i=1}^m{y}_i^{\ast }{A}_i}\underset{\_}{\succ }0,X\underset{\_}{\succ }0,\\ \langle X^{\ast },C-{\displaystyle {\sum }_{i=1}^m{y}_i^{\ast }{A}_i}\rangle =0.\end{array}$

这与(3)是等价的，即$u^{*}={\left(x^{*}{}^{\text{T}},y^{*}{}^{\text{T}}\right)}^{\text{T}}$ 满足半定规划问题的最优性条件。反之亦然。

证毕。

定理2. 神经网络(6)的平衡点$u^{*}={\left(x^{*}{}^{\text{T}},y^{*}{}^{\text{T}}\right)}^{\text{T}}$ 在Lyapunov意义上是稳定的。

证明：令$u^{*}={\left(x^{*}{}^{\text{T}},y^{*}{}^{\text{T}}\right)}^{\text{T}}$ 是神经网络(6)的一个平衡点，我们有

$u^{*}=P_{\Omega }\left[u^{*}-\beta \left(M{u}^{*}+q\right)\right]-u^{*}$

考虑以下函数：

$V\left(u\right)=\beta {\left[F\left(u\right)\right]}^{\text{T}}\left[u-P_{\Omega }\left[u-\beta F\left(u\right)\right]\right]-\frac{1}{2}{\Vert u-P_{\Omega }\left[u-\beta F\left(u\right)\right]\Vert }^2+\frac{1}{2}{\Vert u-u^{*}\Vert }^2\text{, }u\in \Omega$

这里$F\left(u\right)=Mu+q$ 。显然，$F\left(u\right)$ 是连续可微的，并且$V\left(u^{*}\right)=0$ 。

将$\Omega =vec\left(S_{+}^n\right)\times {ℝ}^m$ (它是${ℝ}^{n^2+m}$ 的一个闭凸子集)、$u-\beta F\left(u\right)\in {ℝ}^{n^2+m}$ 、$u\in \Omega$ 代入(5)，我们有

${\left[u-\beta F\left(u\right)-P_{\Omega }\left[u-\beta F\left(u\right)\right]\right]}^{\text{T}}\left[P_{\Omega }\left[u-\beta F\left(u\right)\right]-u\right]\ge 0,$

那么

$\beta {\left[F\left(u\right)\right]}^{\text{T}}\left[u-P_{\Omega }\left[u-\beta F\left(u\right)\right]\right]\ge {\Vert u-P_{\Omega }\left[u-\beta F\left(u\right)\right]\Vert }^2.$

因此

$V\left(u\right)\ge \frac{1}{2}{\Vert u-P_{\Omega }\left[u-\beta F\left(u\right)\right]\Vert }^2+\frac{1}{2}{\Vert u-u^{*}\Vert }^2\ge 0,\forall u\in \Omega ,$

且显然有

$V\left(u\right)>0,\forall u\in \Omega ,u\ne u^{*}.$

与文献[7]中定理3.2的证明类似，我们可知：

$\nabla V\left(u\right)=\beta F\left(u\right)+\left(\beta \nabla F\left(u\right)-I_n\right)\left[u-P_{\Omega }\left[u-\beta F\left(u\right)\right]\right]+u-u^{*},$

其中，$I_n$ 是$n$ 阶单位矩阵。因此，沿着神经网络(6)的轨迹$u=u\left(t,u_0\right)\left(t\ge 0\right)$ ，我们有

$\begin{array}{c}\frac{\text{d}V\left[u\left(t\right)\right]}{\text{d}t}={\left[\nabla V\left(u\right)\right]}^{\text{T}}\frac{\text{d}u}{\text{d}t}\\ =-{\left[u-u^{*}+\beta F\left(u\right)\right]}^{\text{T}}\left[u-P_{\Omega }\left[u-\beta F\left(u\right)\right]\right]+{\Vert u-P_{\Omega }\left[u-\beta F\left(u\right)\right]\Vert }^2\\ -\beta {\left[u-P_{\Omega }\left[u-\beta F\left(u\right)\right]\right]}^{\text{T}}\nabla F\left(u\right)\left[u-P_{\Omega }\left[u-\beta F\left(u\right)\right]\right].\end{array}$

因为$F$ 是可微的，并且

$\nabla F\left(u\right)=M=\left(\begin{array}{cc}0& -{\overline{A}}^{\text{T}}\\ \overline{A}& 0\end{array}\right),$

这是一个反对称矩阵，因此

$\beta {\left[u-P_{\Omega }\left[u-\beta F\left(u\right)\right]\right]}^{\text{T}}\nabla F\left(u\right)\left[u-P_{\Omega }\left[u-\beta F\left(u\right)\right]\right]=0.$

将$u-\beta F\left(u\right)\in R^{n^2+m},u^{*}\in \Omega$ 代入(3)中，我们得到

$\begin{array}{l}{\left[u-\beta F\left(u\right)-P_{\Omega }\left[u-\beta F\left(u\right)\right]\right]}^{\text{T}}\left[P_{\Omega }\left[u-\beta F\left(u\right)\right]-u^{*}\right]\\ ={\left[u-\beta F\left(u\right)-P_{\Omega }\left[u-\beta F\left(u\right)\right]\right]}^{\text{T}}\left[P_{\Omega }\left[u-\beta F\left(u\right)\right]-u+u-u^{*}\right]\\ ={\left[u-P_{\Omega }\left[u-\beta F\left(u\right)\right]\right]}^{\text{T}}\left[\beta F\left(u\right)+u-u^{*}\right]-{\Vert u-P_{\Omega }\left[u-\beta F\left(u\right)\right]\Vert }^2-\beta F{\left(u\right)}^{\text{T}}\left(u-u^{*}\right)\\ ={\left[\beta F\left(u\right)+u-u^{*}\right]}^{\text{T}}\left[u-P_{\Omega }\left[u-\beta F\left(u\right)\right]\right]-{\Vert u-P_{\Omega }\left[u-\beta F\left(u\right)\right]\Vert }^2-\beta {\left(u-u^{*}\right)}^{\text{T}}F\left(u\right)\\ \ge 0.\end{array}$

这意味着，

${\left[\beta F\left(u\right)+u-u^{*}\right]}^{\text{T}}\left[u-P_{\Omega }\left[u-\beta F\left(u\right)\right]\right]\ge {\Vert u-P_{\Omega }\left[u-\beta F\left(u\right)\right]\Vert }^2+\beta {\left(u-u^{*}\right)}^{\text{T}}F\left(u\right).$

因此

$\frac{\text{d}V\left[u\left(t\right)\right]}{\text{d}t}\le -\beta {\left(u-u^{*}\right)}^{\text{T}}F\left(u\right).$ (7)

对于任意的$u\in \Omega$ ，我们有

${\left(u-u^{*}\right)}^{\text{T}}F\left(u\right)={\left(u-u^{*}\right)}^{\text{T}}\left[F\left(u\right)-F\left(u^{*}\right)\right]+u^{\text{T}}F\left(u^{*}\right)-u^{*}{}^{\text{T}}F\left(u^{*}\right).$

由神经网络(6)和最优性条件(3)，我们得到

$\begin{array}{c}{u}^{*}{}^{\text{T}}F\left(u^{*}\right)=\left(x^{*}{}^{\text{T}},y^{*}{}^{\text{T}}\right)\left(\begin{array}{c}-vec\left({\displaystyle {\sum }_{i=1}^m{y}_i^{*}{A}_i}\right)+c\\ \langle A_1,X^{*}\rangle -b_1\\ ⋮\\ \langle A_m,X^{*}\rangle -b_m\end{array}\right)\\ =\left(x^{*}{}^{\text{T}},y^{*}{}^{\text{T}}\right)\left(\begin{array}{c}-vec\left({\displaystyle {\sum }_{i=1}^m{y}_i^{*}{A}_i}\right)+c\\ 0\\ ⋮\\ 0\end{array}\right)\\ =\langle X^{*},C-{\displaystyle \sum _{i=1}^m{y}_i^{*}{A}_i}\rangle \\ =0.\end{array}$

因此

$\begin{array}{l}{\left(u-u^{*}\right)}^{\text{T}}F\left(u\right)\\ ={\left(u-u^{*}\right)}^{\text{T}}\left[F\left(u\right)-F\left(u^{*}\right)\right]+u^{\text{T}}F\left(u^{*}\right)\\ ={\left(u-u^{*}\right)}^{\text{T}}M\left(u-u^{*}\right)+\left(x^{\text{T}},y^{\text{T}}\right)\left(\begin{array}{c}-vec\left({\displaystyle {\sum }_{i=1}^m{y}_i^{*}{A}_i}\right)+c\\ 0\\ ⋮\\ 0\end{array}\right)\\ ={\left(u-u^{*}\right)}^{\text{T}}M\left(u-u^{*}\right)+\langle X,C-{\displaystyle \sum _{i=1}^m{y}_i^{*}{A}_i}\rangle .\end{array}$

上式结合反对称矩阵$M,X\in S_{+}^n,C-{\displaystyle {\sum }_{i=1}^m{y}_i^{*}{A}_i\in S_{+}^n,\beta >0}$ 以及(7)，得到

$\frac{\text{d}V\left[u\left(t\right)\right]}{\text{d}t}\le -\beta {\left(u-u^{*}\right)}^{\text{T}}F\left(u\right)\le -\beta \langle X,C-{\displaystyle \sum _{i=1}^m{y}_i^{*}{A}_i}\rangle \le 0$

这意味着神经网络(6)的平衡点在Lyapunov意义上是稳定的。

证毕。

4. 数值实验

下面的例子是根据文献[8]，经过适当修改而改编的。

考虑半定规划问题(1)和其对偶问题(2)，令$n=3,m=2$ ，

$A_1=\left(\begin{array}{cccc}-1& 0& 0& 0\\ 0& -2& 0& 0\\ 0& 0& 2& 0\\ 0& 0& 0& 4\end{array}\right),A_2=\left(\begin{array}{cccc}3& 0& 0& 0\\ 0& -1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& -1\end{array}\right),$

$b=\left(\begin{array}{c}-3\\ 1\end{array}\right),C=\left(\begin{array}{cccc}3& 0& 0& 0\\ 0& 2& 0& 0\\ 0& 0& 8& 0\\ 0& 0& 0& 16\end{array}\right).$

实验在MATLAB R2022上进行，所使用的常微分方程求解器为ode45。图1展示了基于神经网络(6)的$y\left(t\right)$ 的轨迹，参数取$\beta =100$ ，初始点取$X_0=I_4$ 和$y_0=\left(\begin{array}{c}1\\ 1\end{array}\right)$ 。

Figure 1. $y\left(t\right)$ trajectory based on neural network (6)

图1. 基于神经网络(6)的$y\left(t\right)$ 轨迹

5. 结论

本文提出了一种新的基于投影算子的神经网络来解决半定规划问题。

致 谢

本人衷心感谢张杰老师在学术道路上的悉心指导。