A primal quadratic simplex algorithm tailored to the optimization over the vertices of a polytope is presented. Starting from a feasible vertex, it performs either strictly improving or admissible ...non-deteriorating steps in order to determine a locally optimum basic feasible solution in terms of the quadratic objective function. The algorithm so generalizes over local improvement methods for according applications, including in particular quadratic optimization problems whose feasible solutions correspond to vertices of a 0-1 polytope. Computational experiments for unconstrained binary quadratic programs, maximum cut, and the quadratic assignment problem serve as a proof of concept and underline the importance of a pivoting rule that is able to accept at least a restricted class of degenerate steps.
This paper investigates the problem of channel selection in Wi-Fi 6E networks by modeling it as a congestion game, where access points (APs) aim to minimize their own co-channel interference (CCI) ...selfishly. We study the existence and the number of pure strategy Nash equilibria (PSNEs), the convergence to these equilibria, and the global optimal solution through best response dynamics (BRD). We provide theoretical proof for the existence and convergence properties and propose an algorithm for channel selection in Wi-Fi 6E networks based on the obtained results. Our findings suggest that the proposed BRD-based algorithm can achieve a global optimal solution in a distributed manner, offering a promising approach for efficient channel selection in Wi-Fi 6E networks.
In order to explore the minimum switching frequency required to regulate certain amount of harmonic components, a novel switching frequency minimized harmonic mitigation (SFMHM) model is proposed in ...this paper, which can regulate <inline-formula><tex-math notation="LaTeX"> \mathit{N}\mathbf{-1}</tex-math></inline-formula> harmonics with far less than N switching angles. By flexibly adjusting the threshold values, the proposed model can achieve both harmonic elimination and mitigation objectives. Based on PWM discretization and supported by quadratic programming, the switching frequency in the proposed model is expressed as a quadratic objective function of the PWM waveform. The objectives as fundamental control and selected harmonic mitigations are realized by treating the numerical approximations of the Fourier coefficients as constraints, which are finally transformed into an optimization model with binary variables and can be easily solved by some optimization toolboxes such as YALMIP. Some computing results show that, compared with the conventional selective harmonic elimination/mitigation (SHE/SHM) methods, the number of switching angles required to mitigate the same number of harmonics under the proposed method has been significantly reduced. The switching frequency can be reduced a lot compared with the conventional SHE/SHM methods, e.g., by 40% for some modulation indexes. Simulations and experiments verify the correctness of proposed SFMHM model.
The boolean quadratic programming problem with generalized upper bound constraints (BQP-GUB) is an NP-hard problem with many practical applications. In this study, we propose an effective multi-wave ...tabu search algorithm for solving BQP-GUB. The algorithm performs a sequence of search waves, where each wave alternates between the forward and reverse phases, and the transition between two adjacent waves depends on a hybrid perturbation phase. The forward phase employs tabu search to reach a critical solution and the reverse phase follows to reverse previously performed moves and perform an equal number of moves by referring to the search information gathered from the latest search process. The hybrid perturbation phase randomly chooses a directed strategy, a frequency guided strategy and a recency guided strategy to achieve search diversification. Experimental results on 78 standard instances indicate that the proposed algorithm is able to improve the lower bounds for 6 instances and match the best solutions in the literature for most instances within competitive time.
•Propose a multi-wave tabu search algorithm for BQP-GUB.•Design a tabu search based forward phase for intensification.•Design an information guided reverse phase for adjustments.•Employ memory based strategies to guide search process.•Find new lower bounds for 6 instances.
Beam Hopping (BH) is a popular technique considered for next-generation multi-beam satellite communication system which allows a satellite focusing its resources on where they are needed by ...selectively illuminating beams. While beam illumination plan can be adjusted according to its needs, the main limitation of convectional BH is the adjacent beam avoidance requirement needed to maintain acceptable levels of interference. With the recent maturity of precoding technique, a natural way forward is to consider a dynamic beam illumination scheme with selective precoding, where large areas with high-demand can be covered by multiple active precoded beams. In this paper, we mathematically model such beam illumination design problem employing an interference-based penalty function whose goal is to avoid precoding whenever possible subject to beam demand satisfaction constraints. The problem can be written as a binary quadratic programming (BQP). Next, two convexification frameworks are considered namely: (i) A Semi-Definition Programming (SDP) approach particularly targeting BQP type of problems, and (ii) Multiplier Penalty and Majorization-Minimization (MPMM) based method which guarantees to converge to a local optimum. Finally, a greedy algorithm is proposed to alleviate complexity with minimal impact on the final performance. Supporting results based on numerical simulations show that the proposed schemes outperform the relevant benchmarks in terms of demand matching performance while minimizing the use of precoding.
•Polynomial-size formulations of the quadratic multiple knapsack problem from classical 0-1 quadratic programming reformulations.•New level-1 decomposable reformulation linearization techniques for ...the problem.•Comparison of LP, surrogate, and Lagrangian relaxations.•Theoretical properties and dominances.•Computational experiments on a large set of benchmark instances.
The Quadratic Multiple Knapsack Problem generalizes, simultaneously, two well-known combinatorial optimization problems that have been intensively studied in the literature: the (single) Quadratic Knapsack Problem and the Multiple Knapsack Problem. The only exact algorithm for its solution uses a formulation based on an exponential-size number of variables, that is solved via a Branch-and-Price algorithm. This work studies polynomial-size formulations and upper bounds. We derive linear models from classical reformulations of 0-1 quadratic programs and analyze theoretical properties and dominances among them. We define surrogate and Lagrangian relaxations, and we compare the effectiveness of the Lagrangian relaxation when applied to a quadratic formulation and to a Level 1 reformulation linearization that leads to a decomposable structure. The proposed methods are evaluated through extensive computational experiments.
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.
This paper 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 <inline-formula><tex-math notation="LaTeX">t</tex-math></inline-formula> 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.
This article presents BiqCrunch , an exact solver for binary quadratic optimization problems. BiqCrunch is a branch-and-bound method that uses an original, efficient semidefinite-optimization-based ...bounding procedure. It has been successfully tested on a variety of well-known combinatorial optimization problems, such as Max-Cut, Max- k -Cluster, and Max-Independent-Set. The code is publicly available online; a web interface and many conversion tools are also provided.
PDF
