Градиентный метод с постоянным m. Градиентный метод
Лекция 6.
Градиентные методы решения задач нелинейного программирования.
Вопросы: 1. Общая характеристика методов.
2. Метод градиента.
3. Метод наискорейшего спуска.
4. Метод Франка-Фулфа.
5. Метод штрафных функций.
1. Общая характеристика методов.
Градиентные методы представляют собой приближенные (итерационные) методы решения задачи нелинейного программирования и позволяют решить практически любую задачу. Однако при этом определяется локальный экстремум. Поэтому целесообразно применять эти методы для решения задач выпуклого программирования, в которых каждый локальный экстремум является и глобальным. Процесс решения задачи состоит в том, что, начиная с некоторой точки х (начальной), осуществляется последовательный переход в направлении gradF(x), если определяется точка максимума, и –gradF(x) (антиградиента), если определяется точка минимума, до точки, являющейся решением задачи. При этом эта точка может оказаться как внутри области допустимых значений, так и на ее границе.
Градиентные методы можно разделить на два класса (группы). К первой группе относятся методы, в которых все исследуемые точки принадлежат допустимой области. К таким методам относятся: метод градиента, наискорейшего спуска, Франка-Вулфа и др. Ко второй группе относятся методы, в которых исследуемые точки могут и не принадлежать допустимой области. Общим из таких методов является метод штрафных функций. Все методы штрафных функций отличаются друг от друга способом определения «штрафа».
Основным понятием, используемым во всех градиентных методах, является понятие градиента функции, как направления наискорейшего возрастания функции.
При определении решения градиентными методами итерационный процесс продолжается до тех пор, пока:
Либо grad F(x*) = 0, (точное решение);
где
- две последовательные точки,
-
малое число, характеризующее точность
решения.
2. Метод градиента.
Представим человека, стоящего на склоне оврага, которому необходимо спуститься вниз (на дно). Наиболее естественным, кажется, направление в сторону наибольшей крутизны спуска, т.е. направление (-grad F(x)). Получаемая при этом стратегия, называемая градиентным методом , представляет собой последовательность шагов, каждый из которых содержит две операции:
а) определение направления наибольшей крутизны спуска (подъема);
б) перемещение в выбранном направлении на некоторый шаг.
Правильный выбор шага имеет существенное значение. Чем шаг меньше, тем точнее результат, но больше вычислений. Различные модификации градиентного метода и состоят в использовании различных способов определения шага. Если на каком-либо шаге значение F(x) не уменьшилось, это означает, что точку минимума «проскочили», в этом случае необходимо вернуться к предыдущей точке и уменьшить шаг, например, вдвое.
Схема решения.
принадлежащей допустимой области
3. Выбор шага h.
x (k+1)
= x (k)
«-» - если min.
5. Определение F(x (k +1)) и:
Если
,
решение найдено;
Замечание. Если grad F(x (k)) = 0, то решение будет точным.
Пример.
F(x) = -6x 1
+ 2x 1 2
– 2x 1 x 2
+ 2x 2 2
min,
x 1 +x 2
2,x 1
0, x 2
0,
= 0,1.
3. Метод наискорейшего спуска.
В отличие от метода градиента, в котором градиент определяют на каждом шаге, в методе наискорейшего спуска градиент находят в начальной точке и движение в найденном направлении продолжают одинаковыми шагами до тех пор, пока значение функции уменьшается (увеличивается). Если на каком-либо шаге F(x) возросло (уменьшилось), то движение в данном направлении прекращается, последний шаг снимается полностью или наполовину и вычисляется новое значение градиента и новое направление.
Схема решения.
1. Определение х 0 = (х 1 ,x 2 ,…,x n),
принадлежащей допустимой области,
и F(x 0), k = 0.
2. Определение grad F(x 0) или –gradF(x 0).
3. Выбор шага h.
4. Определение следующей точки по формуле
x (k+1)
= x (k)
h grad F(x (k)),
«+» - если max,
«-» - если min.
5. Определение F(x (k +1)) и:
Если
,
решение найдено;
Если нет:
а) при поиске min: - если F(x (k +1))
Если F(x (k +1))
>F(x (k))
– переход к п. 2; б) при поиске max: -
еслиF(x (k +1))
>F(x (k))
– переход к п. 4; Если F(x (k +1))
Замечания:
1. Если grad F(x (k))
= 0, то решение будет точным. 2. Преимуществом метода
наискорейшего спуска является его
простота и сокращение расчетов, так
как grad F(x) вычисляется не во всех точках,
что важно для задач большой
размерности. 3. Недостатком является то,
что шаги должны быть малыми, чтобы не пропустить точку оптимума. Пример.
F(x) = 3x 1
– 0,2x 1 2
+ x 2 -
0,2x 2 2
x 1
+ x 2
x 1
+ 2x 2
4. Метод Франка-Вулфа.
Метод используется для оптимизации
нелинейной целевой функции при линейных
ограничениях. В окрестности исследуемой
точки нелинейная целевая функция
заменяется линейной функцией и задача
сводится к последовательному решению
задач линейного программирования. Схема решения.
1. Определение х 0 = (х 1 ,x 2 ,…,x n),
принадлежащей допустимой области, и
F(x 0), k = 0. 2. Определение grad F(x (k)). 3. Строят функцию 4. Определение max(min)f(x) при
исходных ограничениях. Пусть это будет
точка z (k) . 5. Определение шага вычислений x (k +1) =x (k) +
6. Определение F(x (k +1))
и проверяют необходимость дальнейших
вычислений: Если
Если нет, то переход к п. 2. Пример.
F(x) = 4x 1
+ 10x 2
–x 1 2
–x 2 2
x 1
+x 2 x 2
5. Метод штрафных функций.
Пусть необходимо найти F(x 1 ,x 2 ,…,x n)
g i
(x 1 ,
x 2 ,…,x n)
Функции F и g i –
выпуклые или вогнутые. Идея метода штрафных функций
заключается в поиске оптимального
значения новой целевой функции Q(x) = F(x)
+ H(x), которая является суммой исходной
целевой функции и некоторой функции
H(x), определяемой системой ограничений
и называемой штрафной функцией. Штрафные
функции строят таким образом, чтобы
обеспечить либо быстрое возвращение в
допустимую область, либо невозможность
выходы из нее. Метод штрафных функций
сводит задачу на условный экстремум к
решению последовательности задач на
безусловный экстремум, что проще.
Существует множество способов построения
штрафной функции. Наиболее часто она
имеет вид: H(x) =
где
Примечание
: Чем меньше
Начинают решение с малых
Используя штрафную функцию,
последовательно переходят от одной
точки к другой до тех пор, пока не получат
приемлемое решение. Схема решения.
1. Определение начальную точку х 0 = (х 1 ,x 2 ,…,x n),
F(x 0) и k = 0. 2. Выбирают шаг вычислений h. 3. Определяют частные производные
4. Определяют координаты следующей точки
по формуле: x j (k +1) 5. Если x (k +1) а) если
б) если grad F(x (k +1))
= 0, то найдено точное решение. Если x (k +1) Пример.
F(x) = – x 1 2
– x 2 2
(x 1
-5) 2 +(x 2
-5) 2 При оптимизации методом градиента оптимум исследуемого объекта ищут в направлении наиболее быстрого возрастания (убывания) выходной переменной, т.е. в направлении градиента. Но прежде чем сделать шаг в направлении градиента, необходимо его рассчитать. Градиент можно рассчитать либо по имеющейся модели моделирование динамический градиентный полиномиальный где - частная производная по i-му фактору; i, j, k - единичные векторы в направлении координатных осей факторного пространства, либо по результатам n пробных движений в направлении координатных осей. Если математическая модель статистического процесса имеет вид линейного полинома, коэффициенты регрессии b i которого являются частными производными разложения функции y = f(X) в ряд Тейлора по степеням x i , то оптимум ищут в направлении градиента с некоторым шагом h i: пкфв н(Ч)= и 1 р 1 +и 2 р 2 +…+и т р т Направление корректируют после каждого шага. Метод градиента вместе с его многочисленными модификациями является распространенным и эффективным методом поиска оптимума исследуемых объектов. Рассмотрим одну из модификаций метода градиента - метод крутого восхождения. Метод крутого восхождения, или иначе метод Бокса-Уилсона, объединяет в себе достоинства трех методов - метода Гаусса-Зейделя, метода градиентов и метода полного (или дробного) факторного экспериментов, как средства получения линейной математической модели. Задача метода крутого восхождения заключается в том, чтобы шаговое движение осуществлять в направлении наискорейшего возрастания (или убывания) выходной переменной, то есть по grad y(X). В отличии от метода градиентов, направление корректируется не после каждого следующего шага, а при достижении в некоторой точке на данном направлении частного экстремума целевой функции, как это делается в методе Гаусса-Зейделя. В точке частного экстремума ставится новый факторный эксперимент, определяется математическая модель и вновь осуществляется крутое восхождение. В процессе движения к оптимуму указанным методом регулярно проводиться статистический анализ промежуточных результатов поиска. Поиск прекращается, когда квадратичные эффекты в уравнении регрессии становятся значимыми. Это означает, что достигнута область оптимума. Опишем принцип использования градиентных методов на примере функции двух переменных при наличии двух дополнительных условий: Этот принцип (без изменения) можно применить при любом числе переменных, а также дополнительных условий. Рассмотрим плоскость x 1 , x 2 (Рис. 1). Согласно формуле (8) каждой точке соответствует некоторое значение F. На Рис.1 линии F = const, принадлежащие этой плоскости, представлены замкнутыми кривыми, окружающими точку M * , в которой F минимально. Пусть в начальный момент значения x 1 и x 2 соответствуют точке M 0 . Цикл расчета начинается с серии пробных шагов. Сначала величине x 1 дается небольшое приращение; в это время значение x 2 неизменно. Затем определяется полученное при этом приращение величины F, которое можно считать пропорциональным значению частной производной (если величина всегда одна и та же). Определение частных производных (10) и (11) означает, что найден вектор с координатами и, который называется градиентом величины F и обозначается так: Известно, что направление этого вектора совпадает с направлением наиболее крутого возрастания величины F. Противоположное ему направление - это «наискорейший спуск», другими словами, наиболее крутое убывание величины F. После нахождения составляющих градиента пробные движения прекращаются и осуществляются рабочие шаги в направлении, противоположном направлению градиента, причем величина шага тем больше, чем больше абсолютная величина вектора grad F. Эти условия осуществляются, если величины рабочих шагов и пропорциональны полученным ранее значениям частных производных: где б - положительная константа. После каждого рабочего шага оценивается приращение величины F. Если оно оказывается отрицательным, то движение происходит в правильном направлении и нужно двигаться в том же направлении M 0 M 1 дальше. Если же в точке M 1 результат измерения показывает, что, то рабочие движения прекращаются и начинается новая серия пробных движений. При этом определяется градиент gradF в новой точке M 1 , затем рабочее движение продолжается по новому найденному направлению наискорейшего спуска, т. е. по линии M 1 M 2 , и т.д. Этот метод называется методом наискорейшего спуска/крутого восхождения. Когда система находится вблизи минимума, показателем чего является малое значение величины происходит переключение на более «осторожный» метод поиска, так называемый метод градиента. От метода наискорейшего спуска он отличается тем, что после определения градиента gradF делается лишь один рабочий шаг, а затем в новой точке опять начинается серия пробных движений. Такой метод поиска обеспечивает более точное установление минимума по сравнению с методом наискорейшего спуска, между тем как последний позволяет быстрее приблизиться к минимуму. Если в процессе поиска точка М доходит до границы допустимой области и хотя бы одна из величин М 1 , М 2 меняет знак, метод меняется и точка М начинает двигаться вдоль границы области. Эффективность метода крутого восхождения зависит от выбора масштаба переменных и вида поверхности отклика. Поверхность со сферическими контурами обеспечивает быстрое стягивание к оптимуму. К недостаткам метода крутого восхождения следует отнести: 1. Ограниченность экстраполяции. Двигаясь вдоль градиента, мы основываемся на экстраполяции частных производных целевой функции по соответствующим переменным. Однако форма поверхности отклика может изменяться и необходимо изменять направление поиска. Другими словами, движение на плоскости не может быть продолжительным. 2. Трудность поиска глобального оптимума. Метод применим для отыскания только локальных оптимумов. 1.
Понятие градиентных методов.
Необходимым условием существования экстремума непрерывной дифференцируемой функции являются условия вида где – аргументы функции. Более компактно это условие можно записать в форме где – обозначение градиента функции в заданной точке. Методы оптимизации, использующие при определении экстремума целевой функции градиент, называются градиентными.
Их широко применяют в системах оптимального адаптивного управления установившимися состояниями, в которых производится поиск оптимального (в смысле выбранного критерия) установившегося состояния системы при изменении ее параметров, структуры или внешних воздействий. Уравнение (2.4.1) в общем случае нелинейно. Непосредственное решение его либо невозможно, либо весьма сложно. Нахождение решений такого рода уравнений возможно путем организации специальной процедуры поиска точки экстремума, основанной на использовании различного рода рекуррентных формул. Процедура поиска строится в форме многошагового процесса, при котором каждый последующий шаг приводит к увеличению или уменьшению целевой функции, т. е. выполняются условия в случае поиска максимума и минимума соответственно: Через n
и n–
1 обозначены номера шагов, а через и – векторы, соответствующие значениям аргументов целевой функции на n
-м и (п–
1)-м шагах. После r-го шага можно получить т. е. после r - шагов - целевая функция уже не будет увеличиваться (уменьшаться) при любом дальнейшем изменении ее аргументов;. Последнее означает достижение точки с координатами для которой можно написать, что где – экстремальное значение целевой функции. Для решения (2.4.1) в общем случае может быть применена следующая процедура. Запишем значение координат целевой функции в виде где – некоторый коэффициент (скаляр), не равный нулю. В точке экстремума так как Решение уравнения (2.4.1) этим способом возможно, если выполняется условие сходимости итерационного процесса для любого начального значения. Методы определения , основанные на решении уравнения (2.2.), отличаются друг от друга выбором , т. е. выбором шага изменения целевой функции в процессе поиска экстремума. Этот шаг может быть постоянным 2. Метод наискорейшего спуска
.Идея метода наискорейшего спуска состоит в том, что поиск экстремума должен производиться в направлении наибольшего изменения градиента или антиградиента, так как это путь – наикратчайший для достижения экстремальной точки. При его реализации, в первую очередь, необходимо вычислить градиент в данной точке и выбрать значение шага. Вычисление градиента.
Так как в результате оптимизации находятся координаты точки экстремума, для которых справедливо соотношение: то вычислительную процедуру определения градиента можно заменить процедурой определения составляющих градиентов в дискретных точках пространства целевой функции где – малое изменение координаты Если предположить, что точка определения градиента находится посередине отрезка то Выбор (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) для каждой точки траектории движения вдоль градиента, начиная с исходной. Вектор-градиент направлен в сторону наискорейшего возрастания функции в данной точке. Вектор, противоположный градиенту -grad(/(x)), называется антиградиентом и направлен в сторону наискорейшего убывания функции. В точке минимума градиент функции равен нулю. На свойствах градиента основаны методы первого порядка, называемые также градиентным. Если нет дополнительной информации, то из начальной точки х (0 > лучше перейти в точку х (1) , лежащую в направлении антиградиента - наискорейшего убывания функции. Выбирая в качестве направления спуска антиградиент -grad(/(x (^)) в точке х (к
получим итерационный процесс вида В координатной форме этот процесс записывается следующим образом: В качестве критерия останова итерационного процесса можно использовать либо условие (10.2), либо выполнение условия малости градиента Возможен и комбинированный критерий, состоящий в одновременном выполнении указанных условий. Градиентные методы отличаются друг от друга способами выбора величины шага а
В методе с постоянным шагом для всех итераций выбирается некоторая постоянная величина шага. Достаточно малый шаг а^
обеспечивает убывание функции, т.е. выполнение неравенства Однако это может привести к необходимости проводить достаточно большое количество итераций для достижения точки минимума. С другой стороны, слишком большой шаг может вызвать рост функции либо привести к колебаниям около точки минимума. Требуется дополнительная информация для выбора величины шага, поэтому методы с постоянным шагом применяются на практике редко. Более надежны и экономичны (в смысле количества итераций) градиентные методы с переменным шагом, когда в зависимости от полученного приближения величина шага некоторым образом меняется. В качестве примера такого метода рассмотрим метод наискорейшего спуска. В этом методе на каждой итерации величина шага я* выбирается из условия минимума функции /(х) в направлении спуска, т.е. Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции /(х) убывает. Поэтому на каждой итерации необходимо решать задачу одномерной минимизации по я функции ф(я) =/(х (/г) - - agrad^x^))). Алгоритм метода наискорейшего спуска состоит в следующем. В методе наискорейшего спуска направление движения из точки х (*) касается линии уровня в точке х (* +1) . Траектория спуска зигзагообразная, и соседние звенья зигзага ортогональны друг другу. Действительно, шаг а^
выбирается путем минимизации по а
функции (а
). Необходимое условие минимума функции - = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках: Задачу минимизации функции ф(я) можно свести к задаче вычисления корня функции одной переменной g(a) =
Градиентные методы сходятся к минимуму со скоростью геометрической прогрессии для гладких выпуклых функций. У таких функций наибольшее и наименьшее собственные значения матрицы вторых производных (матрицы Гессе) мало отличаются друг от друга, т.е. матрица Н(х) хорошо обусловлена. Однако на практике минимизируемые функции часто имеют плохо обусловленные матрицы вторых производных. Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее, чем в других направлениях. Скорость сходимости градиентных методов существенно зависит также от точности вычислений градиента. Потеря точности, а это обычно происходит в окрестности точек минимума, может вообще нарушить сходимость процесса градиентного спуска. Поэтому градиентные методы зачастую используются в комбинации с другими, более эффективными методами на начальной стадии решения задачи. В этом случае точка х (0) находится далеко от точки минимума, и шаги в направлении антиградиента позволяют достичь существенного убывания функции. Градиентный метод и его разновидности относятся к самым распространенным методам поиска экстремума функций нескольких переменных. Идея градиентного метода заключается в том, чтобы в процессе поиска экстремума (для определенности максимума) двигаться каждый раз в направлении наибольшего возрастания целевой функции. Градиентный метод предполагает вычисление первых производных целевой функции по ее аргументам. Он, как и предыдущие, относится к приближенным методам и позволяет, как правило, не достигнуть точки оптимума, а только приблизиться к ней за конечное число шагов. Рис. 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):
max,
7, x 1
0,
10, x 2
0.
(min – «-»;max– «+»).
(k) (z (k) –x (k)),
где
(k) – шаг, коэффициент, 0 
1.
(k) выбирается так, чтобы значение функции
F(x) было max (min) в точке х (k +1) .
Для этого решают уравнение
и
выбирают наименьший (наибольший) из
корней, но 0 
1.
или grad F(x (k +1))
= 0, то решение найдено;
max,
4, x 1
0,
2, x 2
0.
max(min),
b i , i
=
, x j
0, j =
.
,
-
некоторые положительные Const.
,
тем быстрее находится решение, однако,
точность снижается;
и увеличивают их на последующих шагах.
и
.
.
Допустимой
области, проверяют:
-
решение найдено, если нет – переход к
п. 2.
Допустимой области, задают новое значение
и
переходят к п. 4.
max,
8, x 1
0, x 2
0.
(2.4.1)
(2.4.2)
(2.4.3)
или переменным Во втором случае закон изменения значения шага, в свою очередь, может, быть заранее определен или. зависеть от текущего значения (может быть нелинейным).
(2.4.5)
т. е. чтобы
в целевую функцию. Если то в точке процедура определения повторяется, в результате чего находится значение:
