Методы решения экстремальных задач, использующие негладкие и квадратичные штрафные функции тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Министерство просвещения Украины Киевский государственный университет им. Т. Г. Шевченко

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

НУРНАЗАРОВ ДОВЛЕТНАЗАР

УДК 519.853

МЕТОДЫ РЕШЕНИЯ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ, ИСПОЛЬЗУЮЩИЕ НЕГЛАДКИЕ И КВАДРАТИЧНЫЕ ШТРАФНЫЕ ФУНКЦИИ

Специальность 01.01.09 математическая кибернетика.

АВТОРЕФЕРАТ

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

Киев - 1992

Работа выполнена в Киевском государственном университеге им. Т. Г. Шевченко.

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

профессор Ю. М. ДАНИЛИН.

Официальные оппоненты: доктор физико-математических наук, чл.-корр. АН Украины, профессор ШОР Н. 3., кандидат физико-математических наук, доцент БЕИКО И. В,

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

Защита состоится с Ц- » До^ 1992 г. в /У^час. на заседании специализированного совета Д 068.18.16 при Киевском государственном университете имени Т. Г. Шевченко (252127, Киев, проспект Академика Глушкова, 6, КГУ, факультет кибернетики, ауд. 40).

С диссертацией можно ознакомиться в библиотеке КГУ.

Автореферат разослан « ■» Сгл^я^^ 1992 г.

Ученый секретарь

специализированного совета

- 3 ~

■^п^ц^ / Общая характеристика работы

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

Другая проблема связана с тем, что априори неизвестно значение штрафного параметра, поэтому для его подбора прибегают к эвристическим приеме". Это отражается как на качестве соответствующих алгоритмов - делает их не вполне конструктивными, так и на идеологии обоснования методов.

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

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

Научная новизна. В данной работе предложен метод градиент-

- и _

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

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

Разработали методы квадратичных штрафов, итерация которых заключается в решении линеаризованной задачи.

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

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

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

Апробация. Основные результаты диссертационной работы были представлены на Ш1-ХХП Всесоюзной школе-семинаре "Вопросы оптимизации вычислений" /г.Киев, 1990 г., п.Кацивели, 1991 г./, на научно-исследовательском семинаре Киевского государственного университета, БД АНР, Институте проблей кибернетики АНР, Институте кибернетики АН Украины, на I областной научно-практической конференции молодых ученых /г.Чарджоу, 1989 г./.

Структура и объем работы. Диссертация состоит из введения и двух глав. Объем диссертации стр. Список литературы вклю

Чает 441 наименования.

Публикации. По теме диссертации опубликовано четыре печатных работы.

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

В диссертации рассматриваются методы решения общей задачи нелинейного ьрограммирования:

§ с х-)

_ Л/

£ -[осе^: ¿о, С.{,р. кл^-о, ¡'--рТТ^п}

Введем следующие обозначения: дчсх) « и*»-*. { о, |С = 17р .

с ' '

Рс/Х) = , С^^ТР; 1 }

ъ { I-: ■>/ РСэс)-8) С Сё } ^ у с*) ~ II %С.эс>|1

/ * - знак транспонирования/, II • (I - евклидова норма в соответствующем пространстве.

Ч 1% °Ч ъ

>

В первой главе разработан метод минимизации негладких точных штрафных функций для задачи А/. Предлагаемый метод градиентного типа в отличие от других методов минимизации негладких втрафных функций не требует решения каких-либо вспомогательных задач, В точках, где Ч^.-ГО дифференцируема, для построения вектора сдвига в изучаемом методе используется направление градиентного типа функции ЧЧ^,^.

В §1.1 приводится описание метода градиентного типа. Упрощенная схема итерации метода имеет следующий вид.

Пусть ОС, - начальное приближение и выбраны £ , ,

Х> Х>° 3 .

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

- о^+^р^ > К а о,

/2/

я

/3/

где а выбраны из условия

Я Гсхо|1= Д нф'бх^Ц

/4/

г* У

Случай I. Пусть Фом^о, (КЛ >/ уФсх*) .Тогда

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

ющим образом.

Пусть наибольшее значение £ (о, 1] , при кото-

ром выполняется неравенство

Цос^^-^ежк) 4 К /5/

Если К) 4 ЧСЯк.Ю » то в качества • вкбв-

рается любое значение ои^ , при которой

^СХк.'+^Ю ^ /6/

Случай 2. Пусть Фс**) «¿о , И УК У ЧЧ&Л .' Возь-

мем

Ч'Ч^н.К) , а наибольшее значение

1] , при котором

Ч'С**-^, £/) - 4 ¿¿(ЧХъс^Ъь) /В/

Случай 3. Пусть = О . Возьмем - {Сзц} , а

значение оС*. определяется следующим образом. Вычисляется » удовлетворяющее неравенству /5/, Если =

то .Если Ч> С + Лу« Рк} "7 О , то в

качестве ^^ выбирается любое, значение о ^ <А 0

при которой выполняются соотношения

Y Coc^-tet-P^ о

На этом описание процесса /2/ закончено.

В §1.2 определяются основные предположения для дальнейшего изучения свойства метода и его обоснование.

Пусть ¿V - некоторое Бначение штрафного параметра,

СЭс-Хо.хЛ-^ я*-. Ч(хвгм}

1. Шюнество СЗсх.,гО ограничено. ■

2. Градиенты фуйкодй , §Л*> , t-i,i> ¡ •íi.feit ¿ - P+i, vn на множестве удовлетворя-

L

ют усдошО Диншица о константой L, .

3.'Есди «XcOtX-.jv) , ywyo ,?о

4. t/bífC*) f t-7 i для все* х£ • б. Неравенство

f* РП - { с*«0 ^ £ (_ fe*'. 19 рк 3' ДО/

выполняется прн -любом / ~ определяется из

/¿/А • '

• В §1.3 изучается сходимость метода. Формулируются и доказы-ваююя следующие утверждения.

Лемма 1,3.1, Если в процессе /2/ вектор Pt и параметр

выдираются опиоанннм выше образом, то при Ус-»<=>■=> .

Лемма 1.3.2« При предположениях 1-5 для изучаемого итерационного процесса /2/ найдется такой номер ус , что для всех к. справедливо УС*«) ^Ч^Сх«) ,

Лемма 1.3.3. Если в процессе /2/ ^ и р«. выбираются описанным выше образом, то существует бесконечная последовательность -[ос*.} , на которой выполняется условие

л <•

Лемма 1.3,4. Для процесса /2/, реализуемого описанным выше образом, выполняется условие

\1 г а* 11 ус ^ .

Теорема Г.ЭД./о сходимости/. Итерационный процесс /2/, в котором я. {>. выбираются описанным выше образом,. обладает следующими свойствами.

1. Множество X предельных точек последовательности

- связный компакт ,

2. В любой точке •хяг€ выполняются необходимые условия минимума для задачи /I/, т.е. существует . X -Ф о г танков, что

' Р I I Ы 1 4х

$ с*,) X А' о! с*^ -V 21 А.1„ к с*,) ■=. о * п им * 1 ■

г

^ §1.4 исследована скорость сходимости метода. Пусть X, -предельная трчка последовательности /2/ и выполняются следующие условия: \

а/ функции Асйо я » » ксх) ,

< . ___■ ' Л ■ £

I -Р+1,УпЛ двавды непрерывно дифференцируемы;

б/ существует вектор Х^о такой, что

I р • * • I

{с**) + Ц •+ 22 С«,) - о;

ь( выполняется достаточное условие локального минимума, т.е. ' рля всех Р*о „ ,

» • (З'.сл ),?>) > о , ,

* к I с #

Теорема 1.4.1 /о скорости сходимости/. Пусть последовательность г^сск.} , определенная по формуле /2/, в которой ^ ,. в Тк. выЗярастся описанным выше образом, сходятся к предельной точке и выполняются условия а/-в/. Тогда существует бесконечная последовательность {х^. ^ , на которой справедливы оценки

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

Вторая глава посвящена разработка метода квадратичных штра-. фов с использованием вспомогательных линеаризованных задач. Подробно изучаются свойства метода, в частности, вопроо об определении величины , регулировка длины шага, поведение последовательностей {HR.и} и -{11f1^»^} , вопросы сходимости и скорости сходимости. Рассматриваются модификации основного варианта метода, В изучаемом в диссертации методе для определения направления движения из точки оси используется вспомогательная квадратичная задача. Устанавливается, что существует значение штрафного параметра ft^ , при котором вектор является направлением спуска функцяи ЧЧ*, р.») из точки v«, . Величина ß«. зависит от Hft.ll и llf^OH . Регулируя длину шага таким образом, чтобы соответствующая функция ЧС.^, £«) убывала, мояно построить последовательность {_ ее*.} , либо сходящуюся к решению задачи /I/, либо в предельных точках которое в общих случаях выполняются необходимые условия экстремума задачи /I/. По своим свойствам изучаемый метод близок к методу линеаризации. Однако оа конструктивен в том смысле, что последовательность {.R*} определя-етЬя конструктивно.

В §2.1 изучаются общие свойства метода при выполнении следующих условий» а/ при любом к. с точка 'xKe<St? , где С2 некоторое замкнутое ограниченное множество; й/ функции ^СХ) , , f-С? .И Lex) ,

¿i P-tl, \м — непрерывно дифференцируемы на множестве градиенты jf'c*) , g!c*) , Ср и ¿'.сх) , L-- ы^ удовлетворяют условию Липшица о константой L ; в/ множители Лагранжа задачи /2.1.2/ ограничены на множестве GS* : .

1\ \\\ ± V ♦ X - вектор с компонентами X!- , с 6

Определение значения . Пусть й-^о - произволь-

яая постоянная. При > о в качестве штрафного коэффициента выбирается наименьшее число Б*., "г- •" ^ £ » при котором выполняется неравенство

(Ч'^-О,*«) а -Фс**), /II/

где ЧЧ*, + У Ось.) , Р„, - решение задачи

/2.1.2/.

Лемма 2.1 Д. Значение , определенное из условия .

/II/, обеспечивает выполнение неравенства

{*и> Р.) 4 - , ^ Ь Г-Тж ' /12/

Демма 2.1.2. Неравенство /II/ /а следовательно /12// заведомо' выполняется, если

Альтернатива. Если ¡величина определяется описанным выше образом, то либо при \с~*с~р , либо Ври

фиксированном » ^к-1' о ,

Лемма 2Д.З, Пуста. | - подпоследовательность из

/2.1.1/, на которо» £ ^ £ . . Тогда Кч,-* о

*ч I,.1 "с

4 ■ Я,****. 4.'N-+1 . В §2.2 изучается -сходимость метода.

Лемма 2.2Д. Если последовательность {х*} строится по методу /2.1 Л/-/2.1.3/, то 'УС**.) —* о при .

Теорема 2.2.1. Бели последовательность i'**1) определи- . атся /2.1.1/-/2 Л.3/, а значение R*. определяется описанным выше образом, то ори выполнении условий а/-в/ в любой предельной точке выполняются условия

С--1 1 úm ДЗ/

)í„<U*,) = o, £ to, t - Cp'Í t^PÍi^,. •

í* • ^

В §2.3 исследована скорость сходимости метода. Пусть . решение задачи /I/. В дальнейшем будем считать, что -

точка невырожденного минимума задачи Д/, т.е. выполняются следующие условия!

а/ в точке СС, выполняются необходимые условия минимума в форме /13/}

б/ выполняется достаточное условие локального минимума, т.в,

( ¿'С**,^ Р,Р) >° Для всех Р^о и удовлетворяющих условию («JttC^piao » ' ^fO , Í&^C*,) }

(^V'f>)=0 » ^с*0 • t-^P + i.V^. , ГДв L(X,X) -

функция Яагранха, а ¿'(осД) _ матрица вторых производных Le*A) f

В §2,4 рассматривается алгоритм, способ определения (¿^ которого несколько отличается от исходного. /II/. Кроме того, рассмотрена еще одна модификация метода, отличающаяся от исходного /2Л.З/ регулировкой шага. Скорость сходимости такого модифицированного процесса в невырожденном случае - линейная» Будем определять величину р.^ следующим образом: в качестве штрафного коэффициента выбирается наименьшее число >/

..»У/ В. > о , при котором выполняется неравенство /11/ и кроме того,

Д4/

где - произвольная постоянная. Естественно, изменение

способа определения не отражается на результатах лем-

1ш 2.1.2-2.1.3. Рассмотрим еще одну модификацию исходного /2.1.3/ процесса. Пусть •( произвольная последователь-

ность. Введем в рассмотрение функции

Ч1 С*, tfu.) ~ 4 с*) ■+ ^С«) /15/

где

* 11 A.C*o ¡1 ч i

/16/

JlC**) ХА - вектор множителей Лаграижа задачи /2.1.2/ в точке 5Ск. . Рассмотрим теперь итерационный процесс /2.1.1/ в котором Я. - решение задачи /2.1.2/, а множитель л*, определяется следующим образом: в качестве ^ выбирается наибольшее значение { , получаемое дроблением, при котором одновременно выполняется неравенство /2.1.3/ /где определяется условием /11/)ъ

Ч'Сх^Р^П - ЧС^,^) 4 £Л С^'С*^},?*) Д7/

Теорема 2.4.1. Если точка невырожденного минимума задачи Д/ и модифицированная последовательность сс^ , то скорость сходимости - линейная

its»

И«*- t.acjs-

где \с 7 ic0 , ко - достаточно большой номер.

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

Основные результаты, полученные в диссертации, состоят в следующем:

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

2. Доказана сходимость алгоритма и получена оценка скорости сходимости.

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

4. Предложены конструктивные способы регулировки штрафного параметра. Рассмотрены вопросы сходимости и скорости сходимости.

Список публикаций по теме диссертации I. Данилин Ю.М., Нурназаров Д. Алгоритмы оптимизации на основе бесконечных штрафов //Методы решения экстремальных задач .и смежные вопросы: Сб. науч. тр. - Киев: ИК АН УССР, 1989. -С. 34-39.

- 16 -

2. Данилин Ю.61., Нурназаров Д. Модификация метода градиентного типа для минимизации негладких штрафных функций //Вычислительная и прикладная математика: Сб. науч.тр. - Киев:КГУ, 1992. - 73. - СЛОв-ИВ.

3. Нурназаров Д. Об одном варианте метода квадратичных штрафов . на основ® линейной аппроксимации /Киев, ун-т - Киев, 1989,

- 7с. - Деп. в Укр.ШИНТй И.05.89, Ш48-Ук 89.

4. Нурназаров Д. Программа для решения задачи нелинейного про» граммирования методом квадратичных ¿аграфов. - Киев: ЙК АН УССР, 1989. ГосФАП #50830001090,

-уь-л^

Зиаэ 47,тир. ЮО.Кмавсгий уаивврснтвт жм. Т.Шв»че«о.К»е»,Булыир Шввчешсо, И!