Метод сопряженных градиентов
Рассмотренные выше градиентные методы отыскивают точку минимума функции в общем случае лишь за бесконечное число итераций. Метод сопряженных градиентов формирует направления поиска, в большей мере соответствующие геометрии минимизируемой функции. Это существенно увеличивает скорость их сходимости и позволяет, например, минимизировать квадратичную функцию
f(x) = (х, Нх) + (b, х) + а
с симметрической положительно определенной матрицей Н за конечное число шагов п , равное числу переменных функции. Любая гладкая функция в окрестности точки минимума хорошо аппроксимируется квадратичной, поэтому методы сопряженных градиентов успешно применяют для минимизации и неквадратичных функций. В таком случае они перестают быть конечными и становятся итеративными.
По определению, два n-мерных вектора х и у называют сопряженными по отношению к матрице H (или H-сопряженными), если скалярное произведение (x, Ну) = 0. Здесь Н - симметрическая положительно определенная матрица размером пхп.
Одной из наиболее существенных проблем в методах сопряженных градиентов является проблема эффективного построения направлений. Метод Флетчера-Ривса решает эту проблему путем преобразования на каждом шаге антиградиента -f(x[k]) в направление p[k], H-сопряженное с ранее найденными направлениями р[0], р[1], ..., р[k-1]. Рассмотрим сначала этот метод применительно к задаче минимизации квадратичной функции.
Направления р[k] вычисляют по формулам:
p[k] = -f’(x[k])+bk-1p[k-l], k >= 1;
p[0] = -f’(x[0]).
Величины bk-1 выбираются так, чтобы направления p[k], р[k-1] были H-сопряженными:
(p[k], Hp[k-1])= 0.
В результате для квадратичной функции
,
итерационный процесс минимизации имеет вид
x[k+l] =x[k] +akp[k],
где р[k] - направление спуска на k-м шаге; аk - величина шага. Последняя выбирается из условия минимума функции f(х) по а в направлении движения, т. е. в результате решения задачи одномерной минимизации:
f(х[k] + аkр[k]) = f(x[k] + ар [k]).
Для квадратичной функции
Алгоритм метода сопряженных градиентов Флетчера-Ривса состоит в следующем.
1. В точке х[0] вычисляется p[0] = -f’(x[0]).
2. На k-м шаге по приведенным выше формулам определяются шаг аk. и точка х[k+1].
3. Вычисляются величины f(x[k+1]) и f’(x[k+1]).
4. Если f’(x[k+1]) = 0, то точка х[k+1] является точкой минимума функции f(х). В противном случае определяется новое направление p[k+l] из соотношения
и осуществляется переход к следующей итерации. Эта процедура найдет минимум квадратичной функции не более чем за п шагов. При минимизации неквадратичных функций метод Флетчера-Ривса из конечного становится итеративным. В таком случае после (п+1)-й итерации процедуры 1-4 циклически повторяются с заменой х[0] на х[п+1] , а вычисления заканчиваются при , где - заданное число. При этом применяют следующую модификацию метода:
x[k+l] = x[k] +akp[k],
p[0] = -f’(x[0]);
f(х[k] + akp[k]) = f(x[k] + ap[k];
.
Здесь I- множество индексов: I = {0, n, 2п, Зп, ...}, т. е. обновление метода происходит через каждые п шагов.
Геометрический смысл метода сопряженных градиентов состоит в следующем (Рис. 2.11). Из заданной начальной точки х[0] осуществляется спуск в направлении р[0] = -f'(x[0]). В точке х[1] определяется вектор-градиент f'(x [1]). Поскольку х[1] является точкой минимума функции в направлении р[0], то f’(х[1]) ортогонален вектору р[0]. Затем отыскивается вектор р [1], H-сопряженный к р [0] . Далее отыскивается минимум функции вдоль направления р[1] и т. д.
Рис. 2.11. Траектория спуска в методе сопряженных градиентов
Методы сопряженных направлений являются одними из наиболее эффективных для решения задач минимизации. Однако следует отметить, что они чувствительны к ошибкам, возникающим в процессе счета. При большом числе переменных погрешность может настолько возрасти, что процесс придется повторять даже для квадратичной функции, т. е. процесс для нее не всегда укладывается в п шагов.
Основная задача выпуклого программирования
Пусть задано выпуклое и замкнутое множество . Рассмотрим множество
={}, =(,…,), Î.
где () — вогнутые (выпуклые вверх) непрерывные на скалярные функции. В теории математического программирования каждый элемент Î принято называть допустимым планом, а само множество — множеством допустимых планов.
Формальная постановка задачи выпуклого программирования
Задачу
где выпукла, а определяется вышеприведенными условиями, называется основной задачей выпуклого программирования.
Определение означает, что ставится задача:
Если существует минимальное значение функции на множестве , то среди всех допустимых планов найти оптимальный план , для которого
==
при этом число называют значением задачи.
Если оптимального плана не существует, то требуется
· либо найти значение задачи как точную нижнюю грань значений функции на множестве :
=
· либо убедиться, что неограничена снизу на множестве ;
· либо убедиться в том, что множество допустимых планов пусто.
Для решения предложенной оптимизационной задачи следует выполнить следующие действия:
· Определить множество .
· Определить вектор-функцию =(,…,) и вектор Î.
· Определить множество допустимых планов ={}.
· Привести задачу к стандартной форме основной задачи выпуклого программирования и определить оптимизируемую функцию .
· Проверить, является ли полученная оптимизационная задача ЗВП, для этого
· проверить на выпуклость множество ;
· проверить на выпуклость функцию .
В случае успеха п. 5
· Построить функцию Лагранжа полученной ЗВП.
· С помощью дифференциальных условий Куна-Таккера найти седловые точки построенной функции Лагранжа.
В случае неудачи п. 5 попытаться найти другие методы решения задачи.
Методы субградиентной оптимизации. Эти итеративные процедуры формируют последовательность векторов {lk}. Начиная с некоторого начального значения l0 эти вектора меняются по следующему правилу
lk+1 = lk + tk (A xk - b),
где xk — оптимальное решение задачи , а tk — размер шага. Фундаментальный теоретический результат заключается в том, что [14]
Размер шага на практике обычно выбирают, следуя [11],
где q k — скаляр, 0 < q k 2 и z* — верхняя граница для n(D). Обычно z* получают эвристикой для P. В методе ветвей и границ z* — текущий рекорд. Последовательность q k, как правило, начинается с q 0=2 и затем q k делится пополам, через фиксированное число итераций, зависящее от размерности задачи.
Функциональный анализ, часть современной математики, главной задачей которой является изучение бесконечномерных пространств и их отображений. Наиболее изучены линейные пространства и линейные отображения. Для Ф. а. характерно сочетание методов классического анализа, топологии и алгебры. Абстрагируясь от конкретных ситуаций, удаётся выделить аксиомы и на их основе построить теории, включающие в себя классические задачи как частный случай и дающие возможность решать новые задачи. Сам процесс абстрагирования имеет самостоятельное значение, проясняя ситуацию, отбрасывая лишнее и открывая неожиданные связи. В результате удаётся глубже проникнуть в сущность математических понятий и проложить новые пути исследования.
Развитие Ф. а. происходило параллельно с развитием современной теоретической физики, при этом выяснилось, что язык Ф. а. наиболее адекватно отражает закономерности квантовой механики, квантовой теории поля и т.п. В свою очередь эти физические теории оказали существенное влияние на проблематику и методы Ф. а.
1. Линейные пространства. Базис
Одно из основных понятий современной математики - линейное пространство.
Пусть L - некоторое множество объектов произвольной природы, а C - множество комплексных чисел. Множество L называют линейным пространством, если на нем определены две операции: 1) операция сложения любых двух элементов этого множества и 2) операция умножения элементов этого множества на комплексное число, причем эти операции удовлетворяют некоторым естественным аксиомам. Более точно:
Определение. Множество L называется линейным пространством над полем комплексных чисел C, если
Подчеркнем, что перечисленные аксиомы являются естественным обобщением хорошо известных свойств сложения и умножения чисел, сложения векторов и их умножения на число и т.д.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
