约束耦合凸混合整数的递阶分布式优化

欧洲计算优化杂志11（2023）100058约束耦合凸混合整数的递阶分布式优化使用对偶函数近似的程序Vassilios Yfantisa，Simon Wenzelb，c，Achim Wagnerd，马丁·鲁斯科夫斯基a，d，塞巴斯蒂安·恩格尔ca机床和控制系统主席，机械和工艺工程系，TU Kaiserstern，Gottlieb-Daimler-Straße 42，67663 Kaiserstern，Germanyb赢创运营有限公司，Paul-Baumann-Str. 1，45772 Marl，Germanyc过程动力学和操作组，生物化学和化学工程系，多特蒙德大学，Emil-Figge-Str. 70，44227 Dortmund，德国d创新工厂系统，德国人工智能研究中心Trippstadter Str. 122，67663 Kaiserstadern，GermanyARTIcLE IN fO ABSTRA cT保留字：分布式优化对偶分解非光滑优化次梯度法Bundle法ADMM二次近似拟牛顿提出了两种基于对偶分解的分布式优化这两种算法都依赖于原始优化问题的对偶函数的二次近似对偶变量在每次迭代中通过近似对偶函数的最大化来第一个算法通过解决回归问题来近似对偶函数，基于从先前迭代中收集的对偶函数的值第二种算法通过拟牛顿格式更新二次近似的参数。这两种算法采用步长约束的更新的对偶变量。此外，存储来自先前迭代的次梯度，以便构造切割平面，类似于用于非光滑优化的束方法然而，不是使用切割平面来制定对偶函数的分段线性过近似，而是使用它们来构造* 通讯作者。电子邮件地址：vassilios. mv.uni-kl.de（V.Yfantis）。https://doi.org/10.1016/j.ejco.2023.1000582192-4406/© 2023作者。由Elsevier Ltd代表欧洲运筹学协会（EURO）出版。这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表欧洲计算优化杂志期刊主页：www.elsevier.com/locate/ejco2诉Yfantis等人/EURO Journal on Computational Optimization 11（2023）100058更新步骤的有效不等式为了证明算法的有效性，在一个大的约束二次、凸和混合整数基准问题集上对它们进行了评估，并与次梯度法、束信任法、交替方向法进行了比较和二次近似协调算法。结果表明，在大多数情况下，所提出的算法在所需的迭代次数和所解决的基准问题的数量版权所有2023作者。由Elsevier Ltd代表欧洲运筹学协会（EURO）出版。这是CCBY-NC-ND许可证（http：creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍优化的许多工业应用需要通过代理网络解决系统范围的问题[48]。如果涉及大量代理，则在这样的设置中以集中方式解决系统范围的优化问题在此外，近年来，在生产系统中，子系统的模块化和自主性越来越强[56]。这就产生了分布式决策结构，其中所涉及的子系统具有一定的自主权，并在仅访问本地信息的情况下追求个人目标[72]。在这些情况下，子系统之间或子系统与协调单元之间的信息交换通常受到限制，因为子系统不想共享私人信息，例如，它们的目标函数、局部约束、生产参数等。[30、41]。这通常是工业综合体的情况，其中生产系统通过相互连接的材料和能源网络耦合[68]。所涉及的子系统可能不愿意或不能交换系统范围优化问题的集中解决方案所需的信息，例如，因为它们属于不同的业务单位或不同的公司。另一个需要解决大规模优化问题的领域是机器学习[24，58]。除了底层优化问题的大小之外，数据主权在许多机器学习应用中也起着重要作用[39]。训练数据可以分布在网络的多个节点上。由于带宽限制或隐私问题，在不同节点之间或节点与协调器之间共享此数据可能是禁止的[35]。分布式优化方法通过将聚合优化问题分成更小的子问题、局部地求解子问题并且通过合适的机制协调这些解使得子问题的协调解收敛到系统范围的解并且满足系统范围的约束来提供规避上述问题的方式分布式优化算法的设计涉及分解方法和同步机制的选择，诉Yfantis等人/EURO Journal on Computational Optimization 11（2023）1000583取决于子问题和协调实例之间可能的数据通信分解方法的例子包括博弈论方法[71]，基于人口的方法[3]，原始分解[53]和对偶分解[20]。本文重点研究对偶分解，其中通过向子问题中引入额外变量来放松耦合子问题的系统范围约束，以分布式方式求解修改后的子问题，并通过迭代地调整额外变量来协调求解过程这使得有可能实现高度的隐私，因为没有或很少的敏感信息必须在子问题之间共享子问题的协调可以通过与子问题交换信息（分层）的中央协调算法，通过在子问题之间直接交换信息（网络优化）或通过以完全分散的方式解决子问题（非合作游戏）[71]）来执行在这项工作中，分层算法被认为是协调的子问题的解决方案，通过迭代地适应和广播的额外的变量，在这里的对偶变量，从放松的系统范围的耦合约束。一方面，层次结构确保了没有敏感的信息必须共享子问题之间，因为通信只建立在协调员和子问题之间。另一方面，中央协调器的存在使得能够收敛到聚集问题的全系统最优，如果必须满足全系统耦合约束，则通过完全分散的方法通常不可能实现这一点子问题和协同问题之间共享的信息的类型和数量协调器在分布式优化算法的效率交换的信息可以包括子系统对系统范围约束函数[44]或系统范围约束的残差[69]的贡献、每次迭代中子系统的最优目标函数值、子系统的目标函数和约束的梯度前两个选择导致子系统的高度隐私，而交换子系统解决方案的全部信息的算法的动机是与系统范围的解决方案相比减少内存需求或计算时间，在分层分布式优化算法的迭代中，所有子问题并行求解并将信息返回给协调器，即，它们以同步的方式被优化相反，异步算法只需要在每次迭代中解决子问题的一个子集，导致收集的信息和计算效率之间的权衡[11]。如果所有子问题在每次迭代中都得到解决，通常需要较少的迭代次数。基于对偶分解的算法通常表现出缓慢的收敛速度。这一问题已得到解决，例如，Maxeiner和Engell [44]和Wenzel等人。[69]其中有效地使用了来自先前迭代的信息。在本文中，提出了一种新的算法，它使用了一些元素的二次近似协调（QAC）算法提出的Wenzel等人。[69]第二章。与质保局相比，4诉Yfantis等人/EURO Journal on Computational Optimization 11（2023）100058l=1算法，新的算法，二次近似对偶上升（QADA），近似的对偶函数的系统范围内的优化问题的二次函数在每次迭代。这需要在每次迭代时交换子问题的拉格朗日量的值，但仍然保持局部约束和对系统范围约束的贡献如下文所示，这提高了具有实值决策变量的凸问题的收敛速度，特别是导致混合整数规划的高效分布式解。对偶函数的基于回归的近似需要初始化阶段，其中收集必要数量的初始数据点。这通过基于拟牛顿更新来近似对偶函数的算法来避免，该算法被称为拟牛顿对偶上升（QNDA）算法。该算法首先在[73]中介绍，并在本文中详细讨论和比较基准本文的其余部分组织如下：第2节介绍了主要的数学符号。第三节介绍了约束耦合优化问题的对偶和对偶分解的概念。几个分布式优化算法，这将作为新提出的方法的参考讨论在第4节。讨论的重点是算法，采用层次协调结构，只有一阶信息之间的子问题和协调员共享。文中还简要讨论了采用不同通信结构、交换信息和同步策略的其它相关算法第5节讨论了基于光滑代理函数的优化来更新对偶变量的算法。这包括在[69]中引入的QAC算法以及新提出的算法QADA和QNDA，它们计算对偶函数的二次代理函数基于同类问题和类似算法的已知结果，在本节的最后以半形式化的方式讨论了这些算法对于不同类型问题的收敛新算法的性能，与已知的approaches相比，在第6节中，针对不同问题类的大量基准问题进行了评估。最后，在第7节中对全文进行了总结，并对未来的研究进行了展望。2. 符号我们使用粗体大写字母表示矩阵（X），使用粗体小写字母表示向量（x）。符号[x]l表示向量x的第l个元素.类似地，[X]l，j表示矩阵X的第（l，j）个元素。只包含1的向量用1表示，而只包含0的向量用0表示。I表示适当维数的单位矩阵。分布式优化算法的迭代指数由t表示。迭代t中变量x的值记为由x（t），而xi表示变量属于子问题i。欧几里德范数表示为：nnk=1 |2表示弗罗贝纽斯|2 denotes theFrobeniusΣ诉Yfantis等人/EURO Journal on Computational Optimization 11（2023）1000585XXΣΣ∈∈∈∈ X <$X→ ∈{×}∈{}i∈Ii∈I矩阵的范数SRn×n表示具有n行/列的对称矩阵集合的相对内部由relint（）表示符号x表示最优化问题的最优解3. 对偶与对偶分解在这项工作中，我们考虑优化问题的形式min，...，xNsfi（xi），（1a）i∈IS. t.Aixi≤b，（1b）i∈Ixi∈Xi，i ∈ I.（1c项）（1）描述了一个由Ns个子问题i= 1，...，Ns。每个子问题都有自己的一组决策变量xiKnxi和一个目标函数fi：KnxiK。本文考虑KR，RZ，即连续或混合整数优化问题。子系统通过系统范围的约束（1b）耦合，也称为耦合、复杂化或网络约束。项Aixi，其中AiRnb×nxi可以解释为取决于决策变量xi的共享有限资源的利用率，而bRnb表示这些资源的可用性。除了系统范围的约束外，每个子问题i还包含单独的约束xiiKnxi，其中i是非空紧集。我们假设系统范围的目标函数在子系统目标函数值中是加性的。目标是最小化所有子问题（1a）的目标函数之和，也称为社会福利目标[57]，同时满足系统范围的约束（1b）以及个体约束（1c）。问题（1）在目标函数上是可分离的，子问题之间仅通过约束耦合。这类问题被称为约束耦合优化问题.因此，系统范围或中心问题可以通过引入对偶变量λRnb（也称为拉格朗日乘数）来分解用于耦合约束。有了对偶变量，拉格朗日函数可以用公式表示，L（x，λ）：=<$fi（xi）+λT<$Aixi−λTb，（2）其中x =[xT，.，xT] T。基于拉格朗日函数，1Nsd（λ）：=Xinfi∈IL（x，λ）（3）i∈Xi，可以定义。对偶函数是对偶变量λ的函数。对偶变量的域是λ≥0，源于Karush-Kuhn-Tucker条件，X16诉Yfantis等人/EURO Journal on Computational Optimization 11（2023）100058−∞ΣΣΣ1Ns我从系统范围的约束（1b）是不平等的事实[51]。通常，对偶变量λ的域由拉格朗日函数（2）从下有界的所有值组成，即，d（λ）>的所有值。对偶函数（3）的一个重要性质是，它的值总是为系统范围问题（1）的目标值提供一个下界（参见： [9]）。由于对偶函数为系统范围问题的目标值提供了一个下界，因此在最优解x∈ N的情况下也是如此。自然，人们会对最佳可达到的下限感兴趣，对应于对偶函数的最大值。找到这个最大值被称为对偶问题，最大d（λ），（4a）λ∈RnbS. t. λ≥ 0。（4b）相反，系统范围的问题（1）被称为原始问题。我们用λ表示对偶问题（4）的最优解。由于对偶函数的下界性质，fi（xi）≥d（λ）（5）i∈I在原始最优解和对偶最优解之间。不等式（5）称为弱对偶。一个可行原始解和相应的可行对偶解的目标值之间的差异称为对偶间隙，DG=fi（xi）− d（λ）。（六）i∈I如果原始问题，即，系统范围问题（1）是凸的，满足约束资格条件，最优对偶间隙为零。 这意味着，fi（xi）=d（λ）.（七）i∈I这种情况被称为强对偶性。一个常用的约束限定条件是斯莱特与<$x ∈ relint（X）<${x ∈ Rnx|，Aixi−1，注意，由于耦合约束（11b）是等式，因此对偶变量的域是λR。对偶函数的值现在取决于单个约束（11c）是否有效。可以区分两种情况情况1：x11（无效约束）<对于固定的λ，对偶函数（13）的值可以通过将拉格朗日函数（12）的梯度设置为零来计算：L（x1，x2，λ）=. x1+ λ=0x1=−λ，x2= 1 − λ。（十四）将x1和x2的值代入公式12，d（λ）=−λ2+λ，λ> −1。（十五）情况2：x1= 1（活动约束）将约化拉格朗日函数的梯度设置为零，<$L（1，x2，λ）= x2− 1+ λ = 0 <$x2 = 1 − λ。（十六）同样，将x1和x2的值代入（12）中，得到d（λ）=−λ2+1。5 λ+0。5，λ≤− 1。（十七）问题（11）的对偶函数由下式给出：d（λ）=−λ2+1。5 λ+0。5，λ≤−1。（十八）很容易看出，对偶函数是连续的，因为λlim + d（λ）= λ lim − d（λ）= −2。（十九）→−1 →−1然而，对偶函数没有连续导数，λlim+d（λ）=λ lim+−2λ+1=3，（20a）→−1 →−1λlim −d（λ）=λ lim− −2λ +1。5= 4。第5条，（20b）→−1 →−1这意味着它并不平滑。因此，由于对偶函数总是凹的，所以对偶问题maxd（λ）（21）10诉Yfantis等人/EURO Journal on Computational Optimization 11（2023）100058λ∈R诉Yfantis等人/EURO Journal on Computational Optimization 11（2023）10005811是一个凸的，但非光滑的优化问题。不平滑是由一组不断变化的活动单个约束引起的。这种非光滑性对于对偶优化问题是典型的。在基于对偶分解的分布式优化的背景下，在下面的部分中回顾了旨在解决非光滑对偶问题的算法4. 基于对偶分解的分布式优化研究综述对偶分解的一般思想是由Everett [20]引入的。对偶分解可以被看作是一个层次化的方案，其中协调算法计算对偶变量的值，这些值被传递给子问题。子问题解决其各自的优化问题的对偶变量的接收值和通信的结果回到协调器。向协调器传达什么基于对偶分解的分布式优化可以被解释为一种市场机制，其中拍卖者为共享资源设定价格，子问题根据这些价格计算其最优资源利用率[62，69]。在这种情况下，二元变量被称为价格或影子价格[28]。在本节中，讨论了那些基于对偶分解的分布式优化算法，这些算法用作所提出的算法的比较的参考这包括次梯度法、捆绑信任法（BTM）和交替方向乘子法（ADMM）。对其他相关的基于对偶分解的算法也作了简要的评述。4.1. 次梯度法基于对偶分解的最简单的分布式优化算法在该算法中，对偶变量沿对偶函数的次梯度方向更新。向量ψ∈Rnχ是凹函数φ：Rnχ→R的次梯度，χ0∈Rnχ，如果φ（χ）≤φT（χ−χ0）+φ（χ0）（22）对所有的χ∈domφ成立。所有次梯度的集合包括函数φ（χ）在点χ0[2]处的次梯度φ（χ0次梯度是非光滑（不可微分）凸函数的梯度的推广。注意，（22）从技术上定义了凹函数的超梯度然而，术语次梯度在文献中通常用于凸函数和凹函数。在几何上，次梯度/超梯度是凸/凹函数的支撑超平面的法向量。图图1示出了可区分（χ0）和不可区分（χ'0）点的不同子梯度在分布式优化的次梯度方法中，12诉Yfantis等人/EURO Journal on Computational Optimization 11（2023）100058x∈Xii·我pDpD图1.一、可区分（χ0）和不可区分（χ'0）点的次梯度的几何解释因此，原始变量xi和对偶变量λ根据下式更新：（t+1）（t）λi∈I，xi=arg minLi（xi，λ（23 a）λ（t+1）=<$λ（t）+α（t）g（λ（t））<$+（23b）其中g（λ（t））是对偶函数在λ（t）处的一个子级nt，[]+表示在正正交点上的投影。注意，原始变量（23a）的更新可以通过针对对偶变量的给定值求解局部优化问题以分布式方式执行对偶函数的次梯度可以通过评估原始变量x（t+1）[71]的系统范围约束来计算，即，g（λ（t））=. <$Aix（t +1）− b<$∈<$d（λ（t））.（二十四）i∈I更新步骤（23b）在对偶的次梯度的方向上更新对偶变量。步长参数α（t）对算法的收敛性起着重要的作用。如果它选择得太大，算法可能会发散。如果选择得太小，则不会取得实质性进展。最佳步长可以通过对偶函数梯度的Lipschitz常数来定义[49]。但是，在分布式优化设置中，此信息通常不可用。对于实际应用，步长在迭代过程中进行调整[4]。在本文中，我们使用欧氏范数（2-原始残差ωw（t）ω2和对偶残差ωw（t）ω2的范数）低于预定义的阈值或达到最大迭代次数，即.w（t）（二十五）原始残差表明系统范围约束的可行性。如果这些约束（1b）被设为不等式，则原始残差被定义为：诉Yfantis等人/EURO Journal on Computational Optimization 11（2023）10005813=αD←←我，p←p我p我p2p2我ppi∈ILi∈I[w（t）] l：= max.Aix（t）− b，0，l= 1，.， 北湾（二十六）如果它们被视为相等，则定义为w（t）：=Aix（t）−b，（27）也就是说，等于次梯度。我们还使用原始残差的范数来计算步长参数，如[69]所提出的α（t）（0）max {{0}w（0）}，.，w（t）（二十八）对偶残差表示对偶变量收敛到一个固定值，定义为：w（t）：= λ（t +1）− λ（t）。（二十九）算法1总结了次梯度方法（SG）。注意，步骤5算法1次梯度法（SG）。要求：λ（0），α（0），λp，λd，tmax1：t02：重复3：t t+14：将λ（t）发送到所有子问题5：对于所有i=1，.，Nsdo6：x（t+1）←arg minx∈XLi（xi，λ（t））7：将Aix（t+1）发送给协调器8：结束9：g（λ（t））←Aix（t+1）−b10：如果约束is∈（I1b）arie不等式s，则11：对于所有l=1，...，nbdo12：[w（t）] l← maxg（λ（t）），0pl13：结束14：否则，如果约束（1b）是等式，则15：w（t）←g（λ（t））16：如果结束17： α（t）← α（0）/max {w（0）<$2，.， w（t）18：如果约束（1b）是不等式，则19：λ（t+1）[λ（t）+α（t）g（λ（t））]+20：否则，如果约束（1b）是等式，则21：λ（t+1）←λ（t）+α（t）我我14诉Yfantis等人/EURO Journal on Computational Optimization 11（2023）100058g（λ（t））22：结束，如果23：w（t）←λ（t+1）−λ（t）24：直到（t≥tmax）p d25：returnλ（t）D诉Yfantis等人/EURO Journal on Computational Optimization 11（2023）10005815B{−}J{}{− −}4.2. 捆绑信任方法次梯度法描述在第二节。4.1仅采用先前迭代的次梯度以更新对偶变量。然而，与梯度相反，次梯度不一定为对偶函数提供上升方向。这通常会导致收敛速度缓慢一种通常更有效的算法是bundle方法[43]。Bundle方法是求解非光滑优化问题最有效的算法之一[2]。因此，它们已经在基于对偶分解的分布式优化的上下文中被用来解决非光滑对偶问题，例如，用于分布式模型预测控制[55]或用于能源网络的协调[75]。此外，束方法也广泛用于其他必须解决非光滑问题的领域，例如机器学习，由于正则化项经常遇到非光滑性[37]。在下文中，呈现如在[73]中描述的根据[2]的捆绑信任方法（BTM）Bundle方法的思想是利用从多次迭代中收集的次梯度信息来构造非光滑凹对偶函数d（λ）的分段线性为此，数据B（t）={（λ（j），d（λ（j）），g（λ（j）∈ Rnb × R × Rnb |1 ≤ j ≤ t}（30）存储在每次迭代中。被称为束。如前一节所示，由次梯度定义的超平面是其对应函数的过逼近器。在迭代t中对偶函数的切割平面modeld（t）（λ）被定义为：d（t）（λ）：=mind（λ（j）） +gT（λ（j））（λλ（j）），（31）j∈J（t）哪里（t）1，.，t表示所使用的数据点的子集。由于存储所有过去迭代的对偶变量、对偶值和子梯度可能需要大量的存储内存，因此我们只存储特定迭代年龄的束信息τ，J（t）：={max {1，t−τ+1}，.， t}。（三十二）图2示出了非光滑对偶函数的切割平面模型。该近似值可以等效形式写成：d（t）（λ）=mind（λ（t）） +gT（λ（j））（λλ（t））β（j，t），（33）j∈J（t）线性化误差β（j，t）=d（λ（t））−d（λ（j））−gT（λ（j））（λ（t）−λ（j）），<$j∈ J（t）.（三十四）16诉Yfantis等人/EURO Journal on Computational Optimization 11（2023）10005822图二.剖切平面模型的图示。束信任方法通过解决方向发现问题来计算每次迭代中的搜索方向s（tMaxs∈Rnbd（t）（λ（t）+s），（35a）S. t.αs≤ α2 ≤ α（t），（35 b）λ（t）+s ≥ 0。（35 c）约束（35b）表示信任区域，防止过于激进的更新步骤.对于信赖域的半径，我们使用Eq。（28）. 约束（35c）确保更新的对偶变量的可行性，并且如果系统范围的约束（1b）是相等的，则可以省略。它取代了（23b）中使用的可行集上的投影。问题（35）仍然是非光滑的，可以重写为光滑的二次方向寻找问题Maxv∈R，s∈Rnbv，（36a）S. t.αs≤ α2 ≤ α（t），（36 b）gT（λ（j））s−β（j，t）≥v，<$j∈ J（t），（36 c）诉Yfantis等人/EURO Journal on Computational Optimization 11（2023）10005817x∈Xii我我λ（t）+s ≥ 0。（36d）总而言之，捆绑信任方法（BTM）在每次迭代中根据下式更新原始变量和对偶变量：（t+1）（t）λi∈I，xi=arg minLi（xi，λ）、（37a）s（t） =arg maxv∈R，s∈RnbS. t. （36b）-（36d），v，（37b）λ（t +1）= λ（t）+s（t）。（37c）束方法通常采用空步骤，即，λ（t+1）=λ（t），以计算a新的次梯度在当前的梯度和改进的近似。在基于对偶分解的分布式优化的情况下，在零步之后将获得相同的次梯度。因此，在每次迭代中，根据（37c）更新对偶变量。注意，在BTM的情况下，除了对次梯度gi（λ（t））的贡献之外，子问题还必须将它们的贡献传达给对偶函数。di（λ（t））=fi（x（t+1））+λ（t），Tgi（λ（t））=Li（x（t+1），λ（t））（38）到协调员。终止准则与次梯度法相同。本文考虑了一种聚集束方法，即，协调器将所有子系统对对偶函数和次梯度的贡献算法2总结了捆绑信任方法。再次注意，步骤6-4.3. 交替方向乘子解决非光滑对偶问题的另一种方法是通过进一步凸化拉格朗日函数来平滑这在增广拉格朗日方法中使用[1]。增广拉格朗日方法的问题是失去了可分性。交替方向乘子法（ADMM）是增广拉格朗日方法的一种推广，从而保持了可分离性它首先在[23]和[22]中介绍，在那里它被应用于寻找微分方程的解自从Boyd等人推广以来，近年来它获得了极大的关注[8]。在其标准形式中，ADMM算法解决了以下形式的问题：minx1∈Rnx1，x2∈Rnx2f1（x1）+f1（x2）（39 a）S. t. A1x1+A2x2=b，（39b）18诉Yfantis等人/EURO Journal on Computational Optimization 11（2023）100058←Σ←Ax−biL（x，λ）−λb，p←←D2我（i∈I我（t）12算法2捆绑信任方法（BTM）。要求：λ（0）、α（0）、τ、λp、λd、tmax1：t←（0）02：B ←{}3：重复4：t t+15：将λ（t）发送到所有子问题6：对于所有i=1，.，Nsdo7：x（t+1）←arg minx∈XLi（xi，λ（t））8：将Aix（t+1）和Li（x（t+1），λ（t））发送到我9：协调员10：结束11：g（λ（t））12：d（λ（t））←十三（t）（t+1）我（t+1）（t）（t），T我（（十四日：B如果← B<${（λ，d（λ），g（λ））}的情况下，约束（1b）是不等式，则15：对于所有l=1，...，nbdo16：[w（t）] l← maxg（λ（t）），0pl17：结束18：否则，如果约束（1b）是等式，则19：w（t）←g（λ（t））20：如果结束21： α（t）← α（0）/max {w（0）<$2，.， w（t）p p22： J（t）← {max {1，t-τ +1}，.， t}23：如果约束（1b）是不等式，则24：s（t） arg maxv∈R，s ∈Rnb v，s。t. （36b）-（36d）25：否则，如果约束（1b）是等式，则26：s（t） arg maxv∈R，s ∈Rnb v，s。t.（36b）、（36c）27：如果结束28：λ（t+1）←λ（t）+s（t）29：w（t）←λ（t+1）−λ（t）30：直到（t≥tmax）p d31：returnλ（t）通过定义一个增广拉格朗日函数L<$ρ（x1，x2，λ）：=f1（x1） +f1（x2） +λT（A1x1+A2x2−b）+ρ<$A1x1+A2x2−b<$2。（四十）然后，根据下式以交替方式更新原始变量：x（t+1）=arg minL<$p（x1，x（t），λ（t）），（41a）1x1∈Rnx12x（t+1）=arg minL<$p（x（t+1），x2，λ（t）），（41b）2x2∈Rnx21λ（t +1）=λ（t）+ρ（A1x（t +1）+A2x（t +1）− b）。（41c）原始变量（41a）和（41b）的更新不能并行执行。在本文中，我们考虑的问题是多个i∈I我我诉Yfantis等人/EURO Journal on Computational Optimization 11（2023）10005819子系统通过共享有限资源（1）连接。这种情况适合使用的最佳交换版本的20诉Yfantis等人/EURO Journal on Computational Optimization 11（2023）100058∈ΣΣρ2我Ns∈I我我我我我我i∈Ii∈Ii∈Ii∈Ii∈I如[8]中所述，ADMM（第7.3.2）和[64]（第3.5.4）。该公式依赖于辅助变量ziRnb的引入，其可以被解释为子问题i的可行资源利用率。使用辅助变量，问题（1）可以重新表述，min，...，xNsfi（xi），（42a）i∈IS. t. Aixi≤zi，ni∈I，（42b）zi=b，（42c）i∈Ixi∈Xi，i ∈ I.（42d）问题（42）的各个增广拉格朗日函数被定义为：L （x，λ，z）：=f（x）+λT（Ax-z）+Δx-z.（四十三）i，ρ i i i ii我我我2i i i2在每次迭代t中，根据下式更新原始、辅助和对偶变量：<$i∈I，x（t+1）=argminL<$i，ρ（xi，λ（t），z（t））（ 44a）我（t+1）xi∈Xi（t+1）我（t+1）i∈I，zi=Aixi−ave（Ax−b）（44 b）哪里λ（t+1）=[λ（t）+ρ（t） ave（Ax（t+1）−b）]+（44c）ave（Ax（t+1）−b）：1.Ax（t+1）−b（45）i∈I表示系统范围约束的平均值。注意，现在可以并行执行主变量（44a）的更新。辅助变量（44b）的更新步骤确保满足（42c）[64]，z（t+1）==Aix（t+1）−Nsave（Ax（t+1）−b）（46 b）我=Aix（t +1）−。Aix（t+1）−bX1