- •1.3. Численные методы нахождения локального минимума функции одного переменного
- •Алгоритм отыскания локального минимума унимодальной функции
- •Метод дихотомии
- •Метод золотого сечения
- •Рубежный тестовый контроль
- •1.4. Оптимизационная задача при отсутствии ограничений. Целевые функции нескольких переменных
- •Рубежный тестовый контроль
- •1.5. Градиентные методы поиска экстремума функции нескольких переменных
- •Градиентный подход поиска локального минимума функции нескольких переменных
- •Метод наискорейшего спуска
- •Метод Гаусса-Зейделя
- •Овражный метод
- •Рубежный тестовый контроль
- •1.6. Численные методы решения нелинейных алгебраических уравнений
- •Метод Ньютона
- •Решение системы алгебраических уравнений
- •Рубежный тестовый контроль
- •Глава II. Условный экстремум функций
- •Условный экстремум функций при ограничениях типа равенств (Задача Лагранжа)
- •Максимизация скорости набора высоты самолета в установившемся режиме полета на заданной высоте
- •Задача о консервной банке
Градиентный подход поиска локального минимума функции нескольких переменных
Пусть требуется отыскать такую точку в которой целевая функция достигает локального минимума.
Д опустим, что – заданный исходный вектор и – антиградиент функции y(x), соответствующий вектору рис. 1.25.
Вектор выберем так, что
, , (1.98)
где – некоторая неотрицательная константа, которая регулирует величину шага в направлении антиградиента .
В скалярной форме выражение (1.98) записывается в виде
;
. . . . . . . . . . . . . . . . . . . (1.99)
.
Д опустим, что константа задана, тогда имеется возможность c помощью соотношения (1.98) построить некоторую последовательность точек , которая, вообще говоря, может привести к точке минимума , рис. 1.26. На этом рисунке с помощью линий уровня воссоздается рельеф целевой функции .
Задавая константу , следует помнить, что при малых процесс продвижения от точки в окрестность точки будет весьма медленным, а при больших имеется опасность получить неустойчивую последовательность точек .
Замечание. Компоненты градиента можно находить численными методами, вычисляя их, например, по следующим формулам (n=2)
;
,
где и – некоторые малые приращения, k – номер итерации.
Процесс вычислений заканчивается, как только
,
где – некоторое малое число, т.е. вычисление прекращается в том случае, когда расстояние точки от точки станет меньше наперед заданного числа .
Пример. Пусть , . Тогда
.
Зададим . В таком случае, согласно (1.99) на первом шаге поиска имеем:
; ,
т.е. ; .
При k = 2
; ,
т.е.
;
и т.д. Заметить, что , при , что и должно быть, т.к. целевая функция в начале координат имеет локальный минимум.
Если вместо взять , то получим расходящуюся последовательность точек ,… .
Рассмотрим некоторые разновидности градиентного метода.
Метод наискорейшего спуска
Переход от предыдущей точки к последующей по методу наискорейшего спуска осуществляется так, что
, . (1.100)
В этом выражении константа на каждом шаге (переход от к ) выбирается так, чтобы целевая функция
в направлении антиградиента достигла минимума (произойти это должно в точке ). В частности, требуемое значение можно найти, как решение уравнения
. (1.101)
В координатной форме векторному уравнению (1.100) соответствует система уравнений
, . (1.102)
Покажем, что векторы , – ортогональны. Действительно, в точке целевая функция , где для имеют место выражения (1.102). В таком случае согласно (1.101)
а это означает, что .
Рассмотрим геометрическую интерпретацию метода наискорейшего спуска.
П усть целевая функция имеет такой рельеф, как это с помощью линий уровня показано на рис. 1.27. На этом рисунке воспроизводится траектория поиска точки .
Пример. Пусть , .
Как и в предыдущем примере
.
k =0: Согласно (1.102)
, . (1.103)
В таком случае целевая функция
. (1.104)
Уравнение (1.101) запишется как
.
Заметим, что найденное значение обеспечивает целевой функции (1.104) минимум в силу положительности второй производной:
.
Согласно (1.103), при , .
Точка минимума достигнута за один шаг. Правда, так бывает далеко не всегда.
Заметим в заключение, что оптимальное значение на каждом шаге для функции может быть найдено одним из численных методов – дихотомии, золотого сечения и т.п.