Теория и приложения методов последовательной безусловной минимизации тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА I. Теоретические положения метода штрафов

§ 1.1. О некоторых общих конструкциях метода штрафов

§ 1.2. Характеристические свойства функций штрафа

§ 1.3. Двухсторонние оценки в методе штрафов. Конкретные системы функций штрафа

ГЛАВА 2. 0 скорости сходимости метода штрафов

§ 2.1. Характеристика вспомогательных задач в методе штрафов.

§ 2.2. Обзор исследований.

§ 2.3. Прямой метод оценки быстроты сходимости

§ 2.4. Оценки скорости сходимости по аргументу

ГЛАВА 3. Гладкая аппроксимация точных функций штрафа

§ 3.1. Специальный класс функций штрафа. Теоремы о сходимости метода.

§ 3.2. Некоторые свойства минимизирующей последовательности. Оценки скорости сходимости

ГЛАВА 4. Итерационные процессы выпуклого программирования с внутренней регуляризацией.

§ 4.1. Устойчивые алгоритмы на основе метода штрафов

§ 4.2. Метод штрафов с внутренней регуляризацией

§ 4.3. Сходимость по аргументу в методе с внутренней регуляризшдией.

ГЛАВА 5. Применение методов выпуклого программирования для решения нелинейных краевых задач

§ 5.1. Обобщение схемы Ритца на случай вариационных неравенств.

§ 5.2. Метод штрафов в применении к вариационным неравенствам

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

Теоретические исследования в области выпуклой оптими -задии, начатые работами Л.В.Канторовича ("зо] 1940 года и Ф. Джона [122] 1948 года и интенсивно проложенные после опуб -ликования в 1951 г. статьи Г.Куна и А.Таккера [129] , стимулировали формирование нового направления в математике - выпуклого анализа, в котором собственно теория выпуклых экстремальных задач является одной из основных частей.

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

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

К первой группе отнесем те методы, при реализации ко -торых цриходится на каждом шаге решать задачу минимизации линейной или выпуклой функции при линейных ограничениях.Это, прежде всего, различные варианты методов возможных направлений (см.,например, [18,26,27,64,113] ) отсечения [33,50,128, 144] , проекций градиента [5,69,142] . Вторую группу соста -вят методы, с помощью которых искомое решение определяется как предел последовательности безусловных минимумов специальным образом сконструированных вспомогательных функций: методы штрафов, барьеров, центров, модифицированных функций Лагранжа.

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

В данной работе в основном рассматриваются методы второй группы, которые, придерживаясь терминологии А.Фиакко и Г. Мак-Кормика [88] , будем именовать методами последова -тельной безусловной минимизации. Исключение в этом плане составляет § 5.1.

Начало исследований в этом направлении принято датировать 1943 годом, когда Р.Курант [107] , исходя из физических соображений, указал на возможность приближенного решения конкретной вариационной задачи вида: ~ ггИ^! при ограничении , - функционалы в некотором гильбертовом пространстве) на основе определения стационарных точек функционала ttJZ(3C) при больших значениях ~t . Однако, по-видимому, следует обратить внимание на существенно более раннюю работу Р.Куранта [106] , относящуюся к 1922 году. Предложенная в ней модификация вариационного процесса Ритца есть не что иное, как использование метода штрафов для обеспечения более квалифицированной сходимости минимизирующей последовательности.

В качестве исходной в главах I - 4 (и приложении) рассматривается конечномерная задача выпуклого программирования 4cxsi-ryu.hr!

О-1)

OLG Gr, где ^ : ß Й - выпуклая функция, &■ выпуклое замкнутое множество.

В методе штрафов вспомогательные задачи состоят в безусловной минимизации выпуклых функций F^ = 4 + , К- -. , где как правило, почти везде на ¡Z^ удовлетворяют предельному соотношению п. V^ Сое) - S^ (ос.) (0.2)

К -X» £(х}=

О при X £ & ^ . ^СО при х ф

Ввиду очевидной эквивалентности задачи (0.1) задаче безус -ловной минимизации функции + С * ) естественно рас -считывать, что при больших значениях К точки эсеё"окажутся достаточно близкими к множеству решении задачи (0.1) (если оно непусто). В предположении, что о.з) П ^ р> 4. где ^ : К -> Ьс выпуклые функции, соотношение (0.2) выполнено, например, для часто используемой на практике системы функций тгде ^-/с > 0 > ^^ ~~ . Функции такого рода более всего соответствуют привычным представлениям о штрафе.

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

Основными достоинствами метода штрафов являются его универсальность (на практике метод не без успеха применяется

30 см. § 2.1 к задачам, далеко выходящим за рашш выпуклой оптимизации), простота вычислительной схемы, возможность использования широкого аре енажа методов безусловной шншзащ. Наиболее существенше недостатки - возрастающие е увеличением номера !<■ "овражность" поверхностей уровня функций ("V , труд ность вычисления градиента в процессе поиска точки

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

М.Хеетенеом [119] и М.Пауэллом [138] в 1969 г. была предложена модификация метода штрафов, в определенной степени свободная от указанных недостатков. Дальнейшие исследования в этом направлении привели к созданию новых интересных алгоритмов £ 2,15,17,55,70,99,145] .

В несколько вольной нетерпретащж методы этого класса удобно охарактеризовать следующим образом [П5] .

При использовании некоторых систем функций штрафа можно сконструировать итеращон

I*4 ный процесс ала 4 2* @Сос)+)л//~1)}(о.5)

ЭС&Р.*1

ДЛЯ К К > хЧ

0.6) с) " для К ^ ^ уД ^ м/4} , шбов , (0.7) с весьма простой процедурой (0.7) перевычисления параметров У- , который при подходящем выборе К приводит к решению задачи (ОД), (0.3).

Если, например, используются функции штрафа (0.4), то

Ц/) =г УУ1ЛЛС { о, ^сос) + ] ив принципе можно выбрать произвольно. Ясно, что при К- , ■ V/О ж {• ^ • ^ о)«О метод (0.5)-(0.7) превращается в обычный метод штрафов.

Алгоритмы такого рода возникли из различных соображений и имеют различные наименования (методы штрафов со сдвигами, штрафных оценок, модифицированных функций Лагранжа). В настоящее время вееьма перспективным для их развития представляется использование теории модифицированных функций Лагранжа [14,16,99,140] .

С точки зрения качества вспомогательных задач миними -зации номер предпочтительно брать, насколько это возможно, небольшим (в случае функций (0.4) положить , 1С- г — , при небольшом > О ). При этом легче осуществляется отыскание приближенных значений ОС1^ . Одна -ко, недостатком такого подхода является, как правило, весьма медленная сходимость внешнего (по 1с ) итерационного процесса. С увеличением К внешний цикл сокращается, но начинают проявляться недостатки обычного метода штрафов.

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

О ги

В предположении, что С? = : о, 3 -"Ф- Ф , начиная итерационный процесс из аР") . . ж 7 Более точно: жри выполнении естественных требований относительно задачи (0.1), (0.3) последовательность {зс] сходится к множеству ее решений. произвольной точки О- , на Ю-том шаге определяем центральную в некотором смысле точку ОС,*' множества

Исходные варианты этого метода различаются, главным образом, выбором функции Ч^ • & К , определяющей центр:

В качестве таковой может быть взята, например, выпуклая функция л зГ при пиш, £¿¿.0

9¿а * (0в9) ч в противном случае. Сопоставляя метод (0.8), (0.9) и метод штрафов с функцией

Ж- А О Р< % С ) (0.10)

I 400 в противном случае (^>0 ; - ) , легко убедиться в схожести вспомогательных задач, а, если в (0.10) положить = - где {СС^З определена согласно (0.8) ,

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

Более глубокий анализ показывает, что при определенном различии в возможностях управления процессом методы штрафов, центров и внешних центров ^ [ 17,49,113] обладают аналошч -ными достоинствами и недостатками. в другой терминологии - метод нагруженного функционала

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

1. Исследование характеристических свойств функций штрафа. В монографии [881 содержащей основательный обзор и анализ результатов, связанных с развитием метода штрафов примерно до 1967 года, дано аксиоматическое описание класса функций штрафа. Однако, в связи с попыткой охватить невыпуклые задачи, эта аксиоматика оказалась неудобной для задач выпуклого программирования. Кроме того, как теперь выясни -лось, она является неоправданно жесткой и, вместе с тем,-недостаточно полной для того, чтобы на ее основе можно было получить общие теоремы о качестве приближенного решения (двухсторонние апостериорные оценки).

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

2. Оценка скорости сходимости метода штрафов. В пред -положении, что процедура определения длины шага рассматривается как элементарная операция, метод штрафов является двухуровневым итерационным процессом. Оценка его трудоемкости невозможна без установления скорости сходимости последова -тельности приближенных решений вспомогательных задач к точ -ному решению исходной задачи. Можно указать на ряд работ [22,77-79,100,135] , где оценки скорости сходимости получены для отдельных систем функций штрафа. В главе 2 данной работы исследование в указанном направлении осуществляется единообразно для широкого класса функций штрафа и на двух уровнях: в достаточно общих предположениях относительно ис -ходной задачи и при некоторых дополнительных условиях, когда можно рассчитывать на получение наиболее сильных по порядку оценок.

3. Построение функций штрафа с хорошими дифференциальными и аппроксимативными свойствами. Как показывает вычислительная практика, эффективность применения метода штрафов в значительной степени зависит от того, насколько удачно выбрана система функций штрафа. Основными требованиями при этом являются: обеспечение гладкости, достаточной для применения эе) подходящих ' методов безусловной минимизации; улучшение устойчивости вычислительного процесса; возможность более сво -бодной вариации параметров функции штрафа. Эти требования в какой-то степени противоречивы и нуждаются в разумном согласовании. В различных аспектах эта проблема затронута в гла -вах I, 5 и (более основательно) в главе 3.

4. Улучшение качества вспомогательных задач. Как уже отмечалось, "овражность" поверхностей уровня функций является причиной серьезных трудностей на пути минимизации Добавлением к Р/с сильно выпуклой функции можно улучшить обусловленность вспомогательной задачи. При этом повышается возможность использования эффективных алгоритмов бе -зусловной минимизации, более надежных критериев процесса во внутреннем цикле. Метод последовательной безусловной минимизации, в котором на 1С -том шаге определяется точка

ОЯ-Д ууи./1- ]А [ос) ч-Цос-ос^'1/!1} (о.п) о 0Сбг£п чп Выбор метода, естественно, зависит от гладкости функций

4- и Г ■ предложен и исследован (для аксиоматически описанного класса функций штрафа \/к ) в §§ I и 2 главы 4.

5. Построение алгоритмов, обладающих регуляризирующи-ми свойствами. Задачи выпуклого программирования, вообще, говоря, не являются корректными [47,84] . Поэтому значительный интерес цредставляет вопрос о построении алгоритмов, устойчивых к малым искажениям информации и вырабатывающих сходящуюся по аргументу минимизирующую последовательность. При этом важно, чтобы осуществление регуляризации не увеличива -ло глубины итерационного процесса. Такие алгоритмы в последние годы построены на основе комбинирования некоторых мето -дов выпуклого программирования (проекций градиента [3-5] , штрафов [7-9,85] , модифицированных функций Лагранжа [1,2, 141] с методами регуляризации А.Н.Тихонова или Б.Мартине

132,133] . В данной работе установлены условия, при кото -рых указанными качествами обладает итерационный процесс (О.П).

6. Применение метода штрафов для решения бесконечно -мерных задач. Эта проблема, актуальность которой в последнее время существенно возросла в связи с интенсивным исследова -нием вариационных неравенств, является многоплановой. В мо -нографии [ 12 ] , фиксирующей опыт численного решения вариационных неравенств, и ряде последующих работ метод штрафов рассмотрен в традиционном аспекте: решение фиксированной дискре-тизованной задачи получается в результате последовательной минимизации вспомогательных функций. Такой подход, по-види -мому, не вполне удачен. Ввиду весьма специальной структуры получаемой конечномерной задачи целесообразно попытаться та -ким образом согласовать параметры штрафа и дискретизации, чтобы, с одной стороны, при добавлении штрафа не ухудшалась обусловленность ^ минимизируемой функции; с другой стороны, в результате решения (одной) вспомогательной задачи обеспечивалась бы точность решения дискретизованной задачи того же порядка, что и погрешность конечномерной аппроксимации (идея В.Я.Ривкинда [71] ). Еще более перспективным представляется осуществление итеративного процесса с согласованным изменением параметров штрафа и дискретизации.

Исследованию указанных вопросов на примере конкретной вариационной задачи посвящен § 2 главы 5.

Перейдем к изложению содержания диссертации.

1. Антипин A.C. О методе выпуклого программирования, использующем симметрическую модификацию функции Лагранжа. -Экон.и матем.методы, 1976, т. 12, $ 6, с. 1.64-II73.

2. Антипин A.C. Методы нелинейного программирования, основанные на прямой и двойственной модификации функции Лагранжа. ivi: 1979. - 74 с. (препринт ВНИИ системных исследований)

3. Бакушинский А.Б. Методы решения монотонных вариационных неравенств, основанные на принципе итеративной регуляризации. Журн. вычисл.матем. иматем.физ., 1977, т. 17, № 6, с. I35Ü-I362.

4. Бакушинский А.Б. К принципу итеративной регуляризации. -Журн. вычисл. матем. иматем.физ., 1979, т. 19, №4,с. IÜ40-IU43.

5. Бакушинский А.Б., Поляк Б.Т. О решении вариационных неравенств. -Докл. АН СССР, 1974, т. 219, Ji> 5, C.I038-IU4I.

6. Валле-Пуссен Ш.Ж. Курс анализа бесконечно малых, т. II, Ы.-Л.: ГТТИ, 1933. - 463 с.

7. Васильев Ф.П. О регуляризации некорректных экстремальных задач. Докл. АН СССР, 1978, т. 241, № 5, с.IUÜI-IÜÜ4.

8. Васильев Ф.П. О регуляризации некорректных задач минимизации на множествах, заданных приближенно. Жури, вычисл. матем. и матем.физ., 1980, т. 20, I, с. 38-50.

9. Венец В.И., Рыбашов М.В. Непрерывные алгоритмы выпуклого программирования с использованием штрафных функций.-Автоматика и телемеханика, 1975, № II, с. ICJ-I5.

10. Гловински Р., Лионе Ж.-Л., Тремольер Р. Численное исследование вариационных неравенств/перев. с франц. М: Мир, 1979. - 574 с.

11. Гольштейн Е.Г. Теория двойственности в математическом программировании и ее приложения. М.: Наука, 197I. -351 с.

12. Гольштейн Е.Г., Третьяков Н.В. Модифицированные функции Лагранжа. Экон. и матем.методы, 1974, т. 10, 3,с. 568-591.

13. Гольштейн Е.Г., Третьяков Н.В. Градиентный метод минимизации и алгоритмы выпуклого программирования, связанные с модифицированными функциями Лагранжа. Экон. и матем. методы, 1975, т. II, Jí> 4, с. 730-742.

14. Гольштейн Е.Г., Третьяков Н.В. 0 модифицированных функциях Лагранжа задачи выпуклого программирования. Экон. и матем. методы, 1980, т. 16, №4, с. 772-777.

15. Гроссман К., Каплан А.А. Нелинейное программирование на основе безусловной минимизации. Новосибирск: Наука, 1981. - 181 с. (Немецкое издание:olzJL hJ-eM:¿lhJtCLfLLH- Of^blh^fLfUJ-^.-Leipzig : Teulpuisb 3 í£7-9. -2oo&,).

16. Демьянов В.Ф., Малоземов В.Н. Введение в шшимакс. М.: Наука, 1972. - 368 с.

17. Деннис Дж. Математическое программирование и электрические цепи / перев. с англ. М.: Ш1, 1961,- 215 с.

18. Дюво Г., лионс К.-Л. Неравенства в механике и физике / перев. с франц. М.: Наука, 1980. - 383 с.

19. Евтушенко 10.Г. Численные методы решения задач нелинейного программирования. Журн. вычисл.матем. и матем. физ., 1976, т. 16, В 2, с. 308-324.

20. Еремин И.И. Метод штрафов в выпуклом программировании. -Док/1. АН СССР, 1967, т. 173, №4, с. 748-751.

21. Еремин И.И. 0 методе штрафов в выпуклом программировании.- В сб.: Математические методы в некоторых задачах оптимального планирования (ред. И.И.Еремин). Свердловск,1967, с. 43-51.

22. Еремин И.И., Астафьев H.H. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1976. - 191 с.

23. Ермольев ü.M. Методы стохастического программирования.-М.: Наука, 1976. 239 с.

24. Зангвилл У.И. Нелинейное программирование. -М.: Сов. радио, 1973. 312 с.

25. Зойтендейк Г. Методы возможных направлений / перев. с англ. М.: ИЛ, 1963. - 176 с.

26. Иоффе А.Д., Тихомиров В.М. Теория экстремальных задач. -М.: Наука, 1974. 479 с.

27. Исследования по линейному и нелинейному программированию (ред. ЗрроуК., Гурвиц Л., Удзава X.) / перев. с англ.- М.: ИЛ, 1962. 334 с.

28. Канторович Л.В. Об одном эффективном методе решения некоторых классов экстремальных проблем. Докл. АН СССР,1940, т.28, В 3, с. 212-215.

29. Канторович JI.B., Акилов Г.П. Функциональный анализ. -2-е изд. М.: Наука, 1977, 741 с.

30. Канторович Л.В., Крылов В.И. Приближенные методы высшего анализа. M.-Ji.: Физматгиз, 1962. - 708 с.

31. Каплан A.A. К вопросу о реализации метода отсечения для решения задач выпуклого программирования. Оптимальное планирование, 1969, вып. 14, с. 43-48.

32. Каплан A.A. Характеристические свойства функций штрафа.-Докл. АН СССР, 1973, т. 210, Ш 5, с. I0I8-IG2I.34а.Каплан A.A. К характеристике штрафных функций. Оптимизация, 1972, й 8, с. 13-21.

33. Каплан A.A. Метод штрафов и некоторые приложения математического программирования. Материалы международной конференции ИФШ1 по оптимизации (ТК-7). Новосибирск, 1974, с. 7-14 (Препринт 2).

34. Каплан A.A. Замечание к теореме Стоуна-Вейерштрасса. -Сиб.матем.журн., 1975, т.16, $5, с. III3-III5.

35. Каплан A.A. О скорости сходимости метода штрафов. докл. АН СССР, 1976, т. 229, J& 2, с. 288-291.

36. Каплан A.A. К анализу некоторых оценок скорости сходимости метода штрафов. Оптимизация, 1978, вып. 21(38),с. I2I-I26.

37. Каплан A.A. Об одном подходе к решению задач выпуклого программирования. Докл. АН СССР, 1981, т.258, J& 4, с. 785-788.

38. Каплан A.A. Оценки по аргументу скорости сходимости метода штрафов. -Оптимизация, 1982, вып. 29(46), с.22-31.

39. Каплан A.A., Рубинштейн Г.Ш. К теореме Куна-Таккера.Докл. АН СССР, 1969, т. 188, №5, с. 993-996.45а.Каштан A.A., Рубинштейн Г.Ш. Об одном обобщении теоремы Куна-Таккера. Оптимальное планирование, 1969, 14, с. 49-60.

40. Каплан A.A. Алгоритмы выпуклого программирования, использующие сглаживание точных функций штрафа. Сиб. матем. журн., 1982, т.23, М, с.53-64.

41. Карманов В.Г. Математическое программирование. 2-е изд. - М.: Физматгиз, 1980. - 256 с.

42. Ладыженская O.A., Уральцева H.H. Линейные и квазилинейные уравнения эллиптического типа. 2-е изд. - Ы.: Наука, 1973. - 576 с.

43. Лебедев Ю.В. О сходимости метода нагруженного функционала в задачах выпуклого программирования Журн. вычисл. матем. и матем. физ., 1977, т. 17, В 3, с. 765-768.

44. Левитин E.G., Поляк Б.Т. Методы минимизации при наличии ограничений. Журн. вычисл. матем. и матем.физики, 1966, т. 6, №5, с. 787-823.

45. Лионе Ж.-Л. Оптимальное управление системами, описываемыми уравнениями с частными производными / перев. с франц. М.: Мир, 1972. - 414 с.

46. Лионе Ж.-Л. Некоторые методы решения нелинейных краевых задач / перев. с франц. М.: Мир, 1972. - 587 с.

47. Лионе Ж.-Л., Мадженес 3. Неоднородные граничные задачи