Задачи оптимизации (поиска наилучшего решения) не самые популярные в среде 1С-негов. Действительно, одно дело - учет выполнения каких-либо решений, и совершенно другое дело - принятие этих самых решений. В последнее время, однако, мне кажется 1С бросилась догонять конкурентов в данном вопросе. Действительно захватывающе объединить под одной крышей все, что может потребоваться современному менеджеру, догоняя в этом вопросе SAP и заменяя MS Project и другие системы планирования.

Впрочем, разговор о дальнейших путях развития 1С - это тема отдельной публикации и дискуссии, а пока я задумал цикл статей, объясняющих и демонстрирующих современные математические и алгоритмические подходы к многомерной нелинейной оптимизации, или, если хотите - механизмов поиска решений. Все статьи будут сопровождаться демо обработками с универсальными процедурами и функциями многомерной оптимизации - Ваше дело найти при желании им применение или принять на баланс полезного знания и инструментария (только тем, естественно, кто осилит данную статью до конца). Честно обещаю высшую математику излагать наиболее доступным языком и с примерами того, как эти жуткие формулы можно превратить в программно решаемые задачи:) Поехали...

Итак, первая тема - метод градиентного спуска .

Сфера применения метода - любые задачи на нахождения массива из n переменных, обеспечивающих минимальное (максимальное) значение целевой функции. Целевая функция при этом - функция от этих самых n переменных самого произвольного вида - единственное условие, накладываемое методом на целевую функцию - ее непрерывность по крайней мере на отрезке поиска решения. Непрерывность на практике обозначает, что для любого сочетания значений переменных можно найти действительное значение целевой функции.

Давайте введем обозначения:

Множество переменных Х, от которых зависит значение целевой функции

И сама целевая функция Z, вычисляемая самым произвольным образом из множества Х

Теперь поясним, что же такое градиент. Градиент это вектор многомерного пространства, указывающий направление наибольшего возрастания некоторой функции. Компонентами градиента являются дифференциалы всех переменных функции Z .

Вот отсюда и вытекает главное ограничение применимости метода градиентного спуска - дифференцируемость (непрерывность) функции на всем протяжении области поиска решения. Если данное условие соблюдается, то поиск оптимального решения вопрос чисто технический.

Классический метод градиентного спуска реализовывается для минимизации целевой функции через антиградиент (то есть вектор противоположный градиенту), который получается из градиента самым простым образом - умножением на -1 всех компонентов градиента. Или в обозначениях:

Теперь самый главный вопрос: а как нам найти эти самые d Z и dX1 , dX2 и т.д.? Очень просто! dXn - это бесконечно малое приращение переменной Xn , скажем 0,0001 от ее текущей величины. Или 0,0000000001 - главное, чтобы оно (приращение) было действительно малым:)

А как же вычисляется dZ ? Тоже элементарно! Вычисляем Z для набора переменных X , а затем изменяем в этом наборе переменную Xn на величину dXn . Снова вычисляем значение целевой функции Z для этого слегка модифицированного набора (Zn ) и находим разницу - это и будет dZ = Zn - Z . Ну а теперь коль нам известны dXn и dZ найти dZ/dXn проще пареной репы.

Найдя последовательно все компоненты градиента и антиградиента мы получаем направление изменения переменных, которое наискорейшим образом позволит достичь минимума функции.

На следующем (k+1) этапе, нужно вычислить новые значения массива переменных X . Очевидно, что для приближения к минимуму целевой функции Z мы должны корректировать значения X предыдущего (k-го) этапа в направлении антиградиента по такой формуле:

Остается разобраться с этой самой альфой в формуле. Зачем она нужна и откуда она берется.

α - это коэффициент на который домножается антиградиент для обеспечения достижения возможного минимума функции в заданном направлении. Сам по себе градиент или антиградиент не являются мерой сдвига переменной, а указывают лишь направление движения. Геометрический смысл градиента - это тангенс угла наклона касательной к функции Z в точке Xn (отношение противолежащего катета dZ к прилежащему dXn ), но двигаясь по касательной мы неизбежно отклонимся от линии функции до достижения ее минимума. Смысл касательной в том, что она дает отображение в виде прямой произвольной криволинейной функции в очень узком промежутке - окрестностях точки Xn .

Поиск значения параметра α выполняется одним из методов одномерной оптимизации. Значения переменных {X} нам известны, известны и их градиенты - остается минимизировать целевую функцию в окрестностях текущего решения по одному единственному параметру: α .

Останавливаться на одномерной оптимизации я здесь на буду - методы достаточно просты для понимания и реализации, скажу лишь, что я использовал в своем решении метод "золотого сечения". ОДЗ для α находится в промежутке от 0 до 1.

Итак, резюмируя написанное, сформулируем последовательность шагов для поиска решения методом градиентного спуска:

  1. Формируем начальное опорное решение, присваивая искомым переменным случайные значения из ОДЗ.
  2. Находим градиенты и антиградиенты для каждой переменной как отношения прироста целевой функции при относительно малом увеличении значения переменной к значению приращения этой самой переменной.
  3. Находим коэффициент α , на который нужно умножать антиградиенты перед добавлением к исходным значениям опорного решения методом одномерной оптимизации. Критерий оптимизации - наименьшее из возможных значение целевой функции для скорректированных таким образом значений {X} .
  4. Пересчитываем {X} в соответствии с наденными значениями антиградиентов и коэффициента сдвига α .
  5. Проверяем достигнута ли необходимая точность (ε ) вычисления минимума целевой функции:

6. Если условие выполнено и от этапа к этапу значение целевой функции изменилось ниже установленного нами же критерия это значит, что необходимая точность достигнута и текущее множество {X} является решением задачи, иначе - переход к шагу 2.

Теперь давайте перейдем к практической задаче, которая решена в обработке.

По условию задачи необходимо установить цену на некий товар таким образом, чтобы прибыль от его реализации в планируемом периоде была максимальной. При этом нужно учитывать, что объем реализации зависит от установленной нами цены, а закупочная цена товара (влияющая на валовую прибыль) также зависит от объема закупки товара: поставщик готов предоставлять скидки тем больше, чем больше будет объем нашей закупки. То есть нам нужно одновременно с установлением цены понимать, сколько товара мы сможем реализовать и по какой цене и, следовательно, сколько товара нам нужно для этого закупить, и тогда мы будем знать, какова будет закупочная цена. В общем, такая немного рекурсивная логика поиска решения:)

Самое главное, что мы имеем - это непрерывность переменных (цены и объема закупки / реализации) и целевой функции (прибыль есть всегда и может принимать любое значение, даже если она с минусом, то называется убыток), а значит, метод градиентного спуска - самое оно.

Для решения задачи данный метод применяется дважды: на первом этапе мы находим параметры уравнения спроса на продукцию по данным продаж предыдущих периодов. То есть, предполагая некий вид зависимости спроса от цены, вычисляем значения параметров этой зависимости, минимизируя сумму квадратов отклонений между расчетными и фактическими данными о продажах. На втором этапе, пользуясь найденными параметрами зависимости между объемом продаж и ценой реализации, мы оптимизируем прибыль и тоже методом градиентного спуска, хотя бы применяемым всего для одной переменной. Так как метод градиентного спуска минимизирует целевую функцию, а прибыль как ничто другое нуждается в максимизации, мы используем не твиальную целевую функцию с названием "МинусПрибыль", которая всего-то и делает, что вычисляет прибыль по полученному значению цены, а перед возвратом умножает ее на -1:) И ведь работает! Теперь чем меньше становится "МинусПрибыль", тем больше на самом деле самая что ни на есть реальная прибыль от продаж.

Пример решения в обработке, как и универсальная функция поиска решения методом градиентного спуска. Суть универсальности в том, что переменные {X} передаются в нее в виде массива, а целевая функция передается как параметр строкой. Целевую же функцию, которая принимает массив переменных и возвращает значение, пишите сами какого угодно вида - главное, чтобы она возвращала число. И такое число, что чем меньше оно будет, тем ближе поданный массив аргументов к оптимальному решению.

Почему не привел здесь готовую процедуру, а выкладываю обработку? Во-первых, процедура и без того длинновата, а во-вторых, без целевых функций она не работает, так что нужно затаскивать все, да и еще во взаимосвязи. Я надеюсь, что изложенной в статье теории вполне достаточно для того, чтобы Вы смогли реализовать свое решение, возможно, даже лучшим, чем у меня, образом. Ну если уж совсем не будет получаться - качайте готовую обработку и пользуйтесь:)

Вот, собственно, и все. Вопросы, пожелания и замечания жду в комментах. Спасибо за внимание.

В первой части я забыл упомянуть, что если случайно сгенерированные данные не по душе, то можно взять любой подходящий пример отсюда . Можно почувствовать себя ботаником , виноделом , продавцом . И все это не вставая со стула. В наличии множество наборов данных и одно условие - при публикации указывать откуда взял данные, чтобы другие смогли воспроизвести результаты.

Градиентный спуск

В прошлой части был показан пример вычисления параметров линейной регрессии с помощью метода наименьших квадратов. Параметры были найдены аналитически - , где - псевдообратная матрица. Это решение наглядное, точное и короткое. Но есть проблема, которую можно решить численно. Градиентный спуск - метод численной оптимизации, который может быть использован во многих алгоритмах, где требуется найти экстремум функции - нейронные сети, SVM, k-средних, регрессии. Однако проще его воспринять в чистом виде (и проще модифицировать).

Проблема заключается в том, что вычисление псевдообратной матрицы очень затратно : 2 умножения по , нахождение обратной матрицы - , умножение матрицы вектор , где n - количество элементов в матрице A (количество признаков * количество элементов в тестовой выборке) Если количество элементов в матрице A велико (> 10^6 - например), то даже если в наличии 10000 ядер, нахождение решения аналитически может затянуться. Также первая производная может оказаться нелинейной, что усложнит решение, аналитического решения может не оказаться вовсе или данные могут просто не влезть в память и потребуется итеративный алгоритм. Бывает, что в плюсы записывают и то, что численное решение не идеально точное. В связи с этим функцию стоимости минимизируют численными методами. Задачу нахождения экстремума называют задачей оптимизации. В этой части я остановлюсь на методе оптимизации, который называется градиентный спуск.

Не будем отходить от линейной регрессии и МНК и обозначим функцию потерь как - она осталась неизменной. Напомню, что градиент - это вектор вида , где - это частная производная. Одним из свойств градиента является то, что он указывает направление, в котором некоторая функция f возрастает больше всего. Доказательство этого следует из определения производной. Пара доказательств . Возьмем некоторую точку a - в окрестности этой точки функция F должна быть определена и дифференцируема, тогда вектор антиградиента будет указывать на направление, в котором функция F убывает быстрее всего. Отсюда делается вывод, что в некоторой точке b, равной , при некотором малом значение функции будет меньше либо равным значению в точке а. Можно представить это, как движение вниз по холму - сделав шаг вниз, текущая позиция будет ниже, чем предыдущая. Таким образом, на каждом следующем шаге высота будет как минимум не увеличиваться. Формальное определение . Исходя из этих определений можно получить формулу для нахождения неизвестных параметров (это просто переписанная версия формулы выше):

Это шаг метода. В задачах машинного обучения его называют скоростью обучения.

Метод очень прост и интуитивен, возьмем простой двумерный пример для демонстрации:

Необходимо минимизировать функцию вида . Минимизировать значит найти при каком значении функция принимает минимальное значение. Определим последовательность действий:

1) Необходима производная по :
2) Установим начальное значение = 0
3) Установим размер шага - попробуем несколько значений - 0.1, 0.9, 1.2, чтобы посмотреть как этот выбор повлияет на сходимость.
4) 25 раз подряд выполним указанную выше формулу: Так как неизвестный параметр только один, то и формула только одна.

Код крайне прост. Исключая определение функций, весь алгоритм уместился в 3 строки:

simple_gd_console.py

STEP_COUNT = 25 STEP_SIZE = 0.1 # Скорость обучения def func(x): return (x - 5) ** 2 def func_derivative(x): return 2 * (x - 5) previous_x, current_x = 0, 0 for i in range(STEP_COUNT): current_x = previous_x - STEP_SIZE * func_derivative(previous_x) previous_x = current_x print("After", STEP_COUNT, "steps theta=", format(current_x, ".6f"), "function value=", format(func(current_x), ".6f"))

Весь процесс можно визуализировать примерно так (синяя точка - значение на предыдущем шаге, красная - текущее):

Или же для шага другого размера:

При значении, равном 1.2, метод расходится, каждый шаг опускаясь не ниже, а наоборот выше, устремляясь в бесконечность. Шаг в простой реализации подбирается вручную и его размер зависит от данных - на каких-нибудь ненормализованных значениях с большим градиентом и 0.0001 может приводить к расхождению.

Код для генерации гифок

import matplotlib.pyplot as plt import matplotlib.animation as anim import numpy as np STEP_COUNT = 25 STEP_SIZE = 0.1 # Скорость обучения X = def func(x): return (x - 5) ** 2 def bad_func(x): return (x - 5) ** 2 + 50 * np.sin(x) + 50 Y = def func_derivative(x): return 2 * (x - 5) def bad_func_derivative(x): return 2 * (x + 25 * np.cos(x) - 5) # Какая-то жажа и первый кадр пропускается skip_first = True def draw_gradient_points(num, points, line, cost_caption, step_caption, theta_caption): global previous_x, skip_first, ax if skip_first: skip_first = False return points, line current_x = previous_x - STEP_SIZE * func_derivative(previous_x) step_caption.set_text("Step: " + str(num)) cost_caption.set_text("Func value=" + format(func(current_x), ".3f")) theta_caption.set_text("$\\theta$=" + format(current_x, ".3f")) print("Step:", num, "Previous:", previous_x, "Current", current_x) points.set_data(previous_x, func(previous_x)) points.set_data(current_x, func(current_x)) # points.set_data(, ) line.set_data(, ) if np.abs(func(previous_x) - func(current_x)) < 0.5: ax.axis() if np.abs(func(previous_x) - func(current_x)) < 0.1: ax.axis() if np.abs(func(previous_x) - func(current_x)) < 0.01: ax.axis() previous_x = current_x return points, line previous_x = 0 fig, ax = plt.subplots() p = ax.get_position() ax.set_position() ax.set_xlabel("$\\theta$", fontsize=18) ax.set_ylabel("$f(\\theta)$", fontsize=18) ax.plot(X, Y, "-r", linewidth=2.0) ax.axvline(5, color="black", linestyle="--") start_point, = ax.plot(, "bo", markersize=10.0) end_point, = ax.plot(, "ro") rate_capt = ax.text(-0.3, 1.05, "Rate: " + str(STEP_SIZE), fontsize=18, transform=ax.transAxes) step_caption = ax.text(-0.3, 1, "Step: ", fontsize=16, transform=ax.transAxes) cost_caption = ax.text(-0.3, 0.95, "Func value: ", fontsize=12, transform=ax.transAxes) theta_caption = ax.text(-0.3, 0.9, "$\\theta$=", fontsize=12, transform=ax.transAxes) points = (start_point, end_point) line, = ax.plot(, "g--") gradient_anim = anim.FuncAnimation(fig, draw_gradient_points, frames=STEP_COUNT, fargs=(points, line, cost_caption, step_caption, theta_caption), interval=1500) # Для того, чтобы получить гифку необходимо установить ImageMagick # Можно получить.mp4 файл без всяких magick-shmagick gradient_anim.save("images/animation.gif", writer="imagemagick")

Вот еще пример с «плохой» функцией. В первой анимации метод также расходится и будет долго блуждать по холмам из-за слишком высокого шага. Во втором случае был найден локальный минимум и варьируя значение скорости не получится заставить метод найти минимум глобальный. Этот факт является одним недостатков метода - он может найти глобальный минимум только если функция выпуклая и гладкая. Или если повезет с начальными значениями.

Плохая функция

Плохая функция:


Также возможно рассмотреть работу алгоритма на трехмерном графике. Часто рисуют только изолинии какой-то фигуры. Я взял простой параболоид вращения: . В 3D выглядит он так:
, а график с изолиниями - «вид сверху».

Contour plot


Генерация графика с изолиниями

import matplotlib.pyplot as plt import matplotlib.animation as anim import numpy as np STEP_COUNT = 25 STEP_SIZE = 0.005 # Скорость обучения X = np.array() Y = np.array() def func(X, Y): return 4 * (X ** 2) + 16 * (Y ** 2) def dx(x): return 8 * x def dy(y): return 32 * y # Какая-то жажа и первый кадр пропускается skip_first = True def draw_gradient_points(num, point, line): global previous_x, previous_y, skip_first, ax if skip_first: skip_first = False return point current_x = previous_x - STEP_SIZE * dx(previous_x) current_y = previous_y - STEP_SIZE * dy(previous_y) print("Step:", num, "CurX:", current_x, "CurY", current_y, "Fun:", func(current_x, current_y)) point.set_data(, ) # Blah-blah new_x = list(line.get_xdata()) + new_y = list(line.get_ydata()) + line.set_xdata(new_x) line.set_ydata(new_y) previous_x = current_x previous_y = current_y return point previous_x, previous_y = 8.8, 8.5 fig, ax = plt.subplots() p = ax.get_position() ax.set_position() ax.set_xlabel("X", fontsize=18) ax.set_ylabel("Y", fontsize=18) X, Y = np.meshgrid(X, Y) plt.contour(X, Y, func(X, Y)) point, = plt.plot(, , "bo") line, = plt.plot(, color="black") gradient_anim = anim.FuncAnimation(fig, draw_gradient_points, frames=STEP_COUNT, fargs=(point, line), interval=1500) # Для того, чтобы получить гифку необходимо установить ImageMagick # Можно получить.mp4 файл без всяких magick-shmagick gradient_anim.save("images/contour_plot.gif", writer="imagemagick")

Также обратите внимание, что все линии градиента, направлены перпендикулярно изолиниям. Это означает, что двигаясь в сторону антиградиента, не получится за один шаг сразу же прыгнуть в минимум - градиент указывает совсем не туда.

После графического пояснения, найдем формулу для вычисления неизвестных параметров линейной регрессии с МНК.

Если бы количество элементов в тестовой выборке было равно единице, то формулу можно было бы так и оставить и считать. В случае, когда в наличии n элементов алгоритм выглядит так:

Повторять v раз
{

для каждого j одновременно.
}, где n - количество элементов в обучающей выборке, v - количество итераций

Требование одновременности означает, что производная должна быть вычислена со старыми значениями theta, не стоит вычислять сначала отдельно первый параметр, затем второй и т.д., потому что после изменения первого параметра отдельно, производная также изменит свое значение. Псевдокод одновременного изменения:

For i in train_samples: new_theta = old_theta + a * derivative(old_theta) new_theta = old_theta + a * derivative(old_theta) old_theta = new_theta

Если вычислять значения параметров по одиночке, то это уже будет не градиентный спуск. Допустим, у нас трехмерная фигура и если вычислять параметры один за одним, то можно представить этот процесс как движение только по одной координате за раз - один шажок по x координате, затем шажок по y координате и т.д. ступеньками, вместо движения в сторону вектора антиградиента.

Приведенный выше вариант алгоритма называют пакетный градиентный спуск. Количество повторений можно заменить на фразу «Повторять, пока не сойдется». Эта фраза означает, что параметры будут корректироваться до тех пор, пока предыдущее и текущее значения функции стоимости не сравняются. Это значит, что локальный или глобальный минимум найден и дальше алгоритм не пойдет. На практике равенства достичь невозможно и вводится предел сходимости . Его устанавливают какой-нибудь малой величиной и критерием остановки является то, что разность предыдущего и текущего значений меньше предела сходимости - это значит, что минимум достигнут с нужной, установленной точностью. Выше точности (меньше ) - больше итераций алгоритма. Выглядит это как-то так:

While abs(S_current - S_previous) >= Epsilon: # do something

Так как пост неожиданно растянулся, я бы хотел его на этом завершить - в следующей части я продолжу разбор градиентного спуска для линейной регрессии с МНК.

Лабораторная работа № 2

Тема : Многомерная безусловная оптимизация (методы первого и нулевого порядков).

Цель работа: знакомство с методами многомерной безусловной оптимизации первого и нулевого порядка и их освоение , сравнение эффективности применения этих методов конкретных целевых функций.


  1. Краткие теоретические сведения.

    1. О численных методах многомерной оптимизации.

Задача многомерной безусловной оптимизации формулируется в виде:

Где x={x (1) , x (2) ,…, x (n) } – точка в n-мерном пространстве X=IR n , то есть целевая функция f(x)=f(x (1) ,…,f(x (n)) – функция n аргументов.

Так же как и в первой лабораторной работе мы рассматриваем задачу минимизации. Численные методы отыскания минимума, как правило, состоят в построении последовательности точек {x k }, удовлетворяющих условию f(x 0)>f(x 1)>…>f(x n)>… . Методы построения таких последовательностей называются методами спуска. В этих методах точки последовательности {x k } вычисляются по формуле:

Х k +1 = x k +  k p k , k=0,1,2,… ,

Где p k – направление спуска,  k – длина шага в этом направлении.
Различные методы спуска отличаются друг от друга способами выбора направления спуска p k и длины шага  k вдоль этого направления. Алгоритмы безусловной минимизации принято делить на классы, в зависимости от максимального порядка производных минимизируемой функции, вычисление которых предполагается. Так, методы, использующие только значения самой целевой функции , относят к методам нулевого порядка (иногда их называют также методами прямого поиска); если, кроме того, требуется вычисление первых производных минимизируемой функции, то мы имеем дело с методами первого порядка; если же дополнительно используются вторые производные, то это методы второго порядка и т. д.

1.2. Градиентные методы.
1.2.1. Общая схема градиентного спуска.

Как известно , градиент функции в некоторой точке x k направлен в сторону наискорейшего локального возрастания функции и перпендикулярен линии уровня (поверхность постоянного значения функции f(x), проходящей через точку x k). Вектор, противоположный градиенту , называется антиградиентом , который направлен в сторону наискорейшего убывания функции f(x). Выбирая в качестве направления спуска p k антиградиент - в точке x k , мы приходим к итерационному процессу вида:

X k +1 = x k -  k f’(x k),  k >0, k=0,1,2,… .

Но может привести к неприемлемо большому количеству итераций, необходимых для достижения точки минимума. С другой стороны , слишком большой шаг может вызвать неожиданный рост функции (невыполнение условия убывания) либо привести к колебаниям около точки минимума. Однако проверка условия убывания на каждой итерации является довольно трудоемкой, поэтому в методе градиентного спуска с постоянным шагом задают = k постоянным и достаточно малым, чтобы можно было использовать этот шаг на любой итерации. При этом приходится мириться с возможно большим количеством итераций. Утешением является лишь то, что трудоемкость каждой итерации, в этом случае, минимальна (нужно вычислять только градиент ).

Схема алгоритма

Задаются начальное приближение х 0 , постоянный шаг  , условия останова алгоритма  3 . Вычисляется значение градиента – направление поиска. Присваивается к=0.

Определяется точка очередного эксперимента:


Если ||
|| 3 , то поиск точки минимума заканчивается и полагается:
Иначе к=к+1 и переход к шагу 2.
1.3.Метод покоординатного спуска.

При к=0 вводятся исходные данные х 0 ,  1 .


Осуществляется циклический по j (j=1,2,…,n) покоординатный спуск из точки х kn по формулам:


где  kn + j -1 является решением задачи одномерной минимизации функции:


Если ||x (k +1) n – x kn || 1 , то поиск минимума заканчивается , причем:

Иначе к=к+1 и переходим к шагу 2.

Рассмотрим методы отыскания экстремума функ­ции R ( x ) без активных ограничений. Активными принято называть такие ограничения, на границе которых находится решение. Величина шага х в соотношении

x i +1 = x i + x i

вычисляется с использованием градиента целевой функции R ( x ), т.е.

x i = ( gradR ( x i )),

при этом шаг может определяться с использованием градиента в одной (текущей) или в двух (текущей и предыдущей) точках. На­правление градиента, как известно, показывает направления наискорейшего возрас­тания функции, а его модуль - скорость это­го возрастания.

Вычисление градиента предполагает непрерывность функции многих переменных

Поисковые методы оптимизации содержат задаваемые па­раметры, которые су­щественно влияют на эффективность поиска, вследствие чего один и тот же метод может дать совершенно различные траектории поиска. По­этому для всех методов, рассматриваемых далее, на рис.3.5 приводится лишь одна из возможных траекторий.

Рис. 3.5 . Иллюстрация траекторий поис­ка минимума функции градиентными

методами:

1 - оптимум; 2 -- траекто­рия метода градиента; 3 - траектория метода

тяжелого шарика; 4 - траек­тория метода наискорейшего спуска;

5 - траектория метода сопряженных градиентов;

Кроме того, для всех приве­денных траекторий выбраны различные начальные условия, с тем, чтобы не загромождать построения. На этом и последующих ри­сунках зависимость R ( x 1 , x 2 ) приведена в виде линий уровня на плоскости в координатах x 1 - x 2 .

Основные методы

Метод градиента.

Метод градиента в чистом виде формирует шаг по переменным как функцию от градиента R ( x ) в текущей точке поиска. Простейший алгоритм поиска min R ( x ) записывается в векторной форме следующим образом:

или в скалярном виде:


- порядковый номер аргумента,

Величина рабочего шага в направлении градиента h grad R ( x ) зависит от величины градиента, который заранее учесть трудно, и от коэффициента пропорциональности шага h , с помощью которого можно управлять эффективностью метода.

Поиск каждой новой точки состоит из двух этапов:

1) оценка градиента R ( x ) путем вычисления частных производных от R ( x ) по каждой переменной х j ,

2) рабочий шаг по всем переменным одновременно.

Величина h сильно влияет на эффективность метода. Большей эффективностью обладает вариант метода, когда шаг по переменной определяется направляющими косинусами градиента.

где cosφ j =

В этом случае величина рабочего шага не зависит от величи­ны модуля градиента, и ею легче управлять изменением h . В рай­оне оптимума может возникать значительное "рыскание", поэто­му используют различные алгоритмы коррекции h .

Наибольшее распространение получили следующие алго­ритмы:

1. h i = const = h (без коррекции);

2. h i = h i -1 /2, если R (x i ) < R (x i -1 ) ; h i = h i -1 , R (x i ) > R (x i -1 ) ;

3. h i = h i -1 , если  1 ≤  ≤ 2 ; h i =2h i -1 , если 1 >;
если 2 < .

где - угол между градиентами на предыдущем и текущем ша­ге; 1 и 2 - заданные пороговые значения выбираются субъек­тивно (например, 1 = π/6, 2 = π/3).

Вдали от оптимума направление градиента меняется мало, по­тому шаг можно увеличить (второе выражение), вблизи от опти­мума направление резко меняется (угол между градиентами R ( x ) большой), поэтому h сокращается (третье выражение).

Для оценки частных производных используются разностные методы:

1 . Алгоритм с центральной пробой

2. Алгоритм с парными пробами

где g j - пробный шаг по j -й переменной, выбираемый достаточ­но малым для разностной оценки производной.

Первый алгоритм требует меньших затрат по сравнению со вторым (обычно затраты выражаются количеством вычислений критерия оптимальности), но позволяет получить решение менее точно, чем второй, и эта погрешность зависит от величины проб­ного шага.

На рис. приведена одна из возможных траекторий поиска минимума двумерной функции градиентным методом (наряду с другими ниже рассматриваемыми методами).

Условием окончания поиска может являться малость модуля градиента R ( x ) , т.е. |grad R ( x ) | < .


Рис. Иллюстрация получения производной с центральной и парными пробами.

Пример 1.

    Требуется найти минимумфункции

R ( x 1 , x 2 ) = х 1 3 + 2 х 2 2 - 3х 1 - 4x 2 ,

2. Интервал поиска квадрат: х 1нач = -2, х 1кон = 2, х 2нач = -2, х 2кон = 2.

3. Начальная точка: х 10 = - 0,5, х 20 = -1.

4. Параметры поиска: коэффициент шага h = 0,1, пробный g = 0,01, погрешность = 0,01.

5. Алгоритм метода: алгоритм 1 (х i +1 =х i - h grad R ( x i ) ).

6. Алгоритм коррекции шага: без коррекции коэффициента пропорциональности шага (h = const).

7. Способ вычисления производной: вычисление grad R с парными пробами.

Результаты вычислений . В начальной точке вычисляем градиент функции:


Значение критерия R = 7,3750. Делаем рабочий шаг по формуле 5, получаем

х 1 = - 0,275, х 2 = - 0,2.

В новой точке опять вычисляем производные:


Значение критерия R = 1,3750.

Делаем рабочий шаг, получаем x 1 = 0,002, х 2 = 0,280.

Таблица 18

dR /dx 1

dR /dx 2

В последней точке модуль градиента меньше заданной по­грешности (0,0063 < 0,01), поэтому поиск прекращается.

Построить зависимость градиента от № шага

Пример 2.

Отличается от предыдущего только величиной коэффициента пропорциональности шага h , теперь h = 0,4. Ниже, в табл. 19 при­ведены только первые 14 шагов (как и в предыдущем случае). Целесообразно сопоставить их путем построения траекторий поиска при обоих значениях h в координатах х 1 – х 2 .

Таблица 19

dR /dx 1

dR /dx 2

В этом случае поиск носит явно колебательный характер, плохо приближаясь к решению.

номер итерации

параметр оптимизации h=0,4

параметр оптимизации h=0, 1

Рис. 2.5. Сравнение сходимости градиентного метода при использовании различного шага.

Метод наискорейшего спуска.

Основным недостатком градиентного метода является необходимость частого вычисления производных от R ( x ) . Этого недостатка лишен метод наискорейшего спуска, который заключается в следующем.

В текущей точке вычисляется grad R ( x ) , и затем в направлении градиента ищется min R ( x ) . Практически это может быть осуществлено любым методом одномерной оптимизации (поиск по одному направлению - направлению градиента), наиболее часто используется сканирование до первого локального минимума по направлению grad R ( x ) .

В результате вдали от оптимума эффективность метода повышается, мы быстрее попадаем в район оптимума, в окрестности которого эффективность метода снижается из-за частой смены направления поиска и приближается к эффективности метода градиента.

Метод, как и все градиентные методы, обладает невысокой эффективностью в овражных функциях. В ряде случаев можно повысить скорость выхода в район оптимума предъявлением невысоких требований к точности поиска min по направлению (задается величиной h - шагом поиска по направлению).

Условием окончания может являться малость модуля градиента R ( x ) | grad R ( x ) | < . Можно также использовать и малость прира­щений по переменным в результате шага, но только в том случае, если на данном шаге мы "проскочили" оптимум, иначе может оказаться, что малость шага обусловлена не близостью к оптиму­му, а малостью коэффициента пропорциональности шага h .

В ряде случаев используют уменьшение шага поиска оптиму­ма по направлению после каждой смены направления. Это позво­ляет с большей точностью каждый раз находить оптимум, но рез­ко снижает эффективность поиска в овражных функциях. Метод используется для локализации "дна оврага" в специальных ов­ражных методах. Условием окончания поиска в этом случае явля­ется достижение заданной малой величины шага.

Одна из возможных траекторий поиска минимума двумерной функции методом наискорейшего спуска приведена на рис. выше.

Пример.

Для сравнения с методом градиента рассмотрим решение пре­дыдущего примера при h = 0,1.

Результаты расчетов. Расчет производных детально рассмотрен выше, поэтому здесь не приводится. Ниже, в табл. 20 приводятся результаты движения по градиенту с постоянным ша­гом.

Таблица 20

dR /dx 1

dR /dx 2

В следующей точке (0,400, 2,00) значение критерия (R = -0,256) оказывается хуже, чем в последней (R =-2,1996). По­этому в найденной точке оптимума по направлению снова вычис­ляем градиент и по нему совершаем шаги, до тех пор, пока не най­дем наилучшую точку (табл. 21).

Таблица 21

dR /d х 1

dR /d х 2

Второй поиск по градиенту

Третий поиск по градиенту

Четвертый поиск по градиенту

Пятый поиск по градиенту

Метод сопряженных градиентов (пропустить).

Градиентные методы, базирующиеся только на вычислении градиента R ( x ) , являются методами первого порядка, так как на интервале шага они заменяют нелинейную функцию R ( x ) линейной.

Более эффективными могут быть методы второго порядка, которые используют при вычислении не только первые, но и вторые производные от R ( x ) в текущей точке. Однако у этих методов есть свои труднорешаемые проблемы - вычисление вторых производных в точке, к тому же вдали от оптимума матрица вторых производных может быть плохо обусловлена.

Метод сопряженных градиентов является попыткой объединить достоинства методов первого и второго порядка с исключе­нием их недостатков. На начальных этапах (вдали от оптимума) метод ведет себя как метод первого порядка, а в окрестностях оптимума приближается к методам второго порядка.

Первый шаг аналогичен первому шагу метода наискорейшего спуска, второй и следующий шаги выбираются каждый раз в на­правлении, образуемом в виде линейной комбинации векторов градиента в данной точке и предшествующего направления.

Алгоритм метода можно записать следующим образом (в век­торной форме):

Величина может быть приближенно найдена из выражения

Алгоритм работает следующим образом. Из начальной точки х 0 ищут min R ( x ) в направлении градиента (методом наискорейшего спуска), затем, начиная с найденной точки и далее, направ­ление поиска min определяется по второму выражению. Поиск минимума по направлению может осуществляться любым спосо­бом: можно использовать метод последовательного сканирова­ния без коррекции шага сканирования при переходе минимума, поэтому точность достижения минимума по направлению зави­сит от величины шага h .

Для квадратичной функции R ( x ) решение может быть найдено за п шагов (п - размерность задачи). Для других функций поиск будет медленнее, а в ряде случаев может вообще не достигнуть оптимума вследствие сильного влияния вычислительных оши­бок.

Одна из возможных траекторий поиска минимума двумерной функции методом сопряженных градиентов приведена на рис. 17.