Міністерство освіти і науки України
Національний технічний університет
“ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”
Кафедра “Обчислювальної техніки та програмування”
Реферат з курсу “Введение в численные методы”
Тема: “ПОИСК ОПТИМАЛЬНЫХ РЕШЕНИЙ”
Виконав: студент групи
Перевірив:
Харків
Содержание
1. Основные понятия оптимизационных задач
2. Итерационные процессы с учетом градиента
3. Функционал для градиентного равенства
4. Функционалы в задачах условной оптимизации
Литература
1. Основные понятия оптимизационных задач
К задачам поиска нулей функций сводятся многие задачи нахождения наибольших или наименьших значений многомерных функций в заданной области. В литературе такого рода задачи называются задачами оптимизации. В этих задачах дополнительно оговариваются условия, при которых оптимум должен быть достигнут. В качестве условий могут выступать системы алгебраических уравнений, или системы неравенств, или и то и другое одновременно. Оптимизируемая функция при этом является, как правило, критериальной, т.е. описывающей показатель качества объекта.
Простым примером оптимизационной задачи может быть метод наименьших квадратов (МНК), где критерием качества аппроксимации служила сумма квадратов отклонений заданной системы точек от искомой аппроксимирующей кривой. Аналогичным образом построенные многопараметрические критериальные выражения в литературе называют функционалами, минимуму которых и необходимо удовлетворить соответствующим выбором параметров функционала.
Если функционал построен, включает в себя параметры и не содержит ограничений или условий на характер и диапазон изменения параметров, то система уравнений относительно неизвестных значений параметров получается приравниванием частных производных по всем параметрам нулю. В результате задача оказывается сведенной к решению линейной, как в МНК, или в общем случае нелинейной системы уравнений. Такие задачи называются задачами безусловной оптимизации.
2. Итерационные процессы с учетом градиента
Ограничения и условия в задачах оптимизации встраивают тем или иным образом в общий функционал, после чего решают задачу поиска экстремума. Наиболее популярной структурой функционала является взвешенная сумма квадратов невязок, полученных из условий и ограничений. Это обеспечивает всему функционалу квадратичную зависимость по каждому неизвестному параметру и, как следствие, локальный минимум всему функционалу.
Изменение искомых параметров можно подчинить какой-либо детерминированной динамической процедуре, обеспечивающей сходимость итерационного процесса движения к точке минимума. Наиболее распространенным, имеющем множество модификаций, процессом является метод градиента: вектор скорости изменения неизвестных параметров пропорционален с обратным знаком вектору градиента функционала:
Это условие соответствует выбору наибольшей скорости убывания функционала, что несложно увидеть, рассмотрев выражение для производной функционала по времени:
.
Правую часть можно рассматривать как скалярное произведение двух n-компонентных векторов: вектора градиента
и вектора скорости изменения координат-параметров
.
Скалярное произведение максимально, когда векторы коллинеарные. ............
