1
我正在考慮使用cvxopt來解決一些非線性網絡流量優化問題。爲了理解基礎知識，我用一個非常簡單的測試網絡來測試它，只有4個頂點和5個邊。爲什麼CVXOPT爲這種非線性網絡流量優化提供排名誤差？
我的網絡看起來像this。藍色和紅色節點分別是源和匯。
在每個邊緣上的成本是：
alpha*x**2
x表示包含在每個邊緣上的流動的矢量，和α是一些係數。我的優化問題是：
min sum(alpha*x**2)
subject to:
E*x = b
x >= 0
其中E是邊緣弧關聯矩陣，b是包含源和匯的向量。因此矩陣向量方程Ex = b應該強制實施基爾霍夫定律（即每個節點的流量守恆）。
我的Python腳本來做到這一點：
from cvxopt import matrix, spdiag, solvers
#Four vertices, five edges
E = matrix(0.0, (4,5))
E[0,0] = 1.0
E[0,1] = 1.0
E[1,0] = -1.0
E[1,2] = 1.0
E[1,3] = 1.0
E[2,1] = -1.0
E[2,2] = -1.0
E[2,4] = 1.0
E[3,3] = -1.0
E[3,4] = -1.0
#Source-sink vector
b = matrix(0.0, (4,1))
b[0] = 0.5
b[3] = -0.5
#Coefficient in the quadtratic
alpha = 1.0
#Function to pass to cvxopt
def F(x=None, z=None):
if x is None:
return 0, matrix(0.05, (5,1))
if min(x) <= 0.0:
return None
f = sum(alpha*(x**2))
Df = (2.0*alpha*x).T
if z is None:
return f, Df
D2f = 2.0*alpha*matrix(1.0, (5,1))
H = spdiag(z[0]*D2f)
return f, Df, H
#Solve
x = solvers.cp(F, A=E, b=b)['x']
我得到的錯誤是：
pcost dcost gap pres dres
0: 0.0000e+00 1.2500e-02 1e+00 1e+00 2e-01
Traceback (most recent call last):
File "simple_network.py", line 45, in <module>
x = solvers.cp(F, A=E, b=b)['x']
File "/usr/local/lib/python2.7/dist-packages/cvxopt/cvxprog.py", line 1966, in cp
xdot_e, xaxpy_e, xscal_e, options = options)
File "/usr/local/lib/python2.7/dist-packages/cvxopt/cvxprog.py", line 782, in cpl
raise ValueError("Rank(A) < p or "\
ValueError: Rank(A) < p or Rank([H(x); A; Df(x); G]) < n
我不確定如何從這裏着手。我認爲這個優化問題可以用cvxopt解決，因爲它足夠簡單，可以手工找到最佳流程。如果有人能告訴我如何糾正這些代碼，或者告訴我爲什麼這種類型的問題不適用於此軟件，我將不勝感激。
在此先感謝。