Xreferat.com » Рефераты по экономико-математическому моделированию » Теоретические основы математических и инструментальных методов экономики

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

функции φ(a) = f(x[k] - af'(x[k])). Необходимое условие минимума функции dj(a)/da = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:

dj(a)/da = -f’(x[k+1]f’(x[k]) = 0.

Градиентные методы сходятся к минимуму с высокой скоростью (со скоростью геометрической прогрессии) для гладких выпуклых функций. У таких функций наибольшее М и наименьшее m собственные значения матрицы вторых производных (матрицы Гессе)

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

мало отличаются друг от друга, т. е. матрица Н(х) хорошо обусловлена. Напомним, что собственными значениями li, i =1, …, n, матрицы являются корни характеристического уравнения

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

Однако на практике, как правило, минимизируемые функции имеют плохо обусловленные матрицы вторых производных (т/М << 1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются, а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными. Направление антиградиента этих функций (см. Рис. 2.10) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.

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

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

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. Траектория спуска в методе сопряженных градиентов

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

Выпуклая оптимизация. Условие выпуклости. Субградиентный метод выпуклой оптимизации. Метод растяжения пространства. Метод эллипсоидов.

Основная задача выпуклого программирования

Пусть задано выпуклое и замкнутое множество Теоретические основы математических и инструментальных методов экономики. Рассмотрим множество

Теоретические основы математических и инструментальных методов экономики={Теоретические основы математических и инструментальных методов экономики}, Теоретические основы математических и инструментальных методов экономики=(Теоретические основы математических и инструментальных методов экономики,…,Теоретические основы математических и инструментальных методов экономики), Теоретические основы математических и инструментальных методов экономикиОТеоретические основы математических и инструментальных методов экономики.

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

Формальная постановка задачи выпуклого программирования

Задачу

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

где Теоретические основы математических и инструментальных методов экономики выпукла, а Теоретические основы математических и инструментальных методов экономики определяется вышеприведенными условиями, называется основной задачей выпуклого программирования.

означает, что ставится задача:

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

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

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

Если оптимального плана не существует, то требуется

либо найти значение задачи как точную нижнюю грань значений функции Теоретические основы математических и инструментальных методов экономики на множестве Теоретические основы математических и инструментальных методов экономики:

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

либо убедиться, что Теоретические основы математических и инструментальных методов экономики неограничена снизу на множестве Теоретические основы математических и инструментальных методов экономики;

либо убедиться в том, что множество допустимых планов Теоретические основы математических и инструментальных методов экономики пусто.


Для решения предложенной оптимизационной задачи следует выполнить следующие действия:

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

Определить вектор-функцию Теоретические основы математических и инструментальных методов экономики=(Теоретические основы математических и инструментальных методов экономики,…,Теоретические основы математических и инструментальных методов экономики) и вектор Теоретические основы математических и инструментальных методов экономикиОТеоретические основы математических и инструментальных методов экономики.

Определить множество допустимых планов Теоретические основы математических и инструментальных методов экономики={Теоретические основы математических и инструментальных методов экономики}.

Привести задачу к стандартной форме основной задачи выпуклого программирования и определить оптимизируемую функцию Теоретические основы математических и инструментальных методов экономики.

Проверить, является ли полученная оптимизационная задача ЗВП, для этого

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

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

В случае успеха п. 

Построить функцию Лагранжа полученной ЗВП.

С помощью дифференциальных условий Куна-Таккера найти седловые точки построенной функции Лагранжа.

В случае неудачи п.  попытаться найти другие методы решения задачи.

Методы субградиентной оптимизации. Эти итеративные процедуры формируют последовательность векторов {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, если

каждой паре элементов x, y из этого пространства поставлен в соответствие элемент z этого пространства, называемый суммой элементов x и y (обозначение: Теоретические основы математических и инструментальных методов экономики);

каждому элементу x из L и каждому комплексному числу поставлен в соответствие элемент из L, называемый произведением и x (и обозначаемый Теоретические основы математических и инструментальных методов экономикиили x);

указанные операции удовлетворяют следующим аксиомам:

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

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

существует "нулевой" элемент Теоретические основы математических и инструментальных методов экономики, такой, что Теоретические основы математических и инструментальных методов экономикидля любого Теоретические основы математических и инструментальных методов экономики,

для каждого Теоретические основы математических и инструментальных методов экономикисуществует "противоположный" ему элемент Теоретические основы математических и инструментальных методов экономики, такой, что Теоретические основы математических и инструментальных методов экономики,

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

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

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

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

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

Иногда рассматривают линейное пространство не над полем комплексных, а над полем действительных чисел R (т.е. вместо операции умножения на комплексные числа рассматривается операция умножения на действительные числа). Аксиомы линейного пространства при этом не меняются.

Приведем некоторые типичные примеры линейных пространств.

Пример 1. Линейное пространство векторов на плоскости (или в трехмерном пространстве) с обычными операциями сложения векторов и умножения вектора на действительное число. Нулевым элементом является нулевой вектор.

Пример 2. Линейное пространство всевозможных последовательностей комплексных чисел с операциями

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

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

Нулевой элемент - последовательность (0, 0, ..., 0, ...).

Пусть теперь Теоретические основы математических и инструментальных методов экономики- некоторые элементы линейного пространства L, а Теоретические основы математических и инструментальных методов экономики- произвольные комплексные (или действительные) числа. Элемент пространства L, равный Теоретические основы математических и инструментальных методов экономики, называется линейной комбинацией элементов Теоретические основы математических и инструментальных методов экономики.

Определение. Система (набор) элементов Теоретические основы математических и инструментальных методов экономикипространства L называется линейно независимой, если линейная комбинация Теоретические основы математических и инструментальных методов экономикиравна нулевому элементу пространства только в случае Теоретические основы математических и инструментальных методов экономики.

Иными словами, система Теоретические основы математических и инструментальных методов экономикиназывается линейно независимой, если из равенства Теоретические основы математических и инструментальных методов экономикиследует, что Теоретические основы математических и инструментальных методов экономики.

Определение. Система элементов Теоретические основы математических и
    <div class=

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: