Лекция № 8

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

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

Будем рассматривать задачу максимизации нелинейной дифференцируемой функции f (x ). Суть градиентного поиска точки максимума х * весьма проста: надо взять произвольную точку х 0 и с помощью градиента , вычисленного в этой точке, определить направление, в котором f (х ) возрастает с наибольшей скоростью (рис. 7.4),

а затем, сделав небольшой шаг в найденном направлении, перейти в новую точку x i . Потом снова определить наилучшее направление для перехода в очередную точку х 2 и т. д. На рис. 7.4 поисковая траектория представляет собой ломаную х 0 , x 1 , х 2 ... Таким образом, надо построить последовательность точек х 0 , x 1 , х 2 ,...,x k , ... так, чтобы она сходилась к точке максимума х *, т. е. для точек последовательности выполнялись условия

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

Движение из точки х k в новую точку x k+1 осуществляется по прямой, проходящей через точку х k и имеющей уравнение

(7.29)

где λ k - числовой параметр, от которого зависит величина шага. Как только значение параметра в уравнении (7.29) выбрано: λ k =λ k 0 , так становится определенной очередная точка на поисковой ломаной.

Градиентные методы отличаются друг от друга способом выбора величины шага - значения λ k 0 параметра λ k . Можно, например, двигаться из точки в точку с постоянным шагом λ k = λ, т. е. при любом k

Если при этом окажется, что , то следует возвратиться в точку и уменьшить значение параметра, например до λ /2.

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

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

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

Распространенным является вариант градиентного поиска, называемый методом наискорейшего подъема. Суть его в следующем. После определения градиента в точке х к движение вдоль прямой производится до точки х к+ 1 , в которой достигается максимальное значение функции f (х ) в направлении градиента . Затем в этой точке вновь определяется градиент, и движение совершается по прямой в направлении нового градиента до точки х к+ 2 , в которой достигается максимальное в этом направлении значение f (x ). Движение продолжается до тех пор, пока не будет достигнута точка х *, соответствующая наибольшему значению целевой функции f (x ). На рис. 7.5 приведена схема движения к оптимальной точке х * методом наискорейшего подъема. В данном случае направление градиента в точке х k является касательным к линии уровня поверхности f (х ) в точке х к+ 1 , следовательно, градиент в точкех к+ 1 ортогонален градиенту (сравните с рис. 7.4).

Перемещение из точки х k в точку сопровождается возрастанием функции f (x ) на величину

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

(7.31)

Найдем выражение для производной, дифференцируя равенство (7.30) по как сложную функцию:

Подставляя этот результат в равенство (7.31), получаем

Это равенство имеет простое геометрическое истолкование: градиент в очередной точке х к+ 1 , ортогонален градиенту в предыдущей точке х к .

построены линии уровня этой поверхности. С этой целью уравнение приведено к виду (x 1 -1) 2 +(x 2 -2) 2 =5-0,5f , из которого ясно, что линиями пересечения параболоида с плоскостями, параллельными плоскости x 1 Оx 2 (линиями уровня), являются окружности радиусом . При f =-150, -100, -50 их радиусы равны соответственно , а общий центр находится в точке (1; 2). Находим градиент данной функции:

I шаг . Вычисляем:

На рис. 7.6 с началом в точке х 0 =(5; 10) построен вектор 1/16, указывающий направление наискорейшего возрастания функции в точке х 0 . На этом направлении расположена следующая точка . В этой точке .

Используя условие (7.32), получаем

или 1-4=0, откуда =1/4. Так как , то найденное значение является точкой максимума . Находим x 1 =(5-16/4; 10-32/4)=(1; 2).

II шаг . Начальная точка для второго шага x 1 =(1; 2). Вычисляем =(-4∙1 +4; -4∙2+8)=(0; 0). Следовательно, х 1 =(1; 2) является стационарной точкой. Но поскольку данная функция вогнутая, то в найденной точке (1; 2) достигается глобальный максимум.

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

Рассмотрим задачу выпуклого программирования с линейными ограничениями:

(7.34)

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

Начнем с геометрической иллюстрации процесса решения задачи (рис. 7.7). Пусть начальная точка х 0 расположена внутри допустимой области. Из точки х 0 можно двигаться в направлении градиента , пока f (x ) не достигнет максимума. В нашем случае f (x ) все время возрастает, поэтому остановиться надо в точке х , на граничной прямой. Как видно из рисунка, дальше двигаться в направлении градиента нельзя, так как выйдем из допустимой области. Поэтому надо найти другое направление перемещения, которое, с одной стороны, не выводит из допустимой области, а с другой - обеспечивает наибольшее возрастание f (x ). Такое направление определит вектор , составляющий с вектором наименьший острый угол по сравнению с любым другим вектором, выходящим из точки x i и лежащим в допустимой области. Аналитически такой вектор найдется из условия максимизации скалярного произведения . В данном случае вектор указывающий наивыгоднейшее направление, совпадает с граничной прямой.

Таким образом, на следующем шаге двигаться надо по граничной прямой до тех пор, пока возрастает f (x ); в нашем случае - до точки х 2 . Из рисунка видно, что далее следует перемещаться в направлении вектора , который находится из условия максимизации скалярного произведения , т. е. по граничной прямой. Движение заканчивается в точке х 3 , поскольку в этой точке завершается оптимизационный поиск, ибо в ней функция f (х ) имеет локальный максимум. Ввиду вогнутости в этой точке f (х ) достигает также глобального максимума в допустимой области. Градиент в точке максимума х 3 =х * составляет тупой угол с любым вектором из допустимой области, проходящим через х 3 , поэтому скалярное произведение будет отрицательным для любого допустимого r k , кроме r 3 , направленного по граничной прямой. Для него скалярное произведение =0, так как и взаимно перпендикулярны (граничная прямая касается линии уровня поверхности f (х ), проходящей через точку максимума х *). Это равенство и служит аналитическим признаком того, что в точке х 3 функция f (x ) достигла максимума.

Рассмотрим теперь аналитическое решение задачи (7.33) - (7.35). Если оптимизационный поиск начинается с точки, лежащей в допустимой области (все ограничения задачи выполняются как строгие неравенства), то перемещаться следует по направлению градиента так, как установлено выше. Однако теперь выбор λ k в уравнении (7.29) усложняется требованием, чтобы очередная точка оставалась в допустимой области. Это означает, что ее координаты должны удовлетворять ограничениям (7.34), (7.35), т. е. должны выполняться неравенства:

(7.36)

Решая систему линейных неравенств (7.36), находим отрезок допустимых значений параметра λ k , при которых точка х k +1 будет принадлежать допустимой области.

Значение λ k * , определяемое в результате решения уравнения (7.32):

При котором f (x ) имеет локальный максимум по λ k в направлении, должно принадлежать отрезку . Если же найденное значение λ k выходит за пределы указанного отрезка, то в качестве λ k * принимается . В этом случае очередная точка поисковой траектории оказывается на граничной гиперплоскости, соответствующей тому неравенству системы (7.36), по которому при решении системы получена правая конечная точка . отрезка допустимых значений параметра λ k .

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

при ограничениях

для тех t , при которых

где .

В результате решения задачи (7.37) - (7.40) будет найден вектор , составляющий с градиентом наименьший острый угол.

Условие (7.39) говорит о том, что точка принадлежит границе допустимой области, а условие (7.38) означает, что перемещение из по вектору будет направлено внутрь допустимой области или по ее границе. Условие нормализации (7.40) необходимо для ограничения величины , так как в противном случае значение целевой функции (7.37) можно сделать сколь угодно большим Известны различные формы условий нормализации, и в зависимости от этого задача (7.37) - (7.40) может быть линейной или нелинейной.

После определения направления находится значение λ k * для следующей точки поисковой траектории. При этом используется необходимое условие экстремума в форме, аналогичной уравнению (7.32), но с заменой на вектор , т. е.

(7.41)

Оптимизационный поиск прекращается, когда достигнута точка x k * , в которой .

Пример 7.5. Максимизировать функцию при ограничениях

Решение. Для наглядного представления процесса оптимизации будем сопровождать его графической иллюстрацией. На рис 7.8 изображено несколько линий уровня данной поверхности и допустимая область ОАВС, в которой следует найти точку х *, доставляющую максимум данной функции (см. пример 7 4).

Начнем оптимизационный поиск, например с точки х 0 =(4, 2,5), лежащей на граничной прямой АВ x 1 +4x 2 =14. При этом f (х 0)=4,55.

Найдем значение градиента

в точке x 0 . Кроме того, и по рисунку видно, что через допустимую область проходят линии уровня с пометками более высокими, чем f (x 0)=4,55. Словом, надо искать направление r 0 =(r 01 , r 02) перемещения в следующую точку x 1 более близкую к оптимальной. С этой целью решаем задачу (7.37) - (7.40) максимизации функции при ограничениях

Поскольку точка х 0 располагается только на одной (первой) граничной прямой (i =1) x 1 +4x 2 =14, то условие (7.38) записывается в форме равенства.

Система ограничительных уравнений этой задачи имеет только два решения (-0,9700; 0,2425) и (0,9700;-0,2425) Непосредственной подстановкой их в функцию T 0 устанавливаем, что максимум Т 0 отличен от нуля и достигается при решении (-0,9700; 0,2425) Таким образом, перемещаться из х 0 нужно по направлению вектора r 0 =(0,9700; 0,2425), т е по граничной прямой ВА.

Для определения координат следующей точки x 1 =(x 11 ; x 12)

(7.42)

необходимо найти значение параметра , при котором функция f (x ) в точке x

откуда =2,0618. При этом =-0,3999<0. Значит,=2,0618. По формуле (7.42) находим координаты новой точки х 1 (2; 3).

Если продолжить оптимизационный поиск, то при решении очередной вспомогательной задачи (7.37)- (7.40) будет установлено, что Т 1 =, а это говорит о том, что точка x 1 является точкой максимума х* целевой функции в допустимой области. Это же видно и из рисунка в точке x 1 одна из линий уровня касается границы допустимой области. Следовательно, точка x 1 является точкой максимума х*. При этом f max =f (x *)=5,4.

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

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

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

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

Вычисляем координаты х (1) :

Для вычисления координат точки х (2) находим проекции градиента в точке х (1) : , тогда

и т.д.

Данная последовательность также сходится.

Шаговый градиентный метод

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

Пусть дана сепарабельная функция и начальная точка . Зададимся постоянным шагом по координате х 1 , пусть Dх 1 =0,2. Шаг по координате х 2 находим из соотношения градиентов и шагов.

Градиентные методы оптимизации

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

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

Если R (л ь х 2) непрерывна в области D, то вокруг оптимальной точки M°(xi°, х г °) можно провести в данной плоскости замкнутую линию, вдоль ко­торой значение R = const. Таких линий, называемых линиями равных уровней, вокруг оптимальной точки можно провести множество (в зависимости от шага

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

Понятие градиента широко используется в инженерных расчетах при на­хождении экстремумов нелинейных функций. Градиентные методы относятся к численным методам поискового типа. Они универсальны и особенно эффек­тивны в случаях поиска экстремумов нелинейных функций с ограничениями, а также когда аналитическая функция неизвестна совсем. Сущность этих мето­дов заключается в определении значений переменных, обеспечивающих экс­тремум функции цели, путем движения по градиенту (при поиске max) или в противоположном направлении (min). Различные градиентные методы отли­чаются один от другого способом определения движения к оптимуму. Суть заключается в том, что если линии равных уровней R{xu x i) характеризуют графически зависимость R(x\jc?), то поиск оптимальной точки можно вести по-разному. Например, изобразить сетку на плоскости х\, хг с указанием зна­чений R в узлах сетки (рис. 2.13).

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

Численные методы

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

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

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

Выбор узловых точек, проведение экспериментов при определен­ных значениях (уровнях) независимых переменных (при непра­вильном выборе шага изменения фактора либо «пропустим» ха­рактерную особенность изучаемого процесса, либо удлиним про­цедуру и повысим трудоемкость поиска закономерности);

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

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

Выполнение требований заданной точности к выбору приближаю­щей функции.

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

Линейная комбинация степенных функций (ряд Тейлора, много­члены Лагранжа, Ньютона и др.);

Комбинация функций соз пх, ш их (ряды Фурье);

Многочлен, образуемый функциями ехр (-а, г).

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

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

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

Рис. 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;

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) для каждой точки траектории движения вдоль градиента, начиная с исходной.