PROTES: Probabilistic Optimization with Tensor Sampling

2023/01/28 by Anastasia Batsheva, Batsheva, Anastasia, Andrei Chertkov +5 · 6 citations
Computer Science · Engineering · Mathematics · #Computational Physics and Python Applications #Energy Load and Power Forecasting #FOS: Mathematics #Numerical Analysis (math.NA) #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.2301.12162

openalex publication_date 2023/01/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 low-parametric 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¹⁰⁰. 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).

Cited by

• Variational matrix product states for combinatorial optimization
• CrystalFormer-CSP: Thinking Fast and Slow for Crystal Structure Prediction
• Speeding up the Goemans-Williamson randomized procedure by difference-of-convex optimization
• A Novel Block-Alternating Iterative Algorithm for Retrieving Top-k Elements from Factorized Tensors
• High-dimensional Optimization with Low Rank Tensor Sampling and Local Search
• A tensor-train multidimensional inverse Laplace transform

Related

• ProGO: Probabilistic Global Optimizer
• TTOpt: A Maximum Volume Quantized Tensor Train-based Optimization and its Application to Reinforcement Learning
• Parametric Learning and Monte Carlo Optimization
• Inexact Tensor Methods and Their Application to Stochastic Convex Optimization
• Optimization of Functions Given in the Tensor Train Format