在上一篇 Congested network笔记(2) 的最后，我们把问题变成了变分不等式的求解，那么这两个变分不等式在什么情况下存在解，且解唯一呢？

$$\left\{\begin{align}\frac{\partial\mathcal{Z(F)}}{\partial\underline{\mathcal{F}}}\cdot(\mathcal{F}-\underline{\mathcal{F}})&\ge 0&\forall \mathcal{F}\in S&\text{  最优解}\\
\mathcal{C}(\mathcal{F}^*)\cdot(\mathcal{F}-\mathcal{F}^*)&\ge 0&\forall \mathcal{F}\in S&\text{ 均衡解}\end{align}\right.$$

对于这两个变分不等式解的存在性和唯一性，可以这样通过Hussian矩阵判断

均衡解：令矩阵

$$A=\left(\frac{\partial\mathcal{C}_i}{\partial\mathcal{F}_j}\right)$$

如果矩阵\(A\)是正定的，那么它的解存在且是唯一的。

最优解：令矩阵
$$A=\left(\frac{\partial^2\mathcal{Z}}{\partial\mathcal{F}_i\partial\mathcal{F}_j}\right)$$

如果矩阵\(A\)是正定的，那么它的解存在且是唯一的

那么如何判断一个矩阵是否正定呢？根据定义，如果一个矩阵正定，则有

$$\left\{\begin{align}x^tAx&\gt 0\\
\forall x\in R^n, x&\not=0\end{align}\right.$$

比如对这个特殊的矩阵\(A_{1\times 1}=2\)，按照上面的定义有

$$x\cdot 2\cdot x=2x^2\gt 0 \quad \text{if } x\not=0$$

对于一个一般的 3x3 矩阵\(A\)

$$A=\left(\begin{array}{}2 & 0 & 1\\
0 & 3 & 0\\
1 & 0 & 2\end{array}\right)$$

判断它是否正定的过程如下

先令一个具有 3 个分量列向量

$$x=\left(\begin{array}{x}x_1\\
x_2\\
x_3\end{array}\right)$$

然后

$$\begin{align}x^tAx&=x^t\left(\begin{array}{A}2 & 0 & 1\\  
0 & 3 & 0\\
1 & 0 & 2\end{array}\right)\left(\begin{array}{x}x_1\\
x_2\\
x_3\end{array}\right)\\
&=\left(x_1 x_2 x_3\right)\left(\begin{array}{}2x_1 + x_3\\  
3x_2\\
x_1 + 2x_3\end{array}\right)\\
&=2x^2_1+x_1x_3+3x^2_2+x_1x_3+2x^2_3\\
&=(x^2_1+2x_1x_3+2x^2_3)+x^2_1+x^2_3+3x^2_2\\
&=(x_1+x_3)^2+x^2_1+x^2_3+3x^2_2\\
&\gt 0\end{align}$$

这里每一项都是平方，那么显然是大于 0 的，所以这个矩阵是正定。

现在对于另外一个 3x3 矩阵\(B\)

$$B=\left(\begin{array}{}1 & 2 & 0\\
2 & 3 & 0\\
0 & 0 & 1\end{array}\right)$$

它是否正定呢？

$$\begin{align}x^tBx&=x^t\left(\begin{array}{}1 & 2 & 0\\  
2 & 3 & 0\\
0 & 0 & 1\end{array}\right)\left(\begin{array}{x}x_1\\
x_2\\
x_3\end{array}\right)\\
&=\left(x_1 x_2 x_3\right)\left(\begin{array}{}x_1 + 2x_2\\  
2x_1+3x_2\\
x_3\end{array}\right)\\
&=x^2_1+2x_1x_2+2x_1x_2+3x^2_2+x^2_3\\
&=(x^2_1+2x_1x_2+x^2_2)+2x_1x_2+3x^2_2+x^2_3\\
&=(x_1+x_2)^2+2x^2_2+x^2_3+2x_1x_2\end{align}$$

此时我们发现计算之后有一项\(2x_1x_2\)，我们不能确定它的正负，不过当我们取如下值时

$$\left\{\begin{align}x_1&=-1\\
x_2&=1\\
x_3&=0\end{align}\right.$$

代入原式之后有

$$\begin{align}x^tBx&=(x_1+x_2)^2+3x^2_2+x^2_3+2x_1x_2\\
&=0+2+0+(-2)\\
&=0\end{align}$$

即\(x^tBx=0\)，那么说明矩阵\(B\)不是正定的。

关于矩阵是否正定，还有一个快速判断的方法，即看该矩阵是否对角占优。如果矩阵A是对角占优的，那么它是正定的。需要注意的是，这只是一个充分条件。

$$a_{ii}\gt \sum_{i\not=k}\left| a_{ik} \right|\quad \forall i$$

现在继续拿出那个出现了好多次的例子，

给定花费函数\(\mathcal{c}_a\)

$$\left\{\begin{align}\mathcal{c}_1&=f_1+5\\
\mathcal{c}_2&=2f_2+10\\
\mathcal{c}_3&=f_3+15\end{align}\right.$$

如果要判断是否存在均衡解的话，那么有

$$\mathcal{C}=\left(\begin{array}{}f_1+5\\
2f_2+10\\
f_3+15\end{array}\right)$$

接下来计算对应的矩阵\(A\)

$$\begin{align}A&=\left(\frac{\partial\mathcal{C}_i}{\partial\mathcal{F}_j}\right)\\
&=\left(\begin{array}{}\frac{\mathcal{C}_1}{\mathcal{F}_1} & \frac{\mathcal{C}_1}{\mathcal{F}_2} & \frac{\mathcal{C}_1}{\mathcal{F}_2}\\
\frac{\mathcal{C}_2}{\mathcal{F}_1} & \frac{\mathcal{C}_2}{\mathcal{F}_2} & \frac{\mathcal{C}_2}{\mathcal{F}_2}\\
\frac{\mathcal{C}_3}{\mathcal{F}_1} & \frac{\mathcal{C}_3}{\mathcal{F}_2} & \frac{\mathcal{C}_3}{\mathcal{F}_2}\end{array}\right)\\
&=\left(\begin{array}{}1 & 0 & 0\\
0 & 2 & 0\\
0 & 0 & 1\end{array}\right)
\end{align}$$

显然，这个矩阵是对角占优的，那么对于这个题的均衡解来讲是存在且唯一的。

这次让我们把例子换回最开始用的

现在给出每条线段上的花费函数

$$\mathcal{C}_i=\mathcal{F}^2_i+i\mathcal{F}_i$$

若要判断最优解是否存在，那么先写出系统的总花费函数\(\mathcal{Z}\)

$$\begin{align}\mathcal{Z}&=\mathcal{C}_1+\mathcal{C}_2+\mathcal{C}_3+\mathcal{C}_4+\mathcal{C}_5\\
&=(f^2_1+f_1)+(f^2_2+2f_2)+(f^2_3+3f_3)+(f^2_4+4f_4)+(f^2_5+5f_5)\end{align}$$

先对\(\mathcal{Z}\)求一阶偏导数

$$\left\{\begin{align}\frac{\partial\mathcal{Z}}{\partial\mathcal{F}_1}&=2f_1+1\\
\frac{\partial\mathcal{Z}}{\partial\mathcal{F}_2}&=2f_2+2\\
\frac{\partial\mathcal{Z}}{\partial\mathcal{F}_3}&=2f_3+3\\
\frac{\partial\mathcal{Z}}{\partial\mathcal{F}_4}&=2f_4+4\\
\frac{\partial\mathcal{Z}}{\partial\mathcal{F}_5}&=2f_5+5\end{align}\right.$$

对\(\mathcal{Z}\)求二阶偏导数的过程就省去了，其实基本上也能看出来了

$$A=\left(\begin{array}{A}2 & 0 & 0 & 0 & 0\\
0 & 2 & 0 & 0 & 0\\
0 & 0 & 2 & 0 & 0\\
0 & 0 & 0 & 2 & 0\\
0 & 0 & 0 & 0 & 2\end{array}\right)$$

显然，这也是一个对角占优的矩阵，即这个网络存在且只有一个最优解。

那么如果我们计算出一个系统的 Hussian 矩阵不是正定的，那种情况代表什么呢？假如我们为一个目标是求均衡解的题目计算出的Hussian矩阵如下

$$A=\left(\begin{array}{}1 & 1 & 0\\
2 & 1 & 2\\
0 & 0 & 1\end{array}\right)$$

显然，它不是对角占优的矩阵，我们需要用矩阵正定的定义来判断

$$\begin{align}x^tAx&=\left(\begin{array}{}x_1 & x_2 & x_3\end{array}\right)\left(\begin{array}{}1 & 1 & 0\\
2 & 1 & 2\\
0 & 0 & 1\end{array}\right)\left(\begin{array}{}x_1\\
x_2\\
x_3\end{array}\right)\\
&=\left(\begin{array}{}x_1 & x_2 & x_3\end{array}\right)\left(\begin{array}{}x_1+x_2\\
2x_1+x_2+2x_3\\
x_3\end{array}\right)\\
&=x^2_1+x_1x_2+2x_1x_2+x^2_2+2x_2x_3+3x^2_3\\
&=(x^2_1+2x_1x_2+x^2_2)+x_1x_2+2x_2x_3+x^2_2\\
&=(x_1+x_2)^2+x^2_2+x_1x_2+2x_2x_3\end{align}$$

此时可以看出矩阵\(A\)并不是正定矩阵。现在让我们把矩阵\(A\)还原到花费函数

$$\left\{\begin{align}\mathcal{C}_1&=f_1+f_2\\
\mathcal{C}_2&=2f_1+f_2+2f_3\\
\mathcal{C}_3&=f_3\end{align}\right.$$

从花费函数\(\mathcal{C}_1=f_1+f_2\)中，我们可以看出，线段1的花费并不主要由线段1上的流量决定，或者说线段1上的流量不占优。线段2的花费更是由线段1和线段3主导(dominant)。