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

Одним из возможных способов расширения множества, задач математического программирования, поддающихся решению численными методами, является параметризация их постановки. Параметризация заключается в разделении множества, переменных исходной задачи:

найти min f (х,и)                                           (1)

х,и при условиях д8(х,и) > 0, s = [1,m], на два подмножества: собственно переменных х € Еп и пара метров и € Е1, значения которых при необходимости могут быть зафиксированы. Такое разделение позволяет свести решение исходной задачи к двухуровневой системе задач [2, 4]:

найти min f (х,и)                                           (2)

Ж при условиях gs(x,u) > 0, s = [1,m], найти min f(х*(и),и)                                              (3)

и при условиях gs(x*(и), и) > 0, s = [1,m], где х*(и) есть решение задачи (2) при фиксированном векторе параметров и. Обозначим локальное решение задачи (1) как {х*,и*}. Условимся также в дальнейшем задачу (3) называть задачей верхнего уровня, а задачу (2) будем называть задачей ниэюнего уровня. Пару задач верхнего и ниэюнего уровней будем называть двухуровневой системой задач, или задачей параметрического программирования.

В этом случае упрощение процедуры решения исходной задачи (1) может быть обусловлено как очевидно меньшей размерностью задач (2) и (3) (по сравнению с размерностью задачи (1)), так и возможным упрощением их постановок. Примером такого упрощения является случай, когда, за. счет подходящего выбора, параметризуемых переменных задача, нижнего уровня оказывается линейной.

Проблемы и подход к решению двухуровневой системы задач с помощью метода, штрафных функций рассматриваются в [4]. Для решения задачи используется достаточно гладкая по своим аргументам штрафная функция Р(г, а) такая, что lim Р(г, а) = I +”, '    0,                              (4)

г^+а            (    0, а > 0, и удовлетворяющая неравенствам

ЭР     д2Р

.. 6 0 и >  0 V а.

да      да2

При использовании метода штрафных функций задача нижнего уровня (2) является стандартной задачей безусловной минимизации в Е^п;

х+(т, и) = arg min е(т,х,и),(6)

жеЕ"

где вспомогательная функция метода гладких штрафных функций имеет вид [3]:

т

е(т, х, и) = /(х, и) + У^ Р[т, gs(x, и)].(7)

S=1

Итерационный процесс решения этой задачи рассматривается также в [3].

На верхнем уровне выполняется оптимизация функции:

Е(т, и) = е(т, х+(т, и), и), и Е Е1.(8)

Обозначим

U(t) = arg min Е(т,и).(9)

иеЕ1

Для практического решения задач верхнего уровня может быть использована стандартная [1] итеративная схема построения последовательных приближений к искомому решению U ( t ) в пространстве Е¹, k-й шаг которой состоит из следующего набора операторов:

• 1)    для некоторого исходного приближения ик находится решение задачи (6): х ⁺ ( т, и^);

• 2)    затем вычисляются улучшающее направление w^ в пространстве параметров Е¹ и величина шага ст к по этому направлению;

• 3)    выполняется переход к точке и^₊1 по формуле

ик+1 =и_к + ст_к w_k ;                                (10)

• 4)    если в ик+1 условие окончания итерационного процесса. не выполнено, то ик присваивается значение ик+1 и делается переход к пункту 1.

2.    Условия сходимости итерационного процесса

В случае сходимости данной процедуры будет найдено {х ⁺ ( т, и), U ( t ) } - приближенное локальное решение задачи (1). При этом будут справедливы предельные соотношения [5]:

lim U ( t ) = и*, г^+0

lim х ⁺ ( т, U ( t )) = x*.

г^+0

Теперь рассмотрим вопрос о сходимости итерационного процесса (10). Предварительно докажем ряд вспомогательных утверждений.

Лемма 1. Пусть функции р(и) и ^(и) удовлетворяют условию Липшица на компакте М С Е¹:

|Mu1 ) - ^(и2) Н 6 Ми. - « 2 і V и1,и2 Е М,

||^(и1) - ^(и2) Н 6 Рф Ни1 - и2 || V и1,и2 Е М.

Тогда функции

• 1)    р^(и) ■ г:сі.

• ²⁾    ^^(и) • ^^(и)

такэюе удовлетворяют условию Липшица на множестве М.

Доказательство.

Рассмотрим функцию /(и) + Ки). Для нее будет справедливо

II /^(иі) ⁺ W¹^ ^— /^(u2) ^—-гММН 6 II /^(иі) ^— /^(и2 )Н ⁺ II ^х) ^—^M¹ 6

6 ^LP^{h n}i ^{— U}2 Һ + Сф || ^п1 ^{— и}21| = ^(Lp + Һф )| ^п1 ^{— и}21|.

Следовательно, она удовлетворяет условию Липшица на М . Теперь рассмотрим произведение /(и) • Ки):

|| /(иі)-ф(иі) — / ( u 2 ) 1 ( u 2 )|| =                                                             (11)

= || /(иі)1(иі) — <р(гіі)-ф(гі2) + /(иі N(12) — / ( u 2 ) 1 ( u 2 )| =

= һ /О^іХ^і) ^— tX^T ^1(и2⁾⁽/^(иі^{) —} /^(и2^))һ 6

• ^{6 1} /О^І • ¹ ^(vi) ^— W^X ⁺ ll¹(^U2)h • ¹ /^(иі ) ^— /(^U2)||-

• Если функция удовлетворяет условию Липшица, то она непрерывна. Так как М — компакт, то /(и) и 1(и) ограничены на М . Следовательно, существуют такие числа Ср и Сф, что
• || /(и)| 6 Ср V и Е М,                                (12)

|| 1(и)| 6 Сф V и Е М.

Из (И) и (12) получаем

II /(ui)1(ui) — /(12)1(12) | 6 (Ср L^ + Сф Lp)| иі — U2I.

Лемма 2. Пусти функция /(и)

• 1)    непрерывна, на отрезке [а, Ь] Е R,

• 2)    дифференцируема на отрезке [а, Ь], за исключением точек х_і,х₂, ...,х_п Е [а, Ь],

• 3)    3 /'(х^ ± 0) Е R.

Тогда /(и) удовлетворяет условию Липшица на отрезке; [а, Ь]:

| /(иі) —/(и2)| 6 L|u i — и2| V иі,и2 Е [а, Ь],                        (13)

и

| /'(и ± 0)| 6L Vu Е [а, Ь].                                 (14)

Доказательство.

Из условий (2) и (3) леммы следует ограниченность лево- и правосторонних производных функции /(и) на [а, Ь], значит, существует константа L, удовлетворяющая (14). Докажем (13). Без ограничения общности можно считать, что иі < хі < Х2 < ... <  х_п < U2. Применим формулу конечных приращений Лагранжа на отрезках [иі,хі], [хі,Х2], ..., [x„,U2]:

| /(иі) — /(U2)| = | [/(иі) — /(хі)] + [/(хі) — /(Х2)] + ... + [/(х_п) — /(U2)] | 6

6 | /(иі) — /(хі) | + | /(хі) — /(Х2) | + ... + | [/(х„) — /(U2) | =

= | /'(сі) | • | иі — хі | + | /'(с2) | • | хі — х2 | + ... + | /'(с„+і) | • | х„ — U2 | 6

• 6 L| Пі — хі | + L| хі — х2 | + ... + L| х_И — U2 | =

= L| иі — U2 |.

Следствие 1. Если в условии леммы 2 предположить, что количество точек разрыва производной счетно и lim х_п = и₂, то утверждение леммы останется верным. Это следует из непрерывности функции у(и) на отрезке [а, Ь\ и свойств пределов.

Действительно, из

| у(пі) - у(хп)| 6 L| иі - хп | при стремлении п к бесконечности следует

| ^(U1) - ^(П2)| 6 L| Щ - U2 |.

Лемма 3. Пусть функция д(и) непрерывно дифференцируема в выпуклой области G С Е¹. Рассмотрим функцию

Ци) = ө(-д(и))д(и), где Ө(а) - стандартная функция Xевисайда. Если для любых и1,и2 G G граница множества, являющегося пересечением множества нулей функции д(и) и отрезка, соединяющего точки и1 и и2, состоит из счетного количества точек, то функция ^(и) удовлетворяет условию Липшица в области G:

II К(иі) - ^(и2)| 6 L^U1 - U₂| V U1,U2 G G.

Доказательство.

Отметим, что функция д(и) в условии леммы — это некоторая g_s(x+(r, и), и) из задачи (3). Из условий леммы следует, что функция һ(и) непрерывна в области G, а производная ^‘(и) существует всюду, кроме точек, являющихся нулями функции д(и), и ограничена:

• 3 L : I һ'(и)Ц 6 L для всех и, где производная определена.

Рассмотрим пересечение множества нулей функции д(и) и отрезка, соединяющего точки иі и и2. Занумеруем точки, принадлежащие границе этого пересечения, в порядке движения от иі к и2: хі,х₂, ...,х_п,... Без ограничения общности можно считать, что lim х_п = и₂. п^+^

Теперь применим к функции одной переменной

y(t) = Һ(и1 + t(u2 - иі)),   0 6 t 6 1, на отрезке [0,1\ следствие из леммы 2:

II ^(иі) - К(и2 )| 6 L|u i - U2H V U1,U2 G G.

■

Теперь рассмотрим условия сходимости итерационного процесса (10) при решении задачи верхнего уровня (задачи безусловной минимизации (8)). В общем случае минимизируемая функция верхнего уровня (8) является невыпуклой, поэтому представляют интерес теоремы сходимости для минимизации как выпуклых, так и невыпуклых функций (см. [1]). В этих теоремах при условии существования локального минимума предъявляются следующие требования:

• 1)    функция (8) должна быть дважды непрерывно дифференцируема, и матрица её вторых производных локально положительно определена (при использовании методов 2-го порядка, например, метода Ньютона [3]);

• 2)    градиент функции (8) должен удовлетворять условию Липшица (при использовании методов 1-го порядка, например, градиентного поиска);

• 3)    величина шага определяется методом дробления или одномерной минимизации [1].

В первую очередь отметим, что функция (8) является дважды непрерывно дифференцируемой, если дважды непрерывно дифференцируемыми по своим аргументам являются функции J (x,u), g_s (x,u), s = [1,ш] и Р (г, а) [4], и является также локально выпуклой в окрестности решения (9) [5]. Сформулируем теперь условия, которым должны удовлетворять функции /(x,u), g_s(x,u), s = [1,rn] и Р(г,а) чтобы функция (8) удовлетворяла условию Липшица.

Теорема 1. Пусть функции J(ж, u), g_s(x,u), s = [1,rn] и Р(г, а) дваэюды дифференцируемы на компакте М С Е¹. Тогда градиент функции (8) удовлетворяет условию Липшица на множестве М.

Доказательство.

Утверждение теоремы следует из леммы 1, а также того, что градиент дважды дифференцируемой функции удовлетворяет условию Липшица на множестве М и дифференцируемости функции ж+(г, и) [4].

■

Теорема 2. Пусть функции J(x,u),g_s(x,u),s = [1,rn] дважды непрерывно дифференцируемы в замыкании ограниченной выпуклой области G С Е¹, Р(г, а) - квадратичная штрафная функция:

Р(г, а) = (     , ^а< ⁰,

^{V }}     ( 0, а >  0.

Множество нулей функции gs(x+(u),u) удовлетворяет условиям леммы 3 для любого s. Тогда градиент функции (8) удовлетворяет условию Липшица на множестве G.

Доказательство.

Утверждение теоремы следует из леммы 1 и леммы 3.

3.    Заключение

Таким образом, рассмотрен итерационный процесс решения задачи параметрического программирования (2) - (3). Обоснованы условия сходимости двух классов численных методов безусловной минимизации для целевой функции (8) в пространстве параметров.