Лагранжева форма условий оптимальности для выпукло-гладких экстремальных задач в R

В статье рассматриваются условия оптимальности для экстремальной задачи в Rn:

min жесскп

f (®),

где G = {х Е Rⁿ : p(x) 6 0, г = 1,т; hj (х) = 0, j = 1,1; х Е П} , П С R” - выпуклое замкнутое множество.

Задача 1 называется общей задачей математического программирования (ОМП). В учебно-научной литературе ([1-4] и др.) условия оптимальности в форме Лагранжа обычно рассматриваются:

• а)    для гладких задач ОМП, в которых функции f и pt, г = 1,т - дифференцируемые, а функции hj , j = 1,1 - непрерывно-дифференцируемые;

• б)    для выпуклых задач ОМП, в которых функция f выпукла и множество G выпуклое.

В настоящей работе рассматриваются необходимые условия оптимальности (НУО) для более широкого класса экстремальных задач, названного выпукло-гладкой задачей ОМП, для которой выпуклая и гладкая задачи ОМП являются частными случаями.

Определение 1. Функция f : М С Rⁿ ^ R¹ называется выпукло-гладкой (ВГ), если она представлена в виде: f(ж) = f_B(ж) + /_д(ж), ж Е М , где f_B(ж) - выпуклая недифференцируемая функция, /_д(ж) - гладкая (дифференцируемая) функция.

Так как функция f_B = 0 - выпуклая и f_д = 0 - гладкая, то если f - выпуклая или f - гладкая, то она выпукло-гладкая.

Определение 2. Вектор а = а + V/_д(ж) называется квазиградиентом выпукло-гладкой функции. если а Е df_B(ж), df_B(ж) - субдиффсрснтщал функции f_B(ж), а - его субградпепт. Vfn(ж) - градиент функции Д(ж).

Очевидно, что производная В Г функции f (ж), ж Е Rⁿ в точке жд по направлению у f ‘(жо у) = lim liEE+EEMEml существует.

’      о ж +0      “

Определение 3. Задача 1 называется выпукло-гладкой, если в ней хотя бы одна из функций f II рг, г = 1,m, hj , j = 1, Z — выпукло-гладкая. множество П С R” - либо выпукло, либо определяется системой ограничений, которые задаются выпукло-гладкими функциями.

Определение 4. Множество J (жд) называется множеством индексов активных ограничений задачи 1 в точке жд Е G, если J(жд) = {г Е [1,m] : ^_г(жд) = 0}. Ограничения ^г(жд), г Е J(жд) называются активными ограничениями в точке жд Е G, а ограничения ^г(жд), г Е J(жд) - неактивными.

Термин «выпукло-гладкая задача ОМП» был введен в [5], но определение 3 В Г задачи более общее, чем в [5], и поэтому приведем доказателвство НУО. В настоящей работе рассматривается вариант ВГ задачи, в которой функции hj (ж), j = 1,Z непрерывно дифференцируемы в окрестности некоторой точки жд Е G. При этих условиях все касательные конусы для множеств G будут выпуклыми.

Определение 5. Пусть G С Rⁿ — некоторое множество, и ж д Е G (замыкание множества G). Касательным (контингентным) конусом ко множеству G в точке жд Е G называется множество Т(жо,G) = {Аг : 3{ж&} С G, ж^ ^ жд, lim ^-^ 0 ц = г, А > 0}.

Если жд - изолированная тонка, то Т (жд) = 0 = 0„ Е R”. Оневидно. ||г|| = 1.

Определение 6. Пусть в некоторой точке ж д Е G существует ненулевой конус Т ( ж д , G ) , п для фупкщш f (ж) па. {ж^} С G определена пос.тедователыюсть {f (ж^)} , к ^ ж. Производной функции f(ж), ж Е G, по касательному направлению г Е Т(жо,G) назовем величину ff(жд,г) = lim ^(^^-д^ ⁰ ) , если предел в правой части равенства существует.

2.    Условия оптимальности для выпукло-гладких экстремальных задач

Сначала рассмотрим некоторые свойства конуса Т(жо,G) и производной ff(жд,г).

Лемма 1.

• 1)    Конус Т(жо,G) замкнут (из [4]).

• 2)    Если G = {ж Е Rⁿ : hj (ж) = 0,j = 1,Z}, функции hj , j = 1,Z - непрерывно дифференцируемы в некоторой окрестности точки жд Е G, Vhj(жд), j = 1, Z линейно независимы. то Т(жд, г) = {г Е Rⁿ : Vhf(жд)г = 0, j = 1, Z} (из [6]).

• 3)    Если G = {ж Е R” : рг (ж) 6 0, г = 1,m; hj (ж) = 0,j = 1, Z}, жд Е G; рг, г = 1,m - дифференцируемы в точке жд, hj - непрерывно дифференцируемы в окрестности точки жд, Vy_г(жо), г Е J(жд), Vhj(жд), j = 1, Z — линейно независимы, то Т(ж₀,G) = {г Е Rⁿ : V^f (ж_д)г 6 0, г Е J(жд); Vhf(ж_д)г = 0, j = 1, Z} (из [6]).

• 4)    ЕІустъ G = {ж Е R” : ^_г(ж) 6 0, г = 1,m}, функции рг, г = 1,m выпуклы на, Rⁿ, гn^G = 0, тогда Т(жо,G) = {г Е Rⁿ : а/г 6 0, г Е J(жд) Уа_г Е д^_г(жд), г Е J(жд)} (из [5]).

  Теорема 1 (из [4]). Пусть в задаче 1: min f (ж), ж G G С R” в точке ж* G G существует ненулевой касательный конус Т (ж*, G) и существует производная /Г(ж*,z) Vz G Т ^*,G). Тогда, если ж* - решение задачи (1), то

  
  

  ФГ (ж*,z) > 0 Vz G Т (ж*,G).                                (2)

  
  

  Если функция f дифференцируема в ж*, то условие (2) имеет вид V f (ж*)^гz > 0 Vz G Т (ж*,G).

  
  

  Если f вынукла на Rⁿ, то условие (2) имеет вид f^,(ж*,z) > 0 Vz G Т (ж*,£), где

  
  

  f ^,(ж*,z)

  
  

  = lim               . _п

  ам+о      “

  
  

  __                   т

  Лемма 2. Пусти Gt С R ⁿ, i = 1,т - непустые множества, и П G_t = G = 0 , в точке t=i т

  ж G G для всех множсссте су ищете у ют касательные конусы, тогда Т (ж,G) С П Т (ж,G _t ).

  t=i

  
  

  Доказательство. Очевидно, что G С G_t, г = 1,т и Т (ж,G) С Т(ж,G_t ), г = 1,т,

  
  

  т

  
  

  тогда и Т (ж, G) С П Т (ж, Gt). Для сопряженных конусов справедливо обратное включение: t=i

  
  

  / т         \ *

  ( ПТ (ж,GtГ)

  
  

  С Т (ж,G)*. □

  
  

  Лемма 3. Пусти множество G = G_i П G2 = 0 и замкнуто, intG_i = 0, intG₂ = 0, и intGi П G ₂ = 0*; жо G dG_i П G₂, где dG_i - граница множества G_i . Пусти конусы Т (жо, Gi) и Т (жо, G ₂ ) выпуклые. Тогда Т (жо, G) = Т (жо, Gi) П Т (жо, G ₂ ). Если .же емс’сто условия * - int G _i П G ₂ = 0, то существуют a_i G Т (жо,G _i )* и a₂ G Т (жо,G ₂ )*, не равные нулю такие, что a_i + а₂ = 0.

  
  

  Доказательство. Так как по лемме 2 Т (жо,G) С Т (жо,G _i )ПТ(жо,G ₂ ), рассмотрим z G Т (жо,Gi)ПТ(жо^). Вектор z G Т (жо,G2), тогда в достаточно малой окрестности точки ж _о : ж^ = ж _о + Ofc z + о(а^) G G ₂ ,   lim        = 0, и т.к. intG_i П G ₂ = 0, то

  Ыд. > °     ^

  жТ = жо + a^ z G intG_i іі ж^ G intG_i, Т.О. ж^ G G. Значит, a^z G Т (жо,G), z G Т (жо, G) и Т (жо,G_i)ПТ(жо,G₂) С Т (жо,G). Учитывая обратное включение (лемма 2), получим требуемый резулвтат.

  Если же предположить, что intGi П G₂ = 0, то и intТ(жо,G_i)ПriТ(жо,G₂) = 0, т.к. в противном случае intТ(жо,G1)П^riТ(жо,G2) = 0, intGiQG2 = 0 - имеем первое утверждение леммы.

  Известно, что если riMi Qri^2 = 0, где Mi, М2 - выпуклые конусы, то существуют ai G М* 11 ai G М* такие а что ai + а2 = 0 [7]. Лемма доказана. □

  Также легко доказывается следующая лемма:

  Лемма 4. Пусть G_i, G₂- замкнутые множества, множество G = G_if)G₂ и жо G dG_i [\d2, intG _i QintG ₂ = 0, конусы Т (жоG ₁ ), Т (жо,G ₂ ) выпуклые.

  Тогда Т (жо, G) = Т (жо,G ₁ ) ПТ(жо, G ₂ ). Если же GiGi HintG ₂ = 0, то найдутся такие a_i G Т (жо, G _i )* и a₂ G Т (жо, G ₂ )*, wmo a_i + a₂ = 0.

  Доказательство. Доказывается аналогично лемме 3. □

  Замечание 1. Очевидны обобщения (пусть ж о G G ):

  
  

  1) Если G

  
  

  ^П Gt ; intGt = 0, i i=i

  
  

  1, m _i ; intG_t

  
  

  =  0, i = m _i +1, m

  
  

  ( ті          т

  int П Gt П П Gt t=i /    \і=" і +i у

  ( ті            т

  П intGt П П Gt

  t=i             t="i+i

  
  

  =   0,

  
  

  то Т (жо,G)

  
  

  0, то (•уществуют

  
  

  a_t G Т (жо, Gi)*, i = 1,т такие, что ^"Л a_t

  
  

  = 0.

  
  

  т

  П Т (жо,G_t); а также.

  t=i

  
  

  не все равные нулю

  
  

• 2)    Если П2=і intGi = 0, то Т (xg,G) = Q Т (хg,Gi); если же П’=₁ гntGi = 0, то г=1

существуют не все равные нулю а_г Е Т (хд, G, )*, такие, что 522=1 а_г = 0. □

Функция Лагранжа выпукло-гладкой (ВГ) задачи ОМП имеет вид m            I

L(x, А, ц) = Ад/(х) + У^ Агфг(х) + У^ цhj(х), Аг > 0, г = 0, m, х Е П, г=1            j=i где П С R” - выпуклое замкнутое множество.

Определение 7. Пусть дана экстремальная задача (ЭЗ): найти min/(х),х Е G С R”, где G = П i=i Gi = 0; х* — решение задачи. Множество G называется регулярным в точке хд Е G, если Т (хд, G) = fl^i Т(хg,G_i). ЭЗ называется регулярной, если множество G в точке х* Е G регулярно.

Замечание 2. Если ЭЗ регулярна, то в функции Лагранжа множитель Ад можно взять равным 1(из [2]).

Обозначим:

• а)    V / (х) - градиент, если / - дифференцируемая функция на Е д/(х) - субгралнепт функции /, если / - выпуклая, а = а + V/^ (х) - квазиградиент ВГ функции /.

• б)    а_г = V^i (х), г Е [1,m], если ф_г - диффереппируемая функция. а_г - субгралнепт. аг Е дфг (х), если фг — выпуклая функция, а = аг + Vфi (х) - квазигралнепт В Г функции фг .

• в)    Vhj (х) - градиент непрерывно дифференцируемой функции hj (х), j = 1,1.

Также введем обозначения:

G_i = {х Е R” : ф_г (х) 6 0}, г = 1,m,

GH = {х Е R” : фг(х) 6 0, г = 1,m},

G_p = {х Е R” : hj (х) = 0, j = 1, I},

Т (x q ,G^ = {z Е R” : а^т z 6 0, аг Е дфг(хд)}, г Е J (хд),

Т (x _q ,G, J = {z Е R” : aTz 6 0, а_г Е дф_г(х_д), г Е J(хд)}, если zntG„ = 0,

Т (x q ,Gjj) * = {а Е R” : а = ^_г(—Аг)аг, Аг > 0, аг Е дфг(хд), г Е J(хд)} (из [б]).

Т(хд, П) = {z Е R” : a^тz > 0}, где ап Е Т(хд, П)*.___ ___

Т(xg,Gp)* = {а Е R” : а = £j₌i ц Vh₃ (хд)} (из [6]).

Лемма 5. Пусть ф(х) - ВГ функция, мноснсество G = {х Е R” : ф(х) 6 0} , zntG = 0, ф(хд) = 0.

Тогда Т(хд, G) = {z Е R” : a^тz 6 0} , а = Vф^(хд) + а, а Е дф_е(хд).

Доказательство. Пусть z Е Т(хд, G). Тогда х = хд + az + о(а) Е G, а > 0, а ^ 0.

0 >  РИ*) _:j 0 > li_m НйЪНйЛ = lim ^($o+az+o(g)) = ^m ЩжоҢаУЩо^+оЩ) = ^ы              ы >д ^а         ы >д        ^а           ы >д           ^а

= ф,(хg,z) = Vфд(xg)Tz + ф’(xg,z) > Vфд(xg)Tz + aтz = aTz Эа Е дфв(хд), т.к.

ф= (xg,z) > aTzBIз[2]).

Обозначим Т (x q ,G) = {z Е R” : a^тz 6 0}. Очевидно, Т(xg,G) - выпуклый конус. Так как zntG = 0, то п гntТ(xg,G) = 0. Пусть z Е гntТ(хд, G), тогда и х^ = (хд + az) Е G при достаточно малом a > 0. Взяв lim ^&-^о = z, получим, что z Е Т(хд, G) и intТ (x q ,G) С Т (x q ,G), где гntТ(xg,G) = ^z Е R” : а^Т z< 0} . Поэтому замыкание int:r(xg, G) = :Ё(хд, G) и Т(хд, G) = ^Г(хд, G) = {z Е R” : а^т z 6 0} , а Е Т(хд, G)*.

Следствие 1. Если в лемме 5 положить, что G = {х Е R” : ф(х) > 0} , то очевидно, что Т(х_д, G) = {z Е R” : а^тz > 0} .

Лемма 6. Пусть в задаче 1 П = Rⁿ, функции ф, p_i, г = 1,т - выпукло-гладкие, hj , j = 1,Z - непрерывно дифференцируемые, жо G G, G = 0.

Тогда либо Т(жо,G) = Т(жо,Gp)П(ПТ(жо,Gi)), г G J(жо), либо существуют i не все равные нулю Xi    >    0, г    G J(жо), pj, j =    1,Z такие, что а = E^iC + Ej=1pj Vhj (жо) = 0, г G J (жо), г де ец G Т (жо,Gi)*.

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

• 1)    Предположим, что Vhj(жо), j = 1,Z - линейно зависимы. Тогда существуют не все равные нулю pj , j = 1,Z, такие что а = Ej =1 pjVhj (жо) = 0. Взяв X_i = 0, г G J (жо), получим доказательство леммы для этого случая.

• 2)    Предположим, что intG_i = 0, г G J(жо), но P|гntG_i = 0, г G J(жо). Тогда по лемме i

4 существуют такие Х _і , г = 1,т, что Е_i X_iа_г = 0, г G J(ж_о). Взяв pj = 0, j = 1,Z, получим доказательство леммы для этого случая.

Предположим теперь, что Q intG_i = 0, г G J (жо) и Ej=i PjVhj (жо) = 0, где хотя i

бы для одного j pj = 0. Если замечанию к лемме 4 Т (жо, G) = доказательство леммы для этого

int (n_iG_i)nG_p = 0, г G J(жо), то по лемме 3 и

Т (жо,G_p) П0Т(жо,Gi))

г G J(жо), т.е. получили

случая.

• 4)    Пусть теперь int (Q_i Gi ) Q Gp = 0, но int (Q Gi ) = 0 и Ej=1 PjVhj (жо) = 0, г G J (жо), тогда по Лемме 3 и замечанию к Лемме 4 существуют Х і >  0, Еі Х і сц = 0 такие, что а = - Ei Х і Ci + Ej=i pjVh₃ (жо) = 0, г G J(жо).

Лемма, доказана. □

Рассмотрим условия оптимальности регулярной ВГ задачи математического программирования (МП), когда множество П = Rn.

Пусть ф (ж) = ф_в(ж) + ф_д(ж), ж G G С Rⁿ.

Задача: найти min (фв(ж) + фд(ж)), ж G G С Rn,                             (3)

где фв (ж) - выпуклая на Rn, фд(ж) - дифференцируемая на Rn.

Теорема 2. Пусть точка ж* G G - решение регулярной задачи МП, тогда 3 а такой, что а = а + Vфд(ж*) G Т (ж*, G)*, где Т (ж,G) и Т (ж*,G)* - касательный и сопряженный ему конусы, а G Эф_в (ж).

Доказательство. По теореме 1, если ж* G G - решение задачи, то ф^,(ж*,z) > 0 Vz G Т (ж*,G).

Т.к. ф‘(ж, z) = ctz, где а G дфв(ж) - некоторый субградпент. ф‘(ж, z) = Vфд(ж)Tz, то (а + Vфn(ж*)) z > 0 Vz GТ(ж*,М), а + VE(ж*) G Т(ж*,G)*.

Следствие 2. Пусть задача математического программирования (МП) регулярна, G = {ж G Rn : р(ж) 6 0, г = 1,т, hj(ж) = 0, j = 1, Z} . Тогда, если ж* - решение задачи 3, то сугцествуют такие p*, Х* > 0, что тI ао + Vфл(ж*) + ^ Х*сц + ^p*Vh,(ж*) = 0,(5)

i=ij=i где

х * = 0, г G J(жо), hj (ж*) = 0, j = 1,Z,

А* > 0, А_г^_г(ж*) = 0, г = 1,m.; hj (ж*) = 0, j = 1,Z.

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

Т (ж, G) = {2 Е Rⁿ : а_г2 6 0, г Е J (жо); Vhj(ж*)^Т2 = 0, j = 1, Z}

и Т(ж, G)* = (d Е Rⁿ : d = - £^₁ Аг аг + £j₌₁ Pj Vh₃ (ж), p Е R¹, г = 1, z} .

Теперь из включения 4 и 6 получаем утверждение 5. □

Следствие 3. Пусть задача безусловной минимизации (БМ) - выпукло-гладкая. Если точка ж* Е R” - ее решение, то существует а Е Э/_в (ж*) такой, что a + V/^(ж*) = 0. □

Утверждение следует из теоремы 2, т.к. в задаче безусловной минимизации (БМ) Т (ж*, R”)* =0.

Лемма 7 (из [5]). Пусть П С Rⁿ — выпуклое множество. Тогда П = П₁ Р|П₂, где П₁ = (П + (ТгпР)*); П₂ = А//П; гп£ (П + (ТгпР)*) = тгП + гг(ЫпР )*, где А//П - аффинная оболочка множества П, ТгпП и (ТгпП)* - линейное подпространство, параллельное П и сопряженное к нему (ортогоналі>ное дополнение) подпространство. □

Геометрический смысл множества П1 : П1 - это цилиндр, сечением которого является множество П, а образующими - подпространство (ТгпП)* .

Рассмотрим теперь свойства конуса Т(жо,G) для ВГ задачи ОМП (1).

Теорема 3. Пусть задача ОМП 1 - выпукло-гладкая, жо Е G, G = 0, hj, j = 1, Z - непрерывно дифференцируемые функции, множество П С R” - выпуклое и замкнутое. Тогда, либо Т(жо, G) = Т(жо, П) ПТ(жо,Gp) П ^ПТ(жо,Gг)^ , г Е J(жо), существуют не все равные нулю ап, Аг > 0, г Е J(жо), pj, j = 1,Z такие, а = ап - £г Агаг + £j=1 PjVhj(жо) = 0, г Е J(жо), аг Е Т(жо,Gг)*.

Доказательство. Если множество аффинное, то его всегда можно представить в Аж = Ь, ж Е R”, Ь Е R^s, А Е .У" (из [4]). т.с. П2 = А//П = {ж Е Rⁿ : Аж = Ь, Ь Е R^s}.

Тогда задачу 1 можно представить в виде: найти min/(ж), ж Е G С R”, где G = Gp П Gn,

либо

что

виде

Gp = П2 Р| Gp = {ж Е Rn : hj(ж) = 0, j = 1,Z; Аж = Ь} = {ж Е Rn : hj(ж) = 0, j = 1,Z + s}, gh = П п(р^, г Е J(жо).

Таким образом, в этом случае задача ОМП 1 сведена к задаче МП, рассматриваемой в лемме 6, в которой вместо множества G_p надо поставить G_p, а вместо множества Gг, г Е J(жо) - множества Пі и те же Gг, г Е J(жо), пересечение которых есть G_H.

Теперь, применяя к задаче ОМП 1 Лемму б, в регулярном случае получим

Т (жо,G)=Т(жо, Пі) рТ(жо, П2) р^рТ(жо,G_^)^ , г Е J(жо).

Так как Щ,П2 и П = Щ QЩ - выпуклые множества, гпіПі Р|ггП2 = 0, то ([5], стр. 105)

Т(жо, П) = Т(жо, Пі) рТ(жо, Щ)

и

Т(жо,G)=T(жо,П)рТ(жо,Gp)p ^рТ(жо,Gг)^ , г Е J(жо).

В нерегулярном случае, учитывая в лемме 6 п. 4 конус Т (жд, П), для которого существует ап € Т (жд, П)*, получим, что существуют не все равные нулю элементы сопряженных конусов, такие, что а = а_п — ^_г А«аг + ^j₌₁ PjVhj (жд) = 0, г € J (жд), а« € Т(жд,Сг)*. ⊔⊓

Замечание 3.

Если ограничение у«, г € J (жд) неактивно, то ^«(жд) < 0 и жд - внутренняя точка множества G« , г / J (жд). Следовательно, Т(жд,Gг) = R” и Т(жд^_г )* = 0, А_г = 0, г / J(жд). Тогда в теореме 2 вместо Д) «Агаг, г € J (жд), можно по ставить 522=1А«аг.

Теорема 4. Пусть е ВГ задаче ОМП функции hj (ж), j = 1,Z непрерывно дифференцируемы в окрестности точки ж* € G, множество П С R” - выпукло и замкнуто. Тогда, если ж* - решение задачи 1, то существуют не все равные нулю числа А* > 0, г = 0, т, числа р*, j = 1,1 и век торы аг € R”, г = 0,т такие, что

I

(ж — ж*) > 0 Уж € П С R”,           (9)

А*а + ^ А*ец + ^p*Vhj(ж*) «eJ (ж*)           j=i

А* > 0, А*^(ж*) = 0, г = 1,т.

Доказательство. По теореме 2 необходимое условие экстремума для задачи 1 имеет вид а = а + V/д(ж*) € Т(ж*,G).

Если задача регулярна, тогда, используя теорему 2, запишем при Ад = 1 а = Ада = ап — ^2=1 АДг + ^j=1 P*Vh(ж*), где А* = 0, г / J(ж*).

Если задача нерегулярна, то ап — ^2=1 А*а_г + ^j=i P’jVhj (ж*) = Ада = 0 при Ад = 0.

Представим ап = Ада + f^ + ^ p*vhj (ж*)                  (io)

г=1          j=1

для регулярного и нерегулярного случая.

Для выпуклого множества П : аТ(ж — ж*) > 0 Уж € П (из [4]).

Подставляя в неравенство значение ап, получим

) ^т

(ж — ж*) > 0 Уж € П.              (11)

Так как числа pj , j = 1,Z. не ограничены по знаку, то числа р* в (10) равны (— р*) в (И), но для упрощения записи их обозначения оставлены без изменения.

Теорема доказана. □

Замечание 4. Выпукло-гладкая задача ОМП является наиболее общей задачей, рассматриваемой в настоящей работе.

• а)    Если задача МП - выпукло-гладкая (П = Rⁿ), то условие (9) будет иметь вид

I

А*а + ^ А*а« + ^ p*Vhj(ж*) = 0,                     (12)

«eJ (ж*)           j=i

А* > 0, А*^г(ж*) = 0, г = 1,т.

• б)    Если задача (1) выпукло-гладкая (П = Rⁿ), ограничения у_г(ж) 6 0, г = 1,т отсутствуют, то условие (12) будет иметь вид

I

Ада + £p*Vh,(ж*) = 0, Ад > 0.                          (13)

j=i

Приведем примеры решения ВГ задач, используя НУО (13) и (12).

Задача 1. Найти тіп(|ж| + |у| — ж² — 2у²), если ж² + 2у² = 4.

Квазиградиент целевой функции:

3 a — 2ж

3 — 4у

,

где a € [—1,1] : a = 1, если ж > 0; a = —1, если ж < 0;

3 € [—1,1] : 3 = 1, если у > 0; 3 = —1, ^еслп У < 0.

Задачу будем считать регулярной, тогда условие (12):

( a — 2ж А ./2ж\ _м ( 3 — 4у ДЧ 4У )="' ж² + 2у2 = 4.

Из первого уравнения этой системы получим

2Ж+СК — Ж З/ЗД/ — Вт*  І7/І — I ^—  * ІТІ

-4г/+— = 2y И 2aу = 3ж;  'У' = 1 2^|

• а)    Пусть |a| = |3| = 1. Toгда |у| = |2, ж² = 3, у² = 3, A = 22-^ = 1 — 2Ж = 1 — Д/2 - 0, 694.

Имеем 4 стационарных точки:

⁽ ж А  ДД  д А  Ду С6  ⁽ ж А Д .   (ж А ДДА

1 у 3   ^   • д у ^ Ду 3   — .^ ■(, у _ ^■

В этих точках функция Лагранжа дважды дифференцируемая, и /* = —1, 552.

„ = / 2(A — 1)0

^ V 0    4(A — 1) 7

и при A < 1 матрица Ду — отрицательно определена. Значит, указанные 4 стационарных точки - это точки максимума.

• б)    Пусть теперь ж = 0 и |у|  = 42. Касательный конус в этих точках

Т (0, V2) = {2 € R² : 22 = 0} . Квазиградиент в этих точках:

a = ^

a

3 — 4у

.

Применим теперь достаточное условие острого минимума.

Теорема 5 (из [5]). Пусть / - функция, определенная на множестве G; существует ненулевой касательный конус в точке ж* € G и непрерывная по 2 € Т(ж*,G), ^2^ = 1 производная по касательному направлению /3(ж*, 2). Тогда ж* - точка острого (строгого) локального минимума функции /(ж) в том и только в том случае, если /3(ж*, 2) > 0. □

Производная по направлению /‘(ж, у, 2) = aT2, aT2 = a2i, |2i| = 1. Направлений два: 21 = —1, 21 = 1.

aT2 = a2i = 1 > 0, т.к. при 21 = —1 a = —1; nj)ii 21 = 1 a = 1.

Т.к. aT2 > 0, то по теореме 5 точки ж = 0, у = ±42 - точки локального острого минимума,

/* = У — 4 - —2, 586.

в)

Пусть теперь у = 0, |ж| = 2.

Касательный конус в этих точках Т(|ж| = 2; 0) = {2 € R2 : 21 = 0} .

Квазиградиент в этих точках а =

(

a — 2ж

^ И aT2 = 322, |22| = 1. aT2 = 322 = 1 > 0,

т.к. при 22 = —1, 3 = —1; пРи 22 = 1, 3 = 1; таким образом, точки

локального острого минимума. /* = 2 — 4 = —2.

0±2

ТОЧКИ

Задача 2. Найти тіп(ж² + 2у²), ее.ти |ж| + |у| — ж² — 2у² 6 —4.

Квазиградиент функции ограничения-неравенства а = ^ р

-

-

2ж

4у

, тот же. что II в

задаче 1 для целевой функции.

Задачу будем считать регулярной; ограничение-неравенство активно, тогда условие (12):

( 2ж         а — 2ж

( 4у )+А(р — 4у )=°

|ж| + |У|

-

ж2 — 2у2 +4 = 0.

Из этого уравнения, как и в задаче а) Пусть |а| = |Р| = 1, |у| = |f; ж2

1. следует, что ^-^ = 2р1 2ау = Рж; |у| = 12| | • |ж| . — |ж| — 3 = 0 ^ |ж| = 2, 208, |у| = 1,104.

В этих точках функция |ж| + |у|—ж² где а = ±1 л Р = ±1.

-

2у2 +4дифференцируемая, V у(ж,у) =

а — 2ж

Р — 4у

,

т‘‘ = ( ²⁽¹ - ^А) ^жу I о

4(1 - А)

А .       2ж

; А =-------= 1, 293 > 0.

2ж — а

|ж|

Так как U’ < 0 и А > 0, то точки ( | । I не могут быть точками максимума или минимума. В этих точках значение целевой функции / = 7, 31.

б) Пусть ж = 0. Тогна |у| — 2у² + 4 = 0 11 |у|  = 1,686, А= ^у—^  > 0. В этих

точках касательный конус Т = {z : aT z 6 0} , где а =

-

-

2ж

4у

у = 1, 686, Р = 1, а = ^

а

-

5 744 ^ , а € [—1,1] и aTz = аz1 — 5, 744z2 6 0.

) = 0 — 4у)'^Пу'^1Ь

Значит. Т = {z € R² : z1 — 5, 744z₂ 6 0; z1 + 5, 744z₂ >  0} - выпуклый конус.

V/=(4у)=G 744 >и=1.г1=(0:985 р-(

0,172

—0,985

,

где z1 и z2 - граничные лучи конуса (угла).

V/ = ( 4у ) ; /‘(0, У, z) = 6, 744zi = 6, 744 • 0, 985 ж 6, 64 > 0.

По теореме 5 ^ ±1 686 ^ ~ точки острого локального минимума.

/* = 2у2 = 5, 685

в) Пусть |у| = 0, тогда |ж| — ж² + 4 = 0 1і |ж| = 2, 562, А= 2^—_a = 1, 242 > 0.

а

Касательный конус Т = {z : az 6 0}, где a = I р

-

-

2ж

4у

A ( а — 4,124 А

7 = ( Р 7 п

aTz = —4,124zi + Рz₂ 6 0.

Для значений Р = ±1 Т = {z : —4,124z1 + z₂ 6 0; 4,124z1 + z₂ >  0} - выпуклый конус.

V/(ж, у) = ( 0Ж ) = ( 0,124 ) ; V/(ж, Ур = 2ж • Z1 = 5,124Z1;

l|z|| = 1, z1 = f 0, 235 ) , z2 = f 0 235   ) , V/(ж, y)Tz = 5,124 • 0, 235 = 1, 204 > 0.

0,972 у         \ —0,972

Таким образом.   0^ ^ ~ точкп острого локального минимума. /* = 2, 5622 ж 6, 56.

Заключение

Отметим основные результаты, полученные в статье:

• -    Предложено определение выпукло-гладких функций, которые представляют собой сумму выпуклой недифференцируемой функции и гладкой (дифференцируемой) функции.

• -    Предложено определение выпукло-гладких (ВГ) задач математического программирования, в которых функции f,ipi, г = 1,пг, hj , j = 1,Z - выпукло-гладкие. Выпуклые и гладкие задачи ОМП являются частными случаями предложенного класса ЭЗ.

• -    Используя свойства выпуклых касательных конусов и производных функций по касательному направлению, доказано необходимое условие оптимальности (9) для В Г задачи ОМП.