Метод Ньютона в нелинейном программировании. Метод Ньютона. Сходимость метода Ньютона. Метод Ньютона в задачах на безусловный экстремум

Оптимизация означает минимизацию или максимизацию функции. В общем случае задача оптимизации формулируется как задача нахождения на множестве S n-мерного пространства таких значений аргументов функции n вещественных переменных f(x₁,x₂,…,x_n), при которых эта функция достигает минимума или максимума. Минимизация (или максимизация) функции часто называется целевой функцией. Если множество S представляет собой все n-мерное пространство, то говорят, что решается задача безусловной оптимизации (оптимизации без ограничений).

Будем говорить, что функция f(x) имеет глобальный минимум в точке , если точка допустима (принадлежит множеству S) и для всех допустимых точек. Аналогично, f(x) имеет локальный минимум в точке , если точка допустима и для всех допустимых точек из окрестности . Функция f(x) называется унимодальной на отрезки [a,b], если на этом отрезке она единственный минимум и при строго убывает, а при строго возрастает.

Применим метод  Ньютона для минимизации функции f(x). Будем предполагать, что функция имеет по крайней мере три непрерывные производные и ограничена снизу. Идея метода Ньютона состоит в аппроксимации f(x) в окрестности предполагаемой точки минимума х₀ более простой функцией, для минимизации которой можно воспользоваться аналитическими выражениями. Точка минимума х₁ этой аппроксимирующей функции дает новое приближение для точки минимума исходной функции f(x). Затем процесс повторяется до тех пор, пока модуль разности межлу двумя последовательными приближениями не достигает заданной погрешности минимизации. Так как линейная функция не имеет конечного минимума, простейшей аппроксимацией является квадратичная.

Предположим, что точка х_n – текущее приближение к истинному положению минимума , и рассмотрим разложение функции f(x) в ряд Тейлора в окрестности точки х_n, ограничившись тремя членами ряда:

Теперь задача состоит из минимизации квадратичной функции q(h). При этом предполагается, что точка минимума функции q(h) дает лучшее приближение к значению : Для минимизации функции q(h)вычисляем производную q’(h) и приравниваем ее к нулю, что дает:

Таким образом, алгоритм метода Ньютона описывается итерационной формулой:

                                           (1.13)

Условия сходимости итерационного процесса (1.13) можно  сформулировать как следующее утверждение. Пусть  и непрерывна. Тогда существует окрестность точки такая, что если начальное приближение х₀ принадлежит этой окрестности, то последовательность значений х_n , вычисляется по формуле (1.13), сходится к при n→∞. Для функций не являющихся унимодальными при итерации (1.13) сходятся к локальному минимуму, а при - к локальному максимуму.

Когда метод  Ньютона сходится, скорость сходимости квадратична. Это означает, что если точка х_n достаточно близка к , то то  С – неотрицательная константа, зависящая от вида минимизируемой функции. Проще говоря, число верхних значений цифр приближения х_n удваивается с каждой новой итерацией.

Одномерная  оптимизация тесно связана с  задачей решения нелинейных уравнений. Так, формула (1.13) получается, если методом Ньютона решеть уравнение которое представляет собой необходимое условие экстремума функции. С другой стороны, нелинейное уравнение g(x)=0 можно решить, найдя точку нулевого минимума функции f(x)=g²(x).

Метод Ньютона для решения задач минимизации функций многих аргументов является обобщением метода одномерной оптимизации. Разложение целевой функции f(x₁,x₂) в ряд Тейлора в окрестности точки текущего приближения Х^(k) имеет вид:

                       (1.14)

Здесь все производные  вычисляются в точке Х^(k). Выражение (1.14) можно записать в векторно-матричной форме, если ввести в рассмотрение квадратичную матрицу Н (матрицу Гессе) с элементами и вектор-столбец смещений :

                     (1.15)

Несмотря на то, что этот результат получен  для двумерного случая, его векторно-матричная  форма (1.15) сохраняется и для n измерений.

Если в выражение (1.14) сохранить  лишь слагаемые до второго порядка по включительно, то это означает, что истинную целевую функцию f(x) мы заменим квадратичной формой:

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

и приравнивая  его к нулю. В результате получаем систему линейных алгебраических уравнений  относительно компонент вектора  - вектора смещения из точки текущего приближения Х^(k) в точку нового приближения Х^(k+1):

                                           (1.16)

Уравнение (1.16) называются уравнениями Ньютона. Их решение позволяет определить новое  приближение как 

                                                    (1.17)

Если решение  уравнения Ньютона (1.16) формально записать через матрицу Н(х^(k))^-1, обратную матрице Гессе, то

и итерационная формула многомерного метода Ньютона будет выглядеть следующим образом:

                              (1.18)

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

 

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

; .

Выполнить следующее:

а) Кратко описать  сущность модели межотраслевого баланса (2 страницы);

б) Вычислить  вектор-столбец конечного продукта    и вектор-строку   условно-чистого продукта, проверить выполнение балансового соотношения между ними, составить таблицу межотраслевого баланса;

в) Построить  производственную матрицу  , и записать систему балансовых соотношений в матричной форме (проверить её выполнение);

г) Вычислить  матрицу полных потребностей продукции  отраслей , выяснить продуктивна ли производственная матрица;

д) пусть даны:

- вектор-столбец  прямых затрат по оплате труда на рубль продукции

- вектор-столбец  прямых затрат(в чел/час) труда  на рубль продукции 

— вычислить  полную трудоемкость и зарплатоемкость  продукции, по отраслям;

е) Рассчитать план по валовому продукту, если требуется в конце планового периода (года) получить конечный продукт задаваемый вектором  ;

ж) Пусть известно, что  на следующий год планируется  изменить вектор конечного продукта на величину

как должен быть изменен вектор валовых выпусков?

Решение:

а) Модель межотраслевого баланса является классическим примером макроэкономической модели. Первые её варианты появились еще в 10-20-х годах ХХ века, и далее имело место их развитие и весьма плодотворное использование на протяжении всего последующего периода, как за рубежом, так и в СССР, и в соцстранах.

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

1. Планировать необходимый валовый выпуск продукции при заданном объеме конечной продукции отраслей;
2. Рассчитывать такие важные экономические показатели, как полная зарплатоемкость, полная трудоемкость, фондоемкость и т.д.
3. Проводить общий анализ структуры экономики, необходимый для оценки её устойчивости,  перспектив развития и т.д.
4. Ставить и решать различные оптимизационные задачи промышленного производства.

б) Вычисляем  вектор-столбец конечного продукта  

вектор-строку условно-чистого продукта

проверяем выполнение балансового соотношения между ними,

     

Видим – баланс выполняется.

в) Строим производственную матрицу

Проверяем выполнение баланса 

г) Вычисляем матрицу полных потребностей продукции отраслей

 В=(Е-А)^-1.

Сделаем проверку:

Видим, что все  элементы матрицы В положительны, следовательно рассматриваемая производственная матрица А является продуктивной. Это считается необходимым условием структурной устойчивости рассматриваемой экономики.

д) - Вектор полной трудоемкости:

- Вектор полной затратоемкости:

е) Рассчитываем план по валовому продукту:

ж) Если известно, что на следующий год планируется изменить вектор конечного продукта на величину

,

то вектор валовых  выпусков должен измениться на

 

Задача решена.

 

3.  Задача 3. Привести математическую формулировку задачи. Решить ее симплекс-методом. Составить двойственную задачу. Найти ее решение. Проинтерпретировать полученное решение двойственной задачи.

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

Таблица 3.1

Вид оборудования	Нормы затрат ресурсов на одну тысячу изделий.			Общее количество
	A	B	C	ресурсов.
Станочное оборудование	25+N= 25+7=32	10+2N= 10+2*7=24	20+N= 20+7=27	500+5N+4N2= 500+5*7+4*0=535
Рабочая сила	15+2N= 15+2*7=29	24+2N= 24+2*7=38	45-N= 45-7=38	440+3N+6N2= 440+3*7+6*0=461
Цена одной  тысячи изделий, тыс. руб	10+N= 10+7=17	12+N= 12+7=19	8+N= 8+7=15

 

Известно также, что  по ранее заключенным договорам суммарный объем выпуска в денежном выражении изделий видов A и C не может быть менее 250-2N= 250-2*7=236 тыс.руб.

Считается, что сбыт обеспечен. Составить план производства изделий, при котором стоимость продукции  будет максимальной.

Решение.

Составим математическую модель задачи. Искомый выпуск изделий А обозначим через x₁, изделий В – через х₂, изделий C – через x₃.  Переменные должны удовлетворять следующей системе неравенств:

32x₁ + 24x₂  + 27x ₃  £ 535,

29x₁ + 38x₂  + 38x ₃  £ 461,

Общая стоимость  произведенной продукции составит:

С = 17x₁+19x₂+15x₃

x₁  ³ 0 ,  x₂   ³ 0,   x₃  ³ 0.

Мы получили стандартную  задачу линейного программирования, приведем ее к форме основной. Для  этого введем три дополнительные переменные, в результате чего ограничения  запишутся в виде системы равенств:

32x₁ + 24x₂  + 27x ₃  + x ₄ = 535

29x₁ + 38x₂  + 38x ₃  + x ₅  = 461

Для приведения к каноническому виду вводим дополнительную переменную x₆.

17x₁ + 15x₃ – x₆ = 236

Значит матрица ограничений  задачи теперь имеет вид:

и в ней нет 3-х (по количеству ограничений) единичных столбцов.

Введем скусственную переменную x₇³0,

17x₁ + 15x₃ – x₆ + x₇ = 236

Имеем задачу

С = 17x₁ + 19x₂ + 15x₃ – 200*x₇ ® max,

при ограничениях:

32x₁ + 24x₂  + 27x ₃  + x ₄ = 535

29x₁ + 38x₂  + 38x ₃  + x ₅  = 461

17x₁ + 15x₃ – x₆ + x₇ = 236

x_i ³ 0, (i= ).

Ниже приводится последовательность симплекс-таблиц полученных при решении задачи.

Принимаем в качестве первоначального базиса х₄, х₅, х₇ и записываем данные задачи в таблицу, называемую симплекс-таблицей.

 

 

 

Шаг 1. Симплекс-таблица  первого шага.

Таблица 3.2

Базис	х1	х2	х3	х4	х5	х6	х7	Р	С
x4	32	24	27	1	0	0	0	535	0
x5	29	38	38	0	1	0	0	461	0
х7	17	0	15	0	0	-1	1	236	-200
Δ	-3417	-19	-3015	0	0	200	0