Теоретические основы математических и инструментальных методов экономики (стр. 4 из 22)
x[k+l] = x[k] +akp[k],
p[k] = -f’(x[k])+bk-1p[k-l], k >= 1;
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 делится пополам, через фиксированное число итераций, зависящее от размерности задачи.
Элементы функционального анализа. Метрические, линейные и нормированные пространства. Эвклидово пространство. Гильбертово пространство. Линейные операторы и функционалы в линейных нормированных пространствах
Функциональный анализ, часть современной математики, главной задачей которой является изучение бесконечномерных пространств и их отображений. Наиболее изучены линейные пространства и линейные отображения. Для Ф. а. характерно сочетание методов классического анализа, топологии и алгебры. Абстрагируясь от конкретных ситуаций, удаётся выделить аксиомы и на их основе построить теории, включающие в себя классические задачи как частный случай и дающие возможность решать новые задачи. Сам процесс абстрагирования имеет самостоятельное значение, проясняя ситуацию, отбрасывая лишнее и открывая неожиданные связи. В результате удаётся глубже проникнуть в сущность математических понятий и проложить новые пути исследования.
Развитие Ф. а. происходило параллельно с развитием современной теоретической физики, при этом выяснилось, что язык Ф. а. наиболее адекватно отражает закономерности квантовой механики, квантовой теории поля и т.п. В свою очередь эти физические теории оказали существенное влияние на проблематику и методы Ф. а.