bigpo.ru
добавить свой файл
1
ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ


ГОУВПО «Самарский государственный архитектурно-строительный университет»


Факультет информационных систем и технологий


Кафедра прикладной математики и вычислительной техники


Научная работа


по дисциплине

Технология научных исследований


На тему


«ГРАФИЧЕСКАЯ ИЛЛЮСТРАЦИЯ ОПТИМИЗАЦИИ МЕТОДА НАИСКОРЕЙШЕГО СПУСКА ДЛЯ ФУНКЦИИ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ »


6 СЕМЕСТР 3 КУРС


Руководитель: Пиявский С.А.



Проверил:

Выполнила студентка ГИП-105

Кияева Ксения Анатольевна

Пиявский С.А.

__________________


_______________________



Общая оценка __________


Методический руководитель _______________________


  1. г



  1. Цель работы:


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


2. Математическая постановка задачи:

Требуется найти безусловный минимум функции многих переменных, т.е. найти такую точку x* Rn, что ,

где - вектор параметров оптимизации,

N – число параметров оптимизации,

f – скалярная нелинейная функция,


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

Алгоритм наискорейшего спуска

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

Итерационная формула процесса наискорейшего спуска имеет вид

,

или

.

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

,

решая одномерную задачу минимизации с использованием некоторого одномерного метода( см. Рис.1 Графическая иллюстрация.)

. В этом случае получаем алгоритм наискорейшего спуска.



Рис.1 Графическая иллюстрация.


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

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

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

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


4. Программная реализация метода:




Рисунок 1. Интерфейс программы


Программа реализована для нахождения оптимума следующих функций:


F(x)= K1*x1^2+K2*x1*x2+K3*x2^2+K4x1+K5x2+K6

F(x)= K1*sin(x1)+K2*x1+K3*x2+K4x1+K5*x2+K6*x1*x2

F(x)= K1*x1^2+K2*x1*x2+K3*x2^2+K4+K5x2+Ln(K6)

F(x)= Sqrt(K1*x1^2)+K2*x1*x2+K3*x2^2+cos(K5*x1*x2)+K6+K7

F(x)= x1*x2+x1*x1+cos(x1)*20


В программе есть возможность как «мгновенного» так пошагового нахождения оптимума функции, что представлено на: рис.2, рис.3, рис.4, рис.5.



Рисунок 2. Оптимизация 1-й функции




Рисунок 2. Оптимизация 5-й функции





Рисунок 4. Пошаговая оптимизация на примере 2-й функции





Рисунок 4. Пошаговая оптимизация на примере 2-й функции


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

Источники информации:


    1. http://matlab.exponenta.ru

    2. http://sapr.mgsu.ru