Градиентные методы поиска экстремума

РОССИЙСКАЯ академия народного хозяйства И ГОСУДАРСТВЕННОЙ СЛУЖБЫ при прЕЗИДЕНТЕ рф Факультет информационных технологий и анализа данных Отделение бизнес информатики Градиентные методы поиска экстремума Урубков Алексей Ратмирович Москва, 2020 г. Контактные данные преподавателя: Урубков Алексей Ратмирович  alratur@yandex.ru Сведения о градиентных методах нелинейной оптимизации. В основе всех методов классической оптимизации, как известно лежит необходимый признак экстремума Необходимое условие экстремума. Если – точка экстремума функции , то в этой точке Обратное не всегда верно – из равенства нулю частных производных в некоторой точке необязательно следует, что в этой точке экстремум. Те точки, в которых частные производные равны нулю, называют стационарными (критическими) - точками предполагаемого экстремума. . Примечание. Вектор частных производных для функции многих переменных, вычисленный в какой-либо точке области определения функции, называют вектором-градиентом и для его обозначения используют символику: где В реальных задачах нелинейного программирования со сложными целевыми функциями и большим количеством переменных (например, в задачах анализа больших данных) найти аналитические решения системы нелинейных уравнений и проверить выполнение необходимого условия экстремума в стационарных точках как правило не представляется возможным. В таких случаях классические теоретические модели заменяют численными методами, реализующими идеи классической оптимизации на основе многошаговых рекуррентных итерационных алгоритмов и процедур. Наибольшее распространение в приложениях получили градиентные методы поиска экстремума, основанные на свойствах вектора-градиента: В каждой точке области определения функции вектор-градиент указывает направление наибольшего роста функции (то направление, в котором прирост максимален) Общий алгоритм поиска экстремума градиентными методами Если для функции требуется найти точку максимума, то 1. Выбирается произвольная (начальная) точка из области определения функции 2. Вычисляются координаты вектора-градиента в точке 3. Используя свойства вектора-градиента - в каждой точке области определения функции вектор-градиент указывает то направление, в котором прирост максимален, переходят к следующей точке по формуле где - длина шага перемещения (перехода) из точки в точку . 4. Вычисляют значение вектора-градиента в новой точке . Если поиск экстремума продолжается. 5. Процедура последовательного перехода от одной точки к другой продолжается до тех пор, пока значения функции в двух последовательных точках не будут близки, т.е. будет выполнено (с заданной точностью) необходимое условие экстремума Примечания. 1. В задачах поиска минимума функции для перехода от одной точки к другой используют вектор, противоположный вектору-градиенту, показывающий направление наискорейшего «спуска», убывания функции. . 2. На основе градиентного метода создано большое количество модификаций, отличающихся процедурами выбора на каждой итерации оптимальной длины шага , с учетом особенностей целевых функций, проверками стационарных точек на «локальность» и многого другого. 3. Для целевых функций, зависящих только от двух переменных, для поиска экстремума можно использовать инструмент поверхностных диаграмм, позволяющий наглядно в графическом виде исследовать поведение функции и найти стационарные точки и точки экстремума. 4. В Excel в надстройке Поиск решения для решения задач нелинейного программирования предлагается два градиентных метода – «метод ОПГ» и «Эволюционный поиск решения», позволяющих решать большое количество прикладных задач. Применение моделей нелинейной оптимизации в задачах обработки данных Алгоритмы и модели нелинейной оптимизации широко применяются в задачах обработки данных для построения математических моделей, аналитически описывающих закономерности, присущие анализируемым объектам. Пример. Фирма вкладывает в рекламу своей продукции значительные средства. Как показал опыт, результаты – рост объема продаж не всегда соответствует и пропорционален рекламным затратам, а в ряде случаев приводит к обратным результатам. Для количественной оценки и анализа того, как вложенные в рекламу средства влияют на объемы продаж, фирмой были собраны данные за прошлые периоды деятельности (61 наблюдение), приведенные в таблице. Используя эту информацию, требуется построить математическую модель , которая могла бы рассчитывать объемы продаж () в зависимости от размера средств, вложенных в рекламу (). Решение. Этап 1. Выбор подходящего типа математической зависимости yрасч. = f (x) - функции, наиболее адекватно отражающей взаимосвязь между затратами и объемами продаж (линейная, степенная, полиномиальная и т.д.). Выбор подходящей функции можно обосновать и провести на основе анализа диаграмм, построенных на основе имеющихся данных. Этап 2. Оценка параметров выбранной математической модели (ее коэффициентов) таким образом, чтобы расхождения между реальными данными (объемами продаж) и объемами, рассчитанными по модели, были минимальны. В качестве меры расхождения между реальными и рассчитанными по модели данными можно использовать два критерия • Сумму квадратов отклонений реальных данных от расчетных (метод наименьших квадратов - МНК) • Сумму отклонений реальных данных от расчетных, взятых по абсолютной величине Тогда задачу построения математической модели для исследуемого объекта можно сформулировать как задачу нелинейного программирования – необходимо найти такие «управляемые переменные» - параметры (коэффициенты уравнения) искомой модели, при которых целевая функция Z - сумма «различий» между реальными и расчетными данными, будет минимальной.