Образовательный блог – всё для учебы

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

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

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

?Q/?x_j|_x=x* + ? ?_k?g_k/?x_j|_x=x* = 0, j=1, 2, …, n;

g_i (x*) = b_i, i = 1, 2, …, m. (1.60)

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

x_i = ?_i (x_m+1, x_m+2, …, _n), i = 1, 2, …, m

(1.61)

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

Q (?₁(x_m+1, x_m+2, …, _n), …. ?₁(x_m+1, x_m+2, …, _n), x_m+1, x_m+2, …, _n = Q* (x_m+1, x_m+2, …, _n). (1.62)

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

?Q*/ ?x_j |_x=x* = 0, j = m+1, m+2, …, n.
(1.63)

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

?Q*/ ?x_j |_x=x* = ? ?Q*/ ?x_i ??_i/ ?x_j + ?Q*/ ?x_j =0, j = m+1, …, n, (1.64)

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

? ?g*/ ?x_i ??_i/ ?x_j + ?g*/ ?x_j = 0, k = m+1, …, n,

Вместо того чтобы решать систему уравнений (1.65), поступим следующим образом. Рассмотрим совокупность чисел ?_i, i = 1, 2, …, m, являющихся решениями системы линейных уравнений:
? ?_i ?g_i/?x_j + ?Q/ ?x_j =0, j = 1, …, m, (1.66)

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

? ( ? ?_i ?g_i/?x_j)??_i/?x_j + ??_i ?g_i/?x_j = 0.

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

?[ ?Q/?x_i + ??_i ?g_i/?x_j]??_i/?x_j + [ ?Q/?x_j + ??_i ?g_i/?x_j] = 0

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

?Q/?x_j + ??_i ?g_i/?x_j = 0, j=m + 1,…, n. (1.69)

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

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

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

L(x, ?) = Q(x) + ? ?_i(g_i(x) – b_i),

по каждой из компонент векторов х и ?, вычисляются частные производные от функции L (х, ?) и приравниваются нулю:
?L/?x_j = ?Q/?x_j + ??_i ?g_i/?x_j, j = 1, 2, …, m;

?L/??_i = g_i(x) – b_i, i = 1,2,…, n.

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

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

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

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

?Q/?b_i|_x=x* = ?Q/?x_j?x_j/?b_i, j = 1, 2, …, m;
(1.72)
?g_k/?b_i|_x=x* = ?g_k/?x_j?x_j/?b_i – ?_ik, i, k = 1, 2, …, m; (1.73)

где

?_ik = 1, если i=k
0 – в противном случае.

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

?Q/?b_i = ?(?Q/?x_j + ??*_k?g_k/?x_j)?x_j/?b_i – ??*_k?_ik, i = 1, 2, …, m.

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

?Q/?b_i | _x=x* = – ?*_i, i = 1, 2, …, m.

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

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

При выводе условий оптимальности для задачи выпуклого программирования (1.30) необходимо допустить, что выпуклая допустимая область D имеет внутренние точки. Наличие таких точек гарантирует, что существует хотя бы одна точка х ? D, в которой все ограничения могут быть разделены на два типа: активные ограничения, в которых неравенства выполняются как равенства (g_i (х) = b_i i ? J^-), и неактивные ограничения, являющиеся строгими неравенствами (g_k (х) > 0, k ? J⁺). Существование внутренних точек множества D можно определить также следующим образом.

Будем называть направление S возможным направлением в точке х ? D если можно двигаться вдоль направления S, оставаясь в D. Область D имеет внутренние точки, если возможное направление S в точке х для любого активного ограничения удовлетворяет следующим условиям, называемым условиями регулярности:
(?g_i^T(x), S) ? 0, i?J^-. (1-75).

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

g_i(x*) ? 0, i = 1, 2, … m; (1.76)
u_i* ? 0, i = 1, 2,…, m; (1.77)
u_i*g_i(х*) = 0, i = 1, 2, …, m; (1.78)

?Q(x*) – ? u_i*?g_i(x*) = 0.

1. Условия Куна-Таккера для условной оптимизации
2. Условия оптимальности для некоторых классов моделей принятия решений
3. Преобразование задачи нелинейного программирования при помощи функций штрафов в последовательность задач безусловной оптимизации
4. Постановка задачи поиска и оптимизации проектных решений
5. Свертывание векторного критерия оптимальности методом выделения главного критерия
6. Задачи и методы оптимизации в системах имитационного моделирования
7. Сведение многомерной задачи оптимизации к задаче одномерного глобального поиска
8. Геометрическая интерпретация задач поиска и оптимизации
9. Упорядочение векторных критериев оптимальности при помощи обобщенной функции цели
10. Задача квадратичного программирования
11. Определение весовых коэффициентов относительной важности частных критериев оптимальности по матрице экспертных оценок
12. Особенности задач поиска и оптимизации проектных решений
13. Многомерный случай для задач безусловной минимизации
14. Особенности ЭМУС как объектов поиска и оптимизации проектных решений
15. Метод последовательных уступок.
16. Использование коллектива независимых стохастических автоматов как некоторой системы поисковой оптимизации
17. Алгоритм, реализующий метод внутренних точек