Теорема 3.1. Необходимые условия

Для наличия в точке х* локального минимума необходимо, чтобы выполнялось равенство

f(x*)=0 (3.15а)

и матрица ²f(x*) была положительно полуопределенной. (3.15б)

Теорема 3.2. Достаточные условия

Если f(x*)=0 (3.16а)

и матрица ²f(x*) положительно определена, (3.16б)

то х* есть точка изолированного (строгого) локального минимума f(x).

Доказательства этих теорем непосредственно следуют из проведенного выше обсуждения и предоставляются читателю в качестве упражнений. Обычно приходится довольствоваться нахождением локального минимума; вместе с тем если можно показать, что x^T ²f(x) x≥ 0 для всех х, то f(х) называется выпуклой функцией, а локальный минимум оказывается глобальным.

Пример 3.1. Критерии оптимальности

Рассмотрим функцию

f(x) = 2 + 4 – 10 +

линии уровня которой изображены на рис. 3.3. Требуется классифицировать точку = [0, 0]

f(x) = 2 + 4 – 10 +

Рис. 3.3. Линии уровня нелинейной функции двух переменных из примера 3.1

Решение

Следовательно, точка — стационарная.

Следовательно,

Матрица ²f( ) является неопределенной, так как квадратичная форма z^TH z принимает положительное значение при z = (0, 1) и отрицательное значение при z = (l, 1) (см. приложение А). Поэтому представляет собой седловую точку, что и отражено на рис. 3.3.

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

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

1. Методы прямого поиска, основанные на вычислении только значений целевой функции.

2. Градиентные методы, в которых используются точные значения первых производных f(x).

3. Методы второго порядка, в которых наряду с первыми производными используются также вторые производные функции f(x).

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

Методы решения задач безусловной оптимизации отличаются относительно высоким уровнем развития по сравнению с другими методами нелинейного программирования. В специальной литературе представлены достаточно полные обзоры наиболее эффективных методов. Отличным примером такого обзора может служить книга Мюррея [1]. В данном разделе речь идет о методах прямого поиска, для реализации которых требуются только значения целевой функции; в следующем разделе рассматриваются градиентные методы и методы второго порядка. Здесь предполагается, что f(x) непрерывна, a f(x) может как существовать, так и не существовать, поскольку соответствующие числовые значения не используются. Однако следует отметить, что методы прямого поиска можно применять для решения задач, в которых f существует, и они часто используются в тех случаях, когда f представляет собой сложную векторную функцию управляемых переменных. Наконец, в этом и последующих разделах предполагается, что функция f(x) унимодальна в рассматриваемой области. Если же изучаемые методы применяются для анализа мультимодальных функций, то приходится ограничиваться идентификацией локальных минимумов.

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

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

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

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

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

3.2.1. Метод поиска по симплексу (S²-метод)

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

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

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

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

¹⁾ Гиперкубом называется куб в N-мерном евклидовом пространстве, т. е. множество S = {х = (х_1, х₂,..., x )Î R^N ׀ a ≤ x ≤ b, i = 1, 2, …, N}, где a и b — заданные числа.— Прим. перев.

образованный N+1 равностоящими друг от друга точками-вершинами.

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

Рис. 3.5. Построение нового симплекса.

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

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

⇐ Предыдущая 123 4 5 6 7 Следующая ⇒