В основе метода лежит следующая итерационная модификация формулы

x k +1 = x k + a k s(x k),

x k+1 = x k - a k Ñ f(x k), где

a - заданный положительный коэффициент;

Ñ f(x k) - градиент целевой функции первого порядка.

Недостатки:

необходимость выбора подходящего значения ;

медленная сходимость к точке минимума ввиду малости f(x k) в окрестности этой точки.

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

Свободен от первого недостатка простейшего градиентного метода, т.к. a k вычисляется путем решения задачи минимизации Ñ f(x k) вдоль направления Ñ f(x k) с помощью одного из методов одномерной оптимизации x k+1 = x k - a k Ñ f(x k).

Данный метод иногда называют методом Коши.

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

Метод сопряженных направлений

Общая задача нелинейного программирования без ограничений сводится к следующему: минимизировать f(x), x E n , где f(x) является целевой функцией. При решении этой задачи мы используем методы минимизации, которые приводят к стационарной точке f(x), определяемой уравнением f(x *)=0. Метод сопряженных направлений относится к методам минимизации без ограничений, использующим производные. Задача: минимизировать f(x), x E n , где f(x) является целевой функцией n независимых переменных. Важной особенностью является быстрая сходимость за счет того, что при выборе направления используется матрица Гессе, которая описывает область топологии поверхности отклика. В частности, если целевая функция квадратичная, то можно получить точку минимума не более чем за количество шагов, равное размерности задачи.

Для применения метода на практике его необходимо дополнить процедурами проверки сходимости и линейной независимости системы направлений. Методы второго порядка

Метод Ньютона

Последовательное применение схемы квадратичной аппроксимации приводит к реализации оптимизационного метода Ньютона по формуле

x k +1 = x k - Ñ 2 f(x k -1) Ñ f(x k).

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

x k +1 = x k - a k Ñ 2 f(x k -1) Ñ f(x k), где

a k - параметр, выбираемый таким образом, чтобы f(x k+1) min.

2. Нахождение экстремума функции без ограничения

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

Определение exst. Функция f(x) заданная на интервале (а, в) имеет в точке x * max(min), если эту точку можно окружить таким интервалом (x * -ε, x * +ε), содержащимся в интервале (а, в), что для всех ее точек х, принадлежащих интервалу (x * -ε, x * +ε), выполняется неравенство:

f(x) ≤ f(x *) → для max

f(x) ≥ f(x *) → для min

Это определение не накладывает никаких ограничений на класс функций f(x), что, конечно, очень ценно.

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

Теорема Ферма. Пусть функция f(x) определена в некотором интервале (а, в) и в точке "с" этого интервала принимает наибольшее (наименьшее) значение. Если существует в этой точке двухсторонняя конечная производная , то существования необходимоexst .

Примечание. Двухсторонняя производная характеризуется свойством иными словами, речь идет о том, что в точке "с" производная в пределе одна и та же при подходе к точке "с" слева и справа, т.е.f(x) – гладкая функция.

* В случае имеет местоmin, а при →max. Наконец, если при х=х 0 , то использование 2-ой производной не помогает и нужно воспользоваться, например, определением exst.

При решении задачи I необходимые условия exst (т.е. теорема Ферма) используется очень часто.

Если уравнение exst имеет вещественные корни, то точки, соответствующие этим корням, являются подозрительными наexst (но не обязательно самыми экстремумами, ибо имеем дело с необходимыми, а не с необходимыми и достаточными условиями). Так, например, в точке перегиба Х п имеет место , однако, как известно, это не экстремум.

Заметим ещё, что:

из необходимых условий нельзя сказать, какой вид экстремума найден max или min: для определения этого нужны дополнительные исследования;

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

Поэтому, когда находят точки подозрительные на exst, их дополнительно исследуют, например, на основе определения exst или 2-ой производной.

Метод релаксации

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

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

Пусть – осевое направление, т.е. .

Если знак производной отрицательный, функция убывает в направлении оси, если положительный – в обратном направлении:

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

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

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

Алгоритм спуска для выбранного осевого направления может быть записан так

(3.8)

где -значение варьируемой переменной на каждом шаге спуска;

Величина k+1 шага, которая может изменяться в зависимости от номера шага:

– функция знака z;

Вектор точки, в которой последний раз производилось вычисление производных ;

Знак “+” в алгоритме (3.8) принимается при поиске max I, а знак “-” – при поиске min I.Чем меньше шаг h., тем больше количество вычислений на пути движения к оптимуму. Но при слишком большой величине h вблизи оптимума может возникнуть зацикливание процесса поиска. Вблизи оптимума необходимо, чтобы выполнялось условие h

Простейший алгоритм изменения шага h состоит в следующем. В начале спуска задается шаг , равный например, 10% от диапазона d; изменения с этим шагом производится спуск по выбранному направлению до тез пор, пока выполняется условие для двух последующих вычислений

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

Формальная запись этого алгоритма следующая:

(3.9)

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

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

Рисунок 3.5 – Траектория движения к оптимуму в методе релаксации

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

Шаг 1. – осевое направление,

; , если ;

Шаг 2. – новое осевое направление;

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

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

Рисунок 3.6 – Градиент функции

.

Направление градиента – это направление наиболее быстрого возрастания функции (наиболее крутого “склона” поверхности отклика). Противоположное ему направление (направление антиградиента) – это направление наибыстрейшего убывания (направление наискорейшего “спуска” величин ).

Проекция градиента на плоскость переменных перпендикулярна касательной к линии уровня , т.е. градиент ортогонален к линиям постоянного уровня целевой функции (рис. 3.6).

Рисунок 3.7 – Траектория движения к оптимуму в методе

градиента

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

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

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

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

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

, (3.10)

или в векторной форме

, (3.11)

где – положительная константа;

“+” – при поиске max I;

“-” – при поиске min I.

Алгоритм градиентного поиска при нормировании градиента (деление на модуль) применяется в виде

; (3.12)

(3.13)

Определяет величину шага по направлению градиента.

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

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

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

Процесс поиска продолжается до тех пор, пока , , не станут близки к нулю или пока не будет достигнута граница области задания переменных.

В алгоритме с автоматическим уточнением шага величину уточняют так, чтобы изменение направления градиента в соседних точках и

Критерии окончания поиска оптимума:

; (3.16)

; (3.17)

где – норма вектора.

Поиск завершается при выполнении одного из условий (3.14) – (3.17).

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

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

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

Рис. 4.11.

Рис. 4.12.

(двумерный случай)

Вначале выбирают начальную точку Если в одномерном случае (см. подпараграф 4.2.6) из нее можно было

сдвинуться только влево или вправо (см. рис. 4.9), то в многомерном случае число возможных направлений перемещения бесконечно велико. На рис. 4.11, иллюстрирующем случай двух переменных, стрелками, выходящими из начальной точки А, показаны различные возможные направления. При этом движение по некоторым из них дает увеличение значения целевой функции по отношению к точке А (например, направления 1-3), а по другим направлениям приводит к его уменьшению (направления 5-8). Учитывая, что положение точки оптимума неизвестно, считается наилучшим то направление, в котором целевая функция возрастает быстрее всего. Это направление называется градиентом функции. Отметим, что в каждой точке координатной плоскости направление градиента перпендикулярно касательной к линии уровня, проведенной через ту же точку.

В математическом анализе доказано, что составляющие вектора градиента функции у =/(*, х 2 , ..., х п) являются ее частными производными по аргументам, т.е.

&ад/(х 1 ,х 2 ,.= {ду/дху,ду/дх 2 , ...,ду/дх п }. (4.20)

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

У" с координатами:

1§гас1/(х (0)),

или в векторной форме

где X - постоянный или переменный параметр, определяющий длину рабочего шага, ?і>0. На второй итерации снова вычисляют

вектор градиента уже для новой точки.У, после чего по анало-

гичной формуле переходят в точку х^ > и т.д. (рис. 4.12). Для произвольной к- й итерации имеем

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

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

длина рабочего шага - расстояние между соседними точками х^

их 1 " - окажется пропорциональном модулю вектора градиента. Можно, наоборот, на каждой итерации выбирать X таким, чтобы длина рабочего шага оставалась постоянной.

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

у = 110-2(лг, -4) 2 -3(* 2 -5) 2 .

Разумеется, воспользовавшись необходимым условием экстремума, сразу получим искомое решение: х ] - 4; х 2 = 5. Однако на этом простом примере удобно продемонстрировать алгоритм градиентного метода. Вычислим градиент целевой функции:

grad у = {ду/дх-,ду/дх 2 } = {4(4 - *,); 6(5 - х 2)} и выбираем начальную точку

Л*» = {х}°> = 0; 4°> = О}.

Значение целевой функции для этой точки, как легко подсчитать, равно у[х^ j = 3. Положим, X = const = 0,1. Величина градиента в точке

Зс (0) равна grad y|x^j = {16; 30}. Тогда на первой итерации получим согласно формулам (4.21) координаты точки

х 1) = 0 + 0,1 16 = 1,6; х^ = 0 + 0,1 30 = 3.

у(х (1)) = 110 - 2(1,6 - 4) 2 - 3(3 - 5) 2 = 86,48.

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

• 1,6 + 0,1 4(4 - 1,6) = 2,56;

В задаче безусловной оптимизации отсутствуют ограничения.

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

Градиент скалярной функции F (X ) в некоторой точке направлен в сторону наискорейшего возрастания функции и ортогонален линии уровня (поверхности постоянного значения F (X ), проходящей через точку X k ). Вектор, противоположный градиенту  антиградиент  направлен в сторону наискорейшего убывания функции F (X ). В точке экстремума grad F (X )= 0.

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

где  k  параметр шага на k -й итерации вдоль антиградиента. Для методов восхождения (поиска максимума) нужно двигаться по градиенту.

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

Метод с постоянным параметром шага. В этом методе параметр шага постоянен на каждой итерации. Возникает вопрос: как практически выбрать величину параметра шага? Достаточно малый параметр шага может привести к неприемлемо большому количеству итераций, необходимых для достижения точки минимума. С другой стороны, слишком большой параметр шага может привести к проскакиванию точки минимума и к колебательному вычислительному процессу около этой точки. Указанные обстоятельства являются недостатками метода. Поскольку невозможно заранее угадать приемлемое значение параметра шага  k , то возникает необходимость использования градиентного метода с переменным параметром шага.

По мере приближения к оптимуму вектор градиента уменьшается по величине, стремясь к нулю, поэтому при  k = const длина шага постепенно уменьшается. Вблизи оптимума длина вектора градиента стремится к нулю. Длина вектора или норма в n -мерном евклидовом пространстве определяется по формуле

, где n  число переменных.

Варианты остановки процесса поиска оптимума:

C практической точки зрения удобней пользоваться 3-им критерием остановки (поскольку представляют интерес значения параметров проектирования), однако для определения близости точки экстремума нужно ориентироваться на 2-й критерий. Для остановки вычислительного процесса можно использовать несколько критериев.

Рассмотрим пример. Найти минимум целевой функции F (X ) = (x 1  2) 2 + (x 2  4) 2 . Точное решение задачи X*= (2,0;4,0). Выражения для частных производных

,
.

Выбираем шаг  k = 0,1. Осуществим поиск из начальной точки X 1 = . Решение представим в виде таблицы.

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

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

F(X k+1 )=F(X k   k S k )=min F( k ), S k =  F(X);

 k >0

.

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

Пример. min F (x 1 , x 2 ) = 2x 1 2 + 4x 2 3 – 3. Тогда  F (X )= [ 4x 1 ; 12x 2 2 ]. Пусть точка X k = , следовательно  F (X )= [ 8; 12], F (X k   S k ) =

2(2  8 ) 2 + 4(1  12 ) 3  3. Необходимо найти , доставляющее минимум данной функции.

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

Начальный шаг . Пусть   константа остановки. Выбрать начальную точку X 1 , положить k = 1 и перейти к основному шагу.

Основной шаг . Если || gradF (X )||< , то закончить поиск, в противном случае определить  F (X k ) и найти  k  оптимальное решение задачи минимизации F (X k   k S k ) при  k  0. Положить X k +1 = X k   k S k , присвоить k =

k + 1 и повторить основной шаг.

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

Метод дихотомии (бисекции) Начальный шаг. Выбирают константу различимости  и конечную длину интервала неопределенности l . Величина  должна быть по возможности меньшей, однако позволяющей различать значения функции F ( ) и F ( ) . Пусть [ a 1 , b 1 ]  начальный интервал неопределенности. Положить k =

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

k-я итерация.

Шаг 1. Если b k  a k  l , то вычисления заканчиваются. Решение x * = (a k + b k )/2. В противном случае

,
.

Шаг 2. Если F ( k ) < F ( k ), положить a k +1 = a k ; b k +1 =  k . В противном случае a k +1 =  k и b k +1 = b k . Присвоить k = k + 1 и перейти к шагу 1.

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

 = 0,618034 от конца интервала.

Алгоритм метода золотого сечения

Начальный шаг. Выбрать допустимую конечную длину интервала неопределенности l > 0. Пусть [ a 1 , b 1 ]  начальный интервал неопределенности. Положить  1 = a 1 +(1   )(b 1  a 1 ) и  1 = a 1 +  (b 1  a 1 ) , где  = 0,618 . Вычислить F ( 1 ) и F ( 1 ) , положить k = 1 и перейти к основному этапу.

Шаг 1. Если b k  a k  l , то вычисления заканчиваются x * = (a k + b k )/ 2. В противном случае если F ( k ) > F ( k ) , то перейти к шагу 2; если F ( k )  F ( k ) , перейти к шагу 3.

Шаг 2. Положить a k +1 =  k , b k +1 = b k ,  k +1 =  k ,  k +1 = a k +1 +  (b k +1 – a k +1 ). Вычислить F ( k +1 ), перейти к шагу 4.

Шаг 3. Положить a k +1 = a k , b k +1 =  k ,  k +1 =  k ,  k +1 = a k +1 + (1   )(b k +1 – a k +1 ). Вычислить F ( k +1 ).

Шаг 4. Присвоить k = k + 1, перейти к шагу 1.

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

Метод сопряженных градиентов (Флетчера-Ривса). В этом методе выбор направления движения на k + 1 шаге учитывает изменение направления на k шаге. Вектор направления спуска является линейной комбинацией направления антиградиента и предыдущего направления поиска. В этом случае при минимизации овражных функций (с узкими длинными впадинами) поиск идет не перпендикулярно оврагу, а вдоль него, что позволяет быстрее прийти к минимуму. Координаты точки при поиске экстремума методом сопряженных градиентов рассчитываются по выражению X k +1 = X k   V k +1 , где V k +1 – вектор, рассчитываемый по следующему выражению:

.

На первой итерации обычно полагается V = 0 и выполняется поиск по антиградиенту, как в методе наискорейшего спуска. Затем направление движения отклоняется от направления антиградиента тем больше, чем значительнее менялась длина вектора градиента на последней итерации. После n шагов для коррекции работы алгоритма делают обычный шаг по антиградиенту.

Алгоритм метода сопряженных градиентов

Шаг 1. Ввести начальную точку Х 0 , точность  , размерность n .

Шаг 2. Положить k = 1.

Шаг 3. Положить вектор V k = 0.

Шаг 4. Вычислить grad F (X k ).

Шаг 5. Вычислить вектор V k +1.

Шаг 6. Выполнить одномерный поиск по вектору V k +1.

Шаг 7. Если k < n , положить k = k + 1 и перейти к шагу 4, иначе к шагу 8.

Шаг 8. Если длина вектора V меньше , окончить поиск, иначе  перейти к шагу 2.

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

Недостатки градиентных методов

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

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

1. Понятие градиентных методов. Необходимым условием существова­ния экстремума непрерывной дифференцируемой функции яв­ляются условия вида

где – аргументы функции. Более компактно это условие можно записать в форме

(2.4.1)

где – обозначение градиента функции в заданной точке.

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

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

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

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

т. е. после r - шагов - целевая функция уже не будет увеличиваться (уменьшать­ся) при любом дальнейшем изменении ее аргументов;. Последнее означает достижение точки с координатами для которой можно написать, что

	(2.4.2)
	(2.4.3)

где – экстремальное значение целевой функции.

Для решения (2.4.1) в общем случае может быть применена следующая процедура. Запишем значение координат целевой функции в виде

где – некоторый коэффициент (скаляр), не равный нулю.

В точке экстремума так как

Решение уравнения (2.4.1) этим способом возможно, если выполняется условие сходимости итерационного процесса для любого начального значения.

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

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

Вычисление градиента. Так как в результате оптимизации находятся координаты точки экстремума, для которых справедливо соотношение:

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

	(2.4.5)

где – малое изменение координаты

Если предположить, что точка определения градиента находится посередине

отрезка то

Выбор (2.4.5) или (2.4.6) зависит от крутизны функции на участке - Ах;; если крутизна не велика, предпочтение следует отдать (2.4.5), так как вычислений здесь меньше; в противном случае более точные результаты дает вычисление по (2.4.4). Повышение точности определения градиента возможно также за счет усреднения случайных отклонений.

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

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

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

Направление градиента в точке совпадает с направлением касательной. При поиске минимальной экстремальной точки изменение координаты х при движении по градиенту можно записать в виде:

Рис.2.4.2 Схема вычисления шага по методу Ньютона – Рафсона.

Подставив (2.4.7) в (2.4.8), получим:

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

Подставим новое значение в целевую функцию. Если то в точке процедура определения повторяется, в результате чего находится значение:

и т.д. вычисление прекращается, если изменения целевой функции малы, т. е.

где – допустимая погрешность определения целевой функции.

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

Таким образом, оптимальные значения и для поиска минимума и максимума соответственно определяются из решения уравнений:

В (1) и (2) соответственно

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