Дослідження залежності тривалості оптимізації від розмірності задачі

Abstract

Вимірність оптимізаційної задачі суттєво впливає на часову складність та тривалість обчислень алгоритмів оптимізації. Цей взаємозв'язок, відомий як прокляття розмірності, є невід'ємним аспектом оптимізації. Оптимізація є важливим аспектом багатьох наукових і технологічних галузей, включаючи машинне навчання, дослідження операцій та економіку. Ці проблеми часто пов'язані з набором змінних і обмежень, з метою знайти найкраще рішення. Одним з основних факторів, що впливають на час обчислень або тривалість оптимізації, є розмірність задачі, тобто кількість змінних, що беруть участь у процесі оптимізації. Цей зв'язок між розмірністю та часом обчислень часто називають "прокляттям розмірності" - поняття, введене Річардом Беллманом у 1957 році.