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

Robust Phase Retrieval by Alternating Minimization

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2025年 73卷 40-54页

作者： Kim, Seonho Lee, Kiryung Ohio State Univ Dept ECE Columbus OH 43210 USA

We consider a least absolute deviation (LAD) approach to the robust phase retrieval problem that aims to recover a signal from its absolute measurements corrupted with sparse noise. To solve the resulting non-convex optimization problem, we propose a robust alternating minimization (Robust-AM) derived as an unconstrained Gauss-Newton method. To solve the inner optimization arising in each step of Robust-AM, we adopt two computationally efficient methods. We provide a non-asymptotic convergence analysis of these practical algorithms for Robust-AM under the standard Gaussian measurement assumption. These algorithms, when suitably initialized, are guaranteed to converge linearly to the ground truth at an order-optimal sample complexity with high probability while the support of sparse noise is arbitrarily fixed and the sparsity level is no larger than 1/4. Additionally, through comprehensive numerical experiments on synthetic and image datasets, we show that Robust-AM outperforms existing methods for robust phase retrieval offering comparable theoretical performance guarantees.

关键词： Optimization Signal processing algorithms Computational efficiency Minimization Extraterrestrial measurements Convergence Phase measurement Noise Computational modeling Vectors Phase retrieval outliers least absolute deviation linear program convex optimization

来源：评论

学校读者我要写书评

暂无评论

MF-OMO: AN OPTIMIZATION FORMULATION OF MEAN-FIELD GAMES

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 2024年第1期62卷 243-270页

作者： Guo, Xin Hu, Anran Zhang, Junzi Univ Calif Berkeley Berkeley CA 94711 USA Univ Oxford Oxford OX2 6GG England Citadel Secur Miami FL 33131 USA

This paper proposes a new mathematical paradigm to analyze discrete-time meanfield games. It is shown that finding Nash equilibrium solutions for a general class of discretetime mean-field games is equivalent to solving an optimization problem with bounded variables and simple convex constraints, called MF-OMO. This equivalence framework enables finding multiple (and possibly all) Nash equilibrium solutions of mean-field games by standard algorithms. For instance, projected gradient descent is shown to be capable of retrieving all possible Nash equilibrium solutions when there are finitely many of them, with proper initializations. Moreover, analyzing mean-field games with linear rewards and mean-field independent dynamics is reduced to solving a finite number of linear programs, hence solvable in finite time. This framework does not rely on the contractive and the monotone assumptions and the uniqueness of the Nash equilibrium.

关键词： mean-field games Nash equilibrium occupation measure linear program opti- mization complementarity

来源：评论

学校读者我要写书评

暂无评论

LP-Rounding Based Algorithm for Capacitated Uniform Facility Location Problem with Soft Penalties

引用

Tsinghua Science and Technology 2025年第1期30卷 279-289页

作者： Runjie Miao Chenchen Wu Jinjiang Yuan School of Mathematics and Statistics Zhengzhou UniversityZhengzhou 450001China Institute of Operations Research and Systems Engineering Tianjin University of TechnologyTianjin 300384China

Capacitated facility location problem(CFLP)is a classical combinatorial optimization problem that has various applications in operations research,theoretical computer science,and management *** the CFLP,we have a potential facilities set and a clients *** facility has a certain capacity and an open cost,and each client has a spliitable demand that need to be *** goal is to open some facilities and assign all clients to these open facilities so that the total cost is as low as *** CFLP is NP-hard(non-deterministic polynomial-hard),and a large amount of work has been devoted to designing approximation algorithms for CFLP and its *** this vein,we introduce a new variant of CFLP called capacitated uniform facility location problem with soft penalties(CUFLPSP),in which the demand of each client can be partially rejected by paying penalty *** a result,we present a linear programming-rounding(LP-rounding)based 5.5122-approximation algorithm for the CUFLPSP.

关键词： capacitated facility location problem approximation algorithm soft penalties linear program

来源：评论

学校读者我要写书评

暂无评论

Characteristic sets and characteristic numbers of matrix two-person games

引用

JOURNAL OF GLOBAL OPTIMIZATION 2024年第1期90卷 217-241页

作者： Huyen, D. T. K. Yao, J. -C. Yen, N. D. Hanoi Pedag Univ 2 Dept Math Phuc Yen Vinh Phuc Vietnam PHENIKAA Univ Fac Comp Sci ORLab Hanoi 12116 Vietnam China Med Univ Ctr Gen Educ Taichung Taiwan Inst Math Vietnam Acad Sci & Technol 18 Hoang Quoc Viet Hanoi 10307 Vietnam

Focusing on the extreme points of the solution sets of matrix two-person games, we propose the notions of characteristic sets and characteristic numbers. The characteristic sets (resp., the characteristic numbers) are the sets (resp., the numbers) of the extreme points of the solution set of the game and the optimal solution sets of the players. These concepts allow us to measure the complexity of the game. The larger the characteristic numbers, the more complex the game is. Among other things, we obtain upper bounds for the characteristic numbers and give a novel geometric construction. By the construction, we get useful descriptions of the optimal strategy set of each player of a game given by any nonsingular square matrix. Namely, the investigation of the geometry the just-mentioned sets reduces to computing or studying certain simpler sets. We also formulate several open problems.

关键词： Matrix two-person game Mixed strategy linear program Extreme point Characteristic set Characteristic number Upper bound

来源：评论

学校读者我要写书评

暂无评论

Generative Abnormal Data Detection for Enhancing Cellular Vehicle-to-Everything-Based Road Safety

IEEE TRANSACTIONS ON GREEN COMMUNICATIONS AND NETWORKING

引用

IEEE TRANSACTIONS ON GREEN COMMUNICATIONS AND NETWORKING 2024年第4期8卷 1466-1478页

作者： Zhao, Liang Fan, Xu Hawbani, Ammar Xu, Lexi Yu, Keping Liu, Zhi Alfarraj, Osama Shenyang Aerosp Univ Sch Comp Sci Shenyang 110100 Peoples R China China United Network Commun Corp Res Inst Beijing 100048 Peoples R China Hosei Univ Grad Sch Sci & Engn Tokyo 1848584 Japan Univ Electrocommun Dept Comp & Network Engn Tokyo 1828585 Japan King Saud Univ Community Coll Comp Sci Dept Riyadh 11437 Saudi Arabia

Under the framework of Cellular-Vehicle-to-Everything (C-V2X) technology, although vehicles can avoid potential risks and improve traffic efficiency, shared vehicle data may have defects or faults due to inevitable environmental noise or potential sensor failures, which could pose dangers to drivers. Therefore, detecting anomalies in data transmitted via C-V2X is crucial, particularly for the driving control messages, i.e., Basic Safety Messages (BSM). However, anomaly detection in BSM data faces multiple challenges. First, BSM data contains rich driving details, necessitating modeling its high variability to better learn complex and nonlinear spatio-temporal relationships. Second, the rarity of anomalous events and the potential diversity of normal behaviors make defining anomalies more complex, increasing the difficulty of anomaly detection. Third, extracting meaningful information from a large amount of data and understanding the abstract patterns or regularities within it can also be challenging for effective reasoning at the data level. To address these challenges, we propose a hybrid generative model named CoGAN, which combines Variational Autoencoder (VAE) and Generative Adversarial Network (GAN) to implicitly learn the feature representation of normal data in an unsupervised manner. Specifically, the VAE is responsible for learning the distribution of normal data, and capturing the fundamental patterns and structures of the data;meanwhile, the discriminator is dedicated to enhancing the model's ability to learn the distribution of normal data, refining the model's understanding of data through the introduction of an adversarial process. CoGAN explores the distribution characteristics of normal vehicle behavior data by jointly learning the generation process and variational inference of BSM data, thereby achieving the purpose of anomaly detection.

关键词： C-V2X BSM anomaly detection anomaly detection deep learning deep learning hybrid generative model hybrid generative model multi-head attention multi-head attention 3DConv 3DConv LSTM LSTM linear program linear program LSTM linear program

来源：评论

学校读者我要写书评

暂无评论

On computing sparse generalized inverses

引用

OPERATIONS RESEARCH LETTERS 2024年 52卷

作者： Ponte, Gabriel Fampa, Marcia Lee, Jon Xu, Luze Univ Michigan Ann Arbor MI 48109 USA Univ Fed Rio de Janeiro Rio De Janeiro Brazil Univ Calif Davis Davis CA USA

The M-P (Moore-Penrose) pseudoinverse is used in several linear-algebra applications. It is convenient to construct sparse block-structured matrices satisfying some relevant properties of the M-P pseudoinverse for specific applications. Aiming at row-sparse generalized inverses, we consider 2,1-norm minimization (and generalizations). We show that a 2,1-norm minimizing generalized inverse satisfies two additional M-P properties, including one needed for computing least-squares solutions. We present formulations related to finding row-sparse generalized inverses that can be solved very efficiently, which we verify numerically.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Moore-Penrose pseudoinverse Generalized inverse Sparse optimization Norm minimization Least squares linear program

来源：评论

学校读者我要写书评

暂无评论

A new integer programming formulation of the graphical traveling salesman problem

引用

MATHEMATICAL programMING 2023年第2期197卷 877-902页

作者： Carr, Robert Ravi, R. Simonetti, Neil Univ New Mexico Dept Comp Sci Albuquerque NM 87131 USA Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA Bryn Athyn Coll Business Comp Sci & Math Dept Bryn Athyn PA 19009 USA

In the Traveling Salesman Problem (TSP), a salesman wants to visit a set of cities and return home. There is a cost c(ij) of traveling from city i to city j, which is the same in either direction for the Symmetric TSP. The objective is to visit each city exactly once, minimizing total travel costs. In the Graphical TSP, a city may be visited more than once, which may be necessary on a sparse graph. We present a new integer programming formulation for the Graphical TSP requiring only two classes of polynomial-sized constraints while addressing an open question proposed by Denis Naddef. We generalize one of these classes, and present promising preliminary computational results.

关键词： linear program Relaxation Traveling salesman problem Graphical traveling salesman Problem Integrality gap Separation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Nearly-linear Time Algorithm for linear programs with Small Treewidth: A Multiscale Representation of Robust Central Path 2021

A Nearly-Linear Time Algorithm for Linear Programs with Smal...

引用

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Dong, Sally Lee, Yin Tat Ye, Guanghao Univ Washington Seattle WA 98195 USA Microsoft Res Redmond WA USA

ISBN: (纸本)9781450380539

Arising from structural graph theory, treewidth has become a focus of study in fixed-parameter tractable algorithms. Many NP-hard problems are known to be solvable in (O) over tilde (n . 2(O(tau))) time, where tau is the treewidth of the input graph. Analogously, many problems in P should be solvable in (O) over tilde (n . tau(O(1))) time;however, due to the lack of appropriate tools, only a few such results are currently known. In our paper, we show this holds for linear programs: Given a linear program of the form min(Ax=b,l <= x <= u) c(T)x whose dual graph G(A) has treewidth tau, and a corresponding width-tau tree decomposition, we show how to solve it in time (O) over tilde (n . tau(2) log(1/epsilon)), where n is the number of variables and epsilon is the relative accuracy. When a tree decomposition is not given, we use existing techniques in vertex separators to obtain algorithms with (O) over tilde (n . tau(4)log(1/epsilon)) and (O) over tilde (n . tau(2)log(1/epsilon) + n(1.5)) run-times. Besides being the first of its kind, our algorithm has run-time nearly matching the fastest run-time for solving the sub-problem Ax = b (under the assumption that no fast matrix multiplication is used). We obtain these results by combining recent techniques in interior-point methods (IPMs), sketching, and a novel representation of the solution under a multiscale basis similar to the wavelet basis. This representation further yields the first IPM with o (rank(A)) time per iteration when the treewidth is small.

关键词： linear program interior point method treewidth parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

An Efficient LP-Based Approach for Spatial-Temporal Coordination of Electric Vehicles in Electricity-Transportation Nexus

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2023年第3期38卷 2914-2925页

作者： Wang, Hongru Ye, Yujian Wang, Qi Tang, Yi Strbac, Goran Southeast Univ Sch Cyber Sci & Engn Nanjing 210096 Jiangsu Peoples R China Southeast Univ Sch Elect Engn Nanjing 210096 Jiangsu Peoples R China Imperial Coll London Dept Elect & Elect Engn London SW7 2AZ England

A growing integration of electric vehicles (EV) and fast charging stations (FCS) has paved the way for the emergence of transportation and power distribution networks. However, previous work on the coordination of EV in the transportation system mainly focuses on static traffic assignment (STA) models which are unable to characterize the temporal evolution of EV flows on traffic links. Meanwhile, limited prior effort in dynamic traffic assignment (DTA) employs a static FCS model which is unable to describe the temporal evolution of charging and discharging (C&D) behavior of EV flows, while respecting the state-of-charge (SoC) related operating constraints, hindering full exploitation of EV flexibility potentials. To bridge the knowledge gap, this paper proposes a novel DTA model to optimize the spatial-temporal distribution of EV flows on roads and at FCSs, taking into account their flexible C&D options and SoC-related constraints, through the solution of only a single linear program. Case studies validate the effectiveness of the proposed DTA model by benchmarking its performance against traditional STA models, and corroborate the core benefits from the proposed spatial-temporal coordination of EV C&D demand in the power distribution network in terms of peak demand reduction, improved RES absorption, reduced carbon emission as well as more efficient network congestion management.

关键词： Roads Indexes Biological system modeling Power system dynamics Transportation Behavioral sciences Electric vehicle charging Dynamic traffic assignment electric vehicles linear program state-of-charge transportation electrification

来源：评论

学校读者我要写书评

暂无评论

The generalized cash balance problem: optimization-based one step ahead optimal control

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2023年第6期30卷 3993-4025页

作者： Bhaya, Amit Kaszkurewicz, Eugenius Univ Fed Rio de Janeiro Dept Elect Engn COPPE UFRJ POB 68504 Rio De Janeiro Brazil

This paper generalizes the Sethi-Thompson model of cash balance dynamics to the case of multiple current and investment accounts, with the cash flows or demands incident on the current accounts. Cash transfers can occur between any pair of current-current or current-investment accounts, with transaction costs proportional to the amount transferred, always deducted from current accounts. Performance indices are defined and maximization of an index for the next instant (day), by suitable choice of cash transfers that satisfy desired constraints on account balances, defines the basic optimal control problem referred to as one step ahead optimal control. It is shown that this one step ahead optimal control can be written as a mixed integer linear program of small size, leading to an implementable real time strategy for the generalized cash balance problem. In addition, for the simple case of a single cash and investment account, the proposed strategy is derived analytically and compared with a strategy of Miller-Orr type, called a three-level strategy. Omniscient optimal control over a horizon is defined as the globally optimal control strategy, assuming the demands over the entire horizon to be known: although computable a posteriori, it is not implementable a priori, and only serves as a benchmark for comparison. The proposed one step ahead optimal or myopic approach makes no assumptions about the distribution of cash demands, and examples show that it attains performance indices which are superior to those attained by three-level control strategies, and compare favorably with the omniscient benchmark performance indices.

关键词： cash balance optimal control linear program

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：