PROTES: Probabilistic Optimization with Tensor Sampling

We developed a new method PROTES for black-box optimization, which is based on the probabilistic sampling from a probability density function given in the lowparametric tensor train format. We tested it on complex multidimensional arrays and discretized multivariable functions taken, among others, from real-world applications, including unconstrained binary optimization and optimal control problems, for which the possible number of elements is up to 2 100 . In numerical experiments, both on analytic model functions and on complex problems, PROTES outperforms existing popular discrete optimization methods (Particle Swarm Optimization, Covariance Matrix Adaptation, Differential Evolution, and others). * Equal contribution. 1 A tensor is just a multidimensional array with several dimensions d (d ≥ 1). A two-dimensional tensor (d = 2) is a matrix, and when d = 1 it is a vector. For scalars we use normal font (a, b, c, . . .), we denote vectors with bold letters (a, b, c, . . .), we use upper case letters (A, B, C, . . .) for matrices, and calligraphic upper case letters (A, B, C, . . .) for tensors with d > 2. The (n1, n2, . . . , n d )th entry of a d-dimensional tensor Y ∈ R N 1 ×N 2 ×...×N d is denoted by y = Y[n1, n2, . . . , n d ], where ni = 1, 2, . . . , Ni (i = 1, 2, . . . , d), and Ni is a size of the i-th mode. The mode-i slice of such tensor is denoted by Y[n1, . . . , ni-1, :, ni+1, . . . , n d ].