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

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

Пояснительная записка к курсовой работе по курсу "Методы оптимизации"

Аннотация

Используемые термины: Пусть X и Y -- два множества. Закон F, согласно которому каждому элементу поставлен в соответствие единственный элемент, называется отображением множества X в множество Y или функцией, заданной на X со значениями в Y. Экстремум -- максимальное или минимальное значение функции на заданном множестве. Задача безусловной оптимизации состоит в нахождении минимума или максимума функции в отсутствие каких-либо ограничений. Условная оптимизация -- поиск минимума или максимума функции при наличии ограничений. Безусловная оптимизация -- поиск минимума или максимума функции без наличия активных ограничений. Последовательность определенных и неотрицательных функций на множестве называют штрафом или штрафной функцией. Итерационный процесс -- многократно повторяющиеся действия (вычисления) до выполнения некоторого условия окончания. Целевая функция - функция, связывающая цель (оптимизируемую переменную) с управляемыми переменными в задаче оптимизации.

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

Число страниц	22
Число рисунков	9
Число таблиц	2
Число приложений	2

Оглавление

Введение

1. Основная часть

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

1.2 Анализ задачи

1.3 Описание метода штрафных функций

1.4 Графическое решение задачи

1.5 Формализация расчетов

2. Структура приложения, предназначенного для решения задачи

3. Результаты вычислений

4. Выводы

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

6. Приложения

Введение

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

· задачи дискретного программирования (или комбинаторной оптимизации) - если множество конечно и счетно;

· задачи целочисленного программирования - если множество является подмножеством множества целых чисел;

· задачи линейного программирования - если все ограничения и целевая функция содержат лишь линейные функции;

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

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

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

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

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

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

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

1. Основая часть

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

Требуется найти точку такую, что

f( x*) = x₁ ? 2x²₂ + 4x₂ > max (1)

где (2)

с помощью метода штрафных функций.

1.2 Анализ задачи

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

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



Оба метода безусловной оптимизации сводят задачу поиска наименьшего значения функции нескольких переменных к многократному решению одномерных задач оптимизации. Метод наискорейшего градиентного спуска гарантирует сходимость к точке минимума для сильновыпуклых функций. При уменьшении выпуклости уменьшается и скорость сходимости итерационного процесса. Если требуется найти глобальный минимум функции, то для строго выпуклой функции решение этой задачи аналогично поиску локального минимума. В случае существования нескольких минимумов, поиск глобального минимума сводится к перебору всех локальных минимумов. В методе сопряженных направлений используется тот факт, что минимум квадратичной функции может быть найден не более чем за n шагов при условии, что поиск ведется вдоль сопряженных относительно матрицы Гессе направлений. Так как достаточно большой класс целевых функций может быть представлен в окрестности точки минимума квадратичной аппроксимацией, описанная идея применяется и для неквадратичных функций. Исходная функция является строго выпуклой и, соответственно, имеет только один минимум, что оправдывает выбор методов для поиска безусловного экстремума. Методы безусловной оптимизации можно оценить по следующим параметрам:

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

2. Скорость сходимости - число итераций, необходимое для достижения заданной точности.

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

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

5. Надежность - свойство алгоритма приводить к оптимуму при многократном повторении поиска из разных начальных точек.

1.3 Описание метода штрафных функций

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

, (3)

где -штрафная функция, -параметр штрафа, задаваемый на каждой k-ой итерации (k=1, 2, 3,…).

Шаг 1. Задать начальную точку ; начальное значение параметра штрафа >0; число C>1 для увеличения параметра; малое число >0 для остановки алгоритма. Положить k=0.

Шаг 2. Составить вспомогательную функцию

Шаг 3. Найти точку безусловного минимума функции по х с помощью какого-либо метода (нулевого, первого или второго порядка):

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

Шаг 4. Проверить условие окончания:

а) если , процесс поиска закончить:

б) если, положить: и перейти к шагу 2.

1.4 Графическое решение задачи

Рис. 3. Изображение вспомогательной функции при r = 100.

На рис. 1 показано трехмерное изображение целевой функции.

На рис. 2 -- трехмерное изображение целевой функции и функции-ограничения.

На рис. 3 -- трехмерное изображение вспомогательной функции при величине параметра штрафа r₀ = 100.

1.5 Формализация расчетов

В поставленной задаче требуется найти максимум функции f( x) = x₁ ? 2x²₂ + 4x₂ . Однако выбранные методы оптимизации позволяют производить только поиск минимумов. Для применения данных методов сформируем новую целевую функцию

?( x) = ? x₁ + 2x²₂ ? 4x₂ и будем решать задачу на минимизацию этой функции. Найденный минимум функции ?( x) будет являться максимумом исходной целевой функции f(x). Согласно методу штрафных функций при новой целевой функции ?( x) = x₁ ? 2x²₂ + 4x₂ и ограничения ?3х₁ ?2х₂ = 6 сформируем вспомогательную функцию, используя квадратичный штраф:

F(x, r) = ?x₁ + 2x²₂ ? 4x₂ + r( 3x₁ + 2x₂ + 6)²/2.

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

Описание алгоритма поиска минимума методом сопряженных направлений:

1. Выбирается начальное приближение i=0, k=0, , значение параметра штрафа 00 и коэффициент увеличения параметра штрафа С=100, задаются точность поиска начальные направления поиска:



Полагаем ,

2. Из точки с помощью метода сопряженных направлений (см. приложение №1) находиться точка безусловного минимума, равная .

3. Проверяется условие окончания итерационного процесса . Для данной задачи:

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

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

1. Выбирается начальное приближение k=0, , значение параметра штрафа 0 и коэффициент увеличения параметра штрафа С=10, задаются точность поиска .

2. Из точки с помощью метода сопряженных направлений (см. приложение №2) находиться точка безусловного минимума, равная .

3. Проверяется условие окончания итерационного процесса . Для данной задачи:



4. Если условие окончания итерационного процесса не выполняется, то повторяются шаги (2-4), исходя из точки с параметром штрафа .

2. Структура приложения, предназначенного для решения задачи

Реализация методов безусловной оптимизации в программной среде MathCAD пошагово представлена ниже.

Метод сопряженных направлений:

1. Запишем исходную целевую функцию, максимум которой требуется найти:

2. Составим новую целевую функцию, условный минимум которой будем искать:

3. Запишем функцию ограничение:

4. Согласно методу штрафных функций составим штрафную функцию P(x,y,rk), используя квадратичный штраф:

5. Составим вспомогательную функцию F(x,y,rk), безусловный минимум которой будем искать:



6. Зададим начальный параметр штрафа и коэффициент "С" увеличения параметра штрафа:

7. Приступим к безусловному поиску методом сопряженных направлений. Для этого зададим начальные параметры:

8. Первая итерация метода сопряженных направлений:

8.1 Находим минимум функции стандартными свойствами MathCad:



9. Минимум найден, переходим ко второму шагу метода сопряженных направлений:

9.1. Аналогично пункту 8 производится поиск минимума с помошью функции root . После чего переходим на следующий шаг метода сопряженных направлений.

10. Третий шаг метода сопряженных направлений:

10.1. Аналогично пункту 8 производится поиск минимума стандартными свойствами MathCad. После чего переходим на следующий шаг метода сопряженных направлений.

11. Четвертый шаг метода сопряженных направлений:

12. Далее продолжаем двумерную оптимизацию методом сопряженных направлений, начиная с пункта 8.

Описание алгоритма поиска минимума методом сопряженных направлений:

1. На начальном этапе производятся шаги 1-5, как и в методе сопряженных направлений.

6. Зададим начальный параметр штрафа и коэффициент "С" увеличения параметра штрафа:

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

8. Вычисляем градиент целевой функции:

9. Первая итерация метода наискорейшего градиентного спуска:



10. Далее продолжаем двумерную оптимизацию методом наискорейшего градиентного спуска, начиная с пункта 9.

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

.

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

3. Результаты вычислений

Таблица 1 Поиск минимума методом штрафных функций с использованием метода сопряженных направлений

Количество итераций
1	100	(-2;1)	(-2.554; 0.833)	0.611	0.0006
1	10000	(-1; 0)	(-2.556; 0.833)	0.611	0.000006

В результате была найдена точка минимума вспомогательной функции, которая удовлетворяет заданным ограничениям (-2.554; 0.833), и выполнено условие:

P(x*(r₁), r₁) = 0.0006 < 0.001.

Таблица 2 Поиск минимума методом штрафных функций с использованием метода наискорейшего градиентного спуска

Количество итерации
1	10	(-2; 1)	(-2.544; 0.833)	0.606	0.006
2	100	(-2; 1)	(-2.554; 0.833)	0.611	0.0006
1	10	(-1; 1)	(-2.554; 0.833)	0.606	0.006
2	100	(-1; 1)	(-2.554; 0.833)	0.611	0.0006

В результате была найдена точка минимума вспомогательной функции, которая удовлетворяет заданным ограничениям (-2.554; 0.833), и выполнено условие

P(x*(r₂), r₂) = 0.0006 < 0.001.

4. Выводы

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

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

В результате поиска методом наискорейшего градиентного спуска был найдена точка минимума вспомогательной функции (-2.554; 0.833), удовлетворяющая условиям ограничений.

Исходя из особенностей метода сопряженных направлений, данный метод с меньшим числом итераций достиг точки минимума. За точку максимума исходной целевой функции примем точку (-2.554; 0.833). Значение функции в этой точке f(-2.554; 0.833) = - 0.611.

5. Литература

1. Пантелеев А.В., Т.А.Летова. Методы оптимизации в примерах и задачах: Учебное пособие.- М.: Высш. Шк., 2002.

2. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие.--М.: Высш. Шк., 1993.

3. Курицкий Б.Я. Поиcк оптимальных решений средствами Excel 7.0. - СПб.: BHV - Санкт-Петербург, 1997.

Приложение №1

Рис.4. Блок-схема алгоритма метода наискорейшего градиентного спуска



Рис.5. Блок-схема алгоритма метода сопряженных направлений

Приложение № 2

Рис.6. Начало вычислений методом сопряженных направлений.



Рис.7. Последняя итерация метода сопряженных направлений.



Рис. 8. Начало вычислений методом наискорейшего градиентного спуска.



Рис.9. Последняя итерация метода наискорейшего градиентного спуска