混合变分不等式问题的块近端点法

《Communications in Nonlinear Science and Numerical Simulation》：Block Proximal Point Method for Mixed Variational Inequality Problem

　　

摘要混合变分不等式（MVIs）为经济学、工程和机器学习中的各类优化与均衡问题提供了一套强大的建模框架。然而，由于高维度和复杂的算子结构，求解大规模MVIs仍然计算成本高昂。本文提出了一种加速的块近端点算法，结合块分解与扰动梯度方向来解决这些问题。通过动态更新变量子集并引入扰动梯度步，我们的方法显著降低了每次迭代的计算成本，同时保持了收敛性。我们在标准单调性和Lipschitz连续性假设下建立了收敛性，并通过Nash-Cournot均衡、二次耦合和金融投资组合优化等数值实验验证了其有效性。实验结果表明，部分块激活在精度和计算效率之间实现了良好的平衡，使该算法特别适用于资源受限的实际应用场景。引言变分不等式已成为优化、互补问题和均衡问题的统一框架，应用范围涵盖博弈论到金融建模。其中，混合变分不等式（MVIs）结合了单调算子和非光滑凸函数，尤其具有通用性，可解决Nash均衡和约束极小极大优化等问题。尽管具有理论上的吸引力，求解大规模MVIs仍面临重大计算挑战：高维算子求值、变量间耦合交互以及非光滑项往往使经典方法难以实施（参考文献[1], [2], [3], [4], [5]）。现有方法，如块坐标分解方法和基于梯度的加速技术，提供了解决问题的部分方案。块分解技术通过利用问题结构，将其分解为更小、更易管理的子问题[6], [7], [8], [9], [10]。这不仅降低了计算复杂度，还允许更大的步长，从而与经典方法相比实现更快的收敛[11], [12], [13]。然而，在病态条件下，这些方法面临收敛缓慢的问题。此外，惯性外推技术已被广泛用于加速算法收敛，但涉及外推步骤的方法可能会丧失一些期望的性质，例如对收敛保证至关重要的Fejér单调性[14], [15], [16], [17]。另一种技术是基于梯度的加速方法，特别是共轭梯度方法[18], [19]，它们是极小化下降法的改进，用于加速一阶优化算法的收敛[20]。然而，这些方法缺乏有效处理MVI非光滑组件的机制。弥合这些差距需要一种整合结构分解、扰动梯度更新和近端正则化的技术，这种组合在MVI文献中尚缺乏充分探索。在这项工作中，我们提出了一种加速近端点算法，在块分解框架内集成了扰动梯度方向。我们的方法在每次迭代中选择性激活一组索引子集，显著降低计算成本同时确保收敛。此外，块更新的顺序动态变化，确保所有块被足够频繁地激活以维持稳定性和收敛性。据我们所知，现有算法尚未同时结合块分解、扰动梯度更新和近端正则化来解决此处考虑的混合变分不等式类。近期关于块坐标近端方法[6], [11], [21]和惯性技术[14], [15], [16]的研究要么针对不同的问题结构，要么缺乏我们方法所具备的特征组合。因此，我们将我们的贡献视为一种战略方法，展示了求解大规模MVIs的新方向，而非对单一现有方法的改进。我们通过Nash-Cournot均衡的应用展示方法的有效性，在该应用中确定市场中供应商的生产水平以达到均衡。此外，我们考虑了二次耦合情形，这是一类统一各种优化公式的模型，在数学规划中具有特殊重要性。最后，我们考虑金融市场中的投资组合优化，优化公司内不同部门持有的资产和负债的构成。目标是在最小化风险的同时最大化资产持有并减少潜在负债。本文其余部分组织如下。第2节概述问题公式化和预备知识，第3节详细介绍算法及其收敛性，第4节展示所考虑问题的数值案例插图。片段Section 2 问题公式化与预备知识本节给出问题的公式化并回顾本节收敛分析所需的预备结果。我们考虑对每个 α ∈ I 和 k ∈ K 的实Hilbert空间 H_α 和 G_k，其中 K 和 I 为索引集。注2.1 为简化符号，我们在所有空间 H_α 和 G_k 中使用相同的符号表示内积和范数，对每个 α ∈ I 和 k ∈ K 均如此。然而，此符号并不表示这些空间必然具有相同的性质。片段Section 3 算法及其收敛性分析我们提出了一种块坐标算法来求解问题(2)。该算法在每步仅更新变量子集，在保持收敛保证的同时降低了计算复杂度。为确保算法收敛，我们需要以下假设。对于该算法，我们考虑索引集 {I_n}，它们是I的非空子集，满足条件 I_0 = I。此外，存在整数 n, m ≥ 1，使得 ?_{i=n}^{n+m} I_i = I。注3.1 算法1可以视为……片段Section 4 问题2的应用本节通过展示非合作博弈、二次耦合和金融市场投资组合优化中遇到的公式可以重新表述为我们所考虑问题的特例，来说明问题(2)的应用。值得指出的是，所有实验结果的代码均使用MATLAB R2023a编写，并在配备第11代Intel(R) Core(TM) i5-1135G7处理器（运行频率2.40 GHz）和16 GB RAM的Acer笔记本电脑上执行。在所有数值实验中，结论本文通过引入一种利用块分解和扰动梯度方向的加速块近端点算法，解决了求解大规模混合变分不等式（MVIs）的计算挑战。所提出的算法选择性地激活变量子集，并在近端框架中引入扰动梯度更新。该方法在降低每次迭代成本的同时，在标准假设下确保了强收敛性。数值实验……CRediT作者贡献声明Jamilu Abubakar：写作 – 审阅与编辑、写作 – 原始草稿、可视化、验证、软件、方法论、调查、形式分析、数据整理、概念构思。Sani Salisu：写作 – 审阅与编辑、写作 – 原始草稿、可视化、验证、方法论、调查、形式分析、数据整理、概念构思。Kanokwan Sitthithakerngkiet：验证、监督、软件、资源、项目管理、方法论、调查、资金。利益冲突声明作者声明不存在已知的竞争性经济利益或个人关系可能影响本文所报告的工作。Jamilu Abubakar | Sani Salisu | Kanokwan Sitthithakerngkiet，泰国北奔皇宋克理工大学应用科学学院数学系智能与非线性动态创新研究中心，曼谷，泰国。