Paper Info
Title
On the Approximate Solution of a Class of Large Discrete Quadratic Programming Problems by Modulation: The Case of Circulant Quadratic Forms
Abstract
We show that ΔΣ modulators can be interpreted as heuristic solvers for a particular class of optimization problems. Then, we exploit this theoretical result to propose a novel technique to deal with very large unconstrained discrete quadratic programming (UDQP) problems characterized by quadratic forms entailing a circulant matrix. The result is a circuit-based optimization approach involving a recast of the original problem into signal processing specifications, then tackled by the systematic design of an electronic system. This is reminiscent of analog computing, where untreatable differential equations were solved by designing electronic circuits analog to them. The approach can return high quality suboptimal solutions even when many hundreds of variables are considered and proved faster than conventional empirical optimization techniques. Detailed examples taken from two different domains illustrate that the range of manageable problems is large enough to cover practical applications.
Year
DOI
Venue
2010
10.1109/TSP.2010.2071866
IEEE Transactions on Signal Processing
Keywords
Field
DocType
modulators,quadratic programming,signal processing,circulant matrix,circulant quadratic form,empirical optimization,modulator,signal processing,unconstrained discrete quadratic programming,Approximation,delta-sigma modulation,integer programming,optimization
Heuristic,Mathematical optimization,Quadratic form,Control theory,Delta modulation,Delta-sigma modulation,Circulant matrix,Integer programming,Quadratic programming,Optimization problem,Mathematics
Journal
Volume
Issue
ISSN
58
12
1053-587X
Citations 
PageRank 
References 
9
1.26
8
Authors
4
Name
Order
Citations
PageRank
Sergio Callegari111218.52
Federico Bizzarri213131.78
Riccardo Rovatti337754.32
Gianluca Setti447871.19