Рис 7. Графическое пояснение метода сопряженных градиентов

2. Квазиньютоновский метод

Описание алгоритма:

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

Направление поиска определяется выражением:

, где - матрица порядка(метрика).

Матрица - вычисляется по формуле.

, где:

(1)

Где изменение градиента на предыдущем шаге.

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

Алгоритм метода:

Шаг 1. Задать: начальную точку х⁽⁰⁾. Перейти к шагу 2.

Шаг 2. Вычислить направление поиска s^(k). Перейти к шагу 3.

Шаг 3. Произвести поиск вдоль прямой . Перейти

к шагу 4.

Шаг 4. Проверка условия окончания поиска.

Да: закончить поиск;

Нет: перейти к шагу 2.

Ход решения:

Исходные данные:

- целевая функция;

Шаг 1.

- начальная точка;

Шаг 2.

Положим

Шаг 3.

Поиск вдоль прямой:

х⁽⁰⁾ = [2,1176; 5,4836]^T - [-10;-10]^T = [12,1176; 15,4836]^T;

g⁽⁰⁾ = g⁽¹⁾ – g⁽⁰⁾ = [3,7188; -2,9152]^T - [-36;-46]^T = [39.7188;43.085]^T;

Шаг 4:

Поиск вдоль прямой:

х⁽²⁾ =x⁽¹⁾+⁽¹⁾s⁽¹⁾=[2,1176; 5,4836]^T+⁽¹⁾[-3,462; 3,194]^T;

⁽¹⁾=0,997;

x⁽²⁾ = [-1,333;8.667]^Т;

Точность метода позволяет уже на четвертом шаге считать текущую точку точкой-экстремумом. Т.е. х* = х⁽²⁾ = [-1.333; 8,667]^Т; f(x*) =7,6667.

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

Рис 8. Графическое пояснение квазиньютоновского метода Заключение

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

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

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

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

Приложение 1

Библиографический список.

1. Микрюкова В.И. «Методы оптимизации». – Киров, 2004.

2. Интернет.