Градиентный метод решения задач оптимизации в механике

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

Механико-математический факультет Кафедра процессов управления и информационной безопасности градиентный метод оптимизация механика

Курсовая работа по теоретической механике

ГРАДИЕНТНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ В МЕХАНИКЕ

Выполнил:

студент III курса очной формы обучения группы МХП-1,2−2008

Ибраев Динар Фидаилевич

Научный руководитель:

к.ф.-м.н., доцент кафедры ПУиИБ Лутманов Сергей Викторович

Пермь 2011

Пусть дана функция f (x), ограниченная снизу на множестве Rn и имеющая непрерывные частные производные во всех его точках. Требуется найти локальный минимум функции на множестве допустимых решений. В теории оптимизации f называется целевой функцией.

Все описываемые градиентные методы основаны на итерационной процедуре, реализуемой в соответствии с формулой Где — текущее приближение к решению; - параметр, характеризующий длину шага; - направление поиска управляемых переменных x. Способ определения и на каждой итерации связано с особенностями применяемого метода. Рассмотрим простейшие градиентные методы.

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

Второй — метод наискорейшего градиентного спуска, где величина шага определяется для каждого значения k из условия:

.

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

Более подробно рассмотрим метод Флетчера-Ривса. Относительно невысокий уровень требований к объему памяти ЭВМ делает метод Флетчера-Ривса и его модификации особенно полезным при решении задач большой размерности.

1. Градиентный метод Флетчера-Ривса

Постановка задачи

Пусть дана функция f (x), ограниченная снизу на множестве Rn и имеющая непрерывные частные производные во всех его точках.

Требуется найти локальный минимум функции f (x) на множестве допустимых решений X=Rn, т. е. найти такую точку, что f (x*)=min f (x).

Стратегия поиска

Стратегия метода Флетчера-Ривса состоит в построении последовательности точек {xk}, k=0,1,…, таких, что f (xk+1)< f (xk), k=0,1,… Точки последовательности {xk} вычисляются по правилу:

x k + 1 = x k +t d k, k = 0,1,…;

d k = +вk-1 d k -1;

d0 = ;

вk-1 = ;

Точка x0 задается пользователем, величину шага t выбираем постоянной.

Вычисление величины вk -1 обеспечивает для квадратичной формы построение последовательности Н-сопряженных направлений d0, d1,., dk,…. При этом в точках последовательности {xk} градиенты функции f (x) взаимно перпендикулярны.

Для квадратичных функций f (x) метод Флетчера-Ривса является конечным и сходится за число шагов, не превышающих размерность вектора x.

Алгоритм

Шаг 1. Задать x0, е1>0, е2>0, M — предельное число итераций, t — длина шага. Найти градиент ;

Шаг 2. Положить k = 0;

Шаг 3. Вычислить ;

Шаг 4. Проверить выполнение критерия окончания ;

Шаг 5. Проверить условие :

a) если неравенство выполняется, то расчет окончен и ;

б) если нет, то при k = 0 перейти к шагу 6, а при перейти к шагу 7.

Шаг 6. Определить

Шаг 7. Определить .

Шаг 8. Определить

Шаг 9. Вычислить

Шаг 10. Проверить выполнение условий

:

а) в случае выполнения обоих условий в двух последовательных итерациях с номерами k и k — 1 расчет окончен, найдена точка ;

б) если не выполняется хотя бы одно из условий, полагаем и переходим к шагу 3.

Тестовый пример

Применим градиентный метод Флетчера-Ривса для нахождения локального минимума функции:

Задаем начальные условия:

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

.

Текст программы, выполненной в системе Wolfram Mathematica, находится в Приложении.

2. Постановка задачи оптимизации

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

Считать, что

1. Приняв АС, за полярные координаты, определить величину скорости и ускорения точки С.

2. Предполагая, что Исследовать величину скорости и ускорения точки С на минимум по параметрам a, b, t.

3. Стратегия поиска

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

Где — штрафная функция, rk — параметр штрафа, задаваемый на каждой итерации.

Штрафные функции конструируются исходя из условий:

при выполнении ограничений,, при невыполнении ограничений. Как правило для ограничений типа равенств используется квадратичный штраф, а для ограничений типа неравенств квадрат срезки:

.

На каждой k-й итерации ищется точка минимума вспомогательной функции при заданном параметре с помощью метода Флетчера-Ривса. Полученная точка используется в качестве начальной на следующей итерации, выполняемой при возрастающем значении параметра штрафа. При неограниченном возрастании последовательность точек стремится к точке условного минимума .

4. Задача на минимум функции скорости и ускорения

1. Приняв АС, за полярные координаты, определить величину скорости и ускорения точки С.

2. Предполагая, что Исследовать величину скорости и ускорения точки С на минимум по параметрам a, b, t.

AC = AB+BC;

Начальные условия:

Для скорости:

Сравнение полученного результата с результатом команды NMinimize пакета Mathematica функции скорости:

Для ускорения:

Сравнение полученного результата с результатом команды NMinimize пакета Mathematica функции ускорения:

Текст программы, выполненной в системе Wolfram Mathematica, находится в Приложении.

Заключение

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

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

Приложение

Тестовый пример:

Найти локальный минимум функции .

Задача оптимизации Исследовать величину скорости и ускорения точки С на минимум по параметрам a, b, t.

Скорость:

Ускорение:

1. Лутманов С. В. Курс лекций по методам оптимизации — РХД Ижевск, 2001.

2. Рейклетис Г., Рэгсдел К. Оптимизация в технике. М.:Мир, 1986

3. Пантелеев А. В., Летова Т. А. Методы оптимизации в примерах и задачах. М: Высш. шк., 2005