Программа курса
Методы нелинейного программирования и особенности их численной реализации
Нелинейное программирование (НП) – поиск локального минимума целевой функции в условиях ограничений. Локальный и глобальный минимумы. Типичная задача НП – интерпретация физических экспериментов. Метод наименьших квадратов и метод максимального правдоподобия. Прямая и обратная задачи. Штрафные функции. НП как часть Общего Алгоритма Всего. Гладкость целевых функций. Модельные целевые функции.
Задание 1: Написать процедуры для расчета модельных и других интересных целевых функций.
Методы НП, не требующие расчета градиента. Метод сопряженных направлений. Методы одномерного поиска минимума. Метод золотого сечения.Задание 2: Написать программу метода сопряженных направлений или адаптировать программу, предложенную лектором, для среды своего компа. Исследовать работу метода на модельных целевых функциях.
Понятие о числовой ошибке и числовом шуме. Методы одномерного поиска минимума гладких функций. Равенство числовой ошибки и ошибки аппроксимации как критерий окончания поиска минимума. Параметры алгоритма метода сопряженных направлений и их оптимальный выбор для конкретной целевой функции.Задание 3: Написать процедуру исследования числового шума или адаптировать процедуру, предложенную преподавателем. Исследовать числовой шум расчета модельных целевых функций.
Задание 4: Написать или адаптировать процедуры одномерного поиска минимума гладких функций. Вставить их в программу метода сопряженных направлений.
Задание 5: Определить оптимальные параметры метода сопряженных направлений для нескольких модельных целевых функций.
Модифицированный метод сопряженных направлений. Матрица Гесса. Собственные значения и собственные вектора матрицы Гесса. Переход к системе координат, связанной с собственными векторами матрицы Гесса.Задание 6: Написать или адаптировать программу модифицированного метода сопряженных направлений.
Задание 7: Сравнить эффективность простого и модифицированного метода сопряженных направлений на множестве модельных целевых функций. (Эффективность обратно пропорциональна времени, затраченного на поиск минимума.). Оценить устойчивость алгоритмов для разного числа переменных. (Устойчивость обратно пропорциональна ошибке определения координат минимума).
Методы НП с вычислением градиента целевой функции. Метод сопряженных градиентов. Методы одномерного поиска минимума как корня производной по направлению. Определение числового шума вычисления градиента. Критерий окончания поиска минимума – производная вдоль направления порядка числового шума. Параметры алгоритма и их оптимизация. Тестирование программ градиентных методов минимизации.Задание 7: Написать процедуры вычисления градиентов модельных целевых функций.
Задание 8: Написать процедуру исследования числового шума расчета градиентов.
Задание 9: Написать или адаптировать программу метода сопряженных градиентов. Протестировать программу на модельных целевых функциях. Определить оптимальные параметры алгоритма.
Устойчивость метода сопряженных градиентов. Алгоритм метода сопряженных градиентов, устойчивый при большом числе переменных. Метод сопряженных градиентов с ограничениями вида
. Методы минимизации с произвольными линейными ограничениями. Линейное программирование. Алгоритм Давидона-Флетчера-Пауэла. Поиск глобального минимума. Метод Монте-Карло со сжатием границ генерации. Целевые функции для расчета оптических схем. Целевые функции для расчета параметров статистических рядов. Примеры применения Общего Алгоритма Всего. 