使用LP查找分数

Question

我有两个多边形，BP和GP，用不等式约束集描述，黑色多边形的-x+y<=1 and x+y<= 5 and x-y<=3 and -y <= 0和绿色多边形的-1<=x<=4 and 0 <= y <= 3。

​

​

我在这里的目标是使用LP来找到一个分数问题的最优解:如果B在GP中，那么最大值lambda是什么？

B= lambda*B_BP + (1-lambda)*B_GP

换句话说，我想在上面的多边形中找到B的最大部分。为此，我正在努力编写一个LP程序，我认为，如果我们把BP写成矩阵不等式的条件，我们得到每个B_BP都是这样的，M_BP*B_BP <= C是C，向量是(1,5,3,0)，M_BP是矩阵((-1,1),(1,1),(1,-1),(0,-1))。所以我认为应该是这样的，假设B= x_1+x_2

最大朗达 服从M_BP*L_BP <= C_B 和B_BP >= 0

我认为(这是我的所有尝试，可能都是非常错误的)，L_BP = (x,y)向量和lambda = (x+y)/normalization，以及C_B与向量B有某种联系。

抱歉，如果我的第一个问题太乱，我就从这里开始。

Answer 1

如果我正确地理解了你的问题，我认为在数学意义上解决这个问题是可能的。让我解释一下。由于目标函数在lambda中是线性的(正如Superkogito所指出的)，因此在角点之一总是达到最大值(或最小值)。通过使用这个，您可以计算lambda。

让我先举几个简单的例子。对于黑色多边形中的任意一点，很明显，lambda为1:您只需将B= B_BP。现在让我们取B= (-1，3)。如果你取B_BP = ( -1，0)以外的任何黑点，并且lambda > 0，那么对于方格内的任何绿色点，x-坐标将大于-1。所以你能做的最好是把B_BP = (-1，0)。那么绿点应该是B_GP = (-1，3)，因此lambda = 0。

按照相同的逻辑，您可以看到，在端点(-1，0)和(-1，3)定义的边缘上，您总是使用B_BP = (-1，0)和B_GP = (-1，3)。沿着这个边缘，λ将从1减少到0。在(-1，1) lambda = 2/3，in (-1，2) lambda = 1/3。(-1，3)与(2，3)之间的上边缘相同: In (0，3) lambda = 1/3等等。对于带角(4，3)的绿色三角形，必须使用(4，3)作为端点。然后在(3，3)中，例如lambda = 1/2。

有趣的问题显然是在三角形的内部部分。这里，B_GP也是其中的一个角，而B_BP在三角形的一侧的黑线上。您可以假设有另一种解决方案而不是这种情况，然后通过将B_GP或B_BP向左或向右移动来证明增加lambda是可能的。我想，一个完整的数学证明对这里来说太长了。现在让我们取左边的三角形，绿色的角(-1，3)和(-1，0)和(2，3)之间的黑边。对于最大λ，B_GP = (-1，3)，B_BP在黑边。因为B= lambda * B_BP +(1-lambda)* B_GP，这给出了两个方程。因为B_BP在y=x+ 1的直线上，所以给出了第三个方程。由此，您可以求解B_BP和lambda的x-和y-坐标(给定B点)。

我已经这样做了，到达lambda = (By + 4) / 3。B_BP的坐标是B_BPx = (Bx +1+ lambda) / lambda和B_BPy =( By -3+3* lambda) / lambda (只需填写lambda)。例如，对于点(0，2)，你会得到lambda = 2/3，你可以对另外两个三角形做同样的事情，我也这样做了。

我将总结如下：

左三角形: lambda = (Bx - By + 4) /3

右上三角形: lambda = (-By - Bx + 7) /2

右下角三角形: lambda = By - Bx +4

编程，现在这是微不足道的。如果你想要，我可以给你对应的B_BP的其他两个三角形的坐标，请告诉我。顺便说一句，你可以通过画一条直线穿过三角形和B的拐角处来到达它们。

当然，这只在目标函数是线性的情况下才能工作。在其他情况下，您必须使用Superkogito建议的方法。我希望我已经正确理解了你的问题，如果没有，请原谅我！至少我觉得这是一个很好的数学挑战。

Answer 2

在我看来，这个问题需要更好的表述。我不确定这是否解决了你的问题，但希望它能有所帮助。因此，我建议使用scipy.optimize.minimize来解决这个优化问题，仅仅通过反转符号或使用逆，您就可以将最大化转化为最小化。

此外，由于您的代码是基于随机点从BP，GP和随机点B，您应该把这些也提供到您的输入向量。从输入向量中可以计算lambda系数(我在代码中将这个变量命名为k)。这种方法将返回满足约束条件的输入向量的值，目标函数fun的最小输出也就是最大的kx和最大的ky。

前面所解释的办法可以实施如下：

import numpy as np
import scipy.optimize


# compute k
def k(x):
    x_bp, y_bp = x[0], x[1]
    x_gp, y_gp = x[2], x[3]
    bx  , by   = x[4], x[5]

    # compute k
    kx = (bx - x_gp) / (x_bp - x_gp)
    ky = (by - y_gp) / (y_bp - y_gp)
    return kx, ky


# define objctive/cost function
def fun(x):
    kx, ky = k(x)
    return 1 / kx + 1 / ky

# define constraints (bp raandom point constraints)
cons = ({'type': 'ineq', 'fun': lambda x:  x[0] + x[1] - 5},
        {'type': 'ineq', 'fun': lambda x: -x[0] - x[1] - 3})

# init bounds 
bnds = ((None, None), (0, None), 
        (-1., 4.), (0., 3.), 
        (-1., 4.), (0., 3.))

# init vars vec
#x = [x_bp, y_bp, x_gp, y_gp, bx,   by]
x0 = [ 0.1,  0.2,  0.3,  0.5, 0.6, 0.5]

# optimize 
res = scipy.optimize.minimize(fun, 
                              x0, 
                              bounds=bnds, 
                              constraints=cons)

# print result
print("optimal x: ", np.round(res.x, 3))

# print optimal k 
print("optimal k: ", np.round(k(res.x), 3))

请注意，您可能需要稍微修改代码，并处理初始值x0和界限，但这应该会奏效。已发布的代码段将产生以下输出：

optimal x:  [0.1 0.2 0.3 0.5 0.6 0.5]
optimal k:  [-1.5 -0. ]