Метод ньютона

Пусть функция f (x) дважды дифференцируема в En. Тогда для нее можно записать разложение по формуле Тейлора в окрестности точки xk:

f (x) = f (хk) + < f '(хk), x–xk > + < f ¢¢(хk)(x–xk), x–xk > +o (|| x–xk ||2)

Отсюда видно, что поведение функции f (x) с точностью до величины порядка o(|| x–xk ||2) может быть описано квадратичной функцией

Фk(x) = < f ¢¢(хk)(x–xk), x–xk > + < f '(хk), x–xk > + f (хk). (3.68)

Минимизируем функцию Фk(x) вместо f (x). Найдем ее точку минимума xk+1 из условия Ф¢k(x) = 0:

Ф¢k(x) = f ¢¢(хk)(x–xk) + f ¢(хk) = 0. (3.69)

Пусть матрица Гессе f ¢¢(хk) положительно определена при всех xÎEn и, следовательно, невырождена (det f ¢¢(хk) > 0). Тогда существует обратная матрица [f ¢¢(хk)]–1. Отметим, что квадратичная функция (3.68) с положительно определенной матрицей f ¢¢(хk) сильно выпукла и уравнение (3.69) определяет единственную точку глобального минимума функции Фk(x). Умножим слева обе части равенства (3.69) на матрицу [f ¢¢(хk)]–1 и найдем точку минимума xk+1 квадратичной функции (3.68), аппроксимирующей f (x) в окрестности точки

x=xk:

xk+1 = xk – [f ¢¢(хk)]–1× f ¢(хk), k = 0, 1, … (3.70)

Итерационный процесс –, начатый из произвольной точки x0ÎEn, называется методом Ньютона минимизации функции многих переменных.

Задача линейного программирования

Линейное программирование – математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование.

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

Основной (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида:

при условиях

,

.

Задача линейного программирования будет иметь канонический вид, если в основной задаче вместо первой системы неравенств имеет место система уравнений:

,

Основную задачу можно свести к канонической путём введения дополнительных переменных.

Задачи линейного программирования наиболее общего вида (задачи со смешанными ограничениями: равенствами и неравенствами, наличием переменных, свободных от ограничений) могут быть приведены к эквивалентным (имеющим то же множество решений) заменами переменных и заменой равенств на пару неравенств.

Легко заметить, что задачу нахождения максимума можно заменить задачей нахождения минимума, взяв коэффициенты с обратным знаком.