用于具有互补约束的数学规划问题的神经网络模型

《Journal of Computational and Applied Mathematics》：Neural network model for mathematical programming problems with complementarity constraints

　　摘要

在本文中，我们提出了一种基于梯度的神经网络模型来解决具有互补约束（MPCC）的数学规划问题。为了便于优化，通过正则化方法将MPCC问题转化为一个放宽的非线性优化问题。之后，利用惩罚函数和神经网络模型获得了转化后问题的最优解估计。基于李雅普诺夫稳定性和LaSalle不变性原理，理论上证明了所提出的神经网络的平衡点是渐近稳定的，并且神经网络的轨迹会收敛到MPCC问题的全局最优解。此外，我们通过各种示例来展示所提出神经网络的性能和动态行为，并通过理论和数值实验验证了其有效性。

引言

在这项研究中，我们关注以下受限优化问题：

(????????)min???(??)

subject to

?????(??)≤0, ???=1,2,...,m,?

???(??)=0, ???=1,2,...,l,

0≤?????(??)·?????(??)≥0, ???=1,2,...,m,?,

??,

其中所有函数??,????,???,????,????:?^n→?都被假设为连续可微的，并且表达式0≤?????(??)·?????(??)≥0等价于?????(??)≥0, ?????(??)≥0, ?????(??)·?????(??)=0, ???=1,2,...,m,?,??。设?:={??∈?^n∣?????(??)≤0, ???=1,2,...,m,?,???(??)=0, ???=1,2,...,l, 0≤?????(??)·?????(??)≥0, ???=1,2,...,m,?,??}表示MPCC问题的所有可行点集。MPCC问题在包括工程设计、经济均衡分析和多级博弈论在内的多个领域中具有重要意义，参见Luo等人[1]。

解决MPCC问题的主要难点，无论是理论上还是数值上，都源于互补约束的存在。这些约束导致了标准的约束条件（如Mangasarian–Fromovitz约束条件（MFCQ）、线性独立性约束条件（LICQ）等）的违反，这些条件适用于传统的非线性优化问题（参见Leyffer [2]）。因此，标准优化技术的收敛条件通常无法满足。为了解决这个问题，过去十年中的一些研究者提出了利用MPCC问题特定结构的解决方案算法，消除了由互补约束引起的复杂性。解决MPCC问题最常用的策略包括惩罚函数、提升法、平滑法、正则化、隐式编程等（参见[3]、[4]、[5]、[6]、[7]、[8]、[9]及其中的引用文献）。

在过去的几十年里，许多现实世界的问题越来越需要实时解决方案；然而，由于问题的复杂性和高维度，上述传统方法往往难以提供这样的解决方案。由于神经网络具有内在的并行处理能力和与基于硬件的执行的兼容性，因此它们已成为提供实时解决方案和处理复杂优化问题的强大计算工具。神经网络在优化中的应用起源于Tank和Hopfield[10]对线性规划问题的研究，他们表明高度互联的非线性模拟神经元网络在解决线性规划问题方面具有巨大潜力。1992年，Zhang[11]考虑了基于拉格朗日乘数的神经网络来解决具有一元和不等式约束的一般非线性规划问题，并通过最大熵图像恢复验证了其稳定性。此后，Bouzerdoum和Pattison[12]提出了一种用于解决受有界变量约束的二次凸优化问题的神经网络模型，并证明了所提出的神经网络模型是全局收敛和指数渐近稳定的。此外，Xia[13]提出了一种原始-对偶神经网络方法来解决线性和二次规划问题，该方法能够全局收敛并获得问题的精确解。最近，Bian和Xue[14]考虑了受限的非光滑非凸优化问题，并提出了一种基于次梯度的神经网络，利用惩罚函数方法证明了神经网络的轨迹收敛到平衡点集。

在上述研究中，作者主要关注时不变优化问题。然而，为了解决时变参数下的优化问题，Xia和Wang[15]提出了一种单层对偶神经网络来解决冗余机械手的时变逆运动学问题，并证明了所提出的对偶神经网络是全局指数稳定的。最近，Jin等人[16]提出了一种基于梯度的差分神经解决方案（GDN）模型来解决具有线性等式和不等式约束的时变非线性优化问题，并展示了与现有模型相比，该模型具有更快的收敛速度和更低的解误差。

除了方法论的发展外，神经网络越来越成为解决现实世界问题的强大计算框架。在此基础上，Wang等人[17]使用抗噪声梯度神经动力学（NRGD）模型设计了一种鲁棒控制器，以在噪声存在的情况下实现混沌系统的可靠同步。所提出方法的有效性和鲁棒性通过理论分析、数值模拟、图像加密和机器人运动控制得到了验证。此外，Feng等人[18]使用k-Winners-Take-All（k-WTA）机制讨论了竞争选择的计算抽象，将其重新表述为二次规划和零查找问题，并提出了一种自适应的基于梯度的神经框架，实现了更快、更准确的收敛。关于神经网络的更多信息，建议读者参考[19]、[20]、[21]、[22]、[23]、[24]、[25]、[26]、[27]及其中的引用文献。

受到前述研究的启发，本文专注于MPCC问题，并通过Kanzow和Schwartz[3]中给出的正则化方法将其转化为受限非线性程序，从而降低了问题的复杂性。之后，使用适当的惩罚函数将非线性程序重新转化为无约束程序。基于这一框架，提出了一种神经网络模型来有效解决MPCC问题。此外，通过构造合适的李雅普诺夫函数，理论证明了所提出神经网络的渐近稳定性。研究的主要成果如下：

(i) 基于梯度的神经网络框架：提出了一种新的基于梯度的神经网络模型，可以高效解决MPCC问题。

(ii) 问题的重新表述：采用正则化方法将MPCC问题转化为连续可微的受限非线性程序。

(iii) 方法和复杂性：通过使用惩罚函数技术，所提出的神经网络模型具有由n个神经元组成的简单单层架构，而Ezazipour和Golbabai[28]的模型使用了??+2m个神经元。因此，所提出的模型需要的神经元较少，且架构维度更低。

(iv) 理论和实验验证：理论分析证明了在某些假设下，所提出的神经网络的平衡点是渐近稳定的，并且其轨迹会收敛到MPCC问题的全局最优解，这一点通过计算机模拟进一步得到了验证。

本文的其余结构如下。在第2节中，我们介绍了一些与MPCC问题相关的符号和初步概念，以及获得后续结果所必需的一些定义。第3节中，我们构建了一个神经网络模型，其轨迹收敛到MPCC问题的全局最优解。第4节中，我们分析了神经网络平衡点的渐近稳定性及其与MPCC问题解的关系。第5节中，我们提供了计算机模拟，以展示所提出方法的实用性和潜在影响。最后，在第7节中，我们对本文进行了总结并提出了未来的发展方向。

符号和初步概念

在本节中，我们介绍了与具有互补约束的数学规划相关的符号和基本概念，以及构成后续章节中理论发展基础的关键定义。设?^n表示n维欧几里得空间，?^n^+表示?^n中所有分量非负的向量的非负象限。

定义2.1 [29] 如果可微函数??:?^n→?在??*∈?^n中满足???(??)????(??*)≤0，则称??在??*处是凸的。

神经网络模型的构建

一般来说，使用神经网络解决受限优化问题的关键方法是构建一个适当的能量函数，使其最小值对应于所考虑问题的最优解。因此，为了处理NLP(β)问题，我们使用惩罚函数方法将受限问题转化为无约束问题，如Luenberger和Ye[33]所描述的。

min???(??,??)=???(??)+??·??

其中b是一个正常数，??:?^n→?是一个惩罚函数。

稳定性和收敛性分析

在本节中，我们介绍了神经网络(3)的稳定性和收敛性质，并检验了随着参数β趋于零时神经网络的平衡点与MPCC问题全局最优解之间的关系。

定理4.1

设点???(??0)=??0是神经网络(3)的初始点。如果水平集???(??0)={??∈?^n∣??(??,??)≤??(??0,??)}是有界的，则存在神经网络(3)的平衡点w*和严格递增的序列{tk}。

计算机模拟

在本节中，我们对所提出的神经网络进行了计算机模拟。所有的数值实验都是在个人计算机上使用MATLAB R2025b进行的。此外，常微分方程系统是使用ode45求解器积分的，并使用MATLAB的randi函数在区间[0,1]上生成随机初始点。数值实验的结果证明了所提出的神经网络模型的有效性和可靠性。

观察

所提出的神经网络框架为解决所考虑的MPCC问题提供了一种有竞争力的方法。与从单一预定起点开始并需要反复解决具有更新参数的一系列平滑惩罚子问题的惩罚函数算法（l1、低阶和二次）不同，所提出的方法直接从能量函数的连续时间下降动力学生成解轨迹，并使用一些随机值。

结论

在这项研究中，构建了一个基于梯度的神经网络来解决具有互补约束的数学规划问题MPCC。通过使用正则化技术，将MPCC问题转化为等价的放宽的非线性规划问题NLP(β)。然后，使用惩罚函数方法构建了一个能量函数，其最小值代表问题NLP(β)的最优解。接着，我们推导出了神经网络，该网络具有简单的结构。

资金

本手稿的准备工作没有收到任何资金支持。

利益冲突声明

作者声明他们没有已知的竞争财务利益或个人关系，这些利益或关系可能会影响本文报道的工作。

Anurag Jayswal | Ajeet Kumar

数学与计算系，印度理工学院（印度矿业学院），Dhanbad，Jharkhand，826004，印度