Одномерная и многомерная оптимизация

Практическая работа № 2

ОДНОМЕРНАЯ И МНОГОМЕРНАЯ ОПТИМИЗАЦИЯ

Цель работы

1. Знакомство с численными методами одномерной и многомерной оптимизации.

2. Разработка численной ММ, реализующей один из оптимизационных методов.

3. Решение задачи оптимизации при помощи средств MATLAB и калькулятора.

Задачи оптимизации часто возникают в процессе поиска наилучшей конструкции объекта. В общем случае оптимизация заключается в нахождении значения аргумента X*={x1*, x2*,…, xn*}, при котором вещественная функция F(x1, x2,…, xn) на множестве S принимает минимальное или максимальное значение

[pic 1].                                                                (1)

Функция F представляет собой цель, а множество S выражает ограничения задачи. Если S есть все n-мерное пространство, говорят, что решается задача без ограничений (задача безусловной оптимизации). В противном случае рассматривается задача с ограничениями (условная оптимизация), определяющими множество S. Обычно это множество функций в виде условий равенств или неравенств.

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

Одномерная оптимизация является в свою очередь частным случаем для выделенных задач, которая заключается в поиске аргумента x* функции одной переменной F(x). При рассмотрении методов для упрощения будем считать функцию F(x) унимодальной на заданном отрезке [a, b], который называется интервалом неопределенности.

Метод дихотомии реализует процедуру постепенного сужения исходного отрезка [a, b] вплоть до выполнения условия |b–a| < 2ε. При этом в целях экономии вычислительных ресурсов текущий интервал [a, b] делится при помощи двух дополнительных точек  [pic 2]  и  [pic 3] на два участка

[a, x2] и [x1, b]. Далее в качестве нового текущего отрезка при помощи проверки условия F(x1) > F(x2) выбирается тот из них, который содержит искомый минимум (если условие выполняется то новым текущим отрезком [a, b] будет участок [x1, b], в противном случае это [a, x2]). По сравнению с методом поразрядного приближения более детальному исследованию подвергаются только перспективные участки, что существенно повышает экономичность модели.

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

Для этого интервал неопределенности делится на две неравные части в соответствии с коэффициентом дробления k=0.618. В этом случае отношение длины большего участка к длине всего интервала равно отношению длины меньшего участка к длине большего (золотое сечение). Таким образом, на первом этапе значение функции определяются в двух дополнительных точках [pic 4] и [pic 5]. После проверки условия F(x1) > F(x2) и выбора перспективного участка (по аналогии с методом дихотомии) на следующем шаге определяется только одна дополнительная точка. Если F(x1) > F(x2) выбираем участок [x1, b], (т.е. a=x1). Одна дополнительная точка уже известна (x1=x2) и остается определить вторую для нового отрезка [a, b] [pic 6]. Если F(x1) < F(x2) выбираем соответственно [a, x2] (т.е. b=x2), вторая дополнительная точка уже известна (x2=x1). Определяем первую [pic 7]. Расчет до выполнения условия |b–a|<ε.