如何可视化Primal-Dual Hill爬坡？

Question

在Jeff Edmonds的文章“如何思考算法”中，有一节解释了网络流程和线性规划章节中的原始 - 双重爬山。我很难想象指数数量的屋顶以及为什么“最低和因此最优化的屋顶高于最高，因此最适合站立”

Answer 1

我不是100％确定这是对的，但这是我的：给定一个特定的丘陵拓扑结构，你可以想象它的镜像漂浮在你上方的天空中。最高的山顶将达到并接触镜子底部最底部的谷底，谷底从天空向下延伸。相反，如果您向下导航到最低的山谷，您将在镜像中最大化您与正上方的点之间的距离。这本书没有很好地解释，但是这个镜像就是书中提到的“指数屋顶”。

无论如何，这个镜像被用作证明你已达到全局最大值的基础。直观的证据是说，首先，镜像是原始问题的另一个实例，恰恰相反。但是，天空中镜像的存在让您能够区分局部或全局最大值。如果你已经达到了一个特定的高峰，但你的头并没有撞上它在天空中的“镜峰”，那么你已经达到了当地的最大值。另一方面，如果没有足够的空间让你站立起来，因为峰顶与镜像相撞，那么你知道你已经达到了全球最大值。

回到书中原来的描述，我认为它的问题很大，因为作者所描述的“指数屋顶”就像是一系列有着一堆凉亭的山丘，听起来并不对。一个更好的描述将是一个石笋和钟乳石的洞穴相互镜像。