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

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 — трехмерное изображение вспомогательной функции при величине параметра штрафа r0 = 100.

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

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

ω( x) = − x1 + 2x22 − 4x2 и будем решать задачу на минимизацию этой функции. Найденный минимум функции ω( x) будет являться максимумом исходной целевой функции f(x). Согласно методу штрафных функций при новой целевой функции ω( 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. Из точки с помощью метода сопряженных направлений (см. приложение №1) находиться точка безусловного минимума, равная .

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

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

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

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

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

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

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

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

 Скачать реферат