针对非光滑伪单调均衡问题的束型信赖域方法

《Communications in Nonlinear Science and Numerical Simulation》：A bundle-based trust region method for nonsmooth pseudomonotone equilibrium problems

　　

近年来，均衡问题（Equilibrium Problems, EPs）的应用领域得到了显著扩展；然而，对于非光滑均衡问题，现有方法通常需要求解非光滑无约束优化子问题，这带来了较高的计算成本。本文提出了一种基于束（bundle）的信赖域方法，该方法通过求解一个定义为分段线性函数与正则化项之和的近似模型来生成新的迭代点。在温和假设下，建立了所提算法的全局收敛性。与现有束方法相比，所提出的方法不仅消除了选择对算法效率产生不利影响的邻近参数（proximal parameter）的需要，而且在理论上被证明具有更广泛的适用性。数值实验结果进一步表明，所提出的算法展现出优异的计算效能。

本研究聚焦于非光滑伪单调均衡问题，这是一类在数学、工程及经济学领域具有重要理论价值与应用背景的优化问题。均衡问题作为 Ky Fan 不等式的现代表述，为众多数学规划问题提供了统一的理论框架，涵盖非线性规划、变分不等式、不动点问题、纳什均衡、鞍点问题及非线性互补问题等。近年来，该理论在计量经济学模型、压缩感知、航天器系统、整数规划博弈、疫苗接种决策、城市交通系统、多智能体协同控制、智能电网能耗管理、LASSO 问题、调强放射治疗规划、流体滑移与泄漏边界条件问题以及动态寡头市场均衡等领域获得了广泛应用。

然而，非光滑均衡问题的求解面临显著挑战。现有主流方法基于辅助问题原理，需构造正则化子问题，该子问题要求目标函数 g(x^k, ·) 为凸且次可微以保证强凸性。当该函数非光滑时，子问题的求解仍十分困难。尽管近年来次梯度外梯度法及其惯性变体、多步隐式混合最速下降法等迭代算法不断涌现，但这些方法在处理非光滑性时仍存局限。特别地，将束方法应用于均衡问题的研究尚属有限，现有邻近束方法通过引入邻近参数 t_k 构造线性模型，但迭代质量受参数选择影响，且收敛性通常依赖于单调性条件和利普希茨（Lipschitz）连续性条件，这限制了方法的适用范围。

为突破上述瓶颈，研究人员提出了一种创新的束型信赖域方法，该方法整合了束方法与信赖域技术的优势，同时消除了邻近参数选取的难题。该研究发表于《Communications in Nonlinear Science and Numerical Simulation》期刊。

研究所采用的关键技术方法包括：基于分段线性函数与正则化项构建的二次凸近似模型；动态调整的信赖域机制；利用函数值与次梯度信息构造的上包络模型 M?(·, x^k)；以及伪单调性和非利普希茨连续性假设下的全局收敛性分析框架。具体而言，算法通过定义指标束 I_k^? ? {0, 1, ..., ??1} 和信息束 B_k^? = ?_i∈Ik^? {(E_kⁱ, ξ^k(y_kⁱ), y_kⁱ)} 来逼近 g(x^k, ·)，其中 E_kⁱ = ?ξ^k(y_kⁱ), y_kⁱ ? x^k? ? g^k(y_kⁱ)，并采用 "quagprog" 函数求解二次规划子问题。

**预备知识**

本部分引入贯穿全文的标准记号与定义。设 Rⁿ 为 n 维欧几里得空间，?u, v? 表示向量 u 与 v 的内积，‖·‖_E 为相应的欧几里得范数。对于以 x 为中心、半径 r > 0 的任意范数 ‖·‖_A 下的闭球，记为 B^A_r(x)。函数 f 的凸性定义为满足 (1?a)f(x) + af(y) ≥ f((1?a)x + ay) 对所有 x, y 成立。

**算法描述**

该部分详述了所提束型信赖域方法的迭代结构。设外循环当前迭代点为 x^k（指标为 k），内循环迭代点为 y_k^??1（指标为 ?）。通过构造 g(x^k, ·)（简记为 g^k(·)）的近似来推进算法。定义指标束 I_k^? 和信息束 B_k^?，并基于次梯度 ξ^k(y_kⁱ) ∈ ?g^k(y_kⁱ) 构造线性化函数 m^?(y, x^k) = ?ξ^k(y_kⁱ), y ? x^k? ? E_kⁱ。该算法通过求解由分段线性函数与正则化项组成的近似模型，在信赖域约束下生成新的迭代点，从而避免了邻近参数的选择。

**收敛性分析**

该部分建立了算法 1 的全局收敛性理论。根据算法 1，子问题（6）中的信赖域半径上有界，其上界记为 R，由此可得 y_kⁱ ∈ B?^A_R(x^k) 对所有 i ∈ I_k^? 成立。定义上包络模型 M?(y, x^k) = sup_{y?∈B(x^k), ξ∈?g^k(y?)} {m_y?,ξ(y, x^k)}}}，其中 m_y?,ξ(y, x^k) = ?ξ, y ? x^k?，B(x^k) = {y | y ∈ B?^A_R(x^k), y 为试探点}。在假设 1 满足的条件下，引理 1 表明：M?(·, x^k) 是凸函数；m^?(·, x^k) ≤ M?(·, x^k) 对所有 ? 成立；M?(x^k, x^k) = 0；且 ?M?(x^k, x^k) ? ?g^k。基于上述性质，在 g(·, ·) 的伪单调性和非利普希茨连续性假设下，严格证明了所提算法的全局收敛性，这一理论结果将现有方法的适用范围从单调性和利普希茨连续性条件拓展至更为宽松的伪单调性和非利普希茨连续性框架。

**数值实验与结果**

该部分通过数值实验补充理论结果并验证算法 1 的有效性。所有实验均在配备 1.6 GHz CPU 的个人计算机上使用 MATLAB 完成。数值结果呈现了算法 1 与对比算法的性能，并进行了全面的分析与比较。所有实验中，均采用 MATLAB 优化工具箱中的 "quagprog" 函数求解二次规划子问题。实验结果表明，所提算法在实际计算环境中具有优异的效能和鲁棒性。

**结论**

本研究考虑了源于多种实际应用的非光滑伪单调均衡问题。通过整合信赖域方法与束方法的优势，提出了一种新算法。该算法利用源于原均衡问题的函数值和次梯度信息，构造二次凸近似模型并建立相应的信赖域子问题来生成新的迭代点。研究表明，所提出的束型信赖域方法在理论上具有更广泛的适用性，在计算上展现出更高的效率，为非光滑伪单调均衡问题的求解提供了有效的理论工具和算法框架。