Sedumi軟件包在教學(xué)和科研中的應(yīng)用

蔣俊正，周 芳

(桂林電子科技大學(xué)1信息與通信學(xué)院，2.生命和環(huán)境科學(xué)學(xué)院，廣西桂林 541004)

Sedumi軟件包最早由加拿大Mcmaster大學(xué)的研究人員于上世紀(jì)90年代后期提出，它基于Matlab語言開發(fā)主要用于求解半定規(guī)劃問題［1］。在“數(shù)字信號處理”和“最優(yōu)化理論與方法”等電子信息類課程教學(xué)和科研中，很多問題都可以歸結(jié)為某種優(yōu)化問題，可以直接或間接地使用Sedumi軟件包進行有效求解。

1 Sedumi標(biāo)準(zhǔn)形式下的使用

半定規(guī)劃問題可以直接使用Sedumi軟件包進行求解［2-4］。下面筆者分別介紹線性規(guī)劃、二階錐規(guī)劃和半定規(guī)劃問題的標(biāo)準(zhǔn)形式以及求解的Matlab代碼。

1)線性規(guī)劃

用于求解問題(1)的Matlab代碼為

［x，y，info］=sedumi(A，b，c)

代碼中向量y是最優(yōu)解，info包含了一些輔助信息，比如求解耗時等。

2)二階錐規(guī)劃

用于求解問題(2)的Matlab代碼為

K.1=m;

K.q=q;

［xs，ys，info］=sedumi(At，bt，ct，K);

代碼中m等于矩陣D的行數(shù)，即線性約束的個數(shù)。代碼參數(shù)為

3)半定規(guī)劃

式中，矩陣Fi，i=0，…，p為對稱矩陣。用于求解問題(4)的Matlab代碼為

K.S=size(F0，1);

［x，y，info］=sedumi(At，bt，ct，K);

info代碼中參數(shù)為

由于Sedumi軟件包在求解中采用了對偶理論，因此求解效率很高。

2 Sedumi非標(biāo)準(zhǔn)形式下的使用

然而在實際中，很多的優(yōu)化問題并不具備上述的三種標(biāo)準(zhǔn)形式，導(dǎo)致Sedumi軟件包的使用并非如上述那么直觀。因此，如何將非標(biāo)準(zhǔn)形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式，是有效利用Sedumi的關(guān)鍵所在。

我們以二次規(guī)劃問題轉(zhuǎn)化為二階錐規(guī)劃問題為例進行說明。二次規(guī)劃問題是指目標(biāo)函數(shù)是關(guān)于優(yōu)化變量的二次函數(shù)、約束是線性函數(shù)的優(yōu)化問題:

其中，矩陣A是正定的。引入輔助變量 ，問題(6)可等價為

式中代碼參數(shù)為

式中m為x的長度，N為D的行數(shù)。

3 Sedumi軟件包的應(yīng)用舉例

FIR數(shù)字濾波器的設(shè)計問題可以歸結(jié)為一個優(yōu)化問題［5-7］。通常，濾波器的性能指標(biāo)包括:阻帶衰減和通帶平坦性。一個性能優(yōu)良的濾波器應(yīng)該具備阻帶衰減高且通帶平坦，數(shù)學(xué)描述為

式中，ωp和ωs分別為低通濾波器的通帶和阻帶的截止頻率。假定一個線性相位的低通濾波器的系數(shù)滿足:

其頻率響應(yīng)可表示為

式中

設(shè)計阻帶衰減高且通帶平坦的濾波器可以歸結(jié)為如下優(yōu)化問題:

式中εp為容許誤差。將式(11)代入式(13)，并對區(qū)間［0，ωp］進行等間隔離散化 ωk=kωp/K，k=0，…，K，可得

設(shè)計所得的濾波器的沖激響應(yīng)和幅度響應(yīng)如圖1所示?？梢钥闯?，該濾波器具備良好的頻率特性，即通帶平坦、阻帶衰減高。

圖1 Sedumi軟件設(shè)計所得的濾波器

4 結(jié)語

本文首先介紹Sedumi優(yōu)化軟件包求解問題的三種標(biāo)準(zhǔn)形式和相應(yīng)的Matlab代碼，然后以二次規(guī)劃為例說明如何將非標(biāo)準(zhǔn)形式轉(zhuǎn)化標(biāo)準(zhǔn)形式，最后將Sedumi應(yīng)用于數(shù)字濾波器設(shè)計問題求解。在教學(xué)和科研中出現(xiàn)的非標(biāo)準(zhǔn)形式優(yōu)化問題，如何進行轉(zhuǎn)化，并采用Sedumi求解仍需進一步探討和研究。

［1］ J.F.Sturm.Using SeDuMi 1.02，a MATLAB toolbox for optimization over symmetric cones［J］.Optimization methods and software，1999，11(1-4):625-653.

［2］ 袁亞湘，孫文瑜.最優(yōu)化理論與方法［M］.北京:科學(xué)出版社，1997.

［3］ D.P.Palomar，and Y.C.Eldar.Convex optimization in signal processing and communications［M］.Cambridge University Press，2010.

［4］ Z.Q.Luo，and Y.Wei.An introduction to convex optimization for communications and signal processing［J］.IEEE Journal on Selected Areas in Communications，2006，24(8):1426-1438.

［5］ 陳懷琛，王朝英，高西全等.數(shù)字信號處理及其 MATLAB實現(xiàn)［M］.北京:電子工業(yè)版社，1998.

［6］ 郭建濤.“數(shù)字信號處理”課程的Matlab教學(xué)研究［J］.電氣電子教學(xué)學(xué)報，2010，32(3):117-119.［7］ T.N.Davidson，Z.Q.Luo，and J.F.Sturm.Linear matrix inequality formulation of spectral mask constraints with applications to FIR filter design［J］.IEEE Transactions on Signal Processing，2002，50(11):2702-2715.