Метод ориентирован на решение задач с квадратичными целевыми функциями и основывается на фундаментальных теоретических результатах. Хотя используемые в реальных ситуациях алгоритмы, являющиеся эффективными для квадратичных целевых функций, могут плохо работать при более сложных целевых функциях, тем не менее этот подход представляется вполне разумным.
Определение
.
Пусть
-
симметрическая матрица порядка
.
Векторы
называются
-
сопряженными, если они линейно независимы
и выполняется условие
при
.
Пример. Рассмотрим функцию
В
качестве матрицы
можно взять матрицу Гессе
.
В
качестве одного из направлений выберем
.
Тогда направление
должно удовлетворять равенству
.
Следует заметить, что сопряженные направления выбираются неоднозначно. Однако если добавить условие нормировки, то их можно определить однозначно:
Утверждение.
Любая квадратичная функция
переменных, имеющая минимум, может быть
минимизирована за
шагов, при условии, что поиск ведется
вдоль сопряженных относительно матрицы
Гессе направлений
.
Произвольная
функция может быть достаточно хорошо
представлена в окрестности оптимальной
точки ее квадратичной аппроксимацией.
Поэтому сопряженные направления могут
быть полезны для ее оптимизации. Однако
потребуется более чем
шагов. Для определения сопряженных
направлений применяется способ,
основанный на следующем утверждении.
Утверждение.
Пусть задана квадратичная функция
,
две произвольные точки
и направление
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.
Подобные документы
Рассмотрение эффективности применения методов штрафов, безусловной оптимизации, сопряженных направлений и наискорейшего градиентного спуска для решения задачи поиска экстремума (максимума) функции нескольких переменных при наличии ограничения равенства.
контрольная работа , добавлен 16.08.2010
Анализ теорем сопряженных функторов. Естественное преобразование как семейство морфизмов. Характеристика свойств рефлективных подкатегорий. Знакомство с универсальными стрелками. Рассмотрение особенностей метода построения сопряженных функторов.
курсовая работа , добавлен 27.01.2013
Методика преобразования вращения и ее значение в решении алгебраических систем уравнений. Получение результирующей матрицы. Ортогональные преобразования отражением. Итерационные методы с минимизацией невязки. Решение методом сопряженных направлений.
реферат , добавлен 14.08.2009
Методы решения систем линейных алгебраических уравнений, их характеристика и отличительные черты, особенности и сферы применения. Структура метода ортогонализации и метода сопряженных градиентов, их разновидности и условия, этапы практической реализации.
курсовая работа , добавлен 01.10.2009
Численные методы поиска безусловного экстремума. Задачи безусловной минимизации. Расчет минимума функции методом покоординатного спуска. Решение задач линейного программирования графическим и симплексным методом. Работа с программой MathCAD.
курсовая работа , добавлен 30.04.2011
Формирование функции Лагранжа, условия Куна и Таккера. Численные методы оптимизации и блок-схемы. Применение методов штрафных функций, внешней точки, покоординатного спуска, сопряженных градиентов для сведения задач условной оптимизации к безусловной.
курсовая работа , добавлен 27.11.2012
Математическая модель задачи. Решение транспортной задачи методом потенциалов. Значение целевой функции. Система, состоящая из 7 уравнений с 8-ю неизвестными. Решение задач графическим методом. Выделение полуплоскости, соответствующей неравенству.
контрольная работа , добавлен 12.06.2011
Методы нахождения минимума функции одной переменной и функции многих переменных. Разработка программного обеспечения вычисления локального минимума функции Химмельблау методом покоординатного спуска. Поиск минимума функции методом золотого сечения.
курсовая работа , добавлен 12.10.2009
Решение систем линейных алгебраических уравнений методом простой итерации. Полиномиальная интерполяция функции методом Ньютона с разделенными разностями. Среднеквадратическое приближение функции. Численное интегрирование функций методом Гаусса.
курсовая работа , добавлен 14.04.2009
Основные сведения о симплекс-методе, оценка его роли и значения в линейном программировании. Геометрическая интерпретация и алгебраический смысл. Отыскание максимума и минимума линейной функции, особые случаи. Решение задачи матричным симплекс-методом.
Рассмотрим задачу о нахождении максимума квадратичной функции
где и – -мерные векторы евклидова пространства , – положительно определенная квадратичная форма, задаваемая матрицей .
Сначала заметим, что градиент функции равен и точка максимума функции может быть найдена из уравнения
Выводимые ниже алгоритмы позволяют отыскивать максимум, минуя решение системы линейных уравнений или получение обратной матрицы. Напротив, эти алгоритмы могут быть использованы для решения систем уравнений.
1. Рассмотрим сначала процесс, отнюдь не являющийся алгоритмом для нахождения минимума квадратичной функции, но из которого легко следуют весьма эффективные алгоритмы – метод сопряженных градиентов и метод параллельных касательных.
Пусть – произвольная точка
пространства .
Обозначим –
градиент функции в
точке .
Пусть –
одномерное гиперпространство, прямая, проходящая через в направлении , т. е. иными
словами, множество векторов вида 
.
Найдем точку , в которой достигается условный максимум функции на прямой . Продолжим это построение по индукции. Пусть уже построено -мерное гиперпространство и в нем найдена точка , в которой функция достигает условного максимума.
Обозначим градиент функции в точке . Примем, далее, за гиперпространство пространство, натянутое на и прямую, проходящую через в направлении . Пространство состоит из векторов вида
где , а скаляр пробегает значения от до .
Наконец, – это точка, в которой достигает условного максимума на пространстве . Таким образом, получаем такие последовательности:
По индукции легко показывается, что гиперпространство может рассматриваться как множество векторов вида
,
где – градиенты функции в точках , а принимают любые действительные значения. Отсюда, очевидно, следует, что при .
2. Из анализа известно, что если гладкая функция достигает условного экстремума на некотором гиперпространстве в точке , то градиент функции в этой точке ортогонален гиперпространству. Применительно к нашему построению отсюда следует, что ортогонален всякому вектору вида , где и принадлежат , т. е.
при
. (16.2)
В частности, векторы и при принадлежат в силу (16.1), откуда
а следовательно, и вообще
При . (16.3)
Отсюда следует, что если , то вектор невыразим линейно через и поэтому пространство имеет размерность на 1 большую, чем .
Таким образом, размерность пространства последовательно нарастает с ростом до тех пор, пока не обратится в нуль. Но последнее означает, что в точке достигнут уже абсолютный максимум . Действительно, поскольку – выпуклая гладкая функция, то обращение в нуль ее градиента является необходимым и достаточным условием максимума.
После обращения в нуль процесс зацикливается, потому что при этом совпадает с , соответственно – с и т. д. Поэтому в дальнейшем будем считать, что процесс обрывается, как только обратится в нуль, и тем самым будет установлено, что точка , найденная на предыдущем шаге, доставляет абсолютный максимум во всем пространстве . В то же время это обязательно должно произойти при , так как если при градиент не обращается в нуль, то размерность гиперпространства , увеличиваясь каждый раз на 1, на -м шаге достигнет размерности всего пространства , т. е. совпадает с , и тем самым условный максимум на , естественно, совпадет с абсолютным.
Рассмотренный процесс, конечно, не является удобным алгоритмом, для нахождения максимума, так как формально на каждом шаге требуется находить условный максимум в пространствах последовательно нарастающей размерности вплоть до полной размерности всего пространства. Однако оказывается, что в действительности можно искать условный максимум на каждом шаге в гиперпространстве размерности 2, т. е. на обыкновенных двумерных гиперплоскостях, или даже в гиперпространстве размерности 1, т. е. на прямой.
3. Для обоснования этого положения установим следующие факты. Обозначим через вектор , т. е. смещение от условного максимума в , к условному максимуму .
В самом деле, процесс продолжается лишь до тех пор, пока не обратится в нуль. Поэтому достаточно показать что при . Поскольку градиент функции в точке не равен нулю, функция возрастает при движении вдоль прямой из точки по крайней мере при малых . Следовательно, на этой прямой есть точки, в которых больше, чем . Но эта прямая принадлежит и, следовательно, и подавно больше, чем , т. е.
. (16.5)
Отсюда ясно, что и (16.4) верно. Из (16.5) также следует, что
б) Векторы и при ортогональны относительно матрицы , т. е.
При . (16.6)
Поскольку матрица симметрична,
.
.
После очевидного преобразования получим
Окончательно,
в) Система векторов линейно независима, т. е. не существует чисел , не все из которых равны нулю, таких, что
В самом деле, предположим противное, и пусть, например, . Тогда
где положено
Умножая справа и слева это равенство на , получим в силу (16.6)
но это невозможно, поскольку (утверждение а)) и квадратичная форма положительно определена.
г) Утверждения б) и в) устанавливают, что векторы образуют -ортогональный базис. В силу известных теорем линейной алгебры отсюда следует, что всякий вектор пространства представим в виде
. (16.7)
Это
утверждение можно доказать и непосредственно по индукции. Для утверждение
очевидно, так как всякая точка прямой может быть представлена и в виде 
, если учесть, что , так же как и , лежит на этой
прямой и .
В общем случае предположим, что (16.7) верно для , т. е. всякий вектор вида может быть заменен поиском максимума на
плоскости или на прямой.
