Безусловная и условная минимизация функции многих переменных с использованием систем MATCAD

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

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

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

Дана функция y= f(X), на которую накладываются ограничениями в форме равенств и неравенств. ( ) . Требуется найти минимум функции, используя возможности системы MATCAD.

2. Метод решения в системе MATCAD.

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

Функция Minimize(X) должна использоваться в составе блока решения, открываемого директивой Given, и возвращает вектор неизвестных , при которых заданная функция имеет минимальное значение. Внутри блока могут быть различные ограничительные условия в виде равенств или неравенств. Перед блоком решения надо задать начальные значения искомых переменных.

Примечание. При поиске минимума « овражистой» функции ( примером может служить функция Розенброка f(X)=100( x₂ –x₁²) ²+ (1-x₁)² ) результаты решения сильно зависят от выбора начальных значений переменных. х_i.

Другой способ решениявсистеме MATCAD задач безусловной минимизации функции многихпеременныхреализуютсяспомощью функции MinErr (p, q, ...), которая также должна использоваться в составе блока решения, открываемого директивой Given. Функции MinErr возвращает вектор неизвестных , при которых заданная функция имеет минимальное значение. При этом внутри блока решения обязательно д.б. заданы необходимые условия существования экстремума в следующем виде:

( более подробно см. приложение 4)

Данный способ также имеет недостатки при поиске минимума « овражистой» функции , т. е. решение зависит от выбора начальных значений вектора переменных . Поэтому наилучшим способом получения наиболее точного решения для любых функций f(X) в системе MATCAD является возможность программирования любого известного численного метода поиска минимума функции многихпеременных. В качестве примера возьмем метод деформированного многогранника(метод Нелдера —Мида). Напомним его основные положения.

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

Суть метода заключается в последовательном перемещении и деформировании симплекса вокруг точки экстремума.

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

Параметрами метода являются:

· коэффициент отражения α > 0, обычно выбирается равным 1.

· коэффициент сжатия β > 0, обычно выбирается равным 0,5.

· коэффициент растяжения γ > 0, обычно выбирается равным 2.

Алгоритм метода.

1. «Подготовка». Вначале выбирается n+1 точка X_i =( x_i⁽¹⁾,x_i⁽²⁾,…,x_i⁽ⁿ⁾),

i=1,..., n+1 образующие симплекс n-мерного пространства. В этих точках вычисляются значения функции: f₁=f(X₁), f₂=f(X₂), … , f_n+1=f(X_n+1).

2. «Сортировка». Из вершин симплекса выбираем три точки: X_h с наибольшим (из выбранных) значением функции f_h, : X_g со следующим по величине значением f_g и X_L с наименьшим значением функции f_{L .} Целью дальнейших манипуляций будет уменьшение по крайней мере f_h.

3. Найдём центр тяжести всех точек, за исключением X_h: .

4. «Отражение». Отразим точку X_h относительно X_c с коэффициентом α (при α = 1 это будет центральная симметрия, в общем случае — гомотетия), получим точку X_r и вычислим в ней функцию: f_r = f(X_r). Координаты новой точки вычисляются по формуле:

X_r = (1 + α) X_c − α X_h .

5. Далее смотрим, насколько нам удалось уменьшить функцию, ищем место f_r в ряду f_L, f_g. f_h.

Если f_r < f_L, то направление выбрано удачное и можно попробовать увеличить шаг. Производим «растяжение». Новая точка X_e = (1 − γ) X_c + γ X_r и значение функции f_e = f(X_e).

Если f_e < f_L, то можно расширить симплекс до этой точки: присваиваем точке X_h значение X_e и заканчиваем итерацию (на шаг 9).

Если f_e > f_L, то переместились слишком далеко: присваиваем точке X_h значение X_r и заканчиваем итерацию (на шаг 9).

Если f_L < f_r < f_g то выбор точки неплохой (новая лучше двух прежних). Присваиваем точке X_h значение X_r и переходим на шаг 9.

Если f_h > f_r > f_g, то меняем местами значения X_r и X_h. Также нужно поменять местами значения f_r и f_h. После этого идём на шаг 6.

Если f_r > f_h, то просто идём на следующий шаг 6.

В результате (возможно, после переобозначения) f_r > f_h > f_g> f_l.

6. «Сжатие». Строим точку X_s = β X_h + (1 − β) X_c и вычисляем в ней значение f_s = f(X_s).

7. Если f_s < f_h, то присваиваем точке X_h значение X_s и идём на шаг 9.

8. Если f_s > f_h, то первоначальные точки оказались самыми удачными. Делаем «глобальное сжатие» симплекса — гомотетию к точке с наименьшим значением X_l:

X_i= X_i+( X_i- X_L )/2

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

4. Текст программы.

Смотри приложение №4.

Задание.

Используя возможности системы MATCADнайти минимум следующих функций:

I. Задача безусловной оптимизации.

1) f(X)=x₁²+ x₂² +x₃²+ x₁–x₁ *x₂-2x₃

2) f(X)=100( x₂ –x₁²) ²+ (1-x₁)²

3) f(X)=( x₂ –x₁²) ²+ (1-x_1*x₂)²

4) f(X)=5x₁²+ x₂² + 4x₁ *x₂-16x₁-12x₂

5) f(X)=x₁²+ 2x₂² +3x₃²+10 x₁–6x₁ *x₃-20x₃

II. Задача условной оптимизации.

1) f(X)=x₁²+ x₂² + 0.5x₁ *x₂

x₁+ x₂ –1=0

2) f(X)=100( x₂ –x₁²) ²+ (1-x₁)²

x₁+ x₂ –1=0

3) f(X)= 3x₂² -11x₁-3x₂ -x₃

x₁-7x₂ +3x₃+7<=0

5 x₁+2x₂ –x₃–2<=0

x₃>=0

4) f(X)= 4/x₁+ 9/x₂ +x₁+x₂

x₁+x₂–6<=0

x_1>=0

x₂>=0

5) f(X)= 4/x₁+ 9/x₂ +x₁+x₂

x₁+x₂–4<=0

x_1>=0

x₂>=0

Лабораторная работа №5