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

Radar Target Detection via Global Optimality Conditions for binary quadratic programming

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2023年 71卷 2502-2517页

作者： Zhao, Wenjing Cui, Guolong Jin, Minglu Wang, Yumiao Univ Elect Sci & Technol China Sch Informat & Commun Engn Chengdu 611731 Peoples R China Univ Elect Sci & Technol China Sch Elect Sci & Engn Chengdu 611731 Peoples R China Dalian Univ Technol Sch Informat & Commun Engn Dalian 116024 Peoples R China

This article considers the problem of radar target detection in compound Gaussian clutter background. Different from the existing detector design criteria, we propose two new detection schemes for the detection problem from the optimization perspective. Specifically, in the first scheme, the detection problem is firstly studied by introducing an auxiliary variable and transforming it into a maximum likelihood estimation problem. Under this scheme, the maximum likelihood detector and its improved version with parameter estimation are developed by using maximum likelihood criterion. In the second scheme, the detection problem is recast into a binary quadratic programming (BQP) problem. Resorting to the global optimality conditions and solution for the BQP problem, we design four BQP detectors named BQPH, BQPS, BQPM and BQPW with the aid of hard decision fusion, data fusion based on summation and taking median, and whitening respectively. At the analysis stage, the statistical distributions of the BQP detectors are modelled using t location-scale distribution, and the theoretical closed-form expressions of the false alarm probability, thresholds and detection probability of the four BQP detectors are further derived. Finally, simulation experiments on the simulated data and real sea clutter data are performed to highlight the effectiveness of the proposed detectors in comparison with several state-of-the-art detectors.

关键词： Radar target detection non-Gaussian clutter binary quadratic programming global optimality conditions

来源：评论

学校读者我要写书评

暂无评论

An Entropy-Regularized ADMM For binary quadratic programming

引用

JOURNAL OF GLOBAL OPTIMIZATION 2023年第2-4期87卷 447-479页

作者： Liu, Haoming De, Kangkang Liu, Haoyang Wen, Zaiwen Peking Univ Beijing Int Ctr Math Res Beijing Peoples R China Peking Univ Ctr Data Sci Beijing Int Ctr Math Res Beijing Peoples R China Peking Univ Coll Engn Beijing Peoples R China

We propose an entropy regularized splitting model using low-rank factorization for solving binary quadratic programming with linear inequality constraints. Different from the semidefinite programming relaxation model, our model preserves the rank-one constraint and aims to find high quality rank-one solutions directly. The factorization transforms the variables into low-rank matrices, while the entropy term enforces the low-rank property of the splitting variable. A customized alternating direction method of multipliers is utilized to solve the proposed model. Specifically, our method uses the augmented Lagrangian function to deal with inequality constraints, and solves one subproblem on the oblique manifold by a regularized Newton method. Numerical results on the multiple-input multiple-output detection problem, the maxcut problem and the quadratic 0 - 1 problem indicate that our proposed algorithm has advantage over the SDP methods.

关键词： binary quadratic programming Alternating direction method of multipliers Riemannian manifold Entropy penalty Low-rank factorization

来源：评论

学校读者我要写书评

暂无评论

A Fast binary quadratic programming Solver Based on Stochastic Neighborhood Search

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2022年第1期44卷 32-49页

作者： Lam, Benson Shu Yan Liew, Alan Wee-Chung Hang Seng Univ Hong Kong Dept Math Stat & Insurance Sin Lek Yuen Hong Kong Peoples R China Griffith Univ Sch Informat & Commun Technol Brisbane Qld Australia

Many image processing and pattern recognition problems can be formulated as binary quadratic programming (BQP) problems. However, solving a large BQP problem with a good quality solution and low computational time is still a challenging unsolved problem. Current methodologies either adopt an independent random search in a semi-definite space or perform search in a relaxed biconvex space. However, the independent search has great computation cost as many different trials are needed to get a good solution. The biconvex search only searches the solution in a local convex ball, which can be a local optimal solution. In this paper, we propose a BQP solver that alternatingly applies a deterministic search and a stochastic neighborhood search. The deterministic search iteratively improves the solution quality until it satisfies the KKT optimality conditions. The stochastic search performs bootstrapping sampling to the objective function constructed from the potential solution to find a stochastic neighborhood vector. These two steps are repeated until the obtained solution is better than many of its stochastic neighborhood vectors. We compare the proposed solver with several state-of-the-art methods for a range of image processing and pattern recognition problems. Experimental results showed that the proposed solver not only outperformed them in solution quality but also with the lowest computational complexity.

关键词： binary quadratic programming stochastic optimization binary restoration graph bisection optimization

来源：评论

学校读者我要写书评

暂无评论

Global Optimization of binary quadratic programming: A Neural Network Based Algorithm and Its FPGA Implementation

引用

NEURAL PROCESSING LETTERS 2019年第3期53卷 1665-1684页

作者： Gu, Shenshen Chen, Xinyi Wang, Lin Shanghai Univ Sch Mechatron Engn & Automat 99 Shangda Rd Shanghai Peoples R China

The global optimization of binary quadratic programming (BQP) has very important theory and wide application in various fields. Since BQP is a classic NP-hard problem, traditional algorithms will be very time-consuming when the dimension is very large. The neural network based algorithms have significant advantages in solving large scale optimization problems. However, directly applying neural network based algorithm cannot guarantee finding the global optimal solution of BQP. In this paper, we propose a neural network based algorithm for BQP by analyzing and utilizing geometric characteristics of the objective function isosurface and combining the advantages and properties of neural network as well as branch-and-bound method. Furthermore, the neural network algorithm is implemented with field-programmable gate array (FPGA) to take advantage of the parallel structure. System Generator which can be used to convert the design into HDL code automatically is adopted so that the calculation of upper and lower bounds can be deployed to FPGA. The numerical simulation illustrates the effectiveness and efficiency of the algorithm. Meanwhile, simulation results show the feasibility of applying the proposed algorithm to FPGA hardware.

关键词： binary quadratic programming Branch-and-bound Neural network FPGA implementation

来源：评论

学校读者我要写书评

暂无评论

A New Relaxation Method for binary quadratic programming: An Application to Densest k-subgraph

A New Relaxation Method for Binary Quadratic Programming: An...

引用

2018 International Conference on Mathematics, Modelling, Simulation and Algorithms（MMSA2018）

作者： Chuanhao Guo Liping Tang School of Economics and Management Zhejiang Sci-Tech University College of Mathematics and Statistics Chongqing Technology and Business University

ISBN: (纸本)9781510863064

binary quadratic programming(BQP) problem was an NP-hard problem and had a large number of applications. In this paper, a new relaxation method, that was doubly nonnegative relaxation, was proposed for solving BQP problem. Moreover, we prove that the doubly nonnegative relaxation for BQP is equivalent to a new tighter semidifinite relaxation. When BQP problem reduces to densest k-subgraph problem, the doubly nonnegative relaxation is equivalent to a tighter semidifinite relaxation. Finally, some comparative numerical results are reported to show that the efficiency of the doubly nonnegative relaxation is more promising than that of semidefinite relaxation for solving some specific BQP problems.

关键词： binary quadratic programming doubly nonnegative relaxation semidefinite relaxation densest k-subgraph

来源：评论

学校读者我要写书评

暂无评论

Solving the maximum vertex weight clique problem via binary quadratic programming

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第2期32卷 531-549页

作者： Wang, Yang Hao, Jin-Kao Glover, Fred Lu, Zhipeng Wu, Qinghua Northwestern Polytech Univ Sch Management 127 Youyi West Rd Xian 710072 Peoples R China Univ Angers LERIA 2 Blvd Lavoisier F-49045 Angers France Inst Univ France Paris France OptTek Syst Inc 2241 17th St Boulder CO 80302 USA Huazhong Univ Sci & Technol Sch Comp Sci & Technol Wuhan 430074 Peoples R China Huazhong Univ Sci & Technol Sch Management Wuhan 430074 Peoples R China

In recent years, the general binary quadratic programming (BQP) model has been widely applied to solve a number of combinatorial optimization problems. In this paper, we recast the maximum vertex weight clique problem (MVWCP) into this model which is then solved by a probabilistic tabu search algorithm designed for the BQP. Experimental results on 80 challenging DIMACS-W and 40 BHOSLIB-W benchmark instances demonstrate that this general approach is viable for solving the MVWCP problem.

关键词： Maximum vertex weight clique binary quadratic programming Probabilistic tabu search

来源：评论

学校读者我要写书评

暂无评论

An augmented Lagrangian method for binary quadratic programming based on a class of continuous functions

引用

OPTIMIZATION LETTERS 2016年第3期10卷 485-497页

作者： Mu, Xuewen Liu, Wenlong Xidian Univ Sch Math & Stat Xian 710071 Peoples R China Dalian Univ Technol Sch Informat & Commun Engn Dalian 116024 Peoples R China

In this paper, an augmented Lagrangian method is proposed for binary quadratic programming (BQP) problems based on a class of continuous functions. The binary constraints are converted into a class of continuous functions. The approach reformulates the BQP problem as an equivalent augmented Lagrangian function, and then seeks its minimizer via an augmented Lagrangian method, in which the sub-problem is solved by Barzilai-Borwein type method. Numerical results are reported for max-cut problem. The results indicate that the augmented Lagrangian approach is promising for large scale binary quadratic programming by the quality of the near optimal values and the low computational time.

关键词： binary quadratic programming Augmented Lagrangian method Max-cut Barzilai-Borwein type method Continuous functions

来源：评论

学校读者我要写书评

暂无评论

Polynomial time solvable algorithms to a class of unconstrained and linearly constrained binary quadratic programming problems

引用

NEUROCOMPUTING 2016年 198卷 171-179页

作者： Gu, Shenshen Cui, Rui Peng, Jiao Shanghai Univ Sch Mechatron Engn & Automat 149 Yanchang Rd Shanghai 200072 Peoples R China

binary quadratic programming (BQP) is a typical integer programming problem widely applied in the field of signal processing, economy, management and engineering. However, it is NP-hard and lacks efficient algorithms. Due to this reason, in this paper, some novel polynomial algorithms are proposed to solve a class of unconstrained and linearly constrained binary quadratic programming problems. We first deduce the polynomial time solvable algorithms to the unconstrained binary quadratic programming problems with Q being a seven-diagonal matrix (UBQP7) and a five-diagonal matrix (UBQP5) respectively with two different approaches. Then, the algorithm to unconstrained problem is combined with the dynamic programming method to solve the linearly constrained binary quadratic programming problem with Q being a five-diagonal matrix (LCBQP5). In addition, the polynomial solvable feature of these algorithms is analyzed and some specific examples are presented to illustrate these new algorithms. Lastly, we demonstrate their polynomial feature as well as their high efficiency. (C) 2016 Elsevier B.V. All rights reserved.

关键词： binary quadratic programming Polynomial time solvable algorithm Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

On linearization techniques for budget-constrained binary quadratic programming problems

引用

OPERATIONS RESEARCH LETTERS 2016年第6期44卷 702-705页

作者： Yang, Mei-Jia Xia, Yong Zou, Hui-Min Beihang Univ Sch Math & Syst Sci Minist Educ State Key Lab Software Dev EnvironmLMIB Beijing 100191 Peoples R China Beijing Polytech Beijing 100176 Peoples R China

Glover's linearization technique is revisited for solving the binary quadratic programming problem with a budget constraint (BBQP). When compared with the recent two linearizations for (BBQP), it not only provides a tighter relaxation at the root node, but also has a much better computational performance for globally solving (BBQP). (C) 2016 Elsevier B.V. All rights reserved.

关键词： binary quadratic programming Budget constraint Linearization Linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

f-Flip strategies for unconstrained binary quadratic programming

引用

ANNALS OF OPERATIONS RESEARCH 2016年第1-2期238卷 651-657页

作者： Glover, Fred Hao, Jin-Kao Univ Colorado Leeds Sch Business Boulder CO 80309 USA Univ Angers LERIA F-49045 Angers France Inst Univ France Paris France

Unconstrained binary quadratic programming (UBQP) provides a unifying modeling and solution framework for solving a remarkable range of binary optimization problems, including many accompanied by constraints. Current methods for solving UBQP problems customarily rely on neighborhoods consisting of flip moves that select one or more binary variables and "flip" their values to the complementary value (from 1 to 0 or from 0 to 1). We introduce a class of approaches called f-flip strategies that include a fractional value f as one of those available to the binary variables during intermediate stages of solution. A variety of different f-flip strategies, particularly within the context of multi-start algorithms, are proposed for pursuing intensification and diversification goals in metaheuristic algorithms, accompanied by special rules for evaluating and executing f-flips efficiently.

关键词： 0-1 Optimization binary quadratic programming Metaheuristics Multi-start algorithms Computational efficiency

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：