查找满足条件的矩阵

Question

我想在 MATLAB 中解决以下问题，但不知道该使用哪个命令。

Find a matrix B, s.t. A * B = I and 0 <= B*a <= b

其中 A 和 B 是矩阵，a 和 b 是向量。 I 是单位矩阵。

知道要用什么吗？ fsolve 没有用，我不知道如何在 linprog 中表达这个。

示例：

A = [1 0 -1; 0 1 1];
a = [8; 6];
b = [15; 10; 10];

使用cvx的解决方案：

cvx_begin
variable B(3,2)
min (B)
subject to
    A*B == diag(ones(2,1));
    0 <= B*a;
    b >= B*a;
cvx_end

Answer 1

以下是您可能会遇到的两种不同情况：

有了你的等式约束

A*B=I

我认为您已经能够使用 Moore-Penrose inverse 矩阵求解 B，即 pinv（在 MATLAB 中）或 ginv（在 R 中）：

B = pinv(A);

或

B <- ginv(A)

由于Moore-Penrose逆的唯一性，需要对条件

的求解B进行验证

0 <= B*a <= b

如果使用上述方法违反了不等式约束，则可以尝试以下方法（在 MATLAB 中加载 CVX 或在 R 中加载 CVXR）：

不幸的是，我的电脑上没有 MATLAB，但我尝试 CVXR 使用 R 语言，效果很好。也许您需要对 MATLAB 版本进行较小的语法调整或翻译。

下面是一个例子，向您展示如何制定问题：

# given matrices
A <- matrix(c(1,0,-1,0,1,1),nrow = 2,byrow = TRUE)
a <- matrix(c(8,6))
b <- matrix(c(15,10,10))

# formulate optimization problem and solve it
library(CVXR)
B <- Variable(3,2)
obj <- Minimize(norm(A%*%B - diag(c(1,1)),"2"))
cons <- list(B%*%a >= 0, b>=B%*%a )
problem <- Problem(obj,cons)
res <- solve(problem)

这样

> res$getValue(B)
            [,1]      [,2]
[1,]  0.90183254 0.6467117
[2,]  0.09816746 0.3532883
[3,] -0.09816746 0.6467117

Answer 2

为了用 linprog 解决这些问题，你必须列出：

平等
不平等

所以我们有六个未知数：

B = [x1 x2
     x3 x4
     x5 x6]

不等式为：

和

linprog (A*x <= b) 支持的格式给我们：

A = [8  6  0  0  0  0
     0  0  8  6  0  0
     8  6  0  0  8  6
    -8 -6  0  0  0  0
     0  0 -8 -6  0  0
     0  0  0  0 -8 -6];

b = [15 10 10 0 0 0]

注意到为了变换 <=0 中的 >=0 两边都乘以 -1。

等式为：

在 linprog (Aeq*x == beq) 支持的格式中，我们得到：

Aeq = [1  0  0  0 -1  0
       0  1  0  0  0 -1
       0  0  1  0  1  0
       0  0  0  1  0  1]

beq = [1 0 0 1]

我们可以认为所有变量都有相同的"weight"，我们的objective函数可以定义为f = [1 1 1 1 1 1]。但如果您更改这些权重，它也会起作用（并将提供另一种解决方案）。您可以将其视为 6D space 的形状，其中某些维度可以被压缩或拉伸（但不能弯曲）。例如 f = [1 0.25 1 1 -1 1/2] 也是一个选项...

f = [1 1 1 1 1 1] %which correspond to [x1 x2 x3 x4 x5 x6]

s = linprog(f, A,b,Aeq,beq,-10,10) %solve the problem with arbitrary lower and upper boundary.

一个可能的结果：

其中给出：

B = [10 -12
     9   13
     9   -12]

更大问题的自动化：

% B Matrix size
s1 = 3;
s2 = 2;

% Variable
A  = [1 0 -1; 0 1 1];
B  = sym('X', [s1 s2])
ax = [8; 6];
bx = [15; 10; 10];

% Convert linear equations to matrix form
[Aeq,beq] = equationsToMatrix(A*B == eye(s2))
[A1,b1]   = equationsToMatrix(B*ax == bx)
[A2,b2]   = equationsToMatrix(-B*ax == 0)

% Solve the problem
%      (      f      ,          A            ,            b           ,       Aeq  ,      beq  ,  lb,ub)
linprog(ones(s1*s2,1),[double(A1);double(A2)], [double(b1);double(b2)], double(Aeq),double(beq), -10,10)

查找满足条件的矩阵

Find matrix satisfying conditions

matlab

matrix

linear-programming