在上一篇 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)。