寻找欠定线性方程组的正解 [英] Find positive solutions to underdetermined linear system of equations

问题描述

我对Matlab有点陌生，如果这太简单了，抱歉.

I'm a bit new to matlab so sorry if this is horribly simple.

考虑以下问题:

找到x_1, x_2, x_3 > 0使得

67.5 = 60*x_1 +  90*x_2 + 120*x_3 and
60   = 30*x_1 + 120*x_2 +  90*x_3

在这种情况下，我需要解决方案

In this case I want the solution

0 < x_3 < 3/7,
x_2 = 7/20 - 4/10*x_3, and
x_1 = 2/5  -  7/5*x_3

有没有一种简便的方法可以使Matlab为我解决这样的问题?

Is there a easy way to make Matlab solve such a problem for me?

推荐答案

简单的答案是使用lsqnonneg，因为您只需要对参数进行非负约束即可.对于该问题根本不需要lsqlin，并且由于lsqnonneg是MATLAB的一部分，因此不需要优化TB.

The easy answer, since you just need non-negativity constraints on the parameters, is to use lsqnonneg. lsqlin is not needed at all for this problem and since lsqnonneg is part of MATLAB, the optimization TB is not needed.

A = [60 90 120; 30 120 90];
b = [67.5; 60];

x = lsqnonneg(A,b)
x =
                         0
         0.178571428571428
         0.428571428571429

我们可以测试结果以查看它是否解决了原始问题.

We can test the result to see if it solved the original problem.

A*x - b
ans =
     0
     0

您当然可以使用lsqlin，但是为什么要打扰呢?

Of course you COULD have used lsqlin, but why bother?

实际上，由于欠定的系统有许多解决方案，因此我们必须考虑一个问题.我们可以将任意数量的数组A的空空间添加到我们的解决方案中.在这种情况下，零空间的等级为1.这里的向量N表征了它:

In fact, there is an issue we must consider since an underdetermined system has infinitely many solutions. We can add any amount of the null-space of the array A to our solution. In this case that null-space has rank 1. It is characterized by the vector N here:

N = null(A)
N =
        -0.792593923901216
         -0.22645540682892
         0.566138517072299

一种简单的理解方法是识别A的零空间的含义. N是一个向量(或在零空间的维数大于1的情况下跨越子空间的一组基础向量)，使得

An easy way to understand it is to recognize what the nullspace of A means. N is a vector (or a set of basis vectors that span a subspace in case the null-space has dimension higher than 1) such that

A*N = 0

从本质上讲，N是一个与A的所有行正交的向量.如果零空间的维数大于1，则N可以是零空间的基向量的任何线性组合.因此，如果X是欠定系统的ANY解决方案

Essentially, N is a vector that is orthogonal to all of the rows of A. If the null-space has dimension higher than 1, then N can be any linear combination of basis vectors of the null-space. Therefore, if X is ANY solution of the under-detemined system

A*x = b

那么对于任意常数c，x + c * N也是解. (请记住，A * N将为零.)

then it must be true that x+c*N is also a solution, for any arbitrary constant c. (Remember that A*N will be zero.)

例如，我将为N选择一个任意系数:

So for example, I'll pick an arbitrary coefficient for N:

x2 = x + N*(-.1)
x2 =
        0.0792593923901216
          0.20121696925432
         0.371957576864199

同样，x2也是一种解决方案.它也完全具有正系数. (您可以轻易地找到N上系数的值范围，使得解完全为正.)

Again, x2 is also a solution. It too has entirely positive coefficients. (You can trivially find that range of values for the coefficient on N such that the solution is entirely positive.)

A*x2 - b
ans =
      -1.4210854715202e-14
       -7.105427357601e-15

(请注意，在浮点算术中找到的双精度垃圾中，这些实际上是零.)

(Note that these are effectively zeros, to within the double precision trash found in floating point arithmetic.)

因此，如果我们要这样做，从lsqnonneg或反斜杠或pinv解决方案开始就很容易，并找到系统的整套解决方案，以使系数完全为正.提示:您需要做的就是考虑向量x和N，然后寻找问题的解决方案

So, IF we wanted to do so, it is easy enough to start with the lsqnonneg or backslash or pinv solution, and find the complete set of solutions to your system such that the coefficients are entirely positive. Hint: all you need do is consider the vectors x and N, then look for solutions to the problem

(x + c*N) > 0

其中c是某个标量常数.显然，C不能为正，否则总和的第一个元素将为负.

where c is some scalar constant. Clearly, C cannot be positive, else the first element of the sum will be negative.

C = -x./N
C =
            0
      0.78855
     -0.75701

x + C(1)*N
ans =
            0
      0.17857
      0.42857

x + C(3)*N
ans =
          0.6
         0.35
            0

我们可以看到，当c为闭区间[-.75701,0]中的任何值时，我们将以(x + c * N)的形式获得该问题的完全正解.但是，如果超出这些限制，则解决方案中的一个或多个元素将为负.

As we can see, when c is any value in the closed interval [-.75701,0], we get an entirely positive solution to the problem, in the form of (x+c*N). Go any further than those limits though, and one or more of the elements in the solution will be negative.

在某些问题上，根本没有解决方案可以得出具有解矢量所有正元素的精确解.这完全有可能.例如，假设我们将原始问题更改为:

On some problems there will be no solution at all that yields an exact solution with all positive elements of the solution vector. This is entirely possible. For example, suppose we changed the original problem into:

A = [60 90 120; 30 120 90];
b = [-67.5; -60];

现在，当我们使用lsqnonneg时会发生什么?

Now what happens when we apply lsqnonneg?

lsqnonneg(A,b)
ans =
     0
     0
     0

结果为全零.由于该解决方案显然不能完全解决原始问题，因此必须存在这样的肯定解决方案.

An all-zero solution results. Since that solution clearly can not exactly solve the original problem, it must be true that no such positive solution exists.

这篇关于寻找欠定线性方程组的正解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！