Методы решения задач дискретной оптимизации.

 

Методы решения задач дискретной оптимизации делятся на следующие группы:

1. Методы отсечения

2. Комбинаторные

3. Приближенные

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

Методы отсечения

 

Рассмотрим целочисленную ЗЛП.

Если p=n, то это задача полностью целочисленная, если нет - то частично целочисленная. Обозначим ЗЦЛП через z, область допустимых решений D_z, оптимальное решение задачи X_z^*.

Обозначим соответственно ЗЛП без условия (*) через P, область дополнитель­ных решений - D, оптимальное решение - X^*. Предположим, что область D - выпуклое ограниченное множество. Тогда D_z представляет собой дискретное множество точек с целочисленными координатами, которые принадлежат D, то есть .

 

ЗЦЛП z и ЗЛП Р характеризуются следующими свойствами:

1) Минимальное значение целевой функции в z всегда больше минимального значения этой же целевой функции в p.

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

2) Если оказывается целочисленным, то оно является оптимальным решением задачи Z,

3) Если не имеет решений Р, то не имеет решений и Z.

 

Основная идея метода отсечения:

1. Решается последовательность задач ЛП .

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

1) Каждое целочисленное решение задачи Z из области D_z ему удовлетворяет.

2) Нецелочисленное решение задачи P_l-1 ему не удовлетворяет (отсекается).

Таким образом в задаче P последовательно добавляются дополнительные ограничения (отсечения), не исключающее целочисленных допустимых точек и отсекающие нецелочисленные решения ЗЛП.

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

 

Алгоритм Гомори для решения полностью целочисленной ЗЛП.

 

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

Дробная часть числа называется разность между числом и его целой частью.

Пример.

Основные шаги алгоритма.

1. Определение оптимальности решения ЗЛП без учета условий целочисленности симплекс-методом.

2. Если полученное решение ЗЛП является целочисленным, то останов, иначе 3.

3. В нецелочисленном оптимальном решении ЗЛП выбирается базисная переменная x_k с наибольшей дробной частью.

,где -базисные переменные; В- множество индексов базисных переменных.

4. Для выбранной переменной составляется дополнительное ограничение. .

S - номер строки окончательной симплекс-таблицы, которой соответствует переменная x_k.

5. Определение решения ЗЛП, получающейся из предыдущей в результате присоединения дополнительного ограничения. При этом дополнительное ограничение добавляется к последней симплекс-таблице. Для этого дополнительное ограничение преобразуется в уравнение:

Затем полученное уравнение умножается на (-1). После добавляются ограничения к последней симплекс-таблице. ЗЛП решается двойственным симплекс-методом.

6. Переход к S2.

Пример.

Пусть в результате решения симплекс-методом окончательная симплекс-таблица имеет вид:

 

хб	Сб	b	-3	-2
x1	x2	x3	x4	x5	x6
x2	-2	7/2			1/2	-1/2
x1	-3	19/2			1/2	1/2
x5
-71/2			-5/2	-1/2

 

Составим дополнительное ограничение:

Дробные части равны между собой. Поэтому дополнительное ограничение составляется для любой переменной (обычно для первой). Составим ограничение для переменной :

 

Добавляем это ограничение симплекс-таблице:

x6		-1			-1	-1
x2								-1/2
x1								½
x5					-1
x4								-1
-35			-2			½

 

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

Оптимальный план (9; 4; 0; 1; 32).

 

ЗЦЛП не имеет решений в следующих случаях:

1) Если не имеет решений ЗЛП, то не имеет решений и ЗЦЛП

2) Если для дробного b_S все a_sj окажутся целыми.

 

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

 

Алгоритм аналогичен предыдущему:

определяется из следующих соображений:

1) Для переменных , которые могут принимать только целочисленные значения:

2) Для переменных , которые могут принимать целочисленные значения:

 

Достоинства метода.

Простота построения.Простая логика.

Возможность использовать стандартного ПО (для двойственного симплекс метода)

Недостатки.

Ограниченность применения – для решения только линейных целочисленных задач.

Низкая сходимость алгоритма.

Основная проблема метода Гомори – увеличение размерности задачи при добавлении дополнительных ограничений.

 

 

Комбинаторные методы решения задач дискретной оптимизации.

 

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

 

Методы ветвей и границ.

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

 

Обобщенный алгоритм МвиГ.

1) Для задачи вида задачи вида будем называть подзадачами.

2) Релаксации задачи (или подзадачи) - это переход к задаче с той же целевой функцией, но с некоторой дополнительной областью D^/, включающей D в качестве подмножества ).

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

3) Ветвление - разбиение допустимой области на непересекающиеся подмножества и получение таким образом новых экстремальных подзадач. При этом подзадачи являются вершинами дерева вариантов.

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

.

5) Верхняя оценка (граница) оптимальности решения - это значение целевой функции, обеспечиваемое некоторым дополнительным решением подзадачи i (для ЗЦП это целочисленное дополнительное решение).

6) Рекорд - это min-ная верхняя оценка в вершинах дерева вариантов.

7) Прозондированные вершины - вершины, в которых дальнейшее ветвление невозможно и нецелесообразно.

 

Рассмотрим частично целочисленную задачу следующего вида:

 

Максимизировать Z = СX

при ограничениях AX = B, ,

х_j - целочисленная переменная при jÎ I,

 

где I - множество индексов целочисленных переменных задачи. Задача записана в векторной форме: С=(с₁…с_n) - вектор-строка коэффициентов целевой функции; X= - вектор столбец переменных задачи; В= - вектор-столбец правых частей; A= - матрица коэффициентов при переменных в системе ограничений.

В качестве первого шага необходимо решить сформулированную задачу ЛП, рассматривая все ее переменные как непрерывные. Получаемая таким образом задача ЛП обозначается через ЛП-1, оптимальное значение ее целевой функции - через Z₁. Пусть в оптимальном решении задачи ЛП-1 некоторые целочисленные переменные принимают дробные значения; тогда оптимальное решение исходной задачи не совпадает с оптимальным решением ЛП-1. В этом случае величина Z₁ представляет собой верхнюю границу оптимального значения Z исходной задачи.

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

1. Выбор целочисленной переменной с наибольшей дробной частью.

2. Приписывание целочисленным переменным приоритетов и ветвление по переменной с наибольшим приоритетом. Важность целочисленной переменной может определяться следующими соображениями:

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

- коэффициент целевой функции при данной переменной превосходит остальные;

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

4. Произвольные правила выбора. Например, можно выбирать переменную с наименьшим номером.

Пусть ветвление происходит по целочисленной переменной х_j, дробное значение которой в оптимальном решении ЛП-1, равно b_j. Далее рассматриваются две новые задачи ЛП, обозначаемые через ЛП-2 и ЛП-3. Они получаются путем введения ограничений и соответственно, где через обозначается наибольшее целое, не превосходящее b_j , через - наименьшее целое, большее . Условия задачи ЛП-2 и ЛП-3 можно записать следующим образом:

 

ЛП-2 ЛП-3

 

Максимизировать Z=СX Максимизировать Z=CX

при ограничениях AX =B, при ограничениях AX =B,

 

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

На следующем шаге необходимо выбрать задачу ЛП-2 или ЛП-3 и произвести ветвление в соответствующей вершине, вводя новое ограничение. Выбор вершины (задачи ЛП) для дальнейшего ветвления осуществляется с помощью специальных правил. Приведем некоторые из них.

1. Использование оптимального значения целевой функции. Для дальнейшего ветвления следует выбирать вершину, соответствующую наибольшему оптимальному значению целевой функции задачи ЛП. Некоторым обоснованием этого правила служит то соображение, что допустимая область задачи ЛП с наибольшим значением Z может содержать и хорошее целочисленное решение. Например, любое целочисленное решение, полученное ветвлением задачи ЛП-2, не может давать значение Z, лучше, чем оптимальное значение Z в задаче ЛП-2.

2. Правило "последним пришел - первым обслужен". Для дальнейшего ветвления выбирается (произвольным образом) задача ЛП, решавшаяся последней.

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

1.Оптимальное решение, соответствующее данной вершине, целочисленно. В этом случае полученное решение допустимо для исходной задачи ЦЛП.

2. Задача ЛП, соответствующая рассматриваемой вершине, не имеет допустимых решений.

3. Оптимальное значение Z соответствующей задачи ЛП не превосходит текущей нижней границы.

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

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

 

 

Начальный шаг решения этой задачи состоит в нахождении решения задачи линейного программирования, получаемой при отбрасывании условия целочисленности x₁ и x₂. Обозначим эту задачу через ЛП-1. Ее оптимальное решение имеет вид x₁=1, x₂=7.5, оптимальное значение целевой функции Z₁=29.5. Поскольку x₂ принимает дробное значение, найденное решение не может быть оптимальным решением исходной целочисленной задачи. Найденное значение Z₁ представляет собой верхнюю границу истинного оптимального целочисленного значения, поскольку при выполнении требования целочисленности x₂ значение Z может лишь уменьшиться.

Следующий шаг метода ветвей и границ состоит в разбиении задачи ЛП-1 на две подзадачи, первая из которых (ЛП-2) образуется в результате добавления к задаче ЛП-1 ограничения , а вторая (ЛП-3) - в результате добавления ограничения :

 

ЛП-2 ЛП-3

 

 

Дерево возможных вариантов представлено на рис. 33. Оптимальное решение задачи ЛП-3 - точка х₁=0.75, х₂=8, где Z₂=29,25. Оптимальное решение задачи ЛП-2 точка х₁=1.2, х₂=7, где Z₃=29,4. Для дальнейшего ветвления выберем задачу ЛП-2, т.к. значение целевой функции в ней больше. К задаче ЛП-2 добавим ограничения , (задача ЛП-4) и (задача ЛП-5). Результаты решения задачи ЛП-4: х₁=1, х₂=7, где Z₄=28. Результаты решения задачи ЛП-5: х₁=2, х₂=5, где Z₅=29.

Таким образом, получены два допустимых (целочисленных) решения исходной задачи целочисленного программирования, причем значение Z₄=29 представляет собой нижнюю границу максимального значения Z для задачи целочисленного программирования. Даже если исходная задача имеет другие целочисленные решения, значение целевой функции в них не может быть больше 29. Таким образом, значение Z₄=29 представляет собой нижнюю границу максимального значения Z для исходной целочисленной задачи. Вершины ЛП-4 и ЛП-5 являются прозондированными (так как в них получено целочисленное решение, а в процессе дальнейшего ветвления оно может лишь ухудшаться). Ветвление вершины ЛП-3 также нецелесообразно в связи с тем, что целевая функция исходной задачи может принимать только целочисленные значения (т.к. все переменные и коэффициенты целочисленны), а при дальнейшем ветвлении ее значения будут увеличиваться (т.е., станут больше 29). Следовательно, оптимальное решение задачи х₁=2, х₂=5, где Z₅=29.

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

 

 

 

 

	X1=0.75 X2=8 Z3=29.254

 

 

 

 

Основные стратегии метода ветвей и границ.

 

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

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

a) Выбирается вершина с минимальной нижней оценкой.

б) Поиск в глубину: всегда выбирается одна из новых, только что полученных подзадач (Last In First Out).

в) Поиск в ширину: стратегия FIFO.

2. Выбор нецелочисленной переменной, по которой осуществляется ветвление и которая определяет дополнительные ограничения:

1) Выбирается переменная с максимальной дробной частью

2) Переменным приписываются приоритеты и ветвление осуществляется по переменной с максимальным приоритетом. Выбор приоритета может осуществляться следующими соображениями:

a) Коэффициент целевой функции при данной переменной больше остальных

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

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

4) Переменная для ветвления выбирается произвольным образом, например, переменная с минимальным номером.

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

4. Вычисление верхних границ.

а) Верхние границы специально не вычисляются, а определяются в процессе решения при получении целочисленного результата.

б) Верхние границы вычисляются перед началом работы МВГ с помощью какого-либо эвристического алгоритма.

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

б) и в) требуют дополнительных вычислительных затрат, но позволяет более эффективно сократить перебор.

Четких рекомендаций по выбору стратегии в МВГ нет, он зависит от конкретных условий решаемой задачи.

 

Нелинейная оптимизация.

 

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

(1)

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

ЗНП без ограничений.

(2) - задача безусловной оптимизации.

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

. (3)

Область допустимых решений в ЗПН может быть выпуклой или невыпуклой.

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

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

Условия:

(для выпуклой функции)

(для вогнутой функции) или

 

Условия оптимальности для ЗНП.

1. Условие оптимальности для задачи безусловного оптимизации функции одной переменной:

Необходимое условие:

.

Достаточное условие:

.

Больше нуля - для минимума, меньше - для максимума.

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

2. Условие оптимальности для задачи оптимизации функции одной переменной при дополнительном условии неотрицательности этой переменной .

Необходимое условие .

Достаточное условие .

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

Необходимое условие .

Достаточное условие: в точке X* матрица вторых производных (матрица Гессе) должна быть положительно определена (для минимума) или отрицательно (для максимума).

 

Условие минимума , - для отрицательно определенной матрицы.

4. Если к задаче (3) добавить условия неотрицательности всех переменных , то необходимое условие экстремума:

для минимума и меньше нуля - для максимума;

.

5. Условие оптимальности для задачи на условный экстремум.

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

, где - произвольные действительные числа. Затем находятся частные производные и , и рассматривается система n+m уравнений с n+m неизвестными, в которых каждая производная приравнивается нулю.

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

6. Условие оптимальности для задачи выпуклого программирования.

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

.

Определение. Множество дополнительных решений задачи ЗВП удовлетворяет условиям регулярности, если для любой i . Каждый локальный минимум или максимум ЗВП является и глобальным.

Для учета ограничений ЗВП осуществляется переход к задаче без этих ограничений путем введения штрафа за их нарушение. Для этого на множестве вводится штрафная функция Лагранжа:

, где y_i называются штрафными множителями Лагранжа.

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

В терминах функции Лагранжа исходную задачу можно записать:

.

Задачу называется двойственной задачей к исходной задаче.

Точка (X*,Y*) называется седловой точкой функции Лагранжа, если выполняется следующее условие:

или

Теорема Куна-Таккера.

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

 

Дифференциальный вариант теоремы Куна-Таккера (необходимое и достаточное условие экстремума для ЗВП).

Для того, чтобы пара (X*,Y*) была седловой точкой функции Лагранжа, необходимо и достаточно выполнение следующих условий:

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

Пример:

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

а) Составим функцию Лагранжа

.

Т. е. X₁*=(2,1) не является решением, а X₂*=(1,1) - является.

 

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

 

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

1. Учет прямых ограничений

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

, где n - число варьируемых параметров, на которые наложены прямые ограничения. Z_i - новые варьируемые параметры.

Тогда задача с прямыми ограничениями и целевой функцией f(x) сводится к задаче безусловной оптимизации следующего вида:

, где .

Примеры:

1) тогда может быть использована замена переменной .

2) , тогда

3)

 

2. Учет функциональных ограничений.

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

Существует два подхода к построению штрафных функций:

1. Методы внутренних штрафных функций (барьерных функций).

2. Методы вешних штрафных функций.

2.1.Методы внутренних штрафных функций.

Эти методы арактеризуются следующими функциями штрафа:

(1)

(2)

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

В случае 2 выбирается таким образом, чтобы его значения стремилось к нулю при .

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

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

2.2. Метод внешних штрафных функций.

Функции штрафа при этом может иметь следующий вид:

В первом случае параметр a одинаков на всех итерациях.

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

Таким образом, если ограничение не нарушается, т.е. , то à H(X)=0.

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

 

Алгоритмы безусловной оптимизации.

 

Рассмотрим задачу безусловной оптимизации вида

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

,

где k - номер итерации, H^К - направление движения на k-й итерации, - величина шага в этом направлении. При этом:

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

В зависимости от способа выбора направления поиска h методы безусловной оптимизации делятся на методы 0-го, 1-го и 2-го порядка.

а) Методы 0-го порядка - методы, в которых для определения направления поиска используются только значения целевой функции. Производные в данном случае не вычисляются.

Эти методы также называют поисковыми методами оптимизации. К ним относятся методы переменного многогранника и различные методы покоординатного поиска.

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

б) Методы первого порядка - методы, в которых для определения направления поиска используются 1-е производные целевой функции по параметру. Эти методы называют также градиентными.

в) Методы 2-го порядка - это методы, в которых для определения направления поиска используются 2-е производные целевой функции. К этому классу относят метод Ньютона и его модификации.

Важной характеристикой методов является их скорость сходимости. Скорость сходимости линейна:

, где X * - точка минимума.

Скорость сходимости сверхлинейна, если при .

Скорость сходимости квадратична, если

Точность результата может оцениваться величиной , где – решение задачи.

Рассмотрим методы 1-го и 2-го порядка. Для формирования правила перехода из одной точки траектории поиска в другую воспользуемся аппроксимацией целевой функции в окрестности точки Х^К с использованием формулы Тейлора