7. Многовариантный анализ

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

. (92)

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

Функция F(X) имеет глобальный (локальный) минимум в точке X^*, если точка X^* допустима и F(X^*)F(X) для всех допустимых точек X (которые «близки» к X^*).

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

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

Метод поразрядного приближения основан на замене исходного непрерывного отрезка [a,b] несколькими участками равной длины и последующего вычисления целевой функции в узлах образованной сетки. Как только очередное значение функции окажется хуже (больше) предыдущего F(x_i+1)>F(x_i), реализуется аналогичный поиск в обратном направлении с шагом сетки, например в 4 раза меньше прежнего. И так до тех пор, пока величина шага не станет меньше погрешности.

Метод дихотомии реализует процедуру постепенного сужения исходного отрезка [a,b] вплоть до выполнения условия |b-a|<2. При этом в целях экономии вычислительных ресурсов текущий интервал [a,b] делится при помощи двух дополнительных точек и на два участка [a,x₂] и [x₁,b]. Далее в качестве нового текущего отрезка при помощи проверки условия F(x₁)>F(x₂) выбирается тот из них, который содержит искомый минимум (если условие выполняется, то новым текущим отрезком [a,b] будет участок [x₁,b], в противном случае это [a,x₂]). По сравнению с методом поразрядного приближения более детальному исследованию подвергаются только перспективные участки, что существенно повышает экономичность модели.

Метод золотого сечения обеспечивает использование на каждом шаге сужения отрезка (кроме первого) только одной дополнительной точки (необходимое для сравнения значение функции во второй точке берется из предыдущего шага). Для этого интервал неопределенности делится на две неравные части в соответствии с коэффициентом дробления k=0.618. В этом случае отношение длины большего участка к длине всего интервала равно отношению длины меньшего участка к длине большего (золотое сечение). Таким образом, на первом этапе значения функции определяются в двух дополнительных точках и . После проверки условия F(x₁)>F(x₂) и выбора перспективного участка (по аналогии с методом дихотомии) на следующем шаге определяется только одна дополнительная точка. Если F(x₁)>F(x₂) выбираем участок [x₁,b], т.е. a=x₁. Одна дополнительная точка уже известна (x₁=x₂), и остается определить вторую для нового отрезка [a,b] . Если F(x₁)<F(x₂) выбираем соответственно [a,x₂] т.е. b=x₂, вторая дополнительная точка уже известна (x₂=x₁). Определяем первую . Расчет заканчивается при выполнении условия |b-a|<.

Методы многомерной оптимизации используют для поиска экстремума функции многих переменных.

Метод покоординатного спуска заключается в поочередном поиске минимума последовательно по координатам вектора X. Многомерная задача оптимизации сводится, таким образом, к последовательности одномерных задач на каждом шаге. После выбора исходного приближения X⁰S вначале фиксируются значения всех координат кроме x₁. Получаем функцию одной переменной f(x₁), для которой одним из методов решается задача одномерной оптимизации. Затем переходим работе с координатой x₂ и т.д. После исследования функции F(X) по всем координатам пространства проектирования проверяют условие |F(X^k+1) –F(X^k)|< (где X^k – k-ое приближение вектора X), при выполнении которого расчет заканчивается. В противном случае проводят повторное исследование функции.

Метод градиентного спуска использует информацию о градиенте функции F(X), который определяется выражением:

, (93)

где – единичные векторы (орты). Вектор-градиент перпендикулярен касательной к линии уровня функции (соответствующей текущему X) и указывает направление наискорейшего возрастания функции в этой точке. Тогда для организации градиентного спуска используют антиградиент ().

После выбора начальной точки X⁰S и определения в ней антиградиента делается шаг в выбранном направлении. Проверяется условие F(X^k+1)<F(X^k), при выполнении которого вычисляется антиградиент в новой точке с повторением процедуры. Если F(X^k+1)>F(X^k), то в направлении антиградиента делается шаг в два раза меньший и т.д. Перемещение в n-мерном пространстве на шаг h реализуется с помощью следующих выражений:

. (94)

Процесс прекращается при выполнении условия

<. (95)

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

Псевдоградиентные методы обеспечивают выбор перспективного направления без вычисления градиента, использую лишь значения функции в нескольких точках. Примером может служить метод деформируемого многогранника (симплекс метод), для которого в пространстве проектирования вокруг исходного вектора X⁰S строится многогранник с числом вершин (n+1). В качестве направления улучшения функции выбирается ось отражения наихудшей вершины относительно центра тяжести оставшихся вершин [11].