Расширение с использованием исчезающего слагаемого

Обобщением расширения Лагранжа для задачи НП является задача.

Здесь Ф — произвольная непрерывная функция, причем Ф (0) = 0. На множестве D, когда Дх) = 0, целевые функции исходной и расширенной задач равны, а слагаемое Ф (/) исчезает.

Расширению (2.67) соответствует задача вида

Функция достижимости задачи (2.68) равна.

Градиент и элементы матрицы Гессе для этой функции имеют вид.

Таким образом, матрица Гессе для функции достижимости преобразованной задачи представляет собой сумму.

где у и М — матрицы Гессе функции достижимости исходной задачи и исчезающего слагаемого соответственно. В том частном случае, когда функция Ф линейна, расширение (2.67) совпадает с расширением Лагранжа и выпуклость Я* © определяется выпуклостью /₀*.

Обсудим вопрос о том, как выбирать функцию Ф, чтобы достичь эквивалентности расширения. Как уже отмечалось, для эквивалентности расширения требуется, чтобы максимум на множестве V_c функции достижимости Я*© задачи (2.68) оказался в точке с = 0. Иначе говоря, чтобы через точку Я (0) графика Я '© можно было провести горизонтальную плоскость, проходящую выше графика Я*©. Это требование можно записать в форме уравнения относительно функции Ф или ее параметров:

Пусть функция Я" © дифференцируема, тогда для эквивалентности необходимо, чтобы в точке с = 0 она была стационарна, т. е.

Следовательно, в точке с = 0 градиенты функций /₀* и Ф должны быть равны по величине и противоположны по знаку. Достаточным же условием эквивалентности являются выполнение условий стационарности при с = 0 и выпуклость функции Я" (с, Ф).

Другим общим соображением, определяющим выбор Ф, является то, что на множестве D, т. е. при с = 0, всегда Я* (0) = /₀* (0), и эта ордината Я* не зависит от вида и параметров функции Ф. Так как мы хотим, чтобы Я*(0) оказалось максимальным значением Я*©, то функция Ф© должна уменьшать Я*(с, Ф) как при с 0. При этом обсолютный максимум R*© заведомо уменьшается, а так как он ограничен снизу величиной R*(0), то в пределе он стремится к этой величине.

Наконец, последнее соображение, позволяющее в ряде случаев легко найти вид функции Ф, основано на достаточном условии оптимальности. Для эквивалентности расширения достаточно, чтобы оптимальное решение расширенной задачи или одно из ее оптимальных решений, если их несколько, оказалось допустимым для исходной задачи, т. е. удовлетворяло связям/j (x) = 0 (i = 1, 2, …, m). Пусть нам удалось так выбрать Ф, чтобы функция R в расширенной задаче достигала максимума для очень многих значений вектора хеУ^'и хотя бы одно из них оказалось допустимым, тогда оно и является искомым оптимальным решением исходной задачи. На методике выбора функции Ф, при котором пересечение множества V* и D_a заведомо не пусто, мы остановимся ниже.