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

В данной работе приводятся фундаментальные понятия и конкретные методы, используемые при поиске безусловных минимумов функций нескольких переменных.

Методы прямого поиска

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

1) поиск по симплексу, или S²-метод;

2) метод поиска Хука — Дживса;

3) метод сопряженных направлений Пауэлла.

Первые два из перечисленных методов относятся к категории эвристических и реализуют принципиально различающиеся стратегии поиска. В процессе поиска по S²-методу последовательно оперируют регулярными симплексами в пространстве управляемых переменных, тогда как при реализации метода Хука— Дживса используется фиксированное множество (координатных) направле­ний, выбираемых рекурсивным способом. Метод Пауэлла основан на теоретических результатах и ориентирован на решение задач с квадратичными целевыми функциями; для таких задач метод сходится за конечное число итераций. К числу общих особенностей всех трех методов следует отнести относительную простоту соответствующих вычислительных процедур, которые легко реализуются и быстро корректируются.

Критерий оптимальности

Сначала рассмотрим вопрос анализа «в статике» с использованием положений линейной алгебры и дифференциального исчисления, а также условия, которые (в достаточно общих возможных ситуациях) позволяют идентифицировать точки оптимума. Такие условия используются для проверки выбранных точек и дают возможность выяснить, являются ли эти точки точками минимума, максимума или седловыми точками. При этом задача выбора указанных точек остаётся вне рамок проводимого анализа; основное внимание уделяется решению вопроса о том, соответствуют ли исследуемые точки решениям многомерной задачи безусловной оптимизации, в которой требуется

минимизировать f(х), xÎR^N, (3.1)

при отсутствии ограничений на х, где х — вектор управляемых переменных размерности N, f — скалярная целевая функция. Обычно предполагается, что x_i (для всех значений i = 1, 2, 3,…, N)могут принимать любые значения, хотя в ряде практических при­ложений область значений х выбирается в виде дискретного множества. Кроме того, часто оказывается удобным предполагать, что функция f и ее производные существуют и непрерывны всюду, хотя известно, что оптимумы могут достигаться в точках разрыва f или ее градиента

(3.2)

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

Далее перейдем к вопросу анализа «в динамике», который формулируется следующим образом: если точка х⁽⁰⁾ не удовлетворяет условиям, налагаемым упомянутыми выше критериями оптимальности, то как получить «хорошее» новое приближение x⁽¹⁾к решению х*? Попытка дать ответ на этот вопрос приводит к необходимости рассмотрения ряда методов, описание которых составляет значительную часть данной главы. Рассматриваемые методы классифицируются в соответствии с тем, используется ли информация о производных исследуемых функций.

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

f(x)=f( )+ f( ) ∆x+½∆x f( )∆x+O (∆x), (3.3)

где — точка разложения из пространства R^N; ∆х = х - — величина изменения х; f(x) — N-мерный вектор-столбец первых производных f(х), вычисленных в точке ; f( ) = H ( ) — симметрическая матрица порядка N×N вторых частных производных f(x), вычисленных в точке . (Эту матрицу часто называют матрицей Гессе. Ее элемент, расположенный на пересечении i-й строки и j-го столбца, равен f / dx x .) O (∆x) — сумма всех членов разложения, имеющих порядок по ∆x выше второго. Пренебрегая членами высших порядков (т. е. исключая O (∆x)), определим величину изменения целевой функции f(х), соответствующего произвольному изменению х:

∆ f(x)= f(x) - f( ) = f( ) ∆x+½∆x f( )∆x (3.4)

Напомним, что по определению во всех точках из окрестности точки минимума целевая функция принимает значения, которые превышают минимальное, т. е. имеет место неравенство

∆f = f(x) - f( ) ≥0. (3.5)

Точка является точкой глобального минимума, если неравенство (3.5) выполняется для всех хÎ R^N; такие точки будем обозначать через х**. Когда формула (3.5) справедлива лишь в некоторой δ-окрестности точки , т. е. для всех х, таких, что ||х – || < δ при заданном δ > 0, то есть точка локального минимума, или х*. Если же

∆ f = f(x) – f( ) ≤0. (3.6)

то есть точка максимума (локального или глобального в соответствии с данными выше определениями). Исключение знака равенства из формул (3.5) и (3.6) позволяет определить точку строгого минимума или максимума. В случае когда ∆f принимает как поло­жительные и отрицательные, так и нулевые значения в зависимости от выбора точек из δ-окрестности, точка представляет собой седловую точку.

Вернемся к равенству (3.4) и вспомним о выдвинутом ранее предположении о том, что f(х), f(x) и f(x) существуют и непрерывны для всех х Î R^N. Как следует из формулы (3.4), для того чтобы знак ∆f не менялся при произвольном варьировании ∆х, градиент f( ) должен быть равен нулю, т. е. должна быть стационарной точкой. В противном случае разность ∆f может принимать положительные или отрицательные значения в зависимости от знаков f( ) и ∆х. Таким образом, точка должна удовлетворять условию стационарности

f( ) = 0, (3.7)

и формула (3.4) принимает следующий вид:

∆f(x) = +½∆x f( )∆x. (3.8)

Очевидно, что знак ∆f(x) определяется квадратичной формой

Q(х) = ∆x f( )∆x (3.9)

или Q(z)=z^TAz.

Из линейной алгебры известно, что

А — положительно определенная матрица, если Q(z)>0 для любых z;

А — положительно полуопределенная матрица, если Q (z)≥0 для любых z;

А — отрицательно определенная матрица, если Q(z)<0 для любых z; (3.10)

А — отрицательно полуопределенная матрица, если Q(z)≤0 для любых z;

А — неопределенная матрица, если Q (z)>0 для некоторых z и Q(z)<0 для остальных z.

Из (3.10) следует, что стационарная точка есть

точка минимума, если ²f( ) — положительно полуопределенная матрица;

точка максимума, если ²f( ) — отрицательно полуопределенная матрица; (3.11)

cедловая точка, если ²f(x) 0 — неопределенная матрица.

2.3 Метод поиска по симплексу (S2-метод)

Первые попытки решения оптимизационных задач без ограничений на основе прямого поиска связаны с использованием одномерных методов оптимизации. Как правило, при реализации таких методов допустимая область определения показателя качества функционирования системы (целевой функции) заменяется дискретным множеством (решеткой) точек пространства управляемых переменных, а затем используются различные стратегии уменьшения области, которая содержит решение задачи. Часто эта процедура оказывается эквивалентной равномерному поиску в узлах решетки и, следовательно, непригодной для решения задач с числом переменных, превышающим 2. Более полезная идея заключается в выборе базовой точки и оценивании значений целевой функции в точках, окружающих базовую точку. Например, при решении задачи с двумя переменными можно воспользоваться квадратным образцом, изображенным на рис. 3.1. Затем «наилучшая» из пяти исследуемых точек выбирается в качестве следующей базовой точки, вокруг которой строится, аналогичный образец. Если ни одна из угловых точек не имеет преимущества перед базовой, размеры образца следует уменьшить, после чего продолжить поиск.

Рисунок 3.1 - Квадратный образец (частный случай кубического образца)

Этот тип эволюционной оптимизации был использован Боксом и другими исследователями для анализа функционирования промышленных предприятий, когда эффект варьирования значений переменных, описывающих производственные процессы, измеряется с ошибкой. В задачах большой размерности вычисление значений целевой функции проводится во всех вершинах, а также в центре тяжести гиперкуба, т. е. в точках так называемого кубического образца. Если количество переменных (размерность пространства, в котором ведется поиск) равно N, то поиск по кубическому образцу требует 2 +1 вычислений значения функций для одного образца. При увеличении размерности задачи необходимое количество вычислений значения целевой функции возрастает чрезвычайно быстро. Таким образом, несмотря на логическую простоту поиска по кубическому образцу, возникает необходимость использования более эффективных методов прямого поиска для решения возникаю­щих на практике задач оптимизации.

Одна из вызывающих особый интерес стратегий поиска положена в основу метода поиска по симплексу, предложенного Спендли, Хекстом и Химсвортом. Следует отметить, что указанный метод и другие подобные методы не имеют отношения к симплекс-методу линейного программирования, а сходство названий носит случайный характер. Процедура симплексного поиска Спендли, Хекста и Химсворта базируется на том, что экспериментальным образцом, содержащим наименьшее количество точек, является регулярный симплекс. Регулярный симплекс в N-мерном пространстве представляет собой многогранник, образованный N+1 равностоящими друг от друга точками-вершинами.

Например, в случае двух переменных симплексом является равносторонний треугольник; в трехмерном пространстве симплекс представляет собой тетраэдр. В алгоритме симплексного поиска используется важное свойство симплек­сов, согласно которому новый симплекс можно построить на любой грани начального симплекса путем переноса выбранной вершины на надлежащее расстояние вдоль прямой, проведенной через центр тяжести остальных вершин начального симплекса. Полученная таким образом точка является вершиной нового симплекса, а выбранная при построении вершина начального симплекса исключается. Нетрудно видеть, что при переходе к новому симплексу требуется одно вычисление значения целевой функции. Рис. 3.2 иллюстрирует процесс построения нового симплекса на плоскости.

a — начальный симплекс; x⁽¹⁾, x⁽²⁾, x⁽³⁾; б — новый симплекс; x⁽²⁾,x⁽³⁾, x⁽⁴⁾

Рисунок 3.2 - Построение нового симплекса

Алгоритм симплекс-метода

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