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

ВВЕДЕНИЕ.

ШВА I. ПОСТАНОВКА ЗАДАЧ И ОСНОВНЫЕ ОПРЕДЕЛЕНИЙ

§1.1. Квадратичные задачи и а там этического программирования

§ 1.2. Постановка вопроса устойчивости в задачах математического программирования

§ 1.3. Одно обобщение некоторых экстремальных задач

ГЛАВА 2. ИССЛЕДОВАНИЕ УСТОЙЧИВОСТИ В ЗАДАЧАХ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ.

§ 2.1. Устойчивость в конечномерных задачах математического программирования

§ 2.2. Устойчивость в бесконечномерных задачах с ограничениями типа неравенств и равенств

§ 2.3. Устойчивость в задачах с ограничением, заданным с помощью непрерывного оператора

ГЛАВА 3. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ РАССМАТРИВАЕМЫХ ЗАДАЧ.

§ 3.1. Нахождение глобального минимума невыпуклых функций посредством выпуклых огибающих.

§ 3.2. Метод нахождения локальных минимумов квадратичных задач математического программирования

§ 3.3. Расстояние по направлению между двумя множествами и алгоритмы его нахождения

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

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

Из перечисленных выше разделов математического программирования лучше других развито линейное программирование. В этой области достигнуты большие успехи, разработаны такие универсальные алгоритмы, как симплекс-метод Дк.Данцига £l6j . Разработанные в этом разделе методы позволяют решать широкий круг практических задач, сводящихся к задачам линейного программирования. Методам линейного (а также нелинейного) программирования посвящены превосходные монографии [II ] ,[1б] ,[33] , в которых изложена не только теория, во и применения этих методов в теории игр и экономике.

Одним из наиболее развитых разделов является также выпуклое программирование. В задачах этой области особо важную роль играет теория двойственности, основанная либо на понятии сопряженных функций, либо на функции Лагранжа. В последние годы классическое понятие сопряженной функции было обобщено на более широкий класс функций, а вместо функции Лагранжа во многих работах рассматриваются различные модифицированные функции Лагранжа. Фундаментальные результаты выпуклого программирования полу-ч ены в работах Р.Рокафеллара Б.Н.Пшеничного С« J, в.г.

Голывтайна [ 14 ], К.Дж.Эрроу, Л.Гурвивд и Х.Удзавы I также других авторов.

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

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

Г27 ] А.fi.Дубовицким и А.А.Милютиным [18 J была предложена схема, использующая аппарат функционального анализа, с помощью которой можно получить необходимые условия экстремума для разных типов экстремальных задач. В этой же работе получены весьма общие результаты, касающиеся существования и единственности решения.

Методам решения нелинейных оптимизационных задач, несмотря на сравнительно небольшую историю развития этого раздела вычислительной математики, посвящена обширная литература, не говоря уже о работах, имеющих прикладной характер. Самыми распространенными из методов спуске, применяемых в этих задачах, являются методы градиентного типа. В этих методах значение целевой функции на каждом шаге итерации монотонно уменьшается (имеется ввиду задача минимизации). Методам такого типа посвящены работы Е.С.Левитина и Б.Т.Поляка [39] , Ю.И.Любича и Г.Д.Майстровского [ 41 J » в которой в весьма общей постановке рассмотрена теория релаксационных процессов, Б.Н.Пшеничного и Ю.М.Данилина [47 ] , В.З.Беленького и В.А.Волконского [ 2J, а также многих других авторов.

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

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

В многоэкстремальных задачах по сравнению с другими задачами также трудно получить соотношение двойственности для достаточно широкого класса задач. По этому направлению следует отметить работу Р.Рокафеллара L79 ] , а также Дж.Фалька С 68 J . Следует тут же отметить, что для многоэкстремальных задач вместо соотношения двойственности чаще всего удается получить оценки для оптимального значения.

Весьма важной при решении многоэкстремальных задач является проблема нахождения алгоритмов поиска экстремума, оптимальных для определенных классов задач. В этом направлении фундаментальные результаты получены в работах В.В.Иванова С 29 J и А.Г.Сухарева [ 50 ].

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

В задачах нахождения условного экстремума применяются также информационно-статистические методы. Такой подход дан в работах Й.Б.Моцкуса Оз], Р.Г.Стронгина Ы], А.Ф.Торонджадзе и Д.А. Георгобиани [54] , В.КЛичинадзе , а также других авторов.

Многие различные подходы к многоэкстремальным задачам приведены в обзорной статье А.Г.Сухарева

Ы1

Довольно обширным классои многоэкстремальных задач являются задачи сепарабельного программирования. Многие задачи путем введения новых переменных можно привести (см.[5б] ) к таким задачам. При решении задач сепарэбельного программирования часто применяются методы типа ветвей и границ, применяемые в целочисленном программировании. К ним относятся методы, разработанные в работах Д&.Фалька и Р.Соланда [69], Р.Соланда [во], к этим работам примыкает также работа С.А.Канцедала и Ю.Б.Максимова [32]. В работах [©], [ 80J на основе введения понятия выпуклой огибающей исходная сепарабельная задача сведена к последовательности задач выпуклого программирования.

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

Квадратичные многоэкстремальные задачи рассматривались также в работах Р.Беллмана [3 ], П.Р.Гамбурда! ю] , Г.В.Шилове [57 ], а также других авторов. В диссертационной работе, наряду с другими рассмотрены задачи такого типа и дан алгоритм нахождения локальных минимумов, в котором используются методы недифференцируемой оптимизации, развитые в работах Н.З.Шора [5б]-[б0], а также Ю.Н.ВрмольеваС & 1, В.Ф.Демьянова и Л.В. Васильева [ 17]. Здесь же дан метод получения нижней оценки для оптимального значения квадратической задачи с ограничениями типа неравенств и равенств. При этом применяются методы, разработанные в работе А.Фиэкко и Г.Мак-Кормик [55].

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

Пусть на векторном метрическом пространстве задан непрерывный функционал f(X) и ищется элемент для которого хеХ

Одно из самых ранних определений устойчивости в задачах такого типа было дано в рэботе А.Н.Тихонова [52]: предположим, что существует единственное решение ОС этой задачи и пусть

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

X* с ft к элементу X .

Задача минимизации J(Cc) на множестве )(. называется (по теорминологии той же работы) корректно поставленной, если она резрешима и устойчива. В противном случав она называется некорректно поставленной.

Минимизирующая последовательность $функционала j(x) называется [52 ] регуляризованной, если существует компактное множество |VX * содержащее . Очевидно, что если рассматриваемая задача имеет единственное решение, то регуляризованная минимизирующая последовательность сходится к этому решению. Кроме того, если -f(oc) ограничен снизу на )( , то на любой предельной точке регуляризованной последовательности функционал достигает своей нижней грани. Поэтому достаточно указать алгоритм построения регуляризованных минимизирующих последовательностей. Пути построения таких алгоритмов даны в [в], [52], [53] , а также в работах других авторов.

Однако, оказалось, что можно ввести более общее определение устойчивости и корректности задачи минимизации функционала (как безусловной, так и условной) и получить сходимость минимизирующих последовательностей, что и было сделано в работах В.С.Левитина [38] , В.С.Левитина и Б.Т.Поляка [40] и др.

Важное значение в развитии теории устойчивости конечномерных задач математического программирования имелв работа Дж.Еван-С8 и Ф.Гоулда [67] , а также примыкающая к ней работа М.Гринберга и В.Пьерскаллы [7l] . Дальнейшее развитие теория устойчивости получила в работах В.И.Бердышева [V] ,[5] , Б.М.Будака и Берко-вича [б], В.Г.Карманова [34] , А.Фиакко и Г.Мак-Кормика [55], Дж.А^бина [62] , Р.Люккетти [73] , С.Робинсона [7б], [??], С.Робинсона и Р.Дея [78] ; для выпуклых задач - в работах Б.Г .Голь-штейна [14] , Й.И.Брёмина и Н.Н.Астафьева [20] , Р.Люккетти и Ф.Патроне [74] и других авторов. Вопросу дифференцируемости оптимального значения по параметру посвящены работы [15] , [37], [72], и др.

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

Диссертационная работа состоит из введения, трех глав, выводов и приложения.

выводы

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

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

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

§ 1.3. Поставлена задача нахождения расстояния по направлению между двумя множествами конечномерного евклидова пространства и показано, что эта задача является обобщением некоторых экстремальных зэд8ч.

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

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

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

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

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

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

1. Андерсон Т. Статистический анализ временных рядов. -М.:Мир, 1976,757с.

2. Беленький В.З., Волконский В.А. и др. Итеративные методы в теории игр и программировании, М.:Наука, 1974, 240с.

3. Беллман Р. Введение в теорию матриц. М.:Наука, 1969,367с.

4. Бердышев В.И. Непрерывная зависимость элемента, реализующего минимум выпуклого функционала, от множества допустимых элементов. Мэтем.заме тки, 1976, т.19, № 4, с.301-512.

5. Бердышев В.И. Устойчивость задачи минимизации при возмущении множества допустимых элементов. Матем.сборник, 1977,т.103, Ш 4, с.467-479.

6. Будак Б.М., Беркович S.M. Об аппроксимации экстремальных задач, 1,П. ЖВМ и МФ, 1971, т.II, № 3, с.580-596; № 4,с.870-884.

7. Булатов В.П. Методы погружения в задачах оптимизации. -Новосибирск: Наука, 1977,158с.

8. Васильев Ф.П. Лекции по методвм решения экстремальных задач.-М.: Изд-во Московок.ун-та, 1974,374с.

9. Васильев Ф.П. Методы решения экстремальных задач.- М.: Наука, 1981,400с.

10. Гамбурд П.Р. Нахождение стационарных точек квадратичной функции на сфере. Прикладная математика и программирование. Кишинев: 1971, вып.6, с.100-107.

11. Гейл Д. Теория линейных экономических моделей,-М.":ИЛ,1963.,42СЬ

12. Гилл Ф., Мюррей У. Численные методы условной оптимизации .-М.:Мир, 1977,290с.

13. Гирсанов И.В. Дифференцируемость решений задач математического программирования. Тезисы докладов Всесоюзной конференции по применению методов функционального анализа к решению нелинейных задач. Баку:йзд-во АН АзССР, 1965,с.51-52.

14. Гольштейн Е.Г. Теория двойственности в математическом программировании и ее приложения. М.:Наука, 1971, 352 с.

15. Дэнилин Ю.М. Методы минимизации,основанные на аппроксимации исходного функционала выпуклым. ЖВМ и МФ, 1970, т.10, № 5, с.1067-1080.

16. Данциг Д. Линейное программирование, его обобщения и применения. М.:Прогресс, 1966, 600 с.

17. Демьянов В.Ф.,Васильев Л.В. Недифференцируемая оптимизация. -М.:Наука, 1981, 384 с.

18. Дубовицкий А.Я., Милютин А.А. Задачи на экстремум при наличии ограничений. ЖВМ и МФ, 1965, т.5, 1 3, с.395-453.

19. Ермольев Ю.М. Методы решения нелинейных экстремальных задач.-Кибернетика, 1966, N° 4, с.1-17.

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

21. Жужунашвили А.Ш.К вопросу устойчивости в задачах математического программирования .-Сообщения АН ГССР,1984,т.ПЗ,№2, с.269-272.

22. Жужунашвили A.ill. К нахождению глобального минимуме посредством выпуклых огибающих. Математическая и техническая кибернетика. Тбилиси: Мецниереба, 1982, с.26-31.

23. Жужунэшвили А.Ш. О применении ^-алгоритмов для задач математического программирования с квадратичными функциями.-Математическая и техническая кибернетика. Тбилиси:Мецниереба, 1984, с.24-30.

24. Жужунашвили А.Ш. О некоторых достаточных условиях устойчивости в экстремальных задачах. Тезисы докладов конференции молодыхматематиков.Тбилиси: Мецниереба, 1981, с.152.

25. Жужунашвили АЛ. Об устойчивости в задачах математического программирования. Математическая и техническая кибернетика.Тбилиси:Мецниереба, 1983, с.17-22.

26. Жужунашвили А.Ш. О расстоянии по направлению между двумя множествами. Математическая и техническая кибернетика (в печати).

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

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

29. Иванов В.В. Об оптимальных алгоритмах минимизации функций некоторых классов. Кибернетика,1972, № 4, с.81-94.

30. Иосида К. Функциональный анализ. М.:Мир, 1967, 624 с.

31. Канторович Л.В.,Акилов Г.П. Функциональный анализ в нормированных пространствах. М.:Физматгиз, 1959, 684 с.

32. Канцедал С.А., Максимов Ю.Б. О минимизации невыпуклых функций одного класса. Кибернетика, 1974, № 4, с.67-71.

33. Карлин С. Математические методы в теории игр, программирования и экономике. М.:Мир, 1964, 840 с.

34. Карманов В.Г. Математическое программирование. М.:Наука, 1980, 256 с.

35. Колмогоров А.ИФомин С.В. Элементы теории функций и функционального анализа. М.:Наука,1972, 496 с.

36. Куратовский К. Топология, том.1. М.:Мир,1966, 595 с.

37. Левитин B.C. О дифференцируемости по параметру оптимального значения параметрических задач математического программирования. Кибернетика,1976; te I, с.44-59.

38. Левитин Е.С. О корректности ограничений и устойчивости в экстремальных задачах, 1,П. Вестник Московск.ун-та,матем., механ.,1968, №1, с.24-34, № 2, 0.8-22.39