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

Теорема 5.9. Пусть и все выпуклы и функции удовлетворяют условию регулярности Слейтера. Вектор является решением задачи НП (5.3.1), (5.3.2) тогда и только тогда, когда существует такой вектор , что

(5.3.30)

и

(5.3.31)

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

(5.3.15)

(5.3.16)

Определим функцию Лагранжа следующим образом:

(5.3.17)

Тогда теорему Куна-Таккера можно записать в виде

(5.3.18)

(5.3.19)

(5.3.20)

Заметим, что множители Лагранжа в задаче НП с ограничениями-равенствами являются знаконеопределенными, тогда как в теореме Куна-Таккера они должны быть положительными.

Каждой задаче линейного программирования соответствует двойственная задача. Двойственная задача по отношению к исходной задаче строится по следующим правилам:

· Если исходная задача ставится на максимум, то двойственная ставится на минимум и наоборот.

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

· Если A-матрица коэффициентов исходной задачи, то транспонированная матрица T A будет матрицей коэффициентов двойственной задачи.

· В задаче на максимум все ограничения имеют знак ≤ (=), а в задаче на минимум все ограничения имеют знак ≥ .

· Число переменных в двойственной задаче равно числу ограничений в исходной задаче. Каждому ограничению исходной задачи соответствует переменная двойственной задачи. Если ограничение исходной задач имеет знак (≥ ), то соответствующая переменная двойственной задачи неотрицательна. Если ограничение имеет знак (=), то соответствующая переменная двойственной задачи может принимать положительные и отрицательные значения и наоборот.

Градиентные методы гладкой оптимизации. Общая идея градиентного спуска (подъема). Пропорциональный градиентный метод. Полношаговый градиентный метод. Метод сопряженных градиентов.

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

Градиентом дифференцируемой функции f(x) в точке х [0] называется n -мерный вектор f(x [0]) , компоненты которого являются частными производными функции f(х), вычисленными в точке х [0], т. е.

f'(x [0]) = (дf(х [0])/дх ₁ , …, дf(х [0])/дх_n )^T .

Этот вектор перпендикулярен к плоскости, проведенной через точку х [0] , и касательной к поверхности уровня функции f(x), проходящей через точку х [0] .В каждой точке такой поверхности функция f(x) принимает одинаковое значение. Приравнивая функцию различным постоянным величинам С₀ , С₁ , ... , получим серию поверхностей, характеризующих ее топологию

Вектор-градиент направлен в сторону наискорейшего возрастания функции в данной точке. Вектор, противоположный градиенту (-f’(х [0])) , называется антиградиентом и направлен в сторону наискорейшего убывания функции. В точке минимума градиент функции равен нулю. На свойствах градиента основаны методы первого порядка, называемые также градиентным и методами минимизации. Использование этих методов в общем случае позволяет определить точку локального минимума функции.

Очевидно, что если нет дополнительной информации, то из начальной точки х [0] разумно перейти в точку х [1], лежащую в направлении антиградиента - наискорейшего убывания функции. Выбирая в качестве направления спуска р [k ] антиградиент -f’(х [k]) в точке х [k ], получаем итерационный процесс вида

х [k+ 1] = x [k ]-a_k f'(x [k]) , а _k > 0; k =0, 1, 2, ...

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

x_i [k +1]=х _i [k ] - a_k f(x [k]) /x_i