Безусловная и условная минимизация функции многих переменных с использованием систем MATCAD
Цель работы:знакомство с задачей безусловной и условной минимизации функции многихпеременныхвсистеме MATCAD.
Введение.Данная задача может быть решена с помощьюсистемы MATCAD .В этой системе существуют различные встроенные функции, позволяющие с той или иной точностью решить поставленную задачу.
1. Постановка задачи.
Дана функция y= f(X), на которую накладываются ограничениями в форме равенств и неравенств. ( ) . Требуется найти минимум функции, используя возможности системы MATCAD.
2. Метод решения в системе MATCAD.
В данной системе имеется встроенная функция Minimize(X), которая производит вычисления на основе алгоритмов оптимизации, не требующих вычисления производных функции f(X), что позволяет решать задачи, в которых вычисления производных по тем или иным причинам невозможно.
Функция Minimize(X) должна использоваться в составе блока решения, открываемого директивой Given, и возвращает вектор неизвестных , при которых заданная функция имеет минимальное значение. Внутри блока могут быть различные ограничительные условия в виде равенств или неравенств. Перед блоком решения надо задать начальные значения искомых переменных.
Примечание. При поиске минимума « овражистой» функции ( примером может служить функция Розенброка f(X)=100( x2 –x12) 2+ (1-x1)2 ) результаты решения сильно зависят от выбора начальных значений переменных. хi.
Другой способ решениявсистеме MATCAD задач безусловной минимизации функции многихпеременныхреализуютсяспомощью функции MinErr (p, q, ...), которая также должна использоваться в составе блока решения, открываемого директивой Given. Функции MinErr возвращает вектор неизвестных , при которых заданная функция имеет минимальное значение. При этом внутри блока решения обязательно д.б. заданы необходимые условия существования экстремума в следующем виде:
( более подробно см. приложение 4)
Данный способ также имеет недостатки при поиске минимума « овражистой» функции , т. е. решение зависит от выбора начальных значений вектора переменных . Поэтому наилучшим способом получения наиболее точного решения для любых функций f(X) в системе MATCAD является возможность программирования любого известного численного метода поиска минимума функции многихпеременных. В качестве примера возьмем метод деформированного многогранника(метод Нелдера —Мида). Напомним его основные положения.
Метод Нелдера — Мида, также известный как метод деформируемого многогранника и симплекс-метод, — метод безусловной оптимизации функции от нескольких переменных, не использующий градиентов функции, а поэтому легко применим к негладким и/или зашумлённым функциям.
Суть метода заключается в последовательном перемещении и деформировании симплекса вокруг точки экстремума.
Пусть требуется найти безусловный минимум функции n переменных . Предполагается, что серьёзных ограничений на область определения функции нет, то есть функция определена во всех встречающихся точках.
Параметрами метода являются:
· коэффициент отражения α > 0, обычно выбирается равным 1.
· коэффициент сжатия β > 0, обычно выбирается равным 0,5.
· коэффициент растяжения γ > 0, обычно выбирается равным 2.
Алгоритм метода.
1. «Подготовка». Вначале выбирается n+1 точка Xi =( xi(1),xi(2),…,xi(n)),
i=1,..., n+1 образующие симплекс n-мерного пространства. В этих точках вычисляются значения функции: f1=f(X1), f2=f(X2), … , fn+1=f(Xn+1).
2. «Сортировка». Из вершин симплекса выбираем три точки: Xh с наибольшим (из выбранных) значением функции fh, : Xg со следующим по величине значением fg и XL с наименьшим значением функции fL . Целью дальнейших манипуляций будет уменьшение по крайней мере fh.
3. Найдём центр тяжести всех точек, за исключением Xh: .
4. «Отражение». Отразим точку Xh относительно Xc с коэффициентом α (при α = 1 это будет центральная симметрия, в общем случае — гомотетия), получим точку Xr и вычислим в ней функцию: fr = f(Xr). Координаты новой точки вычисляются по формуле:
Xr = (1 + α) Xc − α Xh .
5. Далее смотрим, насколько нам удалось уменьшить функцию, ищем место fr в ряду fL, fg. fh.
Если fr < fL, то направление выбрано удачное и можно попробовать увеличить шаг. Производим «растяжение». Новая точка Xe = (1 − γ) Xc + γ Xr и значение функции fe = f(Xe).
Если fe < fL, то можно расширить симплекс до этой точки: присваиваем точке Xh значение Xe и заканчиваем итерацию (на шаг 9).
Если fe > fL, то переместились слишком далеко: присваиваем точке Xh значение Xr и заканчиваем итерацию (на шаг 9).
Если fL < fr < fg то выбор точки неплохой (новая лучше двух прежних). Присваиваем точке Xh значение Xr и переходим на шаг 9.
Если fh > fr > fg, то меняем местами значения Xr и Xh. Также нужно поменять местами значения fr и fh. После этого идём на шаг 6.
Если fr > fh, то просто идём на следующий шаг 6.
В результате (возможно, после переобозначения) fr > fh > fg> fl.
6. «Сжатие». Строим точку Xs = β Xh + (1 − β) Xc и вычисляем в ней значение fs = f(Xs).
7. Если fs < fh, то присваиваем точке Xh значение Xs и идём на шаг 9.
8. Если fs > fh, то первоначальные точки оказались самыми удачными. Делаем «глобальное сжатие» симплекса — гомотетию к точке с наименьшим значением Xl:
Xi= Xi+( Xi- XL )/2
9. Последний шаг — проверка сходимости. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 2.
4. Текст программы.
Смотри приложение №4.
Задание.
Используя возможности системы MATCADнайти минимум следующих функций:
I. Задача безусловной оптимизации.
1) f(X)=x12+ x22 +x32+ x1–x1 *x2-2x3
2) f(X)=100( x2 –x12) 2+ (1-x1)2
3) f(X)=( x2 –x12) 2+ (1-x1*x2)2
4) f(X)=5x12+ x22 + 4x1 *x2-16x1-12x2
5) f(X)=x12+ 2x22 +3x32+10 x1–6x1 *x3-20x3
II. Задача условной оптимизации.
1) f(X)=x12+ x22 + 0.5x1 *x2
x1+ x2 –1=0
2) f(X)=100( x2 –x12) 2+ (1-x1)2
x1+ x2 –1=0
3) f(X)= 3x22 -11x1-3x2 -x3
x1-7x2 +3x3+7<=0
5 x1+2x2 –x3–2<=0
x3>=0
4) f(X)= 4/x1+ 9/x2 +x1+x2
x1+x2–6<=0
x1>=0
x2>=0
5) f(X)= 4/x1+ 9/x2 +x1+x2
x1+x2–4<=0
x1>=0
x2>=0
Лабораторная работа №5