Online distributed algorithms for mixed equilibrium problems in dynamic environments
Hang Xu, Kaihong Lu, Yu-Long Wang, Qixin Zhu · 2024
Read Online distributed algorithms for mixed equilibrium problems in dynamic environments by Hang Xu, Kaihong Lu, Yu-Long Wang, Qixin Zhu (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-19399.txt.
Introduction
Hang Xu and co-authors let a team of agents solve shifting balance problems online, in work from 2024. Each agent knows only its own cost term and limits, and talks only with near neighbors over links that change with time. The joint goal shifts as data arrive, and agents learn the true terms only after they act.
Their method mixes mirror descent steps with a primal-dual scheme. Scores are kept as regret against the best path over time, plus a tally of broken joint limits. Both grow slower than the time span, under mild terms. A noisy-gradient version holds the same promise with high chance. Worked cases back the math.
Catalog record
| CREATOR | Hang Xu, Kaihong Lu, Yu-Long Wang, Qixin Zhu |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-19399
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Online distributed algorithms for mixed equilibrium problems in dynamic environments Hang Xu, Kaihong Lu, Yu-Long Wang, Qixin Zhu Abstract In this paper, the mixed equilibrium problem with coupled inequality constraints in dynamic environments is solved by employing a multi-agent system, where each agent only has access to its own bifunction, its own constraint function, and can only communicate with its immediate neighbors via a time-varying digraph. At each time, the goal of agents is to cooperatively find a point in the constraint set such that the sum of local bifunctions with a free variable is non-negative. Different from existing works, here the bifunctions and the constraint functions are time-varying and only available to agents after decisions are made. To tackle this problem, first, an online distributed algorithm involving accurate gradient information is proposed based on mirror descent algorithms and primal-dual strategies. Of particular interest is that dynamic regrets, whose offline benchmarks are to find the solution at each time, are employed to measure the performance of the algorithm. Under mild assumptions on the graph and the bifunctions, we prove that if the deviation in the solution sequence grows within a certain rate, then both the dynamic regret and the violation of coupled inequality constraints increase sublinearly. Second, considering the case where each agent only has access to a noisy estimate on the accurate gradient, we propose an online distributed algorithm involving the stochastic gradients. The result shows that under the same conditions as in the first case, if the noise distribution satisfies the sub-Gaussian condition, then dynamic regrets, as well as constraint violations, increase sublinearly with high probability. Finally, several simulation examples are presented to corroborate the validity of our results. keywords Multi-agent systems; Mixed equilibrium problems; Online distributed algorithms. † † thanks: [ † † address: College of Electrical Engineering and Automation, Shandong University of Science and Technology, Qingdao 266590, China † † address: School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200444, China † † address: School of Mechanical Engineering, Suzhou University of Science and Technology, Suzhou 215009, China footnoteinfo] Corresponding author: Kaihong Lu. , , , 1 Introduction In Equilibrium problems (EPs), one shoud find a point to guarante the non-negativity of a bifunction, which takes two arguments as inputs and produces a single output. More specifically, one of the two argements is freely changeable. In recent years, EPs have received increasing attention [ 1 ] - [ 3 ] . This is due to their wide applications in many fields such as electrical networks [ 4 ] , transportation networks [ 5 ] and learning systems [ 6 ] . For example, to analyze ampere-voltage characteristics of circuits formed by the interconnection of electrical devices like generators, diodes and inductors, currents in m loops are usually computed by finding x\in\Omega such that \displaystyle\langle Ax+b,y-x\rangle+F(y)-F(x)\geq 0,~\forall y\in\Omega (1) where \Omega\in\mathbb{R}^{m} , F(\cdot):\mathbb{R}^{m}\rightarrow\mathbb{R} is the electrical potential of diodes and is usually nonlinear, A\in\mathbb{R}^{m\times m} and b\in\mathbb{R}^{m} are determined by the resistance and voltage source in the circuit, respectively. Problem (1) is a typical EP. If the bifunction is formed by the sum of multiple bifunctions, then such an EP becomes a mixed equilibrium problem (MEP). To achieve a solution of EPs or MEPs, various centralized strategies have been proposed [ 7 ] - [ 11 ] . In practical applications such as large-scale electrical networks [ 12 ] and mobile ad-hoc networks [ 13 ] , achieving the global information is usually impossible. Thus, distributed strategies are more desired. Recently, some distributed algorithms have been proposed for MEPs. For example, for MEPs with a set constraint, a distributed extragradient algorithm is proposed in [ 14 ] . For the case with multiple set constraints, a distributed primal-dual algorithm involving a fixed step size is proposed in [ 15 ] . To reduce the communication cost, an event-triggered distributed strategy is developed in [ 16 ] . Moreover, consider the case where the cut property of bifunctions is absent, an auxiliary optimization-based distributed ergodic algorithm is presented in [ 17 ] . If the bifunction in an MEP is time-varying and only available to agents after decisions are made, then the MEP is called an online MEP. Accordingly, an algorithm for solving such an MEP is referred to as an online algorithm. It is noticed that in all the aforementioned works, MEPs are offline, and feasible sets are only constrained by convex sets. On the one hand, dynamic environments arise in many practical cases. For example, in problem (1), due to the conductivity of some electronic components such as diodes and inductors, is often influenced by temperature and air pressure, the bifunction in the problem is time-varying, and changes can only be seen in hindsight. On the other hand, in practical applications such as wireless sensor networks [ 18 ] and plug-in electric vehicles [ 19 ] , coupled inequality constraints are often used to describe some complex and limited resource constraints. Motivated by these observations, we try to study online MEPs with coupled inequality constraints in a distributed manner. Unfortunately, the results and analysis tools for offline MEPs are not applicable to the online cases. In offline MEPs, the asymptotic convergence of an algorithm to a fixed solution is proved by using supermartingale convergence theory [ 14 ] . However, in online cases, the solution is time-varying and the deviation in the solution sequence may not be bounded, then the supermartingale convergence theorem is not applicable. A popular and common way for addressing online problems is the regret, and the effectiveness of online algorithms is usually measured by the sublinearity of the regret [ 28 ] - [ 33 ] . In fact, online MEPs are also related to online distributed optimization. Specifically, when the bifunction is in the form of the difference between two same functions, MEPs are reduced to distributed optimization [ 20 ] . Recently, online distributed optimization has been extensively studied [ 21 ] - [ 31 ] . For example, online distributed optimization problems without constraints are studied in [ 21 ] and [ 22 ] . For the cases with set constraints, an online distributed saddle point algorithm is proposed in [ 23 ] , an online distributed mirror descent algorithm is developed in [ 24 ] , and an online distributed dual averaging algorithm is designed in [ 25 ] . With a linear inequality constraint considered, an online distributed algorithm based on a safety parameter estimation is proposed in [ 26 ] . Considering the case with nonlinear inequality constraints, an online distributed projection-based primal-dual algorithm is presented in [ 27 ] . Moreover, to address coupled inequality constraints, various online distributed algorithms based on primal-dual strategies are developed in [ 28 ] - [ 31 ] . Different from distributed optimization where the goal of agents is to minimize a single-variable function, in MEPs, agents needs to seek a point in a constraint set to ensure that the bifunction is nonnegative. It is worth pointing out that the bifunctions are coupled through a pair of variables, one of which is freely changeable. More significantly, the two variables may be inseparable, and the bifunctions may be nonlinear with