Размещено на http://www.allbest.ru/

Курсовая работа

Метод наискорейшего спуска

метод оптимизация наискорейший спуск



Введение

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

В настоящее время для решения оптимальных задач применяют в основном следующие методы:

методы исследования функций классического анализа;

методы, основанные на использовании неопределенных множителей Лагранжа;

· вариационное исчисление;

· динамическое программирование;

· принцип максимума;

· линейное программирование;

· нелинейное программирование.

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

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

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

Итак, целью моей курсовой работы является:

Изучить алгоритм метода наискорейшего спуска и реализовать его в программном виде.

Из цели можно выявить ряд задач:

· ознакомиться с основными численными методами оптимизации;

· более подробно рассмотреть алгоритм метода наискорейшего спуска;

· написать программу, позволяющую решать задачу оптимизации, используя этот алгоритм.



1. Основные методы оптимизации

Решение многих теоретических и практических задач сводится к отысканию экстремума (наибольшего или наименьшего значения) скалярной функции  -мерного вектора. В дальнейшем под x будем понимать вектор-столбец (точку в -мерном пространстве):

Вектор-строка получается путем применения операции транспонирования:

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

Вектор , определяющий минимум целевой функции, называют оптимальным.

Отметим, что задачу максимизации  можно заменить эквивалентной ей задачей минимизации или наоборот. Рассмотрим это на примере функции одной переменной (Рис. 2.1). Если  - точка минимума функции , то для функции  она является точкой максимума, так как графики функций  и , симметричны относительно оси абсцисс. Итак, минимум функции  и максимум функции  достигаются при одном и том же значении переменной. Минимальное же значение функции , равно максимальному значению функции , взятому с противоположным знаком, т.е. .

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

Рис. 2.1. Экстремум

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

где

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

Каждая точка х в n-мерном пространстве переменных , в которой выполняются ограничения, называется допустимой точкой задачи. Множество всех допустимых точек называют допустимой областью G. Решением задачи (оптимальной точкой) называют допустимую точку , в которой целевая функция  достигает своего минимального значения. (Приложение, см. 6.1.1)

Точка  определяет глобальный минимум функции одной еременной , заданной на числовой прямой , если  и для всех (Рис. 2.2, а). Точка  называется точкой строгого глобального минимума, если это неравенство выполняется как строгое. Если же в выражении  равенство возможно при х, не равных , то реализуется нестрогий минимум, а под решением в этом случае понимают множество (Рис. 2.2, б).

Рис. 2.2. Глобальный минимум. а - строгий, б - нестрогий

Точка определяет локальный минимум функции  на множестве Х, если при некотором достаточно малом для всех х, не равных , удовлетворяющих условию, выполняется неравенство . Если неравенство строгое, то  является точкой строгого локального минимума. Все определения для максимума функции получаются заменой знаков предыдущих неравенств на обратные. На Рис. 2.3 показаны экстремумы функции одной переменной  на отрезке . Здесь  - точки локального максимума, а  - локального минимума. В точке  реализуется глобальный максимум, а в точке  - глобальный минимум.

Рис. 2.3 Экстремумы функции

1.1 Классификация методов

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

,

i=1, …, n.

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

называют градиентом скалярной функции . Как видно, в точке минимума градиент равен нулю.

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

1) выбор направления движения из точки ;

2) определение шага вдоль этого направления.

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

Математически методы спуска описываются соотношением

где  - вектор, определяющий направление спуска;  - длина шага. В координатной форме:

Различные методы спуска отличаются друг от друга способами выбора двух параметров - направления спуска и длины шага вдоль этого направления. На практике применяются только методы, обладающие сходимостью. Они позволяют за конечное число шагов получить точку минимума или подойти к точке, достаточно близкой к точке минимума. Качество сходящихся итерационных методов оценивают по скорости сходимости.

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

или функции



Здесь k - номер итерации; ,  - заданные величины точности решения задачи.

Методы поиска точки минимума называются детерминированными, если оба элемента перехода от  к  (направление движения и величина шага) выбираются однозначно по доступной в точке  информации. Если же при переходе используется какой-либо случайный механизм, то алгоритм поиска называется случайным поиском минимума.

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

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

Качество численного метода характеризуется многими факторами: скоростью сходимости, временем выполнения одной итерации, объемом памяти ЭВМ, необходимым для реализации метода, классом решаемых задач и т. д. Решаемые задачи также весьма разнообразны: они могут иметь высокую и малую размерность, быть унимодальными (обладающими одним экстремумом) и многоэкстремальными и т. д. Один и тот же метод, эффективный для решения задач одного типа, может оказаться совершенно неприемлемым для задач другого типа. Очевидно, что разумное сочетание разнообразных методов, учет их свойств позволят с наибольшей эффективностью решать поставленные задачи. Многометодный способ решения весьма удобен в диалоговом режиме работы с ЭВМ. Для успешной работы в таком режиме очень полезно знать основные свойства, специфику методов оптимизации. Это обеспечивает способность правильно ориентироваться в различных ситуациях, возникающих в процессе расчетов, и наилучшим образом решить задачу.

1.2 Методы безусловной оптимизации

Как говорилось выше, задача безусловной оптимизации состоит в нахождении минимума или максимума функции в отсутствие каких-либо ограничений. Несмотря на то, что большинство практических задач оптимизации содержит ограничения, изучение методов безусловной оптимизации важно с нескольких точек зрения. Многие алгоритмы решения задачи с ограничениями предполагают сведение ее к последовательности задач безусловной оптимизации. Другой класс методов основан на поиске подходящего направления и последующей минимизации вдоль этого направления. Обоснование методов безусловной оптимизации может быть напрямую использовано при обосновании процедур решения задач с ограничениями.

Численные методы оптимизации нулевого порядка.

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

Самые популярные представители:

1) Метод прямого поиска (метод Хука-Дживса);

2) Метод деформируемого многоранника (метод Налдера-Мида);

3) Метод вращающихся координат (метод Розенброка);

4) Метод параллельных касательных (метод Пауэлла).

Численные методы безусловной оптимизации первого порядка.

Данный класс методов базируется на минимизации функции многих переменных, с использованием градиента.

Градиентом дифференцируемой функции  в точке  называется n-мерный вектор , компоненты которого являются частными производными функции , вычисленными в точке , т. е.

.

Этот вектор перпендикулярен к плоскости, проведенной через точку х[0] , и касательной к поверхности уровня функции f(x),проходящей через точку х[0] .В каждой точке такой поверхности функция f(x) принимает одинаковое значение. Приравнивая функцию различным постоянным величинам С₀, С₁, ... , получим серию поверхностей, характеризующих ее топологию (Рис. 2.8).



Рис. 2.4 Градиент

Вектор-градиент направлен в сторону наискорейшего возрастания функции в данной точке. Вектор, противоположный градиенту (-f'(х[0])), называется антиградиентом и направлен в сторону наискорейшего убывания функции. В точке минимума градиент функции равен нулю. На свойствах градиента основаны методы первого порядка, называемые также градиентным и методами минимизации. Использование этих методов в общем случае позволяет определить точку локального минимума функции. (Приложение, см. 6.1.3)

Очевидно, что если нет дополнительной информации, то из начальной точки х[0] разумно перейти в точку х [1], лежащую в направлении антиградиента - наискорейшего убывания функции. Выбирая в качестве направления спуска р[k] антиградиент -f'(х[k]) в точке х[k], получаем итерационный процесс вида

х[k+1] = x[k]-a_kf'(x[k]), а_k > 0; k=0, 1, 2, ...

В координатной форме этот процесс записывается следующим образом:

x_i[k+1]=х_i[k] - a_kf(x[k])/x_i

i = 1, ..., n; k= 0, 1, 2,...



В качестве критерия останова итерационного процесса используют либо выполнение условия малости приращения аргумента || x[k+l] - x[k] || <= ?, либо выполнение условия малости градиента

|| f'(x[k+l]) || <= ?,

Здесь ? и ? - заданные малые величины.

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

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

f(х[k+1]) = f(x[k] - a_kf'(x[k])) < f(x[k]).

Однако это может привести к необходимости проводить неприемлемо большое количество итераций для достижения точки минимума. С другой стороны, слишком большой шаг может вызвать неожиданный рост функции либо привести к колебаниям около точки минимума (зацикливанию). Из-за сложности получения необходимой информации для выбора величины шага методы с постоянным шагом применяются на практике редко.

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



1.3 Методы условной оптимизации

Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции n-мерного векторного аргументах. Решение задачи основывается на линейной или квадратичной аппроксимации целевой функции для определения приращений x₁, …,x_n на каждой итерации. Существуют также приближенные методы решения нелинейных задач. Это методы основанные на методе кусочно-линейной аппроксимации. Точность нахождения решений зависит от количества интервалов, на которых мы находим решение линейной задачи, максимально приближенной к нелинейной. Такой метод позволяет производить расчеты с помощью симплекс-метода. Обычно в линейных моделях коэффициенты целевой функции постоянны и не зависят от значения переменных. Однако существует ряд задач, где затраты зависят от объема нелинейно.



2. Метод наискорейшего спуска

Описав вкратце численные методы оптимизации, остановимся на итерационном методе, ознакомление с которым и является одной из задач данной курсовой работы. Основные понятия, используемые в градиентных методах описаны в пункте 2.2.

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

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

Алгоритм метода наискорейшего спуска состоит в следующем.

1. Задаются координаты начальной точки х[0].

2. В точке х[k], k = 0, 1, 2, ... вычисляется значение градиента f'(x[k]).

3. Определяется величина шага a_k, путем одномерной минимизации по а функции

 

4. Определяются координаты точки х[k+1]:



, i = 1 ,..., п.

5. Проверяются условия остановки итерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае осуществляется переход к п. 1. (Приложение, см. 6.1.4)

В рассматриваемом методе направление движения из точки х[k] касается линии уровня в точке x[k+1] (Рис. 2.9). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг a_k выбирается путем минимизации по а функции Необходимое условие минимума функции . Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:

= .

Рис. 3.1 Геометрическая интерпретация метода наискорейшего спуска

Градиентные методы сходятся к минимуму с высокой скоростью (со скоростью геометрической прогрессии) для гладких выпуклых функций. У таких функций наибольшее М и наименьшее m собственные значения матрицы вторых производных (матрицы Гессе)



мало отличаются друг от друга, т. е. матрица Н(х) хорошо обусловлена. Напомним, что собственными значениями ?_i, i =1, …, n, матрицы являются корни характеристического уравнения

Однако на практике, как правило, минимизируемые функции имеют плохо обусловленные матрицы вторых производных (т/М << 1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются (Рис. 2.10), а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными. Направление антиградиента этих функций (см. Рис. 2.10) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.

Рис. 3.2. Овражная функция



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



3. Руководство пользователя

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

На рисунках 4.1., 4.2., 4.3. изображено главное окно программы и пронумерованы компоненты интерфейса.

Рис. 4.1 Главное окно программы (в стартовом состоянии)

Рис. 4.2 Главное окно программы, (после произведения расчетов)



Рис. 4.3 Вкладка «График», (после произведения расчетов)

3.1 Описание интерфейса

Обратившись к рисунку 4.1. можно увидеть основные элементы интерфейса. Вкратце опишем их:

1) Коэффициент a - поле для ввода коэффициента при первой переменной.

2) Коэффициент b - поле для ввода коэффициента при второй переменной.

3) Координата X начальной точки, откуда начинаются расчет.

4) Координата Y начальной точки, откуда начинаются расчет.

5) Точность, достигнув которой алгоритм прекращает свою работу.

6) Поле для ввода величины начального шага.

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

8) Поле для вывода конечного результата рассчётов (координат точки минимума)

9) Кнопка, запускающая процедуру расчета.

10) Таблица, содержащая результаты работы каждой итерации.

На рисунке 4.2. более подробно описаны элементы таблицы (10).

11) Номер итерации.

12) Координата x точки , где i - номер итерации (11).

13) Координата y точки , где i - номер итерации (11).

14) Шаг на данной итерации.

15) Значение x градиента в точке , где i - номер итерации (11).

16) Значение y градиента в точке , где i - номер итерации (11).

Рис. 4.3. изображает страницу программы с графиком, показывающим результат работы метода.

17) Шкала масштаба, при передвижении которой меняется масштаб графика (18). В правую сторону - больше, в левую - меньше.

18) График отображающий результаты работы метода. Чёрными пунктирными линиями обозначены оси абсцисс и ординат, серыми эллипсами изображена рассматриваемая функция со значением X_i на каждой итерации, красными линиями обозначена траектория передвижения от точки X_i к X_i+1, надписи на жёлтом фоне содержат координаты начальной точки и точки минимума.

3.2 Пошаговое руководство

1) Запустите программу.

2) Введите начальные данные.

3) Нажмите кнопку «Считать».

4) Результаты работы можно увидеть в таблице (10) (Рис. 4.1.) и на графике (18) (Рис. 4.3.).

19) 

Заключение

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

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

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



Список литературы

1. Н. Глебов, Ю. Кочетов, А. Плясунов Методы оптимизации:учебное пособие/Новосибирск:Новосибирский государственный университет,2000. 105 с.

2. В.И. Рейзлин, Численные методы оптимизации: учебное пособие / Томский политехнический университет. - Томск: Изд-во Томского политехнического университета, 2011 - 105с

3. Исследование операций в экономике: Учеб. Пособие для вузов / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; под ред. Проф. Н.Ш. Кремера. - М.: ЮНИТИ, 2003. - 407 с.

4. URL: http://matlab.exponenta.ru/optimiz/book_2/2_2.php (дата обращения: 20.12.2012).

Размещено на Allbest.ru

...