Содержание к диссертации
Введение
Глава I. О существовании седловой точки в задаче квадратичного программирования в банаховом пространстве.. 19
I. Предварительные сведения. Обозначения 19
2. Теорема о существовании седловой точки 27
3. Условия Куна-Таккера для задачи квадратичного программирования 40
4. Эквивалентность условий Слейтера и сильной совместности при наличии внутренности конуса 45
4.1. Контрпримеры 48
Глава II. Вычислительный метод для задачи квадратично го программирования в пространстве [0, Т] 49
I. Сведение задачи квадратичного программирования к двойственной задаче 49
2. Описание метода и доказательство сходимости . 55
2.1. Пример 64
2.2. Описание программы 68
3. Регуляризация в задаче квадратичного программи рования 70
4. Случай матричных ограничений 74
Литература
- Теорема о существовании седловой точки
- Эквивалентность условий Слейтера и сильной совместности при наличии внутренности конуса
- Описание метода и доказательство сходимости
- Регуляризация в задаче квадратичного программи рования
Введение к работе
В 1939 году Л.В.Канторовичем был сформулирован ряд условно-экстремальных линейных задач экономического происхождения - задач линейного программирования, и указаны эффективные методы их решения. В дальнейшем в работах Г.Данцига и многих других авторов, как в нашей стране, так и за рубежом, теория линейного программирования получила широкое развитие (см., например Г16] , [40] ).
Следующим этапом в развитии теории математического программирования явилась разработка теории выпуклого программирования. Первая значительная работа в этом направлении принадлежит Г.Куну и А.Таккеру [46] . Теорема Іфна-Таккера дает необходимые условия для задач выпуклого программирования, а ее дифференциальная форма применима к задачам невыпуклого программирования в конечномерном пространстве и позволяет сформулировать необходимые условия для таких задач.
Уже в 50-х годах, наряду с работами по линейному и нелинейному программированию в конечномерных пространствах появились работы, посвященные задачам математического программирования в бесконечномерных пространствах. По-видимому, впервые такие задачи были рассмотрены Р.Беллманом [2] , но им рассматривалась не общая, а частная задача - так называемая задача на "узкие места".
Существует большое количество экономических задач, решение которых приводит к решению задач математического программирования в бесконечномерных пространствах. Приведем один пример.
mm 4 —
Задача Марковица о максимизации чистой прибыли [3} .
Пусть xi , хг , * Хп - объемы выпуска и видов продукции (в стоимостном выражении) в момент і на каком-то производстве. Часть величины Xf- , обозначаемая и- , идет на расширение производства, причем увеличение выпуска продукции в зависимости от размеров вложений дается соотношениями
- = X atjjfj , 0«у,-«*,- ,іжі,2,...,а
Требуется определить такую стратегию вложений, при которой прибыль за время Т будет максимальной, т.е.
п т
Z J(x.(i)-^(i))(U
Если х.д , Х20 , . . . , X Q - начальные объемы выпуска продукции, то задача может быть переписана в виде:
0 іє[о,Т],і~і.п
у(С*) >/ о
Эта задача является задачей линейного программирования в бесконечномерном пространстве.
Ряд обобщений результатов теории Куна-Таккера по линейному и нелинейному программированию в линейных топологических пространствах содержится в работе ГУрвица [із] . При выполнении условия Слейтера для задачи выпуклого программирования выводятся необходимые условия экстремума в форме существования седловой точки функции Лагранжа. Для задачи линейного программирования необходимые (и достаточные) условия экстремума в той же форме доказываются в предположении, что множество
регулярно выпукло. Здесь Т - линейное непрерывное преобразование линейного топологического пространства U/ , состоящего из пар ( о , х ) ( О - действительное число, х - элемент линейного топологического пространства X ), в топологическое пространство У х \)J s У (У - локально выпуклое линейное пространство), определенное соотношением
Т((р,х)) = (-j>6 +Ах , (р,х)) f
где элемент о и оператор А берутся из линейного ограничения задачи Ах > $
Далее ГУрвицем получены необходимые условия при условии регулярности оператора А в задаче минимизации функционала f(X) при ограничениях Ах >/О , где f - дифференцируемый по Фреше функционал, Д - дифференцируемый по Фреше оператор.
При условии, что конус, частично упорядочивающий пространство, имеет непустую внутренность, для задачи нелинейного программирования в банаховом пространстве в [49] получены необходимые условия экстремума при более слабых предположениях, чем регулярность оператора /\ и регулярная выпуклость множества Ш_ . В работе [49] используются некоторые определения и утверждения из [55] , а также применяется линейное непрерывное отображение
СГд , впервые введенное Л.Нейштадтом в [50] и [5l] : для каждого 2 є X существует линейный непрерывный оператор (г :
X —* У ( X и У *" банаховы пространства), такой, что
{im — — - Q. (x) для любого X Є X (І),
где /\ - непрерывный оператор, отображающий X в У .
Предположим еще, что для каждого І є X существует линейный непрерывный функционал f , определенный на X такой, что
fo+ep-fa) р
(im =f (X) для любого хє Л (2),
->0 г
у^х
где f - непрерывный функционал.
Если выпуклый конус К имеет! непустую внутренность и выполняются соотношения (I) и (2), то для задачи
min f(x)
Ax>,y0 (3),
хє Р
- 7 -где Р - произвольное множество X , следующая теорема, доказанная в [49] , дает необходимые условия минимума.
Теорема I. Если х - решение задачи (3), то существуют число Д и функционал U є У , не равные нулю одновременно, такие, что
V' ^2) + у*(АХ(*д У/ длялюбт: 2е^
А*»' 'У,Ф * для любых уе К,
где о - выпуклый конус, являющийся выпуклой аппроксимацией первого порядка, определенный Нейштадтом [50] .
Проверка выполнимости соотношений (I), (2), при которых доказывается теорема I, намного проще, чем соответствующие предположения іурвица tl3] .
В работе [24] В.Л.Левиным доказана так называемая обобщенная теорема о седловой точке для задачи линейного программирования в локально выпуклых пространствах:
{(х) -> тіп
Условие М (%0) означает соотношение
А"( Ку") = А"(Ку)
где Кц = {^ ' h >/0} + Ку ( Ку - неотрицательный конус). Теорема 2. Цусть Х0Е (X Ах>/^0 } >*0 = у0 - Ах0 и выполняется условие М(%0) . Для того, чтобы минимум функционала
f на множестве {х : А X У/ Ц0] достигался в точке XQ , необходимо и достаточно существование обобщенной последовательности { у у } функционалов уує У со следующими свойствами:
I А У\> I сходится к f в слабой топологии б*(Х, X) ;
yv Кц' Для всякого V ; ( /Су* - конус, сопряженный к Ку );
3) уu (2о)-0 для всякого V .
Если же, наряду с условием /И (н0) , выполняется и условие /V(Zp), заключающееся в слабой замкнутости множества
/ГР(20) (P(Z,)»tyKy'.- /CZ,)«0}) , то в [243 до-казывается теорема (теорема 2 ), дающая необходимые условия экстремума в форме существования седловой точки функции Лагранжа. Для задачи
f(x) -* min Ах >, у,
* п (5)
х >, о
в работе Гіз] выводятся необходимые условия минимума в форме су
ществования седловой точки функции Лагранжа при предположении,
что конус К имеет внутренние точки и выполняется условие Слей-
тера. Но при этих предположениях выполняются условия M(Z0) и
/1/(2р), для г0 = у0 - Ах0 , где Х0 - решение зада-
чи (5). А тогда применима теорема 2 , т.е. результат ГУрвица сразу следует из указанной теоремы.
Следовательно, В.Левиным установлено существование седловой
~ 9 ~ точки функции Лагранжа для задачи линейного программирования при более слабых предположениях, чем в fl3j .
В работе [30] , Б.Н.Пшеничным получены необходимые условия для задачи выпуклого программирования в банаховом пространстве, в формулировке которых используется понятие субдифференциала. В частности, в [ЗО3 показано, что результат ГУрвица совпадает с результатом применения к данной задаче теоремы Милютина-Дубовиц-кого о необходимых условиях в терминах непересечения конусов.
Е.Г.Голыптейном в [II] рассмотрены задачи выпуклого программирования без предположения о существовании у К внутренней точки, но основное внимание здесь уделено, в основном, формулировке теорем двойственности. Слабая форма критерия оптимальности (критерий оптимальности I) предполагает лишь соблюдение соотношения двойственности и поэтому имеет весьма широкий круг приложений.
Теорема 3. Пусть X s / X } - план ~ последовательность задачи выпуклого программирования
Sap fw
Ах* о (б)
X 7/0 .
Для того, чтобы X был решением задачи (6) при f(X)<0O ,
достаточно, а в случае соблюдения соотношения двойственности и
необходимо существование последовательности функционалов Л Єл
такой, что
tim [{(хк) + \(Ах*)] ^йт Suprf(x) + b*(Ax)]
K-+OQ К '
Если же помимо соблюдения соотношения двойственности, известно, что одним из решений двойственной задачи является некоторый план, то критерий оптимальности I может быть уточнен:
Критерий оптимальности П
Теорема 4. Пусть X а (х } ~ план-последовательность задачи (6) и г(Х) < оо . Для того, чтобы X был решением этой задачи достаточно, а в случае соблюдения соотношения двойственности и достижимости нижней грани в двойственной задаче на одном из ее планов необходимо существование функционала Л є К , такого, что
tin Л*(Ах*) = 0 .
К-»оо
К-+0О
В частности, если X «/" X } , т.е. решение X задачи является ее планом, то утверждение теоремы 4 переходит в
Л*(Ах) = о .
Теоремы двойственности, обеспечивающие не только совпадение экстремальных значений исходной и двойственной задач, но и достижимость нижней грани в двойственной задаче доказываются Голь-штейном в предположении соблюдения обобщенного условия Слейтера, впервые введенного автором. А это условие требует, в частности, чтобы конус К имел непустую внутренность.
В работе [17] Р.Дж.Даффин ввел понятие слабой совместности
- II -
для задач линейного программирования и доказал теоремы двойственности, которые являются, в основном, достаточными условиями экстремума.
Целью работы f56] К.Версана является построение правила абстрактных множителей в задачах с операторными ограничениями при Т : X *"* У (X - линейное пространство, У - линейное топологическое пространство). Эти правила дают возможность получить необходимые условия в форме принципа максимума в задачах оптимального управления с фазовыми ограничениями типа равенств.
Основным требованием при выводе правила абстрактных множителей (условие П теоремы 2 и теоремы 3 С36 3 ) является существование отображения А » удовлетворяющего системе функциональных неравенств. Однако метод доказательства этих теорем не позволяет дать удовлетворительных условий для построения такого отображения А в общем случае.
Для применения правила абстрактных множителей к задачам оптимального управления с фазовыми ограничениями типа равенств, К.Версан конструирует отображение весьма громоздким способом.
В работах [34-] и [35] , А.М.Тер-Крикоровым рассмотрены линейные и выпуклые задачи оптимального управления с фазовыми ограничениями. Эти задачи сведены им, соответственно, к задачам линейного и выпуклого программирования в банаховых пространствах. С применением результатов работы [13]эдля полученных задач математического программирования выписаны необходимые условия. Далее, переходя обратно к задачам оптимального управления с фазовыми ограничениями, А.М.Тер-Крикоров получил необходимые условия для этих задач в виде принципа максимума Понтрягина.
Что касается вычислительных методов для задач математического программирования, в настоящее время имеется огромное коли-
- 12 -чество работ в этом направлении (см., например [20] , [2.Z] , [23], [53 ] , [54-] ). Мы коснемся только некоторых работ по линейному и квадратичному программированию.
Многие методы решения задач квадратичного программирования в конечномерных пространствах ( [41] , [43] , [44] ) основываются в получении для этих задач условий Куна-Таккера - необходимых и достаточных условий в виде системы линейных равенств и неравенств. Для нахождения решения этой системы в свою очередь применяется симплекс-метод - универсальный метод для решения задач линейного программирования.
К сожалению, для задач квадратичного программирования в бесконечномерных пространствах этот путь неприемлем. Причина заключается в том, что аналога симплекс-метода для бесконечномерных задач не существует. В работе [47] сделана попытка построить непрерывный аналог симплекс-метода, но главный интерес в этой работе представляет анализ многочисленных трудностей и выяснение причин, из-за которых такой аналог не может быть построен.
На первый взгляд наиболее простой способ решения бесконечномерной задачи математического программирования состоит в ее аппроксимации конечномерными задачами. Недостатком такого подхода является жесткость условий, при которых доказывается сходимость последовательности приближенных решений к оптимальному решению исходной задачи.
В работе [53] В.Тиндалом рассмотрена задача максимизации линейного функционала Г
- ІЗ -
*^
2(0 ?sO
и при условиях - І) /Я Є Е : 5X^0 ,Х>,о) = {0} 2) матрицы S , С и вектор с() имеют неотрицательные компоненты, - доказана теорема существования решения задачи (7),(8) и двойственной задачи.
Работа Тиндала интересна тем, что доказательство вышеуказанной теоремы является конструктивным. Сначала задача (7), (8) и двойственная задача аппроксимируются конечномерными задачами линейного программирования и затем доказывается сходимость последовательности решений аппроксимирующих задач к решению задачи (7), (8).
Представляется интересным метод, предложенный в работе [2.8] . Он разработан для специального класса задач - для так называемых 5* - задач. В частности, к таким задачам приводится задача оптимального управления процессом нефтедобычи в упругом режиме и вышеприведенная задача Марковича о максимизации чистой прибыли. Специфика задачи в данной работе позволяет ввести такие понятия, как опорный план, базис, и предложить некоторый аналог симплекс метода.
В работе [Ю] вопросы конечномерной аппроксимации задач линейного программирования с операторными ограничениями исследовались с привлечением аппарата двойственности и изучалась аппроксимация двух типов: пространственная аппроксимация, заключающаяся в сужении пространства допустимых элементов до конечномерного и пара-
- 14 -метрическая, в которой аппроксимируются параметры исходной задачи.
Прямой подход к этой проблеме предложен в Г 9] , где рассмотрены задачи линейного и выпуклого программирования в банаховом пространстве. Здесь рассмотренные задачи непосредственно заменяются конечномерными задачами и, если пары, составленные из параметров конечномерных и бесконечномерной задач дискретно слабо непрерывны, доказывается сходимость последовательности оптимальных значений конечномерных задач к оптимальному значению бесконечномерной задачи. Следует отметить, что в теореме о сходимости кроме, в общем-то, естественного, условия Слейтера требуется не только существование решений конечномерных и бесконечномерных задач, но и равномерная ограниченность множества решений конечномерных задач, что является весьма обременительным.
Настоящая работа посвящена выводу необходимых условий в форме существования седловой точки функции Лагранжа и разработке на их основе метода для решения задачи квадратичного программирования в пространстве L2 f 0, Т] .
Диссертация состоит из двух глав.
В I первой главы приведены некоторые обозначения и факты, необходимые для дальнейшего изложения.
Как отмечено выше, во многих работах для получения необходимых условий в виде существования седловых точек функций Лагранжа требуется выполнение условия Слейтера. А для выполнения этого условия необходимо наличие внутренности у конуса, частично упорядочивающего пространство. Но, как известно, во многих важных пространствах конусы, определяющие соотношение порядка, не обладают внутренностью. К этим пространствам относятся, например, пространства [п и ip(i
В 2 первой главы рассматривается задача минимизации выпук-
- 15 -лого функционала в банаховом пространстве при линейных операторных ограничениях, причем конус, частично упорядочивающий пространство, может не иметь внутренних точек. В этом случае об условии Слейтера не может идти речь и поэтому вводится условие сильной совместности, заключающееся в следующем: существует некоторая окрестность правой части ограничений, для каждой точки которой данные ограничения совместны.
При условии сильной совместности доказана теорема, в которой устанавливается необходимое и достаточное условие в виде существования седловой точки функции Лагранжа. Достаточность в этой теореме, как известно, справедлива и без условия сильной совместности. В работе она доказана для полноты изложения.
Из доказанной теоремы, в частности, получается утверждение теоремы 4.2 работы Г28] .
В 3 первой главы рассмотрена задача квадратичного программирования в гильбертовом пространстве. При выполнении условия сильной совместности, для этой задачи выписаны так называемые условия Куна-Таккера, т.е. необходимые и достаточные условия оптимальности в виде системы линейных равенств и неравенств и условий дополняющий нежесткости. Полученные условия являются аналогом условий Куна-Таккера для задачи квадратичного программирования в конечномерных пространствах.
4 первой главы посвящен изучению связи между условием Слейтера и условием сильной совместности. Показано, что в случае когда внутренность частично упорядочивающего конуса непуста, условия Слейтера и сильной совместности эквивалентны. При доказательстве используется теорема отделимости для выпуклых множеств.
Во второй главе предложен вычислительный метод для решения задачи квадратичного программирования в пространстве L Ґ0, Т] -
- пространстве вектор-функций, каждая компонента которых интегри~ руема с квадратом на отрезке f 0 > Г J .
В I второй главы рассматривается задача квадратичного программирования, в которой функционал сильно выпуклый. С использованием результатов первой главы эта задача сводится к задаче минимизации квадратичного функционала при более простых ограничениях, а именно при неотрицательности переменных.
функционал в полученной задаче будет выпуклым, но может не быть сильно выпуклым.
Предполагается, что в каждой строке матрицы операторов в ограничениях первоначальной задачи существует оператор, имеющий ограниченный обратный. При этом предположении показано, что диагональные элементы матрицы в полученном квадратичном функционале являются положительно определенными операторами.
В 2 второй главы дается вычислительный метод для решения полученной в I задачи - задачи минимизации квадратичного функ-ционала при неотрицательных переменных в пространстве / [0,1]. Метод напоминает метод покоординатного спуска при данных ограничениях, но здесь на каждом шагу приходится решать задачу квадратичного программирования с сильно выпуклым функционалом в пространстве L«[О, Т] .
При доказательстве сходимости существенно используются некоторые свойства сильно выпуклых функционалов.
Метод, предложенный в 2, применим при условии положительной определенности оператора С в квадратичном функционале
У(Х) = (*, Сх) + С/1, X) . Но во многих задачах С является всего лишь неотрицательным оператором (для любого X,(х,Сх)>,0), т.е. функционал У(х) является выпуклым, но не сильно выпуклым.
В 3 второй главы осуществляется регуляризация функционала
J(X) =і(х,Сх) 4 (р->х) ( С - неотрицательный оператор)
и тем самым функционал превращается в сильно выпуклый. И тогда к полученной регуляризованной задаче можно применить результаты 1-го и 2-го параграфов данной главы.
Доказана теорема о сходимости.
в 4 второй главы метод, предложенный в 2, применяется к
частному случаю - к задаче квадратичного программирования
Т Т
f(x(4),C(i)x«))d{ +f(/i(4)9x(4))cH -+min
о о
A(4)x(4)*fa4) у о 4.4*т ,
где С(4) и Ш , соответственно пхп и tnxfl - матрицы с ограниченными измеримыми компонентами.
В этом случае реализация метода существенно упрощается. Причина заключается в том, что при определении итераций на каждом шаге минимизируется квадратичная функция на положительной полуоси и поэтому компоненты итераций легко получаются по рекуррентным формулам.
В заключение отметим, что многие линейные задачи оптимального управления со смешанными ограничениями и с квадратичным критерием качества сводятся к задачам квадратичного программирования в бесконечномерных пространствах (см., например, 16] , [361 ). Рассмотрим одну из этих задач.
Задача I. Найти управления И(4) є L» Г0, Т] , минимизирующее квадратичный функционал
J(u)*f(x(4)tR(4)xii))cl4 (9)
- 18 -при следующих ограничениях:
^-;= Ш)ХСІ) +Rti)U(4) 4Р(Ь (Ю)
Х(0) *XD , ucbw (И)
С({)хсЬ і Я&)и№ * Ш (12)
Матрицы $({) , АФ , В (4) , С({) и ЗГСО
, и векторы
Q(4) и 6СО имеют ограниченные измеримые компоненты. Соответствующие матрицы и векторы имеют следующие размеры: R [ П х п ] ,
/I f л х/|] , Е>сп*т] , С/^гхл] , 3/"гх/??з , ar/?7 , /*sj .
- самосопряженная матрица. Нетрудно видеть, что решение задачи (10), (II) есть
X(t)=M(bu + a) +F(t)x0 (ІЗ)
где Mf ~F(i)f F4(r) fCDd* , a fCif) - фундаментальная
і) матрица
^ =/1 COW) , /W*Z or
Подставив выражение я (О из (12) в (9) и (II) получим
У(и) * (u,B'M*RM(Bu))*2(B'M*R(M(o) + Fx0 ,и) <о СМ(Ви)+%4 &-CM(a)~Fxn , и>0
т.
где ( ) означает скалярное произведение в /.. СО, Т ] , оС -постоянное число. Эта задача является задачей квадратичного программирования в гильбертовом пространстве.
Нумерация параграфов идет по главам, нумерация формул и теорем по параграфам с указанием номера параграфа. При ссылке из одной главы в другую указывается номер главы и номер формулы или теоремы, а при ссылке на формулу или теорему той же главы, номер главы не указывается.
Теорема о существовании седловой точки
Как уже отмечалось, в большинстве случаев для существования седловой точки в задачах выпуклого программирования требуется выполнение условия Слейтера.
Для этого необходимо наличие внутренности у конуса, частично упорядочивающего пространство.
В случае же, когда внутренность конуса пуста, условие Слейтера невыполнимо. В этом параграфе доказана теорема о существовании седловой точки функции Лагранжа в случае, когда внутренность конуса пуста. При этом предполагается выполнение так называемого условия сильной совместности.
Пусть X к о банаховы пространства, частично упорядоченные выпуклыми и замкнутыми конусами К и г , соответственно. Рассмотрим задачу минимизации выпуклого функционала У(х) при ограничениях Ах $ X ,0 . Здесь А линейный ограниченный оператор, отображающий пространство X в У .
Соотношение Ах4- 6 означает, что X s0 означает, что Х К . Условимся записать данную задачу в следующем кратком виде. У(х) win
Напомним, что ограничения (2.2) называются совместными, если существует такой элемент XQ пространства X , что Ах0 6 Определение 2.1. Ограничения (2.2) будем называть сильно совместными, если существует такое действительное число о 0 , что для любого о из множества В ={6єУ i6-6t et} , ограничения Ах І X ЪО совместны.
Определение 2.2. Точка Х0 линейного пространства Z называется С - внутренней точкой множества L тогда и только тогда, когда для любой точки 2 Z , зЬ ф0 существует такое действительное число Л , 0 А 1 , что все точки У = Х0 -/- Д 2 , 0 Л Л принадлежат множеству Докажем следующую лемму. имеет непустую С - внутренность.
Доказательство. Для доказательства леммы достаточно показать, что нулевой элемент принадлежит С - внутренности множества М , т.е. для любого 2 є У і отличного от нуля, существует такое действительное число Д , 0 )І 1 , что условия О- НХ ъ, \ Н X ,0 совместны для любого Л t 0 Л Л «По условию сильной совместности существует такое действительное число 80 0 » что для любого є У удовлетворяющего неравенству И 6 - в II $ 0 совместны условия Ах w X /0 . Возьмем любой элемент 2 є У , 2 ф О о Если , если же sf » 0 / , выберем//г// " та //г// то можно выбрать любое 0 } 1 . Тогда для любого А , О "X имеем А //2// Следовательно II/12-11 0 , т.е. совместны ограничения для любого X у 0 } Д Лемма доказана.
Докажем теперь лемму, являющейся основной для доказательства теоремы о существовании седловой точки функции Лагранжа - основного результата данного параграфа. Лемма 2.2. Если ограничения (2.2) сильно совместны, то множество имеет непустую С - внутренность. Доказательство. По условию, существует X ЪО такое, что ё-Ах ,о Покажем, что, например, (0, У(% ) +0 является С - внутренней точкой. Обозначим р0 = У(х)
Достаточно показать, что для любого (2,р)є У х R существует й такое, что ( А 2 , Р +%р) Є S для всех Л , 0 А А , т.е. для любого Є(ОУ)І) существует #) 0 такое, что Так как нулевой элемент является С - внутренней точкой множества /Ц (лемма 2.1), то существуют действительное число 0 А 1 , и элемент X s 0 такие, что о Теперь докажем теорему о седловой точке.
Теорема 2.1. Предположим, что ограничения (2.2) сильно сов местны. Тогда для того, чтобы точка Х є X была решением задачи (2.1), (2.2), необходимо и достаточно существование линейного функционала 2 є У » 2„ /0 такого, что пара Хп , 2Л является седловой точкой функции Лагранжа.
Достаточность. Пусть пара «, 2 является седловой точкой функции Лагранжа, т.е. удовлетворяется соотношение (2.3). Из левой части соотношения (2.3) следует (i .Ax-g) (г Ахг ) для любого 2- , 0 (2.4). Тогда для любого 2 /0 {г .Ах,-6) о (2.5) так как в противном случае левую часть соотношения (2.4) можно было бы сделать сколь угодно большой.
Поскольку соотношение (2.5) имеет место для любого 2 ,0 » то пХ04 0, т.е. СС0 является допустимым элементом.
Эквивалентность условий Слейтера и сильной совместности при наличии внутренности конуса
В 2 была доказана теорема о седловой точке функции Лагранжа при условии сильной совместности. В случае, когда конус Р обладает непустой внутренностью в [13] доказана такая же теорема (теорема 5.3.1) при условии Слейтера. (Напомним, что условие Слейтера выполняется тогда и только тогда, когда существует такой элемент ,о » что 6- Ах0 є іniP ). Поэтому представляется важным исследование связи между условиями Слейтера и сильной совместности. Оказывается, справедлива следующая
Теорема 4.1. Пусть конус Р имеет непустую внутренность. Тогда условие Слейтера и условие сильной совместности эквивалентны.
Доказательство. Пусть выполняется условие Слейтера. Тогда существует такое действительное число Р , что о Лхо +РЧ 0 для любых и , II У II 1 » Это означает, что для любого т.е. имеет место условие сильной совместности. Теперь пусть имеет место условие сильной совместности. Тогда для любого и , II Ц Ц 1 » существует такой X ъ 0 , что
В пространстве У шар с центром в нуле и радиусом о обозначим через S р .
Следующие примеры показывают, что существует достаточно широкий класс задач ограничения которых сильно совместны, но для них условия Слейтера не выполняются (так как конус, определяющий частичный порядок, не имеет внутренних точек).
1. Рассмотрим в пространстве / Г0,Т] множество элементов, удовлетворяющих ограничению і 0ССІ) -± fxCTldt S(i) (4Л) о В этом примере конус К совпадает со всем пространством, Р L [0,J] (/.ГО,ТІ - конус почти везде неотрицательных функций). Так как Р не имеет внутренних точек, об условии Слейтера не может идти речь. Однако для любой оСО Є і2Г05Т] существует () удовлетворяющая (4.1). (По крайней мере решения уравнения Вольтерра удовлетворяет неравенству (4.1)).
2. Очевидно, что условие сильной совместности эквивалентно следующему соотношению: і є ft (АК+Р) Даже при Р , имеющем пустую внутренность, /\ и К можно выбрать так, чтобы f\K +г имел непустую внутренность и тем самым можно выбрать 6 так, что имеет место условие сильной совместности.
Как известно, существует большое количество методов для решения задач квадратичного программирования в конечномерных пространствах. Многие из них основаны на следующей идее:
Для задачи квадратичного программирования выписываются уело вия Куна-Таккера - система линейных равенств и неравенств и так называемые условия дополняющей нежесткости. Эти условия допол-няющей нежесткости позволяют для решения системы равенств и неравенств применить симплекс-метод - универсальный метод для решения задач линейного программирования в конечномерных пространствах.
К сожалению, для задач линейного программирования в бесконечномерных пространствах не существует аналога симплекс-метода. Поэтому воспользоваться вышеуказанной идеей не представляется возможным.
В данной главе предлагается метод для решения задачи квадратичного программирования в пространстве L [О ,Т] . С помощью условий Куна-Таккера задача приводится к минимизации квадратичного функционала при неотрицательных переменных и затем решается полученная задача.
Описание метода и доказательство сходимости
Очевидно, что соотношения (2.II), (2.12) вместе с условием U У/0 являются условиями Цуна-Таккера для задачи (I.I3), (I.I4). Следовательно и - решение задачи (I.I3), (I.I4). Таким образом, мы показали, что f(@8) s (&) тогда и только тогда, когда U - решение задачи (І.ІЗ), (I.I4). Последовательность (и J ,получающаяся последовательным применением оператора R к U » , и т.д. является под последовательностью последовательности f 9 / » гДе - и » СР) СР-0 а О г получается от о г после одного координатного спуска. Так как f(u) - сильно выпуклый функционал по U; , справедливо следующее неравенство (см.теорему I.I.6);
Здесь Y - положительное действительное число, при котором для любого ХЄ 1П2Ї0,ТІ , (Х,СХ) fllXll2 , a /. положительные числа, фигурирующие в предположении 1.2. f(Q,W) монотонно убывающая и ограниченная снизу последовательность. (Ограниченность снизу следует из существования решения задачи (І.ІЗ), (I.I4), которое в свою очередь следует из существования решения задачи (1.3), (1.4)).
Следовательно, она сходится. Из соотношения (2.13) следует, что сходится и последовательность О(Р . Так как U являет ся подпоследовательностью последовательности Q r , то и СЮ также сходится. Предел U обозначим через U . Докажем, что U - решение задачи (І.ІЗ), (I.I4). Из непрерывности f(W) следует, что Далее, поскольку R непрерывный оператор, то С О СЮ г ср(и ) = у (/? / ; f(Pu ) . С другой стороны, (к+О . Из единственности предела следует, что - 63 f(u ) = f(Ru ) . А это равенство, как мы показали, является необходимым и доста-точным условием для того, чтобы U был решением задачи (I.I3), (I.I4). Теорема доказана. Как мы уже отметили, для нахождения каждой компоненты каждой итерации необходимо минимизировать f(W) по U: при U /0 Для этой цели займемся решением задачи следующего вида: (г,бг) +( Л2) - ruin (2.14) ? 0 . (2Л5) Здесь 8 - положительно определенный самосопряженный ограничен ный оператор, действующий из L tO l в L2 LO,TJ 9 deL2[o,Tl . Для любого хє L2[0,j] (х,5х) ,оС IIXI/2, ос 0 . Если 2 решение задачи (2.14), (2.15), то оно удовлетворяет следующему соотношению: Z = max {о, 2 -Ъ(2В +с1)1 , Ъ о . (2.16) Для решения задачи (2.14), (2.15) предлагается следующий - 64 алгоритм. (0) (к+О Выбираем начальное ,0 , 2 определяется по формуле Z =тах{о,ъ -Л (2 Bz +d)J , (2.17) Интересно отметить, что А остается постоянным для всех к и находится из оценки, приводимой ниже
Программа, составленная на алгоритмическом языке ФОРТРАН, состоит из головной программы, подпрограммы-функции FI и Oi/I//. Подпрограмма-функция FI составлена для вычисления значения целевой функции (P(U) и эти значения выдаются на головную программу и на печать. Подпрограмма-функция SIN Т составлена для вычисления интегралов, фигурирующих в данной задаче.
Для максимального избежания погрешностей при вычислении, здесь используется 3 разных типа формулы интегрирования и программа-функция в зависимости от шага и длины интегрирования автоматически вычисляет интегралы с большей точностью и передает в головную программу.
Головная программа работает таким образом: Вводится (С І ПО 10) используемые данные и описываются параметры. 2. Вычисляются интегралы и выражения и + а (с 15 по 26). 3. На основании формулы (2.22) вычисляется Щ (с 27 по 33). р 4. Вычисляется выражение!/ \(ц - Uf ) , выдается на пе о чать и если это значение больше S (где заранее заданное 5. Вычисляются интегралы и выражение для BnU +d2 ( 50 значение), то переход к 2 (с 34 по 48). 5. ] по 61). 6. На основании формулы (2.23) вычисляется (/„ (с 62 по 68). 7. Вычисляется выражение Л/ J (uS - U )2 , выдается на печать и если это значение больше , то переход на 5, в противном случае, к 8, (с 69 по 83). 8. С помощью обращения на подпрограмму-функцию pi , вычисляется S I Cui(1\u2h (uilu20))l (с 84 по 85) и выдается на печать. 9. Если $ (заранее заданное значение), выдается на печать пара (и , lf2 ) и (U у U2 , в противном случае переход на I уже для новых начальных значений (ltf , U2 ) (с 86 по 89). 10. Вычисляются выражения для Xt(p) и Х2&) , старые и новые значения выдаются на печать (с 91 по 103). 11. Вычисляется выражение Л / /у со (о)А / W х(0))г и выдается на печать.
Регуляризация в задаче квадратичного программи рования
Итак, если известно, что задача (3.1), (3.2) имеет решение X и мы хотим для ее решения применить метод, предложенный в 2, то поступаем следующим образом: выбираем последовательность Ы 0 » стремящуюся к нулю при К - оо и рассматриваем задачу %[ (х) = ( Сх) + oLK (оеуХ) + (/і, X) - win (3.3) Ах 6 . (3.4)
Допустим, что имеют место предположение І.І и предположение 1.2. Если выписать условия Куна-Таккера для задачи (3.3), (3.4), получим следующие соотношения: - 73 2.(oL 1 + C)x +JI +Д U =0 (3.6) Ax +4 =& (3.7) (У Ю = 0 (3.8) У / 0 , U s 0 . (3.9)
Так как oCKl +C положительно определенный оператор &Х,( ХК1+С)х) Ъ&КЦХЦ2) ТО 0CKI +С имеет обратный оператор. Тогда из соотношения (З.б) X можно выразить через U . х =--( I + C) (Au+/i) . (зло) Подставив это выражение в (3.7) получим условия Куна-Таккера ijK ,o ,и /0 для задачи у до =(u,GKv) +(hK,ii)- win (злі) - 74 U- sO , (3.12) где еки -lAfal+cy Al., /iK.±A( KUCfp. 4 .
Теперь выберем последовательность Ї] так, что у 0 г1к- 0 при К -» оо . Очевидно, что применяя метод, предложенный в 2, при каждом К можно получить такой UK и (подстановкой его в (ЗЛО)) такой хк , что Уос„ J«J K) K ЧК По теореме 3.1, Хк будет минимизирующей последовательностью для функционала (3.1) при ограничениях (3.2). Таким образом, если известно существование решения для задачи (3.1), (3.2), посредством регуляризации получаем минимизирующую последовательность.
В случае, когда в задаче (1.3), (1.4) А и С являются матрицами, численная реализация метода, предложенного в 2 значительно упрощается. Это связано с тем, что при нахождении компонент следующей итерации не приходится решать задачу квадратичного программирования на каждом щаге. Эти компоненты вычисляются непосредственно.
Рассмотрим следующую задачу: Здесь матрицы cm и /im , соответственно п х п и /7) X /7 - матрицы с ограниченными измеримыми компонентами, [l(i) Є I"[О, Т] , (і)І»Г0,Т] ,( ) озна-чает скалярное произведение векторов. В настоящем параграфе выполнение всех равенств и неравенств требуется для почти всех і из [О, Т] Решение ищется в пространстве Z2 7"J Будем предполагать, что в каждой строке матрицы Д(«)хотя бы одна компонента не превращается в нуль почти всюду в [О, Т] . Далее, предположим, что С(4) - положительно определенная матрица почти при всех г Є [О, Т] . И, наконец, пусть существует такое действительное число D 0 , что для всех 4() » IIУ (till 41 , ограничения А#)Х&) 6( )-о9& совместны.
Легко видеть, что последнее предположение ни что иное, как условие сильной совместности. Поэтому, для задачи (3.1), (3.2) можно выписать условия Іфна-Таккера, которые имеют следующий вид: ; 2С(4)х(і) ІfiCti + А Ctiucti =D (4#3) A(i)X(t) +yfo = 6(i) (4.4) tfCt) 0, U(t) 0 (4.6) / где п Of) - матрица транспонирования.
Так как С (+) почти всюду положительно определенная матрица, то уравнение(3.3) можно разрешить относительно X(t) . зс$)ш-1 с foft #м - /if Jj . (4.7) Подстановкой этого выражения ОС (4) в (3.4), условия Куна-Таккера принимают следующий вид: 2G(i)U(i) +Ш) =у(+) (4.8) ($(4), (4))=0 (4.9) yQf) o , г/СО о , (4.Ю) где є&) ±№сюл(4), kv-A(W(:t)/i(v+fa). Покажем, что ею неотрицательная матрица, т.е. для - 77 любого U (і) , (і/(О ,5 СО UСі)) /0 почти для всех І Є [0,Т] .
Действительно = ±f/l(t)U(+),C h)/l(i)u(V) /D . С другой стороны ясно, что (0 может не быть положительно определенной матрицей. Однако ее диагональные элементы Qfi(i) положительны почти при всех ІЄ[0,Т] . Действительно, так как С ft) положительно определенная матрица, то fa. (О = (&,.(«, c ( )at-(U) о . Здесь tf/ft) 1-я строка матрицы л ft) Нетрудно видеть, что условия (4.8)-(4.10) являются условиями Куна-Таккера для задачи Г Т f(u) = Дне ), ft)wft))Л +f(h(t),и(4)) min (4 п) о о U /0 . (4Л2) Итак, решая задачу (4.II), (4.12), тем самым мы решим задачу (4.1), (4.2).
Для решения задачи (4.II), (4.12) применяется метод,предложенный в 2. Однако решение в данном случае существенно упрощается из-за того, что С (г) и /4ft) не операторы, а матри -течи. Решение задачи (4.II), (4.12) начинается с произвольной У ЮъО . Компоненты следующей итерации U определяются последовательно в результате минимизации f(tt) по каждой компоненте К і при Ui /0 . При этом остальные компоненты сохраняют значения полученные в последний раз. Также получаются Lf » и и т.д. Задача минимизации if (и) по Щ (Щ /0) при фиксированных остальных компонентах является задачей следующего типа: (Ю =foc(t)z2a)dt +/eft) C« + Г - МІ» (4.13) о oJ Z(t) sO . (4.14) Здесь ot(i) и В (і) скалярные ограниченные измеримые функции, /г - постоянное число, оС(і) 0 почти везде вГ0,Т]. Решение задачи (4.13), (4.14) легко получить, если функционал видоизменить следующим образом: т т т о о 0 о О ш 79 -Множество [О, Т] разобьем на два подмножества Тогда из (4.15) нетрудно видеть, что решение задачи (4.13),(4.14) имеет вид: Г 0 при і Є Е, 2(0 Н fi(i) 7ї«) ПРИ U Е2 Принимая во внимание вышеизложенное, легко можно заключить, что при решении задачи (4.II), (4.12) компоненты К +f - й ите-рации U - (tv получаются по формулам: (к+0 (к+0 . U{ iir) „ IDQX (0 ШІ (і) J (4.16) cw; w сад A,/# Л f« \ Wi Шф Р№ СІ Т%9 ») (4.17) Доказательство сходимости аналогично доказательству в 2. Таким образом, в случае матричных ограничений метод оказывается удобным с вычислительной точки зрения.
