约束凸优化中非精确次梯度束方法的一种新罚函数策略

《Communications in Nonlinear Science and Numerical Simulation》：A New Penalty Strategy in Inexact Bundle Scheme for Constrained Convex Optimization

　　

## 摘要

本工作提出了一种近端 Bundle 方法，其中包含一种新颖的惩罚方案，用于求解约束凸非光滑优化问题。该方法旨在处理提供目标函数和约束映射的函数值及次梯度的上界或下界的不精确 Oracle。首先，通过带有可控参数更新的惩罚函数对该问题进行重构，并证明了惩罚增长是有界的。随后，提出了一种改进的切割平面模型来管理由 Oracle 不精确性引起的误差。我们的策略专门针对具有上界 Oracle 的问题：它结合目标函数降低的无约束优化技术与分离的惩罚更新以实现可行性控制。生成的序列收敛至一个近似解，其精度仅取决于目标函数 Oracle 的精度。最后，一些令人鼓舞的数值结果验证了所提方法的有效性。

## 引言

本文重点研究约束非光滑优化问题，其形式如下：

min f(x)
s.t. F(x) ≤ 0

其中 f 和 F 是定义在 ?? 上的凸（但可能非光滑）实值函数。假设 Slater 条件成立，即存在一个点 x? 使得 F(x?) < 0。该问题被称为非光滑优化（NSO），其解析性质相比对应的光滑问题表现欠佳。关于非光滑优化的示例和通用算法，请参阅 [1], [2], [3], [4]。约束凸优化广泛出现在现代应用中，包括通信网络中的分布式资源分配、智能电网中的经济调度、多智能体协调、网络效用最大化、无线功率控制和分布式数据上的约束学习。这些应用推动了各种先进约束凸优化算法的发展，例如加速原始-对偶镜像动力学 [5] 和加速原始-对偶投影神经动力学方法 [6]。这些方法对于结构化的、线性的或集合约束的公式非常有效。然而，我们的重点是带有双侧不精确 Oracle 的非光滑不等式约束，这需要一种互补的基于惩罚的 Bundle 框架，这也是本文所考虑的设置。

Bundle 方法已成为求解 NSO 最突出和有效的算法框架之一。这些方法源自切割平面方法 [7], [8]，结合了下降测试——在这些论文中称为"严重步测试"——以确保算法在每次生成试验点后继续下降。Bundle 方法已被广泛应用于无约束优化 [9], [10], [11]，也可用于约束优化问题。在后者中，惩罚函数方法 [12], [13]、过滤策略 [14] 和改善函数方法 [15] 通常被采用。其中，惩罚方法在许多实际场景中具有独特优势，激发了我们的工作。首先，对于约束函数评估计算成本高昂的问题（例如涉及复杂模拟或随机抽样的问题），惩罚方法在约束评估计算需求高的场景中具有独特优势，因为它允许目标函数和约束更新的解耦，从而使算法能够更灵活地分配计算资源，在目标函数降低和可行性恢复之间进行分配，从而与那些需要每步迭代精确或高精度约束信息的方法相比，减少了整体计算负担。其次，惩罚函数天然适合处理"求和型"或可分离的问题结构，便于分解和并行计算——这是改善函数或基于过滤的策略并不总是具备的特性。此外，正如我们稍后讨论的，惩罚框架可以稳健地扩展到适应不精确 Oracle，这是我们的主要关注点。虽然基于改善函数或水平 Bundle 的方法也可以处理不精确性 [16], [17]，但它们通常需要引入和维护目标水平参数来引导算法的进展。该参数的有效更新策略对算法性能至关重要，而它的选择缺乏惩罚参数所具有的基于可行性的直觉解释。

我们方法的发展受到大规模或实际非光滑凸优化中经常遇到的具体计算权衡和实际设置的驱动。下面我们阐明为什么带有双侧不精确 Oracle 的基于惩罚的 Bundle 方法不仅仅是一个理论练习，而是对若干常见挑战的实际回应。

在约束问题的经典 Bundle 方法中，约束通常直接纳入主问题的切割平面模型中。然而，当以下一个或两个条件成立时，这种方法可能变得低效：

• **约束系统的高维性**。如果约束数量 m 很大，在每次迭代时为每个约束添加一个切割平面会显著增加二次规划（QP）子问题的规模。求解更大的 QP 可能会主导总计算成本，特别是当目标函数的函数和次梯度评估相对便宜时。惩罚策略通过将约束违反聚合成单一的标量项来避免这种膨胀。主问题主要管理目标函数的切割，保持 QP 规模小且稳定。约束通过惩罚参数更新来处理，这在计算上可以忽略不计。

• **约束评估的高成本或复杂性**。在许多应用中，获取约束函数 F 的值和次梯度可能比获取目标函数 f 的值和次梯度昂贵得多。例如，由辅助线性规划解定义的约束、复杂模拟或大规模数据拟合过程。基于惩罚的方法允许算法控制何时需要约束相关信息。严重步可以主要基于（更便宜的）目标模型下降来执行，而只有当不可行性持续存在时才会增加惩罚参数。这导致了一种解耦的评估策略，与那些要求每步迭代都有约束切割的方法相比，可以大幅减少昂贵的约束 Oracle 调用次数。

优化数值方法的设计通常假设可以访问能够提供函数和次梯度数据的 Oracle。也就是说，对于每个指定的 x? ∈ ??，我们可以计算 f(x?) 和 F(x?) 的函数值，以及每个函数的一个次梯度。然而，在实践中，获取这样的 Oracle 可能具有挑战性。例如，如果 f 取上确界形式：

f(x) := sup{g?(x) | i ∈ I}

通常 I 是一个无限集，准确计算 f(x) 及其次梯度可能是不可能的。类似问题也出现在随机规划中，例如机会约束问题 [16] 和风险规避两阶段随机问题 [18]。分布式和在线优化中也出现了相关的不精确或有噪声的一阶信息形式，例如具有随机次梯度的分布式异构多智能体优化 [19] 和具有切换成本的分布式在线优化 [20]。在这些情况下，我们通常需要使用不精确 Oracle 来估计给定 x 的信息，即 f_x ≈ f(x) 和 g_x ≈ g(x) ∈ ?f(x)，并近似求解问题。关于不精确 Oracle 的更多示例，请参阅近期工作 [21]。

凸规划中函数值和次梯度值近似评估的初步探索——具体在无约束问题或具有简单约束的背景下——可追溯到 [22]。随后，不精确近端 Bundle 策略在 [23] 中被采用。然而，[22] 和 [23] 中考虑的噪声是渐近消失的。[24] 做出了重要进展，引入了涉及不精确次梯度的非消失噪声的概念。这为进一步发展铺平了道路。在此基础上，[25] 将该方法扩展到允许对函数值和次梯度值进行近似评估，适应非消失噪声。后来，Kiwiel 在 [26] 中引入了一种称为"噪声衰减"的新技术。这项技术尤其擅长处理目标函数的上界或下界不精确 Oracle。与此同时，其他不依赖 Bundle 方法处理非消失不精确性的方法也被提出。显著示例包括 [27], [28], [29]。

在这两种情况下，基本的权衡是在求解主问题的成本与 Oracle 调用成本之间。我们的惩罚方法设计用于减少约束相关 Oracle 调用和主问题求解的频率或复杂性有益的情况。

双侧有界不精确性假设（即 f_x 和 F_x 可以是高估或低估，在固定容差 ε_f1, ε_f2, ε_F1, ε_F2 内）比文献中通常假设的单侧（通常下界）Oracle [21], [24], [25] 更现实和通用。此模型自然出现在以下实际场景中：

• **随机和基于抽样的优化**。考虑定义为期望的约束 F(x) = ??_ξ[Φ(x, ξ)] ≤ 0。使用有限样本 {ξ?}_{i=1}^N 的样本平均近似（SAA），我们得到估计 F_x = (1/N) Σ_{i=1}^N Φ(x, ξ?)。这个估计是随机的：它可能高于或低于真实值 F(x)。然而，使用集中不等式（例如 Hoeffding 不等式），通常可以计算一个以高概率成立的置信区间 [F(x) ? ε_F1, F(x) + ε_F2]。同样适用于定义为期望或大范围集合上确界的对象。我们的 Oracle 模型精确地捕捉了这种情况，容差 ε_F1, ε_F2 反映了可用的统计置信度。

• **代理建模和黑盒模拟**。在基于模拟的优化中，目标或约束值通常由从有限样本数据构建的代理模型（例如高斯过程模拟器或降阶模型）近似。这些近似固有地带有双向误差：代理模型可能在任何查询点高估或低估真实响应，但近似误差可以通过交叉验证或后验方差估计来界定。

知道误差界 ε_f, ε_F 是一个关键要求。虽然这不是平凡的，但在上述场景中这些界通常是可用的：可以推导出统计置信区间，内部求解器的最大迭代次数或残差容差提供确定性界，在分布式场景中可以使用网络延迟估计。在算法中利用这些已知边界的能力是一种优势，而非劣势，因为它允许在不确定的情况下提供严格的收敛保证。

在本工作中，我们关注涉及非消失不精确 Oracle 的非光滑约束凸优化问题。对于提供不超过真实函数值的估计的下不精确 Oracle 的研究，请参阅 [30] 和 [17] 的工作。这些研究假设 Oracle 低估了精确函数值，并且类似于精确情况，分段线性模型保持在相应的凸函数下方。然而，我们的工作考虑双向不精确 Oracle，意味着它们可以提供的估计可能高于或低于真实函数值。这种双侧不精确性自然出现在许多实际场景中，例如通过随机抽样估计函数值时（抽样误差可能为正或负），或者保守的工程设计故意高估约束以确保安全时。它也由于复杂模拟中的数值误差而出现，这些误差缺乏保证的方向性偏差。这引入了不精确信息可能高估真实函数的可能性，导致线性模型可能位于我们的目标和约束函数之上。最近，[16], [18], [31], [32], [33], [34] 的工作也研究了约束问题的不精确 Oracle；[35], [36], [37] 主要考虑了变分不等式和平衡问题；[31], [32], [34], [38] 主要分析了非凸问题；[33], [35] 仅考虑了凸情况下的下界 Oracle。据我们所知，[16], [18] 是唯一另外两个在凸不等式约束问题背景下探索此类 Oracle 的研究。与这些研究相比，我们的不精确 Oracle 更为通用。我们允许所有精度容差（包括与次梯度相关的容差）相互独立。这种灵活性为处理不等式约束凸优化问题中的非消失不精确 Oracle 提供了一个更全面和更适应性的框架。据我们所知，之前的工作尚未在精确惩罚 Bundle 框架内处理双向不精确 Oracle——这正是本文旨在填补的空白。

与 [16], [17], [18], [30] 中使用改善函数的方法不同，我们的方法使用了精确惩罚函数。与改善函数不同，惩罚函数尤其擅长处理求和型函数，并且不需要选择标量目标。这个特征可能相比改善函数赋予一定的计算优势。然而，惩罚参数的选择也带来了一系列挑战。在精确情况下，[12] 提出了有效抑制不必要的惩罚增长的惩罚更新方案，假设 Slater 约束规范成立。类似地，在我们的不精确场景中，Slater 约束规范也是一个前提条件。只要试验点是有界的，我们可以证明随着算法的推进惩罚更新将会停止，而无需预先估计惩罚参数的大小。

此外，与 [12] 相比，本工作中罚参数有限更新的证明不依赖于精确预言机的假设，因此更为通用。罚函数实现中的一个关键挑战是，罚参数可能导致约束值中的误差传播到总体罚目标函数中并占据主导地位。这一问题使得传统罚函数方法在此情境下失效。为了解决这个问题，我们提出了一种新颖的不精确模型，该模型纳入了约束函数的总容差。通过利用该模型，可以减轻约束带来的上部误差。为了与我们的模型函数相匹配，我们设计了一种新的罚策略如下：采用类似无约束的方法来实现目标函数的下降，同时通过罚更新来确保渐近可行性。相应地，我们方法中的聚合线性化误差和预测下降量被重新定义，从而区别于 [12] 等经典约束束方法。在试验点有界的假设下，聚合线性化误差和预测下降量均具有下界。已确立该算法产生的序列的每一个聚点都是问题 (1.1) 的近似解。最优精度仅由目标函数决定，而约束的不精确信息则决定了解的可行性精度。这与其他针对上部预言机的近端束方法 [16] 形成对比，在后者的方法中，最优精度取决于目标函数和约束。需要注意的是，对于涉及精确和下部预言机的情况，不存在类似的困难，可以应用经典罚策略。类似于 [16]、[17]、[26] 中的方法，采用了“噪声衰减”技术来处理噪声被认为过于“大”的情形。然而，遇到的挑战不仅归因于预言机的不精确性（如 [16]、[17]、[26] 所见），还源于我们方法中聚合线性化误差与预测下降量的概念。尽管这些困难可能无限次发生，我们的算法仍能收敛到一个近似解。现有的带有不精确预言机的约束问题的束方法主要依赖于改进函数 [39] 或假设单侧不精确性 [21]、[24]、[25]、[34]。前者可能导致更复杂的主问题，而后者无法处理随机环境中自然产生的高估误差。我们的工作通过以下方式填补了这一空白：
• 提出了一种基于罚函数的束框架，当约束评估成本高或数量多时仍保持高效。
• 引入了带有明确界的双侧不精确预言机模型，该模型涵盖了单侧情况，并捕捉了随机、分布式和近似计算环境中的现实不确定性。
• 设计了一种新颖的罚更新和模型函数，能够自动管理罚参数并隔离约束上部误差的影响，确保收敛到一个最优性和可行性精度清晰分离的解。
• 数值实验旨在验证所提出方法在各种反映这些动机场景的噪声模式下的鲁棒性和效率。

本文其余部分结构如下。第 2 节首先建立必要的背景，然后正式定义我们在分析中采用的不精确预言机类。第 3 节提出了核心思想和一个详细、可实施的算法。第 4 节专注于建立该方案的全局收敛性质。第 5 节讨论了算法的有用修改和增强。第 6 节专门通过一系列数值实验来实证验证我们的方法。我们最后总结主要发现并概述未来研究的潜在扩展。

章节片段
基本概念与符号
我们回顾次微分和 ε-次微分的概念（详见 [40]）。给定凸函数 $h:\mathbb{R}^n \rightarrow \mathbb{R}$ 和任意点 $x$，$h$ 在 $x$ 处的次微分正式定义为
$\partial h(x):=\{g \in \mathbb{R}^n \mid h(z) \geq h(x) + \langle g, z-x \rangle, \forall z \in \mathbb{R}^n\}$
其中 $\langle \cdot, \cdot \rangle$ 表示内积，$|\cdot|$ 表示欧几里得范数，该次微分的元素称为次梯度。$h$ 在 $x$ 处的 ε-次微分描述为
$\partial_\epsilon h(x):=\{g \in \mathbb{R}^n \mid h(z) \geq h(x) + \langle g, z-x \rangle - \epsilon, \forall z \in \mathbb{R}^n\}$
并且，类似地，该元素的
针对上部或下部不精确预言机的约束束方法
在本节中，我们介绍一种增强的束方案，该方案纳入了精确 $\ell_1$ 罚策略。所提出的算法旨在处理约束凸非光滑问题，其中目标函数和约束函数仅有不精确的上部或下部预言机可用。

收敛性分析
在本节中，我们专注于对所提出束方法的收敛行为进行详细研究。我们将问题 (1.1) 的可行域和最优值分别定义为：
$X:=\{x \in \mathbb{R}^n \mid F_j(x) \leq 0, j=1, \dots, m\}$
和 $f^*:=\inf\{f(x) \mid x \in X\}$。
如果点 $x^*$ 满足以下条件，则称为问题 (1.1) 的近似解：
$f(x^*) \leq f^* + \epsilon_f$
和 $F(x^*) \leq \epsilon_F + \epsilon_F 1$。
我们的收敛性分析依赖于以下固定假设：
试验点序列

修改
在本节中，我们探讨经典罚策略在仅配备下部预言机问题中的应用。此外，我们提出了一种更新罚参数的替代方案。

数值实验
在本节中，我们考察所提出算法的数值性能。所有测试均在 MATLAB 2024a 中实现，并在配备 2.30 GHz CPU 的 PC 上执行。为求解二次规划子问题，我们使用了 MATLAB 优化工具箱中包含的 QuadProg.m 函数。

结论
本文提出了一种新颖的罚策略，用于约束凸非光滑优化的不精确近端束方法。与假设单侧（下部或上部）不精确预言机194470 的方法不同，我们的框架系统地容纳了目标函数和约束函数的双向不精确预言机，其中近似值和次梯度可能会在固定误差容差范围内高估或低估精确量。通过整合精确罚函数

作者贡献
所有作者均已阅读并批准最终手稿。Ming Huang 和 Hong Kai Song 撰写了主要手稿正文。Ming Huang、Hong Kai Song 和 Xiao Dan Chao 主要负责理论分析和数值实验，而 Ming Gu、Si Da Lin 和 Suo Suo Yang 主要贡献于算法设计和理论分析。

未引用参考文献
[44], [45], [46], [47], [48], [49], [50], [51]

CRediT 作者贡献声明
Hong Kai Song: 写作 – 初稿，软件，方法论，调查，正式分析。
Ming Huang: 写作 – 初稿，验证，项目管理，方法论，调查，资金获取，正式分析，概念化。
Ming Gu: 验证，方法论，概念化。
Xiao Dan Chao: 写作 – 初稿，软件，调查，正式分析，概念化。
Si Da Lin: 方法论，调查，概念化。
Suo Suo Yang: 方法论，

利益冲突声明
作者声明无利益冲突。

Hong Kai Song | Ming Huang | Ming Gu | Xiao Dan Chao | Si Da Lin | Suo Suo Yang
中国 大连海事大学 理学院