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

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

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

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

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