Scipy.optimize.linprog 到目前为止还没有找到这个问题的最优成本。为什么？

Question

我有一个随机向量

v

，我想解决以下线性优化问题：

这可以表示为线性规划 其中

W

使得

[v,W]

形成可逆矩阵。

为了将其输入

scipy.optimize.linprog

，我写

但是，我没有找到我期望的结果。事实上，我可以很容易地产生一个可行的点，击败

linprog

（到目前为止）的结果，注意到成本至多是

k = np.linalg.norm(v)**2 / np.linalg.norm(v, ord=1)

，因为

z = k*np.sign(v)

总是验证z-v垂直于v。谁能告诉我我为什么会这样？是我使用方式有问题吗

linprog

？

这是我的代码：

def random_orthonormal_basis(n):
    # Generate a random matrix
    random_matrix = np.random.normal(size=(n, n))

    # Perform QR decomposition to obtain an orthonormal basis
    q, _ = np.linalg.qr(random_matrix)

    return q

def affine_max_norm_min(dim_space, dim_subspace):
    U = random_orthonormal_basis(dim_space)
    v = U[:,0]
    W = U[:,1:dim_subspace+1]

    # find the point in v+span(W) that has the minimum maximum norm
    # ie. find min t s.t. -Wx-t <= v and Wx-t <= -v

    # Formulate the problem as a linear program
    from scipy.optimize import linprog
    c = np.zeros(dim_subspace + 1)
    c[0] = 1
    A_ub_withoutone = np.concatenate( (-W, W), axis=0)
    A_ub = np.concatenate( (-np.ones((2*dim_space, 1)), A_ub_withoutone), axis=1)
    b_ub = np.concatenate((v, -v), axis=0)

    res = linprog(c, A_ub=A_ub, b_ub=b_ub,  bounds=None)


    # hand calculation
    k = np.linalg.norm(v)**2 / np.linalg.norm(v, ord=1)
    hand_vec = k * np.sign(v)

    # I can even explicitely construct the feasable x tilde : 
    hand_x = np.linalg.lstsq(W, hand_vec-v, rcond=None)[0]
    hand_x_withone = np.concatenate((np.array([k+1e-8]), hand_x), axis=0)


    print ("We find that hand_x_withone is a feasable point : ", np.all(np.dot(A_ub, hand_x_withone) <= b_ub))
    print ("this point has cost ", np.dot(c, hand_x_withone))
    print ("this is bizarre, since we expected the cost to be no smaller than ", res.fun)

    return res.fun

 affine_max_norm_min(10,9)

Answer 1

我能够找到问题所在，并将问题留下以供将来参考。 我不知道为什么，但

linprog

似乎认为，即使我给出了

bounds=None

，我想要一个只有非负坐标的可行向量

x

。我通过更正为

bounds= (None, None)

解决了这个问题。