Back to Search
Start Over
On the Approximate Solution of a Class of Large Discrete Quadratic Programming Problems by $\Delta\Sigma$ Modulation: The Case of Circulant Quadratic Forms
- Source :
- IEEE Transactions on Signal Processing. 58:6126-6139
- Publication Year :
- 2010
- Publisher :
- Institute of Electrical and Electronics Engineers (IEEE), 2010.
-
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.
- Subjects :
- Mathematical optimization
Optimization problem
sezele
CIRCULANT MATRIX
Heuristic (computer science)
UNCONSTRAINED BINARY QUADRATIC PROGRAMMING
delta-sigma modulation
Delta-sigma modulation
DELTA-SIGMA MODULATOR
Delta modulation
Quadratic form
Signal Processing
Approximation
integer programming
optimization
Quadratic programming
Electrical and Electronic Engineering
Integer programming
Circulant matrix
Mathematics
Subjects
Details
- ISSN :
- 19410476 and 1053587X
- Volume :
- 58
- Database :
- OpenAIRE
- Journal :
- IEEE Transactions on Signal Processing
- Accession number :
- edsair.doi.dedup.....a0150e6d7b728b872210685afe58334f