误解在于什么构成了“解决”优化问题，例如。对于数学家来说，只有在满足以下条件后，该问题才被视为“已解决”：$\arg\min f(x)$

1. 候选解决方案：决策变量及其对应的目标值的特定选择，并且$x^\star$$f(x^\star)$
2. 最优性证明：的选择是全局最优的数学证明，即的每个选择都成立。$x^\star$$f(x) \ge f(x^\star)$$x$

当是凸的时，两种成分都很容易获得。梯度下降找到一个候选解，它使梯度消失。最优性的证明来自 MATH101 中教导的一个简单事实，即如果是凸的，并且其梯度处消失，则是一个全局解。$f$$x^\star$$\nabla f(x^\star)=0$$f$$\nabla f$$x^\star$$x^\star$

当是非凸的时，候选解可能仍然很容易找到，但最优性的证明变得极其困难。例如，我们可以运行梯度下降并找到一个点。但是当是非凸的时，条件是必要的，但对于全局最优性不再是充分的。实际上，对于局部最优而言，它甚至还不够，即我们甚至不能仅根据其梯度信息来保证一种方法是枚举所有满足的点，这可能是一项艰巨的任务，即使只在一维或二维上。$f$$\nabla f(x^\star)=0$$f$$\nabla f(x)=0$$x^\star$$\nabla f(x)=0$

当数学家说大多数问题无法解决时，他们实际上是在说（甚至局部）最优性的证明是不可能构造的。但在现实世界中，我们通常只对计算“足够好”的解决方案感兴趣，而这可以通过无数种方式找到。对于许多高度非凸的问题，我们的直觉告诉我们，“足够好”的解决方案实际上是全局最优的，即使我们完全无法证明它！

一个棘手的低维问题的例子可能是：

鉴于您达到了局部最小值，您如何确定它与全局最小值一样好？鉴于它是全局最优的，你怎么知道你的结果是否是一个唯一的最优解？您如何创建一个对所有山丘和山谷都具有鲁棒性的算法，使其不会卡在某个地方？

像这样的例子就是事情可能会变得困难。显然，并不是所有的问题都是这样的，但有些问题是这样的。更糟糕的是，在工业环境中，成本函数的计算可能很耗时，并且有一个像上面那样有问题的表面。

实际问题示例

我可以在工作中解决的一个例子是对导弹制导算法进行优化，该算法在许多发射条件下都很稳健。使用我们的集群，我可以在大约 10 分钟内针对单个条件获得所需的性能测量。现在要充分判断稳健性，我们至少需要一个条件样本来判断。所以假设我们运行六个条件，使这个成本函数的评估需要一个小时。

非线性导弹动力学、大气动力学、离散时间过程等导致对制导算法变化的非线性反应，使得优化难以解决。这个成本函数将是非凸的，这使得评估一个大问题非常耗时。像这样的一个例子是，我们会努力在给定的时间内尽力而为。

问题在于鞍点，在您链接的帖子中进行了讨论。从其中一篇链接文章的摘要中：

然而，由于在高维中存在复杂的鞍点结构，通常很难保证此类算法甚至收敛到局部最小值。许多函数具有退化的鞍点，因此一阶和二阶导数无法用局部最优来区分它们。在本文中，我们使用高阶导数来避开这些鞍点：我们设计了第一个保证收敛到三阶局部最优值的有效算法（而现有技术最多为二阶）。我们还表明，将其进一步扩展到寻找四阶局部最优值是 NP 困难的。

本质上，当查看一阶、二阶和三阶导数时，您可以拥有与局部最小值无法区分的鞍点的函数。您可以通过使用更高阶的优化器来解决这个问题，但他们表明找到 4 阶局部最小值是 NP 困难的。

我建议阅读这篇文章，因为它们还展示了此类功能的几个示例。例如，函数在 (0,0) 处有一个点。$x^2y+y^2$

您可以使用许多启发式方法来逃避这些点，这可能适用于许多（大多数？）现实世界的例子，但不能被证明总是有效的。
在您链接的博客文章中，他们还讨论了您可以在多项式时间内逃避此类鞍点的条件。

除了已经给出的答案之外，另一个问题是没有凸性，Hessian 不能保证是正定的。这使任何使用二次模型的方法（例如牛顿法或拟牛顿法）变得复杂，因为二次模型没有确定适当搜索方向和步长的最小值。（有一些变通方法，例如参见BFGS 算法。）