电气栅栏的局部最优解

Question

我正在为Usaco问题“电气围栏”写一个解决方案。在这个问题中，你必须在大量的直线中找到一个点的最优位置，所以点-线距离之和是最小的。

我有一个想法，这可能是可能的爬山，它适用于所有的测试案例。给出的分析使用了类似的方法，但它没有解释为什么会这样做。

因此，我仍然无法证明或否定给定任务中局部最优的存在。我有一个想法，它可以通过归纳完成，但我一直未能使它发挥作用。你能帮帮我吗?

更新定义

给定一组(x1，y1，x2，y2)行，可以找到(x，y)点P，从而使函数最小化：

def Val(x,y):
    d = 0
    for x1,y1,x2,y2 in LineSegments:
        if triangle (x1,y1,x2,y2,x,y) is not obtuse in (x1,y1) or (x2,y2):
            d += DistPointToLine(x,y,x1,y1,x2,y2)
        else:
            d += min(DistPointToPoint(x,y,x1,y1), DistPointToPoint(x,y,x2,y2))
    return d

由于某些原因，这个问题只包含一个局部最优，因此可以使用以下过程来解决它：

precision = ((-0.1,0), (0.1,0), (0,-0.1), (0,0.1))
def Solve(precision=0.1):
    x = 0; y = 0
    best = Val(x,y)
    while True:
        for dx,dy in precision:
            if Val(x+dx, y+dy) > best:
                x += dx; y += dy
                best = Val(x,y)
                break
        else:
            break
    return (x,y)

问题是:为什么在走向全球最佳状态的过程中，这个问题不被困在某个地方？为什么没有地方山顶来使这个天真的程序屈服呢？

Answer 1

当我们注意到单个线段的距离函数是凸函数时，很容易证明该算法的正确性。凸在这种情况下意味着，如果我们把距离函数看作一个曲面z=f(x，y)，那么如果我们在曲面上填充体积，我们就会有一个凸体。在距离单线段的情况下，实体看起来就像一个三角形楔形，两端是圆锥形的。

既然是凸函数的和也是凸的，那么距离多个线段的距离之和也将是一个凸函数。因此，由于函数是凸的，你找到的任何局部极小值也必须是全局极小值。