Расширения задачи нелинейного программирования, связанные с переходом к безусловной оптимизации

Любую экстремальную задачу можно деформировать таким образом, чтобы ее решение, значение или и то и другое не изменилось. Например, целевую функцию/0(х) можно заменить другой функцией F0(x) так, чтобы для любых допустимых хг и х2 из условия

следовало бы неравенство

т. е. большему значению исходной целевой функции соответствует большее значение преобразованной. Из неравенств (2.42), (2.43) следует, что зависимость F0 от /0 монотонно возрастающая. В тех точках, где F0(f0) дифференцируема,

Преобразование задачи нелинейного программирования

Преобразование, удовлетворяющее условиям (2.42), (2.43), называют монотонным преобразованием целевой функции. При таком преобразовании оптимальное решение исходной задачи обязательно является оптимальным решением преобразованной (рис. 2.20).

Зависимость от х целевой функции и его монотонного преобразования (а) и вид монотонной зависимости F(f) (б)

Рис. 2.20. Зависимость от х целевой функции и его монотонного преобразования (а) и вид монотонной зависимости F0(f0) (б)

Аналогичным образом можно изменить и функции, определяющие множество допустимых решений. Так, в задаче НП условие /(х) = О можно заменить условием

в котором функция F такова, что она обращается в нуль тогда и только тогда, когда/= 0. При таком преобразовании множество допустимых решений не изменяется, а значит, решение х* исходной задачи (будем предполагать, что оно существует) останется решением и преобразованной. Если целевые функции у них одинаковы, то задачи изоморфны.

Ниже мы будем рассматривать задачу НП как исходную (задачуА). Иногда нас будет интересовать эквивалентность расширения относительно решения. В этом случае все задачи, изоморфные А с точностью до монотонного преобразования/о (х), включаем в класс эквивалентности А.

Расширения задачи нелинейного программирования, основанные на снятии ограничений

Рассмотрим две задачи.

Задача А:

Наибольшую трудность при решении задачи вызывает наличие условий в форме/,(х) = 0, так как множество Vx выделяется двусторонними ограничениями на каждую из составляющих вектора х и представляет собой параллелепипед. Задачу (2.46) будем называть исходной.

Задача В:

Здесь через Дх) обозначена вектор-функция с составляющими /,(х).

Сформулируем требования к функции R, при выполнении которых эта задача оказывается расширением для задачи (2.46). Первое из условий (1.12) выполнено, так как множество допустимых решений в задаче (2.46) является подмножеством Vx. Что касается второго условия, то мы будем требовать его выполнения с точностью до монотонного преобразования/0(х), т. е. в форме

Чтобы условие (2.48) было выполнено, необходимо и достаточно монотонности по /о функции R при/= 0, т. е.

для тех значений/0, при которых R(f0, 0) дифференцируема.

Действительно, на множестве DA функции ft = 0, поэтому монотонность R(f0, 0) гарантирует, что на множестве D решения, соответствующие максимумам целевых функций задач (2.46) и (2.47), совпадают.

Рассмотрим теперь задачу из класса А вида

Здесь R совпадает с целевой функцией в задаче (2.47), а вектор- функция F равна нулю в том и только в том случае, когда/(х) = 0, так что множество допустимых решений задачи (2.50) совпадает с множеством Da. Задача (2.50) изоморфна задаче НП, и их оптимальные решения одинаковы. В зависимости от конкретного вида функции R расширенной задачи мы получим соответствующую задачу (2.50). Расширение (2.47) эквивалентно задаче (2.50), от которой оно отличается снятием ограничений. Следовательно, чтобы свести решение задачи НП к решению расширенной задачи без связей (построить эквивалентное расширение), нужно в задаче (2.50) так выбрать функции R и F, чтобы ее функция достижимости имела абсолютный максимум при с = 0, т. е. ее условный и безусловный максимумы совпали.

Достаточное условие оптимальности задачи НП. Для того чтобы х* было оптимальным решением задачи НП достаточно, чтобы оно принадлежало D и доставляло максимум функции RuaV.

Важно выбрать функцию так, чтобы это условие оказалось выполненным.

Предварительно рассмотрим частные виды задач типа (2.50) и соответствующие им расширения.

Расширение Лагранжа

Пусть в (2.47) и (2.50) функция

где Х( — любые ограниченные числа. Функция (2.51) совпадает с функцией Лагранжа (см. подпараграф 2.2.2). Выберем функцию F в (2.50) равной/, т. е. задача (2.50) примет вид

а расширенная задача (2.47) запишется как

Ясно, что задача (2.52) изоморфна задаче НП, так как множество ее допустимых решений то же, что и в задаче (2.46), и для любого из элементов этого множества R(x, X) = /0(х), так как/Ос) = 0. Вопрос об условиях эквивалентности расширения (2.53) сводится к вопросу о том, при каких условиях найдутся такие ограниченные ^-множители, для которых решение задачи НП доставляет функции R максимум на множестве Vx.

Выясним связь между функцией достижимости /0 (с) задачи НП и функцией достижимости задачи (2.52). Ввиду того что

получим

Справедливость выражения (2.54) следует из того, что приДх) = с второе слагаемое в R(x, X) не зависит от х и максимум в (2.54) может быть достигнут только за счет максимизации/0(х). А ее максимальное значение при условиях/(х) = с есть не что иное, как /0* (с). Таким образом, функция достижимости задачи (2.52) отличается от /0* (с) добавлением m-мернои гиперплоскости, проходящей через начало координат. Множители Аг- определяют наклон этой плоскости (это составляющие ее градиента).

Утверждение. Расширение Лагранжа (2.53) задачи НП эквивалентно тогда и только тогда, когда через точку (/0* (0), 0) на плоскости с координатами «/*(с) — с» можно провести плоскость M(c) = ^/qCj +/0*(0), такую что для любого с е Ус 1

При этом X* = -к{.

Плоскость М(с) в том случае, когда (d/J /dc)c=0 существует, является касательной к /0*. В более общем случае эту плоскость называют опорной.

Покажем справедливость этого утверждения в одномерном случае (рис. 2.21). Функция /о (с) может быть и негладкой в точке с = 0, поэтому касательной в этой точке не существует, но опорная прямая может быть проведена. Ее наклон равен к, и она всюду выше, чем /0 Если теперь ко всем ординатам /0* добавить величину -кс, т. е.

то построенная таким образом функция имеет в точке с = 0 горизонтальную опорную прямую, нигде не пересекающуюся с Я*(с). Таким образом, Я*(0) > Я*(с) Усе Vc, т. е. максимум функции достижимости задачи (4.52) оказался в точке с = 0, так что расширение (4.53) эквивалентно задаче (4.52), а значит, и исходной задаче НП.

Вид функций достижимости задачи НП в случае, когда расширение Лагранжа эквивалентно

Рис. 2.21. Вид функций достижимости задачи НП в случае, когда расширение Лагранжа эквивалентно

В том случае, когда такой опорной прямой нельзя построить, как видно из рис. 2.22, никакое значение А не обеспечит нам смещение максимума Я (с) в точку с = 0. Поясним этот факт. На рис. 2.22 абсолютный максимум функции достижимости исходной задачи оказался на правом конце отрезка Vc. Так как мы хотим сместить точку максимума в точку с = 0, то выбираем А отрицательным. При этом правый конец Я* (А0, с) опускается, но зато левый поднимается, и при некотором А0 для двух значений с, одно из которых больше, а другое меньше нуля, величина Я*(с, А0) окажется одинакова. Любое изменение А приводит к увеличению значения расширенной задачи. При А = А0 значение расширенной задачи тахЯ*(с, А0) минимально по А, но больше, чем значение исходной задачи /0 (0).

Вид функции достижимости задачи НП в случае, когда расширение Лагранжа не эквивалентно

Рис. 2.22. Вид функции достижимости задачи НП в случае, когда расширение Лагранжа не эквивалентно

Мы не будем приводить доказательства условия эквивалентности расширения Лагранжа, так как оно представляет собой формализацию тех построений, которые проведены на рис. 2.21 и 2.22. Обсудим лишь некоторые следствия из этого условия.

  • 1. Если функция достижимости /о (с) выпукла, то расширение Лагранжа заведомо эквивалентно (рис. 2.21, б).
  • 2. Если функция /о (с) строго вогнута (даже только в окрестности с = 0), то расширение Лагранжа заведомо не эквивалентно (см. рис. 2.22).

В том случае, когда расширение эквивалентно, можно воспользоваться свойством седловой точки и определить решение х* задачи НП из условия

При этом функции/0(х) и/(х) могут быть и не дифференцируемыми.

Отметим, что, когда расширение не эквивалентно, множители А,0, при которых максимум R(x, к) по х минимален, вовсе не равны составляющим градиента плоскости, касательной к функции /0Чс) в точке с = 0. Они соответствуют равенству максимальных значений R*(c) в нескольких точках, между которыми (внутри выпуклой оболочки множества этих точек) находится точка с = 0. Для одномерного случая таких точек оказалось две. Для случая т измерений, как показано ниже, число таких максимумов не будет превышать (m + 1).

Построим выпуклую оболочку СОус/о (с) функции достижимости на множестве Vc. В некоторых точках она совпадает с /0*(с), в других проходит выше. В тех точках, где выпуклая оболочка совпадает с функцией достижимости, любая опорная к /0* (с) плоскость является опорной и к выпуклой оболочке, для других значений с она не ниже, чем C°vcfo (с), а значит, тем более не ниже, чем функция достижимости.

Таким образом, если в точке с = 0 функция достижимости и ее выпуклая оболочка совпадают, то расширение Лагранжа эквивалентно (достаточное условие эквивалентности).

Покажем, что это условие и необходимо, т. е. в том случае, когда

расширение Лагранжа не эквивалентно. Действительно, согласно определению выпуклой оболочки

Из условия (2.57) следует, что начало координат в пространстве с является внутренней точкой выпуклой оболочки множества, состоящего из точек cv.

Предположим, что вектор V = (Xl,...,X*m) выбран так, что значения функции R в точках cv одинаковы и максимальны, т. е.

Мы имеем (m + 1) уравнение с (т + 1) неизвестными Хь Х2, ..., Хт и R*. Эти уравнения определяют вектор 7.°, для которого плоскость, опорная к Я*(с) и касающаяся этой функции в точках R*(cv), оказывается горизонтальной и отстоящей от начала координат на расстояние Я*(0). Изменение наклона гиперплоскости приведет к тому, что значение функции Я*(с) в некоторых из точек cv возрастет и станет больше, чем Я*(0), а в других уменьшится. Таким образом, никаким изменением X нельзя сделать значение расширенной задачи меньшим, чем Я*(0). Между тем Я*(0) равно ординате выпуклой оболочки функции достижимости при с = 0, так как добавление слагаемого XX'Q не меняет ординаты выпуклой оболочки функции /о (с) в точке с = 0. Таким образом, если выполнено неравенство (2.56), то расширение Лагранжа не эквивалентно, показатель эффективности

а Х° определяется наклоном к° выпуклой оболочки функции достижимости /о (с) в нуле (см. рис. 2.22, б).

В заключение отметим, что опорная гиперплоскость может пройти не через (m + 1), а через меньшее число точек выпуклой оболочки. В этом случае некоторые из yv в (2.57) обращаются в нуль. Число одинаковых максимумов функции Я* (с) меньше, чем (m + 1), однако для этих максимумов условия (2.58) выполнены и все проведенные выше рассуждения остаются в силе.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >