Градиентный метод с постоянным m. Градиентные методы. Понятие градиента и его вычисление. Разновидности градиентных методов. Применение в искусственных нейронных сетях

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

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-ой производной.

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

Наиболее простой в реализации из всех методов локальной оптимизации. Имеет довольно слабые условия сходимости, но при этом скорость сходимости достаточно мала (линейна). Шаг градиентного метода часто используется как часть других методов оптимизации, например, метод Флетчера - Ривса .

Описание [ | ]

Усовершенствования [ | ]

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

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

Применение в искусственных нейронных сетях [ | ]

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

Ссылки [ | ]

• J. Mathews. Module for Steepest Descent or Gradient Method. (недоступная ссылка)

Литература [ | ]

• Акулич И. Л. Математическое программирование в примерах и задачах. - М. : Высшая школа, 1986. - С. 298-310.
• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация = Practical Optimization. - М. : Мир, 1985.
• Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. - М. : Энергоатомиздат, 1972.
• Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. - М. : МИФИ, 1982.
• Максимов Ю. А. Алгоритмы линейного и дискретного программирования. - М. : МИФИ, 1980.
• Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - М. : Наука, 1970. - С. 575-576.
• С. Ю. Городецкий, В. А. Гришагин. Нелинейное программирование и многоэкстремальная оптимизация. - Нижний Новгород: Издательство Нижегородского Университета, 2007. - С. 357-363.

Как мы уже отметили, задача оптимизации – это задача отыскания таких значений факторов х 1 = х 1* , х 2 = х 2* , …, х k = х k * , при которых функция отклика (у ) достигает экстремального значения у = ext (оптимума).

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

Рассмотрим сущность метода градиента на примере двухфакторной функции отклика y = f(x 1 , х 2 ). На рис. 4.3 в фак­торном пространстве изо­бражены кривые равных значений функции отклика (кривые уровня). Точке с координатами х 1 *, х 2 * соответствует экстремаль­ное значение функции от­клика у ext .

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

Градиент непрерывной однозначной функции y = f (x 1 , х 2) – это вектор, определяемый по направлению градиентом с координатами:

где i, j – единичные векторы в направлении осей координат х 1 и х 2 . Частные производные и характеризуют направление вектора.

Поскольку нам неизвестен вид зависимости y = f (x 1 , х 2), мы не можем найти частные производные , и опреде­лить истинное направление градиента.

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

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

и проверяется ее адекватность.

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

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

где m – положительное число, определяющее величину шага в на­правлении градиента.

Поскольку х 1 0 = 0 и х 2 0 = 0, то .

Определив направление градиента () и выбрав ве­личину шага m , осуществляем опыт на исходном уровне х 1 0 , х 2 0 .

Затем делаем шаг в направлении градиента, т.е. осу­ществляем опыт в точке с координатами . Если значе­ние функции отклика возросло по сравнению с ее значением в исходном уровне, делаем еще шаг в направлении градиен­та, т.е. осуществляем опыт в точке с координатами:

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

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

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

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

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

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

1) исходные уровни факторов (х j 0) следует выбирать воз­можно ближе к точке оптимума, если есть какая-то априор­ная информация о ее положении;

2) интервалы варьирования (Δх j ) надо выбирать такими, чтобы линейная модель наверняка оказалась адекватной. Границей снизу Δх j при этом является минимальное значе­ние интервала варьирования, при котором функция отклика остается значимой;

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

.

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

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

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

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

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

и т.д.

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

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

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

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

Лекция № 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 в сторону точки экстремума х*. Признаком экстремума в подобном случае будет коллинеарность векторов и .