圖拉普拉斯矩陣特征值優(yōu)化及其應(yīng)用.pdf

1、譜圖論是一種常用的研究方法,其可以利用拉普拉斯矩陣來(lái)描述圖的結(jié)構(gòu)。通過(guò)分析拉普拉斯矩陣及其特征值能夠?qū)D結(jié)構(gòu)有更清晰的認(rèn)識(shí),特別是在很多情況下,需要提高拉普拉斯矩陣的次小特征值λ2,以使圖結(jié)構(gòu)得到優(yōu)化。在一定約束條件下,提高λ2是一個(gè)典型的優(yōu)化問(wèn)題。部分優(yōu)化問(wèn)題的求解較為困難,但是對(duì)于凸優(yōu)化問(wèn)題,存在著一系列有效的求解算法。半正定規(guī)劃是凸優(yōu)化問(wèn)題的一種特殊形式,因此,將一個(gè)優(yōu)化問(wèn)題轉(zhuǎn)換為半正定規(guī)劃問(wèn)題后,則說(shuō)明該問(wèn)題可解。
　　本

2、文主要關(guān)注于在交通網(wǎng)絡(luò)規(guī)劃問(wèn)題以及影響力提高問(wèn)題中,λ2的提高在相應(yīng)問(wèn)題中的作用,并且將該問(wèn)題轉(zhuǎn)換為半正定規(guī)劃問(wèn)題從而進(jìn)行求解。
　　交通網(wǎng)絡(luò)規(guī)劃問(wèn)題是指,為了應(yīng)對(duì)越來(lái)越多的交通需求,如何在一定的約束條件下,對(duì)現(xiàn)有的交通網(wǎng)絡(luò)中部分道路進(jìn)行擴(kuò)展,以使得整個(gè)交通網(wǎng)絡(luò)的性能達(dá)到最優(yōu)。交通網(wǎng)絡(luò)規(guī)劃問(wèn)題的求解較為困難。通常一個(gè)交通網(wǎng)絡(luò)的直徑越小,交通網(wǎng)絡(luò)的連通情況越好,越有利于出行。因此,規(guī)劃一個(gè)具有較小直徑的交通網(wǎng)絡(luò)符合出行的需求。對(duì)于交

3、通網(wǎng)絡(luò)直徑與λ2的關(guān)系,本文證明,提高λ2,能夠同時(shí)降低交通網(wǎng)絡(luò)直徑的上界和下界。于是,將交通網(wǎng)絡(luò)規(guī)劃的目標(biāo)由降低交通網(wǎng)絡(luò)的直徑,轉(zhuǎn)變?yōu)樘岣擀?。該問(wèn)題可以轉(zhuǎn)換為半正定規(guī)劃形式,即該問(wèn)題可解。
　　影響力提高問(wèn)題是為了在社會(huì)網(wǎng)絡(luò)中銷(xiāo)售某一商品而提出的。影響力提高問(wèn)題是指在經(jīng)過(guò)影響力最大化問(wèn)題后,提高社會(huì)網(wǎng)絡(luò)中某些個(gè)體與個(gè)體間的影響程度,來(lái)促進(jìn)網(wǎng)絡(luò)中商品信息的傳播,提高整個(gè)商品在社會(huì)網(wǎng)絡(luò)中的影響力,并且最終達(dá)到提高商品銷(xiāo)售量的目的。