Безусловный экстремум нелинейного программирования

Глава 9 нелинейное програмирование.

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

Пример простой нелинейной задачи:

Предприятие для производства какого-то продукта расходует два средства в количестве х и y соответственно. Это факторы производства, например, машины и труд, два различных вида сырья и т.п., а х и y – затраты факторов производства.

Факторы производства считаются взаимозаменяемыми. Если это «труд» и «машины», то можно применять такие методы производства, при которых величина затрат в сопоставлении с величиной затрат труда оказывается больше или меньше (производство более или менее трудоемкое).

Объем производства, выраженный в натуральных или стоимостных единицах, является функцией затрат производства

Z = f (х, y). Эта зависимость называется производственной функцией.

Совокупные издержки выражаются формулой с₁х₁ + с₂y₂ = в.

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

§2 Математическая модель задачи.

Определить такие переменные х и у, удовлетворяющие условиям

с₁х₁+с₂у=в, х≥0, у≥0,

при которых функция z=f(х, у) достигнет максимума.

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

Понятие условного экстремума вводится для случая, когда число переменных n не меньше 2 (n≥2).

Разница между глобальным и локальным экстремумами предоставлена на рисунке:

Источник

1.7. Задача нелинейного программирования и условия существования ее решения

называется задачей нелинейного программирования (ЗНЛП), если целевая функция и (или) функции ограничений и в (1.26) являются нелинейными функциями.

В зависимости от вида целевой функции и системы ограничений (1.26), для решения ЗНЛП применяются различные методы. Перед началом поиска решения задачи желательно знать ответ на принципиальный вопрос о его существовании. Достаточные условия существования решения ЗНЛП с ограничениями даются следующей теоремой.

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

На рис. 1.2 показаны различные варианты экстремумов функции на компактном одномерном множестве – отрезке

Рис. 1.2. Графическая иллюстрация условных экстремумов

Условия теоремы Вейерштрасса нетрудно проверить, когда решается ЗНЛП с ограничениями. Если же задача не имеет ограничений, то тогда для ее решения применяют классический метод.

1.8. Задачи

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

Для указанных ниже матриц определить, используя критерий Сильвестра, являются ли они положительно или отрицательно определенными:

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

13. . 14. . 15. 16.

17. , если . 18. , если .

19. , если . 20. , если .

22. Найти производную функции в точке по направлению к точке .

23. Найти производную функции в точке по направлению к началу координат.

24. Найти производную функции в начале координат в направлении луча, образующего угол с осью .

25. Найти производную функции в точке по направлению к точке .

Для указанных ниже функций найти их стационарные точки:

Найти градиент и матрицу Гессе следующих функций:

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

44. Найти матрицу Якоби вектор-функции в точке .

45. Найти матрицу Якоби вектор-функции в точке .

46. Найти матрицу Якоби вектор-функции в точке .

47. Найти вектор нормали к гиперплоскости, задаваемой уравнением .

48. Найти вектор нормали к гиперплоскости, задаваемой уравнением .

2. Решение задачи нелинейного программирования без ограничений

Необходимо найти либо все максимумы, либо все минимумы целевой функции , либо и то и другое. Ограничений на аргумент целевой функции нет.

Источник

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

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

3.1. Методы поиска безусловного экстремума функции одной переменной

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

3.1.1. Аналитический метод

Постановка задачи: f (x) – функция одной переменной, требуется найти точки экстремума и определить его вид.

1. Находится производная заданной функции и приравнивается нулю:

f  (x) = 0 .

2. Находятся корни полученного уравнениях_i , i = 1, n; n – порядок уравнения.

3. Определяется тип экстремума по второй производной:

 0, то функция в точке x_i имеет максимум;

еслиd 2 f

 0, то функция в точке x_i имеет минимум.

еслиd 2 f

f (x) = х 2 + 5 х + 6,

f ( x) = 2 х + 5 = 0, x = -2,5, f ( x) = 2, тип экстремума – минимум.

3.1.2. Численные методы

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

3.1.2.1. Основные понятия и определения

Унимодальная функция – это функция, имеющая один экстремум, причем слева и справа от экстремума либо строго убывающая, либо строго возрастающая.

Отрезок а, b называется интервалом неопределенности, если внутри него функция имеет экстремум.

Точность нахождения экстремума () определяется следующим образом. Положим х₀ – точное значение экстремума, х₀ – приближенное. Тогда  х₀ — х₀   .

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

Дано: 1. Начальный интервал неопределенности а₀ , b₀.

2. Функция f (x), унимодальная на отрезке а₀ , b₀.

3. Точность нахождения экстремума ().

Требуется с заданной точностью  на отрезке а₀, b₀ найти экстремум функции f (x).

3.1.2.2. Метод ненаправленного поиска

1. Отрезок а₀, b₀ делится на N частей, где N = ( b₀ — а₀) /  .

2. Находятся координаты точек х_i, расположенных внутри интервала неопределенности:

х_i = а₀ + ( i — 1) , i = 1, (N+1).

3. Рассчитываются значения функции в точках f (х_i ).

4. Из полученных значений выбирается экстремальное

Точка х_i , соответствующая F₀, – точка экстремума.

Достоинство алгоритма – простота, недостаток – низкая производительность (для = 1% требуется рассчитать значения функции в 101 точке).

3.1.2.3. Методы направленного поиска

Метод дихотомии (деление отрезка пополам):

1. Интервал неопределенности делится пополам.

2. Находятся значения функции в двух точках, отстоящих от центра на /2.

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

4. На следующем интервале повторяются те же действия.

Рассмотрим более подробно этот метод. Пусть требуется найти минимум функции f (x) на интервале а₀ , b₀ (рис. 3.1) .

f (x)

Находим координату центра интервала неопределенности:

Находим точки, равноотстоящие от х₀ на /2:

Находим значения функции в точках х₀ и х₀, f ( х₀ ) и f ( х₀ ).

Отбрасываем часть отрезка левее х₀, т.к. там минимума нет.

l₁ = b₁ — а₁ – длина нового интервала неопределенности.

Если l₁   , то экстремум найден. За точку экстремума принимают

Если l₁   , то делается по крайней мере еще один шаг.

1. На каждом шаге приближения к экстремуму функция вычисляется дважды.

2. На начальных шагах интервал неопределенности уменьшается примерно на половину. По мере приближения к экстремуму, когда становится соизмеримо с интервалом неопределенности, уменьшается доля отбрасываемой части, т.е. отбрасываемая часть интервала неопределенности не постоянна, что является недостатком метода.

3. Достоинство метода – производительность выше, чем в методе ненаправленного поиска (для нахождения экстремума с  = 1% требуется  20 вычислений функции).

Пример 3.2. Найти максимум унимодальной функции:

e 3 x / 2 , 0  x  0,45

F(x) = 3-2,3x, 0,45 < x  0,7

1. х₀ = (а₀ + b₀ ) / 2 = 0,5.

2. х₀ = х₀ +  / 2 = 0,48, F( х₀ ) = 1,89,

х₀ = х₀ —  /2 = 0,52, F( х₀) = 1,80.

l₁  , следовательно, делаем еще шаг 

Метод «золотого сечения». Сечение отрезка называется золотым, если отношение всего отрезка к большей его части равно отношению большей части отрезка к меньшей. Пусть d – длина отрезка, х – длина большей части отрезка, тогда “золотое сечение”

. (3.1)

, (3.2)

х = (-1  5 ) / 2,

Х = ( 5 — 1) / 2  0,618, (3.3)

1 — Х= (3 — 5) / 20,382.

Рассмотрим алгоритм метода. Введем обозначения: а_к , b_к – границы интервала неопределенности на к-м шаге.

Отметим на этом интервале точки Y_к, Z_к , причем Y_к ближе к левой границе, а Z_к ближе к правой границе интервала неопределенности. Точки Y_к и Z_к симметричны относительно центра и составляют золотое сечение

отрезка а_к , b_к :

0,38 0,24 0,38

1. Определяются координаты точек Y₀ и Z₀:

Y₀ = а₀ + (3 — 5 ) / 2 (b₀ — а₀),

2. Вычисляется функция в точках Y₀ и Z₀ .

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

Записываются новые координаты интервала (рис. 3.2).

Рис. 3.2. Метод золотого сечения

Положим, отброшена левая часть интервала неопределенности (а₀, Y₀), тогда а₁ = Y₀, b₁ = b₀, Y₁ = Z₀, Z₁ = а₁ + b₁ — Y₁ (при отбрасывании правой части объекта Y₁ = а₁ + b₁ — Z ₁).

4. Находится длина нового интервала и сравнивается с :

При l₁   решение найдено, при l₁   делается еще один шаг, причем на каждом последующем шаге значение функции вычисляется только в одной точке (либо в точке Y_к , либо в точке Z_к).

1. На каждом шаге приближения к экстремуму интервал неопределенности уменьшается на 38%.

2. На каждом шаге, кроме нулевого, функция вычисляется один раз.

3. Метод имеет высокую производительность (для нахождения экстремума с точностью = 1% требуется вычислить функцию 11 раз).

Пример 3.3. Найти минимум унимодальной функции f (x) = х 2 — 5х, а₀ , b₀ = 2; 4 ,  = 0,1.

1.Y₀ = а₀ + (3 — 5 ) /2 (b ₀ — а₀) = 2 + 0,382  2 = 2,764,

2. f (Y₀) = — 6,180, f (Z₀) = -5,708 – отбрасываем правую часть интервала неопределенности.

4. l₁ = b₁ — а₁ = 1,236  , следовательно, требуется выполнить еще шаг.

5. f (Z₁) = f (Y₀ ) = — 6,180, f (Y₁ ) = — 6,249. . .

Метод Фибоначчи. Постановка задачи:

1. Начальный интервал неопределенности а₀, b₀.

2. Функция f (x), унимодальная на отрезке а₀, b₀.

3. Точность нахождения экстремума .

Требуется за n измерений функции найти экстремум с точностью .

Метод Фибоначчи считается самым эффективным. Этот метод имеет тот же алгоритм, что и метод «золотого сечения», отличия заключены в координатах начальных точек:

F_n , F_n+2 – n-е и (n+2)-е числа Фибоначчи.

F₁ = 1, F₂ = 1, F_n = F_n-1 + F_n-2 , n = 3, 4, 

F₃ = 2, F₄ = 3, F₅ = 5, F₆ = 8, F₇ = 13, F₈ = 21, F₉ = 34, F₁₀ = 55, F₁₁ = 89, F₁₂ = 144, 

n определяется при помощи неравенства:

Пусть требуется найти экстремум с точностью 0,01. Тогда

( b₀ — а₀ )/  = 100, F₁₁ = 89  100  144 = F₁₂, n = 10,

Далее так же, как в методе “золотого сечения”.

Источник