Методы минимизации псевдовыпуклой функции максимума, основанные на общих достаточных условиях сходимости тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

РГ6 0«

1 2 аВГ

КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

Кашипа Ольга Апдрсевна

МЕТОДЫ МИНИМИЗАЦИИ ПСЕВДОВЫПУКЛОЙ ФУНКЦИИ МАКСИМУМА, ОСНОВАННЫЕ НА ОБЩИХ ДОСТАТОЧНЫХ УСЛОВИЯХ СХОДИМОСТИ

01.01.07 - вычислительная математика

Автореферат

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

Казань - 1996

Работа выполнена на кафедре экономической кибернетик Казанского государственного университета.

Научный руководитель: Официальные оппоненты:

доктор физико-математических наук, профессор Заботин Я.И. доктор физико-математических наук, профессор Ижуткин B.C., доктор технических наук, профессор Галиев Ш.И.

Ведущая организация: Иркутский госуниверситет

Защита состоится " № ■ 19 в ^/^часов I

заседании специализированного совета К 053.29.05 по присуждени ученых степеней по математике в Казанском государственнс университете по адресу:

420008, г. Казань-8, ул. Ленина, 18, корпус 2, ауд. 217.

С диссертацией можно ознакомиться в научной библиоте1 университета (г. Казань, ул. Ленина, 18).

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

г.

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

доцент p-w [ В.В.Шурыгин

Г/

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

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

Современный уровень развития теории оптимальных решений •авит задачу обобщения и систематизации накопленных в этой об-1сти знаний. Возникает вопрос: что является тем общим, что ле-ит в основе выбора итерационных направлений и шагов в методах шейных приближений, обеспечивая сходимость процесса? Выявле-ie этих общих свойств позволит наметить единый подход к анализу [тимизационных алгоритмов, предложить общую схему построения зтодов решения задач НЛП и обоснования их сходимости, разрабо-дъ в рамках этой общей схемы новые эффективные алгоритмы рвения отдельных классов задач НЛП, создать основу для гибридиза-ш методов.

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

Методика исследования. В работе использованы теория и ;тоды выпуклого анализа, общей теории математического програм-фования, псевдо- и квазивыпуклого программирования, разрабаты-емые в работах Мангасариана (Mangasarían), Заботина Я.И. , Ко-'.блева А.И. и Хабибуллина Р.Ф., а также предложенные автором по-стия критерия качества направления в точке, эталона качества

направлений для точки и понятие устойчивости последовательное тей направлений и шагов.

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

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

Апробация работъь. Основные результаты диссертации док ладывались на конференциях "Методы математического программи рования и программное обеспечение" (Свердловск, 23 - 27 феврал 1987г), "Математическое программирование и приложения" (Сверд ловск, 25 февраля - 1 марта 1991г), на итоговых конференциях Ка занского университета за 1984 - 1992 гг., неоднократно обсуждалис на научных семинарах кафедры экономической кибернетики КГУ, * кафедры прикладной математики- Марийского госуниверситета.

Публикации. Все основные результаты диссертации принадле жат автору и получены им самостоятельно. Они опубликованы работах [1 - 5].

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

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

Первая глава посвящена установлению достаточных условий сходимости методов линейных приближений для задачи минимизации строго квазивыпуклых функций при наличии ограничений. Глава I состоит из 4 параграфов.

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

Определение 1.1.3 Функция /, определенная на выпуклом множестве G, называется квазивыпуклой, если для любых Л", у е G и любого а £[0,1] справедливо неравенство:

f(a-x+(\-a)-y)< шах{/(х), f{y)}.

Если неравенство выполняется строго при всех X Ф у и всех (X € (0,1), функция f называется строго квазивыпуклой.

Определение 1.1.10 Функция /, определенная и дифференцируемая на открытом выпуклом множестве G, называется псев-до-выпуклой, если для любых X, у е G справедлива импликация:

(f'(y),x-y)>Q^f(x)>f(y).

Если для всех X Ф у неравенство выполняется строго, функция f называется строго псевдовыпуклой.

Определение 1.1.11 Для квазивыпуклой функции f, определенной в Rn, точки X &Rn и числа О inf{f(y),y ei?"} определим множество:

H(x,f,c)={pGRn:f(x + a(p)p)<c, За(р) >0}

Любой элемент множества Н{х, f, f{x)) будем называть направлением спуска функции f в точке X.

Определение 1.1.12 Пусть в R" определены непрерывные функции /¡(у), ¡g/, где / есть конечное множество индексов,

(pi}') - max {/(>'), i el}, загоны точка X .и число £> 0. Функции с номерами из множества I(x, s) = { i € / : ^(а) > (р(х) — S } будем называть £ -активными в точке X.

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

Пусть в R" определены непрерывные квазивыпуклые функции F, Фи поставлена задача:

min {F(x),xeD}. (i;

Здесь и далее D = {х е/Г: Ф(х) < 0}. Будем считать, что выполнены условия:

1.2.а) intD = (х е R": Ф(х) < 0} ф 0.

1.2.Ь) X* = {xeD : F-x) < F(y), VyeD}* 0.

Будем обозначать F* = F(x*), Vx* el*.

¡j<

l.2.c) intM(F,c) - {x eR": F(x) < с} при всех c>F.

1.2.d) существует точка z такая, что множество X(Z) = M(F, F(z))f]D ограничено.

Определение 1.2.1 Пусть G- множество в R", X eG. Вектор р £ R" назовем надежным направлением для множества G и точка X, если Х + ар gG для любого числа fl> 0. В противном случае вектор р назовем ненадежным для G и X направлением.

Множество надежных для G, X направлений обозначим чере; K(x,G), множество ненадежных направлений, т.е. R"\K(x,G), через ß(x,G).

Доказан-ряд свойств множеств K(x,G) и Q{ X, G). В частности показано, что если G замкнуто и выпукло, то при всех X,Z eG имеют место равенства:

К(х, G) = K(z, G) ее K(G), Q(x, G) = Q(z, G)=Q(G)-

Пусть множество G С R" замкнуто и выпукло. Определим i G xR" функцию:

[maх{а: x + apeG}, ecnupeQ{G) a(x,p,G) = \

Доказано, что ОС {х,р,(7)полунепрерывна сверху на С X Л", причем она непрерывна в каждой точке (Х',р), удовлетворяющей условию: X Л-Рр V/? е (0, а(х, Р, Сг)) .

В параграфе 1.3 даются определения ключевых понятий работы: критерия качества направления и эталона качества направлений для фиксированной точки; устойчивых (почти устойчивых) последовательностей направлений и шагов; устанавливаются предельные свойства таких последовательностей.

Исследуются методы решения задачи (1), формирующие последовательность точек {.X }, к eN по правилу:

А"*"*1 = хк+ак-рк , (2)

где рк £ В.'1 - итерационное направление, ССк > 0 - итерационный шаг.

Будем считать, что задано множество Р с/?л, удовлетворяющее условию:

1.3.а) Р выпукло, замкнуто, ограничено и О Элементы множества Н(х,Р,Г(х))С\Н(х,Ф,0) будем называть подходящими в точке X направлениями.

Определение 1.3.1 Функцию Э(х,р), определенную на Х(г)хР, назовем индикатором принадлежности вектора р множеству подходящих в точке X направлений, если

1.3Л») 3(х,р)>0=} р еН(х,/-(х))пЯ(х,Ф,0).

Определение 1.3.2 Функции Т] (х, р):Х(1) х Р —» Л1 и

Г]*(х): Х(г) —> назовем соответственно критерием качеств о направления р для точки X и эталоном качества направлений для точки X , если выполнены условия:

1.3.с) У] (х,р) ограничена на Х(г) хР) 1.3.(1) ?7*(х) ограничена на Х(г);

1.3.е) для любой пары (х; р) £ Х(г) х Р() и по каждому ¿' > 0 можно указать А>0 так, что при всех X е[/(.Х,А)ПД2) и всех Р е 1/{р, А)ПР выполнится неравенство: Т](х, р) <$(х,р) + £ ; 1.3.0 7/*(х) >0 при всех X &Х(¥), причем

7/*(х) =0<=> х еХ*\ 1.3.§) Т]*(х) полунепрерывна снизу на Х(гУ,

1.3.Ь) для каждой точки Л еотыщется вектор р(х) еР, удовлетворяющий равенству: Т]*(х) = 7] (х, р(х)).

Определение 1.3.3 Последовательность направлений {gk}czP назовем устойчивой относительно последовательности точек если существует такое число (/>0, что при всех к справедливо неравенство: г^ук, gí:) > q■ Т]*(ук).

Определение 1.3.4 Назовем ограниченную последовательность {1гк} почти устойчивой относительно {ук} сХ(г), если существуют устойчивая относительно {)'к} последовательность векторов {£*} и числовая последовательность {И}, удовлетворяющие условиям: /г = И >у> 0, к еИ.

Определим для Д> О, р) X Р величину:

Я(х,р,р) = sign<<F(x)-F(x + (a(x,p,D) +р)р)). Положим X (х, р,р) = шах{0, Л(х, р,Р)}. Обозначим для всех к & N через

а*к = а(ук,Ик,Х(/У), «***=«(/,Л*,/>), Г* (ф) = Х\ук ,1гк, р).

Определение 1.3.5 Числовую последовательность {¡а } назовем устойчивой относительно {(ук',Ьк)}, если существуют числа Д Д, удовлетворяющие условиям: 1.3л) 0 < Д < ~Р<\] 1.3.3) Мк ^р-а*к,к еЛГ; 1.3.Ь) // < Да*\ если 1гк еК(О), к

1.3.1) / <Я+кф)-а**к+Р (\-Гк(Р)) а*к,

если Ик е (2(£>), к еЛ^. Определение 1.3.6 Пусть построена последовательность

{/}сД АтеЛГ.

Положим

Гкс = тт{Г(/); 0< *< к}, к еЛГ, Я = {к>\: F(yk)<Fk;l}U{0}.

Точки ук, к е/? будем называть рекордными точками последовательности {}'*}, /с еЛ^.

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

Теорема 1.4.1 Пусть функции Т7, Ф определены, непрерывны и квазивыпуклы в Я" ; справедливы утверждения (1.2.а)-(1.2.<3), последовательность {хк} С построена по правилу (2), причем существует подпоследовательность IV, сЯ такая, что выполнены условия:

a) {рк} почти устойчива относительно {хк }, к £ ./V, ;

b) {ак } устойчива относительно {(л"* ;/?*)}, /с е ТУ, .

Тогда предел любой сходящейся подпоследовательности после-двательности {хк } , /с £ является решением задачи (1).

Вторая глава посвящена ответу на вопрос: как построить функции с указанными в главе I свойствами с тем, чтобы с их помощью проверить последовательность итерационных направлений на устойчивость? Глава II состоит из двух параграфов.

В параграфе 2.1 предлагаются определенные на Х(Т) х Р функции:

[о, р = о

задающие критерий качества направления р для точки X как максимальный шаг, который может быть сделан по лучу X + а ■ р без нарушения границ допустимой области £) и лебегова множества

функ

[о, р = о

задающие критерий качества направления р для точки X как

полный шаг на отрезке [0, а(х,р/1|/?|], £))]; функции:

задающие критерий качества направления р для точки X как

максимально возможную величину уменьшения функции Р при движении из точки X по направлению р в пределах допустимого множества

Эталон качества направлений для выбранной точки предлагается строить по правилу:

г/*(х) = тах{ г}(х,р), реР }, (3)

где Т] (х,р)- произвольная функция, обладающая свойствами:

a) &(х,р) = Г}(х,р) на Х(1) X Р\

b) справедливы утверждения (1.3.Ь), (1-З.с), (1.3.е);

c) при каждом X существует вектор р(х) £ Р такой,

что 7](х, р(х)) = 0;

а) если пара (Х\р) такова, что р&Н{х,Р ,Р(х))(]Н(х,Ф,0), то Ц(х,р)> 0;

е) при каждом X еХ(г)\Х * функция Т](х,р) непрерывна по

р на множестве Н(х,Р,Р(х))Г\Н(х,Ф,0).

В параграфе 2.2 предлагаются критерии качества направлений для задачи условного минимакса в псевдовыпуклом программировании.

Дополнительные предположения о свойствах функций Р', Ф, определяющих задачу (1), состоят в следующем:

(2.2.а) заданы множества , /2 С N, причем ^ 00 >

(2.2.Ь) функции £ (х), / е71 УД определены, псевдовыпук-

лы и непрерывно дифференцируемы в ;

(2.2.с) ^(х) = шах{^ (х), г },

Ф(х) = шах{/ (*), / е /2}

Для произвольных X € К", £,8 >0 построены множества:

- 10-

I, (х, = {/ €/,: /, (х) > Г(х) -е},12 (х, 5) = {/ е/2: / (х) >.-*},

Предлагается использовать определенную на /) х Р функцию: ф,р) = тт{-у/Хх),р)~Ь1(х); ¡е1(х,е,6)} где

МЫ-РОЦе!

I/ «, '

сак критерий качества направления р для точки X; эталон качес-пва направлений предлагается строить по правилу (3).

Показано также, что эталоном качества направлений может :лужить функция максимума критерия качества векторов, полу-тенных посредством линейной комбинации градиентов активных в выбранной точке функций: 77*(х) = тах{ ^(а,х); а<^А+(у) }, где <р(а,х) = тш{щ(а,х); i <е1(х,б,5)}, ¥г (а,х) = ' (х), р{а, х)) - Ъ, (х); / е 1ХI) 12 , р(а,х) = - £аг//(х); а} >0,; е1(х,е,д),

А+(г) = {а&К{х): 2а;<Г},где Г>0, ш(х) = |/(х,е,6)\.

/

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

р = V/ {х, ^;) , где / - номер алгоритма, ^ 1 - набор параметров алгоритма / ; алгоритмы поиска тага задают отображение пары (х; р) в число ОС = Т} (х, р, 6 - ), где ) - номер алгоритма, 9} - набор его параметров.

Согласно теореме 1.4.1 следующие условия гарантируют сходимость последовательности рекордных точек процесса (2) к решению задачи (1):

условие 1: ьокова бы ни была последовательное г-. {)'к} С -X(z), последовательность {hk} такая, что: hk ~Vi{yk ,Lt ), к eN почти устойчива on осительно {ук}',

условие 2: какова бы ни была последовательность _{{ук ;/?*)} , последовательность {(Хк} такая, что: ССк = Tj{yk,hk,вj) , /с еА' , устойчива относительно {(ук, если только { /)' } почти устойчива

относительно {ук}.

Глава III состоит из двух параграфов.

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

Основные свойства ЗВЯ:

1) ЗВН имеет ограниченное решение при любых допустимых значениях параметров Q,..., ;

2) Решение ЗВН при любых допустимых значениях параметров обеспечивает получение подходящего в точке X направления, если только X £Х* ;

3) Значение целевой функции ЗВН соответствует степени приближения итерационной точки к решению задачи (1), в частности, является индикатором попадания в X *;

4) ЗВН является задачей линейного программирования.

Алгоритм 3.1.1 Шаг 0. Выберем £, 8 > 0.

Шаг 1. Найдем решение (р*(х);а*(х)) задачи:

max а (4)

(fi'(x), р) + Ь,(х) + а < 0, i е 1(х, £, 5) (5)

реР (6)

Шаг 2. Если <7*(х) =0, то р :=0; иначе р := р*(х). Все шаги алгоритма 3.1.1 (при фиксированном X) выполняются однократно. Отсутствует необходимость адаптации параметров к точке X, что отличает алгоритм 3.1.1 от аналогичных алгоритмов. Выбор метода решения ЗВН (4)-(6) определяется структурой множества Р.

х, при Р = {р € Я" : [т^! < 1, у = 1,..., и} ЗВН есть задача линейно-программирования с числом ограничений, равным |/(.V, £, ¿)| + 2/2.

помним, что условие (6), где Р- выпуклый компакт, внутренность 'орого содержит начало координат, предложенное Я.И. Заботиным :ачестве обобщенного условия нормализации Зойтендейка, призва-обеспечить ограниченность последовательности решений ЗВН.

В ЗВН, используемой алгоритмом 3.1.2, проблема кормализа-и решается посредством введения единственного ограничения на

учения новых неотрицательных переменных в Алгоритм 3.1.2 Шаг 0. Выберем е, б, у > 0.

Шаг 1. Найдем решение (>'**(Л'); О"**^)) задачи:

шахгг (7)

(а,. (х),>;)+^(х) + а<0, /е/(х,£,<$) (8)

^ еУ (9)

Шаг 2. Если <7* *(х) = 0, то р := 0; иначе р := р(у**(х)).

Здесь вектор-функция £7, (х) € построена по правилу:

(а!(х)У=(//(х)У,] = 1...,п- (а,(х)Г> =-£(/,'(х)У;

м

] € 1} - номер компонент вектора С11 (х);

рез У обозначено множество точек у € Л "+1, отвечающих услови-

л+1 /=1

г(Р)=5ир{г: Щ О ,г)аР); мпоненты вектора р(у) € К" находятся по правилу:

Показано, что если точка у "пробегает" все множество У, то у) "пробегает" все множество Р, а значит, переход от Р к У не

иводит к "потере" ни одного из направлений р € Я".

Как и в алгоритме 3.1.1, все шаги здесь осуществляются однократно. Число ограничений ЗВН (7)-(9) равно £, <5)| +1, т.е. не зависит от П (в отличие от ЗВН (4)-(6)). Число переменных здесь равнс П+ 2, причем все они неотрицательны.

Заметим, что алгоритмы 3.1.1 и 3.1.2 имеют общий недостаток они предусматривают нахождение оптимальных планов ЗВН. Поскольку на практике, как правило, имеются погрешности решети ЗВН, возникает вопрос о чувствительности к ним методов решенш задачи (1). Приведенные в работе алгоритмы 3.1.3, 3.1.4 свободны о-этого недостатка: они предполагают нахождение не оптимальноп плана ЗВН, а лишь некоторого допустимого "достаточно хорошего решения.

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

ных в текущей точке функций: р. — ~ ^Г* а. (.У) • f !(х), где компо

jel(x,£,t5)

ненты вектора а(х) определяются посредством нахождения оп-тнмал! ного (алгоритм 3.1.5) или некоторого допустимого "достаточно хоронк го" (алгоритм 3.1.6) решения ЗВН:

шаха

j£](x,e,i5)

; aj ^о, j el(x,e,S).

j€l(x,£,S)

В параграфе 32 рассмотрены способы задания функций Tj, oi

вечающих условию 2. Показано, в частности, что такие известнь приемы, как дробление наперед заданного параметра и нахождет шага полной релаксации порождают последовательность {<**}, отв< чающую данному требованию. Заметим, что эти традиционные прощ дуры нахождения шага предусматривают при каждом "пробном" зн; чении шага а вычисление функции максимума F(x + ОС-р), а зн; чит, и всех функций /¡(х + а- р), /б/1( где (Л" р) - "текущая" итер ционная пара: "точка-направление". Как известно, процедуры вычи ления функций являются наиболее "дорогостоящими" элементами а горитмов. Нам удалось показать, что требования к шагу мож:

- 14-

ослабить, а именно: добиваться лишь того, чтобы шаг обеспечивал убывание тех функций, которые в данной итерационной точке являются £—активными. Доказано, что при малых значениях шага соблюдение этого условия гарантирует и релаксацию функции вообще же говоря, последовательность {¡''(х^ )}, является нерелаксационной. Однако здесь существенна "экономия" времени на процедурах вычисления значений функций, особенно в тех случаях, когда ¡/¡(

значительно превышает ¡/^Л", £)|.

Алгоритм 3.2.2 ("экономное" дробление)

Шаг 0. Выберем а0> О, X е(0,1), /? 6 (ОД) и положим а а0.

Шаг 1. Если Ф(.\' + (1- р) < 0, идем к шагу 3; иначе - к шагу 2.

Шаг 2. Положим а '.= а - X и перейдем к шагу 1.

Шаг 3. Если /¡(х + а• р) < Р(х), / €/,(*,£ ), то сг.= а-/?; иначе перейдем к шагу 4.

Шаг 1. Положим а\~а-Х и перейдем к шагу 3.

Согласно условиям 1 к 2 справедливо утверждение: если Х° 6.0, то начиная с некоторого номера процесс, построенный по правилу (2), где р = У;к(хк), а = Т]к(х\ //), вырабатывает релаксационную последовательность допустимых точек при любых сочетаниях (\]к). Здесь

/ке{1,2,3,4,5,б};д€{1,2,3},*е^.

Поскольку устойчивость последовательностей {Ик}, {сс } установлена в предположении, что точки последовательности {.У*}, вообще говоря, не связаны друг с другом, сходимость —> Г * гарантирована при любых сочетаниях {¡к; ]к), /с € N. Таким образом, метод решения задачи (1) может быть указан при помощи последовательности пар номеров {(1к'} к G.N. Если для всех точек Хк выбран алгоритм / поиска направления и алгоритм ) поиска шага, будем говорить об алгоритме г - ) решения задачи (1).

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

В параграфе 4.1 описаны тестовые задачи, для которых про-

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

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

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

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

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

ПУБЛИКАЦИИ

1. Заботин Я.И., Кашина O.A. О достаточных условиях сходимости одного класса методов решения минимаксных задач // Методы математического программирования и программного обеспечения. : (Тез. докл. V научн. конф., г. Свердловск, 23-27 февраля 1987 г.) J /Свердловск: УрО АН СССР, 1987, - с. 45 - 46.

2. Заботин Я.И., Кашина O.A. Об одном общем методе отыскания условного минимакса // Изв. вузов. Математика. - 1988. - № 1, -с. 18 - 25.

3. Заботин Я.И., Кашина O.A. Релаксационный метод решения задач условной минимизации функции максимума // Исследования по прикладной математике. - Казань, 1987, - Вып.14, - с. 25 - 33.

4. Кашина O.A. Об одном подходе к построению алгоритмов условной оптимизации // Матем. программирование и приложения. : (Тез. докл. VII научн. конф., г. Свердловск, 25 февраля - 1 марта 1991 г.) /Свердловск: УрО АН СССР, 1991, - с. 77 - 78.

5. Кашина O.A. Об одном подходе к построению алгоритмов условной минимизации // Исследования по прикладной математике. - Казань, 1992, - Вып.18, - с. 60 - 69.