Содержание к диссертации
Введение
Глава I. Методы погружения до минимизации гладких функций п
1.1.. Метод обобщенно опорных гиперплоскостей для решения задачи математического программирования II
1.2. Метод типа условного градиента с частичным погружением допустимого множества 19
1.3. Итеративная регуляризация одного варианта метода типа условного градиента с погру
жением допустимого множества 28
1.4. Проекционный метод с погружением допустимого множества 38
1.5. Вариант метода Ньютона с частичным погружением допустимого множества 46
Глава II. Релаксационные субградиентные методы минимизации 54
2.1. Две общие схемы отыскания точки выпуклого множества, использующие его погружение 54
2.2. Релаксационный субградиентный метод минимизации строго выпуклых функций 63
2.3. Конечный метод отыскания точки выпуклого множества 67
2.4. Метод условного , - субградиента 74
Глава III. Решение тестовых и прикладных задач 82
3.1. Решение тестовых задач методом условного - субградиента 83
3.2. Применение метода типа условного градиента с погружением допустимого множества для решения задачи синтеза инфор мационно-управляющей системы (ИУС) 95
3.3. Применение метода условного - субградиента для решения задачи выбора опти
мальных времен функционирования подсис тем ИУС 100
Заключение 107
Литература
- Метод типа условного градиента с частичным погружением допустимого множества
- Проекционный метод с погружением допустимого множества
- Конечный метод отыскания точки выпуклого множества
- Применение метода типа условного градиента с погружением допустимого множества для решения задачи синтеза инфор мационно-управляющей системы (ИУС)
Введение к работе
Построение методов решения задач нелинейного программирования и их численная реализация постоянно пользуются вниманием математиков-вычислителей. В тесной связи с разработкой методов находятся и вопросы оценки их эффективности (см.,напр., [15,47,49, 66,67,69,84,90] ). К настоящему времени накоплено значительное число методов минимизации нелинейных функций, складывается определенная их классификация. Различные подходы к построению методов решения нелинейных экстремальных задач предложены в [1-3,6,9,17, 18,23,44-46,48,50-52,55,63-65,68,75,79,81,83],и этот перечень работ далеко не полон. Среди упомянутых можно найти работы, посвященные методам минимизации выпуклых и невыпуклых, гладких и негладких функций. В последнее время большое внимание уделяется разработке методов минимизации недифференцируемых функций. Остановимся на некоторых из них подробнее.
Большую группу методов минимизации негладких функций образуют так называемые субградиентные методы. Одним из первых представителей этой группы является метод обобщенного градиентного спуска (ОГС), предложенный Н.З.ПЬром (см.,напр., [94]). В дальнейшем субградиентные методы разрабатывались в [20,21,28,29,59,62,72,76, 77,94,95]. Для ускорения скорости их сходимости были предложены варианты метода ОГС с растяжением пространства ([94 - 96]). В [41, 42] Я.И.Заботиным, А.И.Кораблевим, Р.Ф.Хабибуллиным метод ОГС был распространен на задачи минимизации квазивыпуклых функций. В [94, 96] установлена связь методов ОГС и фейеровских приближений ([25-27]), ОГС и методов отсечений ([69]).
Другую группу методов для минимизации недифференцируемых функций составляют - субградиентные методы и близкие к ним методы сопряженных субградиентов. Впервые - субградиенты исполь -5 зованы В.Ф.Демьяновым в алгоритмах типа наискорейшего спуска для решения минимаксных задач- (см., напр., [22]). В дальнейшем методы решения минимаксных задач разрабатывались, в частности, в С21,22, 43,62,89,94] . - субградиентные методы и методы сопряженных субградиентов минимизации произвольных выпуклых функций предложены в [21,62,70,71,82,87,101-103,104,108,109] . В работах А.И.Ко-раблева [58-61] - субградиентные алгоритмы обобщены на классы квазивыпуклых и псевдовыпуклых функций.
В последнее время выделился еще один важный класс экстремальных задач, которые требуют специальных методов решения. Это класс некорректных экстремальных задач. Первые методы их решения (методы регуляризации) принадлежат А.Н.Тихонову и подробно описаны в [10,85]. Методам регуляризации посвящены также работы [7,8, 10,11,86] . Идея этих методов заключается в последовательном решении так называемых стабилизированных задач. Оказывается, что для решения их можно применять некоторые известные методы минимизации функций, если согласовать параметры метода с параметрами стабилизации, или,другими словами, провести итеративную регуляризацию методов (см. \_ 10,12,13,24] ).
Однако, несмотря на большое количество работ в области нелинейного программирования, и сейчас еще численная реализация многих методов минимизации вызывает, зачастую, значительные сложности. Одной из причин трудной реализуемости некоторых методов является то, что в них для перехода от одной итерационной точки к другой приходится решать вспомогательные задачи условной минимизации, которые часто сами по себе не многим легче исходной задачи. Примером могут служить хорошо известные методы условного градиента, проекции градиента, метод Ньютона (см. С 9,23,55,63,68,79,83]) и некоторые другие. Эти методы характерны тем, что на каждом шаге для нахождения направления спуска в итерационной точке решается задача минимизации вспомогательной функции (линейной в методе условного градиента и нелинейной - в двух других) на допустимом множестве. Если допустимое множество задано нелинейными неравенствами, то упомянутые методы являются трудно реализуемыми, поскольку в таком случае решение вспомогательных задач в них связано с большими вычислительными затратами.
Даже этот пример доказывает актуальность исследований, направленных на разработку методов минимизации с легко реализуемыми алгоритмами, в которых вспомогательные задачи, несмотря на общий вид ограничений, остаются довольно простыми, во всяком случае, решаются за конечное число шагов.
Одна из идей, на которую можно опираться при построении методов такого типа, является идея погружения допустимого множества в некоторое выпуклое множество более простой структуры, например, в многогранник с целью упрощения подзадач нахождения итерационных точек. Эта идея присутствует, например, в методе опорных множеств В.П.Булатова (см. [6]) ив ряде других методов погружения (см. [14,44,63,100,107,110]) следующим образом. Строится последовательность вложенных друг в друга выпуклых множеств, как правило многогранников, содержащих допустимое множество, и точки минимума целевой функции на этих охватывающих множествах принимаются за приближенные решения исходной задачи. В этих работах предложены способы построения аппроксимирующих множеств с помощью отсечений получаемых на каждом шаге итерационных точек. В случае, когда целевая функция линейна, в упомянутых методах подзадачи отыскания итерационных точек практически разрешимы, т.к. являются задачами линейного программирования. Идейно близкие методы отсечений использованы в [5,6,19,74] для решения многоэкстремальных задач. Операции погружения и отсечения множеств, в том или ином виде,используются также в работах [69,91,96,98,99,105,106] . Отметим, что если идею аппроксимации допустимого множества рассматривать широко, то метод линеаризации Б.Н.Пшеничного ([ 79,81] ) и ряд близких к нему алгоритмов (см.,напр., [73,81]) также можно отнести к своеобразным методам погружения, в которых на каждом шаге для решения задачи отыскания направления спуска производится аппроксимация допустимого множества многогранным путем его линеаризации.
В данном диссертации предлагаются методы условной минимизации в евклидовом пространстве Rn как гладких, так и негладких функций, которые основываются на принципе частичного или полного погружения допустимого множества. Этот принцип используется непосредственно при построении методов условной минимизации гладких функций, а также при численной реализации предложенных в работе методов негладкой минимизации. Однако, в настоящей работе использование операции погружения допустимого множества основывается на идеях, отличных от заложенных в упомянутых выше методах погружения.
В предлагаемых методах операция погружения используется, в основном, для отыскания направления итерационного перехода от точки к точке. А именно, для нахождения направления спуска SK на К -ом шаге с помощью разработанной конечной процедуры отсечений строится множество, охватывающее допустимое, и решается задача минимизации на нем некоторой вспомогательной функции. Во всех разработанных методах, за исключением предложенного в первом параграфе, последовательность приближений { к) строится принадлежащей допустимому множеству. Переход к очередной итерационной точке осуществляется по правилу з .- + SK , что позволяет распоряжаться еще и выбором шага.
Диссертация состоит из трех глав. Первая глава посвящена разработке методов погружения для условной минимизации гладких функций. Во втором, четвертом и пятом параграфах предложены мето -8 ды минимизации, которые обобщают, соответственно, методы условного градиента, проекции градиента и метод Ньютона. Предложенные методы характерны тем, что в них на каждом шаге строится выпуклое замкнутое множество, частично или полностью содержащее допустимое множество, достаточно хорошо его аппроксимирующее, и для отыскания направления спуска решается задача минимизации вспомогательной функции на этом аппроксимирующем множестве. С практической точки зрения это множество удобно строить как многогранное. Если допустимое множество задачи определено нелинейными неравенствами, то предложенные в работе методыіредпочтительнее упомянутых, поскольку вспомогательные задачи в них проще соответствующих вспомогательных задач методов условного градиента, проекции градиента и метода Ньютона. Отметим, что, если охватывающее множество в предложенных методах выбирать совпадающим с допустимым, то они превращаются в известные варианты названных методов. Кроме того, если в методе проекции градиента операция проектирования осуществляется на каждом шаге, то в методе из § 4 на некоторых итерациях она может опускаться. Этот факт позволил предложить в § 4 модификацию метода проекции градиента. Доказана сходимость предложенных методов и почти для всех их вариантов получены оценки скорости сходимости. Для построения аппроксимирующих множеств используется метод обобщенно опорных гиперплоскостей (00Г), разработанный в первом параграфе. Метод 00Г решения задачи математического программирования позволяет строить требуемые аппроксимирующие множества в виде многогранных множеств за конечное число шагов. В первом параграфе показано также, что метод 00Г может быть полезен для приближенного решения некоторых задач линейного программирования и, кроме того, может служить реализуемым способом отыскания направлений спуска в одном известном варианте метода условного градиента ((55] ). В третьем параграфе идея погружения применяется для решения некорректных задач. По методике Ф,П,Васильева (СЮ]) проведена итеративная регуляризация одного варианта предложенного во втором параграфе метода. Основные результаты первой главы опубликованы в [32 - 37] . В заметке [37] автору принадлежат теоретические результаты, а О.В.Боглаевским проведены алгоритмизация и численные эксперименты.
В третьей главе обсуждаются результаты численных экспериментов: при решении некоторых тестовых задач методом типа условного градиента из § 2 первой главы и методом условного - субградиента. Во втором и третьем параграфах этими методами, соответственно, решены задача синтеза информационно-управляющей системы (МУС) и задача выбора оптимальных времен функционирования подсистем И7С. Результаты этой главы опубликованы в [57].
Автор выражает благодарность научному руководителю доценту кафедры экономической кибернетики КГУ А.И.Кораблеву за постоянное внимание и помощь в работе над диссертацией, всем участникам научного семинара кафедры экономической кибернетики за полезные обсуждения и замечания в ходе работы над диссертацией, а также доценту кафедры радиофизики А.В.Кобчикову, указавшему интересные и важные физические задачи.
Метод типа условного градиента с частичным погружением допустимого множества
Как уже отмечалось, некоторые известные методы минимизации, в частности метод условного градиента, трудно реализуемы в случае, когда допустимое множество задано в общем виде. В настоящем параграфе предлагается метод условной минимизации гладких функций, характерный тем, что в нем для отыскания направлений перехода от одной итерационной точке к другой используется операция частичного погружения допустимого множества. Погружающее множество строится с помощью разработанной в I.I процедуры отсечений. Из практических соображений его удобно строить в виде многогранника, поскольку в таком случае задача отыскания направлений спуска может ставиться как задача линейного программирования независимо от общего вида ограничений.
Пусть (р(х) - определенная в R выпуклая непрерывно дифференцируемая функция. Решается задача минимизации её на выпуклом ограниченном замкнутом множестве Ъ с R с непустой внутрен-ностыо Т . Положим х олотіп ср(ос) . Далее всегда через J?(X) будем обозначать градиент функции Ср(эс) в точке эс
Опишем метод решения поставленной задачи. Он вырабатывает последовательность точек {х } такую, что хк є Q , кєК = = . 0,4 .} , и заключается в следующем . Задаются числа 0«ift l , 0 с ( . Выбирается точка J о начального приближения осо е vD . Пусть найдена точка э?к , не являющаяся точкой минимума функции (х) на множестве Ъ . Тогда (К-М)-е приближение отыскивается следующим образом. 1. Строится выпуклое ограниченное замкнутое множество VA так, чтобы х е тк и точка ос = dtamivi tf (х "), х) удовлетворяла (с,2),х ) -условию. 2. Полагается S = х - хи , где ос f 5 эс,ЛПЙ и удовлетворяет неравенству с 11 а? - 1\ И к с \\ 3. Полагается +H= K+?KSK , (0, ] , и следует переход к пункту I при К , увеличенном на единицу. Сходимость описанного метода обеспечивается за счет выбора чисел к . Способы выбора их будут указаны позже.
Замечания. I) Алгоритм построения требуемого в пункте Ішо- жества \А представляет собой конечный итерационный процесс и заключается в следующем. Задается выпуклое ограниченное замкнутое множество М с R п такое, что х є М . Пусть уже построено множество М Находится точка Ч. = ata min (cp (or ) х ) . Ес-ли точка у. удовлетворяет (с,Т),оск) -условию, то есть нашлась точка у Є Цх , ] П Э такая, что С Ц уL — хк \\ \\ Ч. - х И » тогда полагается М = у\ , 5с = и процесс заканчивается. В противном случае, строится множество fv путем отсечения от г\ точки W. .В методе обобщенно--опорных гиперплоскостей из I.I предложен способ отсечений, который, согласно замечанию 6 того же параграфа обеспечивает конечность описанного процесса построения Мк . Выбор точки й. для проверки (с & э Хк ) - условия может производиться, например, следующим образом. Если М. Є 2$ , то достаточно положить У- = У-) чтобы убедиться в выполнении С С , 2), эс ) _ условия. Если Jj«t 2) , то можно полагать U. = Ч. , где U. - точка пересечения луча х +cL ( U. - х ) г с О , с границей множества 2) 3 или точку U. выбирать, например, из условия с \\її. — х lljjL- Хк Ї , где С с і .
2) Очевидно, что реализация предложенного метода будет наиболее простой, если множества М.. строятся в виде многогранни-ков.
3) Если в предложенном методе положить Му.=2) для всех К К , то без дополнительных построений точка х =йіатік С Я(х ),ос} будет удовлетворять, очевидно, (с,2), ) - условию, и алгоритм будет представлять собой один из вариантов метода условного градиента.
4) Процесс отсечений для построения множества [И может начинаться для всех ке К с одного и того же исходного множества М . Поэтому при построении на К -ом шаге множества Мк дополнительные ограничения,полученные за счет отсечений при построении множества Мк_4 , не учитываются. Этим описанный алгоритм выгодно отличается от метода типа условного градиента, предложенного в [91]. Кроме того, вопрос о сходимости метода из [91] остается открытым, т.к. при обсуждении его сходимости используется на стр. 908,910 недоказанное утверждение ша ( -? (эс ) S ) = 0 .
5) Если известно, что х е 2Ь , то,начиная с некоторого номера Ы , будет выполняться включение Е(эс ) = focRJ tyCoc) ФС эО} СЭ, к $=Ы .В этом случае можно полагать М„ = = Е(Х ) для всех К Ы . Подобный алгоритм для безусловной шнишз ащи фикций, использующий множества Е( к) дая построения направлений спуска, предложен в заметке автора [31].
Проекционный метод с погружением допустимого множества
В настоящем параграфе предлагается метод проекционного типа для решения задачи выпуклого программирования. Он характерен тем, что проектирование вспомогательных точек для построения направлений спуска может осуществляться не на допустимое множество, а на некоторое специально построенное множество, охватывающее допустимое.
Решается задача минимизации выпуклой непрерывно дифференцируемой в R функции (р(х) на выпуклом ограниченном замкнутом о множестве cR , ) - 0 . Через Р (ос) обозначим ПрОЄК-цию точки -ос на множество Q Метод решения поставленной задачи заключается в следующем.
Выбирается точка начального приближения х є Э » числа 0 С \ » 0 л А" Пусть найдена точка х є ) , не являющаяся решением задачи. Тогда ( К + \ ) -е приближение отыскивается следующим образом. 1. Полагается Н. = х - Лк Ц (х ) , где А А А . 2. Строится выпуклое замкнутое множество М„ , содержа-щее ТОЧЕШ х и 00 = EL(2K) » так, чтобы точка О) =P(z ) удовлетворяла (С, 2) х ) - условию 3. Полагается к - хк если Ч Ъ эс — к , если оок ф Z) , где X х, С0.7П Э и удовлетворяет неравенству С11 О) -X 11 ; И хк - хк 1 . 4. Полагается x,+ = хк+ S , где (0,0 , и следует переход к пункту I при К , увеличенном на единицу. Сходимость метода будет обеспечиваться за счет выбора параметров Ак и Є к . Способы выбора их будут указаны позже.
Замечания. I) Алгоритм построения требуемого в пункте 2 множества М представляет собой конечный итерационный процесс и заключается в следующем. Выбирается выпуклое замкнутое множество М cR , содержащее точки х и , например, М можно выбрать содержащим множество Т) . Пусть уже построено множество
М . Путем минимизации функции (х)=11х-г II на множестве Ми находится точка У»с — Р і (гк сли она удовлетворяет (С,0,хк) - условию, то есть нашлась точка М. LxK 5jJn) такая, что С\\ у L — эс II \\ u L — ос \\ , то полагается \J\ =Щ оо = у. , ос = Ч. и процесс заканчивается. В противном слу-чае, строится множество М путем отсечения от М точки и . Способ отсечений предложен в I.I и, согласно замечанию 6 того же параграфа, обеспечивает конечность описанного процесса. Выбор точек Ц. для проверки (C,Z))XK) _ условия обсуждался ранее в замечании I 1.2, Как и в замечании 4 1.2, отметим, что при построении множества Мк дополнительные ограничения, полученные за счет отсечений в ходе построения множества Му,_, , могут не учитываться.
2) Для построения множества Мк не обязательно заранее иметь множество \S\ , содержащее точки х и л к . Если такое множество построить трудно, то процесс отсечений, если в нем есть необходимость, можно начинать, полагая \Л = 3) Если в предложенном методе положить Мк- 2) для всех Кб 1 = (0,4,... } , то точка К = (2К) » очевидно, без дополнительных построений будет удовлетворять Сс,2),хк) - условию и алгоритм будет представлять собой один из вариантов метода проекции градиента.
4) Если точка 2 2) , то можно положить М = Q » пос-кольку в этом случае точка сок = 2 удовлетворяет (с , /J, ос ) -условию без дополнительных построений.
5) Пусть на К -ом шаге точка ч. ф Z) , но удовлетворя-ет (С, 2), ) - условию. В этом случае удобно положить OJK=ZK, поскольку можно считать, что М -R и СС.Ъ,?си) -условие К ІП К для точки СО выполняется. Это замечание может служить некоторой модификацией метода проекции градиента. А именно, операция проектирования точки 2 # на Т) в методе проекции градиента может /—"V опускаться на тех итерациях, когда 2 удовлетворяет (С, хк) к условию. В таких случаях можно полагать, например, S - X - х , К К К где х. - точка пересечения луча ос +0 .( -х) ьі 0 , с границей множества D
Конечный метод отыскания точки выпуклого множества
Заметим, что поскольку ф(ос ) = Р(5с ) , то из (2) следует ра венство urn Ф(х,) = Cp + , а кф(2 = ф + . (12) Далее, из последовательности {l?} , teK » выделим сходящуюся подпоследовательность і 2 I , [еК сК» такую, что последо-вательность {22е } , , также является сходящейся. пусть г2е- 2 ,b», K f а г2Є+/1- І , Є- ЄеК4 . В силу (II) Z l , а в силу (12) P(z) = cpCz) . (із) По построению метода ф(22Є+4) (1-Л)срс2 )+Amm(p(z + і Wfl/i2 + J_ з -\ РеК Переходя в последнем неравенстве к пределу по - оо , Ее К , и учитывая строгую выпуклость функции Ф(х) , получим, что CP(iE) 0-A)Cf(z) + + іф(г) + уф(і) . Отсюда и из (13) следует противоречивое неравенство ф("2 ) ФС2 ) . Теорема доказана.
Опишем теперь практический способ отыскания на К -ом шаге метода вектора SK из условия (I) с б \ для случая, когда S =Е(х ) . Применим для этого описанную в 2.1 реали-запию ПІ, положив в ней Q=S = Е.С зс ) » У = » P=R, 1С \& С) vZ. iC и выбрав выпуклое ограниченное замкнутое множество М ЕСх Д Как было показано в 2.1, найдется подпоследовательность точек { У L} , L Li с X , такая, что \\ U - "2. И -» О , L -» « , L -Ц . Тогда, в силу выбора точек Z{ в реализации ПІ, j і. " i " " , L_ 0 , "L є -Ц . Следовательно, найдется такой номер t0 , что выполнится неравенство Ц М. - х Ц 6-к» -хк .Тогда 1 8.girXK max (a y.-x mln max a ,x- oc , то есть ePK 3l « « направление Sk = M -K - зс является искомым. Заметим, в заключение, что описанный метод-является обобщением на случай негладких функций одного метода минимизации, предложенного автором в [31].
В 2.1 были описаны две процедуры, с помощью которых можно решать задачу отыскания точки выпуклого множества. Однако, как было показано, они гарантируют получение решения лишь за бесконечное число шагов. В данном параграфе предлагается общая схема нахождения элемента из конуса, сопряженного к выпуклому конусу и на её основе строится еще один метод отыскания точки выпуклого множества. Этот метод идейно близок к процедуре 2, но в отличии от нее, за счет особого способа построения множеств Р. обеспечивает решение задачи за конечное число шагов.
Пусть К - выпуклый конус из R , множество U={x6fj : К , \(xj=i } замкнуто, О. , 1- = 0,4,..., - выпуклые ограниченные в совокупности замкнутые множества из R такие,что существует хотя бы одна точка W є S. , »-= о, ,... , удовлетворяющая неравенству 1 Q , 1\ ) 0 Для всех Q К . Переходя в (4) к пределу по К - о t получим противоречивые неравенства 0 - 5 К И к II 0 . Тем самым доказана конечность описанного процесса.
Заметим, что по построению процесс заканчивается, когда для некоторого номера K = W не находится вектора о ,. Ц удовлетворяющего (3). В этом случае для всех Q6 U справед ливо неравенство . Q , К ) ьі Поскольку d О то для всех а б U дЛм 0 . (5) Очевидно, (5) выполняется для всех 9 К ) И 2 И О Используя полученные результаты, опишем далее метод для отыскания точки выпуклого множества. Пусть - выпуклое множество, Тогда, как уже было замечено в I.I, VJ(х} Q ) -{ Q R : Г "" выиувлый замкнутый конус
Для отыскания точки из множества U применим приведенный выше алгоритм построения последовательностей { к- \ » { 9-} » положив в нем 1\ -VJ(x,Q) и выбрав множества S- » удовлетворяющие указанным требованиям. Тогда, по доказанному, через конечное число шагов будет получен вектор U Є S » удовлетворяющий (5). В таком случае, следуя схе-N ы ме доказательства теоремы 3 из [60] , нетрудно показать, что найдется такое число Л 0 , что ос + Л h Q- . Кроме того, очевидно, указанные множества S можно чередовать между собой от шага к шагу или положить S = S;+, = S для всех Lei Замечание 2. В методе, очевидно, можно конечное число шагов множество R оставлять без изменения, то есть полагать р. = р. , а менять только множества S Далее на основе этого замечания будет описана одна из реализаций метода.
Описанный метод имеет пока лишь принципиальный характер, т.к. не указан способ отыскания векторов д. с Ц , удов-летворяющих (3). Ниже для множества Q специального вида такой способ будет указан.
Применение метода типа условного градиента с погружением допустимого множества для решения задачи синтеза инфор мационно-управляющей системы (ИУС)
В третьей главе обсуждаются результаты решения модельных задач методом из 1.2 и методом условного , - субградиента. Этими методами, соответственно, во втором и третьем параграфах решены задача синтеза информационно-управляющей системы (ИУС) и задача выбора оптимальных времен функционирования подсистем ИУС.
Остановимся коротко на результатах численных экспериментов, проведенных методом типа условного градиента из 1.2. Целью экспериментов было выяснение влияния параметра С на ход итерационного процесса. Численные эксперименты проводились при П. = 2,5,6,7, в качестве целевых функций и функций, задающих ограничения, выбирались выпуклые квадратичные функции. Шаги в методе выбирались из условия релаксации первым способом. Множество М строилось в виде п - мерного куба, содержащего точку минимума, и на протяжении решения задачи оставалось для всех К одним и тем же.
Каждая задача решалась несколько раз при различных значениях параметра С . В тех случаях, когда значение С выбиралось близким к нулю, точка 5с , удовлетворяющая (С , D , хк ) " Условию либо находилась без дополнительных построений, либо количество отсечений множества М для её отыскания было незначительным. Но в этом случае точность решения большинства задач была невысокой и вблизи решения процесс оказывался неустойчивым. В тех случаях, когда параметр С выбирался близким к единице, точность решения задач была выше, но подзадачи нахождения точек х получались сложными, т.к. требовали значительного числа вспомогательных итераций. Наиболее приемлемые результаты были получены при значениях с от 0.7 до 0.8. При таком выборе параметра С число отсечений на каждом шаге не превосходило 15, а решение задач получалось по функционалу с точностью 10 . Данная рекомендация была учтена при решении реальной физической задачи. Эта задача была решена 12 раз при различных значениях параметров и результаты её решения приведены в 3.2.
Опишем следующий вариант метода условного - субградиента. ется 8. Если tf + A.l ) т( х 5 к » то полага K+j, = XK + i i , К:- K+ і , и следует переход к п.З. 9. Отыскивается вектор О. в UK такой, что (о. , К=0 . Полагается P. , e Р U( 9 . 1 и следует пере ход к п.5. В результате действия этого алгоритма генерируется последовательность х (v .) ,1 = 0,4,... Данная последовательность такова, что найдутся номера j 0 , К 0 , для которых хСО является - оптимальной точкой. Это ут верждение докажем по схеме, предложенной в работе [60]. Покажем, сначала, что найдутся номера j0 , к такие, что для всех j jo ик ко выполняются равенства Х( .)-х(Ч . ) . Допустим противное. Тогда найдется tj С j + подпоследовательность { Х( ?. )\ , Е. = 0,4 ,... , отличных друг от друга элементов, которую для удобства обозначим {ч}7 t = 0,4, .- .В силу построений алгоритма выполняются неравенства 4?(u )- J?(M \ , К = 0,і,... . Просумми руем эти неравенства по В от О до m . Тогда Поскольку +(jO 4 » то Л Л Z e а это невозможно для достаточно больших значений IU в силу выбора чисел » . Покажем теперь, что точка х( . ) является к - оптимальной точкой функции -j?(x) на 0 . Допустим о противное. Тогда за конечное число шагов можно построить вектор К. такой, что jf(r( o)) - Jf (x(?je) +ALk.) S„e , а значит найдется номер j j0 такой, что х(у-)Фх(Ъ. ). Это противоречие доказывает утверждение.
Как уже отмечалось в замечаниях 2.4, векторы [\. ,Q. и числа Л могут выбираться из менее жестких условий. Это учитывается далее при описании одной вычислительной схемы алгоритма для решения минимаксных задач. Отметим, что приведенный алгоритм допускает возможность изменения в методе параметра от шага к шагу. Ниже алгоритм обсуждается, в частности, и с точки зрения целесообразности стремления чисел 8К к нулю.
Пусть решается задача w\ln-f(x) , (j) где (х) = тах .(х) » -(х) . і=і,...,т, - выпук- і її лые дифференцируемые в R функции, Z) = {хёК : F(x F(x) - выпуклая в И функция. Пусть где 0 0 . Для решения задачи (I) была использована следующая вычислительная схема описанного алгоритма. Выбирается произвольно точка начального приближения Хо є D , задаются числа . 0 , сС , А ,А , из интервала (О, О , d О , натуральное число Ы 1 . 1. Полагается К=0 . 2. Выбирается множество S , a lam S А , сог К. 1С ласно требованиям метода условного . - субградиента. 3. Полагается Uo ,1 =( } , где %0- [(. )/ 4. Отыскивается вектор la- =atg тік. max
