Монотонные методы выпуклого программирования на основе внутренней аппроксимации ξ-субдифференциала тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ЦЧ - 1. Я"?

Академия наук Украины Ордена Леиииа Институт кибернетики имени В. М. Глушкова

Иа правах рукописи

РЖЕВСКИЙ Сергей Владимирович

УДК 519.853

МОНОТОННЫЕ МЕТОДЫ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ НА ОСНОВЕ ВНУТРЕННЕЙ АППРОКСИМАЦИИ <§-СУБДИФФЕРЕНЦИАЛА

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

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

Киев 1991

Работа выполнена в Институте кибернетики имени В. М. Глушкова АН Украины.

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

наук, профессор ГОЛЬШТЕЙН Е. Г.,

доктор физико-математических наук, профессор ДЕМЬЯНОВ В. Ф„

член-корреспондент АН Украины, профессор ПШЕНИЧНЫЙ Б. Н.

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

Защита состоится Аи/«^- в

часов на заседании специализированного совета Д 016.45.01 при Институте кибернетики имени В. М. Глушкова АН Украины по адресу:

252207 Киев 207, проспект Академика Глушкова, 40.

С диссертацией можно ознакомиться в научно-техническом архиве института.

Автореферат разослан «— ¡9$?/ года.

Ученый секретарь спецпализированого совета

СИНЯВСКИЙ В. Ф.

•„ ,vic(>*>

M.«'nttij ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

>

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

■Основу теории НДО составляют работы, связанные с исследованиями свойств недяфференцирувмых Функций и оптимизационных задач, содержащих такие функции. Важным моментом этих исследований является установление необходимых и, по возможности, достаточных условий оптимальности. Значительный вклад в создание теории и методов НДО внесли Е.Г.Голынтейи.В.Ф.Демьянов.Я.Г.Евтушенко, И.й.Ере-мш^С.М.Ермольев.А.Д.Иоффе.С.С.Кутателадзе.В.С.Шсхапевич, А.С.Не-мировский.Е.А.Нурминский, Б.Т.Поляк, Б. Н. Пшеничный, A.M. Рубинов, А.Н.Тихонов,Р.П.Федоретад,В.В.Федоров,Н.З.Шор.Д.Б.рдия. Из зарубежных математиков наиболее активны в разработке проблематики НДО А.Ауелендер,Д.Бвртсекяс, Ф.Вулф, А.Голдстайя, Ж.-Б.Ириарт-Уррути, К.Лемарешаль,С.Ииттер,Р.№®1флин,Ж.Ч!.0бен,К.Кивш1.Ф.Кларк, Д.Пэл-лашке, С.Робинсон, Р.Т.Рокафэллар.

Один из фундаментальных подходов к ' исследование ' широкого класса практически значимых задач ЦЦО использует возможность их' локального оэипукления. В связи с этим особую важность приобретает инструментарий выпуклого программирования. Здесь к настоящему времени разработана теория обобщенной дафференцяруемости первого порядка, построены и изучены численные методы градиентного типа. Недостаточно же высокая скорость сходимости этих, методов обусловливает необходимость создания более эффективных вычислительных процедур.

Цель работы. Для сложных задач выпуклого программирования разработать метода е-субградиентного типа и исследовзть их свойс •

- г -

таз сходимости.

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

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

Работе выполнена в соответствии с тематическими планами научных исследований, проводимых в Институте кибернетики имени В.М. Гдушкова АЛ Украины. Предложенные в диссертации методы использовались при разработке рида САПР сложных технических объектов. Соответствующие программные комплексы переданы в отраслевые .фонды алгоритмов и программ.

Апробация работа. Основные результаты диссертационной работа .докладывались и обсуждались на семинарах в Институте кибернетики им.В.М.Глушкова АН УССР, Киевском'госуштероитете им.'Г.Г.Шевченко, республиканском доме, научно-технической и экономической пропаганда (Киев), ВЦ АН СССР, ЦЭШ АН ССОР, на всесоюзных и республиканских школах-семинарах "Еонросы оптимизации вычислений" (Киев, Кяцявели, Алушта, 1980-1989 гг.), на всесоюзных симпозиумах "Систомы программного обеспечения решения задач оптимального планирования," (Нарва-йы:)соуу,Костромэ,Минск, 1984-1990 гг.), на Всесоюзном семинаре но оптимизации и ее приложениям.(Душанбе, 1986), на 5- Всесоюзной научной конференции по защите от ионизируюидгге'

излучений ядерно-технических установок (Протвино, 1Э89 г.), ча всесоюзной конференции "Негладкий анализ и ого прилозяпия к математической экономике" (Баху, 1991 г.).

Публикации. Список основных опубликовалыых по томо дассерга-цш работ приведен в конце авюрефэратэ.

Структура и объем работа. Диссертация состоит из введения, четырех глав (14 параграфов), заключения и списка литературы (192' наименования). Работа представлена на 229 страницах.

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

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

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

Основная сложность задачи

fix) —' щ1л ' . (1.1)

минимизации непрерывной функции /: к"'—к состоит в возможном существовании у этой задачи локалънш решений и ocodtiz точен.

Пусть - множество аошыьнш: м'нилулов функции /, Х^ -множество решений аадачи (1.1).

Вектор з е Rn называется ноправлеш&л убывания функции / в точке х, ведя f(x+t3) < /(х) для некоторого 1 > 0. £ага жэ указанное неравенство выполняется при всех полоажгелышх и достаточно малых t, то з называется иональныл нпщю&шаюл уоыв&шя.

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

Так как множество Sa всегда содержит элемент вида з - х¥ -i. х% € то Sx t 0 ««■ л: ¿ Х%.

Точка х ¿ для которой S^ = 0, яазаяаатся особой для ая дачи (1.1). Совокупность особых точек обозначим Л4.'

В диссертации проводятся исследования сходимости такта бэе-конечношаговну. алгоритмов безусловной минимизации функции /, ¡< процессе работы которых генерируетел последивяталыюст;. приблмпя-

пий {х^'У, принадлежащая либо множеству , либо ки\ (Х^ и Х°).

Условия. сходамо'сти алгоритмов указанного типа формулируются в терминах замкнутых правил построения направлений убывания функции /.

Пусть ни одна из точек а?, х1,... .х* не принадлежат множеству Х^, а направление убывания s^ функции f в точке х* определяется как произвольный элемент образа ixa,х1,....хЪ при точечно-множественном отображении (т.м.о.)

к" « ... «к" Sk. (1.2)

с—,-,--*

te+1

Правилол построения направлений убивания (п.н.н.у.) функции J называется последовательность т.м.о. каждое из которых

удовлетворяет условию (1.2)1

Аналогично, если каждый элемент f^ последовательности т.м.о.

сопоставляет не принадлежащим множеству ^ U точкам ,< элемент а* из fQc, то такая последовательность называется правилол построения лотлышх направлений убывания • (п.и.л.н.у.) функции J. ,

Обладающая некоторым заданным свойством Р ограниченная и не имеющая элементов из множества или и последовательность точек ix^J с »называется соответственно Р- или последовательностью ( i0- и fo-последовательностью, если предикат Р пуст).

Пусть ("Л - -произвольная Р-последователъность, каждой точке а* которой по некоторому п.п.н.у. (РА) функции / сопоставляется какой-либо элемент зк е Р^(х°,х1,... ,хЪ.

Если из условия

х\ — х, х I Xf (1.3)

следует,что.все предельные точки последовательности fsfei> являются элементами из Sx, то последовательность т.м.о. (РА> и опредп-ляемоо ею п.п.н.у. функции / называются Р-замснутыли.

. Если дал произвольной Р-последовательности ГхЪ найдется обладающая свойством (1.3)' подпоследовательность {¿А), сопоставленная которой последовательность (зМ сходится к точке з f Sx, то определяющее последовательность' {зк) п.п.н.у. (Fk) функции / называется 1'-кешизаш>1утл.

Аналогично определяйся понятия Iя -зал тутах и Г*-кдазизаш-нутх п.п.л.н.у.

Наиболее общий способ построения направления убывания выпуклой функции (е-процедурв) предложен в 1981 г. В ороцзссе работы 8—процедуры может учютшаться есп или любая часть получаемой информации о значениях функции, ее субградиентах, траектории поиска. Объем указанной информации и способ ее обработки устанавливаются в зависимости от размеров решаемой задачи и резерва памяти используемой ЭВМ.

Основу е-процедуры составляет предаожекннй Лемарешалем .прием внутренней аппроксимации е-субдифференвдала 0/(1) выпуклой оболочкой вычисляемых е-оубградиентов. Поскольку способ накопления элементов из д^/{.'£), вообще говоря, несущественен, то для атой цели можно использовать любой вспомогательный метод минимизации, при работе которого вычисляются значения фужцни и ее (е-) суб-градаенты.

Для выпуклой функции ' /: к*1—к, имеющей компактные множества уровней, простейший способ вычисления в точке -х 4 направления убывания з е состоит в слвдующем.

е-процедура

Шаг 0. Выбрать параметры е > О, а,и €(0,1) и монотонно возрастающую функцию '£: к+—к+, Г(0)=0. .Вычислить с д/(х) и поло:кить й а е = е. 1=0.

Шаг 1. Выбрать произвольное подмножество О = и вычислить

а = Ргозо/со{й,а,е4> - (2.1)

проекцию начадя координат шп на выпуклу» оболочку векторов множества О и С<2) и. {£*>.

Шаг 2. Если выполняется неравенство

* ?(ё), (2.2)

то положить в = ё-о, = <2 = , £ = €+1 и перейти к шагу 1.

Шаг 3. .(Линейный поиск). На отрезке [а,О], а ;> о локализовать

точку мшымумп Функции /{х%). х = хГ > О С такой степенью тсчности,. при которой либо будет полутона удоъхо-

творящая неравенству

/(х) < /(я)-ё ' (2.3)

точка л = x-t'd, ï > О, либо вычисляемый по формуле

gt+' ш Авв+(1-Л)«ь. (2.4)

X a u<gb.d>/[to<gb,d>-fl<ga,d>), g,€ Ô/U.)

элемент gif!ç ci-/(i) будет удовлетворять неравенству

<gi + ',d> ¡S a|d|2. (2.5)

В первом случае - останов ( s =-<2 ).

Во втором - положить Cr{+( = Gi U {gi+ '}, { = (+1 и перейти К ШРГУ 1 .

Если х X то после конечного числа вычислений значений и субградиентов функции / последует останов е-процедуры. Если при отом окажетсячто s < е, то для некоторого . вычисленного d ç i Ofbf(x) выполняется неравенство

|d| £ Уф). ¡3 = ё/сг. (2.2' )

Если ю 1С Х^, то в процессе работы е-процедуры будут вычисляться последовательности сходящихся к нули положительных чисел {ё> и е-субгрэдавнтов (d>, d е d-f(x), обладающих свойством (2.2').

Если Î4e) s î]e, ч] - фиксированный положительный параметр, то для выполнения неравенства, |d| ^ Г(е) максимально необходимое чиолс К(е) вычислений значений и субградиентов функции f имеет, оценку К (е) = 0(e"z>lnze).

Для некоторых функций гфинятая в е-процедуре "привязка" к точке' х может оказаться малоэффективной. Следующее утверждение позволяет модифицировать е-процедуру в достаточно широких пределах . ' ' ' ■

'Т'е о р о м а 2.6. Пусть f - Выпуклая собственная на кп функция и для а;1 е йоги/, в, ^ 0, g ç 3 f{x{ ) при некоторых 1г е

1 i g [¡опт./, кг > О вгшолаятая неравенство

f(s^) >. '(2.6)

Тогда g t О, f(x2).

Пусть {?( с rs \ íj, е з е_1 > 0. Чтобы сопоставить точке Xй элемент sh е S^ достаточно выполнись следующие вычисления.

(A) Выбрать вк > ёА_1.

(B) К функции / применить е-процедуру с параметрами г е хр, £ = ек. После останова этой процедуры будут определены такие точка Iм е шп и число eJs > 0, что

/(i?) </(а*) - еА, (2.3')

причем, если < ск, то для некоторого вычисленного е dpfix), р г ё,4/а, а 6(0,1) выполняется неравенство

|<3*| ^ Т(ёк/о). (2.2')

(В) ПОЛОЖИТЬ sk a - 3*.

Для выпуклой функции / п.п.н.у. (А)-(В) Ро-замкнуго и может использоваться при отыскании решений различных типов экстремальных задач...

Для заданных е кп, t > 0 обозначим / = f ),

е. и) а rami/tzVts*)! i e io,t)J, . в,. ® ы /(a-Vrs*).

и * По

Т в о р о и а 3.1. Пусть некоторый алгоризпл безусловной .кини-лисзации функции f порождает f-последовательность и каждой

точке этой послевоважлъпости. по f-заиснутолу п.п.л.к.у. сопоставлен элелепт sk с S^k, Тогда если для некалорьа: фиксированного í > 0 и поел еОоажлънссш ítk), tA > í V ft, выполняется предельное соотношение

- wi - ' <3-'>

и« по крайней .»яро одна предельная точна послодователъносш iz*} принадлежит. ü Xo.

Для рвлаюхщиокного алгоритм условия сходимости можно несколько ослабить.

Теорема 3.2. Wyim. релсисаццотмй сигоршл порождает ^-посдедобсдаедйиост и локедыгые лепробдокия убМания fnA) фушеции / в точках (Л определятся по Р" -кбазиаию^толу правилу. Тогда если для ítertomopt<х ywmwjibu: б теареле Я.', i и и^З

выполняетея предельное соотношение (3.1}, то по крайней лерв одна предельная точка последовательности (х*} принадлежит Х^иХ3.

Если функ. дя / видукла, в у ограниченной и обладаэдэй либо свойством /(з^*1) $ /(а*), либо р(хь+1) < р(гг*) V & последовательности {хк} найдется предельная точка х ( Х^ и Х°, то сходится к множеству А^.

Если минимизируемая функция невыпукла, то условия сходимости алгоритма являются более жесткими.

Теорема 3.3. Если последовательность {асходтся к Х^, то для произвольных 1зк}

<3-2>

Д.1Я существования у Р-послеОователъности {з?> по крайней лере одной предельней точки из Х^ достшочно, чтобы для вычисленных по Р-зсиигнурому п.п.н.у. функции ? векторов 1зк), а^ е V & выполнялось предельное сооттошение (3.2).

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

Теорема 3.4. Пусть <хк) - Р-последовазпельностъ, ) < а участвующие в определении Свекторы ,

зк е V к вычисляются по Р-нвазизамкнутолу п.п.н.у. фунвции /. Тогда предельное соотношение (3.2) является достаточны.к условием сходилсст {г'4} к Хм.

Во зтороИ главе диссертации рассматриваются монотонные методы решения задачи

/(I) — ЗлГ, (4.1)

X '

определяемой непрерывной функцией /: к*1—ж.

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

. Г1"41 = £ = 0,1,2..........(4.2)

в котором начальное' приближение х с считается заданным, зл е С - направленна убивания функции / в точке хк, 0.

Пусть компактно множество

Î'S. tel /(г) ^ /(x°)>. (4.3)

Тогда множество решений задачи (4.1) также компактно, а объединение множества локальных минимумов функции / и множества Х° ее особых точек непусто.

Принадлежащая ограниченному шкжеству Х'\(Х° U Х°) или Г \Х„ и обладающая свойством f(yk+1 ) </(ук) V Л последовательность {уь} называется соответственно i/J' - или Р'-последовательностью.

Пусть векторы (s1'} в (4.2) вычисляются по 1п' -кввзизамкну-тому п.п.л.н.у. функции /. Если при этом для проязвольного фШССИ-рованного t > 0 шаговые множителя it^J помико условия

/(z*+1) ^/(лг*). к = 0,1,2..........(4.4}

также обеспечивают выполнение продельного соотношения

f(3^+t.eh) - e.(t) О. 9,(î ) s min f(xk+tak), (4.5)

* л ~ * ~ ostit

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

/(Afc.S*) a mln /(2^+ÎSfc). (4.6)

а но

Если жо л* U = , то условий (4.4)-(4.5) достаточно для сходимости (зг) к

В случае, когда яяирэвлвния (зл> вычисляются по Р'-квнзи-замкпутому п.п.н.у. функции /, значения. {/(г^)} 'не возрастает и

/(x^+tp1') - — О. H Inf /(Ais*). (4.7)

порождаемая согласно i4.2) последовательность сходится к Xt.

Вычислить шаговый множитель из условия (4.6) или

f(3*+tksh) > efc(£),

вообще говоря, нельзя. В связи с этим приведем практически реализуемые способы регулировки {îf£>, обесшшшэздиэ выполнение пре-дольного соотношения (4.Б) или (4.7), а значит, и сответстадщо-го типа сходимость алгоритма (4.2).

Теорема 4.1. Если лнахеаябо X' (4.3) колзштю, направленна Сз*} в (4.2) бъыис.шхпся по Р°' -кбазизалтутолу п.п.л.н.у. функции /, а д..я произвольных фиксированных 1 > О, "К ? (0,1] значения што&ы, то

/(Л^) < (1-Л)/(^1г)+Яейа) V Ь, (4.8)

то либо на некоторой итерации алгоритма будет получена точка из тожества и 1°, либо эполу тожеству принадлежит по крайней лере одна предельная точна генерируелой алгоритлол ограниченной последовательности {а?*}.

Теорема 4.2. Пусть лчохестйо X' шташмо, направления {зЙ> 6 (4,2) вычисляются, по Р'-нвазизалтутолу п.п.п.у. функции / и Оля произвольного фиксированного А. е (0,11 значения С> 6ы-бьратся из условия

f(2k^-tksl>} < (1-А)/(х3г) + \вгл V к.

Тогда либо на некоторой ияюрсщм алгоритм будет получено решение задачи (4.1), либо решвниел этой задачи является любая предельная точка генерируелой алгоритлол ограниченной последовательности, а*}.

В теоремах 4.1, 4.2 условие выбора шагового множителя tb на й-й итерации алгоритма (4.2) состоит в отыскании с заданной относительной погрешностью X «(0,1] значения соответствующей задачи одномерной минимизации функции Отметим случай, когда значение tk определяется из условия заданной точности решения задачи (4.6) по аргументу.

Теорема 4.3. Пуспъ множества уровней функции / котактны, = у ^ направления {зкУ в (4.2) вычисляться по Р'-квази-замшцтолц правилу, а шаговые лножтели {tk} удовлетворят неравенстваЛ К1к С tk V к, б которых Л. 6(0,13 - фиксированный параметр, - проивволътя почт мши.ау.йа функции г^О. Тогда при любоя началъноя приближении х° либо после ко-печ)юго'числа Ш!враций алгориша (4.2) будет получена точка из ■ множества Х^, либо этояу множеству принадлежат все предельные точки ограниченной последовательности (Л.

Пусть в задаче (4.1) множества уровней выпуклой функции / компактны. Для этой функции мошо определить Ро-замкнутое, а значит, и Р'-квазизамкнутое'п.п.н.у., что совместно с описанными ви~

Ев универсальными способами регулировки в (4.2) шаговых множителей равносильно созданию численно реализуемых релаксационных алгоритмов минимизация /. Однако свойства е-су¿дифференциала <Э£/ и е-процедуры, составляющей основу приведенного -замкнутого п.п.н.у. функции /, позволят доказать сходимость некоторых алгоритмов и без привлечения дополнительных ограничительных условий какой-либо формальной теории сходимости.

А л г о р и т м 5.1.

Шаг О. Выбрать конкретную реализацию г-!гроцэдуры, начальное приближенна х°ч о?п,

е >0. Полоить й = 0.

о

Шаг 1. Приыешгть е-процедуру к функции / с параметра-

ми х

-А

е е- е

V

После завершения работы е-процедуры будут онреде-

лены такие ^ е к

/(Xй) « /(сгл> - ё.

£, > о. что «

При этом если е^ < ел.. то для некоторых фиксированного а с (0,1) и вычисленного й^'с д^(з^), р = е^/о выполняется неравенство

¡(^1 ^ Г(ек/о).

гдо У: .!к - заданная монотонно возрастающая функция, , Т(0) = О.

Шаг 2. Положить х7"'1 = Xм, й = й+1. Выбрать е^ > 0 и перейти к шагу 1.

Теорема 5.1. Пусть при к > 1 парадеткр е^ б алгоритле 5.1

выбирается одних из следукюрх способов:

(б)

(в)

- f

а'

Тогда либо па некоторой терации 5 будет получена точна х^ из Хл, либо яно:юсп£у л^ будут принадлежать все предельные точки'генери-руелой алгоршиеоя ограниченной последоВаяюльност гх" >.

Пусть в задаче (4.1) Функция / выпукла, ее множества уровней

компактны д р(х) = min ¡x-xj.

г «х

Способ построения точек {хЪ, для которых

р(а*+1) < р(хА), ft = 0.1,2,..., (6.1)

основан на следующем угБервданзш.

Теорема 6.1. ßj/cmt> /: огп—jr - втунлая фунищя, х,у е к", ß € ö/(,у). g / О. Тогда если значение

Ii * <g,x-y>;\g\ .

неотрицательно, ш.о бдя точки z = х - hg/ \g\ справедливо неравенство рг(г) $ рг(х) - /гг.

В условиях теоремы 6.1 г - проекция х на гиперплоскость

(v> е <g,w~y>*0>,

огдзлищой х от Хм. Местоположение определявшей эту гиперплоскость точки у легко установить из субградиэнтного неравенства

fW~f[y) > <g,x-y> Vgcö/(y). (6.2)

При h|g| = <g,x-.y> > О из (6.2) следует f(y)<f{x). Значит, каждая указанная в теореме б.1 точка у может быть представлена в виде у = х s х + to, s € 'S , t > 0.

Если tt = argniln(/(x+ts)| t > 0) - наименьшее решение задачи .

• 7(x+iö) —» min, tio

то для произвольных gt e 6/(xi), t e (0i ntlgtl*<ßt.x-xt>=-t<gt,B> > 0

и поэтому точка

Zt = X + t<gt;3>g/\gt\Z (6.3)

находится к Хч ближе, чем точка х. Это приближение z± к будет максимальным, если t и g в (6.3) выбирать из условия h = -t<g t,a>/|gJ — sup sup .

Корректность указанного способа выбора t и gt обосновывают сле-дующис утверждения;

Дли х £ з е ¿'^ и t > О определим функцию

h{x,s,t) s зир {-i<g,o>/[g|). g<df(xt)

При фиксированных х,з эта функция на интервала [0,^) полунепрэ-рывна сверху. Так как Л(х,з,0) = 0,

t € СО, Мх.зД) >0, t > 1ш П(х.з^) 4 0,

то максимальное значение функции Щг.з.«) на множестве положительно и достигается в некоторой точке интервала (0,^1.

Обладающие свойством (6.1) точки порождает Алгоритм 6.1.

Ваг 0. Выбрать произвольную точку к" и положить к = 0.

Шаг 1. Если хк е Хш, то останов; иначе вычислить элемент з* е Э к.

X

Шаг 2. Вычислить ^ > О и ^ е Э/^), у* з хЧ^з*. для которых

t.<gk,sk> . .

71 =—5--— ша2 .

.* |в"| но

Шаг 3. Положить = а? ~ Ь.^/Ь = й+1 и пе-

рейти к шагу 1. '

Генерируемая алгоритмом 6.1 последовательность {.хк) обладает свойством |г*+1-.г*| — 0. Поэтому на классе таких последовательностей и определяется свойство замкнутости (Р^ замкнутости) правила построения направлений (зк).

Теорема 6.2. Пусть лнохест&а уровней Выпуклой фугисции / коллатси, а векторы Сзк) в алеортле 6*1 бьс-чсляапся по Р,-н6а-зиоалкнутолу правшу построения направлений ее убивания. Тогда генерируетя эгаиа алгсритлол последовательность (Л лонотонно сходится к Х^.

При э ^ 5х £ 0 найдется единственная точка г с (0,г4), дяя которой

г < -г , если í е ю.х), (б..г)

I <8х,з> > -г, если t > г, П|)И любом е 0/{х%).

Т н о. р е м а б.З. Пусть выюлняюяся пред!изложении т>ю 1<е.е.н 6.2

■л при Уекоторол фиксированно* X. €(0,1) значение tfc на итерации к = 0,1,2,... алгоритма 6.1 выбирается удоблетворящил неравенствам Kik < tk < V ft, eöe 6 (6.4) ik=í, г* н X, si* S 3. Тогда этот сигоршм либо прекращает работу в точке тожества Х$, либо порождает лонотонно сходящуюся к Х% последовательность {хЪ.

Пусть функция /:кп—.к дважды непрерывно дифференцируема и при некоторых 0 < я < М имеют место неравенства

и|у|г <y,^f{х)у> Jí|y|2 V х, у е к".

Тогда если в концептуальном алгоритме 6.1 выбор (3a) подчинить условию

<зfe,v/(rJí)> <-a|v/(i*)J, |зк| = 1, а €(0,1) - произвольный фиксированный параметр,

то генерируемая последовательность приближений {гЪ сходится к единственному решению х% задачи со скоростью геометрической прогрессии, знаменатель ц которой удовлетворяет соотношению

2 _ Г ш

= 1 [ Щ9+Ьа)1уг J .

Далее в диссертации предлагаются практически реализуемые версии алгоритма 6.1. Описывается модификация е-процедуры, ориентированная на построение обладающих свойством (6.1) точек (,zA>.

В третьей главе диссертации рассматриваются методы решения экстремальных задач при ограничениях на переменные.

Пусть в задаче

/„(я)—min, . (7.1)

хеО

. П 5 {г| <р(х) $ 0), ф(1) s шах|/{(х)| i € I s <i,...,ra)j

минимизируемая функция /о: Rn —► R U (со) на допустимом множестве I) принимает конечные значения и непрерывна, функции </{), /{:кПг— —£ € Г непрерывны и 1пШ = {.т\ <р(х) < О) / 0.

Пусть Щх,у) = max{/o(z)-/o(t/),(p(í))' V х е кп, ¡/ f 0, О с 1пШот/о) и"опрвдолявдие задачу (7.1) функции {/,) выпуклы. Тогда при произвольном фиксированном у £ П функция Н(-,у) выпукла и собственна, я ее е-субдоДеренциал

djl(x,y) - <ß с Rn| ¡!{z,y) > Н(х,у)кg,z-x>-c V z е жп)

при любых х с П., е > 0 является непустым выпуклым компактным множеством ( Q с lnt{dom/i(>,y)] V ус П ). Кромэ того, т.м.о. 3.Ji(., •) замкнуто на Q * il *

frb.it/*} с Q, <е } с к g* i

к

3* X, у* — у, Ск — е, • g* — g

в е öjHx.y).

Теорема 7.3. Необходима и бостапочнил условием принадлежности тачки х^ множеству решений Х^ задачи выпуклого программирования (7.1) является вкоачение 0 с д!1(х^,хг).

Для решения задачи (7.1) применим один из вариантов метода центров ~ Алгоритм 7.2,- по форме сошадеглций с Алгоритмом 5.1, в котором ^ П, а па шаге 1 каждой итерации к /(•) нЩ.,^),

Теорема 7.4. Пусть тожество Н(х,х°) $ 0> ограничено и при й > 1 паралепр ер в алгоритме 7.2 выбирается одним из следующих способов;

(а) [/„ (!*)-/„,)7. 7 > О;

(О) ел > /„(г*"1) - /Л(л*>;

(б) еЛ » .

Тогда либо на некоторой итерации й будет пдлучепа точка х^ из компактного множества решений Хш задачи (7.1), либо генерируе.шя последовательность (Л сходится к I,

Пусть задачу (7.1) определяют выпуклая собственная замкнутая функция fn: к"—^ и выпуклое множество П г йощ/0. При этом, если (1от/о? 0, множество О замкнуто.

Для решения рассматриваемой задачи разработан метод условных Е-субградиентоб (Алгоритм 8,2), имеющий ту же структуру, что и Алгоритм 5.1. Отличие между указанными алгоритмами появляется лишь на 'этапе линейного поиска е-нроцэдуры внутренней аппроксимации условного е-субдяфференциала

3 > /0(х)+<в.у-х>-е V в < Ш.

Пусть в задаче (7.1) П ? I (1 Г X, ), К н ( (х) < СП V 1 С Т г ¡1.....т>,

(/.} - выпуклые собственные замкнутые на Rn Функции, а выпуклое

множество X содержатся в dorn/..

<<=1 4

Предположим, что поиск решения задачи (7.1) проводится лишь в пределах множества X и имеется возможность отличать принадлежащие ШХ точки. Кроме того, если i

х € хЛ1Л = IntX П Г П

L lel 4 1

intxt = {у е 1пг(аотц/4)) ft{y) < 0) vier,

то можно вычислить значение /о(х) и какой-либо субградиент g° е f 0/о (а:) минимизируемой функции fo, а если

х € int* с Г П int (dorn/,) 1,

L icl . '

то аналогичная информация может быть получена о казвдой функции-ограничении Если же i е XMntX, то можно вычислить нену-

левой элемент нормального конуса ll(xlX).

Для х £ 1пШ, ä е э"/о(г), d -ф О, е>0 рассмотрим задачу

fa(xt) — Inf, xt в x-td е lntd, t > 0. (8.1)

Точность минимизации функции fa в этой задаче (цель линейного поиска модифицированной е-процедуры) определим выполнением одного из условий:

(Л) найдена точка х £ (Д^ | t 2 0) П intft, в которой

/0(зё)<>0( х)-е;

(В) вычислен ялемент g £ д^/о(х), удовлетворявший для заданного ае (0,1) неравенству

<g,ä> < a|d|2. (8.2)

Для принятого способа задания множества О предположение xt с £ IntO равносильно тому, что

xt £ mu и < о v i ? г.

Ввиду выпуклости множества X и функций (/4), для некоторых t', ■ V £ К , О < Г i: t" (возможно, что t'~ со и/или Г= «)) справедливы утверждения: AlntX;

t с fO.Г) е. £ IntX; i £ CO.i') => < 0 ^ f Л

i e Ir.tr) ^ <g',d> <0 v ( a/tut), £ e

где 1+(у) з {£ е Г| /{(у) > 0>.

Пусть Га.Ы - интервал локализации £' и

< /о<Ха> > /о^)-8' ^а'^ > ва е ¿»/"о (*а> (УСЛОВНО (Л)

не выполняется и минимальное значение функция ) • принимйет

при г > а). Тогда для произвольных I с ? 0/{ (хь)

при Ш. э ——2-2---5-

-Г{(хь)~ъ<в1ь,а>

В - + € ФоОО-. . (8.3)

Пусть теперь 0 ^ а < Ъ - V = V < «. Тогда при любых ¿'а с

Я = + б»? е (8.4)

Если интервал Са.Ы содержит точку минимума функции /0 (л.^>, * » О, 0 < а < Ь < Г и тп1п(/о(.ха),/о (хь)) > /а(х)-в, то

В * А^+О-М^ € 0в/о(х) 5 <£/о(зг), (8.5)

где X з

Ъ<&,П>-а<&,<3> '

если ,й> > О,

1, если <8°а><1> = О-

Наконец, если при локализации точки мшшмума функции /0(;г4), а = О или £> —><о (£'=£'=«), то можно .обеспечить выполнение либо неравенства /а№ь) £ /0 (л:)-5, либо неравенства (8.2) совместно с неравенством ,

Л,<*>-/„(^)-(кё°ь>с1> « е. £ е б/оиъ).

В этом случае

В*£ь<ОсГ„(I) е в°/„(*). , . (0.6)

При минимизации функции /,, (а^), г > О никакого другого мес тоположекия точек о и Ъ бить не может. Кроме того, если длина интервала [а,Ь] достаточно мала, то выполняется (8.2). Теорем а В./. Для задевших х ( ШП, й е кт'\(0>, г, > и.

а е(0.1) пасje конечного числа вычислений значений и субградиентов функций ц </{}, t (. I в тоннах множеств соответственно {я • tïO) Г! intfl. и {xt| г>0) П intX ложно обеспечить выполнение условия (Л) или (Б).

Теорема 8.2 используется при обосновании корректности принятого способа внутренней аппроксимации условного е-субдифференциа-ла. Условие сходимости Алгоритма 8.2 дает

.Теорема 6.3. Пусть лножестВо решений Хш задачи (7.1 ) непусто и колпатно, х°е intiJ, при й > 1 параметр ек в Алгоритле 8.2 выбирается однил из указанных в аеореле 7.4 способов. Тогда если на некоторой итерации 5 этого алгоритм не будет получена точка 2.V i Х^, то из ограниченной последовательности ix1*) с intQ ложно выделить подпоследовательность, все предельные точки кото-рай будут принадлежать лнохеатву Х^. Если хе функция /о m Xl неп-реривна. то Хш принадлежат все предельные почт последовательности ixk},

• Пост-оптимизационный. анализ каадой задачи математического программирования обычно йключает исследование воздействия на ее значение и решение неизбеаашх погрешностей вычисления значений составляющих ату задачу функций. Поскольку вектор Куна-Таккера определяет субградиент функции чувствительности задачи выпуклого программирования (ЗВЩ,.о степени относительного влияния указанных погрешностей на значение ЗВП мо!кю судить по результатам сопоставления между, собой множителей Лаграяага. В диссертации показано, как в процессе работы Алгоритма 8.2 без особых вычислительных затрат можно получать состоятельные оценки вектора Куна-Таккера .

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

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

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

Рассмотрим ЗВП в следующей постановке:

fjx) — sup, (9.1)

/tU)>0, í е Г, = (1.....и,}, (9.2)

fiW = О. í € 1г з {гц+1.....m), (9.3)

ifJt, (9.4.)

где вогнутые собственные замкнутые функции >, i i rtU{0> определены на к" и принимают значения из 8?, функции {/{>, Л € I йф{;;тш, множество X s выпукло.

Для Í ? I s 11 и I обозначим

f ix\ JAx) > 0). если Iii., <• л

í з 4 1 О 3 * n { П ]•

, I tal JAx) = 0), если I ( 4 1 i ei 1 J

i С- f

Задаче (9.1)-(9.4) сопоставим двойственную sodávy

Ф(и) — Inf, (9.5)

ueU

в которой U s (u Í U, » 0, Í С I,).

supíbCr.u) I x с X), если u g U,

v:

ф(м) -

В протиге.'.'-м случае,

Их.и) з /0(х) +<u,F(x)>, F = (/,.....fm).

В дальнейшем будем предполагать, что значение /* ЗВП (9.1)-(9.4) конечно, множество ее решений X* компактно,

intX jí'p, X я int (dorri/o) Л [ П lnt (dony"i) ]

leí-

(для вогнутой полиэдральной функции онераци» "int" в этой записи можно исключить) и для некоторой точки х'i intX

/t(x' ) > О,: 1 е Г;, /{(х')> О, 1(1',

/4Сг') = 0. i е Гг.

где s {1,...,щ;з, О с п'х $ яц, IJ з Г,Ч XJ, U - множество номеров аффинных функций. Тогда для задач (9.1)- (9.4) и (9.5) отсутствует разрыв в двойственности (/* = ф^), множество решений задачи (9.5) непусто и выпуклая замкнутая функция <|> собственна. Будем также предполагать, что'«юставлявдиз ограничения (9.3) аффинные функции / (x)^<a.i i е Г2 определяются линейно независимыми векторами (а*} и, значит, множество решений Ot задачи (9.5) компактно.

Приведем условия, при которых множество lnt(doire|)) непусто н может быть представлена в виде

Int(cloiHt>) = (u е intíf| hj (u) < О ' V J е J), (9.6)

где ííi^), j t V - коночная система выпуклых непрерывных на Ü Функций.

Обозначим

Х(иУ в íx е 1(х,и) = ф(и)), (9.7)

U' = ju € IntííJ (I0+)(J/,U) < ü V У € 0+X\{0)j,

(Ю+)('у.и) в (/о0+ -с 2 и^О+Ну), leí

где О1"А', /0+ .- рецессивный конус и рецессивная фуншда соответственно множества X и функции /.

••' Теорема 9.3. Для. произвольного и с W множество X(ti) непусто выпукло и комшптю. 'Кроле того,

irit<(lom;|>) е (/'£ cloimji. (9.8)

Из соотношения (9.8) следует равенство lnt(domi|>)-intU'.

Bi

Кроме того, при 0+Х П D = <0>, д т f~] dorry',0+

1-0 4

Int(doiixJ)) = InW. (9.'9)

Следствие 9.3.1. Пусть в ЗВП (9.1 )-(9.4) либо множество X компактно, либо по крайней мере одна из функций (-/{>, i € е I^U (0> кофиншта. Тогда справедливо (9.9).

Если 0+Х (1 D - Ш)" то имеет место соотношение (9.9) к в этом случае система функций

hjiu) В -и j е J = (1.....

свойством (9.6) очевидно обладает.,.

"Предположил теперь, что 0*Х П D\(0> f 0. Пусть J' е J - конечная система компактных подмножеств

из каждое из которых не содержит начала координат и

0+Х П D s U ff , jsJ

где Kj з K(Qj) - порожденный множеством Qj замкнутый конус. Например, Qj - выпуклая оболочка единичных векторов, опрэделящих ортант в к", J е J 5 {1,...,2").

Без ограничения общности будем считать, что

Y з 0+Х П D П Qj / 0 У J € J.

Для каждого J с ,1 определим на в?"1 шпунлуп непрерывную субдиф$еренцируемую на U функцию

г supl(ixf}(y,u) j у € Г ), если и-а и, h Ли) н ^ 3 t ® в противном случае«

Теорема 9.4. Ясли 0fX П й\(0) f 0, то {/' = Си е'1пШ| hjiu) < О V i f Л.

Теорема 9.5. Множество lnt(dom:|>) непусто тогда и только тогда, когда

Inf шах hЛи) < 0. и j«/ J' . «

Для лиогеапва 1ти(с1ошф) бтолшежя соотношение (9.6).

Достаточное условие регулярности задачи (9.5) дает

Теорема 9.6. Пусть рецессивный конус 0*1 содержится в " -

г! Шояу^О4) и не содержит прямых. Тогда если из условия сов-

1=--0

местности системы

(/<0+)(у) > О, { е (/{0+)(у) = 0, £ е 1г, у € 0+ХЧ(0) следует существование точки у'е г!(0+Х), в которой

(/,о+')(у;) > о,' { € г,. (/4о +)(у-) =о. игг,

то ШШом))) * 0.

Более' сильное утверждение о йошф может быть получено в предположении, что в задаче (9.1)-(9.4) функции {-/(> и множество X полиэдральны. • 1..

Теорема 9.8. Если в задаче (9.1)-(9.4) функции (-/{> и множество X полиэдральны, то

йоюф з (и е 1Г| (10*)(у,и) € 0. V у € 0+£ >

и множество Х(и) (9.7) непусто для цроизвольного и € йоюф. Яри ртом если значение задани /* конечно, то <|> - полиэЗрсиьшя собственная функция, в йотф и Х(и) - полиэдральные множества.

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

В общем случае удается вычислить лишь "близкую" к множеству И точку и. Поэтому боссжп'ювление решения исходной задачи (9.1 )-(9.4) из условий

/0(аг) = 'ф(и), й4/1(х)=0 У 1 С I, 1(0 (10.1)

может вызвать определенного рода сложности.

. Если для решения задачи (9.5) применять Алгоритм* 8.2, то при любой точности решения этой задачи можно вычислять состоятельную оценку решения порождающей ее. задачи (9.1)- (9.4). Вычисляемые оценки решения этой задачи можно использовать как для корректи-

- гз -

ровки параметров Алгоритма 8.2, так и для формирова!ия критерия . его останова.

При сделанных предположениях задача (9.5) эквивалентна

ф(и) — min, (9.5')

u«7

V = I/ (1 íu| hj(u) $ О V / с J)

(если 0+Х П D = то hj(u) = -u V J е J = О.....m>) и при

этом Int (йошф) ¡¿ 0.

Будем также считать возможным вычисление в произвольной точке и € Int(don*})) какого-либо элемента х множества Х{и.) - íx é Х\ . |I(a:,u) = (j)(u)> и значений ífl(x)}. Если же и с íBti/\üvt(doro|>) И hj (и) > 0, то можно ВЫЧИСЛИТЬ точку

у е г, (и) з Íy С (ХО+)(г/,и)=^(и)> и значения ((/{0+)(у)>.

Для u е йолх)), s^O обозначим Хй(ц) з ix е Jf| I(X.U) » ф(и)-е), Ха{и) Х(и). . (10.2)

Множество Хс(н) выпукло и замкнуто. При и € int(dcm<{>), е > О множества Х(и),Х£(и) непусты и компактны.

Теорема 10.1. Из условий и е аоюф, е > 0, х с Хе(и) следует Р(х) í d£tp(u).

Теорема 10.2. Пусть и1 е doro]), е, > О, х е ^(u1)- loada если Оля е£ > 0 8 точке u2 g dorrxj) выполняется неравенство

'['(и1) > с|)(иг)+<?(о:),и1-иг>+е1-ег,-

то х í Хг(иг).

"г *

Основу применяемого для отыскания решэшя задачи (9.5') Алгоритма'8.2 составляет е-процвдурэ внутренней аппроксимации е-су-бдифференциала б ф(и) (в рассматриваемом случае У a dornj) и поэтому З^ф(и) = 0/J>(u) для произвольных и е йотф, е > 0). На одном из простейших вариантов е-продадурн покажем, как можно вычислять состоятельные оценки решв!шя задачи (9.1 )-(9.4).

Пусть для заданных u е Intt = int(dorttj)), d í Rmv{0) на интервале Га, íj 1 локализована точка минимума задачи

ф(и.) — min. u s u-td (10.3)

. .C {t>-01 ute V}

Рассмотрим случаи возможного местоположения а и b.

Предположим, что uq с intr и <ga.d> >0 V gQ е бф(иа) (решение "задачи (10.3) расположено на числовой оси справа от точки а).

Пусть иь е Int,V. Гели а > О и для заданного е > О

ж1пСф(иа),ф(иь)} > ф(и)-е. (10.4)

Тогда

g в Aga+(1-X)gb с 0Лф<и). (10.5)

где А s b<gb,d>/(b<gb,d>-a<ga,d>), g, s №.), x, e I(u,). Если же ' а = 0 и t{i(uH|>(ub)-b<gb,d> ^ е, gb е Р(ггь>, то в s вь t дсф(и). Вичислязмому указанными способами твэктору g е Зсф(и) сопоставим точку

3? а АХ + (1-A)Xh € ¿Uli). (10.6)

d • О

где, если а - О, К = 0.

В случае, когда ufc £ int7 предположим сначала, что иь с i lnii/\ IntV. Тогда et;ли выполняется нэравзнстао

ф(иа) > ф(и)-е, _ (Ю.Т)

то •

В s 8а+Щь £ ЗсФ(и). (Ю.8)

где ga в Р(аа), j?a-€ Ша),- дь.в (iO+)(yb) € öh,(ub), fb € tyV' j € J+<«b> « f/ С J| n^i«,,) > w = [ф(иаНе-ф(и)+асга,0>]/р^. pJb в (ub)-b<qb,d>. Сопоставим доктору g точку ,

(10.9)

Пусть, наконец, UMnXU и q e Я(иь|У) - вектор нормали к множеству U ■ в точке . ufe, |q| .= т. Тогда если выполняется неравенство (10.7), то

g г g^+uc? € а^ф(и), (10.10)

гдо- 5^(u)^(ua)-G~a<ga,d>^j/b<7,d>. Вектору g сопоставим точ-

ку я® з ха (в формуле (10.9) уь = 0).

Если длина отрезка Со.Ы достаточно мала, то для вычисляемого по одной из формул (10.5) или (10.8) вектора g для заданного

а е(0,1) выполняется неравенство

<g,ü> § a|cl|2. (10.11)

Теорема 1С.З. Пусть ваваш и € int7, а с к"\{0}, е > О, ас (0.1). Тогда после конечного числа вычислений значений и субградиентов функций ф ц (hj} соответственно в точках тожеств {u-id| t > 0) П int? и intU ложно либо отекать точку ö t lntF,

для которой

ф(й) i c|>(u)-e, . ' (10.12)

либо вычислить облайаящий свойством (10.11) элемент g е б <J>(u). При зтол указанному е-субградиешу g можно сопоставить точку Iе € удовлетворяющую условиям

>8l Vie i\iaff, /,(**) = g{ »U iaff

где I - тожество номеров аффинных фушеций С/.), £ с I. iff 1

Пусть заданы параметр а е (0,1) и. монототю возрас/гащоя на к4 функция Г, Г(0) = 0. Для и е IntV и е > 0 рассмотрим следующий вариант е-лроцвдуры внутренней аппроксимации бсф(и) и одновременного вычисления оценки решения задачи (9.1)-(9.4).

е-процедура 10.1.

Ваг 0. Вычислить х° е Z(u) и g° п Fix").

Если g° = 0, то останов ( и е Uf, х° е X* •). Положить (f= в", G0= (g°), 1=0.

Шаг 1. (Линейный поиск). На множестве <ut= u-td11 t > 0) П IJ локализовать точку минимума VfyHKUHH <]) с такой степенью точности, при которой либо будет получена удовлетворяющая неравенству (10.12) точка ü € inxV, либо будет вычислен элемент g1+'tz di:ty{u), достаточно сильно отлячакжеийся от dl:

<ßl+',al> < а|Г.г|г.

В первом случае - останов.

Во втором е-субградиенту gu' сопоставить точку.

г1+'е обладающую свойством

' /((1и!) > В?1

Шаг 2. Выбрать произвольное подмножество С е (возможно пустое), положить С £ С(31} и {£г+1} и С и найти решение задачи квадратичного программирования

1с2„|г ш1п,

Ь*-'- «е-«?

(здесь р - число элементов множества О).

Ваг 3. Положить и {£1+'),

к=}

н е-субградаенту йг+| е й£ф(и) сопоставить точку ■

» 1 I»? •

- А=>

( г^ - связанная с в*' е С точка множества (и) ). Шаг 4. Если 1<Зг*'| ^ У(е) , то Останов; иначе положить 1=1+1 и перейти к шагу 1.

Теорема 10.4. Пусть для решенья задачи (9.5') применяется Ангорипл 8.2, исполъзукщий е-процедуру 10.1, а значение выбирается согласно однолу из пробил:

(о)

<е> > '

(г) для фжсиробаннщ Т,«72 > 0

¡¡'огсМ справедливы утверждения:

генерируемая- алгоритмом послейовшюльность {ик> ое^мничена;

ложно указать подпоследовательность iuk), k с К * ik{i а {1. 2,3,...}, все предельные почии которой содержатся в тожество ре-тений UI задачи (10.6);

из того, что подпоследовательность (и*), Й ç К'я К сходится к точке и следует принадлежность тожеству Q П Х(и) всех предельных точек последовательности lxk~>, k ç К'.

Далее в диссертации предлагается способ одаовремешгого решения задач (9.5) и (9.1)-(9.4).

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

Пусть {J?jL Ï = 1,...,р - заданные на жп функции, Я s tRr-. Обозначим По s П и для Ï = 1,...,р

OjS^ïeO,,,! Р, (х) = min Pj (y) j (12.1)

Р-критериальная лексихографичеаюя задача утилизации fЛОМ)

состоит в отыскании какой-либо точки х. е Q и/или значения

* р

F, 3Ï (I,).

р* р *

Перед началом ft-й итерации алгоритма решения задачи (12.1) предполагаются известными текущее приближение ук с Q к шожеству йр1 и положительный параметр efc (регуляризукэдая "уступка").

На текущей итерации к вычисляется приближешюе допустимое решение xh = задачи

F (я)'— min, (12.2)

Рг(х) $ Рг(/)+еА, I = .1.....р-1, (12.3)

ХЕЙ. ' (12.4)

• Переход к последующей итерации состоит в построешгИ точки yki1 i П и выборе значения ек+1 >0. .

Для приближенного решения задачи (12.2)-(12.4) -предлагается использовать Алгоритм 8.2. При указанном в диссертации условии останова этого алгоритма все предельные точки генерируемой последовательности (А являются решениями задачи (12.1).

п пр

Пусть /; ж * » к —.к - выпукло-вогнутая функция, <р , ср2 -- конечнозначные и выпуклые соответственно на к и к функции, X Я 9,(10) < 0>, Г = СиI <рг(и) <0} и для фиксированного

__• _ • п _ п

2 хек1, у (. к

Я(2,2) £ ШаХ{Р(2,2),ф(2)>, Р(3,2) э ? [Х,у)-?&,у),

п1 "г

<р<г)-ё тах^р, (х),ч>г(у)}, V г Их,!/), ие . & е к .

При произвольных 2,2 е к", п ^ п1+гг2 субдайеронциалы

дР(2,2), 0И(2,2) функций Р(-,2), в точке 2 - непустые

выпуклые компакта.

Теорема 13.4. Если определятся тожество

2 = <2Г( ср(г) $ 0}

фушщия <р регулярна по СлеЩеру, то принадлежность точки г% лно-хестду сеЗловыт точек функции / на X * У ' равносильна включению

0 б.

Теореме 13.5. Лусиь = {г| О е дН(г,г)У * 0 и От

заданных 2°, 2 е к"

Г аР(2,г), ё£т ф(г) ^ О,

(7 <; | _ _ |6'| ?! О.

0р(2.), если <р(г) > 0-,

Човйа если П з <С,2°-2>/|С| >0 и 2Л г 2°-/1С/|С|, ИО

гбе рСгг). ^ ш1п |г-С|.

Итак, если < Zif , то значение функции У{• ,2°) в точке г° можно уменьшить.

Пусть ' - направление убывания функции Н(>,г°) в точке г". Если 2° £ г, то - направление убывания функции ф в точке г° и поэтому при достаточно малых Г ^ О при любом С е )

выполняется неравенство <С,5°> < 0. Если же е 2, то при малом I ^ О 20+13° ( г'и указанное неравенство выполняется при любом б е <ЗР(г°+г5°). .

Таким образом, если 3° - направление .убывания функции Н(-,г°)

в точке 2°. то при достаточно малом О для точки = выполняются условия теоремы 13.5. Значит, можно определить точку г1, находящуюся ближе к чем точка 2°. Затем, если я1 / определить направление убывания й1 функции Н( ,11) в точке г1, выбрать 2Л з zx+t Б* , £., > О и построить точку, находящуюся ближе к

чем точка 21 и т.д. Для заданного начального приближения указанным выше способом моьио либо построить последовательность {гк), точки которой монотонно приближаются к либо при некотором Ъ. окажется, что

й » -

Далее в диссертации предлагаются способы'выбора (5 > и С,

обеспечивающие монотонную сходимость {2Ь) к

В заключении перечислены основные результаты работы:

1. Разработана теория сходимости и локальной сходимости алгоритмов безусловной минимизации непрерывных функций. Условия сходимости представлёш в терминах значений и замкнутых (ивазизамк-нутых) правил построения направлений убывания минимизируемой функции.

Применение разработанного формализма позволяет более : /Око ор-х'ашзовать регулировку шаговых множителей в алгоритмах, в которых вычисляются направления спуска..

2. Для произвольной непрерывной выпуклой Функции разработано замкнутое правило построения направлений убывания, составляющее основу большой группы методов выпуклого программирования. При практической реализации этого гравила может учитываться в ггр; .гци-пе вся получаемая в процессе вычислений информация о значениях минимизируемой функции, ее субградаентах. и траек ории поиска. Объем, тип и способ обработки используемой информации определяются размерами решаемой задачи и могут устанавливаться достаточно произвольным способо;,:. .

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

4. Для с>бдей задачи выпуклого программирования разработан практически реализуемый имриаит метода центров.

5. Предложен конструктивный способ описания внутренних точек ■лДОективнего мнозвсгва двойственной функции произвольной задачи внпуоого програмлгарования.

6. Предложен способ вычисления условных е-субградаентов.

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

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

8. Разработан метод условных е-субградаентов решетя многокритериальных лексккографетоских задач выпуклого программирования.

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

Основные положения диссертации опубликованы в следующих работах:

1. Ржевский C.B. Об одном принципиальном алгоритме минимизации випуюшх функций // Кибернетика. - 1979. - Й 6. -С. 13-14. •

2. Ржевский С.З: Использование е-субдифференциала выпуклой функции в одном методе ее минимизации // Кибернетика. -1980. - Я 1. - О. 109-111.

3. Ржевский C.B. Об одном унифицированном подходе к решению задач безусловной минимизации //Журн. вычисл. математики и мат. физики.-1980.- 20, Я 4.- С.857-863.

4. Ржевский C.B. Замкнутые отображения в задачах безусловной минимизации выпуклых функций //Кибернетика. - 1980.

5.-'С. 105-112.

5. киевский C.B. О некоторых способах построения направлений убывания негладких выпуклых функций в е-субградиен -vaux методах минимизации. - Киев, 1981. - 13 е.- Ден. в

ВКНИ'ГМ 27.-08.81, Я> 4232 - 81.

6. Ржевский C.B. е-субградиентный метод решения.задачи выпуклого программирования // Журн. вычисл. математики и мат. физики. - 1981.- 21_, № 5.- С. 1126-1132.

7. Ржевский C.B. Монотонный алгоритм поиска седловой точки негладкой функции //Кибернетика.-1982.- № 1. - С. 95-98.

8. Ржевский C.B.. Кунцевич A.B. Применение е-субградпент- ■ ного метода для решения двойственной и прямой задач математического ггрогряммировашя //Кибернетика. - 1985. -Jê 5. - С. 51-54.

9. Ржевский C.B. Метод условного е-субградиента решетя задачи выпуклого программирования //Кибернетика.- 198"/.

- № 1. - С. 69-72.

10. Ржевский C.B. Метод условного е-субградиента решения двухкритериалыгой лексикографической задача минимизации //Кибернетика. - 1937. - J6 4. - с. 123-124.

11. Ржевский C.B. Конструктивна способ описания эффективного множества двойственной функции // Докл. АН СССР.-1988. - 30L. № 6. - С. 1325-1327. ' .

12. Ржевский C.B. е-субградаеит1Шй метод одновременного решения двойственной и прямой задач математического программирования // Методы оптимизации в экономико-матема-тнческом моделировании. - М.: ЦЭШ АН СССР, 1988.

- С. 172-198.

13. Ржевский C.B. Конструктивное описание эффективного множества двойственной функция //Кибернетика.- 1989: - № 1.

- С. 50-54.

14. Ржевский C.B. Метод условного е-с.убградяента одновременного решения двойственной, и прямой задач выпуклого программирования //Кибернетика.-1989. - X 2. — С. 54-64.

15. Ржевский C.B. О структуре метода условного е-субградиента одновременного решения прямой и двойственной ¡задач выпуклого 1фогра?,'лировя!шя//докл. АН СССР.- 1990. - 311, Ü 5. - С. 1Ur>b-inrirJ.

16. Р.кевский C.B. Метод условного е-оубградиента одновременного решгая прлмоЯ и двойственной задач выпуклого программирования //Кчо'ерпетика. - 1990.-- .4 ?_. - С. 113-119.