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

Обновлено: 05.07.2024

Градиентный метод с использованием оптимального шага является методом скорейшего спуска.

Градиентный метод относится к методам возможных направлений, суть которых заключается в том, что спуск из любой точки начального приближения (Р 1 , Р 2 ) 0 к точке абсолютного минимума целевой функции можно осуществить по различным направлениям, при которых последовательно уменьшается F(Р 1 , Р 2 ).

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

С точки зрения локальных свойств противоположное ему направление антиградиента является наилучшим из всех возможных направлений, так как оно показывает путь наибольшего убывания функции F(Р 1 , Р 2 ).

Длина шага зависит от вектора и вычисляется из условия обеспечения максимального уменьшения целевой функции в заданном направлении. [pic 1][pic 2]

Задача формулируется таким образом, чтобы найти значение обеспечивающее минимум F(x) на Δx, т. е. min F(q, Δx). [pic 3]

Оптимальная длина шага вычисляется по формуле

Алгоритм для метода скорейшего спуска.

1 Задать исходное приближение для мощностей;

2 Вычислить значения мощности балансирующего узла и суммарного расхода топлива В;

3 Вычислить градиент целевой функции для исходного приближения;

4 Осуществить 2 шага по градиенту;

5 Вычислить оптимальную длину шага.

6 Рассчитать значение мощностей и расход топлива.

Полученное распределение мощностей рассматривать как исходное и перейти к выполнению п. 2.

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

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

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

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

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

Решается задача минимизации функции j(x) на всём пространстве E_n. Методы спуска состоят в следующей процедуре построения последовательности k>. Â качестве начального приближения выбирается любая точка x₀ÎE_n. Последовательные приближения x₁, x₂, … строятся по следующей схеме:

1) в точке x_k выбирают направление спуска — S_k;

Направление S_k выбирают таким образом, чтобы обеспечить неравенство j(x_k+1) 0.

В случае, если =0, полагают x_k+1=x_k и переходят к следующей итерации.

Нужна помощь в написании реферата?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.

Опишем первый цикл метода, состоящий из n итераций. В произвольной точке x₀ выбирают S₀=±e, и определяет величину b₀ способом удвоения так, чтобы было j(x₁)=j(x₀-b₀S₀) 2 +y 2 -xy-3y c точностью e, используя описанные выше методы.

Нахождение минимума моей функции с помощью метода покоординатного спуска.

Для получения результата программой было выполнено 24 итерации.

Нужна помощь в написании реферата?

Нахождение минимума с помощью метода градиентного спуска.

Программа, использованная мной для выполнения этой задачи представлена ниже.

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

Итак, взяв те же начальные условия я получил следующие результаты:

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

Нужна помощь в написании реферата?

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

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

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

Достоинства градиентных методов пропорционального поиска и наискорейшего спуска, или, как их иногда называют, градиентных методов первого порядка, не исчерпываются только простотой реализации. Эти методы эффективно работают при начале счета из точки, значительно удаленной от оптимума. Однако вблизи окрестности оптимума сходимость методов резко падает. Теоретически число шагов в методе… Читать ещё >

автоматизированные системы управления технологическими процессами на тэс

Метод наискорейшего спуска ( реферат , курсовая , диплом , контрольная )

Модифицируя метод выбора шага итерации, можно получить метод наискорейшего спуска. Алгоритм этого метода состоит в следующем. В начальной точке Х° определяют направление вектор-градиента. Через точку Х° по направлению вектор-градиента проводят прямую. Для точек этой прямой находят точку минимума функции /. Пусть это будет точка X* , J .

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

Поиск экстремума методом наискорейшего спуска для функции двух переменных иллюстрирует рис. 1.10.

Рис. 1.10. Стратегия поиска минимума квадратичной функции методом наискорейшего спуска

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

Существуют методы высокого порядка, которые лишены этого недостатка и обладают быстрой сходимостью в окрестности оптимума. К ним относятся методы второго порядка, в частности метод Ньютона—Рафсона.

Безусловная оптимизация. Метод наискорейшего спуска

Информация о материале Обновлено: 11.05.2017, 19:53 Категория: Системы уравнений и задачи оптимизации

- это значения аргумента функции (управляемые параметры) на вещественной области.

В соответствии с рассматриваемым методом экстремум (максимум или минимум) целевой функции определяют в направлении наиболее быстрого возрастания (убывания) функции, т.е. в направлении градиента (антиградиента) функции. Градиентом функции в точке называется вектор, проекциями которого на координатные оси являются частные производные функции по координатам:

где i, j,…, n - единичные векторы, параллельные координатным осям.

Градиент в базовой точке строго ортогонален к поверхности, а его направление показывает направление наискорейшего возрастания функции, а противоположное направление (антиградиент), соответственно, показывает направление наискорейшего убывания функции.

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

- единичный вектор направления, который определяется по формуле:

- модуль градиента определяет скорость возрастания или убывания функции в направлении градиента или антиградиента:

- константа, определяющая размеры шага и одинаковая для всех i-х направлений.

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

Другими словами, величину шага определяют при решении данного уравнения:

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

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

Рис.1. Траектория движения к точке экстремума при использовании метода наискорейшего спуска, изображенная на графике линии равного уровня функции f(x)

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

- траектория поиска остается в малой окрестности текущей точки поиска:

- приращение целевой функции не меняется:

- градиент целевой функции в точке локального минимума обращается в нуль:

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

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

Методика расчета

• 1 шаг: Определение аналитические выражения (в символьном виде) для вычисления градиента функции

• 2 шаг: Задаем начальное приближение

Далее выполняется итерационный процесс.

• 3 шаг: Определяется необходимость рестарта алгоритмической процедуры для обнуления последнего направления поиска. В результате рестарта поиск осуществляется заново в направлении скорейшего спуска.

• 4 шаг: Вычисление координат единичного вектора по представленным формулам

• 5 шаг: определяем шаг расчета из условия поиска экстремума для следующей функции (решения задачи одномерной оптимизации).

• 6 шаг: Определяем новые значения аргументов функции после выполнения k-го шага расчета:

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

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

Читайте также: