High-dimensional Optimization with Low Rank Tensor Sampling and Local Search
Konstantin Sozykin, Andrei Chertkov, Anh-Huy Phan, Ivan Oseledets, Gleb Ryzhakov
我们提出了一种名为TESALOCS(Ttensor Sampling和LOCal Search)的新方法,用于多维优化,结合了无梯度离散方法和基于梯度的方法的优势。 我们方法中的离散优化基于低等级张量技术,由于其低参数表示,可以有效地优化高维问题。 对于第二部分,即本地搜索,可以使用任何有效的基于梯度的方法,无论是现有的(如准牛顿方法)还是将来开发的任何其他方法。 我们的方法解决了基于梯度的方法的局限性,例如被困在局部最优法中;离散方法的局限性,不能直接应用于连续函数;以及需要大量计算预算的无梯度方法的限制。 请注意,我们不仅限于用于离散优化的单一类型的低等级张量分解,但出于说明目的,我们考虑特定的高效低等级张量列车分解。 对于20个具有挑战性的100维函数,我们证明我们的方法可以显著优于使用基于梯度的方法获得的结果,如Conjugate Gradient,BFGS,SLSQP和其他方法,以相同的计算预算按数量级改进它们。
We present a novel method called TESALOCS (TEnsor SAmpling and LOCal Search) for multidimensional optimization, combining the strengths of gradient-free discrete methods and gradient-based approaches. The discrete optimization in our method is based on low-rank tensor techniques, which, thanks to their low-parameter representation, enable efficient optimization of high-dimensional problems. For the second part, i.e., local search, any effective gradient-based method can be used, whether existing...