Летова Т. А. , Пантелеев А. В. Методы оптимизации. Практический курс, 2011

СХОДИМОСТЬ МЕТОДА

Теорема 1. Если квадратичная функция f(x) = (х, Нх) + (b, х) + а с неотрицательно определенной матрицей Н достигает своего минимального значения на Rⁿ, то метод Флетчера-Ривса обеспечивает отыскание точки минимума не более чем за n шагов.

Теорема 2. Пусть функция f(x) дифференцируема и ограничена снизу на R^m, а ее градиент удовлетворяет условию Липшица

Тогда при произвольной начальной точке для метода Полака-Рибьера имеем .

Теорема 2 гарантирует сходимость последовательности {x^k} к стационарной точке x^*, где ▽f(x^*)=0. Поэтому найденная точка x^* нуждается в дополнительном исследовании для ее классификации. Метод Полака-Рибьера гарантирует сходимость последовательности {x^k} к точке минимума только для сильно выпуклых функций.

Оценка скорости сходимости получена только для сильно выпуклых функций, в этом случае последовательность {x^k} сходится к точке минимума функции f(x) со скоростью: |x^k+n – x*| ≤ C|x^k – x*|, k = {0, n, 2, …}

ПРИМЕР. Найти минимум функции методом сопряженных градиентов:

f(X) = 2x12+2x22+2x1x2+20x1+10x2+10.

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

▽ f(X) =

4*x1+2*x2+20 2*x1+4*x2+10

Итерация №0.

▽ f(X0) =

Проверим критерий остановки: |▽f(X₀)| < ε

Вычислим значение функции в начальной точке f(X₀) = 10.
Сделаем шаг вдоль направления антиградиента.

X1 = X0 - t0▽ f(X0) =

- t0

=

-20.0*t0 -10.0*t0

f(X₁) = 2*(-20.0*t₀)²+2*(-10.0*t₀)²+2*(-20.0*t₀)*(-10.0*t₀)+20*(-20.0*t₀)+10*(-10.0*t₀)+10 → min

Найдем такой шаг, чтобы целевая функция достигала минимума вдоль этого направления. Из необходимого условия существования экстремума функции (f '(x₁)=0): 2800*t₁-500 = 0

Получим шаг: t₀ = 0.1786

Выполнение этого шага приведет в точку:

X0 =

- 0.1786

=

-3.5714 -1.7857

Итерация №1.

▽ f(X1) =

2.143 -4.286

Проверим критерий остановки:

|▽f(X₁)|<ε
Вычислим значение функции в новой точке f(X₁) = -34.643.

X² = X¹ - t₁d₁

d₁ = ▽f(X¹) + b₀▽f(X⁰)

d1 =

2.143 -4.286

+ 0.0459

=

3.061 -3.827

Сделаем шаг вдоль направления антиградиента.

X2 = X1 - t1▽ f(X1) =	-3.5714 -1.7857	- t1	3.061 -3.827	=	-3.0612*t1-3.5714 3.8265*t1-1.7857

f(X₂) = 2*(-3.0612*t₁-3.5714)²+2*(3.8265*t₁-1.7857)²+2*(-3.0612*t₁-3.5714)*(3.8265*t₁-1.7857)+20*(-3.0612*t₁-3.5714)+10*(3.8265*t₁-1.7857)+10 → min

Найдем такой шаг, чтобы целевая функция достигала минимума вдоль этого направления. Из необходимого условия существования экстремума функции (f '(x₂)=0):

49.198250728863*t₂-22.9591836734694 = 0

Получим шаг: t₀ = 0.4667

Выполнение этого шага приведет в точку:

X0 =

-3.5714 -1.7857

- 0.4667

3.061 -3.827

=

-5

Итерация №2.

▽ f(X2) =

Проверим критерий остановки: |▽f(X₂)| < ε

Вычислим значение функции в новой точке f(X₂) = -40.

Анализ решения. Найдем матрицу Гессе функции f(X) = 2x12+2x22+2x1x2+20x1+10x2+10.

H =

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

АЛГОРИТМ ДЭВИДОНА - ФЛЕТЧЕРА – ПАУЭЛЛА

 

Первоначально метод был предложен Дэвидоном и затем развит Флетчером и Пауэллом. Метод Дэвидона-Флетчера-Пауэлла называют также и методом переменной метрики. Он попадает в общий класс квазиньютоновских процедур, в которых направления поиска задаются в виде -Dj*grad(f(y)). Направление градиента является, таким образом, отклоненным в результате умножения на -Dj, где Dj - положительно определенная симметрическая матрица порядка n×n, аппроксимирующая обратную матрицу Гессе. На следующем шаге матрица Dj+1 представляется в виде суммы Dj и двух симметрических матриц ранга один каждая. В связи с этим схема иногда называется схемой коррекции ранга два.

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

Начальный этап.

Пусть >0 - константа для остановки. Выбрать точку х₁ и начальную симметрическую положительно определенную матрицу D₁. Положить y₁ = x₁, k = j = 1 и перейти к основному этапу.

Основной этап.

Шаг 1. Если зк f(y_j) зк< e, то остановиться; в противном случае положить d_j = - D_j f(y_j) и взять в качестве l_j оптимальное решение задачи минимизации f(y_j + ld_j) при l ³ 0. Положить y_j+1 = y_j + l_jd_j. Если j < n, то перейти к шагу 2. Если j = n, то положить y₁ = x_k+1 = y_n+1, заменить k на k+1, положить j=1 и повторить шаг 1.

Шаг 2. Построить D_j+1 следующим образом:

, (1)

где p_j = l_jd_j, (2)

q_j = f(y_j+1) - f(y_j). (3)

Заменить j на j + 1 и перейти к шагу 1.

Пример. Рассмотрим следующую задачу:

Минимизировать (x₁ - 2)⁴ + (x₁ - 2x₂)².

Результаты вычислений методом Дэвидона - Флетчера - Пауэлла приведены в таблице 1.

Таблица 1. Результаты вычислений по методу Дэвидона - Флетчера - Пауэлла.

k	xk f(xk)	J	yj f(yj)	f(yj)	зк f(yj) зк	D	dj	lj	yj+1
	(0.00, 3.00) (52.00)		(0.00, 3.00) (52.00) (2.70, 1.51) (0.34)	(-44.00, 24.00) (0.73, 1.28)	50.12 1.47		(44.00, -24.00) (-0.67, -1.31)	0.062 0.22	(2.70, 1.51) (2.55, 1.22)
	(2.55, 1.22) (0.1036)		(2.55, 1.22) (0.1036) (2.45, 1.27) (0.0490)	(0.89, -0.44) (0.18, 0.36)	0.99 0.40		(-0.89, 0.44) (-0.28, -0.25)	0.11 0.64	(2.45, 1.27) (2.27, 1.11)
	(2.27, 1.11) (0.008)		(2.27, 1.11) (0.008) (2.25, 1.13) (0.004)	(0.18, -0.20) (0.04, 0.04)	0.27 0.06		(-0.18, 0.20) (-0.05, -0.03)	0.10 2.64	(2.25, 1.13) (2.12, 1.05)
	(2.12, 1.05) (0.0005)		(2.12, 1.05) (0.0005) (2.115, 1.058) (0.0002)	(0.05, -0.08) (0.004, 0.004)	0.09 0.006		(-0.05, 0.08)	0.10	(2.115, 1.058)

На каждой итерации вектор d_j для j = 1, 2 определяется в виде
–D_j f(y_j), где D₁ ­­– единичная матрица, а D₂ вычисляется по формулам (1) - (3). При k = 1 имеем p₁ = (2.7, -1.49)^T, q₁ = (44.73, -22,72)^T. На второй итерации p₁ = (-0.1, 0.05)^T, q₁ = (-0.7, 0.8)^T и, наконец, на третьей итерации
p₁ = (-0.02, 0.02)^T, q₁ = (-0.14, 0.24)^T. Точка y_j+1 вычисляется оптимизацией вдоль направления d_j при начальной точке y_j для j = 1, 2. Процедура остановлена в точке y₂ = (2.115, 1.058)^T на четвертой итерации, так как норма зкf(y₂) зк = 0.006 достаточно мала. Траектория движения, полученная методом, показана на рисунке 1.

Рисунок 1. Метод Дэвидона - Флетчера - Пауэлла.

Лемма 1 показывает, что каждая матрица D_j положительно определена и d_j является направлением спуска.

Для доказательства леммы нам понадобится:

Теорема 1. Пусть S - непустое множество в Е_n, точка x О cl S. Конусом возможных направлений в точке x называется множество D = {d: d ¹ 0, x + ld О S при всех l О (0, d) для некоторого d > 0}.

Определение. Пусть x и y - векторы из Е_n и |x^Ty| - абсолютное значение скалярного произведения x^Ty. Тогда выполняется следующее неравенство, называемое неравенством Шварца: |x^Ty| £ ||x|| ||y||.

Лемма 1.

Пусть y₁ О Е_n, а D₁ – начальная положительно определенная симметрическая матрица. Для j = 1,..., n положим

y_j+1 = y_j + l_jd_j, где d_j = –D_j f(y_j),

а l_j является оптимальным решением задачи минимизации f(y_j + ld_j) при l ³ 0. Пусть, кроме того, для j = 1,..., n – 1 матрица D_j+1 определяется по формулам (1) - (3). Если f(y_j) ¹ 0 для j = 1,..., n, то матрицы D₁,..., D_n симметрические и положительно определенные, так что d₁,..., d_n – направления спуска.

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

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

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

Алгоритм Дэвидона–Флетчера–Пауэлла получим, если в уравнении (6.2.5) положить . Тогда

(6.2.10)

Заметим, что так как матрицы и симметричные, то если симметричная, то и будет симметричной.

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

= J+

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

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

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

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

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

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

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

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

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

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

 

ДОКАЗАТЕЛЬСТВО

 

Проведем доказательство по индукции. При j = 1 матрица D₁ симметрическая и положительно определенная по условию леммы. Кроме того, f(y₁)^Td₁ = – f(y₁)^TD₁ f(y₁) < 0, так как D₁ положительно определена. Тогда по теореме 1 вектор d₁ определяет направление спуска. Предположим, что утверждение леммы справедливо для некоторого j £ n – 1, и покажем, что оно справедливо для j+1. Пусть x – ненулевой вектор из E_n, тогда из (1) имеем

(4)

Так как D_j – симметрическая положительно определенная матрица, то существует положительно определенная матрица D_j^1/2, такая, что D_j = D_j^1/2D_j^1/2. Пусть a = D_j^1/2x и b = D_j^1/2q_j. Тогда x^TD_jx = a^Ta, q_j^TD_jq_j = b^Tb и x^TD_jq_j = a^Tb. Подставляя эти выражения в (4), получаем:

(5)

По неравенству Шварца имеем (a^Ta)(b^Tb) ³ (a^Tb)². Таким образом, чтобы доказать, что x^TD_j+1x ³ 0, достаточно показать, что p_j^Tq_j > 0 и b^Tb > 0. Из (2) и (3) следует, что

p_j^Tq_j = l_jd_j^T[ f(y_j+1) – f(y_j)]. (6)

По предположению f(y_j) ¹ 0, и D_j положительно определена, так что
f(y_j)^TD_j f(y_j) > 0. Кроме того, d_j – направление спуска, и, следовательно, l_j > 0. Тогда из (6) следует, что p_j^Tq_j > 0. Кроме того, q_j ¹ 0, и, следовательно, b^Tb= q_j^TD_jq_j > 0.

Покажем теперь, что x^TD_j+1x > 0. Предположим, что x^TD_j+1x = 0. Это возможно только в том случае, если (a^Ta)(b^Tb) = (a^Tb)² и p_j^Tx = 0. Прежде всего заметим, что (a^Ta)(b^Tb) = (a^Tb)² только при a = lb, т.е. D_j^1/2x = lD_j^1/2q_j. Таким образом, x = lq_j. Так как x ¹ 0, то l ¹ 0. Далее, 0 = p_j^Tx = l p_j^Tq_j противоречит тому, что p_j^Tq_j > 0 и l ¹ 0. Следовательно, x^TD_j+1x > 0, т.е. матрица D_j+1 положительно определена.

Поскольку f(y_j+1) ¹ 0 и D_j+1 положительно определена, имеем
f(y_j+1)^Td_j+1 = – f(y_j+1)^T D_j+1 f(y_j+1) < 0. Отсюда по теореме 1 следует, что d_j+1 – направление спуска.

Лемма доказана.

Квадратичный случай.

В дальнейшем нам понадобиться:

Теорема 2. Пусть f(x) = c^Tx + 1 x^THx, где Н - симметрическая матрица порядка n x n. Рассмотрим Н - сопряженные векторы d₁, …, d_n и произвольную точку x₁. Пусть l_k для k = 1, …, n - оптимальное решение задачи минимизации f(x_k + ld_k) при l О Е₁ и x_k+1 = x_k + ld_k. Тогда для k = 1, …, n справедливы следующие утверждения:

1. f(x_k+1)^Td_j = 0, j = 1, …, k;

2. f(x₁)^Td_k = f(x_k)^Td_k;

3. x_k+1 является оптимальным решением задачи минимизации f(x) при условии
x - x₁ О L(d₁, …, d_k), где L(d₁, …, d_k) – линейное подпространство, натянутое на векторы d₁, …, d_k, то есть

В частности, x_n+1 – точка минимума функции f на Е_n.

Если целевая функция f квадратичная, то в соответствии со сформулированной ниже теоремой 3 направления d₁, …, d_n, генерируемые методом Дэвидона - Флетчера - Пауэлла, являются сопряженными. Следовательно, в соответствии с утверждением 3 теоремы 2 метод останавливается после завершения одной итерации в оптимальной точке. Кроме того, матрица D_n+1, полученная в конце итерации, совпадает с обратной к матрице Гессе Н.

Теорема 3. Пусть Н – симметричная положительно определенная матрица порядка n x n. Рассмотрим задачу минимизации f(x) = c^Tx + 1 x^THx при условии x О E_n. Предположим, что задача решена методом Дэвидона - Флетчера - Пауэлла при начальной точке y₁ и начальной положительно определенной матрице D₁. В частности, пусть l_j, j = 1, …, n, – оптимальное решение задачи минимизации f(y_j + ld_j) при l ³ 0 и y_j+1 = y_j + l_jd_j, где d_j = -D_j f(y_j), а D_j определяется по формулам (1) – (3). Если f(y_j) ¹ 0 для всех j, то направления d₁, …, d_n являются Н - сопряженными и D_n+1 = H^-1. Кроме того, y_n+1 является оптимальным решением задачи.

Доказательство.

Прежде всего покажем, что для j, такого, что 1 £ j £ n, справедливы следующие утверждения:

1. d₁, …, d_j линейно независимы.

2. d_j^THd_k = 0 для i ¹ k; i, k £ j.

3. D_j+1Hp_k, или, что эквивалентно, D_j+1Hd_k = d_k для 1 £ k £ j, p_k = l_kd_k.

Проведем доказательство по индукции. Для j = 1 утверждения 1 и 2 очевидны. Чтобы доказать утверждение 3, заметим прежде всего, что для любого k справедливы равенства

Hp_k = H(l_kd_k) = H(y_k+1 - y_k) = f(y_k+1) – f(y_k) = q_k. (7)

В частности, Hp₁ = q₁. Таким образом, полагая j = 1 в (1), получаем

,

т.е. утверждение 3 справедливо при j = 1.

Теперь предположим, что утверждения 1, 2 и 3 справедливы для j £ n – 1. Покажем, что они также справедливы и для j + 1. Напомним, что по утверждению 1 теоремы 2 d_i^T f(y_j+1) = 0 для i £ j. По индуктивному предположению d_i = D_j+1Hd_i, i £ j. Таким образом, для i £ j имеем

0 = d_i^T f(y_j+1) = d_i^THD_j+1 f(y_j+1) = –d_i^THd_j+1.

Ввиду предположения индукции это равенство показывает, что утверждение 2 также справедливо для j+1.

Теперь покажем, что утверждение 3 справедливо для j+1.

Полагая k £ j+1, имеем

(8)

Учитывая (7) и полагая k = j + 1 в (8), получим, что D_j+2Hp_j+1 = p_j+1. Теперь пусть k £ j. Так как утверждение 2 справедливо для j + 1, то

p_j+1^THp_k = l_kl_j+1d_j+1^THd_k = 0. (9)

По предположению индукции из (7) и вследствие того, что утверждение 2 справедливо для j + 1, получаем

(10)

Подставляя (9) и (10) в (8) и учитывая предположение индукции, получаем

Таким образом, утверждение 3 справедливо для j+1.

Осталось показать, что утверждение 1 справедливо для j+1. Предположим, что . Умножая это равенство на и учитывая, что утверждение 2 справедливо для j+1, получаем, что . По условию теоремы , а по лемме 1 матрица положительно определена, так что . Так как H положительно определена, то и, следовательно, . Отсюда следует, что , и так как d₁, …, d_j линейно независимы по предположению индукции, то для i = 1, …, j. Таким образом, d₁, …, d_j+1 линейно независимы и утверждение 1 справедливо для j+1. Следовательно, утверждения 1, 2 и 3 выполняются. В частности сопряжённость d₁, …, d_n следует из утверждений 1 и 2, если положить j = n.

Пусть теперь j = n в утверждении 3. Тогда для k = 1, …, n. Если в качестве D взять матрицу, столбцами которой являются векторы d₁, …, d_n, то D. Так как D имеет обратную, то , что возможно только в том случае, если . Наконец, является оптимальным решением по теореме 2.

Теорема доказана.

 

МЕТОД КУБИЧЕСКОЙ ИНТЕРПОЛЯЦИИ

 

 

Интерполяция – это способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений. Метод использует кусочную кубическую Эрмитову аппроксимацию и сохраняют монотонность и форму данных. Если какой-либо из элементов вектора xi находится вне интервала, заданного вектором x, то выбранный метод интерполяции используется также и для экстраполяции. Как альтернатива, функция yi = interp1(x, y, xi, method, extrapval) заменяет экстраполированные значения теми, которые заданы вектором extrapval. Для последнего часто используется нечисловое значение NaN. Все методы работают на неравномерной сетке значений вектора x.

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

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

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

Пусть минимизируется функция на прямой , то есть функция

.

Предполагаем, что известны следующие значения:

.

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

Если выбрать p=0 (для простоты), то уравнения, определяющие a, b, c, d, выглядят так:

Эти уравнения имеют решение:

Стационарные точки кубического полинома являются решением уравнения

Точкой минимума кубического полинома является

, (*)

Как уже отмечалось, это все выполняется при =0. Выбор q осуществляется из следующих соображений.

Если < 0, то следует выбирать q>0, то есть сделать шаг в направлении убывания функции j(h). В противном случае q<0. Значение q должно быть таким, чтобы интервал (0, q) содержал минимум. Это будет верно, если j(q)>j(p) или >0 (даже при j(q)<j(p)). Если ни одно из этих условий не выполнено, то надо удвоить q, повторяя это до тех пор, пока полученный интервал не будет содержать минимум.

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

, где - оценка наименьшего значения j(h), h = const (2 или 1).

Алгоритм кубической интерполяции.

1. Найти и .

2. Проверить, выполняется ли условие <0. Если не выполняется, производить поиск в направлении - , иначе - в направлении . Выбрать q в соответствии с рекомендациями (при этом необходимо "угадать" ).

3. Вычислить

4. Если или , то интервал, содержащий минимум, найден. Иначе положить q = 2q и перейти к 3.

5. Использовать выражение (*) для аппроксимации точки минимума на интервале (0, q) значением r.

6. Если , где e - заданная точность, то остановиться.

7. Вернуться на шаг 5, используя интервал (0, r), если >0, либо используя интервал (r, q), если < 0.

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

 

 

 

ЗАКЛЮЧЕНИЕ

 

 

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

Первоначально метод был предложен Дэвидоном и затем развит Флетчером и Пауэллом. Метод Дэвидона-Флетчера-Пауэлла называют также и методом переменной метрики. Он попадает в общий класс квазиньютоновских процедур, в которых направления поиска задаются в виде -Dj*grad(f(y)). Направление градиента является, таким образом, отклоненным в результате умножения на -Dj, где Dj - положительно определенная симметрическая матрица порядка n×n, аппроксимирующая обратную матрицу Гессе. На следующем шаге матрица Dj+1 представляется в виде суммы Dj и двух симметрических матриц ранга один каждая. В связи с этим схема иногда называется схемой коррекции ранга два.

Интерполяция – это способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений. Метод использует кусочную кубическую Эрмитову аппроксимацию и сохраняют монотонность и форму данных.

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

 

 

СПИСОК ЛИТЕРАТУРЫ

 

1. Кононюк А.Е. Основы теории оптимизации, 2011

Летова Т. А., Пантелеев А. В. Методы оптимизации. Практический курс, 2011

3. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах, 2005

Поделиться:

Воспользуйтесь поиском по сайту: