Аффинное масштабирование
-
История и открытие аффинного масштабирования
- Аффинное масштабирование — это метод решения задач линейного программирования, открытый И. Я. Дикиным в 1967 году.
- Метод был заново изобретен в США в середине 1980-х годов и стал известен благодаря алгоритму Кармаркара.
- Аффинное масштабирование было переосмыслено как вариант алгоритма Кармаркара после его открытия.
-
Алгоритм аффинного масштабирования
- Аффинное масштабирование состоит из двух этапов: определение допустимой точки для начала оптимизации и выполнение оптимизации в пределах допустимой области.
- Итерационный метод, лежащий в основе алгоритма, использует градиентный спуск для решения задач линейного программирования.
-
Анализ сходимости аффинного масштабирования
- Сходимость аффинного масштабирования зависит от размера шага β, и для некоторых значений β алгоритм может сходиться к неоптимальному решению.
- Существуют примеры задач, для которых алгоритм Вандербея сходится, в то время как другие варианты демонстрируют хаотическое поведение.
-
Рекомендации и дальнейшее чтение
- В статье приведены ссылки на дальнейшее чтение и внешние ссылки для углубленного изучения темы.
Полный текст статьи: