Методы нахождения безусловного и условного экстремума
Курсовой проект - Математика и статистика
Другие курсовые по предмету Математика и статистика
p>
Таким образом, решение (точка минимума) , значение функции в которой , получено в результате двух одномерных поисков, поскольку целевая функция квадратична.
Рис 7. Графическое пояснение метода сопряженных градиентов
Квазиньютоновский метод
Описание алгоритма
Данный метод обладает положительными чертами метода Ньютона, однако, использует информацию только о первых производных. В этом методе приближение к очередной точке в пространстве оптимизируемых параметров задается формулой:
Направление поиска определяется выражением:
, где - матрица порядка (метрика).
Матрица - вычисляется по формуле.
, где:
(1)
Где изменение градиента на предыдущем шаге.
Данный алгоритм отличается устойчивостью, так как обеспечивает убывание целевой функции от итерации к итерации.
Нахождение минимума целевой функции квазиньютоновским методом:
Исходные данные:
- начальная точка;
Шаг 1.
Положим
Шаг 2.
Поиск вдоль прямой:
Шаг 3.
Шаг 4.
Поиск вдоль прямой:
Таким образом, точка минимума , значение функции в которой найдена за одну итерацию.
Рис 8. Графическое пояснение квазиньютоновского метода
Градиентные методы поиска экстремума функции
В отличие от методов прямого поиска градиентные методы поиска используют информацию о производных функции. Это позволяет уменьшить количество необходимых вычислений значений функции. Эти методы делятся на две группы: методы, использующие информацию только о первых производных, и методы, учитывающие информацию и первых, и вторых производных.
Метод простейших градиентов
Решение:
f(x1,x2)= (х1 - 3)2 + (х2 - 1)2 +х1х2
?f/?x1=2x1 + x2 - 6 ?f/?x2=x1 + 2x2 -2
1.Шаг: Задаем начальные данные:
х(0) = [-9;-10]Т; ? =0,3;
2.Шаг:
1 итерация: х(1) = х(0) - ? f (x(0) ).
f (x(0) ) = [-34;-30]T; х(1) = [-9;-10]Т -0,3[-34;-30]T=[1,2;-1]T;
итерация: х(2) = х(1) - ? f (x(1) ).
f (x(1) ) = [-4,6;-2,8]T; х(2) = [1,2;-1]T -0,3[-4,6;-2,8]T =[2,58;0,16]T;
итерация: х(3) = х(2) - ? f (x(2) ).
f (x(2) ) = [-0,68;0,9]T; х(3) = [2,58;0,16]T -0,3[-0,68;0,9]T =[2,784;0,11]T;
итерация: х(4) = х(3) - ? f (x(3) ).
f (x(3) ) = [-0,322;1,004]T; х(4) = [2,784;0,11]T -0,3[-0,322;1,004]T =[2,881; -0,191]T;
итерация: х(5) = х(4) - ? f (x(4) ).
f (x(4) ) = [-0,429;0,499]T; х(5) = [2,881; -0,191]T -0,3[-0,429;0,499]T =[3,0097; -0,341]T;
итерация: х(6) = х(5) - ? f (x(5) ).
f (x(5) ) = [-0,322;0,328]T; х(6) =[3,0097; -0,341]T -0,3[-0,322;0,328]T =[3,106; -0,439]T;
итерация: х(7) = х(6) - ? f (x(6) ).
f (x(6) ) = [-0,227; 0,228]T; х(7) =[3,106; -0,439]T -0,3[-0,227; 0,228]T =[3,1741; -0,5074]T;
итерация: х(8) = х(7) - ? f (x(7) ).
f (x(7) ) = [-0,159; 0,159]T; х(8) =[3,1741; -0,5074]T -0,3[-0,159; 0,159]T =[3,333; -0,667]T;
После выполнения 8 итераций получено решение х* = х(7), при котором значение целевой функции f*=-0,3778.
Графическое пояснение метода простейших градиентов
Рис.
Вывод: метод простейших градиентов обеспечивает достаточно высокую точность при сравнительно малом количестве итераций по сравнению с методами прямого поиска, однако проигрывает всем другим градиентным методам, т.к. использует информацию о производных, однако при задании произвольного шага тратится больше времени, нежели в нижеследующем методе Коши, контролирующем процесс шага.
Нахождение условного экстремума. Метод штрафных функций
Суть метода заключается в преобразовании исходной целевой функции посредством включения в неё функции от ограничений, получая, таким образом, задачу безусловной оптимизации, для решения которой можно использовать рассмотренные в первой части методы. Переход от задачи условной оптимизации к задаче безусловной оптимизации осуществляется посредством включения в исходную функцию "штрафов" за нарушение ограничений задачи.
Пусть исходная задача имеет следующий вид:
при ограничениях:
Тогда преобразованная задача определится выражением:
где - штрафная функция от ограничений задачи, а - штрафной параметр. Наличие штрафного параметра вызвано тем, что введение штрафной функции сильно деформирует поверхность целевой функции, что, в свою очередь, приводит к ухудшению обусловленности преобразованной задачи. Поэтому параметр служит "регулятором" веса штрафной составляющей в целевой функции, и процесс решения задачи разбивается на ряд вспомогательных задач с различными значениями параметра и контролем сходимости их решений.
Виды штрафов:
Квадратичный штраф имеет вид: . Этот вид штрафов используется для учёта ограничений - равенств. Функция непрерывна и имеет непрерывную производную, откуда следует, что если непрерывны и дифференцируемы и , то стационарную точку можно найти аналитически.
Логарифмический штраф.
Этот штраф положителен для всех таких, что , и отрицателен при . Логарифмический штраф - это барьерная функция, неопределенная в точках, где . Поэтому на начальном этапе поиска, когда значение шага поиска невелико, необходимо обеспечить защиту процедуры от попадания рабочей точки в недопустимую область.
Штраф, заданный обратной функцией.
Как и предыдущий штраф, является барьерным. В допустимой области вблизи гра