无矩阵方法可以很好地解决具有数千个变量的问题。具体来说，正确实现的 Newton-CG 或信任区域代码不需要形成密集 Hessian 来计算 Newton 迭代，而只需要 Hessian 对向量的作用。这些方法依赖于截断的 Krylov 求解器，例如截断的 CG 或截断的 MINRES，以部分求解线性系统。根据我的经验，使用截断 CG 的无矩阵、信任区域算法效果最好。它往往比 Newton-CG（一种线搜索方法）工作得更好，因为信任区域有助于确定每次迭代需要多少 Krylov 迭代。在 Newton-CG 中，您必须先验地猜测并设置这个数字。有关 Newton-CG 的简短描述，请参阅 Nocedal 和 Wright 的书数值优化（第 169 页）。该书还包含对信任区域算法的描述（第 69 页）。将其与 truncated-CG 一起使用，在第 171 页进行了描述。此外，蓝色的大信任区域方法书拥有最完整的信任域算法的描述。那本书有点压倒性。从第 116 页的基本信任区域算法开始。在第 2 步中，使用第 202 页中描述的截断 CG。

现在，这些方法并不完美。一般来说，由于各种原因，您将获得比一阶方法更好的性能，但只有在接近实际解并且我们足够准确地求解牛顿系统时才能保证高阶收敛速度。如果我们使用截断的 Krylov 求解器，例如截断的 CG，这是由 Hessian 的特征值的聚类决定的，我们可能无法计算。但是，就像我上面所说的，总的来说它运作良好。坦率地说，我从未见过准牛顿方法比良好的无矩阵优化算法效果更好的情况。我敢肯定它会发生，但不是那么频繁。

最后，就热启动而言，如果问题中存在不等式约束，那么热启动的唯一真正问题就会发挥作用。在无约束优化中，我不知道有任何算法存在热启动问题。但是，如果您实际上从最佳解决方案开始，则会出现一些数字难题。在任何情况下，像原始对偶内点法这样的不等式约束算法在热启动时都会遇到问题。然而，其他不等式约束算法，例如Coleman-Li 反射牛顿算法对此有零问题。如果您接近解决方案，只需忽略代码的反射位，它就可以很好地工作。需要注意的是，良好的等式约束算法在热启动方面也没有问题。这些是诸如顺序二次规划（SQP）或更好的复合步骤SQP方法之类的东西。

最后，所有这些算法都已经在Optizelle中实现并免费提供。它是 BSD 许可的，并且有 C++、Python 和 MATLAB 的钩子。如果你想要一个有限记忆的准牛顿法，它也有BFGS和SR1。当然，您可以自己实现这些算法。而且，老实说，无约束优化的代码并没有那么糟糕。然而，Optizelle 已经做到了，并且已经被用于处理超过 50 亿个变量的问题。

一般来说，对于可能有 100 个变量的东西，我可能会尝试顺序二次规划。对于非常大的问题，内点法会更好。使用 L-BFGS 近似；在实践中，通常没问题。

大多数受约束的非线性规划求解器将基于稀疏直接线性代数；预处理 KKT 系统的理论处于研究的前沿，因此预处理迭代内点法的实现即将出现。

如果您的问题是框约束或无约束的，并且您的问题是凸的，那么 CG 也是可行的，并且任何类牛顿方法（L-BFGS 等）或非线性迭代方法（如 NCG、NGMRES 等）都应该工作; 将其与全球化策略（线搜索或信任区域）一起使用以获得更好的结果。

你的 Hessian 稀疏吗？如果是这样，我在下面写的内容并不适用。

数万个变量中的一般函数的 Hessian 至少会有数亿个条目。也就是说，它将占用超过 1 GB 的 RAM。评估它会很糟糕，然后你必须用它做线性代数。不用了，谢谢！

您可以在此处尝试使用非线性共轭梯度或有限内存的 BFGS 变体，如 L-BFGS。直接 BFGS 也可能太贵了，因为它会存储一个近似的 Hessian 逆，这是一个千兆字节。

根据您的问题详细信息，您可以使用Levenberg-Marquardt风格的算法。如果它不适合转化为这种问题，那么我会坚持使用 CG，如果你能找到的话，可能会使用某种预处理器。我已经在数十万维的情况下成功地使用了这两种方法。