Параметрическая форма необходимых условий оптимальности для гладкой задачи математического программирования

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

«Московский физико-технический институт (государственный университет)», 2018

найти

f(ж * )=тіпf(ж), ж G G,                               (1)

где G = {ж G Rⁿ : р _г (ж) 6 0, г = 1,т; hj (ж) = 0, j = 1,Z}.

Предполагается, что решение задачи (1), точка ж* G G, существует, а функции f , рг, hj - достаточно гладкие: порядок их дифференцируемости будет указан ниже. Формулировки необходимых условий оптимальности задачи (1) зависят от формы представления ее функции Лагранжа [1].

Пусть функция Лагранжа задачи (1) имеет вид тI

Т(ж, А, ц) = Aof (ж) + ^2 Агрг(ж) + ^2 Шhj (ж),(2)

г=1j=1

где А_г >  0, г = 0, т.

Теорема 1 (из [1]). Пусть в задаче (1) функции f и р_г, г = 1,т дифференцируемы в точке ж * G G, функции hj, j = 1,1 непрерывно дифференцируемы в некоторой окрестности точки ж * . Если ж* —локальное решение задачи (1). то слрцсствуют числа ц*, j = 1,1 и А * > 0, г = 0, т, не равные нулю одновременно, такие, что

^Дж * ,А * ,ц * ) = 0,                                (3)

А О > 0; А * > 0, А * р г (ж * ) = 0, г = Т“т; hj (ж * ) = 0, j = М.

Точка (ж*,А*,ц*) называется стационарной точкой задачи (1). В регулярном случае, который будет рассматриваться далее, Ао = 1.

Система (3) представляет собой необходимое условие оптимальности для задачи (1). В этой системе п + т + 1 условий типа равенства и п + т + 1 + 1— независимых переменных, причем т условий равенств представляют собой так называемые условия донолняюгцей немсесткости (УДН). НУО (3) - классический результат в теории методов оптимизации, они имеют большое как теоретическое, так и практическое значения. Например, если задача (1) выпуклая, то решение системы (3) является ее решением; если же задача (1) невыпуклая, то после нахождения стационарной точки (ж*,А*,ц*) надо проверить, является ли она ее решением, для чего следует применить какое-нибудь достаточное условие оптимальности.

Известны различные методы решения системы (3) [2], [6]. Как отмечается в [2], прямое решение этой системы как гладкой задачи недостаточно эффективно, поэтому вводятся негладкие переформулировки системы (3), которые также не всегда эффективны. Сложность решения системы определяется в первую очередь наличием УДН. Поэтому, желательно так переформулировать систему (3), чтобы устранить из нее УДН для ограничений-неравенств. В теории и практике решения задач математического программирования (МП) известны способы преобразования ограничений вида рг(ж) 6 0 к виду ф(ж,у) = рг(ж) + у² = 0, г = 1,т, и тогда задача (1) превращается в задачу с ограничениями-равенствами, для которой система (3) уже не содержит УДН [2]. На практике этот прием используется не часто, т.к. увеличивается размерность задачи.

В настоящей работе предлагается метод преобразования системы (3) к виду, в котором отсутствуют УДН, основой чего являются НУО в методе гладких штрафных функций.

2.    Метод штрафных функций

Приведем краткие сведения о методе ШФ, необходимые для построения НУО задачи (1).

Если решать задачу (1) методом гладких штрафных функций, то условие стационарности в нем представляет собой систему только п уравнений, при этом решение ж*(т) этой системы будет приближением к ж*, зависящим от коэффициента штрафа т[3]. Точное решение задачи (1)

ж* = lim ж*(т), т = 0,(4)

т м+0

где

ж*(т) = arg min Ғ(ж,т),(5)

mI

Ғ(ж,т ) = f(ж) + ^ Рі(т,рфж)) + ^ Р2(т, hj (ж)), ж G Rⁿ.

i=i

Р1(т, рфж)), Р2(т, hj(ж)) - функции штрафа, т >  0 - коэффициенты штрафа, которые для функций Р1,Р2 можно брать различными: ті > 0, Т2 > 0. Для упрощения изложения примем: ті = Т2 = т. Конечно, равенства (4), (5) имеют место только при определенных условиях, накладываемых на функции f , р, h, Рі, Р2 [1], [3].

Известен недостаток метода ШФ, заключающийся в том, что при т ^ 0 функция Ғ (ж, т ) становится плохо обусловленной [1, 3], и известные методы решения задачи (5) становятся неустойчивыми, малоэффективными, т.е. время решения таких задач увеличивается по сравнению с хорошо обусловленными задачами.

Однако на основе метода гладких ШФ можно модифицировать необходимые условия оптимальности (3), которые можно также интерпретировать как модификацию условий оптимальности для задачи (5).

Функция штрафа Р2(т, hj (ж)) является внешней штрафной функцией, а функции Р1(т, рфж)) могут быть как внешними, так и внутренними ШФ.

Укажем требования, которым должны удовлетворять внешние и внутренние ШФ [4]. Для внешних ШФ:

Р (ж, тк ) = 0 ил и Р (ж, тк ) ^ 0 пр и ж G G и тк ^ 0;

Р (ж, тк ) > 0 пр и ж G G;

Р(ж,тк+і) > Р(ж,тк ) При ж G G;

Р (ж, тк ) ^ то пр и тк ^ 0, к ^ то, ж G G.

Для внутренних ШФ во множестве G отсутствуют ограничения равенства hj(ж) = 0,j = 1,Z и предполагается, что int G = 0

и

0 <  Р (ж, тк ) <  Р (ж, тк - 1) Уж G int G, к = 1, 2,... ;                       (7)

Р (ж, тк ) ^ 0, к ^ то Уж G int G;

Р(жк,тк) ^ то, к ^ то, р(жк, dG) ^ 0, где dG - гранича множества. G, а р(жк, dG) - расстс)яіше от жк до dG.

Приведем примеры штрафных функций для решения задачи (5).

Для    ограничений-равенств будем    применять степенную функцию:

Р (т,һ₃ (ж)) = Т (hj (ж))^, где 3 = 2,4,6,.... Эта функция является внешней ШФ. Наиболее часто применяется квадратичная ШФ, т.е. при 3 = 2.

Для ограничений-неравенств можно применять как внешние, так и внутренние ШФ.

Рассмотрим вначале внешние ШФ. Степенная ШФ вида ^{Р (т,}уг^(ж)) = ~ ^(max(0, уг^(ж))3, ³ = 2,3,4... широко применяется на практике. При 3 = 2 она непрерывно дифференцируема. Для повышения порядка ее дифференцируемости надо увеличивать степень 3, ^т-^е- 3 = 3, 4 и т.д.

^^(х)

Более удобны показательные ШФ: Р(т, уг(ж)) = то т при о > 1, в частности экспо-^г(х)

ненциальная ШФ: Р (т, уг(ж)) = те т - они бесконечно дифференцируемы по у».

В качестве внутренних можно применять традиционные ШФ вида

Р (т, уг(ж)) = —т ln(—уг(ж)) и Р(т ; уг(ж)) =

т у» (ж) ’

ж G int G.

Сформулируем теорему о сходимости метода ШФ для комбинированного случая, когда функции Р1 (т, уг(ж)) могут быть как внутренними, так и внешними ШФ [4].

Введем множество Mi = {ж G Rⁿ : уг_а (ж) 6 0, i_a G [1,m], 0 6 a 6 a 6 m}; к ограничениям в этом множестве применяется метод внутренних ШФ. Множество M2 = {ж G Rⁿ : ущ (ж) 6 0, i_a G [1,m], a <  a 6 m, h* (ж) = 0, j = 1,l}. К ограничениям во множестве M2 применяется метод внеш них ШФ. Очевидно, что Mi QM2 = G.

Пусть множество В_е (жо) = {ж G Rⁿ : ||ж — жо| < е}— окрестность точки жо.

Теорема 2 (из [4]). Пусть ж0 G G, Gi = {ж G G : f(ж) 6 f(ж0)} - компакт; функции f , уг, i = 1,m, hj, j = 1,l - непрерывно дифференцируемы; существует ж* - решение задачи (1); для некоторого е > 0 задана окрестность Ве(ж*) и выполнено условие Ве(ж*) QM2 Qint Mi = 0. Пусть таксисе выполнены условия (7) и (6) для множеств Mi и M2. Тогда существует последовательность жь  = arg min Ғ(ж,ть), k =  0,1,2,..., 0 <  ть+1  <  ть, такая, что при xER"

lim ть = 0, k ^ то, ж* = lim жь, k ^ то.

Теорема 2 является адаптацией к задаче 1, частным случаем более общей теоремы из [4]. Вместо условия, что Gi - компакт, можно взять условие, что множество G2 = {ж G Rⁿ,жо G G : Ғ (жо, ть) 6 Ғ(ж,ть )} - компакт.

Замечание

• 1)    Если для решения задачи (5) применяется только метод внешних ШФ, то в теореме 2 можно исключить условие В_е(ж*) Q M2 Q int Mi = 0, при этом множество Mi = Rⁿ.

• 2)    Как видно из определения Min M2, существует множество вариантов решения задачи (1) методами внутренних и внешних ШФ.

3.    О модификациях НУ О задачи (1)

Рассмотрим НУО для задачи (5), т.е. запишем уравнение V_x F (ж,т) = 0 в компонентном виде:

дҒ(ж,т ) = df (ж) + U ӘР і ( т, у») ^ дуг (ж) + ^U Ә^р2⁽т^, h* ) , Эһ*(ж) = 0 , = -—

(Ю)

dxt      dxt    4-ф   дуг      dxt ^   dh*      dxt     ,’

;=1*=i

Из теории методов ШФ [1], [4], [5] известно, что

ЭР1(ть ,уг)    v .--- г   ЭР2(ть ,hj)* .

lim ---я----- = Аг, i = 1,m; lim ---кт—— = ^j, j = 1,l, с ^^   дуг                  ь^^   dhj где АТ, д* — множители Лагранжа в системе условий (3). Исходя из (9), обозначим

ЭР1(ть, Уг) _ ь. • _ у—. дР2(ть, h*) _ ь. •_ эу;     = Аг;i =1,m; dh*     =д*; j=

Далее, используя (10), индексы к можно опустить.

Определение

^-преобразованием штрафных функций Р1(т, рі), г = 1,т; P2(T,hj ), j = 1,Z, называются Д-функции К1(т, АД г = 1,т; К ₂ (т, pj ), j = 1,1, такие, что

Рі(ж^ = К 1 ( т,Аі ) , г = 1,т; hj (ж) = Р^т, р ), j = 1,1,                 (11)

и равенства (11) равносильны равенствам (10).

По сравнению с (10) индексы к в (11) опущены.

Представление (11) возможно, если для ^дР д^^ ^{г )} , ^ӘР 2 д һ'^{к з} ) существуют обратные функции. Отметим, что для внутренних и внешних ШФ, указанных выше, обратные для их производных существуют.

Замечание

Д-преобразование ШФ названо по первой букве слова residual (в переводе с англ. «невязка, остаток, погрешность вычислений»). Именно такой смысл имеют функции К1(т, АД К₂(т,р ) в уравнениях (11).

Модификация НУО (8) состоит в следующем:

• 1)    Из т + I произвочных ^щ^Д¹), '-—щ—^ возьмем что»wc их число g 6 т + I и заменим их значения в (8) на множители А^ , pj в соответствии с (10).

• 2)    Систему уравнений (8) дополним g уравнениями из (11) соответствующими выбранным производным штрафных функций. В результате получим систему из n + g уравнений.

Максимальное число уравнений полученной системы, очевидно, равно n + т + I. Запишем эту систему:

Wx) . \'^т \.Э( хМ ,^  „.sMx) __п .з—з

8x t ■ .Л, 1 ^Аі Qx t   ' ^j=1 ^Рі 8x t = ⁰, ^t = 1, ^п,

___                   _             (12)

Рі(ж) = Кі(т, Аі ) , г = 1,т; hj (ж) = Р ₂ (т^), j = 1,1.

Напомним, что в системе (12) т >  0.

Система (12) отличается от (3) тем, что в ней вместо УДН для ограничений рі(ж) 6 0 и уравнений hj (ж) = 0 введены соответствующие уравнения со значениями невязок Д1(т,АД К ₂ (т,р ). Заметим, что множители Лагранжа, в (3)А_і > 0, г = 1,т, и в (10)

ДдД¹) > 0, г = 1, т. Таким свойством обладают все штрафные функции для ограничений-неравенств. Поэтому в системе (12) неравенства Аі >  0, г = 1,т, в отличие от системы (3), можно опустить.

_п< ӘРі(т,ірі ) ӘР 2 (т,һ., )

В силу произвольности выбора производных — д^ ' , — ди- ^{и их} последующего преобразования максимальное число построенных эквивалентных (8) систем равно (включая систему (8)) 2^т+/, поэтому укажем только некоторые частные варианты модификаций условий (8). Рассмотрим случай, когда, одновременно преобразуются одна, или две из двух групп ограничений рі(ж) 6 0, hj (ж) = 0. Таких вариантов (вк.ткшая систему (8)) будет 2² = 4. Приведем один пример, когда преобразуются ограничения рі (ж) 6 0, г = 1,т.

8J (ж)     ^ т А Әф і (ж)    ^/     дР 2 ( T,h j ) 8h j (ж)

= 0, t = 1, n,

8x _t ⁺ 2^і=1 ^Аі дж _t ⁺ T^j=1    gh j     8x _t

Рі(ж) = К1(т, Аі), г = 1,т.

Система (13) состоит из n + т уравнений.

Укажем еще один случай задачи, часто встречающейся на практике.

Пусть задача (1) представлена в виде найти

min /(x), x Е Rⁿ,

^(x) 6 0, i = 1, m; hj (x) = 0, j = 1, 1, x_t >  0, 0 6 t 6 8 6 n.

Если 8 = 0, ограничения x_t >  0 отсутствуют.

Тогда функция F(x,T ) из (5) и уравнение (8) имеют вид

т

I

s

s

^{F (x}, ^T ) = /^{(ж) +} ^ ^Р1^(т, ^i^{(x)) +} 52 ^Р2^(т, ^hj ^{(x)) +} 52 ^{Р г (т}, ^{- x}t) = ^A(x, ^T ) ¹ 52 ^Р3^(т, ^{- x}t),

i=1

j=1

t=1

t=1

где Рз(т, -x_t ) - внутренняя или внешняя dF(ж,т ) _ дА(х,т )

dxt

dxt

-

ШФ для ограничений -x_t 6 0, t = 1,8.

^{У 8}-^£2(T^-^{x £ L} =0,t = 1,7.

t=1      ^{dx t}

dF (ж,т )    дА(х,т )

dxt

dxt

= 0, t = 8 + 1, П.

Если для системы (16) применять Д-преобразование, то максимальное число ее модификаций равно 2m+/+s.

Обозначим ^dp ( ^-p¹) == v_t, t = 1,8. Если применять Д-преобразование к трем группам штра<|>иых <|>упкппй ^{dP 1} dj'^r,^{V l )} , ^ӘР 2 д)Г^{,Һ з} ) , ^др(^Г—у⁾ , ^т° ^па^У⁴¹⁰¹ 2³ = 8 молдкрикаций си-

стемы (14). Например, если применять Д-преобразование к Й/УУ-йй и систему:

dP 2 (r,h j )

ә^ з

, то получим

m

£⁺ У Х

9^і ^{( т,р} ) , v^ dxt     ^^Гз

,=1

дһі(т,х)    дРз(т, -xt )

dxt

dxt

, ^t =¹,⁸,

m

£⁺ й ^Х

3^і ( т, xt)

dxt

I

+ У г, j=1

dhi(T,xt)   n ,   ——:—

--------- = 0, t = 8 + 1, П, dxt

и имеет другую схему для построения системы уравнений, решающей задачу (18). Метод

построения указанной системы назван в [5] «методом обратных связей».

Приведем конкретный вид R(t, а), где а = А«, г = 1,т, или а = p,j , j указанных выше штрафнвіх функций.

1) Для ограничения ф(ж) 6 0 внешняя показательная ШФ Р(т, ж) = а > 1, т >  0, А - соответствующий ограничению множитель Лагранжа. Тогда

= 1,1, Для

фи та т , где

ЭР(т, ж) дф

= ln а • а т , R(t, А) = -— • ln (-— ) . In а у ln а )

Если а = е, т.е. Р (т, ж) =

ЭР (т,х)

те т , то —дф - = е т и R(t, А) = т ln А.

Пусть Р (т, ж)   = Т (ф+(ж))^Т, 3   =   2,3,4,... - степенная ШФ.

^ЭРЭ^Тф^{Ж )} = Т ^(ф+^(ж))Т-1, где ^ф₊^(ж) = ^{тах(0,ф(ж))}, ^ф+^(ж) = ( ^т ^ ) ^5-1 и ^ф+^(ж)Т-1 А > 0. При 3 = 2 ф+(Е) = Ту. Тогда об ратная к ^^у^) будет функция

Для нее = Т при

R ( t, А) = <

с 6 0, А = 0,

(ту)5-1, х> о.

Так как по определению А > 0, то будем считать R(t, А) = (^^ ⁵ 1 , А > 0. Отличие ШФ

Р (т,ф) = Та Т_и Р (т,ф) = 1 (ф+(ж))^Т заключается в том, что в ф(ж) 6 0, а во второй Р(т, ф) = 0 при ф(ж) 6 0. Это необходимо систем (12), (22).

первой Р (т, ф) учитывать при

> 0 при решении

Рассмотрим внутренние ШФ.

Пусть Р(т, ж) = -т ln(—ф(ж)). Тог да ^Уфф^ =

— Дм ¹¹ R(t, А) = — ф(ж)         I , '

А, А > 0.

Если Р(т, ж) = — Д , то ^{эр ( т} ’ ^{х )} = Ду, R(t, А) = — Ду, А > 0. v ,            ф(ж) ,           дф         ф(ж)² , х , у V А ,

2) Для ограничения һ(ж) = 0 Р(т, ж) = ТҺ^Т(ж), 3 = 2,4,6,... ^дРдһ^{Һ )} =

R(t,^) = (^Т_Тт) ^5-1 , ^{а к0Г}Д^а 3 = 2, R(t,^) = Д.

В работе [5] рассматривались функции R(t, А), которые обозначались Q ( t, А) поненциальной, логарифмической, обратной, а также и для других ШФ.

^Т Һ ^{Т 1} в т

для экс-

Рассмотрим теперь другой вариант НУО для задачи (1), в котором присутствуют только функции-невязки R(t, А») = Ri(t, А»), г = 1,т, функции R ₂ (t, ^j ), j = 1,1, отсутствуют.

Представим ее в виде:

найти min/(ж),ж G М, —(ж) 6 0, г = 1,т,                        (19)

где М = {ж G Rⁿ : hj (ж) = 0, j = 1, Z}.

Представим вспомогательную функцию F(ж,т) = /(ж) + Д)Д1 Р(т, ^«(ж)), ж G М, и метод ШФ для задачи (19): найти minF(ж,т), ж G М.                                 (20)

Выпишем для задачи (20) НУО в форме Лагранжа:

^д/(ж) , ^^ ^дР(т, У») ^-Mt) , \д ^dhj^(ж)

джт + Л/ ^-^ • ^жт+|> ^жт = м = 1,",       (21)

hj (ж) = 0, j = 1,Z.

Если теперь провести Д-преобразование для ^д^-Д) , г = 1,т, ^{то из} системы (21) получим равносильную ей систему:

8Цх, Л, Л  8/(х)  А »«(і) А dhj (х)       .— д-   = -5.7 Ж'..-- + А-      = °-t = Ж

і=1              ,=1

Ых) = Р ( т,Лі ) , г = 1,т, hj (х) = 0,j = 1,Z.

Система (22) отличается от системы (12) тем, что в (22) отсутствуют невязки Н(т,рі^. Первые п уравнений в (22) представляют собой производную фупкщш Лагранжа Б(х,Л, р) по х_-, t = 1,п. Если применить НУО (21)для задачи (14), то возможное равносильное (21) условие будет иметь вид, отличный от (17):

д/(х)  А А др,(т,х)  A dhj(т,х) = ЭР(т, -х-)= — дх-   ^ ' др,    j^^ dhj        дх-,

УР1 + урх, д    + у ^PAd^t = г+гж(23)

дх-              дх-      2~^\ дһ,

і=1,

^і(х) = Р(т, Лі ) , г = 1,т, hj (х) = 0,j = 1,1.

Замечание

• 1)    Отметим, что теорема 2 также справедлива и для задачи (20). В этом случае в условие теоремы 2 вместо компакта G1 надо поставить компакт G3 = G1 Q М.

• 2)    Система (22) является результатом Д-преобразования всех т производных ^ХХ) , г = 1,т. В общем случае из споте мы (21) можно получить 2^т систем уравнений, равносильных системе (21).

Рассмотрим теперь некоторые свойства систем (12) и (22). Матрица Якоби для системы (12) по переменным х,Л,р имеет вид

J(х, Л, р) =

^Ад)

дж дж дһ дж

()т   (|һ)T дж        дж / дИ(т,Х)

дХ       ⁰

дЯ(т,л)

⁰        дц

где (тхп) мат}оппа. ^Ж _zz (Іхп) матіоппа. ду - матрицы Якоби систем функций рі, г = 1, т. іі hj, j = 1,1;Р_жж (х,Л,р) — п х п матрица вторых производных функции Лагранжа задачи (1); дНХтХ                                                                             дИ(тХг ) • I

—дХ — (т х т) диагональная матрица с ди агональными элементами — дХ- , г = 1,т; ^{дК ( Т}^ ⁾ — ( х I) диагональная матрнпа. е янагоналыіымп элементами -~Xi^ ^ ⁾ , j = 1,Z.

Матрица J (х,Л, р) для системы (22) отличается только тем, что в ней матрица ^д к ^(т ,в ⁾ = о дц        .

Отметим, что в системах (12) и (22) матрицы РЖ_ж(х, Л, р) не зависят от коэффициента штрафа т, в то время как матрицы Ғ_жж(х,т ) для задач (5) и (20) зависят, причем для этих задач число обусловленности 7 матрицы Ғ’Ж_ж(х,т ) 7 ж ^ при т ж 0 [1, 4], в результате чего методы ШФ решения задачи (1) становятся неустойчивыми. Вопрос обусловленности матрицы J(х,Л,р) для систем (12) и (22) в зависимости от т определяется видом ШФ и требует дополнительного исследования. В частности, если элементы диагональной матри- дН(т,Х)    дй(т,р)

Ч^ы — дХ ^и —дц окажутся ограниченными при т ж 0, то можно ожидать, что число обусловленности 7 матрицы J(х, Л, р) будет ограниченным, и методы решения систем (12) и (22) будут устойчивыми.

Отметим также, что от числа т в (22) зависят невязки R(t, АД т.е. рфж(т)) = R(t, Аг(т )), г = 1,ттг, причем решение задачи (1) является предельным значением для ж(т) и А(т) при т ^ 0, т.е. ж* = ж(0), А* = А(0) и будет иметь место УДН: АД0)рг(ж*) = 0, Аг(0) > 0, г = 1,т.

4.    Схемы решений задачи (1)

Рассмотренные выше модификации НУ оптимальности могут быть использованы для построения различных схем решения задачи (1) . Так как модификаций НУ оптимальности много, то ограничимся рассмотрением только комбинаций систем (8) (метод ШФ) и (22).

Напомним некоторые свойства метода ШФ и систем нелинейных уравнений (СНУ) (22).

Метод ШФ обладает хорошей сходимостью на начальных итерациях и его сходимость ухудшается при уменьшении коэффициента штрафа тиа конечных итерациях [4], [7].

Для методов решения СНУ необходимо хорошее начальное приближение к решению, т.е. знание такой начальной точки, из которой метод будет сходиться [2]. Кроме того, как показывает практика, увеличение коэффициента штрафа т(КШ) расширяет окрестность точки ж*, из которой сходимость методов решения СНУ имеет место.

Используя указанные свойства, можно предложить схему решения задачи (1) как комбинацию методов ШФ и методов решения СНУ.

Схема 1. Для решения задачи (1) построим вспомогательную функцию F(ж,т) (5) и решим некоторым методом последовательность а задач БМ: min F (ж,т), ж G Rⁿ при т1 > т₂ > ... >  т_а. Считая, что точка ж(т_а) - решение за дачи БМ при т = т_а находится в области сходимости методов решения системы (22), решаем СНУ (22) для последовательности коэффициентов штрафа т_а+1 >  т_а+2 > ... >  т_еп<1 , где т_еп<1 ~ значение КШ, при котором полагаем, что решение СНУ обладает достаточной точностью.

Схема 2. В этой схеме используются только методы решения СНУ (22). Считая, что при достаточно большом КШ ті начальная точка жо находится в области сходимости методов решения СНУ, решаем последовательность СНУ (22) при ті > Т2 > ... >  т_еп(}.

Указанные схемы решения задачи (1) являются примерами из многих возможных схем, построенных на основе модификаций НУО, рассмотренных выше.

Рассмотрим некоторые возможности уточнения приближенного к ж* решения задачи (1).

Решение ж* удовлетворяет условиям (3) и определяется ограничениями hj (ж) = 0, j = 1,Z, и некоторым набором J(ж*) = {г G [1,т] : рфж*) = 0} активных ограничений рфж*) = 0, г G [1,т]. Если бы набор активных ограничений был известен, то точку ж* можно было бы найти, решив только одну систему уравнений. И главная проблема в общем случае состоит в том, что набор активных ограничений р^(ж*) = 0, г G [1,m] неизвестен. Метод уточнения приближения к ж* состоит в следующем.

• 1)    Используя вышеизложенную схему 1 или схему 2, находим приближенные к ж*, А* 'значения ж, А.

• 2)    Рассматривая малые (на наш взгляд) значения А^ > 0, полагаем, что ограничение рфж) не будет активным. Удал ив из списка ограничений рфж) 6 0, г = 1,ттг, неактивные ограничения, для которых считаем А* = 0, построим новую задачу (1), в которой будут только активные ограничения (по нашей гипотезе), и решим снова задачу по схеме 2, где начальной точкой будут ж и А^, а А^ по гипотезе соответствуют активным ограничениям.

Если новое найденное приближение к решению мало отличается от ж и А, то можно считать, что ж и А - хорошее приближение к ж* и А*. Если указанное отклонение не мало, то необходимо рассматривать другой набор активных ограничений.

Заключение

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

• -    Для задачи МП рассмотрены два варианта метода штрафных функций (5) и (20).

• -    Используя Д-преобразование (11), на основе НУО для метода ШФ (8) и (21) построены варианты параметрических условий оптимальности для задачи (1). Показано, что для (1) имеет место многовариантность равносильных параметрических НУО.

• -    Показано, что матрица Якоби (24) слабо зависит от коэффициента штрафа т, т.е. если число обусловленности для многих модификаций НУО окажется ограниченным, то численные методы решения систем (12), (22) будут более устойчивыми, чем в методах ШФ.

• -    Предложены схемы решения задачи (1), представляющие собой комбинации метода ШФ и методов решения СНУ.