Рассмотрение эффективности применения методов штрафов, безусловной оптимизации, сопряженных направлений и наискорейшего градиентного спуска для решения задачи поиска экстремума (максимума) функции нескольких переменных при наличии ограничения равенства.
При низкой оригинальности работы "Численные методы решения задач условной многомерной оптимизации", Вы можете повысить уникальность этой работы до 80-100%
Математическое программирование - математическая дисциплина, изучающая теорию и методы решения задач о нахождении экстремумов функции на множествах конечномерного векторного пространства, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами). В зависимости от природы множеств задачи математического программирования классифицируются как: · задачи дискретного программирования (или комбинаторной оптимизации) - если множество конечно и счетно; · задачи линейного программирования - если все ограничения и целевая функция содержат лишь линейные функции; · задачи нелинейного программирования - если ограничения или целевая функция содержат нелинейные функции и множество является подмножеством конечномерного векторного пространства. В данной работе поставлена задача условной оптимизации, т.е. задача, содержащая некоторые ограничения по независимым переменным на множестве G.Требуется найти точку такую, что f( x*) = x1 ? 2x22 4x2 > max (1) где (2) с помощью метода штрафных функций.Данная задача относится к классу задач нелинейного программирования. Этот метод заключается в сведении задачи, на условный экстремум, к решению последовательности задач на поиск безусловного экстремума вспомогательной функции, которая будет составлена по нижеописанным методам. Для данного проекта были выбраны метод сопряженных направлений, который является методом нулевого порядка, и метод наискорейшего градиентного спуска, являющийся методом первого порядка. Применение данного метода допустимо, так как функция непрерывна на всей области определения (областью определения функции является вся плоскость (x1,x2)), и непрерывны ее частные производные первого порядка: Оба метода безусловной оптимизации сводят задачу поиска наименьшего значения функции нескольких переменных к многократному решению одномерных задач оптимизации. Метод наискорейшего градиентного спуска гарантирует сходимость к точке минимума для сильновыпуклых функций.Идея метода штрафных функций заключается в сведении задачи (1-2) на условный экстремум к решению последовательности задач на поиск безусловного экстремума вспомогательной функции: , (3) где-штрафная функция,-параметр штрафа, задаваемый на каждой k-ой итерации (k=1, 2, 3,…). Задать начальную точку ; начальное значение параметра штрафа >0; число C>1 для увеличения параметра; малое число >0 для остановки алгоритма. Составить вспомогательную функцию Найти точку безусловного минимума функции по х с помощью какого-либо метода (нулевого, первого или второго порядка): При этом задать все требуемые этим методом параметры.1 показано трехмерное изображение целевой функции. 2 - трехмерное изображение целевой функции и функции-ограничения.В поставленной задаче требуется найти максимум функции f( x) = x1 - 2x22 4x2 . Однако выбранные методы оптимизации позволяют производить только поиск минимумов. Для применения данных методов сформируем новую целевую функцию ?( x) = - x1 2x22 - 4x2 и будем решать задачу на минимизацию этой функции. Согласно методу штрафных функций при новой целевой функции ?( x) = x1 - 2x22 4x2 и ограничения-3х1-2х2 = 6 сформируем вспомогательную функцию, используя квадратичный штраф: F(x, r) =-x1 2x22 - 4x2 r( 3x1 2x2 6)2/2. Для поиска безусловного минимума вспомогательной функции в первом случае воспользуемся методом сопряженных направлений: Описание алгоритма поиска минимума методом сопряженных направлений: 1. Выбирается начальное приближение i=0, k=0, , значение параметра штрафа 00 и коэффициент увеличения параметра штрафа С=100, задаются точность поиска начальные направления поиска: Полагаем , 2.Запишем функцию ограничение: 4. Согласно методу штрафных функций составим штрафную функцию P(x,y,rk), используя квадратичный штраф: 5. Зададим начальный параметр штрафа и коэффициент "С" увеличения параметра штрафа: 7. Приступим к безусловному поиску методом сопряженных направлений. Минимум найден, переходим ко второму шагу метода сопряженных направлений: 9.1.Таблица 1 Поиск минимума методом штрафных функций с использованием метода сопряженных направлений В результате была найдена точка минимума вспомогательной функции, которая удовлетворяет заданным ограничениям (-2.554; 0.833), и выполнено условие: P(x*(r1), r1) = 0.0006 <0.001.В процессе выполнения данной курсовой работы был рассмотрен метод штрафов, а также методы безусловной оптимизации, в частности был освоен метод сопряженных направлений и метод наискорейшего градиентного спуска. Проведя соответствующие исследования, можно утверждать, что метод данные методы являются достаточно стабильными, т.е. алгоритм незначительно увеличивает число итерации при малых возмущениях выбора начальных точек.
План
Оглавление
Введение
1. Основная часть
1.1 Постановка задачи
1.2 Анализ задачи
1.3 Описание метода штрафных функций
1.4 Графическое решение задачи
1.5 Формализация расчетов
2. Структура приложения, предназначенного для решения задачи
3. Результаты вычислений
4. Выводы
5. Список литературы
6. Приложения
Введение
Математическое программирование - математическая дисциплина, изучающая теорию и методы решения задач о нахождении экстремумов функции на множествах конечномерного векторного пространства, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами). В зависимости от природы множеств задачи математического программирования классифицируются как: · задачи дискретного программирования (или комбинаторной оптимизации) - если множество конечно и счетно;
· задачи целочисленного программирования - если множество является подмножеством множества целых чисел;
· задачи линейного программирования - если все ограничения и целевая функция содержат лишь линейные функции;
· задачи нелинейного программирования - если ограничения или целевая функция содержат нелинейные функции и множество является подмножеством конечномерного векторного пространства.
Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.
Математическое программирование используется при решении оптимизационных задач исследования операций. Способ нахождения экстремума полностью определяется классом поставленной задачи.
В данной работе поставлена задача условной оптимизации, т.е. задача, содержащая некоторые ограничения по независимым переменным на множестве G. Эти ограничения задаются совокупностью некоторых функций, удовлетворяющих равенствам или неравенствам. Ограничения - равенства выражают зависимость между проектными параметрами, которая должна учитываться при нахождении решения. Ограничения-неравенства устанавливают менее жесткие зависимости между проектными параметрами, позволяя им в некоторой части области G оставаться независимыми, а в остальной части проявляется зависимость друг от друга. Решение задачи условной оптимизации зачастую нельзя найти, используя аналитические методы решения, поэтому требуется использование дополнительных численных методов.
В настоящее время разработано множество численных методов для задач как безусловной, так и условной оптимизации.
Методы условной оптимизации, как правило, сводят решение исходной задачи к многократному решению вспомогательной задачи безусловной оптимизации.
Решение безусловной оптимизации является более простым и легко реализуется в современных математических пакетах. Для решения поставленной задачи использовались средства программы MATHCAD. Данная программа позволяет выполнить как численные, так и аналитические вычисления, имеет удобный математически-ориентированный интерфейс и прекрасные средства графики. Система MATHCAD изначально создавалась для численного решения математических задач, позже в нее были интегрированы инструменты символьной математики из системы Maple, что постепенно превратило MATHCAD в универсальный инструмент решения математических задач. Поэтому выбор данного программного средства вполне обоснован.
1. Основая часть
Вывод
В процессе выполнения данной курсовой работы был рассмотрен метод штрафов, а также методы безусловной оптимизации, в частности был освоен метод сопряженных направлений и метод наискорейшего градиентного спуска. Проведя соответствующие исследования, можно утверждать, что метод данные методы являются достаточно стабильными, т.е. алгоритм незначительно увеличивает число итерации при малых возмущениях выбора начальных точек. Метод наискорейшего градиентного спуска является надежным, а метод сопряженных направлений - нет, т. к. при повторении поиска из разных начальных точек, алгоритм приходит к различным точкам оптимума.
В результате поиска методом сопряженных направлений была найдена точка минимума вспомогательной функции (-2.554; 0.833), удовлетворяющая условиям ограничений.
В результате поиска методом наискорейшего градиентного спуска был найдена точка минимума вспомогательной функции (-2.554; 0.833), удовлетворяющая условиям ограничений.
Исходя из особенностей метода сопряженных направлений, данный метод с меньшим числом итераций достиг точки минимума. За точку максимума исходной целевой функции примем точку (-2.554; 0.833). Значение функции в этой точке f(-2.554; 0.833) = - 0.611.
Список литературы
1. Пантелеев А.В., Т.А.Летова. Методы оптимизации в примерах и задачах: Учебное пособие.- М.: Высш. Шк., 2002.
2. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие.-М.: Высш. Шк., 1993.
