Методы оптимальных решений. Нелинейные задачи оптимизации. Задачи нелинейного программирования в процессах оптимизации ресурсов и принятия решений. Решение задач условной оптимизации методом множителей Лагранжа. Двойственность в нелинейном программировании. Теорема Куна–Таккера. Теория оптимизации. Матрица Гессе

Решение задач и выполнение научно-исследовательских разработок: Отправьте запрос сейчас: irina@bodrenko.org    
математика, IT, информатика, программирование, статистика, биостатистика, экономика, психология
Пришлите по e-mail: irina@bodrenko.org описание вашего задания, срок выполнения, стоимость





Методы оптимальных решений

 

Лекция 7

 

Тема лекции 7: «Нелинейные задачи оптимизации»

Разделы лекции:

 

1. Задачи нелинейного программирования в процессах оптимизации ресурсов и принятия решений.

2. Решение задач условной оптимизации методом множителей Лагранжа.       

3. Двойственность в нелинейном программировании. Теорема Куна–Таккера.

 

РАЗДЕЛ 1. ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В ПРОЦЕССАХ ОПТИМИЗАЦИИ РЕСУРСОВ И ПРИНЯТИЯ РЕШЕНИЙ.

 

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

 

КАКОВЫ ОСНОВНЫЕ ОСОБЕННОСТИ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ?

 

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

1. Множество допустимых планов D может иметь очень сложную структуру (например, быть невыпуклым или несвязным).

2. Глобальный максимум (минимум) может достигаться как внутри множества D, так и на его границах (где он, вообще говоря, будет не совпадать ни с одним из локальных экстремумов).

3. Целевая функция f(X) может быть не дифференцируемой, что затрудняет применение классических методов математического анализа.

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

 

КАК МОЖНО КЛАССИФИЦИРОВАТЬ ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ?

 

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

Нелинейное программирование

1. Виды экстремумов

2. Типы задач оптимизации

3. Методы решения

Локальный

Глобальный

Безусловная оптимизация

Условная оптимизация

Численные

Аналитические

Рисунок 1. Классификация задач нелинейного программирования.

1. ЭКСТРЕМУМЫ ЦЕЛЕВЫХ ФУНКЦИЙ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

 

Максимум и минимум целевой функции f(Х) объединяются в одно понятие экстремум. Экстремальная точка функции f(Х), где X=(х1,…, xj, … , xn), определяет либо ее максимальное, либо минимальное значение. С математической точки зрения точка Х0=(х01,…, x0j, … , x0n) является точкой максимума функции f(Х), если неравенство

 
f(X0+h) ≤ f0)

 

выполняется для всех h=(h1, …, hj, …, hn) таких, что |hj| достаточно малы при всех j=1, …, n. Другими словами, точка Х0 является точкой максимума, если значения функции f(X) в окрестности точки Х0 не превышают f0).

 

Аналогично, точка Х0 является точкой минимума функции f(Х), если для определенного выше вектора h=(h1, …, hj, …, hn)  имеет место неравенство:

 

f(X0+h)≥f0).

 

В общем случае, точка Х0 является точкой НЕСТРОГОГО МАКСИМУМА функции f(X), где X=(х1,…, xj, … , xn),    если выполняется нестрогое неравенство:

 

f(X0+h) ≤ f(Х0),

 

и точкой ее СТРОГОГО МАКСИМУМА, если выполняется строгое неравенство:

 

f(X0+h) < f(Х0), 

 

где h=(h1, …, hj, …, hn) – вектор, определенный выше. 

 

Аналогично,  точка Х0 является точкой НЕСТРОГОГО МИНИМУМА функции f(X), где X=(х1,…, xj, … , xn),    если выполняется нестрогое неравенство:

 

f(X0+h)≥f(Х0),

 

и точкой ее СТРОГОГО МИНИМУМА, если выполняется строгое неравенство:

 

f(X0+h)>f(Х0), 

 

где h=(h1, …, hj, …, hn) – вектор, определенный выше. 

 

ПРИМЕР 1(ЭКСТРЕМУМЫ ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ).

 

На рисунке 2 показаны точки максимума и минимума действительной функции одной переменной f(х) на интервале [а, b]. Точки х*1, х*2, х*3, х*4 и х*6 составляют множество экстремальных точек функции f(x). Здесь точки х*1, х*3 и х*6 являются точками максимума, а точки х*2 и х*4 точками минимума функции f(х).

 

Поскольку выполняется равенство:

 

f(x*6) =max{f(x*1), f(x*3), f(x*6)},  

 

то значение f(х*6) является ГЛОБАЛЬНЫМ ИЛИ АБСОЛЮТНЫМ МАКСИМУМОМ,  а значения f(x*1) и f(x*3) – ЛОКАЛЬНЫМИ ИЛИ ОТНОСИТЕЛЬНЫМИ МАКСИМУМАМИ.

 

Подобным образом, поскольку выполняется равенство:

 

f(x*2) =min{f(x*2), f(x*4)},

 

то значение f(x*4) является ЛОКАЛЬНЫМ, а значение f(x*2) – ГЛОБАЛЬНЫМ МИНИМУМОМ функции f(x).

 

Заметим, что хотя точка х*1 является точкой максимума функции f(x)  (рисунок 2), она отличается от остальных локальных максимумов функции f(x) тем, что, по крайней мере, в одной точке ее окрестности значение функции f(x) совпадает с f(х*1). Точка х*1 по этой причине называется НЕСТРОГИМ (СЛАБЫМ) МАКСИМУМОМ ФУНКЦИИ f(x), в отличие, например, от точки х*3, которая является СТРОГИМ МАКСИМУМОМ ФУНКЦИИ f(x). Нестрогий максимум, следовательно, подразумевает наличие (бесконечного количества) различных точек, которым соответствует одно и то же максимальное значение функции. Аналогичные результаты имеют место в точке х*4, где функция f(x) имеет нестрогий минимум.

 

На рисунке 2 легко заметить, что первая производная функции f(x) (тангенс угла наклона касательной к графику функции) равна 0 во всех ее экстремальных точках. Однако это условие выполняется и в точках перегиба и седловых точках функции f(x) таких, например, как точка х*5. Если точка, в которой угол наклона касательной к графику функции f(x) равен нулю, не является в то же время точкой экстремума (максимума или минимума), то она автоматически должна быть точкой перегиба или седловой точкой.


Рисунок 2. Экстремумы функции f(x).

 

2. ЗАДАЧИ ОПТИМИЗАЦИИ В НЕЛИНЕЙНОМ ПРОГРАММИРОВАНИИ.

 

К задачам оптимизации в нелинейном программировании относятся задачи безусловной и условной оптимизации.

ЗАДАЧАМИ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ называются такие задачи, в  которых задается лишь одна целевая функция f=f(X) → max (min)  без указания ограничений и граничных условий.  Эти задачи  носят теоретический характер, так как на практике граничные  условия задаются всегда.  Поэтому в таких задачах для нахождения оптимального решения применяют методы нахождения экстремума функции.

ЗАДАЧАМИ УСЛОВНОЙ ОПТИМИЗАЦИИ называются такие задачи, когда, кроме целевой функции, в них задаются некоторые  дополнительные условия, которые должны быть выполнены. Ограничения могут быть заданы в виде, как уравнений, так и неравенств, при этом введение ограничений либо не влияет на оптимум,  либо ухудшает его, подтверждая тем самым вывод, сделанный для задач линейного программирования, что введение  дополнительных условий не улучшает оптимального решения, а в ряде  случаев приводит к несовместности условий.

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

 

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

КЛАССИЧЕСКАЯ ТЕОРИЯ  ОПТИМИЗАЦИИ. ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ БЕЗ ОГРАНИЧЕНИЙ. АНАЛИТИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ.

 

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

 

НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ  СУЩЕСТВОВАНИЯ ЭКСТРЕМУМА.


В этом разделе мы изложим необходимые и достаточные условия существования экстремумов действительной функции п переменных f(X), где Х=( х1,…, xj, … , xn). При этом предполагается, что первые и вторые частные производные функции f(Х) непрерывны в каждой точке Х из области определения функции. 

 

ТЕОРЕМА 1 (НЕОБХОДИМОЕ УСЛОВИЕ СУЩЕСТВОВАНИЯ ЭКСТРЕМУМА). Необходимым условием того, что точка Х0 является экстремальной точкой функции f(Х), является равенство: Ñf0) =0 (то есть градиент функции f(X) в точке X0 равен нулю).

 

КАКИЕ ТОЧКИ НАЗЫВАЮТСЯ СТАЦИОНАРНЫМИ?

 

Так как необходимое условие существования экстремума выполняется также в точках перегиба и седловых точках функции f(X), поэтому точки, удовлетворяющие уравнению Ñf(Х)=0, называют стационарными точками функции f(X).

 

ЧТО ТАКОЕ МАТРИЦА ГЕССЕ?

 

Введем следующее определение.

 

Матрица H(X)=||Hij|| порядка n с элементами Hij=∂2f/∂xixj,   называется матрицей Гессе функции  f=f(X), где Х=( х1,…, xi, …, xj, … , xn).

 

 

Следующая теорема устанавливает достаточные условия того, что стационарная точка Х0 является экстремальной.  

 

ТЕОРЕМА 2 (ДОСТАТОЧНОЕ УСЛОВИЕ СУЩЕСТВОВАНИЯ ЭКСТРЕМУМА). Для того чтобы стационарная точка Х0 функции f(X) являлась экстремальной, достаточно, чтобы в точке Х0 матрица Гессе Н(X0) функции  f(X) была  

 

(1) положительно определенной (тогда Х0точка минимума);  

 

(2) отрицательно определенной (тогда Х0точка максимума).  

 

 

ЗАМЕЧАНИЕ. Таким образом, положительная определенность матрицы Гессе H(X) функции f(X) в стационарной точке Х0 является достаточным условием существования в этой точке минимума функции f(X). Стационарная точка X0 является точкой максимума функции f(X), если матрица Гессе H(X) в этой точке отрицательно определена. 

 

Теперь применим достаточные условия, полученные в теореме 2, к функции одной переменной f(x). Пусть x* – стационарная точка функции f(x). Тогда 

 

(1) выполнение строгого неравенства f’’(x*)<0 является достаточным условием существования максимума в точке x*;  

 

(2) выполнение строгого неравенства f’’(x*)>0 является достаточным условием существования минимума в точке x*.


Если же для функции одной переменной выполняется равенство f’’(x*)=0, то необходимо исследовать производные высших порядков в соответствии со следующей теоремой. 

 

ТЕОРЕМА 3.  Если в стационарной точке у0 функции f(y) первые (n–1) ее производных равны нулю (n≥2), и n-я производная не равна нулю: f(n)(y0)≠0,  то в точке у=y0 функция f(y) имеет:

 

(а) точку перегиба, если n – нечетное;

 

(б)  экстремальную точку,   если n – четное. При этом данная экстремальная точка является точкой максимума при f(n)(y0)<0 и точкой минимума при  f(n)(y0)>0.

 

 

Проиллюстрируем нахождение экстремумов функций на конкретных примерах, используя теоремы 1 и 2 (необходимые и достаточные условия существования экстремума) и теорему 3 (в случае функции одной переменной f(x)).

 

НАХОЖДЕНИЕ ЭКСТРЕМУМА ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ.

 

В соответствии с теоремами 1 и 2, для того чтобы найти экстремум дифференцируемой функции одной переменной f=f(x), необходимо выполнить следующий алгоритм.

 

(1). Найти первую производную f’(x)=df(x)/dx.

 

(2). Приравнять ее к нулю: f’(x)=0.

 

(3). Решить полученное уравнение; каждое решение х*данного уравнения является стационарной точкой функции f(x).

 

(4). Найти вторую производную f’’(x)=d2f(x)/dx2  и определить знаки этой производной в точке х*. Если при этом f’’(x*)<0, то точка х* - точка максимума, а  если f’’(x*)>0, то точка х* - точка минимума функции f(x).

Если же для функции f(x) выполняется равенство f’’(x*)=0, то необходимо исследовать производные высших порядков функции f(x) в точке x* в соответствии с теоремой 3. 

 

ПРИМЕР 2 (НАХОЖДЕНИЕ ЭКСТРЕМУМА ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ).

 

Требуется найти экстремум  функции  одной переменной

 

f(x)= –2x2+12x – 10.

РЕШЕНИЕ. Произведем необходимые действия согласно вышеприведенному алгоритму.

1. Найдем первую производную заданной функции: f’(x)= –4x+12.

 

2. Приравняем первую производную к нулю: -4x+12 =0.

 

3. Решим полученное уравнение: –4x+12 = 0; отсюда получим, что x*=3. Таким образом, получаем, что стационарная точка функции f(x)= –2x2+12x – 10  - это точка x*=3.

 

4. Находим вторую производную заданной функции: f’’(x)= -4<0. То есть в найденной точке x*=3 исследуемая функция f(x)= –2x2+12x – 10  имеет максимум.

Для наглядности построим график заданной функции (рисунок 3) f(x)= –2x2+12x – 10 в прямоугольной системе координат OXY.

 

 

Рисунок 3. График функции y= –2x2+12x – 10.

 

ПРИМЕР 3. Рассмотрим функции f(у)=y4 и g(y)=y3.  Графики этих функций изображены на рисунке 4.

 

Рисунок 4. Графики функций f(у)=y4 и g(y)=y3.

 

Для функции f(x) мы имеем.

 

Первая производная f’(y)=4y3 . Отсюда  получим уравнение: 4y3 =0. Следовательно, y0=0  - стационарная точка функции f(y).   Производные f’’(y)=12y2, f’’’(y)=24y.  Тогда в стационарной точке f’’(y0)=f’’(0)=12∙0=0; f’’’(y0)=f’’’(0)=24∙0=0.  То есть в стационарной точке производные второго и третьего порядков функции f(y) равны нулю.  Производная четвертого порядка f(4)(y)=24≠0 отлична от нуля. Следовательно, в силу теоремы 3, y0=0 – точка минимума функции f(у)=y4 , поскольку f(n)(y0)≠0 при n=4 (n – четное число) и при этом f(4)(y0)=24>0.

 

 

Для функции g(x) мы имеем.

 

Первая производная g’(y)=3y2 . Отсюда  получим уравнение: 3y2 =0. Следовательно, y0=0  - стационарная точка  функции g(y).

Производные g’’(y)=6y.  Тогда в стационарной точке g’’(y0)=g’’(0)=6∙0=0. То есть в стационарной точке производная  второго порядка функции g(y) равна нулю.  Производная третьего порядка g’’’(y)=6≠0 отлична от нуля. Следовательно, в силу теоремы 3, y0=0 – точка перегиба функции g(у)=y3 , поскольку g(n)(y)≠0 при n=3 (n – нечетное число).

 

 

НАХОЖДЕНИЕ ЭКСТРЕМУМА ФУНКЦИИ ДВУХ ПЕРЕМЕННЫХ.

 

Согласно теоремам 1 и 2, для нахождения экстремума функции двух переменных F(x1,x2) необходимо произвести следующие действия.

 

(1).  Найти частные производные ∂F/∂x1, ∂F/∂x2 функции F(x1,x2) по каждой переменной x1, x2.

 

(2). Выписать необходимые условия существования экстремума функции F(x1,x2):

 

F/∂x1 =0, ∂F/∂x2=0.

 

(3). Решить систему уравнений:

 

F/∂x1 =0, ∂F/∂x2=0. Каждое решение (x*1, x*2) данной системы – стационарная точка функции  F(x1,x2).

 

(4). Составить матрицу Гессе H=H(x1,x2) для функции F(x1,x2) и исследовать ее в найденных стационарных точках (x*1, x*2).

 

Рассмотрим теперь процесс нахождения экстремума функции  двух переменных на следующем простом примере.

ПРИМЕР 4 (НАХОЖДЕНИЕ ЭКСТРЕМУМА ФУНКЦИИ ДВУХ ПЕРЕМЕННЫХ).

 

 Найти экстремум функции: F(x1,x2)=(х1 – 5)2/2 + (x2 – 3)2/2 + 4, график которой схематично изображен на рисунке 5 в прямоугольной системе координат OX1X2Z. График данной функции – это поверхность второго порядка (эллиптический параболоид). 

 

Рисунок 5. График функции z=(х1 – 5)2/2 + (x2 – 3)2/2 + 4.

 

РЕШЕНИЕ.

 

(1). Для функции F(x1,x2)=(х1 – 5)2/2 + (x2 – 3)2/2 + 4 имеем:

F/∂x1 = х1 – 5, ∂F/∂x2= x2 – 3.

 

(2). Отсюда, получим систему уравнений:

 

х1 – 5 =0, x2 – 3=0.

 

(3). Решая данную систему, находим: x*1=5; x*2=3. То есть точка (5,3) – стационарная точка функции  F(x1,x2)=( х1 – 5)2/2 + (x2 – 3)2/2 + 4.

 

 

(4). Составим матрицу Гессе H=H(x1,x2) для функции F(x1,x2)=( х1 – 5)2/2 + (x2 – 3)2/2 + 4.

Мы имеем:

 

H=

2F/∂x1x1  

2F/∂x1x2  

2F/∂x2x1   

2F/∂x2x2  

=

1

0

0

1

 

 

Полученная матрица H – единичная матрица второго порядка, угловые миноры данной матрицы равны: 1, 1. Следовательно, матрица H является положительно определенной в  точке (x*1,x*2)=(5,3).

 

Таким образом, точка (5,3) является точкой минимума функции F(x1,x2)=( х1 – 5)2/2 + (x2 – 3)2/2 + 4.

 

ЗАМЕЧАНИЕ. Используя график функции z=F(x1,x2), легко увидеть, что точка (x*1,x*2)=(5,3) является точкой минимума функции  F(x1,x2)=(х1 – 5)2/2 + (x2 – 3)2/2 + 4. При этом, значение функции F(x*1,x*2)=4.

 

НАХОЖДЕНИЕ ЭКСТРЕМУМА ФУНКЦИИ ТРЕХ ПЕРЕМЕННЫХ.

 

Нахождение экстремума дифференцируемой функции трех переменных f1, х2, х3) разберем на следующем примере.

 

ПРИМЕР 5 (НАХОЖДЕНИЕ ЭКСТРЕМУМА ФУНКЦИИ ТРЕХ ПЕРЕМЕННЫХ). Рассмотрим функцию  f1, х2, х3) = x1+2х3+ х2х3 – х12 – х22 – х32.  Необходимое условие экстремума – градиент функции f(X) в точке X0 равен нулю,  здесь принимает следующий вид. 

 

f/∂x1 =0,

 

f/∂x2=0,

 

f/∂x3=0.

 

То есть

 

f/∂x1 =1 – 2x1=0,

 

f/∂x2=x3 – 2x2=0,

 

f/∂x3=2 +x2 – 2x3=0.

 

Решением этой системы линейных уравнений является точка Х0=(1/2, 2/3, 4/3).  

 

 

Для проверки выполнения условия достаточности вычислим  матрицу Гессе функции трех переменных f1, х2, х3) = x1+2х3+ х2х3 – х12 – х22 – х32.

 

Мы имеем:

H =

2f/∂x1x1  

2f/∂x1x2  

2f/∂x1x3  

2f/∂x2x1  

2f/∂x2x2  

2f/∂x2x3  

2f/∂x3x1  

2f/∂x3x2  

2f/∂x3x3  

=

-      2

0

0

0

-      2

1

0

1

-      2

 

 

Угловые миноры матрицы Н равны: Δ1=(- 2), Δ2=4 и Δ3= (-8) соответственно. В этом случае Н в точке X0 является отрицательно определенной матрицей. Откуда, в силу теоремы 2,   следует, что точка Х0=(1/2, 2/3, 4/3) является ТОЧКОЙ МАКСИМУМА функции f1, х2, х3) = x1+2х32х3 – х12 – х22 – х32. 

 

В общем случае, если матрица Гессе Н(X) является неопределенной в точке X0, то точка Х0 должна быть седловой. Если же матрица H(X) оказывается полуопределенной в точке X0, то соответствующая точка Х0 может как быть, так и не быть экстремальной. При этом формулировка достаточного условия существования экстремума значительно усложняется, ибо для этого необходимо учитывать члены более высоких порядков в разложении Тейлора. Иллюстрацией вышесказанного в случае функции одной переменной f(x) служит теорема 3.  В некоторых случаях такие сложные процедуры не являются необходимыми, поскольку диагонализация матрицы Н(X0) позволяет сделать вывод о наличии или отсутствии экстремума. Проиллюстрируем это следующим примером. 

 

ПРИМЕР 6 (СЕДЛОВАЯ ТОЧКА ФУНКЦИИ ДВУХ ПЕРЕМЕННЫХ). Рассмотрим функцию  f(x1,x2)=4x1x2+3x22 . Необходимые условия экстремума для которой принимают следующий вид:

 

4x2=0,

 

4x1+6x2=0.

 

Отсюда следует, что стационарной является точка Х0=(0,0). При этом матрица Гессе в точке Х0 имеет вид:

H=

0

4

4

6

 

и не дает информации о наличии или отсутствии экстремума в рассматриваемой точке в соответствии с теоремой 2.

 

Используя один из методов диагонализации матриц, получаем преобразованную матрицу Гессе Нd =

-2

0

0

8

 

 

Матрица Нd (и, следовательно, Н) является неопределенной. Следовательно, Х0 – СЕДЛОВАЯ ТОЧКА функции f(x1,x2)=4x1x2+3x22. 

 

ЗАМЕЧАНИЕ. Если диагональная матрица Нd  подобна матрице H (а это здесь подразумевается), то нет необходимости проверять угловые миноры матрицы Нd, так как в этом случае диагональные элементы матрицы Нd являются собственными значениями матрицы Н.  Поэтому данная матрица H будет неопределенной, если диагональные элементы матрицы Нd  имеют разные знаки.

 

На этом закончим рассмотрение аналитических методов  нахождения экстремума в задаче безусловной оптимизации и опишем численный метод нахождения стационарных точек.  Для численного нахождения стационарных точек функции f(X) может быть применен метод Ньютона-Рафсона.

 

В ЧЕМ СОСТОИТ МЕТОД НЬЮТОНА – РАФСОНА?

 

В общем случае использование необходимого условия экстремума Ñf(Х0) =0 (то есть градиент функции f(X) в стационарной точке X0 равен нулю)  для нахождения стационарных точек функции f(X) может быть сопряжено с трудностями, возникающими при численном решении соответствующей системы уравнений. Метод Ньютона—Рафсона предлагает итерационную процедуру решения системы нелинейных уравнений. Несмотря на то, что данный метод рассматривается в этом разделе именно в указанном контексте, на самом деле он относится к числу градиентных методов численного поиска экстремумов функций при отсутствии ограничений.

 

Рассмотрим систему уравнений:

 

fi (X)=0, i=1,…, n.

 

Пусть Хk некоторая фиксированная точка. Тогда в некоторой окрестности точки Хk, используя разложение Тейлора для функции fi (X), имеем

 

fi (X)≈ fi (Xk)+ Ñfi(Хk)(X – Xk), i=1, …, n.

 

Следовательно, исходная система уравнений в некоторой окрестности точки Хk приближенно представима в следующем виде:

 

fi (Xk)+ Ñfi(Хk)(X – Xk) =0,i=1, ...,n.

Эти уравнения можно записать в матричной форме:

Аkk(Х – Хk)=0.

Учитывая, что матрица Bk  является невырожденной (в предположении, что  fi (X) независимы, i=1,  …, n) , из предыдущего уравнения получим:

X=XkBk-1Ak .

 

Идея метода Ньютона—Рафсона состоит в следующем. На первом шаге выбирается начальная точка Х0. С помощью полученного уравнения по известной точке Хk можно вычислить координаты новой точки Хk+1. Процесс вычислений завершается в точке Хm, которая считается приближенным решением исходной системы, если Хm≈Хm–1.

Геометрическая интерпретация данного метода для функции одной переменной f(х) приведена на рисунке 6. Связь между точками хk и хk+1 в этом случае выражается следующей формулой.

 

xk+1=xk – (f(xk)/f’(xk)),

 

или

 

f’(xk)= f(xk)/( xk– xk+1).

 

Из рисунка 6 видно, что положение точки хk+1 определяется углом φ, который образует касательная к графику функции y=f(x)  в точке (хk ,f(xk)) с положительным направлением  оси ОX. Обозначим:  Θ=π – φ. Тогда имеем: tg Θ= –f’(xk)= f(xk)/(xk+1xk). 

 

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

 

Рисунок 6. Геометрическая интерпретация метода Ньютона – Рафсона.

 

 

РАЗДЕЛ 2.  РЕШЕНИЕ ЗАДАЧ УСЛОВНОЙ ОПТИМИЗАЦИИ МЕТОДОМ МНОЖИТЕЛЕЙ ЛАГРАНЖА.

 

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

 

В ЧЕМ СОСТОИТ МЕТОД МНОЖИТЕЛЕЙ ЛАГРАНЖА?

 

Метод множителей Лагранжа применяется для решения задач условной оптимизации с ограничениями на переменные в форме равенств. Идея метода множителей Лагранжа состоит в сведении задачи поиска условного экстремума целевой функции 

 

f(x1, …, xn)  (1)

 

на множестве допустимых значений D, описываемом следующей системой уравнений:

gi(x1, …, xn)=0,  i=1, …, m. (2)

к задаче безусловной оптимизации функции:

 

Φ(X,λ)=f(x1,x2, …, xn) +λ1g1(x1, x2, …, xn)+  … + λmgm(x1, x2, …, xn), (3)

 

где X=(x1, x2, …, xn), а вектор λ=(λ1, …, λm) – вектор дополнительных переменных, называемых множителями Лагранжа.

 

 

ЧТО ТАКОЕ ФУНКЦИЯ ЛАГРАНЖА?

 

Функцию Φ(X,λ), заданную формулой (3), где

где X=(x1, x2, …, xn), λ=(λ1, …, λm), называют функцией Лагранжа.

 

КАК ФОРМУЛИРУЕТСЯ НЕОБХОДИМОЕ УСЛОВИЕ СУЩЕСТВОВАНИЯ ТОЧКИ УСЛОВНОГО ЭКСТРЕМУМА?

 

В случае дифференцируемости функций f(X) и gi(X), i=1, …, m,  справедлива теорема, определяющая необходимое условие существования точки условного экстремума в задаче (1), (2).

 

ТЕОРЕМА 4. Если X*=(x*1, x*2, …, x*n) является точкой условного экстремума функции (1) при ограничениях (2), и ранг матрицы J=||∂gi(X*)/∂xj|| (размера m x n) первых частных производных функций gi  (i=1, …, m) равен m, то существуют такие λ*1, λ*2, … , λ*m, не равные одновременно нулю, при которых выполняется равенство:

 

ÑΦ(X*,λ*)=Ñf(X*)+ λ*1Ñg1(X*) +  … + λ*mÑgm(X*) = 0.

ИЗ КАКИХ ЭТАПОВ СОСТОИТ МЕТОД МНОЖИТЕЛЕЙ ЛАГРАНЖА?

 

Из теоремы 4 вытекает метод поиска условного экстремума, получивший название метода множителей Лагранжа, или просто метода Лагранжа. Он состоит из следующих этапов.

1. Составление функции Лагранжа Φ(X,λ).

2. Нахождение частных производных

Φ(X,λ)/∂xj, j=1, …, n;  Φ(X,λ)/∂λi, i=1, …, m.

3. Решение следующей системы уравнений (4):

 

Φ(X,λ)/∂xj =0,  j=1, …, n;

 

Φ(X,λ)/∂λi = gi(X)=0,   i=1, …, m.

относительно переменных X=(x1, x2, …, xn)и λ=(λ1, …, λm).

 

 

4. Исследование точек, удовлетворяющих системе (4), на максимум (минимум) с помощью достаточного признака экстремума.

Присутствие последнего (четвертого) этапа объясняется тем, что теорема 4 дает необходимое, но не достаточное условие экстремума. Положение дел с достаточными признаками условного экстремума обстоит гораздо сложнее. Вообще говоря, они существуют, но справедливы для гораздо более частных ситуаций (при весьма жестких предпосылках относительно функций f и gi, i=1, …, m) и, как правило, их трудно применить на практике.

КАКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ УСЛОВНОЙ ОПТИМИЗАЦИИ НАЗЫВАЮТСЯ НЕПРЯМЫМИ?

 

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

ГРАДИЕНТНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ.

 

Ведущее место среди прямых методов решения экстремальных задач занимает градиентный метод (точнее, семейство градиентных методов) поиска стационарных точек дифференцируемой функции. Напомним, что стационарной называется точка X*, в которой Ñf(X*) = 0 и которая в соответствии с необходимым условием оптимальности является «подозрительной» на наличие локального экстремума. Таким образом, применяя градиентный метод, находят множество точек локальных максимумов (или минимумов), среди которых определяется максимум (или минимум) глобальный.

НА ЧЕМ ОСНОВАН ГРАДИЕНТНЫЙ МЕТОД?

 

Идея данного метода основана на том, что градиент функции указывает направление ее наиболее быстрого возрастания в окрестности той точки, в которой он вычислен. Поэтому, если из некоторой текущей точки X(1) перемещаться в направлении вектора Ñf(X(1)), то функция f(X) будет возрастать, по крайней мере, в некоторой окрестности точки X(1).  Следовательно, для точки  X(2) = X(1) +mÑf(X(1)), (m>0), лежащей в такой окрестности, справедливо неравенство:

 

f(X(1))≤ f(X(2)).

 

Продолжая этот процесс, мы постепенно будем приближаться к точке некоторого локального максимума (см.: рисунок 7).

Рисунок 7. Градиентный метод.

 

Однако как только определяется направление движения, сразу же встает вопрос о том, как далеко следует двигаться в этом направлении или, другими словами, возникает проблема выбора шага m в рекуррентной формуле:

X(q+1) = X(q) +mÑf(X(q)), (m>0),

задающей последовательность точек X(1), X(2), …, X(q+1),  стремящихся к точке максимума X*.

 

В зависимости от способа ее решения различают различные варианты градиентного метода. Наиболее известные из них – метод наискорейшего спуска и метод дробления шага.

МЕТОД НАИСКОРЕЙШЕГО СПУСКА.

 

Кратко опишем  метод наискорейшего спуска. Название метода можно было бы понимать буквально, если бы речь шла о минимизации целевой функции. Тем не менее, по традиции такое название используется и при решении задачи на максимум.

Пусть f(X)=f(x1, x2, …, xn) – дифференцируемая функция, заданная на Rn, X(q) =( x1(q), x2(q), …,  xn(q)) – некоторая текущая точка.

 

Отметим, что каких-либо общих рекомендаций, касающихся выбора исходной точки (или, как еще говорят, начального приближения) X(q)  не существует, однако, по возможности,  она должна находиться близко от искомого оптимального плана X*.

 

Как уже говорилось выше, если X(q)    нестационарная точка (т. е. в силу теоремы 1 |Ñf(X(q))|>0), то при движении в направлении Ñf(X(q))  функция f(X) на некотором промежутке обязательно будет возрастать. Отсюда возникает естественная идея такого выбора шага m, чтобы движение в указанном направлении продолжалось до тех пор, пока возрастание не прекратится.

 

Согласно методу наискорейшего спуска скалярное произведение градиентов функции f в точках X(q) и  X(q+1) равно нулю.  Продолжая геометрическую интерпретацию метода наискорейшего спуска, заметим, что геометрически равенство нулю указанного скалярного произведения оно может быть интерпретировано как перпендикулярность векторов градиентов функции f в указанных точках, что и показано на рисунке 8. Продолжая геометрическую интерпретацию метода наискорейшего спуска, отметим, что в точке X(q+1)  вектор Ñf(X(q+1)), будучи градиентом, перпендикулярен линии уровня, проходящей через данную точку. Следовательно, вектор Ñf(X(q)) является касательным к этой линии в точке X(q+1). Итак, движение в направлении градиента Ñf(X(q)) следует продолжать до тех пор, пока он пересекает линии уровня оптимизируемой функции (см: рисунок 8). После того как точка X(q+1) найдена, она становится текущей для очередной итерации. На практике признаком достижения стационарной точки служит достаточно малое изменение координат точек, рассматриваемых на последовательных итерациях. Одновременно с этим координаты вектора Ñf(X(q)) должны быть близки к нулю.

 

Рисунок 8. Метод наискорейшего спуска.

 

ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ ДЛЯ ВЫПУКЛЫХ ФУНКЦИЙ.

 

Общим недостатком рассмотренных выше методов безусловной оптимизации было, с одной стороны, то, что они позволяют отыскивать только точки, «подозрительные» на локальный экстремум, а с другой – то, что найденные решения могут существенно зависеть от начального приближения. Поиск глобального оптимума подразумевает перебор найденных точек, который, в случае градиентных методов, может быть осуществлен за счет подбора соответствующих начальных приближений X(0). Однако существует один класс функций, для которых градиентные методы приводят к нахождению глобального оптимума. Это выпуклые функции.

 

КАКАЯ ФУНКЦИЯ НАЗЫВАЕТСЯ ВЫПУКЛОЙ?

 

Функция f(X)=f(x1, x2, …, xn)  называется ВЫПУКЛОЙ в области D, если для любых двух точек X(1) и  X(2)  из области D и любого 0≤λ≤1 выполняется неравенство:

f((1 – λ)∙X(1)+ λ∙X(2))≤ (1 – λ)∙f(X(1))+ λ∙f(X(2)).

 

 

Если же выполнено неравенство:

f((1 – λ)∙X(1)+ λ∙X(2))≥ (1 – λ)∙f(X(1))+ λ∙f(X(2)),

 

то функция называется ВОГНУТОЙ.

 

 

Геометрический смысл понятий выпуклости и вогнутости для случая функции одной переменной f(x) представлен на рисунке 9. График выпуклой функции лежит ниже отрезка, соединяющего точки (x(1),f(x(1))) и (x(2),f(x(2))), а график вогнутой функции – выше.

 

Рисунок 9. Графики выпуклой и вогнутой функций.

 

Можно доказать, что достаточным условием выпуклости функции f(X)=f(x1, x2, …, xn)  является положительная определенность матрицы Гессе H(X)=||∂2f/∂xixj || во всех точках X, принадлежащих области D. Соответственно, достаточным условием вогнутости является отрицательная определенность матрицы Гессе.

Имеет место следующее утверждение.

ТЕОРЕМА 5. Если f(X) есть выпуклая (соответственно, вогнутая) на Rn функция,  и в точке X* выполнено равенство Ñf(X*)=0, то X* есть точка глобального минимума (соответственно, максимума).

 

Поскольку выпуклые функции обладают столь «полезными» оптимизационными качествами, они занимают исключительно важное место в теории исследования операций. Соответствующий раздел получил название выпуклого программирования, а общая задача выпуклого программирования формулируется как проблема поиска максимума вогнутой (минимума выпуклой) функции на выпуклом множестве.

РАЗДЕЛ 3. ДВОЙСТВЕННОСТЬ В НЕЛИНЕЙНОМ ПРОГРАММИРОВАНИИ. ТЕОРЕМА КУНА – ТАККЕРА.

 

В этом разделе лекции мы кратко остановимся на некоторых фундаментальных понятиях теории нелинейного программирования.  Отправной точкой для них является распространение метода Лагранжа для решения ЗНП с ограничениями в форме неравенств.

Требуется максимизировать целевую функцию

 

f(X)=f(x1, x2, …, xn) → max (5)

 

 на множестве допустимых значений D, описываемом следующей системой неравенств:

gi(x1, …, xn)≤0,  i=1, …, m; (6)

где X принадлежит некоторой области U пространства Rn.

 

По аналогии с формулой (3) определим для задачи (5), (6) функцию Лагранжа:

Φ(X,λ)=f(x1,x2, …, xn) – λ1g1(x1, x2, …, xn) –    λmgm(x1, x2, …, xn). (7)

 

 

ЧТО ТАКОЕ СЕДЛОВАЯ ТОЧКА ФУНКЦИИ ЛАГРАНЖА?

 

Пара векторов (X*,λ*)  называется седловой точкой функции Φ(X,λ) в некоторой области UxV, если для любых векторов  X, принадлежащих  U (XÎU) и любых векторов λ, принадлежащих VÎV), выполняются неравенства:

 

Φ(X,λ*)≤ Φ(X*,λ*)≤Φ(X*,λ).  (8)

 

Неравенства (8) также называют неравенствами седловой точки.

ПРИМЕР 6 (СЕДЛОВАЯ ТОЧКА ФУНКЦИИ ДВУХ ПЕРЕМЕННЫХ).

 

В качестве примера седловой точки может быть приведена точка (0,0) для функции

 

Ф(x,λ)= – х22,

 

определенной на множестве R2.

 

В самом деле, Ф(x,0)= – х2, Ф(0,λ)=λ2. Тогда условия (4) в точке (0,0) выполняются для любых действительных чисел x, λ:

 

Ф(x,0)= – х2≤ Ф(0,0)=0≤λ2 =Ф(0,λ).

 

На рисунке 10 изображен график функции Ф(x,λ) (гиперболический параболоид), и, как видно, в окрестности точки (0,0) он действительно по форме напоминает седло, чем и объясняется происхождение соответствующего термина.

 

Рисунок 10. Седловая точка функции Лагранжа.

 

ТЕОРЕМА КУНА—ТАККЕРА.

 

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

ТЕОРЕМА 6. (ДОСТАТОЧНОЕ УСЛОВИЕ ЭКСТРЕМУМА). Если (X*,λ*)  – седловая точка функции Лагранжа Ф(X,λ) (8), в области UÊD, λ≥0, то X* является оптимальным планом задачи (5),(6). Причем справедливо так называемое правило дополняющей нежесткости:

 λ*1∙g1(x*1, x*2, …, x*n) +    + λ*m∙gm(x*1, x*2, …, x*n)=0,

 

где X*=( x*1, x*2, …, x*n), λ*=( λ*1 ,λ*2 , …, λ*m).

 

 

Утверждение, обратное теореме 6, т. е. необходимое условие экстремума в ЗНП, оказывается верным только при выполнении дополнительных условий, которым должна удовлетворять задача (5), (6). Важнейшим из них является так называемое условие регулярности Слейтера.

ЧТО ТАКОЕ УСЛОВИЕ РЕГУЛЯРНОСТИ СЛЕЙТЕРА?

 

Говорят, что функция gi(X), задающая ограничение в задаче (5),(6), удовлетворяет условию регулярности Слейтера, если существует такая точка X⌂, принадлежащая области допустимых планов D, что gi(X⌂)<0.

 

То есть точка X⌂ является внутренней точкой относительно ограничения gi(X). Поэтому данное условие также называют УСЛОВИЕМ ТЕЛЕСНОСТИ.

 

 

Вообще говоря, существуют разные варианты необходимого условия Куна—Таккера. Приведем один из них.

ТЕОРЕМА 7. (НЕОБХОДИМОЕ УСЛОВИЕ ЭКСТРЕМУМА).  Если задача (5), (6) является задачей выпуклого программирования с решением X*, ее целевая функция f(X) и функции ограничений gi(X), i=1, …, m,  дифференцируемы; нелинейные ограничения в форме неравенств удовлетворяют условию регулярности Слейтера, то существует такой вектор λ*≥ 0, что (X*, λ*) – седловая точка функции Лагранжа Ф(X,λ) (8).

 

Значение теоремы Куна—Таккера состоит в том, что она позволяет связать процесс решения оптимизационной задачи с поиском седловых точек функции Лагранжа Ф(X,λ), т. е., грубо говоря, с максимизацией этой функции по X и минимизацией по λ.

 

СПИСОК  РЕКОМЕНДУЕМОЙ  ЛИТЕРАТУРЫ.

 

[1] Конюховский П.В. Математические методы исследования операций в экономике: Учебное пособие. СПб.: Питер, 2000. – 208 с.: ил. (Серия «Краткий курс»).

 

[2] Таха Х.А. Введение в исследование операций. 6-е изд. Пер. с англ. — М.: Издательский дом «Вильямс», 2001. — 912 с.: ил.

[3] Фомин Г. П. Математические методы и модели в коммерческой деятельности: Учебник. — 2-е изд., перераб. и доп. — М.: Финансы и статистика, 2005. — 616 с.: ил.

 

[4] Шелобаев С. И. Математические методы и модели в экономике,  финансах, бизнесе: Учебное пособие для вузов. — М.: ЮНИТИ - ДАНА, 2001. - 367 с.

[5] Экономико-математические методы и прикладные модели: Учебное пособие для вузов/ В.В. Федосеев, А.Н. Гармаш,  Д.М. Дайитбегов и др.; Под ред. В.В. Федосеева. — М.:  ЮНИТИ, 1999. - 391 с.