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（代数连通度）：拉普拉斯矩阵的第二小的特征值，反映图的稳定性和健壮性的关键指标。

$\mathcal{G}$ : A graph of fixed order (顶点个数) 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)$ ，边的权重的值为关于两个顶点间距离的函数。

$\Lambda :\mathop{max}\limits_{x} \lambda_2(L_G(x))$ ， $L_G(x)$ :带权拉普拉斯矩阵。 $[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: 两个顶点间的距离不能小于特定值 $\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.

函数 $f$ 的选择。 $f(d_{ij})=\epsilon ^{(\rho_1-d_{ij})/(\rho_1-\rho_2)}, \epsilon >0$ 。具有可微性，且反映了现实场景。节点间相对距离达到给定阈值后，链路的强度会随着距离的增加而呈现指数下降。

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$ ，对于 $M \in S^n$ ，当且仅当 $P^TMP>0$ 时， $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: 对于拉普拉斯矩阵 $L_G$ ,约束 $\lambda _2(L_G)>0$ 与 $P_TL_GP>0$ 等价， $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)$ 。