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

• Название: Нелинейное программирование
• Дата: 21.12.2022
• Размер: 220.65 Kb.
• Имя файла: kazedu_132142.docx
• Тип: Реферат; #857585
• страница: 2 из 7

2.2. Множители Лагранжа

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

Рассмотрим задачу минимизации функции n переменных с уче­том одного ограничения в виде равенства:

Минимизировать (3)

при ограничениях (4)

В соответствии с методом множителей Лагранжа эта задача преобразуется в следующую задачу безусловной оптимизации:

минимизировать L(x,u)=f(x)-u*h(x) (5)

Функция L(х;u) называется функцией Лагранжа, u — неизвест­ная постоянная, которая носит название множителя Лагранжа. На знак u никаких требований не накладывается.

Пусть при заданном значении u=u⁰ безусловный минимум функ­ции L(x,u) по х достигается в точке и удовлетворяет урав­нению . Тогда, как нетрудно видеть, x⁰ минимизирует (1) с учетом (4), поскольку для всех значений х, удовлетворяющих (4), и L(x,u)=min f(x).

Разумеется, необходимо подобрать значение u=u° таким обра­зом, чтобы координата точки безусловного минимума х° удовлетво­ряла равенству (4). Это можно сделать, если, рассматривая u как переменную, найти безусловный минимум функции (5) в виде функции u, а затем выбрать значение u, при котором выполняется равенство (4). Проиллюстрируем это на конкретном примере.

Пример 2

Минимизировать

при ограничении =0

Соответствующая задача безусловной оптимизации записывается в следующем виде:

минимизировать L(x,u)= -u

Решение. Приравняв две компоненты градиента L к нулю, получим





Для того чтобы проверить, соответствует ли стационарная точка х° минимуму, вычислим элементы матрицы Гессе функции L(х;u), рассматриваемой как функция х,

,

которая оказывается положительно определенной. Это означает, что L(х,,u) — выпуклая функция х. Следовательно, координаты , определяют точку глобального минимума. Оптималь­ное значение u находится путем подстановки значений и в урав­нение =2, откуда 2u+u/2=2 или . Таким образом, условный минимум достигается при и и равен min f(x)=4/5.

При решении задачи из примера 2 мы рассматривали L(х;u) как функцию двух переменных и и, кроме того, предполагали, что значение параметра u выбрано так, чтобы выполнялось ограни­чение. Если же решение системы

, j=1,2,3,…,n

в виде явных функций u получить нельзя, то значения х и u нахо­дятся путем решения следующей системы, состоящей из n+1 урав­нений с n+1 неизвестными:

, j=1,2,3,…,n

Для нахождения всех возможных решений данной системы можно использовать численные методы поиска (например, метод Ньютона). Для каждого из решений ( ) сле­дует вычислить элементы матрицы Гессе функции L, рассматри­ваемой как функция х, и выяснить, является ли эта матрица поло­жительно определенной (локальный минимум) или отрицательно определенной (локальный максимум).

Метод множителей Лагранжа можно распространить на случай, когда задача имеет несколько ограничений в виде равенств. Рас­смотрим общую задачу, в которой требуется

Минимизировать f(x)

при ограничениях =0, k=1, 2, ..., К.

Функция Лагранжа принимает следующий вид:

L(x,u)=f(x)-

Здесь —множители Лагранжа, т.е. неизвестные параметры, значения которых необходимо определить. Приравни­вая частные производные L по х к нулю, получаем следующую систему n уравнении с n неизвестными:





………..



Если найти решение приведенной выше системы в виде функций вектора u оказывается затруднительным, то можно расширить систему путем включения в нее ограничений в виде равенств






Решение расширенной системы, состоящей из n+К уравнений с n+К неизвестными, определяет стационарную точку функции L. Затем реализуется процедура проверки на минимум или максимум, которая проводится на основе вычисления элементов матрицы Гессе функции L, рассматриваемой как функция х, подобно тому, как это было проделано в случае задачи с одним ограничением. Для некоторых задач расширенная система n+К уравнений с n+K неизвестными может не иметь решений, и метод множителей Лагранжа оказывается неприменимым. Следует, однако, отметить, что такие задачи на практике встречаются достаточно редко.