检索结果-内蒙古大学图书馆

Online distributed Optimization With Nonconvex Objective Functions: Sublinearity of First-Order Optimality Condition-Based Regret

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2022年第6期67卷 3029-3035页

作者： Lu, Kaihong Wang, Long Jiangsu Univ Sch Elect & Informat Engn Zhenjiang 212013 Jiangsu Peoples R China Peking Univ Coll Engn Ctr Syst & Control Beijing 100871 Peoples R China

In this article, the problem of online distributed optimization with a set constraint is solved by employing a network of agents. Each agent only has access to a local objective function and set constraint, and can only communicate with its neighbors via a digraph, which is not necessarily balanced. Moreover, agents do not have prior knowledge of their future objective functions. Different from existing works on online distributed optimization, we consider the scenario, where objective functions at each time step are nonconvex. To handle this challenge, we propose an online distributed algorithm based on the consensus algorithm and the mirror descent algorithm. Of particular interest is that regrets involving first-order optimality condition are used to measure the performance of the proposed algorithm. Under mild assumptions on the communication graph and objective functions, we prove that regrets grow sublinearly. Finally, a simulation example is worked out to demonstrate the effectiveness of our theoretical results.

关键词： Optimization Linear programming distributed algorithms Convex functions Mirrors Standards Mathematical model distributed nonconvex optimization multiagent systems (MASs) online optimization

来源：评论

学校读者我要写书评

暂无评论

Finite-Time distributed Flow Balancing

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2022年第12期67卷 6926-6933页

作者： Hadjicostis, Christoforos N. Dominguez-Garcia, Alejandro D. Rikos, Apostolos, I Univ Cyprus Dept Elect & Comp Engn CY-1678 Nicosia Cyprus Univ Illinois Dept Elect & Comp Engn Urbana IL 61801 USA KTH Royal Inst Technol Div Decis & Control Syst S-11428 Stockholm Sweden

We consider a flow network that is described by a digraph, each edge of which can admit a flow within a certain interval, with nonnegative end points that correspond to lower and upper flow limits. We propose and analyze a distributed iterative algorithm for solving, in finite time, the so-called feasible circulation problem, which consists of computing flows that are admissible (i.e., within the given intervals at each edge) and balanced (i.e., the total in-flow equals the total out-flow at each node). The algorithm assumes a communication topology that allows bidirectional message exchanges between pairs of nodes that are physically connected (i.e., nodes that share a directed edge in the physical topology) and is shown to converge to a feasible and balanced solution as long as the necessary and sufficient circulation conditions are satisfied with strict inequality. In case, the initial flows and flow limits are commensurable (i.e., they are integer multiples of a given constant), then the proposed algorithm reduces to a previously proposed finite-time balancing algorithm, for which we provide an explicit bound on the number of steps required for termination.

关键词： Balancing distributed algorithms distributed balancing feasible circulation finite-time flow networks

来源：评论

学校读者我要写书评

暂无评论

A Game-Theoretic Approach to Solving the Roman Domination Problem

引用

IEEE-CAA JOURNAL OF AUTOMATICA SINICA 2025年第5期12卷 1024-1040页

作者： Chen, Xiuyang Tang, Changbing Zhang, Zhao Chen, Guanrong Xinjiang Univ Coll Math & Syst Sci Urumqi 830000 Peoples R China Zhejiang Normal Univ Coll Phys & Elect Informat Engn Jinhua 321004 Peoples R China Zhejiang Normal Univ Coll Math Sci Jinhua 321004 Peoples R China City Univ Hong Kong Dept Elect Engn Hong Kong 999077 Peoples R China

The Roman domination problem is an important combinatorial optimization problem that is derived from an old story of defending the Roman Empire and now regains new significance in cyber space security, considering backups in the face of a dynamic network security requirement. In this paper, firstly, we propose a Roman domination game (RDG) and prove that every Nash equilibrium (NE) of the game corresponds to a strong minimal Roman dominating function (S-RDF), as well as a Pareto-optimal solution. Secondly, we show that RDG is an exact potential game, which guarantees the existence of an NE. Thirdly, we design a game-based synchronous algorithm (GSA), which can be implemented distributively and converge to an NE in O(n) rounds, where $n$ is the number of vertices. In GSA, all players make decisions depending on local information. Furthermore, we enhance GSA to be enhanced GSA (EGSA), which converges to a better NE in O(n(2)) rounds. Finally, we present numerical simulations to demonstrate that EGSA can obtain a better approximate solution in promising computation time compared with state-of-the-art algorithms.

关键词： Games Resource description framework Nash equilibrium Approximation algorithms distributed algorithms Optimization Multi-agent systems Heuristic algorithms Gallium arsenide Faces distributed algorithm game theory multi-agent system potential game Roman dominating function

来源：评论

学校读者我要写书评

暂无评论

DOT and DOP: Linearly Convergent algorithms for Finding Fixed Points of Multiagent Operators

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2024年第6期69卷 3689-3704页

作者： Li, Xiuxian Meng, Min Xie, Lihua Tongji Univ Coll Elect & Informat Engn Dept Control Sci & Engn Shanghai 200092 Peoples R China Tongji Univ Shanghai Res Inst Intelligent Autonomous Syst Shanghai 200092 Peoples R China Nanyang Technol Univ Sch Elect & Elect Engn Singapore 639798 Singapore

This article investigates the distributed fixed-point finding problem for a global operator over a directed and unbalanced multiagent network, where the global operator is quasi-nonexpansive and only partially accessible to each individual agent. Two cases are addressed, i.e., the global operator is sum separable and block separable. For this first case, the global operator is the sum of local operators, which are assumed to be Lipschitz, and each local operator is privately known to each individual agent. To deal with this scenario, a distributed (or decentralized) algorithm, called distributed quasi-averaged operator tracking algorithm (DOT), is proposed and analyzed, and it is shown that the algorithm can converge to a fixed point of the global operator at a linear rate under a linear regularity condition, which is strictly weaker than the strong convexity assumption on cost functions in existing convex optimization literature. For the second scenario, the global operator is composed of a group of local block mappings which are Lipschitz and can be accessed only by each individual agent. In this setup, a distributed algorithm, called distributed quasi-averaged operator playing algorithm (DOP), is developed and shown to be linearly convergent to a fixed point of the global operator under the linear regularity condition. The above studied problems provide a unified framework for many interesting problems. As examples, the proposed DOT and DOP are exploited to cope with distributed optimization and multiplayer games under partial-decision information. Finally, numerical examples are presented to corroborate the theoretical results.

关键词： distributed algorithms Hilbert space Optimization Convergence US Department of Transportation Games Game theory distributed optimization fixed point game linear convergence linear regularity multiagent networks real Hilbert spaces

来源：评论

学校读者我要写书评

暂无评论

distributed Resilient Nash Equilibrium Seeking Under Network Attacks and Disturbances

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2022年第6期9卷 4287-4296页

作者： Shao, Guangru Wang, Xue-Fang Ye, Maojiao Wang, Rui Yantai Univ Sch Math & Informat Sci Yantai 264005 Peoples R China Dalian Univ Technol Key Lab Intelligent Control & Optimizat Ind Equip Minist Educ Dalian 116024 Peoples R China Nanjing Univ Sci & Technol Sch Automat Nanjing 210094 Peoples R China Dalian Univ Technol Key Lab Adv Technol Aerosp Vehicles Dalian 116024 Liaoning Peoples R China Dalian Univ Technol Sch Aeronaut & Astronaut Dalian 116024 Liaoning Peoples R China

This paper investigates the Nash equilibrium (NE) seeking problem of the game in which the dynamics of all players are affected by external disturbances and the communication network among players may be influenced by persistent attacks. To solve this problem, a distributed robust switched algorithm is proposed. This distributed switched strategy consists of two modules: One is the internal-model based dynamics that can be used to compensate the effects caused by external disturbances;the other is gradient-based optimization module which can utilize the local information to estimate the players' decisions and dynamically seek the optimal solution. By utilizing average dwell-time and time-ratio constraints to characterize the network attacks, the proposed switched strategy is modeled into a hybrid dynamical system. Moreover, employing the hybrid systems approach, we prove that the decisions of all players can exponentially converge to the NE of the considered game. Finally, an example is provided to illustrate the theoretical results.

关键词： Heuristic algorithms Games Vehicle dynamics Topology Eigenvalues and eigenfunctions distributed algorithms Cost function Nash equilibrium Disturbance rejection distributed robust switched algorithm hybrid systems Nash equilibrium (NE) seeking network attacks

来源：评论

学校读者我要写书评

暂无评论

Communication-Efficient distributed Cooperative Learning With Compressed Beliefs

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2022年第3期9卷 1215-1226页

作者： Toghani, Mohammad Taha Uribe, Cesar A. Rice Univ Dept Elect & Comp Engn Houston TX 77005 USA

In this article, we study the problem of distributed cooperative learning, where a group of agents seeks to agree on a set of hypotheses that best describes a sequence of private observations. In the scenario where the set of hypotheses is large, we propose a belief up-date rule where agents share compressed (either sparse or quantized) beliefs with an arbitrary positive compression rate. Our algorithm leverages a unified communication rule that enables agents to access wide-ranging compression operators as black-box modules. We prove the almost sure asymptotic convergence of beliefs on the set of optimal hypotheses. Additionally, we show a nonasymptotic, explicit, and linear concentration rate in probability of the beliefs on the optimal hypothesis set. We provide numerical experiments to illustrate the communication benefits of our method. The simulation results show that the number of transmitted bits can be reduced to 5%-10% of the noncompressed method in the studied scenarios.

关键词： Algorithm design and analysis Bayesian update compressed communication distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed minimum vertex coloring and maximum independent set in chordal graphs

引用

THEORETICAL COMPUTER SCIENCE 2022年 922卷 486-502页

作者： Konrad, Christian Zamaraev, Viktor Univ Bristol Dept Comp Sci Bristol Avon England Univ Liverpool Dept Comp Sci Liverpool Merseyside England

We give deterministic distributed (1 + epsilon)-approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in O(1/epsilon log n) rounds, and our independent set algorithm has a runtime of O(1/epsilon log(1/epsilon) log* n) rounds. For coloring, existing lower bounds imply that the dependencies on E1 and log n are best possible. For independent set, we prove that Omega(1/epsilon) rounds are necessary. Both our algorithms make use of a tree decomposition of the input chordal graph. They iteratively peel off interval subgraphs, which are identified via the tree decomposition of the input graph, thereby partitioning the vertex set into O(log n) layers. For coloring, each interval graph is colored independently, which results in various coloring conflicts between the layers. These conflicts are then resolved in a separate phase, using the particular structure of our partitioning. For independent set, only the first O(log 1/epsilon) layers are required as they already contain a large enough independent set. We develop a (1 + epsilon)approximation maximum independent set algorithm for interval graphs, which we then apply to those layers. While tree decompositions have only played a minor role in distributed computing, our work demonstrates their potential for designing efficient distributed algorithms. (C) 2022 The Authors. Published by Elsevier B.V.

关键词： distributed algorithms Maximum independent set Minimum vertex coloring Approximation algorithms Chordal graphs

来源：评论

学校读者我要写书评

暂无评论

A distributed Model-Free Algorithm for Multi-Hop Ride-Sharing Using Deep Reinforcement Learning

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2022年第7期23卷 8595-8605页

作者： Singh, Ashutosh Al-Abbasi, Abubakr O. Aggarwal, Vaneet Purdue Univ Sch Ind Engn W Lafayette IN 47907 USA Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47907 USA

The growth of autonomous vehicles, ridesharing systems, and self-driving technology will bring a shift in the way ride hailing platforms plan out their services. However, these advances in technology coupled with road congestion, environmental concerns, fuel usage, vehicles emissions, and the high cost of the vehicle usage have brought more attention to better utilize the use of vehicles and their capacities. In this paper, we propose a novel distributed multi-hop ride-sharing (MHRS) algorithm that uses deep reinforcement learning to learn optimal vehicle dispatch and matching decisions by interacting with the external environment. By allowing customers to transfer between vehicles, i.e., ride with one vehicle for some time and then transfer to another one, MHRS helps in attaining 30% lower cost and 20% more efficient utilization of fleets, as compared to the ride-sharing algorithms. This flexibility of multi-hop feature gives a seamless experience to customers and ride-sharing companies, and thus improves ride-sharing services.

关键词： Multi-hop ride-sharing passenger transfer matching deep Q-network vehicle dispatch distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

The END: Estimation Network Design for Games Under Partial-Decision Information

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2024年第4期11卷 2200-2212页

作者： Bianchi, Mattia Grammatico, Sergio Swiss Fed Inst Technol Automat Control Lab CH-8092 Zurich Switzerland Delft Univ Technol Delft Ctr Syst & Control NL-2628 CD Delft Netherlands

Multiagent decision problems are typically solved via distributed iterative algorithms, where the agents only communicate among themselves on a peer-to-peer network. Each agent usually maintains a copy of each decision variable, while agreement among the local copies is enforced via consensus protocols. Yet, each agent is often directly influenced by a small portion of the decision variables only: neglecting this sparsity results in redundancy, poor scalability with the network size, and communication and memory overhead. To address these challenges, we develop Estimation Network Design (END), a framework for the design and analysis of distributed algorithms. END algorithms can be tuned to exploit problem-specific sparsity structures, by optimally allocating copies of each variable only to a subset of agents, to improve efficiency and minimize redundancy. We illustrate the END's potential on generalized Nash equilibrium seeking under partial-decision information by designing new algorithms that can leverage the sparsity in cost functions, constraints, and aggregation values, and by relaxing the assumptions on the (directed) communication network postulated in the literature. Finally, we numerically test our methods on a unicast rate allocation problem, revealing greatly reduced communication and memory costs.

关键词： Costs Vectors Games distributed algorithms Scalability Memory management Convergence Nash equilibrium (NE) seeking optimization algorithms variational methods

来源：评论

学校读者我要写书评

暂无评论

Fully distributed Event-Triggered Optimal Coordinated Control for Multiple Euler-Lagrangian Systems

引用

IEEE TRANSACTIONS ON CYBERNETICS 2022年第9期52卷 9120-9131页

作者： Huang, Yi Meng, Ziyang Tsinghua Univ Dept Precis Instrument Beijing 100084 Peoples R China

This article studies a fully distributed optimal coordinated control problem with the global cost function for networked Euler-Lagrange (EL) systems subject to unknown model parameters. In particular, the global cost function is the sum of all the local cost functions assigned to each agent and only available to itself. The objective is to minimize the global cost function in a distributed manner while achieving a consensus on its optimal solution. Since the model parameters of the considered EL systems are not available, a new auxiliary system is introduced as a reference model, and its outputs exponentially converge the optimal solution of the global cost function. A fully distributed optimal control algorithm without requiring global information is first proposed. Then, an alternative distributed optimal algorithm via the event-triggered mechanism is proposed to reduce the communication cost. In particular, by combining an edge-based adaptive gain method, the proposed event-triggered optimal algorithm is also fully distributed. Finally, numerical simulation is carried out to validate the theoretical results.

关键词： Cost function Multi-agent systems distributed algorithms Topology Symmetric matrices Optimal control Laplace equations Adaptive gain Euler-Lagrange (EL) systems event-triggered fully distributed control optimal consensus

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：