Метод Лагранжа

Рассмотрим классический метод множителей Лагранжа. Классическая задача Лагранжа есть задача с ограничениями-равенствами, мы же проследим ее логическое развитие для задачи с ограничениями-неравенствами.

Итак, пусть ограничения заданы только равенствами h(x)=0. Как известно из математического анализа, для решения такой задачи на условный минимум записывается функция Лагранжа:

L(x, λ) = f(x) – λ^Th(x),

где λ - вектор множителей Лагранжа.

Условия минимума записываются в следующем виде:

а) условия первого порядка:

_xL(x, λ) = _x f(x) – λ^T_xh(x) = 0 (минимум по x);

_{(1) λ} L(x, λ) = h(x) = 0 (максимум по λ).

б) условия второго порядка:

y^T2_xx L(x, λ) y > 0 для всех векторов y, не равных нулю и удовлетворяющих условию: _xh^t(x)y = 0.

Здесь ²_xx L(x, λ) обозначена матрица вторых производных (матрица Гессе), которую для удобства в дальнейшем будем обозна­чать H (x, λ).

Для решения этой задачи можно применить один из двух способов:

- непосредственный поиск седловой точки функции L (x, λ)
одним из известных алгоритмов численного поиска безусловного
экстремума;

- решение (скорее, также численное) системы уравнений (1) -
условий минимума первого порядка.

Пусть теперь в исходной формулировке присутствуют ог­раничения-неравенства g_j(x)>=0. Тогда для решения задачи ис­пользуем следующий характерный прием. Превратим неравенства в эквивалентные равенства путем введения фиктивных перемен­ных z_j:

_j (x,z)=g_j(x) – z_j²=0

Как видно из этого выражения, для какой-либо фиксирован­ной точки x существует значение z_j, для которого это равенство спра­ведливо.

Таким образом, введение фиктивного вектора z размерности r позволяет свести исходную задачу с неравенствами к новой искусст­венной задаче с равенствами. В этой задаче функция Лагранжа имеет вид:

(x, z, λ, μ) = f(x) – λ^Th(x) – μ^T(x, z)

где - μ вектор множителей при искусственных равенствах, имеющий тот же смысл, что и вектор λ.

Поскольку функция _j(x, z_j) явно выражена через z_j, то фиктивные переменные теперь можно исключить, записав условия ми­нимума первого порядка.

= _x f(x) – λ^T _x(x) – μ^T _x (x, z) = 0;

_x(.) = – μ _z (x, z) = 2μ^T z = 0;

_x(.) = - h(x) = 0;

_x(.) = - g(x, z) = 0;

где (.) – (x, z, λ, μ).

Учитывая соотношения _x g(x, z) =_x (x) и z_j = , а также то, что равенствам (x, z) = 0 соответствуют неравенства g(x)>=0, перепишем эту систему уравнений в виде:

μ_j g_j(x) = 0; i = 1, m; j = 1, r; k = 1, n;

h_i(x) = 0;

g_j(x) >= 0;

μ_j >= 0.

Эта система уравнений и неравенств называется условиями Куна - Таккера. Последняя группа неравенств (неотрицательность компонент вектора μ) следует из условий минимума второго поряд­ка.

Отметим, что равенства μ_j = 0 имеют место для пассивных неравенств (действительно, их можно исключить из функции Лагранжа). Напротив, для активных неравенств μ_j строго положитель­ны.

Различают отдельные классы задач нелинейного программи­рования. Среди них обычно выделяют так называемые задачи выпук­лого программирования. Чтобы отнести задачу к этому классу, нуж­но иметь выпуклую функцию f(x), вогнутые функции g_j(x) и линей­ные функции h_i(x). Будем называть точку, удовлетворяющую услови­ям Куна - Таккера, точкой Куна - Таккера.

Отметим, что для задачи выпуклого программирования усло­вия Куна - Таккера являются необходимыми и достаточными усло­виями минимума. При этом точка Куна — Таккера является единст­венной.

В задаче невыпуклого программирования обычно имеется несколько точек Куна - Таккера. Определить, какая из них является условным минимумом, можно только после выполнения условий второго порядка.

Другим выделяемым классом являются задачи квадратичного программирования. Они характерны тем, что f(x) - квадратичная форма, а все ограничения описаны линейными функциями. При этом условия Куна - Таккера являются системой линейных уравнений.

Дата добавления: 2014-01-07