Несобственные задачи оптимизации, методы их оптимальной коррекции и приложения тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им. С.Л.СОБОЛЕВА

г Г ОД-:-

! П ФЕЗ !П07

На правах рукописи УДК 519.6

ПОПОВ Леонид Денисович

НЕСОБСТВЕННЫЕ ЗАДАЧИ ОПТИМИЗАЦИИ, МЕТОДЫ ИХ ОПТИМАЛЬНОЙ КОРРЕКЦИИ И ПРИЛОЖЕНИЯ

(01.01.09 — математическая кибернетика)

Авторефереат диссертации на соискание ученой степени доктора физико-математических наук

Новосибирск-1997

Работа выполнена в Институте математики и механики УрО РАН.

Официальные оппоненты: доктор физ.-мат.наук

доцент А.А.Колоколов, доктор физ.-мат.наук профессор А.Г.Ченцов, доктор физ.-мат.наук профессор В.И.Шмырев.

Ведущая организация: Вычислительный центр РАН.

,___- * , х- ¿"

Защита состоится " О " —_ 1997 г. в 6

часов на заседании специализированного совета Д 002.23.03 в Институте математики Сибирского отделения РАН по адресу: 630090 Новосибирск, Университетский проспект, 4, Институт математики СО РАН.

С диссертацией можно познакомиться в библиотеке Института математики СО РАН.

Автореферат разослан

1997 г.

Ученый секретарь специализированного совета доктор физ.-мат.наук

А. В. КОСТОЧКА

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Направление в теории условной оптимизации, иучающее несобственные (не удовлетворяющие основным соотношениям 1войственности) задачи математического программирования (МП), появи-юсь в начале 80-х годов и имеет своим истоком работы И.И.Еремина, Зл.Д.Мазурова. 1 В случае линейного программирования (ЛП) несоб-;твенность задачи означает несовместность системы ограничении у пря-лой, или двойственной, или у той и другой задачи одновременно (соответственно говорят о несобственности 1-го, 2-го или 3-го рода).

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

Использование противоречивых моделей позволяет обеспечить большую гибкость и адекватность моделирования, дает возможность улучшить ;го адаптацию к требованиям практики. При поиске адекватной модели чожет оказаться целесообразным идти от варианта собственной модели I несобственной за счет включения в модель не учитывавшихся ранее эграничений, а также всевозможных внешних и внутренних требований, эбязательных или желательных в той или иной мере для выполнения, а эт последней - уже к собственной, но на основе объективных процедур коррекции.

Важнейшими направлениями в проблематике несобственных задач (113) MII стали исследования по теории двойственности и методам оптимальной

'Еремин H.H., Мазуров В.Д. Нестационарные процессы математического программирования. - М.: Наука, 1979.

Еремин H.H., Мазуров В.Д., Астафьев H.H. Несобственные задачи линейного и выпуклого программирования. - М.: Наука, 1983.

премии U.U. ДиоЛс гнойноеи> для mvoiv шейных, .»лдлч линейной4 и г-к-пуклого программирования // ДАН СССР. -1981. -Т.256. №2. -С.272-276.

коррекции для таких задач. Основная идея новой двойственности состоит в том, что исходной несобственной паре двойственных задач С а С* ставятся в соответствие определенным образом формируемые собственные задачи D и , связанные соотношениями двойственности друг с другом и в то же время определенным образом связанные с некоторыми параметрическими задачами С(6) и С* (б), выступающими в роли задач, аппроксимирующих исходные. С этими идеями тесно связан и принцип оптимальной коррекции (аппроксимации) несобственной задачи С, который предполагает согласовывать выбор в параметрическом семействе С{6) собственных представителей с дополнительным условием минимизации (максимизации) некоторой функции от 6 , трактуемой как критерий качества коррекции (аппроксимации). Этот критерий, впрочем, может иметь и более сложную структуру.

В настоящее время по теории и методам для НЗМП и их приложениям опубликован ряд монографий, обзоров, сборников статей, защищено несколько кандидатских и докторских диссертаций (В.Н.Фролов, П.Г.Романий, А.А.Ватолин). Работы И.И.Еремина (и Вл.Д.Мазурова) и его учеников (Н.Н.Астафьев, А.А.Ватолин, Л.Д.Попов, С.В.Плотников, В.Д.Скарин, С.П.Трофимов, В.Н.Фролов и др.) послужили стимулом к интенсификации исследований в этом направлении других авторов (В.А.Бу-лавский, А.И.Вересков, М.М.Ковалев, П.Г.Романий, М.Е.Салуквадзе, А.Л.Топчишвили, Н.В.Третьяков), в том числе зарубежных (R.Baumgart, К.Beer, J.N.Burke, H.J.Greenberg, O.L.Mangasarian, I.Marusciac и др.). Библиография по этой теме насчитывает более трехсот пятидесяти работ.

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

Исторически вариационные неравенства и задачи о дополнительности появились в работах Ф.Хартмана, Дж.Стампаччи, Р.Коттла, Дж.Хабетле-ра, С.Лемке. В настоящее время эта проблематика превратилась за рубежом в жизнеспособную и плодотворную область исследований. Это объ-

[сняется по крайней мере тремя крупными научно-прикладными собы-•иями. Первое - это развитие PIES (Система независимой оценки проектов) энергетической модели, предпринятое Американским министер-:твом энергетики в конце 70-х гг. Второе - публикации М.Смита и по-:ледователей, в которых задача о равновесии транспортных потоков бы-ia сформулирована как конечномерное вариационное неравенство. Вслед ш открылся широкий поток публикаций по различным моделям равно->есия: прогнозирование межрегиональных товарных потоков, равновесие ю Нэшу, прогнозирование цен на транспортные услуги. Наконец, третье событие - попытка М.Матиенсена решить задачу об общем равносеспи Зальраса при помощи методов, развитых для решения нелинейных задач > дополнительности. Его успех подтолкнул других исследователей к применению этих методов для нахождения состояний равновесия в больших :пстемах.

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

Цель настоящей работы состоит в разработке теории и методов анализа и оптимальной коррекции несобственных задач оптимизации различных классов. При этом решаются следующие задачи.

1. Разработка теории и методов линейной коррекции несобственных выпукло-вогнутых минимаксных задач.

2. Разработка теории и методов оптимальной (в том числе нелинейной) коррекции несобственных обобщенных уравнений и вариационных неравенств для общих критериев качества.

3. Разработка численных схем, алгоритмического и программного обеспечения для методов оптимальной коррекции несобственных оптимизационных задач перечисленных типов (с приложением к конкретным оптимизационным моделям).

Методы исследования. Основным инструментом исследования служит аппарат выпуклого анализа и теории линейных неравенств.

Научная новизна состоит в следующем.

1. Сформулированы и изучены задачи оптимальной линейной коррек-

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

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

3. Разработаны численные схемы различных вариантов общего метода композитных отображений для коррекции неразрешимых задач оптимизации, обощенных уравнений и вариационных неравенств с применением приемов регуляризации и итеративной аппроксимации. Предложены новые схемы метода модифицированных функций Лагранжа для анализа и оптимальной коррекции несобственных задач выпуклого программирования (ВП) 1-го рода.

4. Дано описание диалогового пакета программ численного анализа несобственных задач линейного программирования 1-го рода ДЕЛЬТАПЛАН-ЕС, созданного в ИММ УрО РАН группой программистов под руководством автора (которому принадлежит разработка общей структуры и принципов функционирования пакета, его алгоритмическое наполнение, схемы привязки к СПО МПР-2 и схемы интерфейса), а также описание ряда прикладных результатов соискателя, полученные при моделировании работы сложных космических систем с большим числом взаимодействующих элементов, каждый из которых имеет свои цели, ресурсы и задачи.

Практическая значимость. Полученные результаты открывают новые возможности предлагаемых моделей и методов как для рассматриваемых ранее традиционных приложений задач МП, так и для новых

приложений в задачах нахождения различного рода равновесных состояний в экономических и технических системах и ряде других. Разработанное программное обеспечение применялось для решения важных прикладных задач, в частности, для проведения расчетов по теме "Оптимальное объемно-календарное планирование производства" для НПО Урал-маш (ППП ДЕЛЬТА-ПЛАН-ЕС был передан на это предприятие).

Апробация работы. Результаты диссертации докладывались на конференциях: Методы математического программирования и программное обеспечение. Свердловск, 23 - 27 февраля 1987, Методы математического программирования и программное обеспечение. Свердловск, 27 февраля-3 марта 1989, Методы математического программирования и программное обеспечение. Екатеринбург 22-26 февраля 1993, Системы программного обеспечения решения задач оптимального планирования. X Всесоюз. сими. 20-27 марта 1988, г. Нарва, Системы программного обеспечения решения задач оптимального планирования. XI Всесоюз. симпоз. 21-29 мая 1990, г. Кострома, Методы оптимизации и их приложения. 10-ая Байкальская школа-семинар. Иркутск, 14-19 августа 1995г. и др.

Публикации. Основные результаты диссертации опубликованы в работах [1-26] и в отчетах о НИР "Раунд" Института математики и механики УрО РАН N279 от 18.06.1987, N339 от 29.07.1988, N407 от 16.11.1989, N458 от 23.11.1990, N485 от 12.11.1991.

Структура и объем работы. Диссертация изложена на 221 страницах машинописного текста и состоит из введения, трех глав, приложения, заключения и списка литературы, содержащего 185 названий.

СОДЕРЖАНИЕ РАБОТЫ

Во введении дается обзор подходов и результатов разных авторов по исследованию НЗМП, формулируются новые задачи и проблемы и излагается содержание работы по главам.

В первой главе диссертации излагаются результаты автора но методам оптимальной линейной коррекции несобственных минимаксных задач в абстрактной постановке. Глава содержит параграфы с 1-го по 6-ой. П.1 является вводным. Цусгь имеется класс эквивалентных собственных замкнутых вогнуто-выпуклых (СЗВВ) функций Р(х, и) : Я" х И,"1 —г Й =

RU { ±оо }. 2

Определение 1, Назовем абстрактную двойственную пару минимаксных задач

V* sup inf F(x, и), V* inf sup F(x, ti) (1)

sec uzd ueD xec

несобственной, если их оптимальные значения не совпадают или несобственны.

Рассмотрим некоторое содержащее эти задачи параметрическое семейство минимаксных задач вида

V*(w) := sup inf F{x, и, w), V*(w) := inf sup F(x, u, w). (2)

fZC и£D xec

Определим множество

^Vs(cr) := { iv € E задачи (2) обладают свойством cr }.

Определение 2. Подзадачей (S, <т)-оптимальней коррекции несобственных задач (1) будем понимать задачу нахождения такого элемента w 6 i^a(cr), который бы оптимизировал заданный критерий качества аппроксимации S(w).

В паиестье свойства сг берется условие существования конечного сед-лоаого значении и ссдловой точки у параметризованной функции.

Б п.2 сс с уедается структура множеств разрешимости при линейном способе параметризации исходной пары минимаксных задач. Функция и) погружается в параметрическое семейство СЗВВ-функций вида

!■(£, н, ?/, = F(r, !')-(«, х) - (f„ и), (3)

2 КаждиИ такой класс определяется значениями любого своего представителя F в точках ошеентельной внутренности ею эффективной области (общей дли всех представителей класса). ¡3 классе имеется максимальный F и минимальный элемент F_. Дли любого другого представители F имеем с!•> F[x, •) = F_{.v, •), F_(x, :t) < /'(„:, и) < ~F(,;\ и), сЬ F(-, и) Ei F(\ u). Ух Vu, Все представители одного класса имеют одно и то :ке седловое значение и одно и то же множество седловых точек (терминологии следует книге Р.Т.Рокафеллара ''Выпуклый анализ").

где [г/, £] = w' - вектор параметров коррекции. Соответственно множество разрешимости определяею! Kai:

17(F) = { [г;, £] £ Г!" х В"' : F(-, ■, >;, £) имеет седловуго точку }.

Выпишем нижнюю и верхнюю сопряженные к /'(г, и) функции

£*('?. s) = Slip inf { (г/, Х-) + (£, 1/) - F(x, v.) ],

Ii x

V~(i], £) = inf sup { (.,, *)+(£, u) - F(x, u) }.

r «

Эти функции являются эквивалентным!! СЗВВ-функциями с общей эффективной областью dorn F = doin F* = С* х где

6" {г, : £*(?/, О > -оо V£} #0, ZT = {i :Г(г;,0 < +оо V?,} ^ О.

При этом

ri (С* х D") С 1V(F) С С* х 1Г, (-1)

cl ir(F) = cl (С* х D*), ri (cl W(F)) = ri(C* х D~). (5)

Таким образом, множество разрешимости оказывается почти выпуклым.

В п.З рассматривается задача отыскания элемента множества cl \V{F), минимального относительно заданно!'! сепарабёльной выпуклой симметричной функции А'(»/, £) = Ki (rj) + К•>(£). Соотношения (4) - (5) позволяют разбить задачу минимизации А'(т], £) па множестве cl \V(F) на две независимые подзадачи

(я) : min { Кх(г]) : г; е cl С* }, (Ь) : min { : £ £ cl D* }. (G)

Свяжем с исходными несобственными задачами (1), (3) задачу поиска седлового значения расширенной функции

FK,aß{x, и) = F(x, и) + KUß, и) - К*(а, гт),

где A'i(n, •) и Кч(а, •) всюду конечные симметричные выпуклые функции, зависящие от скалярного параметра а > 0 и связанные условиями

lim nKi{n, »;) = A'1(0, )/), lim а A'2(a, = А'2(0, £), (7)

Arg min A'i(0, rj) — С , Arg min Л'2(0, £) = D , (8 vecl с iecl D' »

причем существует j > 0, такое что

ri С П int (dorn A'i (tv, •) ф 0, ri D П int (dorn K*2{a, ■) ф 0 (9

для всех 0 < « < -f. Здесь /v'j(a, •) и ■) - функции, сопряженные

к Л'! (о-, ■) и •).

D качестве примера выпишем функции вида

. .Г о-1 Л'3 (tj)^ , если а > 0, ,1П.

ЛЦа, т?) = \ ' (10)

L Ац?/)р, если а — 0;

где р > 1. При этом, если A'i(-) - некоторая норма, то к;(а, х) = |

_ / (р~ 1 )p~p/(p-1)alf(-P-1'>K;{x)P^P-1\ если р > 1, ¿(a_1i?i | е), если р = 1.

Здесь К\(х) = тах (г/, ж) - норма, сопряженная к А'х, ¿(Л/ | г) -к :0?)<1

индикаторная функция множества А/, = { г : /<Г(г) < 1 }.

Чтобы сформулировать основной результат параграфа, введем миожс-

u) = dxF(x, и)ПдКЦа, х), N}{x, u) = duF(x, n)n-dK*2{ß, и).

Пусть Sa,ß - множество седловых точек функции Fji,a,ß{x> и) ■ Если [х, u] е Saß, то имеем 0 € дхРк,а,р{х, и) = drF(x, и) - дК*(а, и), 0 € duFn,aß(x, и) = duF(x, и) + (/?, и), и следовательно

Nai0(x, и) := Nl(x, и) х N$(x, и) ф 0.

Введем далее множество NQß — |J Naß(x, и) и функции

[г, u]eSo,i(i

чувствительности

Л'о(»/)= iiif. £*('/, О. 'Ш)= sup О-

ieß чес"

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

С* = Arg max Ko{i]), D' = Arg mjn T0(().

vec' ?ео*

Связь задачи поиска седлового значения расширенной функции FK,a,ß{x, и) с задачей оптимальной коррекции исходных несобственных минимаксных задачам устанавливает

Теорема 1 Пусть F является СЗВВ-функцпей, выпуклые функции A'i(a, •), A'2(/ö, •) всюду конечны, симметричны и выполнены условия (7)-(9). Тогда

a) W(F) Э Na¡p ф 0 для всех 0 < а < у, 0 < ß < у ;

b) max p(z, С х D ) 0 при а —+ +0, ß —► +0, а/3-1 —» г, где zeNcp

г £ (0, +оо), р -расстояние от точки до лможества;

c) если функции К\(а, •), •) имеют вид (10) и функции А'о, То - собственные и замкнутые, то шах p(z, С* х £)*)—► 0 при а —► +0,

ß —► +0, aß= г, г £ (0, +оо); если замкнута только одна из них, это свойство верно для соответствующей ей компоненты векторов z.

В п.4 обсуждается приложение полученных результатов к прояснению аппроксимативных свойств двойственности для НЗЛП. Пусть имеется пара несобственных взаимно двойственных задач ЛП

шах { (с, х) : Ах < 6, х > 0 }, min { (6, и) : АТи > с, и > 0 }, (И)

где х £ R", с е R", 6 £ Rm, А ~ m х п -матрица, индекс т означает транспонирование. Рассмотрим их симметричную параметризацию вида

шах { (с - t¡, х) : ах < ь + £, х > 0 } =: Ф* (г/, (12)

min { (6 + и): Ат и >с-г), и > 0 } =: £)> (13)

Определим множества

Л/(4) = { х : Ах < ¿ + Í, х > 0 }, М'(п) = { и : Ати > с - rj, и > 0 },

= { V : M'(r¡) ф0}, П( = { í : M(f) ф 0 }, ÍJ = П„ х Щ.

При [т), £] <= задачи (12)—(13) разрешимы и их оптимальные значения совпадают (т.е. они находятся в отношении совершенной двойственности). Выпишем следующие задачи ВП

тл\ ; х) - r-2',| iyU - Ь)4 \\2 : х > 0, х ¡ц < 14 }, у\\)

min { (6, у) + n|| (с - Лт«)+ ||i : u > 0, || у ||$ < r2 }. (15)

Здесь a+ = max { О, а } для числа а, р+ — ,..., р+] для вектора р= \pi,...,p,], и > 0, г2>0; ||-Щ и I) -1|5 - нормы сопряженные к ||-||i и || • ||2 . Эти задачи могут быть получены из конструкции, изложенной выше, если взять в качестве СЗВВ-функции F(x, и) функцию Лагранжа задачи (11) и воспользоваться функциями вида (10) с р = 1 , положив П = а-1, г2 = /?->.

Обозначим через [»/, £] (Е П элементы, минимальные относительно заданной монотонной сепарабельной нормы ||(»7, £)||о = ||r/||i + ||f||2 . Пусть Мг - оптимальное множество задачи (14), а М* - оптимальное множество задачи,(15), здесь г = [ri, г2] > 0.

Теорема 2 Пусть [гг, ur] Е Мг х Л/*. Тогда можно определить вектор [?)г, £г] = [(с — vlTur)+, (Ахг — 6)+] £ Q, причем хГ есть решение задачи (12), а иТ - задачи (13) при tj = t]r, £ = . Если же ri —► +оо, г2 —♦ -foo и r'1^ = f € (0, +оо), то также

р((с-АТиТ)+, П^)—О, р((Лхг-6)+,

где х - множество седловых точек функций Ф* и Ф* относительно области х Q^ С х ii^. Здесь

Ür, = Arg min Ц77Ц1, Щ = Arg min ||f||2.

ЧбП, iE"«

Более сильное утверждение верно для кусочно-линейных норм.

Теорема 3 Пусть в задачах (14), (15) нормы ||-||i и Ц-Цг кусочно-линейны (представимы в виде поточечной верхней грани конечного числа линейных функций) и пусть [a;r, «г] £ Mr х М*. Тогда (в дополнение к утверждению теоремы 2) существует R > 0 такое, что

rfr = (c-ATur)+ е £г = (Ахг - 6)+ G Щ, как только r\ > R, r?> R.

В п.5 рассматривается случай минимаксного критерия качества коррекции, когда выбором параметров коррекции занимаются две стороны, интересы которых противоположны. Эти интересы описываются платежной функцией (седловым критерием коррекции) К, где К (г/, £) :

R" x R"1 —» R = R U { ±oo } - СЗВВ-функция. Формулируется задача нахождения седлового значения

а(К, F) = sup inf К(п, О = Inf sup Л'(»/, О- (16) Т7ес1 с* fecl d- iecl о* ,)€С1 с-

Эта задача изучается при предположениях:

51°. F(-, •) и К(-, •) - СЗВВ-функции.

В2° . X := ri Хк Л ri С* ф 0, U := ri UK Л ri D* ф 0, где dorn К = Хк х Uk ~ эффективная область функции К.

В3° . При некоторых хо 6 X и щ Е U псе множества уровня функций А'(яо, u)-f 6(и | D*) и К(х, «о)—¿(а; | С*) ограничены, здесь 6(z \ М) -индикаторная функция множества М.

Инструментом анализа задачи является СЗВВ-функция 3

Фа,к(»7, и, S, х) = К{т], О - a(F(x, и) - (»/, х) - (£, и)), о > 0.

Обозначая г = [т], и], w = [f, х-] будем записывать значения функции Фа,к(п, х) как Фа,А'(г, w).

Введем также функции Ра(х, и) = aF(x, и) -f А'"(—ах, —аи), Qa('h 0 = QF*(r)i 0 + ^ i)' здесь К* и F" - сопряженные функции для К и F (выбранные произвольно в соответствующих классах эквивалентности).

Введем обозначение ЩК, F) для множества седловых точек функции К относительно области cl Л' х cl I! и Sa для множества седловых точек функции Фа,А' относительно Rn+mxRm+n, т.е. множество таких [го, что

Ф«,к(*. <Ф*,к(го, V00) <Фа,кЫ Ш) Уг, 4w.

Теорема 4 Пусть выполнены условия В1° — ВЗ" и последовательность att —* +0 . Тогда

a) при некотором tо и всех t > <о множества седловых точек Sat функций Фа,,к не пусты;

b) если [zt, u>t] = [г;,, ut, £<, G Sa,, то векторы xt и щ являются седловой точкой функции F(x, и, r/t, 4«) — F(x, и) —(r/t, х-) — (£t, и), т.е.

Здля сложения несобственных значений можно воспользоваться одним in правил (безразлично, каким именной: —ос 4- со = 4-ос — сс = —ос или —оо + оо = 4-оо — оо = -foo .

скорректированные минимаксные задачи

■= гшпта:= тахтт Р(х,и,

иг л: и

находятся в отношении совершенной двойственности;

с) Нт^оо Фа,,я(21, и)<) = сг(К, Р), причем последовательность {^(1 ограничена и все ее предельные точки лежат в П(К, Р);

й) если еще и 0(Л", Р) С И^/1), то все предельные точки последовательности {77*, являются также седловыми для функции Р* относительно ЩК, Р).

Верно также

Следствие 1 Пусть выполнены предположения теоремы 4 и функции Ра, замкнуты при всех малых а( > 0. Тогда

a) при некотором <о и всех I > <о множества седловых точек На, функций Ра1 также не пусты;

b) если [х(, и(] £ На,, то при любом выборе £ Са,> £< £ гс?е

С'а, иОП^аГ1^/^^^«. -а,«.)] # 0,

Са, ~д2Р(хи щ)П[-аТ1д2К'(-а(хи -о,и,)] Ф 0,

точки 4«] принадлежат Ж(-Р), « векторы Х| и являются сед-ловой точкой функции Р(х, и, щ, £<) = Р(х, и) — (»7<, х) —и);

c) Нш«_оо Ра,(хг, "() = с(К, Р), причем последовательность {щ, ограничена и все ее предельные точки лежат в ЩК, Р) ;

если кроме того П(Л', Р) С И^Р), то все предельные точки последовательности {г/|, являются также седловыми точками функции .Г* относительно Р).

Отметим, что множества 5а и 7/а не обязательно зависят от а > 0. Пусть, например, в качестве исходной поставлена задача: найти точку из множества ЩС\, Р) = (С\ х С\\У(Г), где С\, - заданные выпуклые компакты, причем и (С\ х Пп (С* х £)*) ф 0. Полагая в общей схеме Л'(т/, £) = | Их) — 6(г] \ С\), получаем

Следствие 2 При сделанных предположениях относительно С\, £)х и Р функции Ра, а > 0, имеют вид /^(х, и) = аР(х, и), где Р(х, и) :=

Р(х, и) 4- 1шп1;6с, (»/. л) — тт^ел, (£, и). Они не зависят от о и являются СЗВВ-функциями, обладают седловьши точками и, если [жо, »"] -любая из них, то С0 ~ дгГ(х0, и°)ПС 1 ф 0, О0 := д2Р(х0, «°)П/?1 ф 0, так что Со х О0 С П(Сь 1){, /,л). Более того, если \У(Р) замкнуто, то всякая точка из С'о х О о будет седловой точкой функции /•'* относительно 12(6*1, 01, F).

В п.6 дается приложение полученных результатов к анализу аппроксимативных свойств некоторых схем двойственности для НЗВГ1. Пусть имеется задача ВП

8пр{/0(х): /,■(*)< О С? = 1,2,...,т), ге 1Г }, (17)

а также двойственная к ней задача

шГ вир Ь{х, и), (18)

и<0 х

где функции — /о(х), А(х), ..., /т(х) предполагаются выпуклыми, всюду конечными и дифференцируемыми, Цх, и) = /о(х) + (и, /{х)), и — [ыь ..., !/„,] е В"1, /(х) - [/1 (А-), ..., /т{х)]. Предполагается, что эта пара задач - несобственная. Ищется

['Ль = агё гшп ||[»/, [ч. е]ес1 п-

где |( • || - евклидова норма, О! = {[?;, £] 6 11" х 11"' : Цх, и) — (?;, х) — (£, и) имеет седловую точку относительно 11" х Л"1 }, И™ = {?/ €= В'" : и < 0 }. В общей схеме предыдущих разделов можно положить

п

X, и) = |

к(ч, 0 = 1/2(11^Н2-1Ы12).

Ь(х, и), если и < О,

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

1 1 т тах { Мх) - -а,|И|2 - — ^[.//(г)]2 : }, (19)

mill { /0(1) + (и, /(*)) - -^-|И|2 + -f\\uf : q^ = V/0(x)+ (20) +(«, V/(x)), ue R'_" },

здесь Qi = Q2 = Q > 0 .

Обозначим через Ma оптимальное множество задачи (19), а через М* - проекцию оптимального множества задачи (20) на подпространство переменных и.

Теорема 5 При сделанных относительно задач (17) —(18) предположениях оптимальные значения задач (19) —(20) совпадают, множества Ма, М* не пусты и, если ха € Ма, иа G Л/*, то [ах0, f+[xa)] € Q', причем ха - оптимальный вектор задачи

sup { fo{x) - (аг0) х) : /,•(*) < //(га) (j = 1,2,..., m), х € R" },

- оптимальный вектор двойственной к ней задачи

inf sup [L(x, и) - (qxq) х) - (f+(xa), «)],

• ■ u<0 x

и имеет место равенство lima_+o [аг;а, /+(яа)] = [tyo. -

Задача (19), как замещающая задачу (17), рассматривалась ранее в работах А.Н. Тихонова, В.Я. Арсенина и И.И. Еремина в предположении регулярности последней и при способе управления параметрами ит и а 2 отличном от предложенного здесь. Соотношения двойственности между задачами (19) и (20) в собственном случае устанавливались В.Д. Скари-ным. Им же анализировалась связь между задачами (17)—(18) и (19)—(20) в случае, когда две последние являются несобственными задачами 1-го рода (несовместна система ограничений только у прямой задачи).

Вторая глава посвящена аппроксимационным корням монотонных отображений и неразрешимым вариационным неравенствам. Она содержит параграфы с 7-го по 12-ый. П.7 носит вводный характер.

Определение 3. Пусть заданы Z - некоторое подмножество R" и Т : R" =t It" - точечно-множественное отображение. Под вариационным неравенством, в дальнейшем обозначаемым VI(Z, Т), понимают задачу нахождения векторов г* G Z, t* € T(z') таких, что

(Г, г-г*) > 0 при всех z € Z. (21)

В работе рассматриваются только монотонные отображения, т.е. отображения со свойством

(<" _ t', г" - z') > 0 Vz", г', Г € Тг", i' G Tz'.

В п.8 даны определение апнроксимационных корней монотонного отображения, их свойства и условия существования для широкого класса допустимых монотонных параметризаций.

Определение 4. Вариационное неравенство VI(Z, Т) назовем несобственным, если оно не имеет решений.

Вариационное неравенство можно представить в виде обобщенного уравнения (включения) вида

0 е r(z) := / T(z) + N(Z, z), если z <= Z П dorn T \ 0, в остальных случаях.

Здесь dorn Т = { z : T(z) ф 0 } - эффективная область отображения Т , N(z, Z)={h: (h, у - z) < 0 Vy € Z }.

Рассмотрим монотонное обобщенное уравнение или, в иной терминологии, задачу отыскания корня заданного монотонного отображения Т : R" =3 R" , т.е. задачу отыскания такого вектора г € R" , для которого

Т(г) Э 0. (23)

Будем изучать его в предположении его несобствениости (неразрешимости). А именно, пусть

Т(г, w) Э 0 (24)

есть реализация некоторого погружения, исходного уравнения (23) в класс уравнений, зависящих от векторного параметра w Е Rn (конечной размерности, для простоты совпадающей с п). Определим множество

W = {u> G R" : уравнение T(z, w) Э 0 разрешимо).

Пусть это множество не пусто (используемая параметризация содержательна). Выбор элемента w £ IV фиксирует способ коррекции уравнения (23). Пусть выбор ограничен множеством М таким, что М W ф 0 . Будем оценивать его с помощью вариационного неравенства, порождаемого некоторым монотонным отображением S : R" =3 R" , (например, суб-диффференциальным отображением некоторой выпуклой числовой функции. оценивающей разность ш — w') следующим образом: оптимальным

считается вектор параметров коррекции wq Е Wm := cl (М f] W) такой, что при некотором «о 6 S(wо) и всех w £ IVm выполняется неравенство

(so, w0 - w) < 0. (25)

Определение 5. Решение уравнения (24), соответствующее wq (или некоторому его с-приближению, если u>o $ W ), назовем S -аппрокснма-ционным решением (корнем) уравнения (23).

В частном случае, когда S(w) = w — w и множество cl W —выпукло, S-аппроксимация означает просто поиск ближайшего к w элемента из cl W.

Определение 6. Назовем параметризацию (24) монотонной, если существует монотонное отображение F : R" х II" => R" х R" аргументов г, w такое, что

T(z, w) = { у G R" : ЗЛ £ R" такое, что [у, h] £ F(z, w) }. (26)

Поскольку F монотонно, то при любом ui отображение Т(-, w) также монотонно.

Определение 7. Отображение Су : R" R", определяемое по правилу

CF(w) = { у £ R" : 3z такое, что [0, у] £ F(z, w) }, (27)

будем называть характеристическим для отображения F .

Теорема G Пусть отображение F монотонно и выполнено условие (26). Тогда его характеристическое отображение Cf также будет монотонным. При этом

W = { iv £ Rn : T(z, w) Э 0 разрешимо по z } — dom Cf-

Следствие 3 Пусть характеристическое отображение Ср, определяемое из соотношений (27), лхаксималъпо монотонно. Тогда множество W в задаче (25) об S -оптимальной коррекции уравнения (23) будет почти выпуклым.

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

С\°. Отображения F и Ср максимально монотонны.

С2°. Множество М выпукло и замкнуто, ri М |~)ri (dorn Ср) Ф О.

СУ. Отображение S монотонно, полунепрерывно сверху и выпукло-:омпактно-значно на \\'м = cl (dorn Срр|Л/).

СЛ". Существует точка /iq £ ri Wm и окружающий ое компакт D ■акие, что для любого w G Wm р) В при некотором s G S(w) выполнено [еравенство (s, w — hо) > 0 .

Отдельного рассмотрения заслуживает случай, когда в соотношениях 24)-(25) параметр w входит в T(-, w) линейно: T(z, и>) = T(z) — w, v G Rn. Этот случай укладывается в рамки класса монотонных параметризаций: в качестве отображения F можно взять отображение

F'(z,w)=(T(z)-w)x{:}.

1ри этом Cf(-) = Т-1(-) и уравнение T(z) — w Э 0 разрешимо тогда I только тогда, когда w G dorn Т-1 . Для почти выпуклости этого мно-кества достаточно потребовать максимальной монотонности отображения

г*

В п.9 рассматривается метод композитных отображений. Эти отобра-кения FaiS : R" х R" z{ R" х 1Г, C^s : Rn =t II" определяются как

Г aF(z, w) + (0) х Sm(w) при [r, w] € dorn Ff\L \ 0 в противном случае;

{nCf(w) -f Sm(w) при w G dorn Sm p|dom Cy, 0 в противном случае.

Здесь Sm — S + Nm, отображение Nm : R" =3 R" порождает-:я нормальными конусами к множеству Л/, dorn Sm — М f]dorn 5, ^ = {[г, ту] : z e R", w G dorn Sm], а > 0 .

Теорема 7 Обобщенные уравнения Cf.s(iv) Э 0, Fa:s(z, ш) 3 0 уазрегиимы или не разрешимы одновременно.

Роль введенных вспомогательных отображений видна из следующего утверждения.

Fa,s(2' "') = C£s(w) =

Теорема 8 Пусть отображение F люнотонно, выполнены условия С2°, С3° и последовательность {ш„} составлена из корней отображений Cp"s, где ап —> +0. Если эта последовательность имеет предельные точки, то все они являются решением вариационного неравенства (25).

Некоторые уточнения приведенных фактов дает

Следствие 4 Пусть выполнены условия теоремы 8, условие СIo и множество Wj¡j решений неравенства (25) не пусто и лежит в W . Если ivo - предельная точка последовательности {id„} и множество Cf(u'o) ограничено, то при некотором щ £ C¡?(wо) имеем неравенство (tío, u'o — w) < 0, верное при всех w <Е .

Теорема 8 и следующее за ней следствие показывают путь отыскания S-оптимального вектора коррекции wq и соответствующего ему аппрок-симационного решения уравнения (23): следует выбрать малое а > 0 и найти корень [zQ) ша] отображения Fais ■ Вектор wa будет искомым приближением к и<о , тем более точным, чем меньше а > 0 .

Приведем различные условия, гарантирующие разрешимость уравнений Cfis(w) Э 0, 0 < а < с*о, и ограниченность множеств их решений г совокупности.

Теорема 9 Пусть выполнены предположения СIo — С3° и отобра жение S сильно монотонно на Wm с константой -у > 0 , т.е. при ecei w',w"E.Wm, s' е S{w'), s" e S(xv") выполнено неравенство

(«'-Л w'-w")>y || w'-w" И2.

Тогда отображение CpS также является сильно монотонным, имееп единственный корень wa и множество По = Uo<o<q w<* ограничен< при любом ао > 0 .

Условие сильной монотонности S можно несколько ослабить за счс усиления условия С4° . Пусть Va - множества корней отображений CyS

Теорема 10 Пусть выполнены условия СIo — С3° и следующее усь леиие условия С4° : существует точка Ло € ri lV\i С ri (dora Cf и окружающий ее компакт В диаметра d такие, что для любо г

w € dorn CpS p) В при некотором s £ S(w) выполнено неравенство (s, w — ho) > 6, где dorn — M f]domCF, 6 > 0 фиксирова-

но. Пусть 0 ф <о G C/-(/io) выбрано произвольно. Тогда множества V", 0 < а < ао — S/{d || /о ||), не пусты и ограничены в совокупности (лежат в В). Если же Cp{ho) Э 0 , то Va С В при всех а > 0 .

Приведем одну из оценок точности решения задачи об оптимальной аппроксимации.

Следствие 5 Пусть выполнены предположения теоремы 9 и включение и>о Е dorn Cf, где wq - решение задачи (25) . Тогда

II wa - Wq || < а7_1|| z0 II, где zо £ Cf(wо) выбрано произвольно.

Некоторые дополнительные результаты аналогичного плана получены в разделе, посвященном линейной аппроксимации монотонного отображения.

В п.10 обсуждается условие максимальной монотонности характеристического отображения Cf. Условия, при которых отображение Cf будет максимально монотонно, формулируются в терминах параметрического отображения Fx(-, v) : R" =3 R", определяемого как

Fx(u, v):={ ze R" : 3 w 6 R" F(z, w) + [г, w] Э [«, r] }, (28) где v £ R" играет роль параметра.

Теорема 11 Пусть отображение F монотонно. Тогда для максимальной монотонности отображения Cf необходимо и достаточно , чтобы при любом фиксированном v £ Rn отображение Fx(■, v) имело неподвижную точку.

Рассмотрим некоторые свойства отображения Fx( -, v).

Теорема 12 Пусть отображение F максимально монотонно. Тогда при любом фиксированном v £ Л" отображение Fx(-,v) определено на всем пространстве (т.е. dorn Fx(- ,v) = Rn) и является нерасширяю-щим.

Теорема 13 Пусть исходное отображение F монотонно, а отображения Fx(-,v) определены на всем R" и при всех v £ R" являются сжимающими, т.е. при всех г' £ (и', v), z" £ FK(u", v) выполпепь неравенствы \z' — z"\ < q(v) |u'—u"\, где q(v) £(0, 1). Тогда отображена) Cf будет максимально монотонным.

Для линейной аппроксимации имеем равенство Ср(-) = и та

ким образом уравнение T(z) — w Э 0 разрешимо тогда и только тогда когда w £ dorn T~l . Для почти выпуклости этого множества достаточш потребовать максимальной монотонности отображения Т. В работе пока зано, что в этом случае отображение, построенное в соответствии с (28) будет сжимающим.

В п. 11 рассмотрены дополнительные вопросы линейной аппроксимацш для несобственной задачи поиска корня монотонного отображения. Основ ным остается метод композитных отображений. Состав этих отображенн! конкретизируется и расширяется. Устанавливаются некоторые новые i уточняются полученные ранее факты. Используются следующие аналоп условий С Г - С4° .

С1 J. Отображение Т максимально монотонно.

С2°. Множество М выпукло и замкнуто, ri Л/ f~)ri (dorn

С'3°. Отображение S монотонно, полунепрерывно сверху и выпукло компактно-значно на 17д/ .

C'4'j. Существует точка ho 6 ri Н'д/ и окружающий ее компакт 1 такие, что для любого w £ W\i f) В при некотором s £ 5(и>) выполнен! неравенство (s, и> - h0) > 0 .

Выпишем новый набор композитных отображений

Та s(z) = ( Г(г) _ SM(~az) "Ри 2 е do,n Т П (-¿dorn 5д/), 1 О в противном случае;

SC,T(UI) = |

Sm(u>) + q:T ^ш) при w £ dorn Sm p|domT 0 в противном случае;

{{aT(z) - а ш} х

х{5д/(го) + az} при (z, w) £ dorn tf 0 в противном случае.

Здесь Sm — S+Nm , Л'д/ : R" R" - монотонное отображение, порождг емое нормальными конусами к множеству М, dorn Sm — М p)dgm '

dorn HyS = {(г, w) : z £ dorn T, w £ dorn 5д/} , о > 0 .

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

Теорема 14 Пусть отображение Т максимально монотонно, отображение Sq1 = полунепрерывно сверху, компактно-значно и

сильно монотонно на Rn с константой у > 0 и М = R" . Тогда для любого Qq > 0 множества Wa при 0 < а < ао ме пусты и ограничены в совокупности, множества Za = {za} одноэлементны и

«II || <о0|| zQ || +7-1( II ||+max max \\ s \\ ),

II * ll<>-

где zq £ dorn T и wq £ T(zq) выбраны произвольно.

Теорема 15 Пусть М = Rn, wo - S-оптимальный вектор сдвига максимально монотонного отображения Т и Zq Г-1(гУо) ф 0 • Тогда найдется вектор sq £ S[vüq) такой, что —Sq есть направление рецессии множества Zq (т.е. Zо — so С Za )■

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

Третья глава содержит параграфы с 13-го по 17-ый. Она объединяет результаты по численным схемам оптимальной коррекции несобственных задач оптимизации, неразрешимых вариационных неравенств и задач пояска корней монотонных отображений.

В п. 13 обсуждаются вопросы получения ограниченности и сходимости г-компонент последовательности корней отображений Рассматри-

вается расширенная система вида

H%s(x, w) Э 0, T(z) + ez - w В 0. (29)

Здесь е > 0 - параметр регуляризации.

Теорема 16 Пусть отображение S сильно монотонно с константой у > 0, Wo — оптимальный вектор сдвига, zo — минимальный по норме аппроксимационпый корень монотонного отображения Т, т.е.

z0 = arg min ||г||, где М0 = {; : T(z) - w0 Э 0}.

г 6 Л/ о

Пусть отображение Т удовлетворяет квалификациошюму условию pm(z, Mo) < С min ||w- w0||

uiET(z)

при всех г £ dorn T, где С > 0. Тогда

Ik - roll < НгоН^^Ы^МтО"1 + (гсфоН)1/'2"^,

где ze - проекция произвольного решения системы (29) па подпространство переменных z .

Таким образом параметры регуляризации и релаксации следует согласовывать друг с другом для обеспечения нужной точности аппроксимаци-онного решения.

В п.14 рассматриваются методы проекционного типа. Предполагается, что М — R", Т = Т0 + Nc , отображения Sq 1 и 2о однозначны, непрерывны и монотонны, С С М - выпуклое замкнутое множество, Nc " отображение, порожденное нормальными конусами к множеству С .

Метод проекции применительно к отображению Та $ описывается соотношениями:

Zo Е С; '¿„'+1 = Pc(zn - ßk(T{(zn) - S»1 (~akzn))), (30)

n = 0,1,2,... .

Здесь Pc{-) - оператор проектирования на С, а^ > Q, ßk > 0 - числовые параметры, Т£ - отображение, аппроксимирующее То на к -ом шаге (например, вбирает в себя погрешность вычислений То или моделирует нестационарность процесса оптимальной коррекции исходного неразрешимого уравнения).

Приведем несколько результатов для случая, когча гц-• " Т? = Tv не зависят от к .

Теорема 17 Пусть отображение сильно монотонно с константой 7 > 0 и вместе с отображением То удовлетворяет условию Липшица с константами Ь\ > 0, ¿2 > 0 соответственно. Тогда при всех го € С, 0 < Р < 2ау (¿2 + последовательность (30) сходится к

единственному корню отображения Та,з ■

Теорема 18 Если отображения То и 5д 1 удовлетворяют условию сильной обратной монотонности с константами 71 > 0 и 72 > 0 соответственно и множество корней отображения Х^ ме пусто, то при всех ¿о Е С, 0 < ¡3 < тт{71, 72/»} последовательность (30) сходится к одному из них.

Пусть Т = То + N0, -5 = ¿и + Ым , где отображения То и монотонны, однозначны и непрерывны на Л" , N0 и Мм ~ монотонные отображения, порожденные нормальными конусами к выпуклым замкнутым множествам С и М соответственно. Рассматривается следующий метод с экстраполяцией направления спуска:

го = ¿о £ С, и>о = гио £ М — произвольные;

гп+1 = Рс(2п - а(3(Т(гп) - «;„)), гп+1 = РС(гг1+1 - а/3{Т(гп) - й>п)), Мп+1 = Рм{ып - /3(5(й)„) + аг„)), й>„+1 = -Рл/(™„-и ~ /?(5(™п) + аг„)),

п = 0,1,2.....

(31)

Здесь Рс и Рм - операторы проектирования на С и М соответственно, а > 0 , (3 > 0 - числовые параметры.

Теорема 19 Пусть отображения То и £1 удовлетворяют условию Липшица с константами > 0 и [¿2 > 0 соответственно и а > 0, О < /3 < (3£)~1 , где Ь = ¿2 + <*(2 + ¿1) • Если множество корней отображения не пусто, то при любых начальных го, и>о обе последовательности (31) - основная {(г„, ш„)} и вспомогательная {(гп, ^п)} - сходятся к одному из них.

В приведенной формулировке Ь - оценка константы Липшица для отображения .

В п.15 (в духе методов итеративной регуляризации А.Б.Бакушинского, но уже для несобственных задач) изучены вопросы согласованного стремления к нулю параметра ак , ошибки вычисления То(г*) и шагового

параметра ßk > 0 так, чтобы на основе последовательности (30) минуя корни вспомогательных операторов можно было непосредственно получить решение исходной проблемы об оптимальной коррекции.

Теорема 20 Пусть T(z) = Tq(z) + Nm(z), М - выпуклое замкнутое множество, монотонные операторы То и S-1 удовлетворяют условию Липшица с константой L, причем оператор является сильно монотонным с константой у. Пусть также выполнены условия:

(a)ак\+ 0, ßk-*+0, E(Jt) akßk - +00,

(b) at+1alßk{ak -at+i)"1 -+oo, \\Tj>(zt)-T0(zk)||/a*0; , (с) 0 < ßkfai < €* = 2T[I(1 + ajt)]-2 (fc = 0,1,...).

Тогда последовательность zk , порожденная процессом (30), обладает свойством: \\zk — zk\\ —» 0, где zk (к = 0,1,...) - корни операторов Ta,s , соответствующие а = ак. При этом wk = S~1(—akzk) сходится к (единственному) решению вариационного неравенства (25).

Условия, накладываемые на последовательности шагового и релаксационного параметров, можно ослабить, если ограничиться целью получить сходимость последовательности wk = S~1(—akzk) и не стремиться к сходимости ||г* — zk\\ —► 0.

Теорема 21 Пусть выполнены предположения теоремы 1 относительно отображений Т и S'1 и в соотношениях (30)

(a)at\+0, А—+0, E(fc) «k+ißk = +00,

(b) ak+1akßk(ak - ajt+i)-1 +oo, ||Т/(^) - T0(zt)ll -

(c) 0 < ßk/ak <ck= 2T[L(1 + a*)]"2 (¿ = 0,1,...).

Тогда последовательность wk = S~1(—akzk) сходится к (единственному) решению вариационного неравенства (25).

В п. 16 рассматривается задачи последовательной (лексикографической) оптимизации: 4 найти

щ := min { fi(x) : iGM*"1' }, i = l

4Такие задачи играют в частности большую роль при построении ап-проксимационных моделей несобственных задач МП 1-го рода с ограни чениями, ранжированными по степени их директивности (обязательност! для выполнения^.

и хотя бы одну точку множества М(т\ где

М(,'> := Arg min { х 6 M(i~l) : f^x) = Vi), i = 1,..., т. (32)

Здесь - заданное выпуклое замкнутое множество, все функции

fj (я), j = 1,..., т, конечны и выпуклы на R".

Будем обозначать через ht(x) произвольный субградиент функции /¿(г), вычисленный в точке х, Ро(') - оператор проектирования на множество М(°\ - конечный набор последовательностей положительных чисел ( i = 1,..., т ).

Выпишем следующую модификацию метода обобщенного градиентного спуска

х0ем(0), r.+i = р0 ^ *.-£<*,■./',•(*,) j, e = o, 1,... (зз)

Сходимость этого процесса к множеству Л/'"1' доказана в работе при следующих предположениях:

Dl0 . Множество не пусто и ограничено.

D2° . Все функции fi(x) ограничены на множестве снизу.

D3° . Субградиенты всех функций ограничены сверху по норме на множестве М.

DA" . В случае т > 2 для каждого i, 1 < г < ш, существуют такие С1 > 0, 0 < а < 1, что функции оптимума

tMO := min { fi(x) : /Дх-) < vs + t, j = 1_____i - 1; * G Л/(0) }

удовлетворяют условию роста вида

V>«(0 < vi - Cii",

при всех достаточно малых t > 0.

D5° . Y^sLo а<! = H27Loah < 00 ПРИ всех '> причем имеет место :ходимость отношений вида r,-3 := «НМ0^1 ~О ПРИ s г ~~ любое.

D6° . В случае гп > 2 для каждого г, 1 < i < m, имеет место сходимость отношений вида pi, := r"_j 3 (П^Л* гч>) ® ПРИ s ~* 00 (3ЛССЬ 1араметр а тот же что и в DV ).

Наконец, в п. 17 исследуются вопросы адаптации и применения метода проксимальных отображений для решения проблемы оптимально!'; коррекции несобственных задач BII 1-го и 2-го рода. Рассмотрена задача минимизации функции f(x) : Rm R на множестве D в предположении неиустоты, выпуклости и замкнутости ее надграфика

epi / = { [*, t] € Rm+1 : t > /(*), xeD}.

Пусь эта задача — несобственная 2-го рода, т.е.

inf f(x) = -ос. (34)

t£D

Задача ее оптимальной линейной коррекции имеет вид: найти

й = inf { и(р) : р в Rm, inf (f(x) - (р, х-)) > -оо } (35)

и хотя бы один из векторов

ре{р: и(р) < й + с, inf (/(г) - (р, г:)) > -оо ),

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

х0 - любое ; , .

£n+i € Arg minx6i) { f(x) + w(xn - x) }, n = 0, 1,... .

Будем предполагать, что w(p) — замкнутая кофинитная выпуклая функция, причем ri (dorn w) fl " D ф & .

Обозначим M* = Arg 1П1Пред; w*(p) и

У„+1 = dw(xn - жп+1) P| dfD(xn+1), n = 0, 1,... ,

где Id{x) — ограничение f(x) на D. Последние множества образуют некоторый сопряженный процесс

У'п+1 С Arg min { f* (у) + и;'(у) - (х„, у)}, п — О, 1,... . (37)

у

Теорема 22 Пусть множество М замкнуто, множество М* - не пусто и ограничено. Тогда множества Уп ограничены в совокупности и для любой последовательности уп € У„, п = 0, 1,... , существует предел w = lini(„j w*(y,¡) = linif,,) inf w*(yn) .

Обозначим через У* множество предельных точек процесса (37).

Теорема 23 Пусть множество М замкнуто, множество М* - не пусто и ограничено, функции f*(p), и>*(р) дифференцируемы (первая па int А/ , вторая — на всем пространстве). Если их градиенты удовлетворяют условию Липшица на любом ограниченном замкнутом подмножестве области их определения, vio У* р) int М С М* .

Более сильное утверждение имеет место в случае, когда градиент \7/*(р) можно распространить на граничные точки р множества М по правилу

V/*(р) = lim V/* (?'»)> Pn € int, Л/, pn p.

(n)

Для этого необходимо и достаточно, чтобы подобные пределы совпадали для всех последовательностей, сходящихся к одной и той же граничной точке.

Теорема 24 Пусть множество М за-мкнуню, лтоэксслкзо М" - не пусто и ограничено, функции f*(p) и го*(р) дифференцируемы и значения V/*(p) можно распространить на граничные точки Л/. Если градиенты V/*(p)i Vw*(p) удовлетворяют^ условию Липшица на любом ограниченном замкнутом подмножестве области иг определения, то Г* С М* .

Эти результаты применятся затем при построении методов оптимальной коррекции правых частей несобственных задач БГ! 1-го рода (метод расширенных функций Лагранжа). Обсуждаются вопросы их реализации и в частности вопросы управления точность» решения внутренних оптимизационных подзадач для НЗВГ1.

Завершает диссертацию приложение, состоящее из трех разделов.

П разделе 1 описываются назначение, архитектура, алгоритмическая часть, состав и условия применения ШШ ДЕЛЬТЛ-ПЛЛП-ЕС, разработанного а отделе МП ИММ УрО РЛII группой программистов под руководством автора (которому принадлежит разработка общей организации и

структуры пакета, его алгоритмического наполнения и разработка части вычислительных схем, принципов диалогового интерфейса и некоторые другие вопросы). Пакет предназначен для численного анализа несобственных задач ЛП 1-го рода в режиме диалога. Он разработан на базе оптимизационного ядра известной системы МПР-2 для ЕС ЭВМ серии Ряд-2 и ориентирована на работу в среде ПДО СВМ. Его особенность в том, что он алгоритмически учитывает многочисленные дополнительные ограничения и переменные коррекции, появляющиеся в аппроксимационных моделях для НЗЛП.

ППП ДЕЛЬТА-ПЛАН состоит из библиотеки процедур оптимальной коррекции, программ пользовательского интерфейса и ядра оптимизатора МПР-2. Наряду с выполнением в диалоге логических и оптимизационных процедур оптимизатора МПР-2 система ДЕЛЬТА-ПЛАН-ЕС позволяет:

а) проводить постоптимальный анализ получаемого с помощью МИР-2 недопустимого базисного решения исходной несобственной задачи;

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

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

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

В разделе 2 приведена задача оптимального распределения программ автоматического обслуживания некоторых объектов между блоками предназначенной для этого космической системы. На качество обслуживания накладываются жесткие ограничения. Поскольку намять блоков имеет ограниченный объём, возникает потребность так распределить полную совокупность этих программ между элементами системы (возможно с повторениями), чтобы при данном временном графике поступления заявок, при заданной продолжительности процесса обслуживания и неопределенном заранее моменте его начала каждый объект мог быть обслужен в соответствии с задлниым нпперед качеством.. Приведены математическая модель

оптимизационного типа

т 2 Ь]

1-П П Пс-?.)"^^ • ;=1 » = 1 ¿ = 1

с минимаксным критерием и алгоритмы ее решения.

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

Диссертацию завершает заключение и список литературы.

СПИСОК РАБОТ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Попов Л. Д. Метод обобщенного градиентного спуска для задачи последовательного программирования. - В кн.: Методы аппроксимации несобственных задач математического программирования. Свердловск: У11Ц 4Н СССР, 1984.-С. 76 -82.

2. Попов Л.Д. О методах аппроксимации для несобственных задач вы-1уклого программирования 2-го и 3-го рода. - В кн.: Параметрическая ттимизация и методы аппроксимации несобственных задач математиче-:кого программирования. - Свердловск: У ИД АН СССР, 1985. - С. 89 7 107.

3. Попов Л.Д. Применение максиминного критерия для коррекции не-обственных задач выпуклого программирования. - В кн.: Противоречите модели оптимизации. -Свердловск: УНЦ АН СССР, 1980. -С. 45 -55.

4. Попов Л.Д. Линейная коррекция несобственных выпукло-вогнутых гинимаксных задач по максиминному критерию // ЖВМ и МФ. г 1986. Т. 26. - вып. 9. - С. 1325 -1338.

5. Попов Л.Д. Об отыскании квазикорней максимально монотонных тображений. - В кн.: Исследования по несобственным задачам онтимиза-ии. -Свердловск: УрО АН СССР, 1988. -С. 43 -47.

тах тах пин > А'ед' уеУ 1 <г<н ^

6. Попов Л.Д. Коррекция по выпукло-вогнутому критерию // Математические методы оптимизации в экономико-математическом моделировании. [Под ред. Е.Г. Гольштейна) -М.: Наука, 1991. (§ 5.5.3).

7. Попов Л.Д. Об одной динамической модели целераспределепия с учетом конструкционных ограничений. // РКТ, серия 12, вып.1, 1991, с. 50-53.

8. Попов Л.Д. Об одном методе декомпозиции в несобственном линейном программировании. - В кн.: Нерегулярная двойственность в математическом программировании. Сб. статей. -Свердловск: Уро АН СССР, 1991, с. 42-48.

9. Попов Л.Д. Аппроксимационные корни неразрешимых уравнений с монотонными отображениями в левой части // Известия высших учебных заведений. Математика. -1993. -Л"« 12. -С. 70-80.

10. Попов Л.Д. Модифицированная функция Лагранжа и несобственные задачи выпуклого программирования 1-го рода. - В кн.: Методы математического программирования и программное обеспечение. Тезисы докл. науч. конф. Екатеринбург 22-26 февраля 1993 г. -Екатеринбург: УрО РАН, 1993, с. 73.

11. Попов Л.Д. Применение модифицированного ргох-метода для оптимальной коррекции несобственных задач выпуклого программирования // Труды Института математики и механики УрО РАН. -1994. -Т. 3. - С. 261

-266.

12. Попов Л.Д. Применение метода проекции для нахождения аппрок-симационных корней монотонных отображений // Известия высших учебных заведений. Математика. -1995. -JV» 12. -С. 74-80.

13. Попов Л.Д. Об аппроксимации монотонных отображений, не имеющих корней. - В кн.: Методы оптимизации и их приложения. 10-ая Байкальская школа-семинар. Иркутск, 14-19 августа 1995г. Тез. док. Иркутск: СЭИ СО РАН, 1995. с. 111-112.

14. Попов Л.Д. Применение метода проекции для нахождения аппрок-симационных корней монотонных операторов. - В кн.: Математическое программирование и приложения. Информационный бюллетень АМН. Екатеринбург: УрО РАН, 1995, №5, с. 165-166.

15. Г.'оосй Л, Ц. Лнлянд Несобственных вариационных неравенств и монотонных операторных уравнений. // Информационный бюллетень АМН, Екатеринбург: УрО РАН, - 1996, -Л'»6, - с.46-57.

16. Попов Л.Д., Глезер H.H., Корнилова Г.Ф., Коротаева Л.Т., Ко-

стина M.А., Хрипун М.С. Система программного обеспечения ДЕЛЬТАПЛАН для ЭВМ БЭСМ-6. - В кн.: Методы математического программирования и программное обеспечение. Тезисы докл. науч. конф. Свердловск, 23 - 27 февраля 1987 г. - Свердловск: УНЦ АН СССР, 1987, с. 96-97.

17. Попов J1.Д., Глезер H.H., Коротаева Л.Т., Костина М.А., Хрипун M.C..0 совершенствовании программного обеспечения численного анализа несобственных задача ЛП 1-ого рода. - В кн.: Системы программного обеспечения решения задач оптимального планирования. X Всесоюз. сими. 20-27 марта 1988, г. Нарва. -Тезисы докл. -М., 1988, с. 84-85.

18. Попов Л.Д., Глезер H.H., Костина М.А., Хрипун М.С. Система численного анализа несобственных задач ЛП ДЕЛЬТА-ПЛАН-ЕС. - В кн.: Методы математического программирования и программное обеспечение. Тезисы докл. науч. конф. Свердловск, 27 февраля-3 марта 1989 г. -Свердловск: УНЦ АН СССР, 1989, с. 52-53.

19. Попов Л.Д., Глезер H.H., Костина М.А., Хрипун М.С. Диалоговая система численного анализа несобственных задач ЛП ДЕЛЬТА-ПЛАН-ЕС. - В кн.: Системы программного обеспечения решения задач оптимального планирования. XI Всесоюз. симпоз. 21-29 мая 1990, г. Кострома. Тезисы докл. -М., 1990. с. 58-59.

20. Попов Л.Д., Глезер H.H., Костина М.А., Хрипун М.С. Диалоговая система численного анализа несобственных задач Л11 1-го рода ДЕЛЬТА -ПЛАН-ЕС. // Информационный бюллетень АМП. Л"® 1. Свердловск: УрО АН СССР. 1991, с. 8-13.

21. Попов Л.Д., Глезер H.H., Костина М.А., Хрипун И.С. Диалоговая система численного анализа несобственных задач ЛП 1-го рода ДЕЛЬТАПЛАН-ЕС. - В кн.: Методы выпуклого программирования и некоторые приложения. Сб. ст. Свердловск: УрО АН СССР. 1992, с. 22-40.

22. Попов Л.Д., Костина М.А., Хрипун М.С. Диалоговая система анализа несобственных задач объемно-календарного планирования производства ДЕЛЬТА~ПЛАН-ОКП. - В кн.: Методы математического программирования и программное обеспечение. Тезисы докл. науч. конф. Екатеринбург 22-26 февраля 1993 г. -Екатеринбург: УрО РАН, 1993, с. 74.

23. Popov L.D. Correction with respest to concave-convex criterion. - In: Modem Mathematical Methods of Optimization. / Ed. by K.-ll.Elster. Berlin, Academie Verlag GmbH. 1993. Part 5.5.3.-P. 201 -203.

24. Popov L.D. On the approximative roots of the maximal monotone mappings // Yugoslav Journal of Operations Research. -1995. -Vol. 1. 1.

-P. 19-32.

25. Popov L.D., Eremin I.I. Numerical analysis of improper linear programs using the DELTA-PLAN-ES interactive system // Optimization Methods and Software. -1993, - Vol. 2. - P. 69 -78.

26. Popov L.D., Eremin I.I. Delta-Plan-ES -the Interactive system of numerical analysis of improper linear programs // International Journal Software Engeneering and Knowledge Engeneering. -1993, - Vol. 3, -№ 4. - P. 429 -438.

Подписано в печать 08.01.97. Формат 60x84 1/16.

Бумага офсетная. Объем 2,0 печ.л. Тираж 100. Заказ № ' *

Екатеринбург, К-83, пр.Лешша, 51. Типолаборатория УрГУ.