Файл: Методы оптимизации в статистических задачах управления..pdf

3. Специальные методы поиска экстремума

Рассмотрим некоторые другие методы поиска экстремума, которые связаны с линейными методами. Начнем с метода симплекспланирования, предложенного в 1962 г. [151].

В основе этого метода лежит построение и последовательное перемещение симплекса в п-мерном пространстве переменной х. Под симплексом п-мерного пространства понимается выпуклая правильная фигура, задаваемая системой п + 1 точек.

Алгоритм метода симплекс-планирования состоит в следующем. Задаемся системой п + 1 точек х°, х1, . . ., хп, образующих исход­ ный симплекс 5°, и вычисляем в этих точках значения функции F (X). Выбираем вершину симплекса, соответствующую максималь­ ному значению функции. Обозначим эту вершину хг. Строится

новая точка хг, которая получается зеркальным отражением точки хг от грани симплекса, лежащей против нее (рис. 35):

Точки X0, X1, . . . , хг~ , хг, хг+ , . . . , хп образуют новый симплекс. Вычисляем значение функции в хг. Возможны следую­ щие варианты:

1. Среди вершин нового симплекса максимум функции дости­

гается в некоторой точке, отличной от точки х . Тогда на этом за­ канчивается первая итерация и производится следующая итерация

сновым симплексом.

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

среди оставшихся вершин. Если в п + 1 последовательном сим­ плексе какая-либо точка сохраняется, то вокруг этой точки строит­ ся новый симплекс с вдвое меньшим ребром.

Известны некоторые модификации метода, в которых симплекс может быть правильным или неправильным и в которых исполь­ зуются другие правила дробления симплекса.

Одним из правильных п-мерных симплексов с ребром, равным единице, и вершиной в начале координат является симплекс, за­ даваемый следующей матрицей:

сходимостью при большом значении коэффициента обусловлен­ ности р для матрицы вторых производных минимизируемой функ­ ции. Такие функции часто называются «овражными», так как для случая двух переменных (п = 2) поверхность, изображающая по­ добные функции, имеет вид вытянутого оврага. Одним из методов ускорения линейных методов является овражный метод миними­ зации [20, 22], который сводится к следующему. Задаемся началь­ ным приближением х° (рис. 36) и градиентным или каким-либо другим линейным методом производим оптимизацию. Обычно через несколько итераций применение линейного метода становится мало­ эффективным, так как итерационная точка достигает «дна оврага». Тогда предлагается прекратить применение линейного метода. Конечную точку обозначим Л 0. Далее в окрестности точки х° на расстоянии, превышающем шаг линейного метода, выбирается точка X 1 и аналогичным образом производится оптимизация линей­ ным методом. Результирующую точку обозначим А г. Для овраж­ ных функций точки Л 0 и Л х обычно находятся на дне оврага. За­ тем по дну оврага по прямой, соединяющей А 0 и Л х, в сторону точки с меньшим значением функции делается шаг в точку х2. Размер шага обычно больше размера шага градиентного метода и выбирается экспериментально. Затем из точки х2 осуществляется спуск в точку А а путем очередного применения линейного градиент­ ного метода, и по линии, соединяющей точки Л х и Л 2, делается новый шаг по дну оврага в точку Xs.

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

4.Квадратичные методы минимизации

Основная идея квадратичных методов минимизации состоит

вквадратичной аппроксимации минимизируемой функции F (х)

вокрестности итерационной точки х1 и выбор следующего при-

100

ближения xt+1 в качестве точки минимума квадратичного при­ ближения. По-видимому, исторически первым квадратичным ме­ тодом является метод Ньютона, в котором аппроксимация функции строится на основе разложения в ряд Тейлора:

/=1

сказанным определим следующее приближение х‘+г как точку минимума квадратичной аппроксимации q (х1, х). Предполагая

Сравнивая выражения (235) и (223), можно увидеть связь рас­ четных формул градиентных методов и метода Ньютона. Различие методов, с одной стороны, состоит в том, что в методе Ньютона отпадает проблема выбора шага, но, с другой стороны, требуется вычислять, а затем обращать матрицу вторых производных, что связано с значительной затратой труда. Заметим, что обратную матрицу для матрицы вторых производных рационально вычис­ лять по методу квадратного корня [14, 78], так как в процессе обращения матрицы таким способом одновременно производится

d2F (х)

проверка матрицы — на положительную определенность.

Осуществление этой проверки очень важно, так как соотношение (235) имеет смысл только для положительно определенных матриц.

В противном случае точка хг+1 может оказаться или точкой мак­ симума, или седловой точкой квадратичной аппроксимации q (х, X1).

В отличие от градиентных методов итерационная последова­ тельность, полученная при использовании метода Ньютона, не зависит от линейных (в частности, масштабных) преобразований

переменных. Так, если последовательность \х1) найдена при ми­ нимизации F (х), а последовательность {У1} — при минимизации

101

Ф (у) — F {Ах), где А — невырожденное преобразование, то из условия х° = Ау° следует равенство

Однако практически, если преобразование А близко к особен­ ному (I А I я« 0), то за счет ошибок округления вычисление

(236) может нарушиться.

Естественно, что скорость сходимости метода Ньютона значи­ тельно выше скорости линейных методов. Так, если функция F (х) дважды непрерывно дифференцируема, выпукла и имеет точку минимума х+, то при выполнении некоторых других естественных условий метод Ньютона дает квадратичную скорость сходимости

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

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

32F (X)

проверка матрицы вторых производных — на положитель­

ную определенность. При достижении положительной определен-

d2F (X)

ности матрицы —д^2— следующие итерации производятся по ме­

тоду Ньютона.

Существуют модификации метода Ньютона, направленные или на упрощение его реализации, или на расширение области сходи­

102

Доказано, что алгоритмы (237)—(239) сходятся со скоростью геометрической прогрессии, т. е. аналогично градиентному методу.

Перечисленные в настоящем параграфе методы являются ме­ тодами минимизации второго порядка, так как они предполагают

d2F (х)

использование матрицы — . Применение этих методов ока­

зывается рациональной только в случае, когда вычисление ма-

трицы d2F (х) не связано с большими трудностями, например,

когда известно аналитическое выражение функции F (х). Рассмотрим квадратичный метод минимизации, предложенный

Ф. Вольфом [152], в котором предполагается возможность вы­ числения значения функции и ее градиента в любой точке. Алго­ ритм метода состоит в следующем. Выбирается п + 1 базисная точка х°, X1, . . ., хп и в этих точках вычисляется градиент

из старых базисных точек (обычно в этой точке F (х) максимальна) выводится. Далее расчеты повторяются для полученной вновь системы базисных точек.

Нетрудно показать, что приведенный алгоритм за один шаг

где Q — симметричная положительно определенная матрица.

Действительно, система уравнений (240) для указанного случая имеет вид

103