用 cvx 解决秩亏系统

计算科学 线性规划 简历
2021-12-17 09:30:23

我正在使用 cvx 来求解具有形式的约束的线性程序。然而,矩阵秩不足并且 cvx 返回警告并最终将状态显示为“不可行”。排名不足的系统可以有一个解决方案,我的猜测是我的系统确实有一个解决方案。有没有办法让 cvx 在不使矩阵满秩的情况下解决这个系统?Ax=b,x0A

3个回答

众所周知,CVX 本身以及它使用的求解器在一定程度上存在方程矩阵中的秩不足问题。(因此发出警告。)但是您对在这里进行某种 LU 分解有什么反感呢?另外,您是否尝试了所有求解器,还是只尝试了一个?

另一种方法是求解一个保证可行的模型。例如:

cvx_begin
    variables x(n)
    minimize(norm(A*x-b))
    x >= 0
cvx_end

如果您的原始问题是可行的,那么这应该具有接近零的最佳值(在舍入误差内)。如果它具有不可忽略的正最优值,那么您的原始模型是不可行的。

根据您拥有的特定向量,可能是方程组不可行,或者存在的解但没有的解。与 CVX 一起使用的求解器完全能够检测任何一种类型的 LP 不可行,因此很可能您的猜测是错误的并且 LP 实际上是不可行的。 bAx=bx0

请注意,即使具有完整的行秩并且方程组是可行的,这并不意味着包含约束的 LP必须有解。AAx=bx0

扩展布赖恩的回答:您可能会认为,如果矩阵秩不足,则需要的解,因为存在解满足等式并且肯定该仿射空间的部分在所有分量中必须是非负的。AAx=bx0x=x0+y,ykerA

但这不一定是真的。想象一下,例如例如,这将对应于 尽管x0=(0,1)T,kerA={yR2:y=(y1,0)T}

A=(0100),b=(10).
A秩不足,线性系统也没有非负解。