Методы оптимизации функций многих переменных (стр. 3 из 6)
Анализ поведения функции в окрестности точки A0 (0; 0) показывает, что, придавая х1 положительное и отрицательное значение при любом х2, можно получить соответственно положительное и отрицательное значение функции. Таким образом, A0 (0; 0) не является ни точкой локального минимума, ни точкой локального максимума.
Н (А1 (1,068; 1,668)) ≈ 
, матрица отрицательно определена, в точке А1 локальный максимум.
Н (А2 (-1,068; - 1,668)) ≈ 
, матрица положительно определена, в точке А2 локальный минимум.
Н (А3 (-0,331; 0,848)) ≈
, матрица положительно определена, в точке А3 локальный минимум.Н (А4 (0,331; - 0,848)) ≈ 
, матрица отрицательно определена, в точке А4 локальный максимум.
Точками глобального экстремума являются А1 (1,068; 1,668) - глобальный максимум, f (A1) ≈1,801; А2 (-1,068; - 1,668) - глобальный минимум, f (A2) ≈≈ - 1,801.
3. Остальные задания реализованы на языке СИ, для чего написаны классы для работы с векторами и матрицами (Cvector и Cmatrix) и использующее их приложение. В методе наискорейшего спуска для одномерной минимизации используется метод золотого сечения. Для отыскания собственных чисел матрицы Гессе применяется метод Якоби, для построения обратной матрицы - метод Жордана-Гаусса.
В начале работы программа выводит информацию о стационарных точках:
Stationary dots:
x1x2f (x1,x2) Extreme
1.0678901.6675661.801131LOC MAX
1.067890-1.667566-1.801131LOC MIN
0.3310770.848071-0.144426LOC MIN
0.331077-0.8480710.144426LOCMAX
GLOBALMIN: x (-1.067890, - 1.667566)
f (x) = - 1.801131
GLOBALMAX: x (1.067890, 1.667566)
f (x) = 1.801131
Затем устанавливается начальная точка x0 (-2,-2), функция исследуется на выпуклость/вогнутость в этой точке, выводится число обусловленности матрицы Гессе:
x0 (-2.000000, - 2.000000) Hessian: Alternating sign
f (x0) = - 0.398297
condH (x0) = 4.751665
Таким образом, квадратичная форма, соответствующая матрице
, является знакопеременной. Функция не является овражной в окрестности точки, и допустимо применение метода градиентного спуска.Далее запускается метод наискорейшего градиентного спуска, и выполняются две итерации.
Steepest descent method:
x2 (-1.200031, - 1.706888) Hessian: Convex
grad_f (x2) = (-0.963083, 0.275166)
f (x2) = - 1.741440
В результате двух итераций мы получили точку, достаточно близкую к точке глобального минимума.
Теперь из точки (-2; - 2) стартует метод Ньютона с поправкой гессиана. Результат двух итераций:
Newtonmethod:
x2 (-2.735431, - 2.306328) Hessian: Alternatingsign
grad_f (x2) = (-0.110421, 0.031948)
f (x2) = - 0.018516
Видно, что метод расходится. Начальная точка выбрана неудачно. Увеличение числа итераций приводит к дальнейшему расхождению метода. Это объясняется тем, что в начальной точке функция не является выпуклой. Анализируя линии уровня функции, выберем начальную точку ближе к оптимальной. Например, (-1; - 2):
x0 (-1.000000, - 2.000000) Hessian: Convex,
f (x0) = - 1.471518, cond H (x0) = 3.786885
Newton method:
x2 (-1.047041, - 1.722604) Hessian: Convex
grad_f (x2) = (0.379214, - 0.339841)
f (x2) = - 1.787758
Как в начальной, так и в конечной точке функция является выпуклой. За две итерации мы приблизились к точке А2 (-1,068; - 1,668).
Теперь возьмем начальную точку еще ближе к А2, например (-1; - 1,5):
x0 (-1.000000, - 1.500000) Hessian: Convex
f (x0) = - 1.752302
cond H (x0) = 3.857905
Newton method:
x2 (-1.067889, - 1.667566) Hessian: Convex
grad_f (x2) = (0.000000, 0.000000)
f (x2) = - 1.801131
Метод Ньютона достиг точки глобального минимума, об этом говорит практически нулевой вектор-градиент.
Точное значение
отличается от полученного методом Ньютона 
на 4,729∙10-7 (по модулю). В лабораторной работе проведено исследование заданной функции на глобальный экстремум с использованием аналитических преобразований, графика функции и разработанного приложения на языке C++.
С помощью метода градиентного спуска удалось улучшить целевую функцию. Выбор точки x0 (-2,-2) в качестве начальной для реализации метода Ньютона оказался неудачным, так как матрица Гессе в ней не является положительно определенной. Замена начальной точки на более подходящую для данного метода позволила за две итерации прийти в точку глобального минимума. Полученные результаты хорошо согласуются с теорией.
Разработанные классы Cvector и Cmatrix могут применяться в будущих проектах.
4. Задания для лабораторного практикума
Аналитически найти стационарные точки заданной функции, области выпуклости/вогнутости функции. Найти точку глобального минимума. Оценить овражность исследуемой функции в окрестности точки минимума.
Построить график функции, используя средства EXCEL или MATLAB.
Решить задачу минимизации численным методом из нескольких начальных точек. Сделать вывод об эффективности выбранного метода.
При выполнении задания на языке СИ написать классы для работы с векторами и матрицами.
Задание выбирать в соответствии с порядковым номером фамилии студента в списке группы.
, метод Хука-Дживса. 
, метод наискорейшего спуска. 
, метод Хука-Дживса. , метод сопряженных градиентов. 
, метод Нелдера-Мида. , метод Ньютона. 
, метод Нелдера-Мида. , метод наискорейшего спуска. 
, метод сопряженных градиентов. , метод Хука-Дживса. 
, метод Ньютона. , метод дробления шага. 
, метод наискорейшего спуска. , метод Нелдера-Мида. 
, метод дробления шага. 
, метод Ньютона. 
, метод Нелдера-Мида. , метод сопряженных градиентов. 
, метод наискорейшего спуска. , метод Ньютона. 
, метод дробления шага. 
, метод Нелдера-Мида. 
, метод сопряженных градиентов. , метод Ньютона. Контрольные вопросы:
Объяснить алгоритмы следующих методов
Метод конфигураций (Хука-Дживса).
Метод деформируемого многогранника (Нелдера Мида).
Метод наискорейшего спуска.
Метод сопряженных направлений и его модификации.
Метод Ньютона и его модификации.
Метод дробления шага.
Лабораторная работа № 2.
1. Методы условной оптимизации
Цель лабораторной работы - закрепление навыков аналитического решения задач оптимизации со смешанными ограничениями с использованием теоремы Куна-Таккера, нахождение седловой точки функции Лагранжа, использование теории двойственности для оценки чувствительности решения задачи оптимизации.
1.1 Теоретический обзор. Решение задачи минимизации со смешанными ограничениями
Общая задача нахождения экстремума функции при наличии ограничений - равенств и ограничений - неравенств записывается в следующем виде:
f (x) → extr, (6)
xÎX= {xÎEn: gi (x) ≤0, i=1,2,…,r; gi (x) =0, i=r+1, …, m, m-r<n},
где среди функций f (x) и gi (x) могут быть нелинейные.
Активные ограничения - неравенства в точке х* ─ это ограничения, которые выполняются в данной точке в виде равенства.
Пассивные ограничения - неравенства в точке х* ─ это ограничения, которые выполняются в данной точке в виде строгого неравенства.
Если градиенты активных ограничений-неравенств и ограничений-равенств в точке х* линейно независимы, то говорят, что в оптимальной точке выполнено условие регулярности.
Обобщенная функция Лагранжа для задачи со смешанными ограничениями задается как
L (x,λ0,λ) =λ0f (x) + 
λigi (x). (7)