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

S-DIGing: A Stochastic Gradient Tracking Algorithm for Distributed Optimization

IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE 2022年第1期6卷 53-65页

作者： Li, Huaqing Zheng, Lifeng Wang, Zheng Yan, Yu Feng, Liping Guo, Jing Southwest Univ Coll Elect & Informat Engn Chongqing Key Lab Nonlinear Circuits & Intelligen Chongqing 400715 Peoples R China Xinzhou Teachers Univ Dept Comp Sci Xinzhou 034000 Peoples R China

In this article, we study convex optimization problems where agents of a network cooperatively minimize the global objective function which consists of multiple local objective functions. The intention of this work is to solve large-scale optimization problems where the local objective function is complicated, and numerous. Different from most of the existing works, the local objective function of each agent is presented as the average of finite instantaneous functions. Integrating the gradient tracking algorithm with stochastic averaging gradient technology, a distributed stochastic gradient tracking (termed as S-DIGing) algorithm is proposed. At each time instant, only one randomly selected gradient of an instantaneous function is computed, and applied to approximate the local batch gradient for each agent. Based on a novel primal-dual interpretation of the S-DIGing algorithm, it is shown that the S-DIGing algorithm linearly converges to the global optimal solution when step-size do not exceed an explicit upper bound, and the instantaneous functions are strongly convex with Lipschitz continuous gradients. Numerical experiments are presented to demonstrate the practicability of the S-DIGing algorithm, and correctness of the theoretical results.

关键词： Optimization Convergence Linear programming approximation algorithms Stochastic processes Machine learning algorithms Convex functions Distributed optimization gradient tracking stochastic averaging gradient multi-agent systems linear convergence

来源：评论

学校读者我要写书评

暂无评论

Joint Device Pairing, Reflection Coefficients, and Power Control for NOMA Backscatter Systems

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2022年第4期71卷 4396-4411页

作者： Ardakani, Farhad Dashti Huang, Rui Wong, Vincent W. S. Univ British Columbia Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada

Non-orthogonal multiple access (NOMA) and backscatter communication are two emerging technologies for low-power communication. In this paper, we consider a NOMA backscatter system, where signals from two backscatter devices are multiplexed on a frequency resource block using NOMA in each time slot. Our objective is to maximize the average energy efficiency by optimizing backscatter device pairing, reflection coefficients of backscatter devices, and the transmit power of the reader. We formulate the average energy efficiency maximization problem subject to the minimum circuit power and the minimum data rate requirements of the backscatter devices, and the transmit power constraint of the reader. The formulated problem is nonconvex. To obtain a suboptimal solution for this problem, we use alternating optimization technique and decompose the problem into two subproblems. The subproblems are solved by using fractional programming, Dinkelbach's algorithm, and successive convex approximation method. Simulation results show that our proposed algorithm converges quickly to a suboptimal solution. Our proposed algorithm outperforms several baseline algorithms, including the genetic algorithm, fixed device pairing scheme, conventional device pairing scheme, maximum transmit power allocation scheme, and random reflection coefficient selection scheme, in terms of the average energy efficiency. The optimality gap of our proposed algorithm is investigated by comparing with the optimal scheme, in which the optimal device pairing is obtained based on exhaustive search.

关键词： Backscatter NOMA Energy efficiency Resource management Reflection coefficient Optimization approximation algorithms Alternating optimization backscatter communication energy efficiency fractional programming non-orthogonal multiple access

来源：评论

学校读者我要写书评

暂无评论

Design of Distributed Event-Triggered Average Tracking algorithms for Homogeneous and Heterogeneous Multiagent Systems

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2022年第3期67卷 1269-1284页

作者： Zhao, Yu Xian, Chengxin Wen, Guanghui Huang, Panfeng Ren, Wei Northwestern Polytech Univ Sch Automat Xian 710129 Peoples R China Southeast Univ Sch Math Nanjing 210096 Peoples R China Univ Calif Riverside Dept Elect & Comp Engn Riverside CA 92521 USA

This article addresses the design problem of distributed event-triggered average tracking (DETAT) algorithms for homogeneous and heterogeneous multiagent systems. The objective of the DETAT problem is to develop a group of distributed cooperative control algorithms with event-triggered strategies for agents to track the average of multiple time-varying reference signals. First, for homogeneous linear multiagent systems, based on sampling measurements and model-relied holding techniques, a class of static-gain DETAT algorithms is proposed with a couple of local event-triggered functions for estimators and controllers, respectively. Compared with the existing distributed average tracking (DAT) algorithms, the static-gain DETAT algorithms greatly reduce the cost over communication networks and the frequency of control protocol updates. Second, to reduce the chattering phenomenon caused by nonsmooth items in static-gain algorithms and requirements of the global information of networks, smooth dynamic-gain DETAT algorithms are introduced based on boundary layer approximation methods and self-adaptive principles. Third, for heterogeneous linear multiagent systems, a new algorithm is established by using the output regulation techniques for the heterogeneous DETAT problem. The outputs of heterogeneous agents can ultimately track the average of multiple time-varying reference signals. To the best of our knowledge, it is the first time to study the DETAT problem for heterogeneous multiagent systems. Finally, some examples are presented to show the validity of theoretical results.

关键词： Heuristic algorithms Multi-agent systems Eigenvalues and eigenfunctions approximation algorithms Communication networks Trajectory Regulation Distributed average tracking (DAT) event-triggered strategy homogeneous and heterogeneous dynamics linear multiagent system

来源：评论

学校读者我要写书评

暂无评论

Multiplayer Stackelberg-Nash Game for Nonlinear System via Value Iteration-Based Integral Reinforcement Learning

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2022年第4期33卷 1429-1440页

作者： Li, Man Qin, Jiahu Freris, Nikolaos M. Ho, Daniel W. C. Univ Sci & Technol China Dept Automat Hefei 230027 Peoples R China Univ Sci & Technol China Sch Comp Sci & Technol Hefei 230027 Peoples R China City Univ Hong Kong Dept Math Hong Kong Peoples R China

In this article, we study a multiplayer Stackelberg-Nash game (SNG) pertaining to a nonlinear dynamical system, including one leader and multiple followers. At the higher level, the leader makes its decision preferentially with consideration of the reaction functions of all followers, while, at the lower level, each of the followers reacts optimally to the leader's strategy simultaneously by playing a Nash game. First, the optimal strategies for the leader and the followers are derived from down to the top, and these strategies are further shown to constitute the Stackelberg-Nash equilibrium points. Subsequently, to overcome the difficulty in calculating the equilibrium points analytically, we develop a novel two-level value iteration-based integral reinforcement learning (VI-IRL) algorithm that relies only upon partial information of system dynamics. We establish that the proposed method converges asymptotically to the equilibrium strategies under the weak coupling conditions. Moreover, we introduce effective termination criteria to guarantee the admissibility of the policy (strategy) profile obtained from a finite number of iterations of the proposed algorithm. In the implementation of our scheme, we employ neural networks (NNs) to approximate the value functions and invoke the least-squares methods to update the involved weights. Finally, the effectiveness of the developed algorithm is verified by two simulation examples.

关键词： Games Heuristic algorithms Mathematical model approximation algorithms Decision making System dynamics Nonlinear dynamical systems Integral reinforcement learning (IRL) multiplayer Stackelberg-Nash game (SNG) neural networks (NNs) nonlinear system value iteration (VI)

来源：评论

学校读者我要写书评

暂无评论

Efficient Approximate Search for Multi-Objective Multi-Agent Path Finding 34

Efficient Approximate Search for Multi-Objective Multi-Agent...

引用

34th International Conference on Automated Planning and Scheduling, ICAPS 2024

作者： Wang, Fangji Zhang, Han Koenig, Sven Li, Jiaoyang Tsinghua University China University of Southern California United States Carnegie Mellon University United States

ISBN: (纸本)9781577358893

The Multi-Objective Multi-Agent Path Finding (MO-MAPF) problem is the problem of computing collision-free paths for a team of agents while minimizing multiple cost metrics. Most existing MO-MAPF algorithms aim to compute the Pareto frontier. However, the Pareto frontier can be time-consuming to compute. Our first main contribution is BB-MO-CBS-pex, an approximate MO-MAPF algorithm that computes an approximate frontier for a user-specific approximation factor. BB-MO-CBS-pex builds upon BB-MO-CBS, a state-of-the-art MO-MAPF algorithm, and leverages A*pex, a state-of-the-art single-agent multi-objective search algorithm, to speed up different parts of BB-MO-CBS. We also provide two speed-up techniques for BB-MO-CBS-pex. Our second main contribution is BB-MO-CBS-k, which builds upon BB-MO-CBS-pex and computes up to k solutions for a user-provided k-value. BB-MO-CBS-k is useful when it is unclear how to determine an appropriate approximation factor. Our experimental results show that both BB-MO-CBS-pex and BB-MO-CBS-k solved significantly more instances than BB-MO-CBS for different approximation factors and k-values, respectively. Additionally, we compare BB-MO-CBS-pex with an approximate baseline algorithm derived from BB-MO-CBS and show that BB-MO-CBS-pex achieved speed-ups up to two orders of magnitude. Copyright © 2024, Association for the Advancement of Artificial Intelligence (***). All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Data Deduplication With Random Substitutions

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2022年第10期68卷 6941-6963页

作者： Lou, Hao Farnoud, Farzad Univ Virginia Dept Elect & Comp Engn Charlottesville VA 22903 USA Univ Virginia Dept Comp Sci Charlottesville VA 22903 USA

Data deduplication saves storage space by identifying and removing repeats in the data stream. Compared with traditional compression methods, data deduplication schemes are more computationally efficient and are thus widely used in large scale storage systems. In this paper, we provide an information-theoretic analysis of the performance of deduplication algorithms on data streams in which repeats are not exact. We introduce a source model in which probabilistic substitutions are considered. More precisely, each symbol in a repeated string is substituted with a given edit probability. Deduplication algorithms in both the fixed-length scheme and the variable-length scheme are studied. The fixed-length deduplication algorithm is shown to be unsuitable for the proposed source model as it does not take into account the edit probability. Two modifications are proposed and shown to have performances within a constant factor of optimal for a specific class of source models with the knowledge of model parameters. We also study the conventional variable-length deduplication algorithm and show that as source entropy becomes smaller, the size of the compressed string vanishes relative to the length of the uncompressed string, leading to high compression ratios.

关键词： Symbols Entropy Data models Probabilistic logic Analytical models approximation algorithms Genomics Chunking data compression data deduplication source coding substitution edits

来源：评论

学校读者我要写书评

暂无评论

A Spectral Feature Selection Approach With Kernelized Fuzzy Rough Sets

引用

IEEE TRANSACTIONS ON FUZZY SYSTEMS 2022年第8期30卷 2886-2901页

作者： Chen, Jinkun Lin, Yaojin Mi, Jusheng Li, Shaozi Ding, Weiping Minnan Normal Univ Sch Math & Stat Zhangzhou 363000 Peoples R China Minnan Normal Univ Sch Comp Sci Zhangzhou 363000 Peoples R China Hebei Normal Univ Hebei Int Joint Res Ctr Math & Interdisciplinary Sch Math Sci Shijiazhuang 050024 Hebei Peoples R China Xiamen Univ Dept Artificial Intelligence Xiamen 361005 Peoples R China Nantong Univ Sch Informat Sci & Technol Nantong 226019 Peoples R China

Feature evaluation is an important issue in constructing a feature selection algorithm in kernelized fuzzy rough sets, which has been proven to be an effective approach to deal with nonlinear classification tasks and uncertainty in learning problems. However, the feature evaluation function developed with kernelized fuzzy rough sets cannot better reflect the affinity relationship of samples and is time-consuming. To overcome these drawbacks, in this article, the problem of feature selection with kernelized fuzzy rough sets is studied based on the spectral graph theory. First, the within-class and between-class sample similarity matrices by using kernelized fuzzy approximation operators are constructed. Two operators, which can capture the affinity relationship of samples, are then introduced based on the sample similarity matrices. The proposed operator can be regarded as the sum of the weighted kernelized fuzzy approximation operators. Second, based on the ratio criterion, a feature evaluation function and its corresponding feature selection algorithm FRKF are presented, which can effectively evaluate the importance of features. Third, to illustrate the performance of the proposed algorithm, extensive experiments have been carried out to compare FRKF and other well-known feature selection methods, including the feature ranking methods and feature subset selection methods on various classification tasks. The experimental results on real-world datasets demonstrate that FRKF achieves the high performances in terms of the robustness, efficiency, and effectiveness.

关键词： Feature extraction Rough sets Kernel approximation algorithms Graph theory Task analysis Uncertainty Feature evaluation feature selection fuzzy rough sets kernel spectral graph theory

来源：评论

学校读者我要写书评

暂无评论

Secure Deterministic Wallet and Stealth Address: Key-Insulated and Privacy-Preserving Signature Scheme With Publicly Derived Public Key

引用

IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING 2022年第5期19卷 2934-2951页

作者： Liu, Zhen Yang, Guomin Wong, Duncan S. Khoa Nguyen Wang, Huaxiong Ke, Xiaorong Liu, Yining Shanghai Jiao Tong Univ Shanghai 200240 Peoples R China Univ Wollongong Wollongong NSW 2522 Australia CryptoBLK Hong Kong Peoples R China Nanyang Technol Univ Sch Phys & Math Sci Singapore 639798 Singapore Huawei Technol Co Ltd Shenzhen 518129 Peoples R China Univ Southern Calif Los Angeles CA 90007 USA

Deterministic Wallet (DW) and Stealth Address (SA) mechanisms have been widely adopted in the cryptocurrency community, due to their virtues on functionality and privacy protection, which come from a key derivation mechanism that allows an arbitrary number of derived keys to be generated from a master key. However, these algorithms suffer a vulnerability that, when one derived key is compromised somehow, the damage is not limited to the leaked derived key only, but to the master key and in consequence all derived keys are compromised. In this article, we introduce and formalize a new signature variant, called Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Key (PDPKS), which fully captures and improves the functionality, security, and privacy requirements of DW and SA. We propose a PDPKS construction and prove its security and privacy in the random oracle model. Furthermore, we implement the construction with parameters for 128-bit security, and the results show that it is practically efficient for the setting of cryptocurrencies. With its solid guarantee on functionality, security and privacy, as well as its practical efficiency, our PDPKS construction provides a practical cryptographic tool that refines DW and SA, without security vulnerability.

关键词： Public key Privacy Companies Bitcoin Digital signatures approximation algorithms Solids Signature scheme publicly derived public key key-insulated security privacy cryptocurrency stealth addresses deterministic wallets

来源：评论

学校读者我要写书评

暂无评论

Vertex Cover Optimization Using a Novel Graph Decomposition Approach

引用

Computers, Materials & Continua 2022年第10期73卷 701-717页

作者： Abdul Manan Shahida Bashir Abdul Majid Department of Mathematics University of GujratGujrat50700Pakistan Department of Physics University of GujratGujrat50700Pakistan

The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph *** MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a *** algorithm exits till date that can exactly solve the problem in a deterministic polynomial time ***,several algorithms are proposed that solve the problem approximately in a short polynomial time *** algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational *** MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising *** work aims to solve the MVCP approximately by a novel graph decomposition *** decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or *** order to reduce complexity of the algorithm a new strategy is also *** reduction strategy can be used for any algorithm solving *** on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the *** algorithms are tested using well known standard benchmark *** key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.

关键词： Combinatorial optimization graph theory minimum vertex cover problem maximum independent set maximum degree greedy approach approximation algorithms benchmark instances

来源：评论

学校读者我要写书评

暂无评论

Dynamic Time Warping Under Translation: approximation Guided by Space-Filling Curves 38

Dynamic Time Warping Under Translation: Approximation Guided...

引用

38th International Symposium on Computational Geometry, SoCG 2022

作者： Bringmann, Karl Kisfaludi-Bak, Sándor Künnemann, Marvin Marx, Dániel Nusser, André Universität des Saarlandes Saarbrücken Germany Max Planck Institute for Informatics Saarland Informatics Campus Saarbrücken Germany Aalto University Espoo Finland Institute for Theoretical Studies ETH Zürich Switzerland CISPA Helmholtz Center for Information Security Saarbrücken Germany BARC University of Copenhagen Denmark

ISBN: (纸本)9783959772273

The Dynamic Time Warping (DTW) distance is a popular measure of similarity for a variety of sequence data. For comparing polygonal curves p,s in Rd, it provides a robust, outlier-insensitive alternative to the Fréchet distance. However, like the Fréchet distance, the DTW distance is not invariant under translations. Can we efficiently optimize the DTW distance of p and s under arbitrary translations, to compare the curves' shape irrespective of their absolute location? There are surprisingly few works in this direction, which may be due to its computational intricacy: For the Euclidean norm, this problem contains as a special case the geometric median problem, which provably admits no exact algebraic algorithm (that is, no algorithm using only addition, multiplication, and k-th roots). We thus investigate exact algorithms for non-Euclidean norms as well as approximation algorithms for the Euclidean norm. For the L1 norm in Rd, we provide an O(n2(d+1))-time algorithm, i.e., an exact polynomial-time algorithm for constant d. Here and below, n bounds the curves' complexities. For the Euclidean norm in R2, we show that a simple problem-specific insight leads to a (1 + e)-approximation in time O(n3/e2). We then show how to obtain a subcubic Oe(n2.5/e2) time algorithm with significant new ideas;this time comes close to the well-known quadratic time barrier for computing DTW for fixed translations. Technically, the algorithm is obtained by speeding up repeated DTW distance estimations using a dynamic data structure for maintaining shortest paths in weighted planar digraphs. Crucially, we show how to traverse a candidate set of translations using space-filling curves in a way that incurs only few updates to the data structure. We hope that our results will facilitate the use of DTW under translation both in theory and practice, and inspire similar algorithmic approaches for related geometric optimization problems. © Karl Bringmann, Sndor Kisfaludi-Bak, Marvin Knnemann, Dnie

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：