Условия оптимальности для задачи условной оптимизации

Сформулируем теперь условия оптимальности для задачи условной оптимизации (1.32).

Предположим, что ограничения gi (х) являются непрерывными дифференцируемыми функциями и уравнения связи gi(х) =bi, i = 1,2,…, m < n, могут быть разрешены относительно части переменных (не нарушая общности будем считать, что зависимыми переменными являются m первых компонент x1, х2,…, хn). Для того чтобы выполнялось последнее условие, необходимо, чтобы ранг матрицы Якоби для функций gi (х), i = 1, 2,…, m, равнялся m, т. е. определитель этой матрицы, составленной из производных по первым m аргументам, не равнялся нулю:



Для того чтобы точка х* ∈ D являлась оптимальным решением задачи условной оптимизации (1.32), она должна удовлетворять системе из (n + m) уравнений вида:

∂Q/∂xj|x=x* + ∑λk∂gk/∂xj|x=x* = 0, j=1, 2, …, n;

gi (x*) = bi, i = 1, 2, …, m. (1.60)

По теореме о неявных функциях, если в точке х* выполняется условие (1.59), то из уравнений связи gi (х) = bi, i = 1, 2, …, m, можно выразить зависимые переменные через независимые!

xi = φi (xm+1, xm+2, …, n), i = 1, 2, …, m (1.61)

где φi (xm+1, xm+2, …, n) — непрерывные дифференцируемые функции. Подставляя (1.61) в функцию Q (х), получаем для любых значений х ∈ d (х*, ε) следующее выражение:

Q (φ1(xm+1, xm+2, …, n), …. φ1(xm+1, xm+2, …, n), xm+1, xm+2, …, n = Q* (xm+1, xm+2, …, n). (1.62)

Точка х* является локальным минимумом функции Q* (xm+1, xm+2, …, n). если выполняется условия оптимальности (1.55) для многопараметрической задачи безусловной оптимизации:

∂Q*/∂xj |x=x* = 0, j = m+1, m+2, …, n. (1.63)

По правилу дифференцирования сложных функций, учитывая (1,62), вместо (1.63) можем записать:

∂Q*/∂xj |x=x* = ∑∂Q*/∂xi ∂φi/ ∂xj + ∂Q*/∂xj =0, j = m+1, …, n, (1.64)

где производные ∂φi/ ∂xj, i — 1, 2, …, m, для каждого j представляют собой единственное решение системы уравнений;

∑∂g*/∂xi ∂φi/∂xj + ∂g*/∂xj = 0, k = m+1, …, n,

Вместо того чтобы решать систему уравнений (1.65), поступим следующим образом. Рассмотрим совокупность чисел λi, i = 1, 2, …, m, являющихся решениями системы линейных уравнений:

∑λi∂gi/∂xj + ∂Q/∂xj =0, j = 1, …, m, (1.66)

Решение системы (1.66) существует и единственно в силу предположения (1.59). Умножим k-ое уравнение (1.65) на λk и просуммируем по k от 1 до m. Тогда для каждого j = m + 1, …, n, если поменять порядок суммирования, справедливо соотношение

∑ ( ∑ λi ∂gi/∂xj)∂φi∂xj + ∑λi ∂gi/∂xj = 0.

Прибавляя (1.67) к (1.64), имеем:

∑[ ∂Q/∂xi + ∑λi ∂gi/∂xj]∂φi/∂xj + [ ∂Q/∂xj + ∑λi ∂gi/∂xj] = 0

откуда, учитывая (1.66), получаем, что для выполнения соотношений (1.63), необходимо, чтобы выполнялась система уравнений:

∂Q/∂xj + ∑λi ∂gi/∂xj = 0, j=m + 1,…, n. (1.69)

Объединяя эту систему с системой уравнений (1.66) и уравнениями связи gi (х) — bi, i = 1, …, m, получаем, что точка х* является оптимальным решением задачи условной оптимизации (1.32), если она удовлетворяет системе (n+m) уравнений (1.60).

Условия оптимальности (1.60) для задачи условной оптимизации (1.32) могут быть получены при помощи следующего приема, называемого методом множителей Лагранжа.

Составляется функция (n + m) переменных х = (х1, х2,…, хn) и λ = (λ1, λ2,…, λn), которые считаются независимыми:

L(x, λ) = Q(x) + ∑λi(gi(x) — bi),

по каждой из компонент векторов х и λ, вычисляются частные производные от функции L (х, λ) и приравниваются нулю:

∂L/∂xj = ∂Q/∂xj + ∑λi ∂gi/∂xj, j = 1, 2, …, m;

∂L/∂λi = gi(x) — bi, i = 1,2,…, n.

Функция L (х, λ) называется функцией Лагранжа, а числа λi, которые могут иметь любой знак, множителями Лагранжа.

Представляет интерес ответить на вопрос: какова в терминологии рассматриваемой задачи оптимизации (1.32) интерпретация искусственно введенных множителей Лагранжа λi, i = 1, 2,…, m. С этой целью рассмотрим поведение минимального значения критерия оптимальности Q* = Q (х*) при изменении правых частей bi, i = 1, …, m, уравнений связи:

gi (х) = bi, i = 1, 2, …, m. (4.70)

Пусть х* — оптимальное решение задачи условной оптимизации (1.32), а λ*— множители Лагранжа, соответствующие точке х*. Очевидно, что х* и λ* являются функциями правых частей уравнений связи (1.70):

х* = х* (b), λ* = λ* (b). (1.71)

Предположим, что зависимости (1.71) являются непрерывно дифференцируемыми функциями вектора b = (b1, b2,…, bn), и вычислим частные производные критерия оптимальности Q (х*) и уравнений связи (1.70) по bi в точке х*:

∂Q/∂bi|x=x* = ∑∂Q/∂xj∂xj/∂bi, j = 1, 2, …, m; (1.72)

∂gk/∂bi|x=x* = ∑∂gk/∂xj∂xj/∂bi — δik, i, k = 1, 2, …, m; (1.73)

где

δik = 1, если i=k
0 — в противном случае.

Умножим k-e уравнение (1.73) на λ*k, просуммируем по k от 1 до m и прибавим его к правой части выражения (1.72). Тогда, меняя порядок суммирования, можем записать

∂Q/∂bi = ∑(∂Q/∂xj + ∑λ*k∂gk/∂xj)∂xj/∂bi — ∑λ*kδik, i = 1, 2, …, m.

Так как х* и λ* удовлетворяют условиям оптимальности (1.60), то, учитывая (1.74), получим, что

∂Q/∂bi | x=x* = — λ*i, i = 1, 2, …, m.

Таким образом, множители Лагранжа λ*i, i = 1, 2, …, m, можно интерпретировать как коэффициенты чувствительности минимального значения критерия оптимальности Q (х*) к малым изменениям правых частей уравнений связи (1.70).

Практическое значение полученного результата заключается в том, что, не решая задачи оптимизации (1.32) при новых значениях правых частей уравнений связи (1.70), мы можем оценить, как изменится оптимальное значение критерия оптимальности при малых изменениях вектора b.

При выводе условий оптимальности для задачи выпуклого программирования (1.30) необходимо допустить, что выпуклая допустимая область D имеет внутренние точки. Наличие таких точек гарантирует, что существует хотя бы одна точка х ∈ D, в которой все ограничения могут быть разделены на два типа: активные ограничения, в которых неравенства выполняются как равенства (gi (х) = bi i ∈ J), и неактивные ограничения, являющиеся строгими неравенствами (gk (х) > 0, k ∈ J+, J+ ≠ ∅). Существование внутренних точек множества D можно определить также следующим образом.

Будем называть направление S возможным направлением в точке х ∈ D если можно двигаться вдоль направления S, оставаясь в D. Область D имеет внутренние точки, если возможное направление S в точке х для любого активного ограничения удовлетворяет следующим условиям, называемым условиями регулярности:

(∇giT(x), S) ≥ 0, i∈J. (1.75).

Пусть допустимая область D = {x|gi(x) ≥ 0, i = 1, 2, …, m} удовлетворяет условиям регулярности (1.75). Тогда для того, чтобы точка х* ∈ D была оптимальным решением задачи выпуклого программирования (1.30), необходимо существование таких чисел u* = (u1*, u2*,…, um*), что

gi(x*) ≥ 0, i = 1, 2, … m; (1.76)
ui* ≥ 0, i = 1, 2,…, m; (1.77)
ui*gi(х*) = 0, i = 1, 2, …, m; (1.78)

∇Q(x*) — ∑ui*∇gi(x*) = 0.


Оставить комментарий





Статистика

Рейтинг@Mail.ru