Теоретические основы математических и инструментальных методов экономики

Метод сопряженных градиентов

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

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[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, как правило, начинается с 0=2 и затем q k делится пополам, через фиксированное число итераций, зависящее от размерности задачи.

Элементы функционального анализа. Метрические, линейные и нормированные пространства. Эвклидово пространство. Гильбертово пространство. Линейные операторы и функционалы в линейных нормированных пространствах

Функциональный анализ, часть современной математики, главной задачей которой является изучение бесконечномерных пространств и их отображений. Наиболее изучены линейные пространства и линейные отображения. Для Ф. а. характерно сочетание методов классического анализа, топологии и алгебры. Абстрагируясь от конкретных ситуаций, удаётся выделить аксиомы и на их основе построить теории, включающие в себя классические задачи как частный случай и дающие возможность решать новые задачи. Сам процесс абстрагирования имеет самостоятельное значение, проясняя ситуацию, отбрасывая лишнее и открывая неожиданные связи. В результате удаётся глубже проникнуть в сущность математических понятий и проложить новые пути исследования.

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

1. Линейные пространства. Базис

Одно из основных понятий современной математики - линейное пространство.

Пусть L - некоторое множество объектов произвольной природы, а C - множество комплексных чисел. Множество L называют линейным пространством, если на нем определены две операции: 1) операция сложения любых двух элементов этого множества и 2) операция умножения элементов этого множества на комплексное число, причем эти операции удовлетворяют некоторым естественным аксиомам. Более точно:

Определение. Множество L называется линейным пространством над полем комплексных чисел C, если

  1. каждой паре элементов x, y из этого пространства поставлен в соответствие элемент z этого пространства, называемый суммой элементов x и y (обозначение: );
  2. каждому элементу x из L и каждому комплексному числу поставлен в соответствие элемент из L, называемый произведением и x (и обозначаемый или x);
  3. указанные операции удовлетворяют следующим аксиомам:
  4. для любых ,
  5. для любых ,
  6. существует "нулевой" элемент , такой, что для любого ,
  7. для каждого существует "противоположный" ему элемент , такой, что ,
  8. для любого ,
  9. для любого и любых ,
  10. для любого и любых ,
  11. для любого и любых .

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17



Реклама
В соцсетях
рефераты скачать рефераты скачать рефераты скачать рефераты скачать рефераты скачать рефераты скачать рефераты скачать