Метод параметрической линеаризации, использующий штрафные функции со всюду обратимой производной для решения пар двойственных задач

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

В данной работе исследуется один из возможных вариантов декомпозиционной схемы — метода параметрической линеаризации, описанной в общем виде в [2], идея которой заключается в следующем.

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

Приведем описание процедуры параметрической линеаризации. Пусть x Е En, u Е Ek и ||x| | = = ||f 1 f 2 • • • fn| ^T- ||u| | = |v 1 V 2 ... Vk | |^T. а. исходная задача, математического программирования имеет

вид:

максимизировать по x и и функцию F ( x, и ) при условиях

x > o, и Е П С E^k, fi ( x,u ) 6 0 Vi = [1 ,m ] ,

которая в координатной форме записывается так: максимизировать по x, и:

n

F (x,u) = ^°j (и) fj j=1

при условиях fj >  0 V j = [1 ,n ] , и Е П ,       (2)

n fi(x, u) = -0i(и) +52 aij(и)fj 6 0 Vi = [1, m].

j =1

При фиксированном и задача (2) принимает вид:

максимизировать по {f 1 , f 2 ,.. ., f_n}:

n

F ( x,u ) = ^CTj fj , j=1

при условиях fj >  0 V j = [1 , n ] ,             (3)

n fi(x,u) = -0i + ^aijfj 6 0 Vi = [1 ,m].

j =1

Это — задача нижнего уровня, она. линейна, по переменным f 1,f2,...,fn. Пусть ее1 решение x*(и). тогда, задача верхнего уровня запишется так: n максимизировать по и F(x* (и), и) = 52 Ej (и)f* (и) j=1

при условии и Е П.

Тот факт, что зависимость x* (и) входит в условие этой задачи, может в значительной степени осложнить процедуру решения. Действительно, пусть начальное приближение к ее решению есть и0, а последующее определяется для каждого шага t стандартным итерационным соотношением ut+1 = ut + ptwt, t = 0, 1,2,...,        (4)

где wt — локальное улучшающее F ( x* ( и ) , u ) направление в E^k, a pt — величина шага по этому направлению. Тогда, например, в результате

«неудачного» выбора, величины шага, может оказаться, что задача (3) несовместна для ut ⁺¹, то есть x* ( u ) не будет определена. В другом случае может оказаться, что задача. (3) совместна, по имеет неограниченный целевой функционал или же пеедипствеппое решение. То есть зависимость x* ( u ) может нс быть опроделенной для всех u Е О. Но даже, если она. и определена, то в силу неоднозначности может не быть функциональной. Наконец, даже при тех u, для которых зависимость x* ( u ) определена и однозначна, она практически всегда, оказывается «негладкой», что делает невозможным использование тейлоровских аппроксимаций для поиска, локально улучшающих F ( x* ( u ) , u ) направлений.

В [3,4] был предложен подход, в котором отмеченные (за. исключением одного) затруднения удается единообразно преодолеть при помощи использования метода гладких штрафных функций [5,8]. В этом подходе зависимости x* ( u ) заменяются достаточно гладкими вектор-функциями x ( т, u ), которые являются точкой максимума, вспомогательной функции

для тех u , при которых x* ( u ) существует, позволяет использовать схему (4) для приближенного решения задачи верхнего уровня.

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

минимизировать по Л Е Em с коорд!гнатами {А 1,

А2.....Ат} футщию G(Л,u)= £ ^iAi i =1

при условиях

Ai > 0 V i = [1, m], m gj(x,u) = -aj + 22 aijAi > 0 V j = [1, n].

m ap(т, x, u) = F(x, u) - 22 P (т, -f(x, u))    (5)

i =1

Пусть Л * ( u ) — решение задачи (7) при некотором фиксированном u , тогда для вспомогательной функции этой задачи

задачи нижнего уровня при фиксированных т и u. Иначе говоря, x ( т,u ) = argmax Ap ( т,x,u ).

x

Потребуем дополнительно, чтобы штрафные функции P ( т, s ) были непрерывны вместе со своими производными до второго порядка, включительно для всех s и любых т >  0, а также удовлетворяли условиям¹:

lim P ^{( т,s} ) = т ^ +0

и, кроме того,

∂P

< 0 и ∂s

0 , + го,

s >  0 , s <  0

n

Ad ( т, Л ,u ) = G ( x,u ) + X P ( т,gj (Л ,u ))    (8)

j =1

будет справедливо предельное соотношение lim Ad(т, Л(т, u),u) = G(Л*(u),u), т ^+0

где Л(т, u) = argmin Ad (т, Л, u), а также выполнено л условие стационарности gradл Ad(т, Л(т, u), u) = o.           (9)

д ² P ds ²

0 ,

причем ds[ = отношения у.

Ф I у I , то есть зависит только от Последнее условие (как показано

Кроме того, в случае однозначной разрешимости задач (3) и (7) будут иметь место равенства.

lim x ( т, u )= x* ( u ) и lim Л( т, u ) = Л * ( u ) .

т ^ +0                   т ^ +0

в [8]) гарантирует дифференцируемость функции x ( т, u ) по т при т ^ +0,

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

ции gradx Ap(т, x(т, u), u) = o.            (6)

Требуемые от x ( т, u ) однозначная определенность и достаточная гладкость обеспечиваются свойствами вспомогательной функции (5), в пер

вую очередь применимостью теоремы о неявных функциях [6] к условию (6). А предельное соотношение

Однако, в случае, когда, задачи (3) и (7) несовместны, имеют пеедипствеппое решение или же решение, неограниченное в допустимой области, оказывается возможным получать сглаженные аппроксимации зависимостей x* ( u ) и Л * ( u ) путем построения некоторой специальной системы уравнений. Как будет показано ниже, такая система, позволяет одновременно находить аппроксимации независимо от того, являются задачи (3) и (7) регулярными или пет и без использования какой-либо схемы регуляризации.

Рассматриваемый подход основан на. справедливых для задач (3) и (7) соотношениях

lim Ap ( т, x ( т, u ) , u ) = F ( x* ( u ) , u ) т ^ +0

∂P lim угу (т, —fi(x(т,u))) = —А* (u) Vi = [1 ,m], т ^+0 dfi

1 Следует отметить, что достаточно часто используемые в вычислительной практике «барьерные» штрафные функции с P (т, s) = + ^ при s 6 0 или «внешние» штрафньie функции, для которых P (т, s) = 0 пр и s > 0, этим условиям не удовлетво ряют.

∂P т 1™0 dgj- (T,9j(Л(T,u))) = —ез (u) Vj = [1 ,n]

λ ∗

1 ^∗

3 ’

λ^∗ 2

3 ’

G^* = 10 .

в случае, когда, их решения существуют и единственны [7]. В этом подходе предлагается вместо сглаживающих аппроксимаций Х(т, и) и Л(т, и) использовать аппроксимации х(т,и) и Л(т,и) такие, что lim x(т, и) = x* (и), τ→+0 ^^^^

lim Л( т, и ) = Л * ( и ) τ→ +0

И f. (т, -fi(x(т,и))) = —Ai(и) dP (т,9з(Л(т, и))) = —1з(и)

V i = [1 , m ].

V j = [1 ,n ]

V т e (0 , T ) для некоторого (фиксированного T >  0.

Поскольку др >  о V s ii V т >  0. то (функция Г — yP ] ^п0 s строго монотонна и потому [6] имеет обратную, которую обозначим как Q ( т, s ). Это позволяет записать систему (10) в ином, более удобном для использования, виде:

Г — fi ( ( x ( т,и )) = Q ( т,А i ) V i = [1 ,m ],

1 9з (Л( т,и )) = Q ( j )    V j = [1 ,n ].

Или, окончательно, n _ _ в (и) — Е^з (и) ^з = Q (т,Ai)

j =1

m _ _

^з ^{( и} ) ^— Е ^aij ^{( и} ) ^Ai = ^{—Q ( т}3 )

i =1

V i = [1 ,m ].

(И)

V j = [1 ,n ]•

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

Пример 1. Прямая задача:

максимизировать в E2 фуикцию F = 2е 1 +3е2 при условиях е 1 > 0. е2 > 0 и е 1 + 2 е 2 6 6,

2 е 1 + е 2 6 6 .

Двойственная задача: минимизировать в E ² (функцию G = 6 A 1 + 6 A 2 при ус.товиях A 1 > 0. A 2 > >  0 и

A 1 +2 A 2 >  2 ,

2 A i + A 2 > 3 .                 □

Легко видеть, что обе эти задачи имеют единственные решения е1* = 2, е2* = 2, F* = 10

В качестве штрафной функции используем предложенную в [8] P ( т, s ) = т exp( — - ) удовлетворяющую всем сформулированным выше условиям и для которой Q ( т,s ) = —т in s. Тогда вспомогательные функции двойственной пары задач примера. 1 будут

Ap ^{( т}, ^е 1 ^,е 2) = ^{2 е} 1 ^{+3 е} 2 ^—

_ _{т exp} ( е 1 + 2 е 2 — 6 } _ _{т exp} ( 2 е 1 + е 2 — 6 } Ad ⁽ Т, ^A 1 , ^A 2) = ^{6 A} 1 ^{+ 6 A} 2 ⁺

+ т exp ( ² — ^A 1 _т ^{— 2 A 2} ) + т exp ( ³ — ^{2 A} _t ¹ — ^{A 2} ) , а их условия стационарности (6) и (9) соответственно

| 2 — exp ^ ^ 1 ^{+ 2} Т ² ~ ⁶ ) — 2 exp ( ² ^ 1 ⁺ _Т ^ ² ~ ⁶ ) = 0 , [ 3 — 2 exp ( < 1 ^{+ 2} < ² - ⁶ ) — exp ( ² < 1 ⁺ < ² "  ⁶ ) = 0

(12) и

• 6 — expl ^{2 - Х} 1 _Т ^{- 2 Х 2} J — 2exp I ^{3 - 2} Т^{1 - Х 2} ) = 0 ,

• 6 — 2 exp I ^{2 - Х} 1 _Т ^{- 2 Х 2} J — exp I ^{3 - 2} Х -^{1 - Х 2} ) = 0 .

Наконец, система, уравнений (11) будет иметь вид

^^^™                              ^^^^а^^^™

• 6 — е 1 — 2 е 2 + т in a 1 = 0 ,

^^^™                       ^^^^а^^^^а

• 6 — 2 е 1 — е 2 + т in a 2 = 0 ,

^^^а                                ^^^^а^^^а

• 2 — A1 — 2 A 2 — т in е 1 =0

^^^а                         ^^^^а^^^а

• 3 — 2 A1 — A 2 — т in е 2 =0

  
  

Приведем решения как систем (12) - (13), так и системы (14), полученные при помощи программного средства. MathCAD для значения параметра, штрафа т = 0 . 01, в удобной для сравнения результатов таблице 1.

Результаты, приведенные в таблице 1, демонстрируют, во-первых, факт близости полученных оценок к точному решению (что обусловлено использованием метода, гладких штрафных функций в качестве базового алгоритма), и, во-вторых, несовпадение оценок {x ( т, и ); Л( т, и ) } и {x ( т, и ); Л( т, и ) } в случае, когда значение т не является бесконечно малым.

Таблица. 1

	ξ 1	ξ 2	F	λ 1	λ 2	G
Система. (12)	1.99172	2.00558	10.00017
Система. (13)				1.33102	0.33103	9.97229
Система. (14)	1.99168	2.00559	10.00013	1.33099	0.33106	9.97230

Исследуем теперь свойства, системы (11). В первую очередь, естественно, возникает вопрос о содержательном смысле условий (11), ответ на. который дают нижеследующие теоремы.

Рассмотрим функцию U ( т, х, Л , u ), заданную при фиксированных т и u на прямом произведении пространств En и Em значения которой находятся по формуле

n

U(т,х, Л,u) = X (.•(u)^j + R(т, ej)} + j=1

m           nm

+ Е ( li ( u ) Xi - R ( т, Xi )) - E E aij ( u ) ej Xi,  (15)

i =1                          j =1 i =1

s где R (т,s) = J Q (т,t) dt, г i. ||e 1 e 2 •••€nhT 11

||X 1 X ₂ •••Xml ^T — соответственно координатные представления векторов х е En и Л Е Em.

Теорема 1. Если х ( т, u ) и Л( т, u ) — решения системы (11), то {х ( т,u ) , Л( т,u ) } — стационарный вектор функции U ( т,х, Л , u ) в En х Em.       □

∂U

∂ξj

m

.j ( u ) — Е “Ч ( u ) Xi + Q ( т^ ) V j = [1 ,n ] , i =1

∂U          n dX = ei(u)- E aij(u) ej- Q (т, Xi)

V i = [1 , m ] ,

j =1

что в силу соотношений (11) дает

|U (х(т,u), Л(т,u)) =0 ∂ξj dU (х(т,u), Л(т,u)) =0

Vj = [1 , n ] ,

V i = [1 ,m ] •

Теорема 2. Если х ( т, u ) и Л( т, u ) — решения системы (11), то {х ( т,u ) , Л( т,u ) } — седловая точка, функции U ( т,х, Л , u ) в En х Em. □

Доказательство. Рассмотрим зависимость функции U(т, х, Л, u) от х при фиксированных значениях т, Ли u. Из соотношений (11) получаем д 2 U _dQ dejдек    aej 5jk    j, [, ]

(где 5j_k — символ Кронекера), что означает диагональность матрицы Гессе функции U ( т, х, Л , u )

по компонентам х.

Покажем, что эта. матрица, отрицательно опре-

деле! МИНО det шая. Действительно, значениг ров вида. д2 U     д2 U           д2 U 1x2" д^ 10^ 2          Ь^ 1 д^к ∂2U     ∂2U           ∂2U 8^2811     Э12            81281к . . .                          . . .                   . . .                   . . . д2 U     д2 U           д2 U 81к 011   д1к д12           д1к ее главных V к = [1, n ] определяются по формулам п g vк=[1 .”]• j=1 j

Числа.

∂Q

∂ξ j

отрицательные, так как в силу связи между производными взаимно обратных функций

[6] II условия dP >  0:

∂Q ∂s

_∂ 2 _P

< 0 •

Таким образом, все миноры нечетного порядка, отрицательны, четного — положительны, и, согласно критерию Сильвестра, матрица. Гессе функции U ( т,х, Л , u ) по компонентам х отрицательно определена, а сама функции U ( т, х, Л , u ) по компонентам х имеет максимум в стационарной точке.

Аналогично доказывается, что функция U ( т,х, Л , u ) по компонентам Л имеет минимум при фиксированных т,х и u. Окончательно получаем, что при фиксированных т и u точка {х ( т,u ) , Л( т,u ) } является седловой для функции U ( т,х, Л ,u ) в En х E^m.

Лемма 1. Для любого фиксированного s >  0 lim R ( т, s ) = 0. □ т ^ +0

Доказательство. Поскольку dP = Ф (т)’ а функция Ф I s I имеет монотонную обратную, то вид зависимости Q (т, s) определяется соотношениями s = Ф (Q) ^ Q = Ф_ 1(s) ^ Q(т, s) = т • Ф_ 1(s),

s что в сочетании с условием R(т, s) = J Q (т, t) dt доказывает лемму.                    °

Теорема 3. Для любого фиксированного s > >  0:

lim U ( т,х, Л , u )= L ( х, Л , u ) , т ^ +0

где L ( х, Л , u ) — (функция Лагу)аижа задачи (3). □ Доказательство. Функция Лагранжа, задачи (3) имеет вид nm  n

L(х, Л, u) =    ,,.ej      X. V-h + Е aijej) , j=1        i=1            j=1

или n     m    mn

L ( х, Л , u ) = £ .j ej + E eiXi - E E aij ej x . ^ j =1         i =1         i =1 j =1

Теперь очевидно, что применение леммы 1 к формуле (15) позволяет сделать заключение о справедливости утверждения данной теоремы.

Теорема 4. В случае регулярности (существования и единственности) решения пары двойственных задач (3) - (7) справедливы соотношения lim х( т, u ) = х* (u),    lim ,Л( т,u )=Л * (u), т ^+0                т ^+0

Таблица. 2

τ 0.1 0.02 0.003 0.001 0.0005 0.0001 _ _ £1 = £,2 0.536192 0.506999 0.501041 0.500347 0.500173 0.500035 _ λ1 2.062326 2.013585 2.002073 2.000693 2.000346 2.000069 где х(т, и) и Л(т, и) — решения системы (11) при фиксированном и.

Доказательство. Функция Лагранжа, задачи (3) в регулярном случае при фиксированном и имеет единственную седловую точку {ж* ( и ) , Л * ( и ) } . Фуикция U ( т, х, Л , и ) всегда, имеет единственную седловую точку при фиксированных т, и. Тогда в силу утверждения теоремы 3 получаем, что для регулярной исходной задачи (3):

lim х ( т, и ) = х* ( и ) ,    lim Л( т, и )=Л * ( и ) .

τ→ +0                 τ→ +0

дипствеппое решение и требует соответствующей регуляризации.

Наконец, система, уравнений (11) будет иметь ВИД

_ _ _

1 - е 1 - е 2 + т ln А 1 = 0 , _ _

2 - А 1 - т ln е 1 = 0 , ^^^^.                                                  _____

2 - А 1 - т ln е 2 = 0 .

Заметим, что при любом т > 0 она имеет решение я я         — А е 1 = е2 = exp I —т-1) 1 гДе А 1 — корень уравнения

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

Пример 2 (случай неединственности).

Прямая задача: максимизировать в E ² функцию F = 2 е 1 + 2 е 2 при ус.товиях е 1 > 0. е 2 >  0 i1 е 1 + ^{+ е} 2 6 1-

Двойственная задача: минимизировать в E ¹ функцию G = А 1 при условиях А 1 > 0. А 1 > 2. А 1 > 2. □

Легко видеть, что прямая задача, имеет решение: е* = М* = 1 - t- t G [0 , 1]. F* = 2. оно пеедипствеппое, в то время как двойственная переопределена и имеет решение: А 1 =2, G* = 2.

Рассмотрим вначале схему, использующую вспомогательные функции (5) и (8). Опи соответственно будут иметь вид

^^^^.

^{1 - 2ex}p( ^-^ )

^^^™

+ т ln А 1 = 0 ,

Ap ( т,^ 1 ,е 2) = 2 е 1 + 2 е 2 - т exp

^е 1 ^{+ е} 2 ^-

τ

,

Ad ( т,А 1) = А 1 +2 т exp

(' . „;

имеющего единственное решение. Наконец, отметим, что полученные в данном примере решения системы (11) удовлетворяют предельным соотношениям А 1 ^ 2 1i ф = ё ₂ ^ 2 Щ hi т ^ +0. Результаты численных расчетов приведены в таблице 2.

Основное различие результатов использования условий (6) - (9) и системы (11) состоит в том, что в последнем случае решение оказывается единственным V т >  0 благодаря свойствам функции (15), в которой слагаемые, зависящие от R ( т, s ), играют роль регуляризирующей компоненты.

Пример 3 (случай неограниченности целевой функции). Прямая задача: максимизировать в E ² фуикцию F = 2 е 1 при условиях е 1 > 0. е 2 >  011 е 1 - е 2 6 1-

Двойственная задача: минимизировать в E ¹ функцию G = А 1 при условиях А 1 > 0. А 1 > 2.

-А 1 > 0.                 '                           □

Первая из этих задач совместна, но значение ее целевой функции пеограпичепо в допустимой области. Двойственная задача, в этом примере несовместна.

Сначала, рассмотрим схему, основанную на использовании вспомогательных функций (5) и (8). В данном примере они будут иметь вид

а их условия стационарности (6) и (9) соответственно

2 - exp ( ^ ⁺ Т 2 - ¹ } = 0 ,

2 - exp ( ^ ⁺ Т ^{2 - 1} } = 0

Ap ( т, е 1 , е 2) = 2 е 1 - т exp (-— т 2—¹ ) , Ad ( т, А 1) = А 1 + т exp ( ² ^ ¹ ^ + т exp ^ ^ Т^

и 1 — 2 exp

(

2 -

1-W

λ ₁

)

= 0 .

Второе условие просто дает А 1 = 2 + т ln2, в то время как первая система, очевидно имеет пее

а их условия стационарности (6) и (9) соответственно

2 - exp ( ^ 1 - Т ^{2 - 1} } = 0 , exp ( ^ ^- Т ^{2 - 1} } = 0

и

1 — exp

(

a-W

- λ 1

τ

+ exp

( ~ \ λ_τ 1

= 0 .

Легко видеть, что обе приведенные задачи несовместные, при этом условия стационарности (6) и (9) вспомогательных функций

Второе условие имеет асимптотическое решение А 1 ^ 1 пр и т ^ +0, в то время как первая сис

тема. очевидно несовместна, что означает неприменимость схемы (5) - (8) для решения данной задачи.

Рассмотрим теперь систему уравнений (11), она. будет иметь вид _ _ _

1 — € 1 + € 2 + т ln А 1 = 0 , _ _

2 — А 1 — т ln € 1 = 0 , _ _

А 1 — т ln € 2 = 0 .

Ap ^{( т}. ^€ 1 ^,€ 2) = ^€ 1 ^{+ 3 €} 2 ^—

— т exp ( ^{€ 1 —} т 2 ^{— 3} ) — т exp ( ^{—€ 1} ^2 ⁺ 4 ) ,

Ad ^{( т}. ^А 1 . ^А 2) = ^{3 А} 1 ^{— 4 А} 2 ⁺

+ т exp ( ^{1 — А}т ^{+ А} 2 ) + т exp (³±A z^А^

очевидно противоречивые:

Она имеет решения € 1 = exp ( — у— ¹ I и € 2 = у

= exp I -т 1, где А 1 — корень уравнения

1 — exp ( ^{А —} ^ 2 - 3 } + exp ^ - f i+ f 2 +4 } = 0 ,

3 + exp ( ^{A 1} - Т 2 - ³ ) — exp ( - ^{А +}/ ^{2 +4} } = 0

^^^^а

^^^^а

exp

_ _

(² .^А '1...... (-т)

^^^™

+ т ln А 1 = 0 ,

3 — exp

1 — — 1 + — 2 τ

3 + а 1 —

^+exp 1      у

λ 2

)

имеющего единственное решение при любом т >  0.

В заключение отметим, что полученные в данном примере решения системы (11) удовлетворяют предельным соотношениям А 1 ^ 1 и € 1 — € 2 ^ 1 при т ^ +0. хотя продолы lim € 1 ¹¹ lim € 2 ^{IIC С}У^- τ→ +0     τ→ +0

ществуют. Результаты численных расчетов приведены в таблице 3.

Пример 4 (случай несовместности).

Прямая задача: максимизировать в E ² функцию F = € 1 + 3 € 2 ^ПР^П У^с-товиях € 1 > 0. € 2 >  0 и

— 4 + exp

1 — — 1 + — 2

— exp

*#

3 + — 1 — τ

*#

— 2

= 0 ,

) =0 .

€ 1 — € 2 6 3 ,

—€ 1 + € 2 6 — 4 .

Двойственная задача: минимизировать в E ² функцию G = 3 А 1 — 4 А 2 при ус.товиях А 1 > 0. А 2 > >  0 и

А 1 — А 2 > 1 ,

поэтому стандартный вариант метода, штрафных функций в данном примере не может быть использован.

Как альтернативу рассмотрим систему уравнений (11), она. будет иметь вид _ _ _

( 3 — € 1 + € 2 + т ln А 1 = 0 , I                                 ____ ____ ___

— 4 + € 1 — € 2 + т ln А 2 = 0 , _ _ _

| 1 — А 1 + А 2 — т ln € 1 = 0 , I                        ____ ____ ___

3 + А 1 — А 2 — т ln € 2 = 0 .

Заметим, что эта система имеет решения Vт ^ ^ +0, удовлетворяющие легко проверяемому следствию ln € 1 € 2 = 4ln А 1 А ₂. Однако, как и в примере 3. пределы lim € 1- lim € 2- lim А 111 lim А ₂ τ→ +0    τ→ +0    τ→ +0     τ→ +0

ne существуют. Результаты численных расчетов с допустимой погрешностью 10 ^{- 7} приведены в таблице 4.

—А 1 + А 2 > 3 .                 □

Таблица. 3

τ	0.6	0.5	0.4	0.3	0.2	0.1
_ ξ 1	5.7996196	7.8969374	12.683928	28.535267	148.91394	22026.966
_ € 2	4.8333558	6.9138386	11.695904	27.536873	147.91407	22025.966
_ А 1	0.9453246	0.9667625	0.9836955	0.9946578	0.9993263	0.9999977

Таблица. 4

τ	1.0	0.75	0.5	0.25	0.15
_ ξ 1	9.1243426	16.132626	56.328286	2982.7001	61743.938
_ € 2	5.9837900	12.839029	52.921156	2979.2170	61743.588
_ λ 1	1.1509095	1.4791425	2.2575066	6.9058856	27.536084
_ А2	2.3618554	2.5647752	3.2731050	7.9060316	28.536084
ξ 1 ξ 2 ( — 1А2Д	1 . 5 • 10 - 8	— 1 . 1 • 10 - 7	— 2 . 0 • 10 - 8	5 . 5 • 10 - 8	7 . 9 • 10 - 9

Приведенные примеры вполне наглядно демонстрируют практическую эффективность схемы, основанной на. решении системы (11) как альтернативы метода. (5) - (8). В заключение также отметим, что метод гладких штрафных функций является принципиально приближенным, что не является существенным недостатком, для значений вектора параметров и, значительно отличающихся от решения задачи верхнего уровня. Однако в ином случае следует предусмотреть использование процедур, позволяющих находить точные решения при ненулевых т (например, описанных в [9]), или же применить экстраполяционные процедуры типа. [10], основанные па. тейлоровской аппроксимации вида.

( х* « х ( т ) — т Д х, I Л * « Л( т ) — т ДЛ ,

где компоненты векторов Д х, ДЛ находятся из

системы линейных уравнений

' m P i =1

_∂ 2 _U ∂λ i ∂λ p

n

^^^^

Д Xi + Е j=1

_∂ 2 _U ∂ξ j ∂λ p

^^^^

^Д «3

m P i =1

∂ ² U ∂λ i ∂ξ q

n ₂

^{Д X +} P dl j U q. ^Д «

= — ди ∂τ ∂λp , p = [1,m ], ∂2U = дтд^ , q = [1 ,n] •

Результат использования экстраполирующей процедуры для примера 1 при т = 0 • 01, приведен в таблице 5.

Таблица. 5

Переменная	« 1	« 2	X 1	X 2
Приближ. значение	1.9916772	2.005591	1.3309903	0.3310599
Вектор { Д х , ДЛ }	— 0 • 8146454	0.554041	— 0 • 2375052	— 0 • 2236908
Уточнен, значение	1.9998237	2.0000506	1.3333654	0.3332968