автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Методы конечных штрафов в нелинейной условной оптимизации

/о?

уи/

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

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

ПАНИН Виктор Михайлович

УДК 519.853

МЕТОДЫ КОНЕЧНЫХ ШТРАФОВ В НЕЛИНЕЙНОЙ УСЛОВНОЙ ОПТИМИЗАЦИИ

05.13.16 — применение вычислительной техники, математических моделей и математических методов в научных исследованиях

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

Киев 1989

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

Официальные оппоненты: академик АН УССР

ЕРМОЛЬЕВ Ю. М„

доктор физико-математических наук ЕРЕМИН И. И.,

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

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

Защита состоится «-» - 19 г. в -

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

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

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

Автореферат разослан «-» - 19 года.

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

АНДОН Ф. И.

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

Актуальность темы. Метода математического программирования играют важную роль при решении многих задач экономики, механики, физики, используются в научных исследованиях. Основы численных методов условной оптимизации были заложены в 40 - 60-х годах в работах Г.Данцига, П.Вулфа, Дж.Розена, У.Зангвилла, Г.Зойтевдей-ка, Р.Куранта, Р.Вильсона, Г.Келли, П.Хьюарда, А.Оиакко, Г.Мак-Кормика, Р.Гриффита, Р.Стюарта. Все возрастающая сло.яность и расширение круга решаемых задач потребовали разработки более эффективных алгоритмов, обладающих нелокальной и ускоренной сходимостью, устойчивостью, сокращением объема вычислений, удобством программной реализации.

Значительный вклад в их создание внесли В.С.Михалевич, A.A. Самарский, А.Н.Тихонов. В настоящее время численные методы нелинейной оптимизации получили развитие, главным образом, в работах Б.Н.Пшеничного, Ю.М.Ермольева, И.В.Сергиенко, Ю.Г.Евтушенко, В.Ф.. Демьянова, И.И.Еремина, Н.З.Шора, Ф.П.Васильева, В.Г.Карманова, Б.Т.Лоляка, В.В.Федорова, Р.П.Федоренко, З.Н.Малоземова, Ю.Г.Голь-штейна, Ю.М.Данилина, А.И.Голикова, В.Г.2адана, А.С.Антипина, Н.В.Третьякова. Из зарубежных авторов наиболее активны в их раз-• работке Р.Флетчер, М.Паузлл, З.Гиля, У.ййэрреЯ, Р.Ж^фшн, С.Хая, Д.Мейн, Н.Каратес, О.Мангасариан, Д.Бергсекас, Т.Колемап, Э.Конн, М.Биггс, Х.Уррути, К.Шиттковский, К.Кивил и рад других.

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

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

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

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

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

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

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

Апробация работы. Основные результаты диссертации докладывались на научных семинарах Института кибернетики имени В.М.Глусжо-ва АН УССР и ЛГУ (I9S3-I9G9 гг.), МГУ (1983 г., IS09 г.), Института системных исследований ПАН (Заршава, 1987 г.), всесоюзных семинарах "Вопросы оптимизации вычислений" (Алушта, 1987 г.; Киев, 1909 г.), 6-й конференции "Методы математического программирования и программное обеспечение" (Свердловск, 1989 г.), семинарах Киевского госуниверситета (1989 г.), ВЦ АН СССР (1989 г.), Института проблем кибернетики АН СССР (1989 г.).

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и трех приложений. Об<ций обьем диссертации - 212 страниц.

Публикации. По теме диссертации опубликовано 30 работ, основные результаты отражены в приведенном списке литературы.

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

В главе I. изложена постановка задачи и приведена схема построения методов конечных штрафов. Исходная задача: найти

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

xeQ

min

Градиенты > , о,1г..,т+Ь , предполагаются удовлет-

воряющими условна Липшица.

Через У* обозначается множество точек е , в которых выполняются необходимые условия экстремума задачи (I), А. -множество соответствующих им векторов множителей Лагражка =

= < \\ > , I т.. Всвду векторы ^ < ^ > рассматриваются как вектор-столбцы, вектор г с компоненташ-векторами

обозначается ъ = <■ > . Под решением задачи (I) подразумевается отыскание точки .

Задаче (I) ставится в соответствие безусловная задача дискретного миншлакса

mi.IT, \plVj\f) = rn.Cn. тДИ Ч^С'ь.'О ,

ТС. \ X.

(2)

где = £о<-х> , ** Ы^ЛЮ , г =

« 1,..., m-.it £ lx^ -- I .<.*> , j ;

tn.fi «"-' '

^ > 0 - коэффициент штрафа. ,

В (2) = ■ { (х) - недифференцируемая

штрафная функция, р\чо = °т.<х*.|ол } ,

1*1,..,т., j = 1,..., 4 . Множество пар < ; > Куна -Таккера задачи (2) обозначается, Ц,^ > .

Недифференцируемые штрафные функции впервые рассматривались С.Эблоу и Г.Ерайхемом (1955 г.). В нашей стране они начали изучаться И.И.Ереминым (1966 г.) для задач выпуклого программирования и позже исследовались различными авторами для более обидах задач оптимизации. Основным результатом этих исследований было установление факта существования порогового тако-

го, что при любом фиксированном значении N > , называемым точным коэффициентом штрафа, решения задач (I) и (2) совпадают в окрестности точки ,

Лемма I. Если при некотором \ „ = ^ с х,) выполняется

14 \ ' * N , (3)

. I*«

то *» с . Обратно, если % е , то среди век-

торов начнется удовлетворяющий (3).

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

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

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

Здесь $ е. Е - дополнительная переменная ; ^ 1Х> -= ^ '^^к^к)!'""«) . 1" симмет-

ричная неотрицательно определенная ( А „ % о ) ограниченная при к — о" матрица п. * п. ; А^и-х^!2 = ( А-ч <-,,с-хн), * ) « х * " «а-х I х ^ , ^ =1,...,п. ; 17 к ■> О ; 5 и у - положительные константи. При Ак > ° ограничение н^-^кЧоо л у в (4) отсутствует.

Задачу (4) можно рассматривать как минимаксный аналог вспомогательных задач методов Гриффита - Стюарта, линеаризации, Ньютона и других, записываемых в общем виде:

Х 1 1 * * <5>

- I , 5 ) , «*-*„ ч « у , Ан»о ^

1у ■ А15 \

где выбор матрицы определяет тип метода } к > =

" + , «<мт» г* . Задача (5) в ука-

занных алгоритмах предполагается разрешимой, множители Яагранжа -.ограниченными по процессу.

Через < х^ •, у и. ^ > , "Л к > обозначаются пары Куна - Танкера соответственно задач (4),(5);и-ч = 1 6

и ^ к = < > > € I к 7 - векторы их множителей Лагран-жа; » о для ¡- £ О* , ^ „ ° 0 для ] £ ; =

, , ^-и'Ч .

В отличие от (5) вспомогательная задача (4) разрешима в любой точке ** « , а вектор * принадлежит единичному симплексу.

Леша 2. Условие ^ ■ > выполняемое для

всех решений *к « X „ задачи_(4), достаточно, а при <>«0^

и необходимо для того, чтобы X » У .

к , /

Следствие I. Если равенство { = спра-

ведливо для некоторого * к е X ^ , то задачи (4) и (5) эквивалентны, т.о. « У* ,< п > *■ А * . 1 с 1 н- •

Достаточным условием эквивалентности задач (4), (5), эффективно проверяемым при реализации итерационного процесса со вспомогательной задачей (4), является неравенство

т * I

2 4-- 1 I т«4»41

^ 1 '

где в « юм) - любая константа.

В случае эквивалентности (4) и (5) при постоянном ь/к ш и методы решения задачи (2), базирующиеся на (4), можно рассматривать как методы решения исходной задачи (I). Соответственно формулируются и признаки сходимости -х. к —- или I,,-исходя из выполнения соотношений « —0 (ПРК

А к > о ) или = —* 0 % и из эк~

вивэлентности вспомогательных задач (4), (5).

Величина называется полной невязкой системы условий

оптимальности задачи (2); 4 0 при любом е ; х^ м при ^ ч = 0

Схема построения методов конечных штрафов (МКШ). Выбираются скалярная функция со с £) >0 (и) (£) —<*> при £ _ *» ) и положительные числа с , 10 , £ , у , £с(оц) , .9 е (о.ц) Описание к-й итерации процесса «к.^» * ♦ и-крк- * =о,<,.~.

Шаг I. Определив Н * = (. ^ ^ 3 , решить задачу (4) и двойственную к ней и найти и. к , , полагая и.^ = о

для 1- 2 О к . Если у ^ = «о, то = -

процесс окончен. Если - 0 , ^ + >0 ,т0 положить

^ к + л - ^ к * 1 - итерация закончена. При * к < о переход к шагу 2.

Шаг 2. Вычислить J- как наибольшее-из чисел j. = а

*

$ » o,i,... , таких, что

if 6 f <Ж,Л) . o<«<t.(6)

Шаг 3. Если 14 « С. , S Iй-к) > 0 .то принять С к ^ i ' £ к * i ; при нарушении хотя бы одного из этих условий положить = 2к . Конец итерации.

Основанием для выбора Х„ из условия проверки (6) является Лемма З.Пои любых * к е Е , справедливо нера-

венство 3 <р схк , (V ^ ) / дрк & vj» , где Bipix^) / Эр - производная функции i *■, м ) по направлению воктора р в точке * .

Обозначил i;. = J- ,

Qo«.*) »{ j + t | f\«) = I f Л*>| } , R IX) = eolx) и Rt tx).

Определение. Ограничения задачи (I) называются регулярными

в точке х , если для любого некулевого \ е е j TaK0r0i

что "Xй JO, ¿е R^ix) , si.g.tx 'Х - , je (?„<«) | f/*)*0,

выполняется £ Äli! * ° , i. e r i * >. t c

Ограничения (I), регулярные в каэдой точке х , называются регулярным на Е ; точка * , не являющаяся регулярной, называется стационарной для ограничений в (I).

Теорема I. В МКШ либо генерируемое w* -— и тогда

любая точка сгущения г последовательности ^ х к } является стационарной для ограничений в (I), либо величина = ы при w » к о постоянна и тогда г е t —* о г Vu.^ —-

. i. „, m*4 nwt+j

A#, , J - Л, , j.^.t ,

вспомогателыше задачи (4), (5) после некоторой итерации эквивалентны и для каждого продельного ^ » 6 А. * выполняется

\\1\ 6 вН . (7)

i » 1

Предположение огршшченности ixK \ влечет существование точек сгущения "Z. . Согласно теореме I для задач (I) с регулярными ограничениями оно гарантирует стабилизацию = Ы и сходимость к искомому решению.

При решении задач выпуклого программирования, когда сильно

выпукла одна из функций > 1 = >■,■■, т. ( мкш гарантируют

ограниченность { « * } и тем самым - стабилизацию ы к » Ы и сходимость к решению. В более общих задачах (I) с регулярныш ограничения/ли, для которых линии уровня функции Р ком-

пактны, ограниченность {х*- } достигается путем незначительной модификации описанных алгоритмов. С этой целью в точках , лежащих вне некоторой окрестности множества О- , при определении -1 к достаточно кроме (6) обеспечить еще выполнение условия релаксации функции р ) .

В главах 2-4 изучаются асимптотические свойства 1.Ш1 при решении задач (I) с регулярными ограничениями; генерируемая последовательность 4 * к ^ предполагается ограниченной.

Во второй главе рассматриваются МКШ первого порядка со вспомогательной задачей квадратичного программирования, когда ДЛЯ любых же М , К « 0,1

2 2 а. и*, и 4 с А^х.-к) 6 А «XII , А * о- > 0 ,

где А я о- - константы.

Первым таким алгоритмом, использующим недифференцируемую штрафную функцию ^ <.*, к/> , был метод линеаризации Б.Н.Пшеничного. В нем Е - единичная матрица, вектор рк определяется из решения задачи (5), а «ь * - из условия проверки неравенства

Т ""-Рк-.^ * ~е А ^ А*Р*>РкЬ 0<£<1-(9)

Значение точного коэффициента штрафа N при этом предполагается известным, задача (5) - разрешимой, генерируемые ^ * - ограниченными г") процессу величиной Ы

Методы конечных штрафов устанавливают сходимость к решению без этих предположений. После стабилизации ы к » N • они характеризуются формулами (4), (6), (8). Так как при задачи (4), (5) эквивалентны, то отличие МКШ (4), (6), (8) от метода линеаризации (5), (8), (9) вблизи решения определяется неравенствам (6), (9), участвующими при отыскании . Взаимосвязь методов в окрестности решения устанавливается соотношением

"V* = + где

Отметим, что число дроблений единицы, необходимое для вычисления ' J-* , в обоих алгоритмах равномерно ограничено: i , ^ >о - константа. .

Пусть = R.^iUR^V , к Ч LeVV \

> ° , ь. » f1* ) - f 1 •

* J» "vt \ w » к ' * О *

Оценки скорости сходимости ЖШ (4), (6), (8) получены в зависимости от выполнония различных видов достаточных условий минимума задачи (I):

а) функции i0<-*> » , , выпуклы ,

с . . j « i....,t линейные с линейно-независимыми

градиентами;

б) градиенты {L > L 6 R <■"*». 1 , линейно-независимы , i в ix, ii <n. , и для всех -х. , таких,что

(•f1. (.*,) «о vieR^-**), выполняется условие

¿«»ч1 4, U и ,1,1*,*) 4 , £*t>°, (10)

где - функция Лагранжа задачи (I); ¿и t - констан-

ты; вторые производные i«) , ft i*} , le С*-*.) , непрерывны в окрестности точки ;

в) градиенты f'L <••*») , l е Q it,) , линейно-независимы,

> о для i.e. Rj.it,> И lRi*„>\»n. .

В условиях а) - в) не фигурирует требование строгой дополняющей нежесткости "Х1, & о для всех l « йс«„)

Теорема 3. Для МКШ (4), (6), (3) имеют место следующие оценки скорости сходимости: I) при условии а) « о(к-1) г к р. ; если, кроме того, матрица ä w постоянна, то *к .—- с У. » ; 2) при условии б) ь. w+t <= йк , К« \\ • « С , где С > о и ¡1, « («)») - стандартные обозначения констант; 3) при"условии в) в окрестности предельной точки будет Xw=i и х w —1- с квадратичной скоростью: «хнч1-х)1ц s С it,-*, \\г .

На основании результатов теоремы 2 установлены оценки скорости сходимости метода линеаризации.

Теорема 3. Для метода линеаризации (5), (8), (9) в окрестности решения справедливы утверждения 2) и 3) теоремы 2.

Одгапл из.МКШ рассматриваемого типа является параметрический метод линеаризации, в котором А = а-, £ , а-ч">° ~ па_

раметр, + при _ <\ , = при

J- v = l . Условие \ ^v w \ s с ка шаге 3 этого метода заменяется на ».„Ц^Ц 4 С .

Цель введения параметра - добиться стабилизации значений J. w « i , , для сокращения объема вычислений на ите-

рации.

Теорема 4. В параметрическом методе линеаризации значения = а( и = i при к * к-0 постоянны и справедливы все утверждения теоремы 2.

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

В главе 3 рассматриваются линейные методы конечных штрафов (ЖОП) со вспомогательной задачей (4) при A w « о , индуцированной вспомогательной задачей Гриффита - Стюарта (5), когда Л = о . Алгоритмы на базе линойного программирования наиболее полно разработаны в настоящее время для решения задач (I) с линейными ограничениями. Трудность построения эффективных методов с линейными вспомогательными задачами (5) для решения нелинейных задач (I) вызвана, в частности, возможной несовместностью участвующих в (5) огршшчений, отсутствием правила выбора под- „ ходящих 5" и у . На отсутствие процедуры выбора параметра у , согласующейся с оценками скорости сходимости методов градиентного типа,, указывали Ф.Гилл, У.Мюррей, Б.Муртаф.

Изучение свойств ЛМКШ проводится на основе Ш1ализасоставляющих ё ^ , оt к полной невязки ^ к = & ^ + cl w ш

Вместо параметров S и у в задаче (4) фигурируют соответственно и у ^. Для всех рассматриваемых ЛМКШ сохраняется общая схема построения МКШ, но на шаге 2 определяется ■ как наибольшее из удовлетворяющих (6) значений

■J. = г"\ып.К; 'J \ , ^о,!,... . (II)

В зависимости от способа выбора и ^ исследуются различные типы ШКШ. При постоянных %« , ^ > о стаби-

лизация к к0 , и сходимость к решению сле-

дуют из теоремы I.

Теорема 5. Для ЛМКШ с постоянными > 0 , у* >о ет место Ъ к е V ; при условии а) справедлива оценка ь к = = О (к'1) , к-»» , при условии з) - квадратичная по * сходимость в окрестности ТОЧКИ х# .

Оценка л = ) , характеризует медленную

сходимость процесса и типична при условиях а) или б) для методов последовательного линейного программирования с постоянными % * , V к .

Ускорения сходимости удается добиться за счет управления параметрами , %« • При этом теорема I становится неприменимой.

В ЛМКШ первого типа (методы 5 -спуска )

£ Г , < кМ 1/2 ,

а величина в (II) заменяется на

5

к-

" 1 о:

о 4 "о ,

Теорема 6. В ЛМКШ с управляемым ° -спуском величхша N к = Ы при к * к-в постоянна, $ е ^ ог к —»• У „ при к —* <» . В точках некоторой подпоследовательности -С^-ь } из {^Л имеет место сходимость по двойственным переменным, ^ о , вспомогательные задачи (4), (5) в точках ^ эквивалентны и любой предельный вектор "К л е Д ^ удовлетворяет (7).

Оценки скорости сходимости метода установлены для случая, когда -ь = о , а предельные точки строго регулярны, т.е. векторы <*„) , 1«1!1»,) , линейно-независимы, "X1",, ^ о для всех с е я I -в, ) .

Теорема 7. Если предельные точки е строго регулярны, то справедливы утверждения теоремы 2 об оценках скорости сходимости.

Теорема 7 устанавливает более сильные результаты, чем известные для линейных методов с управляемым -спуском , в частности, полученные для метода наискорейшего спуска Г.Д.Майст-ровским л Ю.Г.Ольховским.

Эффективность всех методов 5 -спуска, в значительной степени зависит от выбора начального и от способа дробления . Более предпочтительными представляются ЛМКШ с управлением нормой вектора спуска рк посредством изменения параметра ук при постоянном 5К = 5 >о, в § 4 - 6 главы 3 изучаются два таких метода.

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

со = гп-^-п. т,а-х (ч> с* ,^ ) р) * 11 ?н»6 У *

где у >0 - произвольно выбранная константа.

Значение со ч учитывается при отыскании вектора спуска ?к из решения основной вспомогательной задачи (4), в которой

- < п11( = 01,\о.

Схема * -й итерации метода: определение вектора спуска р^ (задачи (12), (4)), отыскание (соотношения (6), (II)), вычисление (шаг 3 МКШ, в котором условие ¿(а^) > © заменено на 2 1©^) ® , где - вектор множителей Лагранжа задачи (12)).

В этом методе процедура

У . 1

\ 6К/, . , г .. а

имеет цг.'ью, в отличие от предыдущего алгоритма, стабилизацию при к г к-„ такого = 5"» > о , при котором^ 1 =

- 1

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

Второй линейный метод с управлением нормой вектора спуска, названный нормализованным ЛМКШ с эффективным выбором у , ис-

пользует на итерации лишь одну вспомогательную задачу линейного программирования. Он учитывает специфику присутствия в задаче (I) простых ограничений, когда * « Q (\Х , где

У = (*\ f w). »-«'to, ft*>a *-6S so, } ,

4 1

?+ и - заданные множества индексов из (i,...,n. }

Ограничение * е / = I i^ t-зО « о , j е = и } включается в качеству дополнительного в линейную вспомогательную задачу (4). Через "X, , \ обозначим векторы множителей Ла-гранжа задач (I), (4), относящиеся к ограничениям -f. i^t) «■ о , i е 3" .

В (4) величина у определяется через множители Лагранда по их предыдущим значениям:

I - ? 1/г 1

У*. = ma* « ; \ J ,

Здесь у , 1 6 Q к , выбираются принадлежащими единичному симплексу. Для этого вначале полагается и. ^ = ^"k-i лля

i-e Q w П Q K_t I . ^ - Для остальных Если эе = 1 - ZI г 1 >о, где t е Q , то к первоначальным u. ^ добавляется слагаемое «в w / \ Q w \ , и они вновь обозначаются CL ^ .

Алгоритм стартует из произвольной начальной точки еХ с любыми фиксированными ye>°, S ^ = ^ > о .

Схема к -й итерации второ^ метода: I) вычислить ук , 2) определить р^. , -J , u, к , "X и из решения задачи (4) и двойственной к ней, 3) найти ч , используя соотношения (6), (II), 4) определить согласно шагу 3 схемы МКШ с за-

меной в нем неравенства * с на . « с/tvi .

Теорема 8. Для нормализованного Л1ЖШ с эффективным выбором у ъ имеет место сходимость к множеству <Х»,1\„,Л.„.> ; ^-о, у^ —► о , Э w 4 -i . При к -s к0 величина ы к = Ы постоянна и удовлетворяет (7), вспомогательные задачи (4), (5) эквивалентны ий- = и.

Оценки сходимости метода установлены при выполнении соответствующих условий а) - в) главы 2, в которых = U R. i*1«),

1 .0.1,а , Rai-x#) = \ \ i К

Теорема 9. Если ограничения { *.*> , i е {^....m+t} U "J , регулярны в области X , то справедливы все утверждения теоремы

2 об оценках скорости сходимости.

По своим свойства;.! второй метод полностью аналогичен методам последовательного квадратичного программирования первого порядка.

Вследствие эквивалентности при задач (4), (5)

ЛМКШ можно переформулировать в их "локальной" форме, базируясь на вспомогательной задаче (5), приведенной к традиционному виду:

m-un. { lx> 1 { ix) SO ttl" ,

f i*) --о , iel \

1 '

(13)

где I , Iн -множества ^-активных в точке ограничений - равенств и неравенств. Аналогично записывается и задача квадратичного программирования (5), (8).

Величины +к , , /у в терминах решения вспомогательной задачи (13) или (5), (8) вычисляются по соответствующим фор-

£. л I , , гп+ и

мулам путем замены в них = А „ , <■ - • \ и. -

" к- ) , где через л обозначены множители Лагранжа задач (13) или (5), (8), I = 1.....т.-а .

Схема построения всех МКШ первого порядка в их локальной форме аналогична схеме метода линеаризации. Без описания процедур выбора и к-я итерация процесса схематично может быть представлена следующим образом.

Шаг I. Из решения задачи (5), (8) или задачи (13) найти Р к > ^ к

Шаг 2. Вычислить

Г гп + 1 1 т 1

N • г -Ы (V" \ I = г ■

X I К-1. > I -1. " \ ■* 1 ~ 1

Шаг 3. Определив = К***-« найти из условия проверки выполнения неравенства (6).

Для нелокальной сходимости этих методов необходима разрешимость задач (5), (8) или (13) в каждой точке процесса и равномерная ограниченность генерируемых > к , ^ . Оценки их скорости сходимости вблизи решения вытекают из соответствующих теорем главы 2 и 3.

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

По аналогии с (5) вспомогательная задача, аппроксимирующая исходную, для методов второго порядка имеет вид

Un.fi + (.-ас-х \ \ Г

« »» г «■ * * Чу

IX} 6 О I е I I (14)

Здесь - линейная аппроксимация функции <-х.) в точ-

ке

и - симметричные неотрицательно-определенные матрицы п, * п. «В качестве и мргут выступать, в частности, вторые производные функций Г I») или их аппроксимации.

Ограничения вспомогательной задачи (14), как правило, несовместны вдали от X, . Методы конечных штрафов исключают такую несовместность. Они изучаются на примере исходной задачи, в которой t » 0 .

Соответствующая (14) вспомогательная задача имеет ввд

(15)

где обозначено ф V.*, ы^л а Г <.•*) • ч>. и.к/ «

- *ок1Х> Кк ^ , I « I „ .

Задача (15) используется для построения нелокально сходящихся ШСЦ до второго порядка включительно по описанной в главе I общей схеме.

Особый интерес представляет случай

л 1 —* ~ (| ^

АК я а , о, и,..,™, (16,

г

где м- вычисляются через "-^-г по описанному выше правилу.

Вспомогательная задача (15), (16) индуцирована методом Ньютона, предложенным в условной оптимизации Вильсоном (1961 г.)

и основанным на использовании вспомогательной задачи (14) при

В предположении, что задан коэффициент штрафа ы , мажорирующий генерируемые X ^ по процессу, и матрица А ^ = » в (14) удовлетворяет (8), нелокальная сходи-

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

Предложенный в § I главы 4 демпфированный метод Ньютона со вспомогательной задачей (15), (16) построен по схеме МКШ. В нем на шаге 3 вместо » Ч1 * \ с проверяется неравенство

и р к И ь о / Ы к ,а процедура вычисления , следующая: если н & г „ « * £ , , го полагается « 1, в< * / а ; в противном случае X к определяется из условия проверки выполнения (6) и принимается = ■$> к • Здесь

= < Рк ; -ак-г)> . р. - « 1 •

Теорема Ю. Если функции ^ с*) . с , выпуклы,

а }о I *) сильно выпукла, то в демпфированном методе Ньютона со вспомогательной задачей (15), (16) при любом хв е е после некоторой итерации величина Ык - Ы постоянна и удовлетворяет (7), а, . , л, - ^ЛДк-!) и —> < *« ; . Если, кроме того, точка *. строго регулярна, то Л, 1 и имеют место известные для метода Ньютона оценки сверхлинейной или квадратичной скорости сходимости по.аргументу г =<«;\>.

Оценки скорости сходимости других методов второго порядка изучаются по единой схеме .для локальной формы (6), (14) при условии, ЧТО ДЛЯ ЛЮбЫХ X €. е , < =0,1,...

С ||1|| 4 ( и + \ ь1 и ХЛ < С ИХ« с г С >0 (Г7)

1 4 I * 14 * К-]'/ £ > г 1>4 '

величина г/^. = м постоянна и удовлетворяет (7) г < '5СК5'ХК.>

— < Л,> .

Теорема II. Если <£ к = { при т. ка , то 11 РЛ * 1,-1 «Р*^ \1 ,

где

-1 Г 2 -I*

, = г + (г и>"*) + т. а> 1

V, = И С*«-!.») - Ак.4 * £ О^Ч-^'О 1 .

. ГП_ £

к - наименьшее собственное число матрицы * -г (а

+ б»1"».- , х «--!,;. и «ц..!^ - промеяуточные в

интервале точки разложения в ряд Тейлора.

При ~ % <1 теорема II устанавливает более

сильные, чем доказанные'в главе 2 и 3 оценки Я -линейной скорости сходимости, поскольку относятся к » р к \\ . Это обусловлено требованием выполнения неравенства (5) при к = 1 . Для метода Ньютона оно, вообще говоря, кэ имост мсста С эффект Маратоса ). Полученная для =1- к оценка снизу позволила провести анализ условий; которым должна удовлетворять исходная задача или параметры метода, чтобы = 1 . Исследованы оценки скоро-

сти сходимости алгоритмов оптимизации с различной комбинацией значений «« Е , £\*к) ; 6^ =

параметр. В частности, тлеет место ведущий результат. Следствие 2. Если А = ' , = , ^^1,...,™.

то при к % к-о эффект Маратоса отсутствует С X 1 ) , н рк \\ б

- > ^к-т.-* ° ' 2СЛ1! ВТ0РЫе ПрОИЗВОДНЫв ^ < * > » и з 1-*, ^удовлетворяют условию Липшица, то

ЦРК \\ - СП^к-У'*^8''.

При выводе последней оценки требование линейной независимости градиентов , «• е е <•*» > , отсутствует, а исходная задача (I) для любых I е Е° . ^ 6 Л, удовлетворяет условию (10).

т х

I

В § 4 главы 4 ШОП распространены на нелинейную задачу' дискретного минимакса

т.1- IX. (\х> = гмип- т« . .

гдо 3 4 о , , - о,

^ - О, с

Аналогично (4) вспомогательная задача г.КЛ первого порядка записывается в виде

\ »»-*„.«.. - У ,

* м(19)

где 1)" и ( - дополнительные переменные; С?к и - соответствующе множества ^ -активных функций ^.^и ограничений; ^к1"1,5 11 - линейные аппроксимации соответствующих

функций в точке .

Обозначим О IX) = т.о./ (о , К'*) . ГДе

При решении задачи (18) структура построения МКШ со вспомогательной задачей (19) сохраняется прежней и их сходимость доказывается по общей схеме. При к ? к-0 , когда и ,

вспомогательная задача (19) становится эквивалентной следующей:

± \ У ,

Оценки скорости сходимости установлены в зависимости от достаточных условий минимума а) - в) главы 2, в которых, однако, в качестве линейно-независимой фигурирует система векторов

где о - некоторый индекс из ; й^х^ и

соответствующие множества "активных" в точке х.^ функций I1 <.х; И

Теорема 12. Если векторы f . <•*•> , j е R j lao , аффинно-независимы, ограничения в (18) регулярны, а генерируемая последовательность к- } ограничена, то для ЖШ первого порядка со вспомогательной задачей (19) справедливы все соответствующие результаты, установленные при решении задачи (I).

Аналогично формулируется утверждение и для методоз зторо-го порядка.

В § 5 главы 4 построен аналог параметрического метода линеаризации для решения задачи непрерывного мшшмакса

miru В min. ™м f (х, и )

Т хеХ ^У 7 '

где У с £ и Ч с Е - выпуклые компакты, функция f ) непрерывна по совокупности аргументов , у. ; 5 ^ ) удовлетворяет условию Липшица по * для каддого ^ е У .

Алгоритм, генерирующий последовательность х = х +1 (.х--ж ), к-= 0,1,...,заключается в следующем. *

1. Определяется решение < £ к »^ > вспомогательной задачи а г

тСп. тО-Х I Г(х и) + ( I ,0.) х-Х +. —-\\-X-x »

хеХ ^ z j ^ (20)

значение целевого функционала которой в точке обозна-

чается tf* .

2. Отыскивается J.« по описанной процедуре из условия проверки для функции <•*:> - "S неравенства (6), в котором £ * Ч* * У^к") . ■

3. = 2 % лрк < 1 , + 1 = а^при а-о ■> 0 произвольно.

Пусть Х^ - множество точек , удовлетворяющих не-

обходимым условиям минимума функции f на множестве У , е У<-%) = ^^'у ^"ViO, У* - совокупность всех Теорема 13. При любом будет у^>

,РК = «и.-**-—11 ак в ** > ° . ■ - 1 ври К »

Если вторая производная 5 непрерывна в окрестнос-

ти единственной предельной точки 5 у <х.) > и удовлетворяет в ней аналогичному (10) условию, то а, } { ; при

а > £ справедлива оценка *

WPJI « ЧИк-Л , ч, - К < 1 •

к

Стабилизация значения А*"* позэоляет при проверке неравенства (6) производить на итерации лишь однократное вычисление функции ^ рк ) , связанное с трудоемким решением

внутренней задачи максимизации.

В приложениях: I к 2 приведены результаты численных экспериментов по ЖК1 первого порядка и их сравнение. Результаты вычислений показали (приложение I), что Л:,К13 с управляемым 5 -спуском в локальной и минимаксной формах менее эф'^ективен, чем метод линеаризации с единичной матрицей квадратичной подзадачи. Исключение составляют задачи (I), в которых точка х„ совпадает с вершиной допустимого множества О. .

Сопоставимым с методом линеаризации по числу вычислений функций и количеству итераций при заданной точности окончания расчетов (Ю~5 по аргументу х , Ю-9 - но и невязкам

ограничений задачи (I)) является нормализованный ЛЖШ с эффективным выбором ук (приложение 2). Преимущество одного из них перед другим проявилось на примерно одинаковом числе репейных задач. Различие в значениях установившихся Ы к - N , удовлетворяющих (7), несущественно влияло на быстроту сходимости ЛМКШ.

В приложении 3 сформулирована одна из задач оптимальной организации строительства линейной части магистральных трубопроводов, формализуемая как задача нелинейного программирования. Целевым функционалом в ней выступает себестоимость производства работ, ограничениями являются наличие трудовых и материальных ресурсов. Для ее решения разработан специальный комплекс программ оптимизации на основе методов штрафных функций, линеаризации, линейного программирования. Комплекс программ может использоваться на стадиях проектов производства работ и при оперативном управлении ходом строительства. В составе системы оптимального проектирования организации работ он применялся при сооружении участков магистральных трубопроводов /рентой - Помары - Ужгород, Ямбург - Тула I и ряда других.

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

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

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

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

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

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

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

6. Методы конечных штрафов перенесены на нелинейные задачи дискретного минимакса с сохранением всех своих свойств. Параметрический метод линеаризации распространен на условную задачу непрерывного минимакса.

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

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

1. Панин В.М. О методе второго порядка для задачи дискретного минимакса // Курн. вычисл. математики и мат. физики. -1979. - 19, ü I. - С. 88-98.

2. Панин В.М. Метод линеаризации для задачи дискретного минимакса // Кибернетика. - 1980. - Я 3. - С.86-90.

3. Панин З.М. Метод линеаризации для задачи непрерывного минимакса // 'Гам же. - 1981. - JS 2. - С.75-78.

4. Панин В.М. 0 некоторых методах решения задач выпуклого программирования // Курн. вычисл. математики и мат. физики. -

1981. - 21, Я 2. - С.315-328.

5. Панин В.М. Глобальная сходимость демпфированного метода Ньютона в задачах выпуклого программирования // Докл. АН СССР. Cep.i.-ат.- 1981. - 261. Р 4. - C.8II-8I4. '

6. Панин В.М. Расширение области сходимости некоторых методов математического программирования // Теория оптимальных решений. - Киев: Ин-т кибернетики им. В.М.Глушкова АН УССР,

1982. - С.9-15.

7. Панин В.М. Оценки сходимости двух методов линеаризации // Докл. АН УССР. Сер.А.- 1984.- .'"» 5.- С.77-79.

8. Панин В.М. Методы конечных штрафов с линейной аппроксимацией ограничений // Кибернетика.- 1984.- й 2.- Ч.1.- С.44-50.

9. Панин В.М. Методы конечных штрафов с линейной аппроксимацией ограничений // Там же,- Л 4.- Ч.2.- С.73-81.

10. Панин З.М. Об асимптотической эквивалентности двух методов конечных штрафов первого порядка // Там же.- 1986.- !Ь 5.-С.47-53.

11. Панин В.М." Линейный аналог метода градиентного спуска в условной оптимизации // Докл. АН СССР. Сер.мат.- I98G.- 291.

Js 4.- С.786-788.

12. Панин В.М. Оценка сходимости одного метода конечных штрафов // Докл. АН УССР. Сер.А.- 1986.- Л 2.- С.62-65.

13. Панин В.М. Линейный метод конечных штрафов с регулируемым вектором спуока // Кибернетика.- 1988.- JS I.- С.50-55.

14. Пшшн В.М. Линейный метод конечных штрафов с управляемым £-спуском // ::{урн. вычисл. математики и мат. физики.- 1988.28, а 3.~ С.316-324.

15. Панин В.М. Нормализованный мэтод конечных штрафов в задаче нелинейного программирования // Докл. АН СССР. Сер.мат.-1989. - 3&4. № 3. - С. 549-552.

16. Панин В.М., Пшеничный Б.Н. Параметрический метод линеаризации в задачах математического программирования // Нурн.вы-числ.математики и мат.физики. - 1983. - 23, I. - С. 61-72.

17. Пшеничный Б.Н., Панин В.М. Линейная сходимость методов линеаризации // Докл. АН УССР. Сер.А. - 1987. - Je 4. -

С. 16-18.

18. ВСН 187-85. Инструкция по автоматизированному расчету оптимальных проектов производства работ на строительство линейной части магистральных трубопроводов / Миннефтегазстрой СССР. - М.: ВНИИСТ, 1986. - 64 с. - Разраб.: З.Г.Чирсков, Л.М.Унигов-ский,..., В.М.Панин и др.

Пчдп. в П9Ч. 25.07.89. Е<? 16799,-формат "60x84/16. Бул.тип.$ 1.0фс.печ. Усл.печ.л. 1,51. Усл. 1ф.-отт. 1,63,

Уч.-изд.л. 1.06. Тираж 100 эта. Рак. 1311. Бесплатно_

Редэкцконно-издательский отдел с полиграфическим участю-ил Института кибернетики имени В.М.Глугоова АН УССР 252207 Киев 207, проспект Академика Глуикова, 20

Бесплатно