Kim Y , Mesbahi M . On Maximizing the Second Smallest Eigenvalue of a State-Dependent Graph Laplacian[J]. IEEE Transactions on Automatic Control, 2006, 51(1):116-120.

1. Introduction

Problem: finding the best vertex positional configuration in the presence of an additional proximity constraint to maximize algebraic connectivity.

Algebraic connectivity（代數(shù)連通度）：拉普拉斯矩陣的第二小的特征值，反映圖的穩(wěn)定性和健壯性的關(guān)鍵指標(biāo)。

$\mathcal{G}$ : A graph of fixed order (頂點(diǎn)個(gè)數(shù)) and weighted edges.?Weight:? $w: \mathbb{R}^3 \times \mathbb{R}^3 \rightarrow \mathbb{R}_+$ ， $w_{ij}:=w(x_i,x_j)=f(\parallel x_i-x_j\parallel)$ ，邊的權(quán)重的值為關(guān)于兩個(gè)頂點(diǎn)間距離的函數(shù)。

$\Lambda :\mathop{max}\limits_{x} \lambda_2(L_G(x))$ ， $L_G(x)$ :帶權(quán)拉普拉斯矩陣。 $[L_G(x)]_{ij}:=\left\{\begin{array}{lr} -w_{ij}&if~i \neq j \\ \sum\nolimits_{s \neq i} w_{is} &if~i=j \\ \end{array} \right.$

Proximity Constraint: 兩個(gè)頂點(diǎn)間的距離不能小于特定值 $\rho _1$ 。

$d_{ij}:=\parallel x_i-x_j \parallel \geq \rho_1, for~all~i \neq j$ . (1)

2. Method

An iterative SDP-based approach for the problem is proposed.

函數(shù) $f$ 的選擇。 $f(d_{ij})=\epsilon ^{(\rho_1-d_{ij})/(\rho_1-\rho_2)}, \epsilon >0$ 。具有可微性，且反映了現(xiàn)實(shí)場(chǎng)景。節(jié)點(diǎn)間相對(duì)距離達(dá)到給定閾值后，鏈路的強(qiáng)度會(huì)隨著距離的增加而呈現(xiàn)指數(shù)下降。

2.1 maximizing? $\lambda_2(L_G)$

Proposition 2.1: $P:=[p_1,\dots,p_m] \in R^{n \times m}$ 表示由向量 $p_i \in \mathbb{R}^n,i=1,\dots,m$ 組成的m維子空間， $P \subseteq \mathbb{R}^n$ ，對(duì)于 $M \in S^n$ ，當(dāng)且僅當(dāng) $P^TMP>0$ 時(shí)， $x^TMx>0$ ,其中， $x \in P$ 為非零元素。 $x=\alpha_1 p_1+\alpha_2 p_2+\dots+\alpha_m p_m$ , $\alpha_1,\dots,\alpha_m \in \mathbb{R}$ 不全為0.

Corollary 2.2: 對(duì)于拉普拉斯矩陣 $L_G$ ,約束 $\lambda _2(L_G)>0$ 與 $P_TL_GP>0$ 等價(jià)， $P=[p_1,p_2,\dots,p_{n-1}]$ , $p_i \in \mathbb{R}^n$ 滿足 $p_i^T 1=0, i=1,2,\dots,n-1$ 和 $p_i^Tp_j=0~(i \neq j)$ 。