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

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

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

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

.

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

.

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

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

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

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

Алгоритм.

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

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

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

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

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

(*)

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

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

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

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

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

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

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

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

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

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

Этот метод основан на последовательном применении процедуры оценивания с использованием квадратичной аппроксимации.

Назначение сервиса . Онлайн-калькулятор предназначен для нахождения минимума функции методом Пауэлла (см. также калькулятор для двух переменных). Решение оформляется в формате Word .

f(x) =

Начиная из точки x 0 = . Точность ξ =
Шаг приращения h = .
Множитель приращения a = .

Правила ввода функций :

Схема алгоритма Пауэлла

пусть x 1 - начальная точка; Δx- выбранная величина шага по оси х .
Шаг 1: Вычислить x 2 =x 1 +Δx.
Шаг 2: Вычислить f(x 1) и f(x 2).
Шаг 3: Если f(x 1)>f(x 2), положить x 3 =x 1 +2Δx, если f(x 1)≤f(x 2), то x 3 =x 1 -Δx.
Шаг 4: Вычислить f(x 3) и найти F min = min{f 1 , f 2 , f 3 }
X min равно точке x i , которая соответствует F min .
Шаг 5: По трем точкам x 1 , x 2 , x 3 вычислить , используя квадратичную аппроксимацию.




а) является ли разность ;
б) является ли разность ,
где ε>0 и δ>0 - заданные точности.
Если условия а) и б) выполняются одновременно, то закончить поиск. Иначе переход на Шаг 7.
Шаг 7: Выбрать "наилучшую" точку (X min или ) и две точки по обе стороны от нее. Обозначить эти точки в естественном порядке и перейти на Шаг 4.
Замечание : после пятого шага необходимо провести дополнительную проверку, т.к. точка может находиться за точкой x 3 . В этом случае точка заменяется точкой, координата которой вычисляется c учетом заранее установленной длины шага.
Пусть полученная точка x лежит вне отрезка интерполяции. Смысл здесь заключается в следующем. О характере функции, в общем случае, ничего неизвестно, но при помощи аппроксимации происходит замена ее по трем точкам параболой (на рисунке обозначена пунктиром). Вид параболы полностью определяется выбранными точками. Если точки выбраны неудачно, то минимум параболы может оказаться весьма далеко от минимума функции. Причем, если у функции имеются несколько локальных минимумов, в итоге можно найти не тот минимум, что является ближайшим к начальной точке. Применение же вышеописанного правила предотвращает подобную ситуацию.

Пример . Найти .
Пусть начальная точка x 1 =1 и длина шага Δx=1.
Критерии останова:

Замечание. Оба критерия должны выполняться одновременно.
Итерация 1:
Шаг 1: x 2 =x 1 + Δx =2
Шаг 2: f(x 1)=18; f(x 2)=16
Шаг 3: f(x 1)>f(x 2), следовательно x 3 =1+2 = 3;
Шаг 4: f(x 3)=23.33;F min =16; X min =x 2 .
Шаг 5:

Вычислим :

Шаг 6: Проверка на окончание поиска:
а) . Критерий останова не выполняется, следовательно поиск продолжается. Переход на Шаг 7.
Шаг 7: Выбираем как "наилучшую" точку, а x 1 =1, x 2 =2 – как точки, которые ее окружают. Обозначим эти точки в естественном порядке и переходим к Шагу 4.
Итерация 2:
Шаг 4: x 1 =1; f 1 =18; x 2 =1.714, f 2 =15.21 = F min ;
X min = x 2 = 1.714, x 3 = 2; f 3 = 16
Шаг 5:


Шаг 6: Проверка на окончание поиска: а) .
Первый критерий останова не выполняется. Переход на Шаг 7.
Шаг 7: Выбираем как "наилучшую" точку, а x 1 = 1, x 2 = 1,714 – как точки, которые ее окружают. Обозначим эти точки в естественном порядке и переходим к Шагу 4.
Итерация 3:
Шаг 4:
x 1 = 1, f 1 = 18; x 2 = 1.65; f 2 = 15.142; = F min ; X min = x 2 = 1.65
x 3 = 1.174; f 3 = 15.21
Шаг 5:


Шаг 6: Проверка на окончание поиска:
а) б)
Оба критерия останова выполняются, следовательно, поиск закончен.
Ответ: (точное решение x=1.5874).

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

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

, (7)

Сопряженность связана с ортогональностью. Если Н – единичная матрица, то при
имеем два взаимно перпендикулярных вектора. Соотношение (7) можно трактовать таким образом: матрица Н, примененная к вектору, изменяет его длину и поворачивает на некоторый угол так, что новый вектор
должен быть ортогонален вектору.

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

1) Производится выбор и в этом направлении отыскивается экстремум.

Возьмем вектор с направлениямии. Векторможно выбирать произвольно, поэтому возьмем==1. Вектордает направлениеL 1 .

Проведем через L 1 плоскость перпендикулярную плоскости {x 1 ,x 2 }. Плоскость пересечет экстремальную поверхность у(х 1 , х 2) и выделит на ней экстремальную линию. Определим координаты минимума на этой линии (параболе), для чего вычислим проекции градиента в точке х 0:

,

и по формуле (6) найдем :

Естественно, линия L 1 касается в точке х (1) линии равного уровня функции у.

2) Отыскивается из условия сопряженности
.

Получим сопряженный вектор с проекциями
и
, воспользовавшись формулой (7):

П
олучили одно уравнение с двумя неизвестными. Т.к. нам требуется только направление вектора, а не его длина, то одним из неизвестных можно задаться произвольно. Пусть
=1, тогда
= –4.

3) Из точки х (1) в направлении ищется экстремум.

Сопряженный вектор должен проходить через х (1) . Сделаем шаг в сопряженном направлении:

Величина шага  (1) в х (1) :

,

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

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

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

Классическая задача Лагранжа на условный экстремум (ограничения-равенства).

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

Рассмотрим геометрическую интерпретацию классической задачи. На плоскости {x 1 ,x 2 } построим функцию
, а также линии равного уровня функции
со значениямиN 1 , линияN 3 имеет 2 общих точки с
и они не могут быть решением задачи, т.к.N 3 >N 2 . Остается линия уровняN 2 , которая имеет единственную точку касания с
. Абсолютный минимумN 0 может не принадлежать ограничению
и поэтому не может быть решением задачи. Отсюда ясно и название «условный экстремум», т.е. такой экстремум, который достигается только на заданных ограничениях.

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

Из подобия треугольников можно записать:

–множитель Лагранжа.

или

Составим теперь функцию
следующим образом:

–функция Лагранжа.

Запишем соотношения для нахождения экстремума функции F.

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

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

или в векторной форме

Для решения задачи записывается система уравнений:

, (8)

т.е. для n+mпеременных будем иметьn+mуравнений. Если система совместна, то задача Лагранжа имеет единственное решение.

Т.к. для определения экстремума использовались только первые производные, то полученные условия будут являться только необходимыми. Если функции
и
выпуклые или вогнутые, то условный экстремум единственный. Если одна из функций невыпуклая, то экстремум может быть и не единственным. Кроме того, открыт вопрос о том, что найдено – минимум или максимум, хотя в инженерной практике обычно из физических соображений это бывает ясно.

Пример: Покажем технику решения задачи методом Лагранжа.

Д
ля рассмотренного выше примера с двумя насосами, задан объем перекачиваемой жидкости:

При этом ограничении требуется найти потребляемую мощность насосов
. Пусть коэффициенты равны 1 = 2 =1, К 1 =1, К 2 =1,5. Тогда целевая функция, найти минимум при ограничении:.

Процедура решения:

Составляем функцию Лагранжа

Составляется система уравнений (8):

Записываются Q i черези подставляются в третье выражение:

,
,
,

Тогда координаты экстремума:

,

Пример 2:

Пусть дано последовательное соединение компрессоров.
Задана требуемая степень сжатия:, которую требуется обеспечить при минимуме расхода мощности:

2.

3.
,
, подставляем в выражение для:

,
,
. Из физических соображений положительный корень отбрасываем, поэтому= –0,98.

Тогда координаты экстремума:

,

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

Шаг 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.

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

Данный метод состоит в том, что для минимизации функции п переменных 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), получим требуемый симплекс, используя который продолжим процедуру поиска минимума. Эту процедуру считаем законченной, если после очередного сжатия алгоритм приведет в точку, расстояние от которой до точки предыдущего сжатия не превосходит некоторого, достаточно малого.