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

ч

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

АДАПТИВНЫЕ МЕТОДЫ С РЕГУЛИРОВКОЙ ШАГА ДЛЯ РЕШЕНИЯ ЗАДАЧ ПСЕВДОБЫПУКЛОГО ПРОГРАММИРОВАНИЯ

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

Автореферат

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

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

УДК 519.6

ГАБИДУЛЛИНА Зульфия Равипевна

КАЗАНЬ -1994

Работа выполнена на кафедре экономической кибернетики Казанского государственного университета имени В.И.Ульянова-Ленина.

Научный руководитель: доктор физико-математических

наук, профессор ЭАБОТИН Я.И.

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

наук, профессор ИЖУТКИН B.C. кандидат физико-математических наук, доцент МАЛИКОВ А. И.

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

университет.

Защита состоится " 19Q4 г в fV

часов на заседании специализированного совета К 0S3.29.05 пс присуждению ученых степеней по математике в Казанском государственном университете имени В. И. Ульянова-Ленина по адресу: -420008, г.Казань-8, ул.Ленина, 18, корпус 2, ауд. 217.

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

Автореферат разослан ¿¿^Ц/б"1"-^ 1994 г.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПерЕая глава состоит из 4 параграфов.

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

Будем называть функцию тСх,у) для х,уе03?п симметричной на Б, если т(х,у)= тСу.х), тСх,х)=0.

Определение 1.1. Пусть функция Кх) определена на выпуклом множестве и существуют симметричная неотрицательная на О функция тСх,у) и константа *>0 такие, что для всех х,уеО, а<=[0,и выполняется неравенство:

Кох+а-сОу) > а-ГСх)+С1-оО-ГСу)-аС1-а)*тСх,у). Тогда будем говорить, что функция ГСх) удовлетворяет на Б условию А с функцией тСх.у) и константой *>0.

- 4 -

В тех случаях, когда важно лишь подчеркнуть, что функция тСх,у) и константа * с данными свойствами существуют, а конкретный вид их не важен, будем для краткости говорить, что функция f(x) удовлетворяет на D условию А <5ез указания функции т£х,у) и константы х.

В параграфе 1.1 показано, что введенный класс функций достаточно широк. Он содержит часть выпуклых и некоторые типы невыпуклых функций. В частности, показано, что условию А удовлетворяют: всякая вогнутая функция FCx), определенная на множестве DçRn; квадратичная функция FCx) = <х, Ax>+<p,x>+q с неотрицательно определенной симметрической матрицей А.

В параграфе 1.2 обоснованы критерии принадлежности классу функций, удовлетворяющих условию А.

Теорема 1.5. Пусть

1) fCx) -непрерывно дифференцируемая на выпуклом множестве D£Rn функция,

2) существуют такие число у>0 и неотрицательная выпуклая по х симметричная функция тСх,у), что для всех x,yeD выполняется неравенство:

f(x)-f(y) > < gC х), х-у> -у • тС х, у). Тогда fCx) удовлетворяет на D условию А с коэффициентом х~2у и функцией тСх.у).

Следствие 1.1. Если D - выпуклое множество в Rn, ГСхЗеС1''CD), то fCx) удовлетворяет на D условию А с коэффициентом «=L и функцией тСх,у)=11х-у11г, где L - константа Липшица для градиента функции fCx).

На простом примере показано, что класс непрерывно дифференцируемых функций, удовлетворяющих условию А, шире класса С1 -'CD).

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

Теорема 1.9. Если fCx) выпукла на выпуклом множестве D£Rn и существует такая постоянная 0<с<+оо, что HsCx) !1 <о для всех xeD, sCx)€3fCx), то fCx) удовлетворяет условию А на множестве D с коэффициентом *=2с и функцией тСх,у)=11х-у11.

- S -

Теорема 1.10. Пусть

1) fix) - выпуклая на выпуклом множестве D£Rn функция,

2) существуют такие число *>0 и определенная на D неотрицательная симметричная выпуклая по х функция гСх,у), что для всех x,yeD имеет местс неравенство:

fCx)-fCy) > ГСх,х-у)-*-тСх,уЗ. Тогда fCx) удовлетворяет ка D условию А.

Основные свойства функций, удовлетворяющих условию А, исследованы в параграфе 1.3.

Теорема 1.11. Пусть для каждого iel=<1,2,... m) функция rtCx), x«sD£Rn, удовлетворяет условию А с некоторым коэффициентом *t и функцией тдСх,у). Тогда удовлетворяют условию А и функции

1) GCxD= £ XjFjCx) при всех ^>0,

2) QCx)= min F.Cx).

i Q 1

Основной результат параграфа 1.3 устанавливает следующая теорема.

Теорема 1.13. Если D - выпуклое множество, fCxJ- непрерывно дифференцируемая функция, удовлетворяющая на множестве DSRn условию А с функцией тСх,у) и с константой *, то для всех x.ysD выполняются следующие неравенства:

fCtf-fCy) i <дСх) ,х-у>-зе-тСх,у). <дСх)-дСу),х-у> < 2*-тСх,у). Приводящийся ниже результат позволяет проводить исследование функций, удовлетворяющих условию А, с помощью функции одной переменной.

Теорема 1.14. Для того, чтобы функция f(x) удовлетворяла на выпуклом замкнутом множестве D условию А с коэффициентом % и функцией тСх,у), необходимо и достаточно, чтобы функция pCU=f(x+te) для всех xeD и любого возможного в точке х направления еС lie 11=1) удовлетворяла условию А на множестве R(x)={t:

x+teeDj с коэффициентом ж и функцией TCt4,ta)=rCx+tie,x+t2e),

t ,t eRCx). 1 2

В параграфе 1.4 рассматривается соотношение некоторых классов функций с классом функций, удовлетворяющих условии А. Например, для равномерно выпуклых функций, исследованных Поляком Б.Т., установлено, что если модуль выпуклости Кх) таков, что ух,уеВ, уаеЮ,1]

ГСох+С1-а)у) = аЯхЖЬаЖуЬаа-аЖНх-уЮ; то ГСх) удовлетворяет условию Ас «=1 и функцией тСх.уЗ такой, что т(х,у)< £С11х-у11),

Рассматривался также класс слабо вогнутых функций, введенный Нурминским Е. А. Класс слабо вогнутых функций достаточно широк. В' частности, он включает в себя дифференцируемые выпуклые функции, гладкие и негладкие вогнутые функции.

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

Теорема 1.18. Если

1) Кх)- слабо вогнутая функция,

2) функция г(х,у) - неотрицательная симметричная выпуклая функция Спо каждой из переменных х,у), то ГСх) удовлетворяет условию А с «5:2 и функцией гСх.у).

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

Вторая глава состоит из 2 параграфов.

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

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

задачи

min fCxi, С 4)

хЭ

где fix)- непрерывно дифференцируемая псевдовыпуклая функция, удовлетворяющая на выпуклом замкнутом множестве DcRn условию А с функцией rCx,y)=llx-yllv, v>2.

В параграфе 3.1 введено понятие ¿-нормированного направления спуска.

Для функции fCx3, удовлетворяющей условию А на множестве D£Rn с функцией т(х,у)=11х-у!Г, v>2, введем следующее

Определение 3.1. Вектор 5*0 назовем ¿-нормированным направлением спуска (гг>0) для функции f в точке xeD, если выполняется неравенство

<gCx),s>+£llsliv<0, v>2.

Леша 3.1. Если направление спуска s в точке х для функции

ts

f не является с-нормированным, то вектор s = ПРИ

0<t,i |<gCx) ,s> | является е-нормированным при любом v>2.

Следующие утверждения описывают основные свойства е-нор-мированных направлений спуска.

Лемма 3.2. Пусть зафиксирована точка xeRn. Все точки zeRn, для которых векторы z-x являются е-нормированными направлениями) '!

ми спуска в точке х при v=2, принадлежат шару радиуса R= -

1 2е

с центром в точке u= х---д(х).

2s

Леша 3.3. Пусть:

1) 3 г>0 такое, что НдСх) 11<^<со, yx6GcRn,

2) sCx) - гг-нормированное направление спуска в точке xeG, тогда имеет место оценка

HsCx)II < (у/£У/<у-х \ yxeü.

Обозначим ? =

Се-х-'У"-", при е<х, 1, при е>х.

Лемма 3.4. Если 5 - гг-нормированное направление спускг функции Г в точке х, то для каждого /МО, 11 существует К=КС/3)>С

С1 —/ЗЭ1 такое, что для всех ХеСО.Х] выполняется

fC x5 -fCx+Xs) > -kß ■ <gC x5, s>, (5)

fCx5-fCx+\s5 > \ß-e\\s\\v. C65

Лемма. 3.5. Если s - ¿-нормированное направление спуска функции f в точке х, то 3 Х>0 [ такое, что для yx.eCОД] выполняется неравенство

fCx5-fCx+\s5 > -Х-[<gCx5,s>+ßllsllv]>0. С75

Предлагаются способы регулировки величины итерационного шага по ¿-нормированному направлению спуска.

Пусть s - ¿-нормированное направление спуска функции f в

А. ГА А. Л.

точке х, /?еС0,15. Определим множество JCi5=-|i.i+l,i+2r.. . J- для

некоторого i. Тогда значения удовлетворяющие условиям С5), С65,С7), можно вычислить, например, следующем образом. Выбрать П= Cl-ß)t^v-,>. 1=1 и определить 1*- наименьший индекс ieJCi), при котором выполнится неравенство:

fСх)-fСх+г)1 s5 > ~r)lß<gCx5,s>, С85

либо выполняется более слабое условие

fCx5-fCx+r/1 s5 > 77i/?sllsüv, С 9)

. *

затем положить Х.=т)1 . Из леммы 3.4 следует, что если е>х, то неравенства С85Д95 выполняются при i*=l. В этом случае шаг Х.=С1-/?5'/<v"1 1 по ¿-нормированному направлению спуска функции f в точке х обеспечивает строгую релаксацию функции.

В следующем способе выбора шага нелинейная часть аппроксимации минимизируемой функции учитывается явно: если выбрать TjeCO, 15, .1=0, определить i*- наименьший индекс ieJCi5, при котором выполняется неравенство:

fCx5-fCx+7?is5 > -т?1 [<gCx5,s>+<sl!sllv], СЮ)

ПОЛОЖИТЬ \=7)1 .

Получена нижняя оценка для величины шага по ¿-нормированному направлению спуска, не являющемуся; х-нормированным. Лемма 3.6. Если: 15 0<е<ж, /?<=С0,1); 2) s - ¿-нормированное направление спуска функции f б точке х, ко не *-нормированное;

35 i*- первый индекс i=l,2,..., для которого выполняется не-

г л ■ *

равенство С 85 ^С 93 J, Х=т7х ,

то имеет место оценка X > [с*"1 -CI-/?)2]1 /<v~11 >0. Замечание 3.1. Из леммы 3.6 следует оценка:

* >e-Cl-/3)2^"v. СИЗ

Аналогично оценке из леммы 3.6 можно получить для длины шага X, удовлетворяющей С3.93, следующую нижнюю оценку:

X > 75-CsK-,31/<v-t».

В этом случае для коэффициента к из условия А справедлива следующая оценка:

* >Ct)/X3v"1 •£. С12)

Далее оценки С11),С12) используются в алгоритмах для адаптации параметра е-нормировакия направления спуска.

В конце параграфа 3.1 описана процедура адаптации параметра «-нормирования направления спуска в зависимости от способа вычисления и величины шагового множителя. Эта процедура является общей для всех алгоритмов, приведенных в 3 главе. Сходимость алгоритмов с фиксированной константой е Спри произвольном соотношении е с величиной к из условия А) следует из сходимости адаптивных алгоритмов. Заметим, что параметр «, вообще говоря, заранее неизвестен. Поэтому на практике решающим для сходимости алгоритмов является выбор значения е близкого к величине * из условия А. Если выбирать параметр с слишком маленьким, то в силу формул С8),С9),С10) можно получить значительное дробление шага. При выборе значения с неоправданно большим можно замедлить сходимость метода. Поэтому наиболее целесообразно оценивать параметр е по ходу работы алгоритма. Неравенства С8), С9), СЮ),СИ) позволяют производить корректировку числа е, увеличивая его, если предыдущий выбор е был неудачным.

Пусть на k-той итерации Ск=0,1,...) некоторого адаптивного алгоритма ек>0 - значение параметра с-нормирования направления спуска. Пусть s^- -нормированное направление спуска функции f в точке хк; итерационный шаг Хк выбирается по одному из условий С8),С9),С10). Если ifc- наименьший индекс ieJCi), для которого выполняется условие выбора итерационного шага при x=xfc, c=cY , s^. Если ik=i, то при переходе к следующей - Ск+1)-ой итерации метода согласно леммам 3.4,3.3 целесообразно оставить неизменным значение параметра нормирования направления спуска, т. е.

положить -ск. Если же проверяемое в процессе дробления шага условие С8) Сили С9),С 10)3 оказывается выполненным при iK>i, то согласно оценкам СИ),С12) следует увеличить текущее значение параметра s-нормирования направления спуска, например, сле-дущим образом: =ск 'Cj., где î -i t.

(1-/?) , при выборе X. из условия С 8) или С9),

^u -ifc> (v-i > [ПШ ВЬК50ре х из условия СЮ).

С13)

т/г. илттгоиз Г 1т

Из того, что «<+сп следует, что после конечного числа увеличений параметра е в адаптизных алгоритмах САлг. 3.1, 3.2, 3.3, 3.4, 3.5) эта величина может превзойти и и перестать меняться. Пусть - номер итерации, когда оказалось выполненным £.>«, тогда' для ук>з выполняется ек>£^>*. В этом случае с некоторой итерации адаптивные алгоритмы начинают работать с фиксированной константой е-нормирования. направления спуска. Заметим, что с .¡-ой итерации значение итерационного шага становится постоянным: ук-.]- При этом для вычисления итерационного шага производится только два вычисления целевой функции Сдля проверки выполнения условий выбора шага).

В предлагаемых методах реализованы два подхода к решению задачи выбора ¿-нормированного направления спуска. При первом подходе задача выбора направления ставится специальным образом так, чтобы ее решением являлся ужо «-нормированный вектор спуска. При втором подходе задача выбора направления решается традиционными методами, затем к найденному подходящему направлению применяется процедура ¿-нормирования Св случае необходимости). Первый подход реализован в алгоритмах, описанных в параграфах 3.2.3.3, 3.6. Алгоритмы, предлагаемые в параграфах 3.4,3.5 реализуют второй подход.

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

Алгоритм 3.1.

Шаг 0. Выбираются точка хо€0, числа Э,7)<=(0,1), £о>0, 0<бо<1. В качестве способа выбора шага выбирается одно из условий

- И -

С8),С93,С10). Определяется правило изменения Ск так, чтобы (k>l, к=0,1,2..,

Шаг 1. Точка yfceD, к=0,1,... выбирается таким образом, что при 0<6<6k£l, ск>0 выполняется условие:

<gCxfc), ук-хк > +£к ИукIIv< 6kmini <д( хк), х-х^ > +sk llx^ II'v). С14)

Если <g(xfcD ,yJ;-xk>+£kllyk-xkliv=:0, то решение задачи С4), иначе V уfc-xk.

Шаг 2. Пусть ik~ наименьший индекс ieJCi) , для которого выполняется условие выбора итерационного шага при x=xk,s=sk, е=еу ,

тогда полагаем к-

Шаг 3. Вычисляем точку xk+j = х^+Х^, k=k+l. Шаг 4. Полагаем екн -еу -Ск и переходим к шагу 1.

Замечание 3.2. Если (к выбрать,^например, из условия (13), то (к=1 при ik-i и ( >1 при ik>i. Тогда на шаге 4 алгоритма происходит адаптивное изменение параметра &-нормирования направления спуска. При С =1, к=0,1,2... алгоритм будет неадап-тиьным.

Под xfc, k-0,1,2,... понимаются точки последовательности, вырабатываемой по исследуемому алгоритму.

Теоремы 3.1,3.2 обосновывают критерий остановки в алгоритме 3.1.

Теорема 3.1. Пусть fCx) - непрерывно дифференцируемая псевдовыпуклая на множестве D функция , тогда для того чтобы в точке xk<=D достигался минимум функции fCx) на множестве D, необходимо и достаточно, чтобы для всех xeD выполнялось неравенство:

<gCxk),x-xk>+£k Bjc-xJcIIv>0. Теорема 3.2. Пусть выполнены условия теоремы 3.1 и точка ук выбрана в соответствии с условием С14). Для того чтобы x^eD была точкой минимума функции fix) на множестве D, необходимо и достаточно, чтобы выполнялось равенство:

<gCxk),yk-xk>+£kHyk-xkllv=0. Следующая лемма доказывает ограниченность сверху параметра ¿-нормирования направления спуска в процессе адаптации.

Лемма 3.1. Пусть 1) sk, ksL - ек -нормированные направления спуска,

- 12 -

2) 1- наименьший индекс 1еД1), при котором выполняется условие (8) 9)] при х=х)с, к.

3) <хк> - некоторая итерационная последовательность, построенная по правилу: хк+1 = х^+^з^, кеЬ,

4) ео>0, 5к+1=скС1-Э)1_1к, кеЬ.

Тогда для ё= тах {е ,—1 >0 выполняется е. <с, укеЬ.

I с 1-13) к

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

Теоремы 3.3,3.4,3.5 позволяют получить общую оценку, выполняющуюся при 1,3,4 условии леммы 3.7 для различных способов регулировки шага. Эта оценка важна для доказательства теоремы 3.6.

Теорема 3.6. Если:

1) ГСх)- псевдовыпуклая функция, удовлетворяющая условию А на выпуклом замкнутом множестве д с константой *>0 и функцией тСх.у)=11х-у1Г, у>2;

2) числовая последовательность <8к>, определенная в главе 2, удовлетворяет условию: 39>0 такое, что 8к>8, ук;

3) 3 у>0 такое, что Нд(х) 11^<<я , ухё);

4) множество М1)СГ,хоЗ=-|хеВ: ГСх) 5 ~ ограничено;

5) шаги для всех кеЬ выбираются по одному из условий (8), (9), СЮ),

то последовательность <хк), ке1 сходится по функционалу:

ГСхк)-Г*~0С1/к).

Сходимость последовательности <хк> к решению задачи С4) (без оценок скорости сходимости) доказана при более слабых условиях в теореме 3.7.

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

- 13 - '

£-нормированность направления спуска. В параграфе 3.4 в классический метод условного градиента встроена процедура я-нормиро-вания направления спуска. В алгоритмах, предлагаемых в параграфе 3.5, выбор подходящего направления проводится на пересечении допустимого множества с п-мерным кубом, описанным вокруг шара, определяющего е-нормированные направления спуска при у~2. Поэтому задача выбора направления в этих алгоритмах - линейна. Для всех методов обоснованы оценки скорости сходимости.

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

4 глава состоит из 2 параграфов. В параграфе 4.1 описано 10 тестовых задач. В параграфе 4.2 приведены результаты численных экспериментов. Описаны два эвристических алгоритма уточнения параметра ¿¡-нормирования направления спуска, использованные в некоторых тестируемых методах.

Численная реализация 1 адаптивных алгоритмов подтверждает целесообразность использования процедуры пошаговой адаптации параметра е, описанной на с.10-11. Эксперименты показали, что, действительно, начиная с некоторой итерации происходит стабилизация параметра е-нормирования направления спуска. Отметим, что с этой же итерации величина итерационного шага становится постоянной. С этого момента для вычисления шага производится только два вычисления значения целевой функции для проверки выполнения условия выбора шага.

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

- 14 -

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

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

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

2. Введено понятие е-нормированного направления спуска. Изучены основные свойства ¿¡-нормированных направлений спуска. Предложены способы регулировки величины итерационного шага по гг-нормированному направлению спуска. Описана процедура адаптации параметра нормирования направления спуска в зависимости от способа вычисления и величины шагового множителя. Предложены и реализованы в алгоритмах дБа подхода к решению задачи выбора е-нормированного направления спуска.

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

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

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

ПУБЛИКАЦИИ

1. Габидуллина З.Р. К сходимости метода условного градиента для одного класса невыпуклых функций // Исследования по прикладной математике.- Казань: Изд-во КГУ, 1987.-Вып.14.-С. 15-25.

2. Габидуллина Э.Р. Сходимость метода условного градиента для псевдовыпуклой функции// Методы математического программирования и программного обеспечения.:СТез.докл. V научн.конф., г.Свердловск, 23-27 февраля 1587 г.)/ Свердловск: УрО АН СССР, 1987. - С. 29.

3. Габидуллина 3. Р. Об одном условии дифференцируемости выпуклой функции // Исследования по прикладной математике. -Казань: Изд-во КГУ, 1988, Вкл.15.- С.3-6.

4. Габидуллина 3. Р. Минимизация негладкой строго квазивыпуклой функции методом типа условного градиента // Исследования по прикладной математике. - Казань: Изд-во КГУ, 1989.-Вып.16.-С.97-101.

5. Габидуллина 3.Р. Адаптивный метод с регулировкой шага для решения задачи условной оптимизации // Матем. программирование и приложения.: СТез. докл. научн.конф., г.Свердловск, 25 февраля -1 марта 1991 г.)/ Свердловск: УрО АН СССР, 1991.-С.33-34.

6. Габидуллина 3.Р. Адаптивный метод с регулировкой шага для решения задачи условной оптимизации // Исследования по прикладной математике.- Казань: Изд-во КГУ, 1992.-Вып.18.-с.30-38.

7. Габидуллина 3.Р. К вопросу сходимости метода условного градиента для одного класса невыпуклых функций. - Казань, 1986.- 8с,- Деп. в ВИНЖИ 29.12.86 ,N8963-886.

8. Габидуллина 3. Р. Оценка скорости сходимости метода наискорейшего спуска для выпуклой негладкой функции. -Казань, 1986.- 5с,- Деп.в ВИНОТИ 29.12.86, N8962-686.

9. Габидуллина 3.Р., Заботин Я. И. Релаксационный метод для одного типа задач псевдовыпуклого программирования//Изв. вузов. Математика.-1993.- N12.-с.44-51.