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

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость новой

Детальная информация о работе

Выдержка из работы

Математическая теория управления и оптимизации
УДК 519. 3:62−50 Э.Я. Рапопорт
0 ЧЕБЫШЕВСКИХ СВОЙСТВАХ РЕШЕНИЙ ЗАДАЧ ПОЛУБЕСКОНЕЧНОЙ ОПТИМИЗАЦИИ1
Приводятся формулировки и доказательства теорем, устанавливающих альтернансные свойства решений задач математического программирования с континуумом ограничений в условиях, ослабленных по сравнению с традиционными. Рассматривается вычислительный алгоритм, базирующийся на этих свойствах.
Достаточно широкий круг параметрических экстремальных задач формулируется в терминах функций максимума, что приводит к специальным задачам математического программирования с континуумом ограничений [1,2], получившим название задач полубесконечной оптимизации или полубесконечного программирования (ЗПО) [3,4].
Известные необходимые условия экстремума для ЗПО формулируются в виде обобщенного правила Лагранжа для таких точек максимума соответствующих функций на заданных множествах, в которых значения данных функций оказываются равными по определению величине критерия оптимальности и заданному пределу для функциональных ограничений [1,2,5].
В соответствии с теоремой Каратеодори о выпуклой оболочке подмножества в векторном пространстве здесь сразу устанавливается верхняя граница для минимального числа этих точек, а достижение в определенных условиях равенства данного числа его верхнему граничному значению, при котором отмеченное число становится равным числу всех искомых неизвестных, является центральным свойством решений ЗПО, называемым далее альтернансным по аналогии с подобными определениями в теории чебышевских приближений [6−11].
Еще П. Л. Чебышев [12] и С. Н. Бернштейн [13] указывали, что альтернансные свойства решений в задачах равномерного приближения функций приводят к замкнутым системам соответствующих соотношений в точках максимума погрешностей приближения, редуцируемым, в свою очередь, к разрешаемым относительно всех искомых величин системам уравнений.
На альтернансных свойствах экстремальных элементов базируется целый ряд алгоритмов, с успехом используемых для решения рассматриваемого круга задач [2,14−17].
Однако известные условия, при которых решения ЗПО обладают альтернансными свойствами часто оказываются (за исключением простейших одномерных модификаций в линейной постановке) достаточно сложными и стеснительными, а их предварительная проверка затруднительной. В значительной степени это связано с типичными формулировками данных свойств в форме так называемого & quot-обобщенного альтернанса& quot- [18−21], обладающей избыточными признаками по отношению к определяющему соотношению для числа точек максимума, использованием которого во многих случаях исчерпывается & quot-практическая полезность& quot- соответствующих теорем.
Отмеченные особенности в первую очередь относится к многомерным постановкакм ЗПО, для которых функции максимума определяются на множествах с размерностью, большей единицы.
В соответствии со сказанным возникает проблема ослабления предварительных допущений, гарантирующих выполнение альтернансных свойств оптимальных решений ЗПО, понимаемых в указанном выше более узком смысле по сравнению с понятием обобщенного альтер-нанса.
В настоящей работе сформулированы теоремы об альтернансных свойствах, в определенной степени решающие отмеченную проблему в рамках рассматриваемых математических мо-
1 Работа поддержана грантом Минобразования Р Ф по фундаментальным исследованиям в области автоматики и телемеханики (проект 97−6-1. 1−62).
делей. Приводятся полные доказательства этих теорем по схеме, указанной в работах [17,22]. Обсуждается вычислительный алгоритм решения ЗПО, базирующийся на полученных результатах.
1. Задача полубесконечного программирования с гладкой целевой функцией
Рассмотрим задачу математического программирования [1]
I (А) ® тіп, А є Оп (1)
с бесконечным числом ограничений
^ А)-в 0 & lt- 0, х є^ т, т & gt- 1, 8 0 & gt-8 тп) п & gt- 0, эквивалентных условию
Ф (А) = тах{^ (х, А): х єП т, т & gt- 1} & lt- ?0, ?0 & gt- є & gt- 0, ^
етп = щЦф (А): Ає Оп }.
n
n
Здесь Gn — замкнутое множество в En, обладающее в каждой точке Ае Gn некоторым непустым выпуклым конусом- Wm — связное компактное множество в Em, m & gt- 1- I (А) — непрерывно
дифференцируемая функция п- мерного аргумента, А = (Аt), i = 1, n, n & gt- 1- F (x, А) — заданная
функция, непрерывная вместе со своими частными производными по совокупности аргументов на Wm x Gn, и е0 — заданное число.
Замечание 1. В характерном частном случае Ф (А) = max{| F (x, А|: x eW m }, где сохраняются прежние свойства W m и F (х, А), задача сводится к виду (1), (2) с помощью преобразования [1] max{ f (t, А: t е Pk с Ek } = max{f (j, А): фе Pk+l с Ek+1}, f (ф, А) = X f (t, А) — j = (X, t) — ?е[-Ц]- Pk+1 = Pk x [-1,1] для заданной функции f (t, А), А e Gn ?.
Поскольку существует минимизирующая последовательность, на которой достигается нижняя грань функции Ф (А), равная eт^П, то множетво Лебега N (е0) = {Ае Gn: Ф (А) & lt-е0}
(n)
оказывается непустым для всех е 0 & gt- е m/n.
Будем всюду далее считать выполненным достаточное в такой ситуации условие [23]
lim I (А) = да (3)
||а|®?
существования решения задачи (1), (2) для всех е0 & gt- е|"П, где 11 • || - евклидова норма в En.
Пусть для всех e0 & gt- e (mni)n, при которых существует решение А0 задачи (1), (2), выполняются следующие допущения, характеризующие искомую точку А0:
a) А0 е int Gn- (4)
b) grad I (А0) * 0- (5)
c) для всех е 0 & gt-е min найдется такой вектор S, ||S|| = 1, принадлежащий конусу K (А0) возможных направлений [1, 2] множества Gn в точке А0, что производная функции максимума Ф (А) в этой точке по направлению S отрицательна:
& lt-0- SеK (А0), ||S|| = 1- (6)
OS
1Ч, OF (х, А0) — ^
d) функции-----------, i = 1, n, линейно независимы на W m-

e) всякому фиксированному Ае Gn сопоставим множество Wm (А) = {х еПm: F (х, А) = = Ф (А) = е} всех точек х на Wm, в которых F (х, А) достигает своего максимального значения, равного е.
Тогда будем считать, что число Ях таких различающихся точек для е = е 0 и, А = А0 ограничивается при выполнении (5) неравенством
Ях & gt- 2. (7)
Покажем, что в рассматриваемых условиях решения задачи (1), (2) обладают альтернанс-ными свойствами, формулируемыми в виде следующей теоремы.
Т е о р е м, а 1. Пусть А° = (А1]),, = 1, п — решение задачи (1), (2) и выполняются условия
а) — е). Тогда существует Ях различающихся точек х° е W^ (А0), j = 1, Ях, где
— (n).
Ях = п если в о & gt-в тП- (8)
Ях = п +1, если во =в& lt-?. (9)
Доказательство теоремы 1
1°. Рассмотрим сначала задачу (1), (2) при в о & gt-в тп. В силу (7) достаточно рассмотреть при
этом случай п & gt- 3. Нетрудно видеть, что линейная система уравнений
51 (А°). «5Е (х0,А0)
-1--И, = а- & gt- ---------- '-
,¦=1 5А, г? 5А ,
должна быть неразрешима относительно h = (hi), i = 1, n, для всех a & lt- 0, bj & lt- 0, j = 1, Ях. Действительно, в противном случае существуют возможные (с учетом включения (4)) направления h е En, ||h|| = 1, производные по которым SI (А)/ Oh и 5Ф (А)/ Oh целевой функции I (А) и
функции максимума Ф (А), определяемые выражениями [2]
ОД ОД 0Ф (А) = max ?0^(х!Д) (11)
Sh is SA г Sh хеой- (А) f~t SA г г
отрицательны при, А = А0, что противоречит необходимому условию локального минимума SI (А0)/Sh & gt- 0 по всем допустимым h е K (А0), ||h|| = 1 [2].
Вопреки утверждению (8) предположим теперь, что Ях = Я * & lt- n, где Я * & gt- 1 в соответствии с (7). Тогда для того, чтобы система (10) не имела решений при отрицательных, а и bj, в
соответствии с теоремой Кронекера-Капелли [24] необходимо, чтобы при Я * & lt- n ранг r * ее
* * матрицы был меньше максимально возможного rmax, который в условиях Я & lt- n равен
rmax = я *+1 & lt- n. Но в таком случае существуют [24] нетривиальные решения h = (ht) однородной системы (10) при a = b1 = b2 = … = bR, = 0:
SI (А0) ~ = 0, I OF (х°, а0) —
i=1 SAг — 1 SA i
= 0- Z-j-h = 0, j = 1, Я (12)
откуда, в силу определений (11), следует существование допустимых направлений И, для которых
h
= 1,
SI (А0) ей
00
SI (А0) SA
0 5Ф (А0)
= 0- -----~- = max
SF (х j, А0)
Л
SA
= 0, (13)
5И х
4 '- ч /
где внешние круглые скобки в правых частях равенств (13) означают скалярное произведе-
77 П
ние в Е.
Последующий этап доказательства проводится по следующей схеме. При сделанном выше предположении Ях = Я * & lt- п в условиях а) — е) теоремы 1 можно сформулировать такую деформированную задачу вида (1), (2) с заменой Е (х, А) на некоторую варьированную функцию
ЕДх, А), тождественно совпадающую с Е (х, А) на От эх при, А = А°, что, во-первых, А° является одновременно решением как исходной, так и деформированной задачи в некоторой окрестности А° и, во-вторых, ранг г * матрицы вида (10) после замены Е на Е равен максимальному г^ах = Я * +1? п. С другой стороны, последнее равенство оказывается невозможным в условиях существования нетривиального решения однородной системы уравнений (12) для возмущенной задачи в силу необходимого условия экстремума при Ях = Я * & lt- п как для исходной, так и деформируемой задачи, если Е1(х, А°) °Е (х, А°), хеОт. Получаемое противоречие и
г& gt-*
свидетельствует о невозможности неравенства Я & lt- п.
В целях формирования функции Р (х, А), обладающей указанными свойствами, используется разложение Р (х, А) в бесконечный ряд.
Приступим к реализации изложенной схемы доказательства.
Постулируемые свойства функции Р (х, А) е Ь2р [О т ] позволяют выполнить ее разложение в равномерно сходящийся на О т ряд Фурье по некоторой полной ортонормированной с весом р (х) системе функций к (х)}е ?2& gt-р [О т ] [25]:
?
Р (х, а) = X гк (А)^к (х) — гк (А) = | Р (х, А) р (х)^к (х)ф. (14)
к=1 О
т
Равномерная сходимость ряда в (14) гарантирует правомерность всех используемых ниже операций с этим рядом.
Используя изоморфизм пространств Ь2р [От ] и 12 э X (А) = (гк (А)} функций с интегрируемым на От квадратом и бесконечных числовых последовательностей с ограниченной суммой квадратов их членов [25], рассмотрим далее в Оп непустые множества
М (10) = (А е ап: I (А) -10 = 0- 10 = I (А0)}- N (е0) = (А е ап: Ф (А) & lt- е0}, содержащие точку А0 е М (10) IN (е 0), являющуюся граничной точкой множества N (е 0), и их отображения согласно (14) в 12 — соответственно М*(10) и N*(е0), содержащие точку
X (А0) = (1к (А0)}е М * (10) IN * (е 0), которая является граничной точкой множества N * (е 0). Установим вначале справедливость следующих утверждений.
У т в е р ж д е н и е 1. Каждый вектор И в (12), (13) является касательным одновременно к М (10) и N (е0) в точке А0, причем производные д1 (А0)/ дИ и дФ (А0)/ дИ по направлениям каждого касательного вектора к этим множествам равны нулю.
* * * п дгк (А0) ~
У т в е р ж д е н и е 2. Отображение И = (Ик), Ик = X---------------Иг, к = 1,2,… каждого век-
г=1 дАг
тора И в пространстве 12 является касательным вектором одновременно к
М*(10) и N*(е0) в точке X (А0), и при этом производные отображений I (А) и Ф (А) по
направлениям И* в точке X (А0) равны нулю.
Доказательство утверждения 1. Утверждение 1 относительно множества М (10) для непрерывно дифференцируемой функции I (А) непосредственно следует в условиях (5), (12) из теоремы Люстерника о касательных пространствах [26,27] и остается доказать это утверждение относительно N (е 0).
Поскольку [2]
Ф (А0 + а~) = Ф (А0) + адФ (А) + о (а) — Нш = 0, (15)
дИ а®+0 а
то при дФ (А0)/дИ = 0 согласно (13) и Ф (А0) = Р (х0,А0) = е0 по определению точек
о * *
,] = 1, Я, Я & gt-1 получим из (15)
Ф (А° + а/~) = ео + о (а). (16)
— /"ч /114 1 дР (х, А)
В силу условии (4), (6) и определения (11) для непрерывных функции -------------------- наидется
дА
/ (1) Еп II/ (1)|| 1 дф (А0 + а/)
такое допустимое направление / є Е, |/ 11 = 1, для которого производная ------------------------ от-
лична от нуля при достаточно малом, а & gt- 0 и имеет требуемый знак. Тогда, используя выражение вида (15), приходим к существованию такого а1 & gt- 0, что
Ф (А0 + а/~ + а1/(1)) = Ф (А0 + а/~) + а1 дФ (А + а/) + 0(а1) = ф (А0) = е 0. (17)
д/(}
Подставляя сюда равенство (16), будем иметь
При
дФ (Л0)
дФ (Л0 + ah)
дh (1)
дФ (Л + ah) a,-----------------+ o (a) + o (a,) = 0.
1 дк (1) 1
Ф 0 отсюда следует, что a, = o (a). Таким образом, если Л0 е N (е0) и
= 0, то найдется такое, А = А0 +аИ +а1И (1) =А0 +аИ + о (а) при а®+0, что дИ
Ае N (е0). Поскольку в условиях (12) производная функции максимума Ф (А) равна нулю в точке, А = А0 и по направлению — И, то аналогичным образом получаем, что последний вывод справедлив и при, а ® -0, то есть, А = А0 + аИ + о (а) е N (е0) при, а ® 0 и, значит, И по определению есть касательный вектор к множеству N (е 0) в точке А0 е N (е 0) [26, 27].
Обратно, если
= 1 — касательный вектор к N (е 0) в точке Л0
то
А0 + аИ + о (а) е N (е 0) при, а ® 0 и, следовательно,
Ф (А0) = Ф (А0 +аИ + о (а)) = е 0 (18)
при некотором достаточно малом а.
Полагая здесь о (а) = а1 И (1), ||и (1)|| = 1, где а1 = о (а), приходим к равенству (17), из которого после подстановки выражения (15) следует, что
дФ (А0) дФ (А0 + аИ~)
а-----~----+а,-------------+ о (а) + о (а,) = 0.
дИ дИ (1) 1
При а1 = о (а) последнее соотношение принимает вид
дФ (А0) дФ (А0)
а-----~---+ о (а) = 0 ^~- = 0,
дИ дИ
что и завершает доказательство утверждения 1.
Доказательство утверждения 2. Если И, где
= 1 — касательный вектор к множеству
Wв точке Л = Л0, W = M (I0) или W = N (e0), то
Л = Л0 + ah + o (a) е W при a ® 0, если Л0 е W. Обозначая здесь Л = Л0 + ah + o (a) — 5Л* = ah, имеем отсюда [27]
||Л-Л0 -8Л*|| = oil5Л*||,
(19)
(20)
где || • - евклидова норма.
Теперь, используя разложение zk (А), к = 1,2,…, в ряд Тейлора в точке А0 +5А*, получим с учетом (20) следующую оценку для нормы || | в пространстве 12 разности X (А) — X (А0 + 5А*):
Х (Л) -X (Л0 + 8Л*)|| = ^?(zk (Л) -Zk (Л0 + 5Л*))2
к=1
к=1
? & amp-«(^дЛ+) (Л, — Л — 8Л*) + o (||Л — Л0 — бЛ’Ц)
г=1 дЛ, 11 11
= o 5Л*
Аналогичным образом
||Х (Л0 + 5Л*) — X (Л0)||г = j? (Zk (Л + 5Л*) — Zk (Л))2
к=1
(21)
?
к=1
«дz, (Л0) * II *11
Х-дЛ^ 5Л* + o (8Л*) ,=1 дЛ, 11 11
2
2
2
?
2
2
?
причем здесь не все
д? к (А0). -
і = 1, п- к = 1,2,…, равны нулю одновременно. Действительно, в
противном случае в силу (14)
п / Л0 п? /& quot- Л0
пк (х) = Е5А* Е дА
, ,=1 к=1 дА
1
^(А)пк (Х) = Е ^ «Л*. 0
,=1 дА,
по всем х є О т при 5А Ф 0, что противоречит условию d теоремы 1. Тогда, согласно (22), будем иметь
ІІ2(А0 + 5А*) — 2(А0)|| = 0(115А* II), (23)
II II2 Н ^
где 0(||бА* ||) есть малая того же порядка, что и евклидова норма ||8А*||. Сопоставляя (21) и (23),
получим следующее соотношение:
2(А) — 2(А0 + 5А*) = оГ1І2(А0 + 5А*) — 2(А°)|| 1. (24)
12 V 2 /
Отсюда следует в силу (24) и (19), что
2(А) = 2(А0 + 5А*) + оГ 2(А) — 2(А0 + 5А*)
(25)
= 2(А0) + (2(А0 + 5А*) — 2(А0)) + о| 2(А) — 2(А0 + 5А*)
= 2(А0) + (2(А0 + 5А*) — 2(А0)) + о| 2(А0 + 5А*) — 2(А0)|| І є Ж& quot-
если 2(А) є Ж, где Ж есть отображение Ж в 12. Так как
д2 (А0) *
. *шд2 (А0)
2(А0 +5А) — 2(А0) = ^^д^5А' + о (|5А*||)= аЕ дА ,=1 дА, 11 11 ,=1 дА,
И, + о (а),
д2 (А0)
где не все ------- одновременно равны нулю, то (25) принимает следующий вид:
2 (А) = 2 (А0) + аЕ
д2 (А0)
1 дА,
+ о (а)єЖ*, если 2(А0)єЖ*.
(26)
Последний вывод по определению [26, 27] означает, что отображение
И = (И*) — К =Е
д? к (А0)
1 дА,
каждого вектора И из (12), (13) в 12 есть касательный вектор од-
новременно к М и N *(е0) в точке X (А0), так как всякий вектор И является касательным одновременно к М (10) и N (е 0) согласно утверждению 1.
Используя далее возможность представления вида (15)
/(X + ад) = /(X) + а д2) + о (а) — Нш °(а) = 0
дд «®+0 а
для дифференцируемых по любому направлению д функций / заданных на элементах Ъ нормированного пространства 12 [1], можно далее совершенно аналогично выводу равенства
дФ (А0)
= 0 при доказательстве утверждения 1 показать, что производные отображений I (А) и
д/
Ф (А) по всем направлениям И* равны нулю в точке X (А0). Сказанное завершает доказательство утверждения 2.
Возвращаясь к анализу множеств М*(10) и N*(е0), рассмотрим теперь функцию максимума
Ф*(2) = тах ЕПк (х), 2(А) с 2 = () є 12, А є О
хєО,
(27)
т к=1
и ее производную по направлениям И = (/.) [1] в точке 2(А0):
2
п
дФ^(А0)) ^ ,» (0). ^ (28)
----771----= шах X ИкПк (х] X ] = 1, Я. (28)
дИ х. к=1
Поскольку утверждение 1 справедливо для каждого вектора ± И в силу соотношений (12), (13), то согласно утверждению 2
дФ *(!. (А0)) дФ *(2 (А0))
дИ* д (-И*)
откуда, в соответствии с (28) будем иметь:
= 0, (29)
X И*Лк (х0) = 0, ] = 1, Я*. (30)
к=1
Очевидно, что N * (е 0) с N ** (е 0) = (X е 12: Ф *^) & lt- е 0}, и все касательные к N *(е 0) векторы И* являются касательными также и к N**(е0) в точке X (А0), причем N**(е0) — выпуклое множество в 12 [1] с непустой внутренностью. Тогда к N**(е0) можно провести, по крайней
мере, одну опорную гиперплоскость Г через граничную точку X (А0), такую, что [28]
|? |? ?
Г = ^ е 12: ХРкгк = 4 ХРЛ (А0) = Ь- ХРЛ & lt- Ь, X е N& gt-0), (31)
I к=1 J к=1 к=1
?
где Р = (Р к), ХР к & lt- ?, есть нормальный вектор к Г и Ь — некоторая константа.
к=1
Справедливо следующее
У т в е р ж д е н и е 3. Все касательные векторы И* лежат в любой из опорных гиперплоскостей (31).
Доказательство утверждения 3. Пусть, согласно (26),
X (А) = X (А0) + аИ * + о (а) е N **(е 0) и И * ё Г.
Тогда в соответствии с (31) и (29)
?? ?
ХР к (2к (А0) + аИ*) Ф Ь, ХРЛ (А0) = Ь и аХР А* & gt- 0
к=1 к=1 к=1
при соответствующем выборе знака а, который можно принять любым, заменяя, если потребуется, И * на — И *. Но в таком случае
?? ?
Х Рл (А) = ХРЛ (а0) + аХРА* + о (а)& gt-Ь,
к=1 к=1 к=1
что невозможно при X (А) е N**(е0) в силу неравенства обратного знака в (31). Полученное
противоречие доказывает утверждение 3.
Определим теперь аналитическое представление касательных векторов И* и условие принадлежности И* е Г.
Согласно теоремам о неявных функциях, равенство I (А) -10 = 0 определяет в условиях (5)
для некоторого р е (1, п} переменную, А как однозначную непрерывно дифференцируемую
функцию Ар = g (А1, А2,… Ар-1, Ар+1,…, Ап, I0) в достаточно малой окрестности Q (А0) е шЬОп
точки А0. Отсюда получаем в соответствии с (14) следующее параметрическое представление М *(!0) в окрестности X (А0):
2к = ~к (А1, А 2,…, А р-1, А р+1,…, А п) = (32)
= 2к (А1, А 2 ,…, А р-1, g (А1, А 2 ,…, А р-1, А р+1,…, А п, ^ 0), А р+1,…, А п), к = 1,2,….
Положим здесь, А г = А г (у), А0 = А г (у 0) — у е [у 0 — а, у 0 + а], а & gt- 0, г = 1,2,…, р -1, р +1,…, п,
где Аг (у) — произвольные достаточно гладкие функции скалярной переменной у, отображаю-
л0
щие точку, А при некотором значении у = у0.
В таком случае получим вместо (32)
гк = ~к (а (у)) = Ч (У), к =1,2,…
Если 2*(у0) = 2(А0) єМ*(/0) — 2*(у0 + 5у) = 2(А0 +5А°) єМ*(10), то в силу разложения в ряд Тейлора
^(У0 + 5У) = 2*к (У0) + 5У + о (5У), !іт = 0, к = 1,2,…
ау 5^®0 5у
к = 1,2,…, есть касательный вектор к
а2 '(у 0)
по определению получаем, что
ау
У
, *

М (10) в точке X (А0) и, следовательно, все векторы И, касательные в точке X (А0) одновременно к М * (10) и N * (е 0), согласно утверждению 2, представляются в виде
И. ^(у0) Х т А,(у т & lt-кк (А0) + д^к (А0) дg (А0,10) (33)
Ик =-з- = Хт*А (у0) — тш =-гг-+^-----------------------------гг-. (33)
dy г=1 дА г дА р дАг
г ф р
*.
Если И е Г, согласно утверждению 3, то в соответствии с (31), (33)
?? п п ?
ХР кИк* =ХР к Хт кг А'-г (у 0) =ХАг (у 0) ХР к т *=0. (34)
к=1 к=1 г=1 г=1 к=1
гФ р г Ф р
Поскольку последнее соотношение должно выполняться в силу утверждения 3 для любых А'- (у0), то из (34) получаем следующее необходимое и достаточное условие принадлежности
всех касательных векторов И* опорной гиперплоскости Г:
?
ХР к т кг = 0, г = 1,2,…, р -1, р +1,…, п. (35)
к=1
Для дальнейшего потребуется Л е м м, а 1. Равенства
Х^Л]цк (х.) = 0, к = 1,2,… (36)
]=1
выполняются для всех к=1,2,… в любых Я & gt- 1 различающихся точках х. еО т, ] = 1, Я,
1 & lt- Я & lt-? только тогда, когда все коэффициенты Л., ] = 1, Я равны нулю.
Доказательство леммы 1. Пусть все равенства (36) выполняются в некоторых Я& gt-1 точках х] при не всех Л], равных нулю, и пусть /(х) е Ь2р [О т ] - некоторая функция, удовлетво-
Я
ряющая условию Х Л. /(х.) Ф 0. Тогда, используя, подобно (14), разложение /(х) в ряд Фурье
]=1
с коэффициентами Ск по системе функций Лк (х), будем иметь
Я Я? ? Я
Х Л]/(х]) = Х Л] Х ск Л к (х]) = Х ск Х Л] Л к (х]) Ф 0,
. =1. =1 к=1 к=1. =1
что невозможно в условиях (36). Полученное противоречие доказывает лемму ?.
Теперь установим справедливость следующего предложения.
У т в е р ж д е н и е 4. При выполнении условия (7) для любой опорной гиперплоскости Г
А 0 * Т& quot-1 II * II 1
существует в точке, А такое направление s е 1, $ = 1, что
«Мф^ (37)
д$
Доказательство утверждения 4. Предположим противное, и пусть
дФ (X (А0)) дФ^А0)) 0. Г
------*-----=--------*----= 0 для всех $ е Г,
д$ д (-$)
откуда в силу выражения (28) получаем подобно (30), что
ЕПк (х-) = 0, ] = 1, Я, для всех 5 = (^к) є Г. (38)
к=1
Поскольку 5 є Г, то, согласно (31) и также, как в (34),
ХРк$* = 0 для всех = ($*) еГ. (39)
к=1
Из соотношений (38), (39) следует, что тогда
Лк (х0) = Лк (х2) = … = Лк (х0*) = Рк для всех к = 1,2,…, (40)
где Я * & gt- 2 по условию (7). Но в таком случае равенства (36) выполняются для Я = Я * & gt- 2 при
Я*
любых отличных от нуля коэффициентах Л., удовлетворяющих условию Х Л. = 0, что невоз-
]=1
можно в силу леммы 1. Полученное противоречие доказывает утверждение 4.
Замечание. Отметим, что условие (7), согласно которому здесь Я * & gt- 2, существенно для справедливости утверждения 4. Если Я * = 1, то гиперплоскость
Г1 = ^ е 12: Х Лк (х10)к =е 0 ^ (41)
где х0 — единственная точка максимума функции Р (х, А0), проходит через точку X (А0) и является, очевидно, опорной для N **(е 0) по определению этого множества. Тогда в качестве Г в (31) можно выбрать Г1 и, следовательно, в (31) выполняются равенства (40) для одной точки х0 при Ь = е 0, Р к =л к (х10), к = 1,2,… В таком случае соотношения (38) и (39) при Я * = 1 оказыва-
дФ^ (А0)) 0 * Г 4 П
ются тождественными, и значит -----------*---= 0 для всех $ е Г, вопреки утверждению 4. При
д$
Я & gt- 2 существуют более одной гиперплоскости Г], ] = 1, Я вида (41) и только в этом случае верно утверждение 4.
Рассмотрим далее в окрестности Q (А0) е шЬ Оп точки А0 наряду с исходной некоторую деформированную задачу для, А е Q (А0), отличающуюся от прежней только заменой Р (х, А) в
(2) на функцию Р1(х, А), которая определяется в пределах Q (А0) разложением вида (14)
?
Р1(х, А) = Х ^к1}(А)Лк (х)
к=1
с коэффициентами
(Л) = Zk (Л) + ?g к, (Л,-Л0), к = 1,2,… (42)
i=1 i Ф p
Здесь укг: ХУ*!¦ = сот1 & lt-?, г = 1,2,…, р -1,р +1,…, п, — некоторые достаточно малые
к=1
константы.
Как следует из (14) и (42), в таком случае
F1(x, Л0) ° F (х, Л0), x е Wm- Ф1(Л0) = maxF1(x, Л0) = F (x0,Л0) = Ф (Л0) = е0, j = 1, R (43)
XeWm 1 ' 0 '
В деформированной задаче множество N (е 0) заменяется множеством N1(e 0) = {Л е Gn: Ф1 (Л) = max F1(x, Л) & lt- е 0}, а отображение M* (10) множества M (10) и каса-
xeWm
тельные векторы h** = (h*k) к М*(10) в точке X (Л0) описываются вместо (32), (33) на основании (42) соответственно выражениями
(Л) = ~к (Л) + к, (Л i -Л0), к = 1,2,… — (44)
i=1, Ф Р
h* = ZmLЛ,(У0) — mк, — =mk, +gк, к = 1Д… (45)
i =1
i Ф p
Выберем теперь уш в (42) так, чтобы все векторы И** в (45) лежали вместе с И* в опорной гиперплоскости (31). Это требование удовлетворяется, если вместе с (35) выполняются условия
ХР к У кг = 0, г = 1,2,…, р — 1, р +1,…, п, (46)
к=1
что показывается по схеме вывода соотношений (35).
У т в е р ж д е н и е 5. При выполнении условий (46) точка А0 является локальным решением А1 е Q (А0) сформулированной выше деформированной задачи.
Доказательство утверждения 5. Предполагая противное, будем иметь
I (А1) = ~ & lt-I (А0) = 10 при ФДА1)& lt-е0.
В силу условий (4), (6), малости у ^ и непрерывности рассматриваемых функций по у кг и
А, в точке А1 существует такое направление я1 е Оп, Ця1! = 1, что -----------^-) & lt- 0, причем
II II д$
д (-) & gt- 0, если А1 е Q (А0) есть локальное решение деформированной задачи.
д$
Но тогда в соответствии с (5) найдется вектор я2 е Оп, |$ 2|| = 1, достаточно мало отличаю-
й Еп 1 д (А1) 0 дФ (А1) 0 И
щийся по норме в Е от $, для которого -^ & lt- 0. Используя выражения вида
д$ д$
(15), приходим в таком случае к выводу о существовании точки А2 е Q (А0): I (А2) = 0 & gt-I-
ФДА2) & lt-е0.
Последнее означает, что некоторая внутренняя точка А2 множества Nl (e0) = (Ае ап: Ф1(-)& lt-е0} принадлежит множеству М (10), а значит пересечение М (10) с шЬ N1(e0) не является пустым множеством, т. е. М (10) 11Ш N1(e0) Ф0. Отсюда следует для малых у ш, сохраняющих выполнение условия ф теоремы 1 в деформированной задаче, аналогичный вывод для отображений М* (10) и N1* (е 0):
М* (10) 11п! N1* (е 0) Ф 0 ^ М* (10) 11п! N** (е 0) Ф 0, что показывается по схеме доказательства утверждения 2.
В таком случае Q*(X (А2), 5) е шЬN**(е0), где Q*(X (А2), 5) — шар достаточно малого радиуса 5 с центром в точке X (А2). Если И** - касательный вектор к М*(10) в точке X (А0), то, подобно (26), будем иметь X (А2) = X (А0) + аИ** + о (а) еМ*(!0) — X (А0) еМ*^0), и так как X (А2) — (X (А0) + аИ**) = о (а), то при достаточно малом, а получаем, что
X (А0) + аИ** е Q*(X (А2), 5) е шЬN**(е0) и, следовательно, аИ** е шЬN**(е0). Но тогда вектор И** не может принадлежать опорной гиперплоскости Г к N**(е0), проходящей через точку X (А0) по определению Г, что противоречит условиям (46), при выполнении которых И** еГ. Полученное противоречие доказывает утверждение 5.
Покажем теперь, что можно так выбрать опорную гиперплоскость (31), коэффициенты у кг
в (42), значения А'- (у0) в (45), чтобы все касательные к М*^0) векторы И**, принадлежащие Г вместе с И* в условиях (46), в то же время не являлись бы касательными векторами к N**(е0), а значит, и к ^*(е0), т. е. в соответствии с утверждением 4 для всех И** не выполнялись бы, в противовес (29), равенства
дФ: 2^=дl>-:щА°))=0. (47)
дИ ** д (-И)
Возможность выбора И**, удовлетворяющих указанным требованиям, определяется в соответствии с утверждением 4 существованием направлений в Г с ненулевой производной функции максимума Ф * (X).
Равенства (47) в силу (28), (45) приводятся, подобно (30), к виду
Е Ик**Пк (х0) = Е
к=1
к=1
п
Еткі Аі (у 0)
і=1 і Ф Р
Пк (х°0) =ЕАі (у 0)
і=1 ІФ Р
Еткі Пк (х0)
к=1
= 0, 7 = 1, Я.
(48)
Положим в (48) А'- (у0) = 0, V = 1, п — Я * -1 для любых п — Я * -1 значений
е (1,2,…, р — 1, р + 1,…, п}, если Я * & lt- п — 1 в условиях исходного предположения Я * & lt- п -1. Тогда приходим к выводу, что производные (47) не равны нулю для всего ограниченного указанным образом множества векторов И**, если однородная система Я* & lt- п — 1 линейных уравнений
ЕАіГ (у 0)
Г=1
Ет*і, Пк (х0)
к=1
= 0, 7 = 1, Я
(49)
где іг, г = 1, Я — все Я значений і є {1, п} за исключением і = іу и і = р, не имеет нетривиаль-
ных решений А'- (у0), г = 1, Я, для чего достаточно, чтобы определитель этой системы был отличен от нуля:
^|Хтиг Лк (х0Ф 0- г, ] =1, Я*. (50)
Выберем теперь Г по (31) так, чтобы условия (46) и (50) были совместны. Заметим, что не всякая опорная гиперплоскость удовлетворяет этим требованиям. Действительно, опорными
для множества N **(е 0) в точке X (А0) являются, очевидно, все гиперплоскости вида (41)
Г Ч2 є 12: ЕгкПк (х7) = е0 ^ 7 = 1Я^
к=1
число которых Я* & gt- 2, и их произвольные линейные комбинации
Г Я*? ? {Я* ^ Я* 1
ГЕ =Г Xе 12: ХС Х^Лк (х0) = Х ХС, Лк (х, 0) ^ =е0,0& lt-С, & lt- 1, ХС, = 1 Г.
7=1 к=1
(51)
(52)
¦V ]=1 0 ]=1 ]
Для всех Г] и ГЕ по (51), (52) соотношения (46) и (50) не могут быть выполнены одновременно с равенством (35), которое является следствием утверждения 3. Действительно, если в (31) Г = ГЕ, то
Рк =ЕС}Пк (х0), к = 1,2,…
7=1
(53)
Рассматривая теперь равенства (35) и (46) только для г = гг в (50) и складывая их, получим в силу (45), (53)
Ерк (т"Г +укіг) = ЕркткіГ =ЕСІ Ет*іГПк (х°0) 1 =0, г =1,Я
(54)
к=1 к=1 ]=1 V к=1
что означает линейную зависимость строк определителя системы уравнений (49), и следовательно, в данном случае обеспечить неравенство (50) невозможно. Отсюда, в частности, следует, что если Я * = 1, то условия (46) и (50) заведомо несовместимы при наличии единственной опорной гиперплоскости Г1 вида (51), что опять свидетельствует о существенности допущения (7) в формулировке теоремы 1.
Выберем далее любые две различающиеся точки х0 из их общего числа Я & gt- 2. Пусть для определенности это будут х0 и х0. Если все Г] в (51) — опорные гиперплоскости множества N** (е 0) в точке X (А0), то
Егк (А0)Пк (х0) = е0- Е2кПк (х0)& lt-е0, 2єм**(е0) — 7 = IЯ*.
к=1
к=1
Отсюда следует, что
Е (^к — гк (А0))Пк (х°) & lt- 0, 2 є N** (?0) —
к=1
?
Е гк л к (х 2) + Е (гк — (Л°))л к (х°) ?е о, 2 е N **(в 0). (55)
к=1 к=1
Поскольку 2(Д°) — граничная точка выпуклого множества N**(в°), то найдутся такие к е {1,2,… }, что разности гк — zk (Д°) не меняют знака в пределах N**(в°) (иначе любое направление в шаре с центром в 2(Д°) будет принадлежать N**(в °), что противоречит опреде-
лению граничной точки). Тогда для любого из этих значений к = к1 можно выбрать такое ~к, фЛк1(х°), что (2К — г*. (Д°))Лк, & lt- (^ - ^(Д°))лк,(х1°) для всех 2 е N& quot-"-"-(в°). Но тогда в
силу (55) будем иметь:
? ?
/ *(2) = Е гк л к (х 2°) + Е (гк- гк (Д°))л к (х10) +(гк, — гк1(Д°))л к, ?в о, 2 е N **(в о),
к=1 к=1
к ф к!
причем строгое равенство достигается здесь при 2 = 2(Д°). Следовательно, гиперплоскость
Г* = е 12: /* (2) = в° }, не совпадающая ни с одной из Г-- и ГЕ в (51), (52), является в то
же время опорной к множеству ^*(в °) в точке 2(Д°) при произвольных Лк1 Ф лк1(х°), что и
доказывает существование такой Г в (31) при соответствующем выборе Р к и Ь, для которой обеспечивается совместность условий (35), (46) и (5°).
?
Согласно теореме Рисса-Фишера [25] при любых укг: ?у^ & lt-? найдутся такие функции
к=1
ф о (х), ф г (х), Г = 1, Я, и ф (х), 7 = 1, П, в Ь2, р [О т ], что
?? ?
ф °(х) = Ер к л к (х) — ф °(х) = Ет и, л к (х) — фг (х) = Еу и л к (х).
к=1 к=1 к=1
Здесь ф°(х) и ф°(х) фиксируются значениями Рк в (31) и ткг в (33), а ф г (х) зависят от выбора у кг в (42).
В таком случае
?? ?
Ерк у кг =Ерк |ф|(х) р (х) л* (х) Лт= | ф|(х) р (х) Ерк л* (х) Лт =
к=1 к=1 От От к=1
= фг (х)ф°(х) р (х) ф, г = 1,2,…, р -1, р + 1,. п,
О т
и соотношения (46), (5°) принимают вид
ф (х)ф°(х)р (х)ф = °, г = 1,2,…, р-1,р + 1,. п- (56)
ае1{ф°(х°°) + фг, (х°°)} Ф °- ], г = 1, Я*. (57)
Задавая произвольную совокупность достаточно малых значений фг (х°), обеспечивающих выполнение неравенства (57), можно затем множеством различных способов выбрать каждую из функций фг (х) требуемого порядка малости с фиксированными значениями фг (х°), исходя из г-того равенства (56).
Теперь искомые коэффициенты у ш, при которых одновременно соблюдаются условия (46) и (5°), могут быть найдены как соответствующие коэффициенты разложения фг (х) в ряд по системе {лк (х)}.
Так как в соответствии с утверждением 5 локальное решение сформулированной выше деформированной задачи с определенными указанным образом коэффициентами у к совпадает в
окрестности Q (Д0) с Д°, для нее сохраняются, в виду малости уш и непрерывности рассматриваемых функций по совокупности аргументов, условия а) — е) теоремы 1 и выполняется тождество в (43), то для такой задачи так же, как и для исходной, в предположении Я * & lt- п, имеют
От
место в тех же точках х0 соотношения (12), (13) после замены Р (х, А0) на РДх, А0) и, как
следствие, (утверждение 2) существуют общие касательные векторы И ** к М*(I) и N**(ь0) для которых, аналогично (30), выполняются равенства
следствие, (утверждение 2) существуют общие касательные векторы И ** к М*(1) и N**(е0),
?Ик~ъ (х°) = 0, ] = 1, Я*. (58)
к=1
Среди нетривиальных решений однородной системы уравнений (12) с рангом
г * & lt- Я * +1 & lt- п -1 при Я «& lt- п -1 содержатся такие, что И, = 0, V = 1, п — Я * -1, для некоторых п — Я * -1 значений ^ е {1, п}, ^ Ф р, поскольку г * базисных переменных этой системы линейно выражаются через п — г * свободных неизвестных, число которых больше единицы при
* 1
г & lt- п -1.
Данный вывод остается справедливым вместе с соотношениями (12) и для деформированной задачи и, следовательно, в силу утверждения 2 при Я * & lt- п -1 существуют касательные векторы И **, для которых А'- (у0) = 0 в выражениях (45). Тогда равенства (58) в силу соотно-
шений (45) редуцируются при всех Я & lt- п -1 к однородной системе уравнений
(^
п
? и*пк (х0) = ?
?т к, А'- (у 0)
,=1
Vг Ф р 0
пк (х])=
= ?А'- (у0)?ткпк (х0) =? ?т"г п (х])]Аг'-г (у0) =0, ] =1Я* (59)
'-0/^ г^кг 1! к ^-Л'-] / _ /^ГЧ^г хк л] / 0& gt-
, =1 к=1 г=1 V к=1 0
, ф Р
с нетривиальным решением относительно А, (у0), где так же, как в (49),, г, г = 1, Я* - все
значения, е {1, п}, за исключением и р.
С другой стороны, система (59) не может иметь нетривиальных решений в условиях (50).
С учетом тождества в (43) полученное противоречие означает, что неравенство Ях & lt- п в системе уравнений вида (10) невозможно как для деформированной, так и для исходной задачи, откуда в итоге непосредственно следует утверждение (8) теоремы 1.
2°. Рассмотрим далее задачу (1), (2) при е0 = е[1. В силу (7) достаточно рассмотреть здесь
случай п & gt- 2. Вопреки утверждению (9) теоремы 1 предположим теперь, что Ях = Я ** & lt- п +1,
где в соответствии с (7) Я ** & gt- 2.
При е 0 = е [пП искомая точка А0 является решением минимаксной задачи
Ф (А) = тах{р (х, А): х е От }® т1п, А е Оп. (60)
дФ (А0) 0 и и (п) **
Условие --------& gt- 0 & quot-И е К (А), И = 1, при е 0 =е тП приводит при Я & lt- п +1, подобно
дИ
(12), (13), к существованию таких возможных направлений И е Еп, И = 1, для которых
дР (х0,а0) -* дФ (А0) ГдР (х0,А0) Ч
1 -И, = 0, ] = 1, Я ----1 = тах
г=1
дА
, И
= 0.
Отсюда, опять используя разложение (14) функции Р (х, А) в ряд Фурье, приходим по схеме доказательства утверждений 1 и 2 к существованию касательных векторов И * = (Ик*), к = 1,2,…, к множеству N**(е[1) = 2 е 12: Ф*(2) & lt-е[11 } в точке 2(А0), которые являются отображением в 12 направлений И — лежат в опорной гиперплоскости (31) (в соответствии с утверждением 3 и, подобно (29), (30), удовлетворяют равенствам:
?и*Пк (х0) = 0- ] = 1, я**. (61)
к
к=1
Здесь Ф*(2) по-прежнему определяется согласно (27). Аналогично (33) получаем представление И * в виде
х
И* dzl (v0) п_ А (ч _ д^к (А0), 12 (б2)
Ик =--- = ?т*,-А,(У0) — т*, — = --, к = 1,2,…, (62)
ау ,=1 дАг
где в отличие от (33) исключается ограничение г Ф р, коэффициенты тш содержат лишь первое слагаемое тш в (33). Очевидно, что по определению векторы И * в форме (62) являются одновременно касательными векторами в точке А0 к параметрически задаваемому разложением (14) множеству К * = {2 е 12: гк = гк (А), к = 1,2,…, А е Оп }.
Перейдем теперь, по аналогии с п. 10, в окрестности 2(А0) к деформированной минимаксной задаче вместо исходной (60):
Ф1 (А) = тах{р (х, А): х е От }® т1п, А е Оп, (63)
в условиях (42), (43), где, как и везде далее, опять исключим неравенство г Ф р.
Тогда К * заменяется множеством
0
К =|2 е 12:. 2к = 2к (А) +? У кг (Аг — А.), к = 1,2,…, Ае Оп| и, подобно (45), касательные векторы И ** к К** в точке 2(А0) описываются на основании (62) следующими выражениями:
_ п
К* =?^2-А, (У 0) — Мк = Мк + У кг, к = 1,2,… (64)
, =1
Аналогично (35), (46) получим, что все И ** лежат вместе с И * в опорной гиперплоскости
(31), если выполняются соотношения
? ?
?Р к ткг= 0- ?Р к у кг = 0- г = 1, п. (65)
к=1 к=1
В условиях (65) опять оказывается справедливым утверждение 5 о совпадении решений А1 и А0 деформированной и исходной задач, рассматриваемых в 0(А0). Действительно, в противном случае ФДА1) & lt-Ф1(А0) = Ф (А0) — Ф*(2(А1)) & lt-Ф*(2(А0)), где Ф*(2) определяется по (27) — 2(А1) е К** для деформированной задачи и, следовательно, 2(А1) есть внутренняя точ-
Т**, (п) (п) -Т. / А 0 Т/¦** Т1 Т-** / (п)
ка множества N (етП), где етП =Ф (А), т. е. пересечение К с внутренностью N (етП) не
является пустым множеством:
к * п иг N& gt- тпп) ф0. (66)
Отсюда по схеме завершающей части доказательства утверждения 5 приходим к выводу, что И ** ё Г, а это невозможно, если выполняются равенства (65).
Теперь, точно так же, как и для случая е 0 & gt- е ГП1Г1, опираясь на утверждение 4, устанавливается при Я ** & gt- 2 возможность такого выбора опорной гиперплоскости Г и касательных к К ** векторов И **, принадлежащих Г вместе с И * в условиях (65), при котором все И ** не являются
Т» Т ** / (п)
одновременно касательными векторами к N (е т1п).
Аналогично предыдущему п. 10 такая возможность сводится к совместности условий вида (46), (50), которые в данном случае, подобно (56), (57), записываются следующим образом:
|ф, (х)ф0(х)р (х) ф = 0- г = 1, п- (67)
О т
аег{фг0 (х]) + ф 1 г (х])}Ф 0- ], г = 1, Я**, (68)
?
где ф0 (х) =? ты П к (х), все остальные функции определяются так же, как в (56), (57), и способ
к=1 г
выбора достаточно малых коэффициентов у кг в (42), удовлетворяющих соотношениям (67), (68), остается прежним. Далее, следуя схеме последнего этапа доказательства по п. 10, получаем, что если А0 является одновременно локальным решением деформированной задачи (63), то в условиях (43) при Я** & lt- п +1 должны выполняться, аналогично (61), равенства
? Кк (х0) =0- ] =1Я**,
которые, с другой стороны, оказываются невыполнимыми в условиях (68).
Полученное противоречие доказывает утверждение (9) теоремы 1, что и завершает ее доказательство в целом ?.
Заметим в заключение, что альтернансные свойства (8) и (9) для решения задачи (1), (2), & quot-не отягощенные& quot- дополнительными признаками обобщенного альтернанса [18−21], устанавливаются теоремой 1 в условиях, существенно ослабленных и значительно проще проверяемых при практическом решении задач по сравнению с традиционными.
2. Минимаксная задача полубесконечного программирования
Перейдем теперь к рассмотрению задачи на минимакс:
/1(A) = max|p0(y, A): y е Lr, r & gt- 1}® min, Ае Gn- (69)
с ограничением (2)
Ф (А) = max{F (х, A): x е W т, m & gt- 1}& lt- e 0, e 0 & gt- e ?? & gt- 0.
Здесь Lr — связное компактное множество в Er- F0(y, А) — заданная функция, непрерывная
вместе со своими частными производными по совокупности аргументов на Lr х Gn, и все ос-
тальные элементы определяются так же, как в задаче (1), (2).
Для характерных частных случаев, когда вместо самих функций F0 (у, А) или (и) F (х, А) рассматриваются их модули, задача приводится к виду (69), (2) с помощью преобразования, приведенного в замечании 1.
Подобно (3), будем всюду далее считать выполненным достаточное условие
lim 11(А) =? (70)
||А||®?
существования решения задачи (2), (69) для всех e 0: e |"П & lt- e 0 & lt- e, где
e = Ф (А) — А = arg inf {/j (А): А е Gn }. (71)
Замечание 2. Очевидно, что по определению (71) решение, А минимаксной задачи (69) без функциональных ограничений является одновременно решением задачи (69), (2) для всех e0 & gt-8 ?.
Пусть, подобно условиям а) — е) теоремы 1 для всех e0: e^П^П & lt-e0 & lt- e, при которых существует решение А0 задачи (2), (69), выполняются следующие допущения, характеризующие искомую точку А0:
а:) А0 е int Gn — (72)
bi) для всех e 0 & gt-e mn^ и / j (А0) & gt- inf {/1(А): Ае Gn } найдутся такие векторы s, s,
\s\ = 1, \s\ = 1, принадлежащие конусу K (А0) возможных направлений множества Gn в точке
А0, что производные в этой точке функций максимума /1 (А) и Ф (А) по соответствующим направлениям отрицательны:
^ & lt- 0. «Ф (А!& gt- & lt- 0,1 И = 1Щ = 1- (73)
ds ds ^ ^
ч ф 5F0(y, А0) 5F (х, А0). 1- й
с1) функции -------------------------------- и-, г = 1, n, линейно независимы, соответственно, на
М г дАг
Lr & quot- y и W m & quot- х-
d1) наряду со множеством Wm (А) = {хеПт: F (х, А) = Ф (А) = e} в условии е) теоремы 1
всякому Ае Gn сопоставим множество Lr (А) = {y е Lr: F0(y, А) = /1(А)} всех точек на Lr, в
которых F0 (y, А) достигает своего максимального значения, равного /1 (А) — тогда будем считать, что числа Ях и Ry различающихся точек, принадлежащих, соответственно, Пт°(А°) и
Lr (А0) при e = e 0 и, А = А0, ограничиваются при выполнении (73) неравенствами
Rx & gt-2- Ry & gt-2. (74)
Альтернансные свойства решений задачи (2), (69) в описанных условиях определяет, подобно теореме 1, следующаим образом.
Т е о р е м, а 2. Пусть А0 = (А1]), г = 1, п — решение задачи (2), (69) и выполняются допущения а1) — йг).
Тогда существуют Яхразличных точек х0 еОт (А0), у = 1, Ях, и Яу различных точек
У0 е Ь (А0), V = 1, Яу, где
Ях + Яу = п +1, если 8тп & lt-80 & lt-8- (75)
Ях = п +1 если 80 =8??- (76)
Яу = п + 1, если 80 & gt-8. (77)
Доказательство теоремы 2
Поскольку для 80 =8["П и 80 & gt-8 задача (2), (69) с учетом замечания 2 сводится к минимаксным задачам, соответственно Ф (А) ® шт, А е Оп и 11 (А) ® шт, А е Оп, то в условиях а!) — ^) утверждения (76) и (77), по существу, повторяют доказанное ранее утверждение (9) теоремы 1 и, следовательно, остается рассмотреть случай (75). Доказательство равенства в (75) проводится по общей схеме доказательства теоремы 1.
В силу (74) достаточно рассмотреть (75) при п & gt- 4. Вопреки утверждению (75) предполо-
д/ДА0) дк
мых направлений к е К (А0) при 8П & lt-8 0 & lt-8 приводит тогда, подобно (12), (13), к существо-
й ~ (~) ¦ Г& quot- дФ (А0) д/1 (А0)
ванию возможных направлений к = (кг), г = 1, п, с нулевыми производными ------~- и
жим теперь, что Ях + Яу = Я & lt- п +1. Условие локального минимума -^- & gt- 0 для допусти-
функций максимума Ф (А) и 11 (А) в точке А0:
дФ (А0)
-----~- = тах
дк
др (х0,А0) ^ д1 (д0) ^д^ (-0 л0) ^
] -
дА
V
0 дії (А0)
= 0- -------~- = тах
дк у0
д^СС А)
дА
= 0-
дк дк
= 1- (78)
] = 1, Ях- V = 1, Яу ,
У
где
п др (х0,А0) ~ п дР0(у0 А0) ~
I дА ~ = 0-, А) ~ = 0 (79)
і=ї дА г г-=1 дА і
для всех у = 1, Ях- V = 1, Яу.
Выполним теперь, аналогично (14), разложение р (х, А) и р0(у, А) в ряды Фурье по некоторым полным ортонормированным с весами р Р (х) и р р0 (у) системам функций
{Пр (х)}е и, рг [О т ] и {п р0(у)}е 12, рГо[1г ]:
?
р (х, А) =? Хр (А)лр (х) — Хр (А) = { Р (х, А) рр (х) лр (х) ф- (80)
к=1 О

?
рo (y, А) = ?2р0(А)пр0(у) — 2р0(А) = |рo (y, А) рр0(у)лр0(у)(81)
к=1 Ьг
Так же, как и при доказательстве теоремы 1, приходим к выводу, что векторы к в (78), (79) являются одновременно касательными векторами в точке А0 к множествам
Р (/10) = {а е Оп: /ДА) & lt- /ДА0) = 1 т } и N (8 0) = {Ае Оп: Ф (А) & lt-8 0}, где А0 е Р (1Ю) П N (8 0), а
отображения
п д7р0(Д0)~ п д7р (А0)~
кр0 = (ккр0), кр0 =Ед^д (^, к = 1,2,… и кр = (ккр), кр =?г^ДГ}кЧ, к = 1,2,…, каждого
=1 дА, дА і
вектора к — касательными векторами в различающихся точках {г0 (А0)} и (А0)} к отобра-
жениям Р*(110) и N*(80) в пространстве /2, соответственно, множеств Р (110) и N (80).
Аналогично (29), (30) получим тогда, что производные функций максимума
?
11* (гр°) = тах? гр лр (у) — 2р° (А) с 2Р0 = (гр) е /2, А е Оп — (82)
уеЬг к=1
Фгр) = тах I грк цРк (х) — 2р (А) с 2Р = (гРк) є 12, А є Оп (83)
хєО,
т к=1
соответственно по направлениям кР& lt->-, кр& gt- = 1, и кр, ||кр || = 1 равны нулю в точке А0:
ді-(2р°(А0)) х, р, р1(0) 0 (84)
------г--------= тах I кк0 Ц к0(Уv) = 0- (84)
дк 0 -V к=1
дФ *(2р (А0))? 0
---------р-= тах I ккЦк (хі) = 0, (85)
дк х» к=1
причем здесь
IVцЛУv) =0, v =1 Яу- (86)
к=1
I кр цр (х°) = 0, ] = 1, Ях. (87)
к=1
Подобно утверждению 3 при доказательстве теоремы 1 можно показать, что все векторы к 0 и кр принадлежат опорным плоскостям, соответственно Гр и Гр вида (31), проведенным через граничные точки 2р°(А0) и Хр (А0) к выпуклым множествам с непустой внутренностью Р**(І10) = 2р°: і*^)<-і 10ЬР*(І10) и N**(80) = 2р: Фгр)<-80ЬN*(80):
Гр = 2Р& lt-0: ?р р0 гр = ЬРо к? р р0 гр & lt- ЬРо, & quot-ХР0 е Р **(7ю) — (88)
I к=1 ] к=1
??
Гр =р: ?РР^Р = Ьр I- ?Р*грк & lt-Ьр, & quot-2Р еN"(80). (89)
I к=1 ] к=1
Используя параметрическое представление, А = А (у) в виде достаточно гладких функций
скалярной переменной у, получим, аналогично (62), что кр& lt-0 и кр могут быть представлены в форме касательных векторов соответственно к параметрически заданным множествам
Кр0 =2Р° е /2:Р0 = гР0(А), к = 1,2,… -Ае Оп } и
К*р =2Р е / 2: ^ ^ (А), к = 1,2,…- Ае Оп } в точках 2Р°(Д°) и 1Р (А0):
ккр0 = =? тР А] (у 0) — т Р =- к = 1,2,… — (90)
кр = = ?тргд-(У0). тРг = МД^- к = 1,2,… (91)
йу г=1 дА г
При этом, подобно (35), (65), все векторы кр& lt-0 и кр принадлежат, соответственно, опорным гиперплоскостям Гр0 и Гр, если выполняются равенства
? ?
?РР0тР° = 0- ?РРтР = 0- г = 1, п. (92)
к=1 к=1
Далее, аналогично доказательству теоремы 1, рассмотрим в окрестности 2(А0) е шЬ Оп точки А0 некоторую деформированную задачу, отличающуюся от (2), (69) только заменой
Р (х, А) и Р0(у, А) на функции Р (х, А) и Р0(у, А), определяемые в пределах 0(А0), подобно
(42), разложениями вида (80), (81) с коэффициентами
~кР0(Д) = гР0(Д) + ?уР0(Дг -Д0), к = 1,2,… — (93)
г =1
~кР (А) = гРк (А) + ?уР (А- Д0), к = 1,2,…, (94)
г=1
где у Р:? (у р0) & lt-?- у кг:? (у ы) & lt-?, г = 1, п — некоторые малые константы.
к=1 к=1
При этом так же, как в (43), выполняются условия совпадения функций Р (х, А) с Р (х, А) и Р0 (у, А) с Р0 (у, А) в точке, А = А0:
р0(у, А0) = Р0(у, а0), у еЬг- Р (х, А0) = Р (х, А0), хеОт. (95)
Для деформированной задачи множества Р (/10) и N (8 0) заменяются множествами Р (/10) = {а е Оп: РДА) = тах (р0 (у, А): у е Ьг) & lt- р (А0) = /ДА0) = /ю } и
N (8 0) = {а е Оп: Ф (А) = тах (Р (х, А): х е О т) & lt-80} их отображения Р*(/10) и N*(80) в отли-
чие от Р* (/10) и N*(80) описываются теперь выражениями (93), (94) вместо (80), (81), а множества Кр0 и К*р трансформируются, соответственно, к виду
К^ =2Р0 е /2: гр = ~кР0(А), к = 1,2,…- Ае Оп }- Кр = {гр е /2: гР = рР (А), к = 1,2,…- Ае Оп }. Тогда касательные векторы к Р0 и /гр к множествам и КР в точках 2 Р0(Д0) = '-|{?Ak0 (А0)} и 2р (А0) = {рР (А0) } определяются вместо (90), (91), подобно (64), выражениями:
РкР0 =?Рр°Дг (у0) — РР0 =тр +уРк = 1,2,…, (96)
г=1
~кр =? РР а'- (у 0) — РР =т Рг + у Р, к = 1,2,… (97)
г =1
Эти векторы так же, как и кр& lt-0, кр, принадлежат тем же гиперплоскостям ГР0 и Гр по
(88) и (89), если наряду с (92) выполняются, подобно (65), равенства
? ?
?РР0уР = 0- ?РРуРр = 0- г = 1, п. (98)
к=1 к=1
Покажем теперь, что аналогично утверждению 5 при доказательстве теоремы 1, в условиях (98) точка А0 является одновременно локальным решением А1 е Q (А0) деформированной задачи.
Предполагая противное, будем иметь тогда
/ДА1) = тахрД у, А1):у е Ьг }& lt-/ДА0) = /1(А0) = /10-
Ф (А1) = тах{~(х, А1): х еО т }& lt-8 0.
В силу условий (72), (73), малости ур и непрерывности рассматриваемых функций по ур и
Д ~ О 11~Н 1 Д А1 дФ (А1) 0
А, существует такое направление 5 е Оп,? = 1, что в точке, А = А имеем -----------& lt- 0, причем
д?
д/ДД1) — л1
----~- & gt- 0 в соответствии со свойствами точки, А локального минимума в рассматриваемой
д?
деформированной задаче.
Поскольку, согласно (73),
д/1 (А0) {^'-0 л04 ^
= тах
ды
Уv
дА
& lt- 0,
дР,(у1_, Д)
дА
/
00
то ------^-------Ф 0 для всех V = 1, Яу и тогда в силу малости у р, условия, А е Q (Д) и непре-
рывности рассматриваемых зависимостей от у р0 и, А получим, что последнее неравенство соф — дР0(Р°, А1) Ф 0
храняется и в деформированной задаче, т. е. --------Ф 0 для всех V = 1, Яу, где
дА
ру0 е р (А1) = {у е Ьг: РДу, А1) = /ДА1)}
В таком случае существует такое направление ~1, достаточно близкое к ~, для которого
дФ (А1) & lt- 0 д~1 (А1) & gt- 0
дР1 ' сР1 '-
Отсюда по схеме доказательства утверждения 5 приходим к выводу о пересечении множеств Р (I10) и int N (e0), а значит, int P (I10) и N (e0) с непустыми внутренностями:
P (IW) nint 7V (e0) Ф0- (99)
N~(e 0) П int Рад Ф0. (100)
В свою очередь, при переходе к отображениям в 12, из (99), подобно (66), следует, что
K*F П int N**(e0) Ф0. (101)
и аналогичным образом, в соответствии с (100), получаем
KF0 n int Р** (110) Ф0. (102)
Так же, как и при доказательстве утверждения 5, последние выводы означают, что касательные векторы hF и НР°, определяемые согласно (96), (97), при достаточно малых gF и
gF в условиях (101), (102) не принадлежат опорным гиперплоскостям, соответственно
TF и Гр, что невозможно, если выполняются равенства (98).
Полученное противоречие свидетельствует о том, что А0 действительно является локальным решением рассматриваемой деформированной задачи.
Подобно утверждению 4, получаем, что в условиях (74) производные обеих функций максимума I*(Zf°(A)) и Ф*(ZF (А)) в точке А0 не равны нулю по всем направлениям в опорных гиперплоскостях Гр и Гр соответственно. Опираясь на этот факт, можно аналогично тому, как это сделано при доказательстве теоремы 1, так выбрать эти гиперплоскости, коэффициенты gFi и gр в (93), (94) и значения А'-(у0) в (96), (97), чтобы все векторы hF и hF, принадлежащие Гр и Гр вместе с hF° и hF, одновременно не являлись бы касательными векторами к
множествам Р *(I10) и N*(e0) соответственно.
Подобно (50), достаточным условием для выполнения этого требования является неравенство нулю определителя соответствующей однородной линейной системы уравнений вида (49) при исходном предположении Rx + Ry & lt- n:
ае! 1? Рк°лрЧу0) — ?РрЯ лр (х0 пф 0-V = I Яу- у =1 Ях- я = I Ях + Яу, (103)
1к=1 к=1)
где гд е {1, п} - любые Ях + Яу из п возможных значений г е {1, п}, и в отличие от (49), (50) учитывается необходимость выполнить рассматриваемое требование одновременно для обоих множеств Р *(/10) и N *(8 0).
Так же, как и при доказательстве теоремы 1, можно показать, что при одновременном выполнении условий Ях & gt- 2, Я у & gt- 2, согласно (74), соответствующий выбор обеих опорных
гиперплоскостей Г. и Гр обеспечивает совместность условий (98) и (103).
Далее, аналогично (56), (57) и (67), (68), обозначая
??
Ф0(х) = ?Ррлр (х) — ф0(у) = ?Рр0пр0 (у) —
к=1 к=1
??
фЯ (х) =? тлр (х) — фЯ (у) =? тлр0 (у) —
к=1 к=1
??
фг (х) = ?урлр (х) — фг (у) = ?у. лр0(у),
к=1 к=1
приведем соотношения (98), (103) к следующему виду:
Фг (х)ф0(х)рр (х)ф = 0, г = 1, п- (104)
О т
^ Фг (У)Ф0(у) рр0(у)йт = 0, г = 1, п- (105)
ае!{ф0я (у:) + Фг, (У0) — Ф, (х0) + Ф, (х0)}ф 0, V = Яу- у = 1Я- д = 1, Ях + Яу. (106)
После выбора здесь произвольной совокупности достаточно малых значений фг (х0) и фг (у°), обеспечивающих выполнение неравенства (106), можно затем любым из возможных способов выбрать каждую из функций фг. (х) и фг. (у) требуемого порядка малости с фиксированными значениями фг (х0) и фг (у°), исходя из г-тых равенств в (104) и (105). Теперь искомые значения у Р° и у Р, при которых одновременно выполняются условия (104)-(106), находятся как соответствующие коэффициенты разложения соответственно функций фг (у) и фг (х) в ряды по системам (лР° (у)} и (лР (х)}.
Следуя далее схеме завершающей части доказательства пп. 1° и 2° теоремы 1, получаем, что если А° является одновременно локальным решением сформулированной выше деформированной задачи, то в условиях (95) при Ях + Яу & lt-п +1 существуют векторы кр° и НР вида
(96), (97), касательные, соответственно, к Р*(110) и N*(е°) в точках 2Р°(А°) и 2Р (А°), для
которых в тех же точках у° и х° выполняются, аналогично (86), (87), равенства
I ^° пР°(у») = °- IЬР цр (х°) = 0- V = 1, Яу- ] = 1, Ях. (107)
к=1 к=1
Подобно (59), эти равенства в силу соотношений (96), (97) редуцируются при всех Ях + Яу? п к однородной системе уравнений
Ях + Яу (?
I 11~4лр0(Уv) К (у°) = °- v =1 Яу-
9=1 V к=1 0
(1°8)
Ях + Яу (? Л
I Iтр"лкр (х°) А- (у°) = °- ] = 1Ях
9=1 V к=1 0
с нетривиальным решением относительно А'-, где, д = 1, Ях + Яу — некоторые Ях + Яу из п значений г е (1, п}.
С другой стороны, система уравнений (108) не может иметь нетривиальных решений в условиях (103). С учетом тождества (95) полученное противоречие означает, что неравенство Ях + Яу & lt- п +1 невозможно как для деформированной, так и для исходной задачи, откуда следует утверждение (75). Теорема 2 полностью доказана ?.
Подобно случаю с гладкой целевой функцией, теорема 2 устанавливает альтернансные свойства решений задачи (69), (2) в форме соотношений (75)-(77) при допущениях а1) — ^) более слабых и легче проверяемых по сравнению с типовыми, гарантирующими обладание точкой А0 свойством обобщенного альтернанса, которое наряду с этими соотношениями включает ряд дополнительных признаков [18−21].
Отметим в итоге, что для дальнейшей детализации альтернансных свойств решений рассматриваемых ЗПО, например, для существования чебышевского альтернанса [5−11] в одномерных задачах (69), (2) или (1), (2) при г=т=1 с заменой функций Р°(у, А) и Р (х, А) на их модули подобных допущений уже оказывается недостаточно. В частности, в этом случае необходимо, чтобы система функций
дР°(у, А°) дР°(у, А°) — дР (х, А°) дР (х, А°)
аА1 & quot-. "- дАп ' дА1 ,… дАп
являлась чебышевской (Т-системой) [5−11] на Ь1 хП1 для задачи (69), (2).
Соответствующие теоремы, формулирующие альтернансные свойства решений ЗПО в подобной ситуации, приведены в [17,29].
3. Анализ параметрических зависимостей решений ЗПО
Характер зависимости решений задач (1), (2) и (69), (2) от основного параметра е° в (2) устанавливает
Т е о р е м, а 3. При выполнении условий (3)-(6) или (70), (72), (73) зависимости А0(в0)
решений А° задачи (1), (2) или (69), (2) от е0 непрерывны справа по е0 в любой точке е° & gt- е
0
(n)
0 °min
(в любой точке e0 & gt-emin, если решение задачи существует при e0 = em^). Указанные зависимости непрерывны в тех точках s0, для которых рассматриваемые задачи имеют единственное решение.
Доказательство. Сначала рассмотрим задачу (1), (2). Пусть e = e0 +5e& gt-e|"П, |Se| - 0- А0 (e) — решение задачи (1), (2) с ограничением Ф (А) & lt- e вместо (2), и I (А0 (e)) = Imin (e).
Поскольку множество Лебега V© = {А е Gn: I (А) & lt- с}, с = const ограничено в условиях (3) [23], то в силу замкнутости Gn и непрерывности функции I (А) это множество компактно [9,23] и Imin (e) — конечная величина [9], что обеспечивает существование компактного подмножества G* с Gn, которому принадлежат все решения А0 (e) [5].
В силу компактности G* существует подпоследовательность {^0(e i)}е G*, e i =e 0 +5e i, |5e11 — 0, сходящаяся к некоторому элементу, А е G*.
Поскольку требование Ф (А) & lt- e = e'- заведомо удовлетворяется при выполнении неравенства Ф (А) & lt- e = e'-'-, если e'-'- & lt- e'-, то Imin (e) — невозрастающая функция e.
Если теперь А0^ г-) — А (1) при e г- - e 0 + 0, то из сказанного следует для непрерывной функции I (А)
lim01 (А0^ i)) = I (А (1)) & lt- I min (e 0),
ei ®e0 +0
откуда имеем, что I (А (1)) = Imin (e 0), А (1) = А0 (e 0), и значит,
lim А0(e) = А°^0),
e®e0 +0
т. е. зависимость А0(e) непрерывна справа в каждой точке e = e0 & gt- em^ в соответствии с утверждением теоремы 3.
e
0
Если решение задачи (1), (2) существует при e 0 =e, то полученный вывод распространяется на все e = e 0 & gt- e 00.
Далее, невозрастающая функция I min (e) непрерывна по e в точке e 0 при выполнении условия (6). Действительно, предположим противное, и пусть тогда в силу компактности G* имеем
А0^ i) — А (2) е G* при e i -- e 0 — 0, где А (2) ФА (1). При этом значения I (А (1)) и I (А (2)) ко-
нечны [9], функция I min (e) претерпевает в точке e 0 разрыв первого рода и I (А (2)) -1(А (1)) = I (А (2)) -1(А0^ 0)) = A & gt- 0, где A = const & lt-<-х>-, откуда следует, что
!(А00−5e)) -I (А0(e0)) = A1 & gt- 0, A1 — A при 5e — 0 (109)
для достаточно малого 5e & gt- 0.
С другой стороны, в силу (6) найдется такое направление S в Gn, ||S|| = 1, что
Ф (А0 (e0) + aS) = Ф (А0 (e0)) + a--(-(0)) + o (a) = e0 — 5e (110)
dS
при некотором малом a & gt- 0, для которого будем иметь
I (А0 (e 0) + aS) = I (А0 (e 0)) + a 8I (А 0)) + o (a), (111)
8S
8Ф (А0 (e 0)) 8I (А0(e 0)) S
где ------------ и--------------------соответствующие производные по направлению S.
8S 8S
Но тогда получим на основании (109)-(111), что I (А0 (e 0) + aS) & lt- I (А0 (e 0 — 5e)) в условиях Ф (А0^ 0) + aS) = e 0 -5e, что невозможно по определению А0(e 0 -5e). Полученное противоречие доказывает непрерывность функции Imin (e) в рассматриваемой точке.
В таком случае
Нш I (А° (е)) = I (А (2)) = 1хш I (А° (е)) = I (А (1)) = /т1П (е°)
?г не°-0 ег не° +0
и, следовательно, обе точки А (1) и А (2) являются решениями задачи (1), (2) при е = е °. Если теперь задача (1), (2) имеет единственное решение, то А (1) =А (2) = А°(е °) и, следовательно, функция А° (е) непрерывна в точке е = е °.
Сказанное завершает доказательство теоремы для задачи (1), (2), которое дословно сохраняется и для задачи (69), (2) после замены целевой функции I (А) на ^ (А) и условия (6) на неравенства (73), если иметь в виду, что для функции максимума ^ (А) сохраняется выражение вида (111) ?.
4. Вычислительные алгоритмы
4.1. Если выполняются допущения а1) — с1) теоремы 2, то, согласно ее утверждениям, для задачи (69), (2) при всех значениях е °: е ШП & lt-е ° & lt-е в (2) возникает следующая альтернатива
для суммарного числа Ях + Яу точек х °, у = 1, Ях- у°, V = 1, Яу, максимумов функций Р (х, А°) и Р° (у, А°), достигаемых на искомом решении А°: либо здесь, в соответствии с утверждением (75), искомая точка А° обладает альтернансным свойством Ях + Яу = п +1, либо в
случае, когда нарушается одно или оба неравенства (74), основное соотношение (75) не выполняется и
Ях + Яу = п1 & lt- п +1 при Ях = 1 или (и) Яу = 1. (112)
Рассмотрим сначала основной первый вариант.
Утверждение (75), дополненное условиями существования экстремума функций Р (х, А°) и Р°(у, А°) на От и Ьг в точках х°'- е0т°(А°), у° е 1! г (А°), принадлежащих
шЬ0 т и шЬ Ьг, приводит в условиях Ях + Яу = п +1 при заданном е° к определяющей системе
соотношений:
дР°(у°, А°)
Р°(у°°, А°) = Il (А0) — -----у-----= 0-
ду (113)
V = 1, Яу-? = 1, Я1У- Я1У? Яу- Уvg е (Уv }-
дР (х °, А°)
Р (х°, А°) = Ф (А°) = е°- ----------------------±-= 0,
У }& gt- & gt- У & gt- °& gt- дх ' (114)
у =1,Ях- р =1,Я1х- Я1х? Ях-х°}р е (х°°},
замкнутой относительно всех искомых параметров оптимальных решений задачи (69), (2).
При наличии дополнительной информации о характере распределения Р° (у, А°) на Ьг э у и Р (х, А°) на О т э х, позволяющей установить поведение этих функций и идентифицировать точки у° и ху, данные соотношения редуцируются к системе Н+Н1 уравнений с Н+Н1 неизвестными, где Н = Ях + Яу = п +1, Н1 = гЯ1у + тЯ1х, а в роли неизвестных фигурируют п составляющих А1], г = 1, п вектора А°- минимакс ^(А0) — гЯ1у координат Я1у точек у° экстремума Р°(у, А°) на Ьг и тЯ1х координат Я1х точек х °р экстремума Р (х, А°) на О т.
Решения такой системы уравнений относительно указанных неизвестных содержат решения задачи (69), (2) и могут быть найдены с помощью известных численных методов.
Подобным образом, при выполнении допущений (74) случай е ° = е Щ"П приводит в условиях Ях = п +1 к системе п + тЯ1х +1 уравнений (114) с п + тЯ1х +1 неизвестными А1], х ° и е ШП, а при е° & gt-е на основании (77) получаем для Яу = п + 1 систему п + гЯ1 у +1 уравнений (113) с п + гЯ1 у +1 неизвестными А°, у° и ^ (А°).
Для задачи (1), (2) с гладкой целевой функцией I (А) при выполнении всех допущений теоремы 1, включая условие Ях & gt- 2, утверждение (8) этой теоремы аналогичным образом определяет при Ях = п систему п + тЯ1х уравнений (114) с п + тЯ1х неизвестными А° и х ° для
(п)
заданного значения е ° & gt- е ШП.
Таким образом, при выполнении всех условий теорем 1 и 2 число Ях + Яу точек х° и у°, либо только Ях или Яу оказывается всегда достаточным для замыкания систем соотношений (113), (114) относительно всех искомых параметров.
4.2. В условиях (112) при Ях + Яу = п1 & lt- п +1, когда заведомо Ях = 1 или Яу = 1, в качестве дополнительных уравнений, замыкающих систему соотношений (113), (114) для решения задачи (69), (2) при еШ"П & lt-е° & lt-е, можно рассматривать общее необходимое условие экстремума с нетривиальными нормированными множителями Лагранжа 1 ^ & gt- 0 1 у & gt- 0, которое в соответствии с допущением (72) принимает следующий вид [1,2]:
Яу дР°(V0 А°) я, дР (х°, А°) —
0vдА, А) +^1 = °, г = 1, п- (115)
v=1 дА г у=1 дА г
Я у Ях
110v +11 у = 1. (116)
V=1 у=1
Тогда равенства (113)-(116) образуют в условиях (112) систему п1 + Н1 + п +1 соотношений, замкнутую относительно всех п1 + Н1 + п +1 неизвестных, в качестве которых в данном случае выступают п искомых параметров А°, г = 1, п- Н1 координат всех точек у° и х° экс-
тремума Р°(у, А) и Р (х, А) на! г и От — п1 множителей Лагранжа 1, V = 1, Яу-
, ] = 1, Ях и минимакс ^(А).
Если п1 = п, то достаточно дополнить (113)-(114) равенством нулю определителя системы
(115):
& quot-дР°(у°, А°) дР (х°°, А°)'-
дА. дА.
= °- (117)
V = 1, Яу- у = 1, Я, — Я, + Яу = п = п- г = 1, п,
понижая тем самым размерность систем уравнений путем исключения множителей Лагранжа из числа промежуточных неизвестных.
Аналогичным образом, если в задаче (69), (2) не выполняется требование (74) и для заданного е ° & gt- е имеем Яу = 1, то соответствующую замкнутую относительно п + г +1 неизвестных
А°, г координат точки у1° и ^ (А°) систему соотношений для наиболее простого случая, когда единственной точкой максимума у1° является точка экстремума Р° (у, А°), образуют г + 1 равенств (113) и п соотношений
дР°(у°, А°) —
-'- = °, г = 1, п, (118)
дА г
к которым редуцируются в этом случае условия (115).
Точно так же, если Ях = 1 в задаче (69), (2) при е ° = е Ш"П или в задаче (1), (2) при е0 & gt-еШП, то определяющая замкнутая система уравнений формируется из т + 1 равенств (114) и п соотношений вида (118) в единственной точке х° экстремума Р (х, А°):
дР (х°, А°) °. 1-
------------= 0, г = 1, п.
дАг
4.3. Описанный альтернансный метод решения ЗПО базируется на процедуре редукции соотношений (113)-(114) к соответствующей трансцендентной системе уравнений. Подобная процедура, вообще говоря, невыполнима априори однозначным образом при отсутствии дополнительной информации о характеристиках функций Р° (у, А°) и Р (х, А°). Этим, по-
видимому, и объясняется тот факт, что альтернансный метод (в форме так называемого & quot-выравнивания максимумов& quot- [15]) используется, как правило, лишь на заключительном этапе вычислительного процесса, когда за счет предварительного получения достаточно хорошего приближения к искомому решению численными методами оказывается известной конфигурация
распределения функций F0(у, А0) и F (x, А0) на Lr э у и Wm э x [15,21].
Принципиально иная ситуация складывается во многих прикладных ЗПО, знание предметной области которых часто позволяет априори получить содержательную информацию о конфигурации распределений F0(у, А0) и F (x, А0) на множествах Lr э у и Wm э x, по крайней мере, для некоторых характерных значений e 0 в (2). Для последующего перехода к заданным величинам e 0 во многих случаях может быть использована устанавливаемая теоремой 3 непрерывность зависимостей А0(е 0).
Отмеченные обстоятельства значительно упрощают процедуру редукции исходной задачи к решению соответствующих систем уравнений, которые приобретают ясный содержательный смысл применительно к каждой конкретной ситуации. В связи со сказанным подобный естественный путь построения вычислительной процедуры часто оказывается предпочтительным именно применительно к прикладным задачам конкретного физического или инженерного содержания, тем более, что соответствующий предметный анализ обычно позволяет найти достаточно хорошие начальные приближения для последующего эффективного решения расчетных систем уравнений стандартными методами. В работах [17, 30, 31] приводится большое число примеров, иллюстрирующих возможность применения описываемого метода решения ЗПО применительно к широкому кругу задач параметрической оптимизации нестационарных процессов тепло- и массопереноса и структурно-параметрического синтеза оптимальных систем автоматического управления.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Пшеничный Б. Н. Необходимые условия экстремума. М.: Наука, 1969.
2. Демьянов В. Ф., Малоземов В. Н. Введение в минимакс. М.: Наука, 1972.
3. Lecture notes in Economics and Mathematical Systems. Vol. 215. Semi-Infinite Programming and Application, A.V. Fiacco and K.O. Kortanеk, Eds. New York: Springer-Verlag, 1983.
4. Полак Э., Мейни Д. К., Стимлер Д. М. Применение методов полубесконечной оптимизации для синтеза систем автоматического управления: Обзор // ТИЭЭР. 1984. T. 72. № 12, С. 132−152.
5. Кларк Ф. Оптимизация и негладкий анализ. М.: Наука, 1988.
6. Березин И. С., ЖидковН.П. Методы вычислений. Т. 1. М.: Наука, 1966.
7. ДзядыкВ.К. Введение в теорию равномерного приближения функций полиномами. М.: Наука, 1977.
8. Даугавет И. К. Введение в теорию приближения функций Л.: ЛГУ, 1977.
9. Коллатц Л., КрабсВ. Теория приближений. Чебышевские приближения. М.: Наука, 1978.
10. Карлин С., Стадден В. Чебышевские системы и их применение в анализе и статистике. М.: Наука, 1976.
11. Пашковский С. Вычислительные применения многочленов и рядов Чебышева. М.: Наука, 1983.
12. Чебышев П. Л. Вопросы о наименьших величинах, связанные с приближенным представлением функций: Избр. тр. М.: АН СССР, 1955. С. 462−578.
13. Бернштейн С. Н. Экстремальные свойства полиномов и наилучшее приближение непрерывных функций одной вещественной переменной. М. -Л.: ОНТИ, 1937.
14. Ремез Е. Я. Основы численных методов чебышевского приближения. Киев: Наукова думка, 1969.
15. Малоземов В. Н. О выравнивании максимумов // Журн. вычислит. математ. и мат. физики. 1976. Т. 16. № 3. С. 781−784.
16. Бейко И. В., Бублик Б. Н., Зинько П. Н. Методы и алгоритмы решения задач оптимизации. Киев: Вища школа, 1983.
17. Рапопорт Э. Я. Альтернансные свойства оптимальных решений и вычислительные алгоритмы в задачах полубесконечной оптимизации управляемых систем // Изв. РАН. Теория и системы управления. 1996. № 4. С. 84−95.
18. Малоземов В. Н., Певный А. Б. Альтернансные свойства решений нелинейных минимаксных задач // Докл. АН СССР. 1973. Т. 212. № 1. С. 37−39.
19. Даугавет В. А., Малоземов В. Н. Альтернансные свойства решений нелинейных минимаксных задач с невыпуклыми ограничениями // Докл. АН СССР. 1975. Т. 225. № 2, С. 253−255.
20. Даугавет В. А. Альтернансные свойства решений нелинейных минимаксных задач с нелинейными ограничениями // Журн. вычислит. математ. и мат. физики. 1976. Т. 16. № 3. С. 784−788.
21. Вопросы теории и элементы программного обеспечения минимаксных задач / под ред. В. Ф. Демьянова и
В. Н. Малоземова. Л.: ЛГУ, 1977.
22. Рапопорт Э. Я. Чебышевские приближения в задачах параметрической оптимизации управляемых процессов. I. Необходимые условия оптимальности и вычислительные алгоритмы // А и Т. 1992. № 2. С. 60−67.
23. Васильев Ф. П. Численные методы решения экстремальных задач. М.: Наука, 1980.
24. ВоеводинВ.В., КузнецовЮ.А. Матрицы и вычисления. М.: Наука, 1984.
25. КолмогоровА.Н., Фомин С. В. Элементы теории функций и функционального анализа. М.: Наука, 1972.
26. АлексеевВ.М., ТихомировВ.М., Фомин С. В. Оптимальное управление. М.: Наука, 1979.
27. ЛюстерникЛ.А., СоболевВ.И. Краткий курс функционального анализа. М.: Высш. шк., 1982.
28. Васильев Ф. П. Методы решения экстремальных задач. М.: Наука, 1981.
29. Рапопорт Э. Я. Чебышевские приближения в задачах параметрической оптимизации управляемых процессов. II. Альтернансные свойсва оптимальных решений // А и Т. 1992. № 3. С. 59−64.
30. Рапопорт Э. Я. Оптимизация процессов индукционного нагрева металла. М.: Металлургия, 1993.
31. Рапопорт Э. Я. Параметрическая оптимизация систем автоматического управления по равномерно-частотным
критериям // Вестн. Самар. гос. техн. ун-та. Сер. & quot-Технические науки& quot-. 1998. Вып.5.
С. 13−27.

ПоказатьСвернуть
Заполнить форму текущей работой