Дослідження залежності тривалості оптимізації від розмірності задачі
Анотація
Вимірність оптимізаційної задачі суттєво впливає на часову складність та тривалість обчислень алгоритмів оптимізації. Цей взаємозв'язок, відомий як прокляття розмірності, є невід'ємним аспектом оптимізації. Оптимізація є важливим аспектом багатьох наукових і технологічних галузей, включаючи машинне навчання, дослідження операцій та економіку. Ці проблеми часто пов'язані з набором змінних і обмежень, з метою знайти найкраще рішення. Одним з основних факторів, що впливають на час обчислень або тривалість оптимізації, є розмірність задачі, тобто кількість змінних, що беруть участь у процесі оптимізації. Цей зв'язок між розмірністю та часом обчислень часто називають "прокляттям розмірності" - поняття, введене Річардом Беллманом у 1957 році.
Посилання
Bellman, R. (1957). Dynamic Programming. Princeton University Press.
Wolpert, D. H., & Macready, W. G. (1997). No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation.
Duda, R. O., Hart, P. E., & Stork, D. G. (2001). Pattern Classification (2nd ed.). Wiley
