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

Определение . Пусть - симметрическая матрица порядка
. Векторы
называются
- сопряженными, если они линейно независимы и выполняется условие
при
.

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

В качестве матрицы
можно взять матрицу Гессе

.

В качестве одного из направлений выберем
. Тогда направление
должно удовлетворять равенству

.

Следует заметить, что сопряженные направления выбираются неоднозначно. Однако если добавить условие нормировки, то их можно определить однозначно:

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

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

Утверждение. Пусть задана квадратичная функция
, две произвольные точки
и направление S ..Если точка является точкой минимума функции
вдоль направления S из точки , а- точкой минимума функции вдоль направления S из точки
, то направление
сопряжено с направлением S .

Алгоритм.

Шаг 1. Задать начальную точку и систему линейно независимых направлений
(они первоначально могут совпадать с направлениями координатных осей). Минимизировать функцию
при последовательном движении по направлениям; используя какой-либо одномерный поиск; и полученную ранее точку минимума взять в качестве исходной.

Шаг 2. Выполнить дополнительный шаг
, соответствующий полному перемещению на шаге 1. Вычислить точку
(рис 12). Проверить критерий (*) включения нового направления в систему сопряженных направлений.

Шаг 3. Пусть – наибольшее уменьшение целевой функции в одном из направлений
:

и является направлением, соответствующим.

Если выполняются условия

(*)

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

Шаг 4. Если условия не выполняются, то минимизировать функцию
вдоль направления
. Точку этого минимума взять в качестве начальной на следующем этапе. На этом этапе использовать систему направлений

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

Шаг 5. Если
, то минимум найден. В противном случае выполнить шаг 1.

Пример. Щелкнув по значку, откроется Mathcad документ метода сопряженных направлений, в котором можно выполнить вычисления.

Минимизация функции

методом сопряженных направлений

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

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

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

Шаг 1. Задать начальную точку x o и систему N линейно независимых направлений s i ; целесообразно принять s i = e i , i=1,2,...,N.

Шаг 2. Минимизировать W(x) при последовательном движении по N+1 направлениям; при этом полученная ранее точка минимума берется в качестве исходной, а направление s N используется как при первом, так и при последнем поиске.

Шаг 3. Определить новое сопряженное направление с помощью обобщенного свойства параллельного подпространства.

Для применения метода на практике его необходимо дополнить процедурами проверки сходимости и линейной независимости системы направлений. Если целевая функция квадратична и обладает минимумом, то точка минимума находится в результате реализации N циклов, включающих шаги 2-4. Здесь N - число переменных. Если же функция W(x) не является квадратичной, то требуется более чем N циклов.

13.3.3.Градиентныеметоды

Важность прямых методов неоспорима, т.к. в практических задачах информация о значениях целевой функции является единственно надежной информацией, которой располагает инженер. Однако, если существует и непрерывна целевая функция W(x) и ее первые производные а также они могут быть записаны в аналитическом виде (или с достаточно высокой точностью вычислены при помощи численных методов), то целесообразно использовать методы, основанные на использовании градиента целевой функции.

Все методы основаны на итерационной процедуре, реализуемой в соответствии с формулой

x k+1 = x k + a k s(x k), (13.9)

x k - текущее приближение к решению x * ;

a k - параметр, характеризующий длину шага,

s(x k) - направление поиска в N - мерном пространстве управляемых переменных x i , i = 1, 2,..., N.

Способ определения a k и s(x k) на каждой итерации связан с особенностями применяемого метода. Обычно выбор a k осуществляется путем решения задачи минимизации W(x) в направлении s(x k). Поэтому при реализации градиентных необходимо использовать эффективные алгоритмы одномерной минимизации.

Простейший градиентный метод

В основе метода лежит следующая итерационная модификация формулы (13.9):

x k+1 = x k - a DW(x k), (13.10)

a - заданный положительный коэффициент;

DW(x k) - градиент целевой функции первого порядка.

Недостатки:

· необходимость выбора подходящего значения a;

· медленная сходимость к точке минимума ввиду малости DW(x k) в окрестности этой точки.

Метод наискорейшего спуска

Свободен от первого недостатка простейшего градиентного метода, т.к. a k вычисляется путем решения задачи минимизации DW(x k) вдоль направления DW(x k) с помощью одного из методов одномерной оптимизации

x k+1 = x k - a k DW(x k). (13.11)

Данный метод иногда называют методом Коши.

Алгоритм характеризуется низкой скоростью сходимости при решении практических задач. Это объясняется тем, что изменения переменных непосредственно зависит от величины градиента, которая стремится к нулю в окрестности точки минимума и отсутствует механизм ускорения на последних итерациях. Поэтому, учитывая устойчивость алгоритма, метод наискорейшего спуска часто используется как начальная процедура поиска решения (из точек, расположенных на значительных расстояниях от точки минимума).

Метод Ньютона

Последовательное применение схемы квадратичной аппроксимации приводит к реализации оптимизационного метода Ньютона по формуле

x k+1 = x k - D 2 W(x k) -1 DW(x k). (13.12)

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

x k+1 = x k - a k D 2 W(x k) -1 DW(x k), (13.13)

a k - параметр, выбираемый таким образом, чтобы W(x k+1)®min.

Метод Пауэлла является одним из самых популярных методов. Эффективен как и рассмотренный ранее алгоритм квадратичной интерполяции – экстраполяции, если начальная точка x 1 Îd(x*).

Начальный этап

Выбрать ε 1 , ε 2 , h.

Взять 3 точки a, b, c на равных на равных интервалах. Предполагается, что сработал метод Свенна и получен интервал .

Основной этап

Найти аппроксимирующий минимум на 1-й итерации по формуле:

на последующих итерациях по формуле:

Проверить критерии близости двух точек:

;

Если он выполняется, принять и остановиться.

Если не выполняется, то из 2-х точек b и d выбрать «лучшую» - в которой наименьшее значение функции, обозначить её как b, а 2 соседние с ней – a и c. Далее рассмотреть 4 ситуации аналогично ЗС-2.

Положить k=k+1 и вернуться на шаг 1.

Метод Давидона

Начальный этап

Выбрать ε, x 0 , p, α 1

Предполагается, что сработал метод Свенна и получен интервал .

Основной этап

Найти аппроксимирующий минимум, т.е. точку d по формулам:

Проверить КОП: если y ` r ≤ ε , то остановиться, х=a+α r p . Иначе: сократить ТИЛ: если y ` r <0, то , если y ` r >0, то .

Положить k=k+1 и вернуться на шаг 1.

Методы многомерной минимизации

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

x – вектор от которого зависит функция

x0 – стартовая точка

p – направление

L – смещение по направлению

Метод Коши

Метод Коши относится к группе методов градиентного спуска. Градиентные методы – это методы, где на каждом шаге выбирается антиградиентное направление спуска.

Начальный этап

Выбрать x1, e, k.

Основной этап

(1) Найти L как результат минимизации функции по направлению p.

(2)

(1) Вычислить новое значение градиента

(2) Проверить КОП: если , то, иначе на Шаг 1.

Метод Циклического покоординатного спуска

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

Начальный этап

Выбрать x1, e, k=1, l=1.

Основной этап

(1) В качестве направления p выбрать , где ненулевая позиция имеет индекс l.

(2) Найти L как результат минимизации функции по направлению p.

(3)

(4) Если l

Описание алгоритма

Метод ориентирован на решение задач с квадратичными целевыми функциями. Основная идея алгоритма заключается в том, что если квадратичная функция:

приводится к виду сумма полных квадратов

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

В методе Пауэлла поиск реализуется в виде:

вдоль направлений, называемых -сопряженными при линейной независимости этих направлений.

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

Шаг 1. Задать исходные точки, и направление. В частности, направление может совпадать с направлением координатной оси;

Шаг 2. Произвести одномерный поиск из точки в направлении получить точку, являющуюся точкой экстремума на заданном направлении;

Шаг 3. Произвести одномерный поиск из точки в направлении получить точку;

Шаг 4. Вычислить направление;

Шаг 5. Провести одномерный поиск из точки (либо) в направлении c выводом в точку.

Нахождение минимума целевой функции методом сопряжённых направлений Пауэлла.

Целевая функция:

Начальная точка:

Значение целевой функции в этой точке:

Шаг 1. Зададим исходные точки S(1) и S(2):

S(1) = S(2) =

Шаг 2. Найдем значение, при [Х(0)+2S(2)]. Произвольная точка на луче из точки Х(0) в направлении S(2) определяется как

Х = Х(0) + S(2) = [-9;-10] +

откуда X 1 = -9 X 2 = - 10

Отсюда находим:

X(1) = [-9;-10] + 15.5 = [-9;5.5]

Аналогично найдем значение, при [Х(1)+S(1)].

Х = Х(1) + S(1) = [-9;5.5] +

откуда X1 = -9 X2 =5.5

Подставляя эти значения в целевую функцию, получаем

Дифференцируем это выражение по и приравниваем нулю:

Отсюда находим:

X(2) = [-9;5.5] + 10.5 =

Также найдем значение, при [Х(2)+2S(2)].

Х = Х(2) + S(2) = +

откуда X 1 = 3 X 2 = 5.5+

Подставляя эти значения в целевую функцию, получаем

Дифференцируем это выражение по и приравниваем нулю:

Отсюда находим:

X(3) = -6 =

Шаг 3. Положим

S(3) = X(3) - X(1) =

Направление S(3) оказывается сопряженным с направлением S(2). Поскольку N = 2, то оптимизация вдоль направления S(3) дает искомый результат. Шаг 4. Найдем такое значение, при

X = X(3) + = +

X 1 = 3+ 12 X 2 = -0.5 -6

Х(4) = +0.0278* =

Таким образом, получили точку х= T , значение функции в которой f(x) = -3,778, совпадает со стационарной точкой.

Вывод: метод сопряженных направлений Пауэлла обеспечивает высокоточный при малом количестве итераций по сравнению с предыдущими методами.

Графическое пояснение метода сопряженных направлений Пауэлла:

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

Метод деформируемого многогранника (метод Нелдера--Мида)

Данный метод состоит в том, что для минимизации функции п переменных f(х) в n-мерном пространстве строится многогранник, содержащий (п + 1) вершину. Очевидно, что каждая вершина соответствует некоторому вектору х. Вычисляются значения целевой функции f(х) в каждой из вершин многогранника, определяются максимальное из этих значений и соответствующая ему вершина х[h]. Через эту вершину и центр тяжести остальных вершин проводится проецирующая прямая, на которой находится точка х[q] с меньшим значением целевой функции, чем в вершине х[h] (Рис. 7.6). Затем исключается вершина х[h]. Из оставшихся вершин и точки x[q] строится новый многогранник, с которым повторяется описанная процедура. В процессе выполнения данных операций многогранник изменяет свои размеры, что и обусловило название метода.

Геометрическая интерпретация метода деформируемого многогранника

Метод Нелдера-Мида.

Пусть - некоторая точка 5-мерного пространства, которая лежит в окрестности минимума. В этом пространстве зададим симплекс (правильный 6-вершинный многогранник), одна из вершин которого лежит в т. . Метод Нелдера-Мида на каждом шаге реали-зует исключение из симплекса точки с самым большим значением функции, заменяя ее некоторой “лучшей” точкой. В результате нахо-дится точка, для которой значение функции минимально (с заданной точностью).

Алгоритм метода реализует следующую последовательность действий.

Вводится симплекс, координаты которого заданы таблицей (одна из вершин в начале координат)

Если, то, в частности, для имеем

Расположение симплекса показано на рис. 7.7.

Легко убедиться в том, что если координаты вершины симплекса задавать в соответствии с матрицей, то расстояние между любыми двумя верши-нами симплекса всегда будет равно выбранной константе t независимо от размерности задачи n. Действительно, расстояние между любой вершиной, и вершиной равно

С другой стороны, расстояние между любой парой вершин,также равно t.

Действительно,

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

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

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

Осуществим отражение вершины относительно центра тяжести. Получим точку. Если то получится зеркальное отражение. Сравним теперь между собой значения. Возможны следующие варианты:

В этом случае выполняется растяжение и отыскивается точка. Параметр обычно принимают равным 1.5. Полученная точка V заменяет, если В противном случае для замены используется точка.

В этом случае реализуется отражение. Точка заменяет.

В этом случае осуществляется сжатие и отыскивается точка. Параметр обычно принимают равным 0.5. Полученная точка заменяет.

При этом осуществляется редукция (уменьшение размера симплекса с подтягиванием всех вершин к). Координаты вершины нового симплекса рассчитываются по формуле

Критерий останова:

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

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

Пусть координаты центра тяжести симплекса образуют вектор

Найдем теперь координаты точки такой, что центр тяжести симплекса с длиной ребра, равной t, использующего вершину в качестве начальной, совпадал бы с.

Матрица координат указанного симплекса имеет вид:

Координаты центра тяжести этого симплекса образуют вектор

Теперь координаты точки найдем из равенства

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