{-1，1}二次規(guī)劃算法及其應(yīng)用研究.pdf

1、{-1,1}二次規(guī)劃是一類十分重要的整數(shù)規(guī)劃問(wèn)題.許多經(jīng)典的組合優(yōu)化問(wèn)題，如最大割問(wèn)題、圖的最大二等分問(wèn)題以及最大團(tuán)等問(wèn)題都是它的特例.它在大規(guī)模集成電路設(shè)計(jì)、統(tǒng)計(jì)物理、金融分析、多用戶檢測(cè)以及信號(hào)處理等實(shí)際問(wèn)題中有著廣泛的應(yīng)用.因此，研究{-1,1}二次規(guī)劃的算法及其應(yīng)用具有重要的理論意義和實(shí)用價(jià)值. {-1,1}二次規(guī)劃問(wèn)題是NP難問(wèn)題，它不存在多項(xiàng)式時(shí)間的全局優(yōu)化算法.本文主要研究了{(lán)-1,1}二次規(guī)劃的一些近似求解算法和

2、一些帶預(yù)處理的優(yōu)化算法，并把這些算法應(yīng)用到多用戶檢測(cè)問(wèn)題和離散系數(shù)的FIR數(shù)字濾波器設(shè)計(jì)問(wèn)題中.主要內(nèi)容如下: 1.基于{-1,1}二次規(guī)劃的半定規(guī)劃松弛模型，利用矩陣分解技巧和低秩分解技巧得到與半定規(guī)劃松弛模型等價(jià)的非線性規(guī)劃模型，提出求解該模型的序列線性規(guī)劃算法和序列二次規(guī)劃算法.在一定的條件下，證明了算法的全局最優(yōu)性.結(jié)合隨機(jī)擾動(dòng)算法給出了{(lán)-1,1}二次規(guī)劃的一個(gè)較好的近似解.對(duì)最大割問(wèn)題和圖的最大二等分問(wèn)題的數(shù)值實(shí)驗(yàn)表

3、明:上述算法在時(shí)間和內(nèi)存的利用上要優(yōu)于半定規(guī)劃內(nèi)點(diǎn)算法，尤其對(duì)于大規(guī)模的半定規(guī)劃松弛問(wèn)題. 2.基于{-1,1}二次規(guī)劃問(wèn)題的結(jié)構(gòu)特性，利用{-1,1}二次規(guī)劃的全局最優(yōu)性必要條件，提出了一種預(yù)處理算法，該方法可以確定{-1,1}二次規(guī)劃的最優(yōu)解中的大部分元素的取值，把原問(wèn)題等價(jià)轉(zhuǎn)化為一個(gè)規(guī)模較小的二次整數(shù)規(guī)劃模型.然后基于預(yù)處理算法，結(jié)合求解{-1,1}二次規(guī)劃的一些有效算法，如基于半定規(guī)劃的隨機(jī)擾動(dòng)算法，分支定界算法，互補(bǔ)算

4、法，得到了求解{-1,1}二次規(guī)劃問(wèn)題的三種有效算法. 3.利用前面提出的基于序列二次規(guī)劃的隨機(jī)擾動(dòng)算法、帶預(yù)處理的隨機(jī)擾動(dòng)算法、帶預(yù)處理的分支定界算法以及帶預(yù)處理的互補(bǔ)算法研究了多用戶檢測(cè)問(wèn)題和離散系數(shù)的FIR數(shù)字濾波器設(shè)計(jì)問(wèn)題.其中帶預(yù)處理的隨機(jī)擾動(dòng)算法和帶預(yù)處理的互補(bǔ)算法不僅在性能上優(yōu)于已有的基于半定規(guī)劃的隨機(jī)擾動(dòng)算法，而且大大節(jié)省了CPU的計(jì)算時(shí)間.基于序列二次規(guī)劃的隨機(jī)擾動(dòng)算法在CPU的計(jì)算時(shí)間方面要優(yōu)于已存在的基于半