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

• Черняев, Юрий Анатольевич
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Черняев, Юрий Анатольевич

Введение

Глава 1. Метод условного градиента для случая предвыпуклых ограничений с непустым множеством внутренних точек

1.1. Постановка задачи и алгоритм метода.

1.2. Необходимые условия экстремума.

1.3. Обоснование алгоритма при первом способе выбора шага

1.4. Обоснование алгоритма при втором способе выбора шага

1.5. Результаты вычислений.

Выводы по главе 1.

Глава 2. Метод проекции градиента для случая предвыпуклых ограничений с непустым множеством внутренних точек

2.1. Постановка задачи и алгоритм метода.

2.2. Обоснование алгоритма при первом способе выбора параметров

2.3. Обоснование алгоритма при втором способе выбора параметров

2.4. Обоснование алгоритма при третьем способе выбора параметров

2.5. Результаты вычислений.

Выводы по главе 2.

Глава 3. Метод проекции градиента для случая ограничений в виде выпуклой гладкой поверхности.

3.1. Постановка задачи и алгоритм метода. 3.2. Обоснование алгоритма при первом способе выбора шага

3.3. Обоснование алгоритма при втором способе выбора шага

3.4. Результаты вычислений.

Выводы по главе 3.

Глава 4. Эвристические алгоритмы метода проекции субградиента для предвыпуклых множеств ограничений.

4.1. Постановка задачи и алгоритм для ограничений первого типа

4.2. Постановка задачи и алгоритм для ограничений второго типа

4.3. Результаты вычислений.

- Выводы по главе 4.

Введение диссертации (часть автореферата) на тему «Численные методы решения экстремальных задач с предвыпуклыми ограничениями»

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

Как и всякие прикладные задачи, экстремальные задачи обычно возникают в описательной, а не в аналитической форме. Поэтому для того, чтобы применить к задаче математический аппарат, её нужно формализовать - построить математическую модель, что, как правило, требует знания не только математики, но и той области техники или экономики, в которой задача возникла. Таким образом, объектом изучения в теории экстремальных задач является математически поставленная экстремальная проблема. В связи с каждой такой проблемой возникают следующие вопросы. Существует ли решение? Если решение существует, то каким условиям оно должно удовлетворять? Как найти решение? Поставленные вопросы соответствуют разделам теории экстремальных задач, в которых изучаются вопросы существования решений, необходимые и достаточные условия экстремума и вычислительные методы.

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

Среди задач минимизации функций многих переменных наиболее изучены задачи линейного программирования. В таких задачах оптимизируемая функция является линейной, а область, на которой ищется экстремум, задана линейными равенствами и неравенствами. Задачи этого класса впервые исследовались JL В. Канторовичем, одной из первых работ которого по данной тематике является статья [32]. Для решения задач линейного программирования разработаны конечношаговые методы, одним из которых является известный симплекс-метод, или метод последовательного улучшения плана, разработанный Дж. Данцигом. Многие задачи этого класса (например, транспортные задачи) имеют определённые особенности, что привело к разработке специфических методов для таких задач. Кроме конечношаговых алгоритмов, для задач линейного программирования успешно разрабатываются итерационные методы, которые в ряде случаев оказываются более эффективными. Отметим, что задачи линейного программирования приходится решать как вспомогательные при реализации некоторых методов нелинейного программирования. Теории линейного программирования и методам решения задач соответствующего класса посвящена обширная литература, в частности, работы [7, 15, 68], отдельные главы работ [11, 21, 33, 52, 55] и многочисленные статьи.

Многие практические задачи, связанные с нахождением экстремума, сводятся к задачам нелинейного программирования. В таких задачах оптимизируемая функция и ограничения, задающие допустимую область, вообще говоря, не являются линейными. Большое разнообразие задач нелинейного программирования не позволяет разработать метод, пригодный для решения любой задачи. Важнейшим классом таких задач является класс задач выпуклого программирования (оптимизируемая функция и допустимое множество выпуклы). Задачи выпуклого программирования обычно приходится решать итерационными методами, позволяющими получать приближённые решения. Эти задачи, в силу своей специфики, позволяют доказывать сходимость численных методов в смысле необходимых и достаточных условий экстремума. Существуют также методы, для которых теоретически не доказана сходимость, но они тоже эффективно используются на практике. Многие методы выпуклого программирования могут быть применены и для решения некоторых невыпуклых задач. Например, в случае гладких целевых функций и выпуклых ограничений доказывается сходимость некоторых методов в смысле необходимых условий экстремума. Для отдельных классов невыпуклых задач с липшицевы-ми целевыми функциями разработаны специфические методы, позволяющие искать глобальной экстремум многоэкстремальных функций. Количество работ, посвященных различным методам нелинейного программирования, чрезвычайно велико, поэтому отметим лишь основополагающие работы Ф. П. Васильева [11], В. Г. Карманова [33], В. Ф. Демьянова и JI. В. Васильева [17], Б. Н. Пшеничного и Ю. М. Данилина [52], И. В. Романовского [55], В. В. Фёдорова [58], М. Аоки [6], У. И. Зангвилла [31], Ф. Кларка [36] и Д. Химмельблау [59]. Из многочисленных статей, опубликованных в последние годы, отметим [3, 4, 5, 12, 16, 39, 46, 47, 70].

Среди задач нелинейного программирования выделяются задачи, в которых допустимой областью является всё пространство - задачи безусловной оптимизации. Для таких задач существуют свои итерационные методы решения, например, градиентные методы, использующие аппарат частных производных первого порядка. Иногда экстремум выпуклой функции может быть найден и без привлечения итерационных процедур. Если же функция не является дифференцируемой, вычисление градиента затруднительно или трудно решить уравнение, из которого определяются точки экстремума, то целесообразно применять методы, не использующие аппарат производных, например, метод деформируемого многогранника, методы покоординатного спуска или методы случайного поиска. Если же функция имеет частные производные первого и второго порядка, которые вычисляются без труда, то можно использовать более точные методы поиска, например, метод Ньютона. Что касается задач оптимизации выпуклых негладких функций с ограничениями или без ограничений, то для их решения могут быть применены методы, использующие те или иные обобщения понятия градиента. Ряд таких методов рассматривается, например, в работах В. Ф. Демьянова, Ф. Кларка, А. М. Гупала, Н. 3. Шора и др. К числу работ указанных авторов относятся, например, [16, 17, 36, 43, 67]. Интерес представляют также специфические методы оптимизации овражных функций, поскольку обычные методы в этом случае оказываются, как правило, неэффективными. Ряд таких методов рассмотрен в [41].

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

Одним из распространённых методов условной оптимизации является метод возможных направлений, развитый Г. Зойтендейком, и рассматриваемый, например, в [11, 26, 28, 33, 52]. Этот метод требует на каждой итерации решения вспомогательной задачи линейного или квадратичного программирования. Несмотря на достаточно большой объём вычислений на каждой итерации, метод универсален: он применим для любой выпуклой гладкой задачи, если допустимое множество задаётся с помощью функциональных ограничений типа неравенств. Метод может использоваться также в случаях, когда кроме ограничений типа неравенств имеются линейные ограничения типа равенств. Применение различных дополнительных приёмов позволяет добиться достаточно быстрой сходимости метода возможных направлений.

Своеобразным является метод штрафных функций, идея которого состоит в сведении задачи условной минимизации к последовательности задач безусловной минимизации. Метод может быть применён к задачам с функциональными ограничениями типа равенств и неравенств. Несмотря на простую схему вычислений, при практическом использовании метода могут возникать различные трудности. В частности, эффективность метода для каждой конкретной задачи существенно зависит от удачного выбора вспомогательных функций. Кроме того, для успешного решения задач безусловной оптимизации часто приходится использовать трудоёмкие методы. На практике методом штрафных функций обычно пользуются лишь для получения грубого приближения к решению. Различные варианты метода штрафных функций и их вычислительные аспекты рассмотрены, например, в работах [3, 11, 16, 21, 33, 52, 59].

Алгоритмы метода проекции градиента и метода условного градиента, различные варианты которых рассмотрены, например, в монографиях [11] и [33] и в статьях [4, 12, 46, 47, 50, 70], отличаются простотой, но не отличаются универсальностью. Для использования метода проекции градиента нужно на каждой итерации решать задачу проектирования на допустимое множество, а для использования метода условного градиента -задачу минимизации некоторой линейной функции на этом множестве. Эти вспомогательные задачи, разумеется, далеко не всегда легко решаются, что и ограничивает область применения этих методов.

Отметим, что исследованию сходимости различных методов математического программирования предшествует изучение тех или иных вопросов выпуклого анализа, теории экстремальных задач и общих вопросов сходимости классов методов. Сюда, в первую очередь, относятся вопросы, связанные с различными свойствами оптимизируемых функций и допустимых множеств, необходимыми и достаточными условиями экстремума, существованием решений, а также с нахождением произвольной точки допустимого множества. Рассмотрению таких вопросов посвящена обширная литература, в частности, статьи [2, 19, 27, 29, 34, 35, 39, 40, 51, 53, 56, 57] и отдельные главы работ [11, 14, 17, 18, 21, 30, 33, 42, 49, 50, 54]. Одной из интереснейших является проблема обобщения результатов, полученных применительно к экстремальным задачам в конечномерном евклидовом пространстве, на случай бесконечномерных функциональных пространств. Начало этим исследованиям положено в работах А. Я. Дубовицкого и А. А. Милютина, Б. Н. Пшеничного, И. В. Гирсанова, А. Д. Иоффе и В. М.

Тихомирова и др. Такие обобщения позволили, в частности, построить общую теорию экстремума на основе первой вариации, позволяющую получать необходимые условия экстремума в негладких задачах, а в выпуклых задачах - и достаточные условия. Среди работ указанных авторов, посвященных этой теории, можно отметить, например, [14, 19, 30, 50].

Наряду с задачами математического программирования существуют так называемые динамические задачи, в которых описываются процессы, изменяющиеся во времени. Сюда относятся задачи оптимального управления и во многом пересекающиеся с ними задачи вариационного исчисления. В этих задачах допустимая область задаётся некоторым функциональным пространством, а часть ограничений задаётся системой диффе-* ренциальных уравнений, правые части которых зависят не только от искомой функции, но и от некоторых "управляющих" функций или параметров, выбираемых из некоторого заданного множества. Задачи этого класса существенно отличаются от описанных выше: если в задачах оптимизации функций конечного числа переменных искомая точка экстремума является точкой конечномерного евклидова пространства, то в задачах оптимально* го управления искомая точка, вообще говоря, представляет собой функцию, принадлежащую некоторому бесконечномерному функциональному пространству. Такие задачи имеют многочисленные приложения в самых различных областях человеческой деятельности, связанных с управлением динамическими системами. Количество работ и результатов, посвященных задачам оптимального управления, очень велико, поэтому отметим лишь основополагающие работы JI. С. Понтрягина и др. [48], В. Г. Болтянского [9], Н. Н. Красовского [37], В. Ф. Кротова и В. И. Гурмана [38], А. Я. Дубовицкого и А. А. Милютина [20], В. М. Алексеева и др. [1], Н. Н. Моисеева [45], Р. Беллмана [8] и JI. Янга [69], ставшие классикой.

Тематика диссертации. Настоящая диссертация посвящена разработке и доказательству сходимости численных методов решения задач математического программирования с невыпуклыми ограничениями, названными В. И. Заботиным и Ю. А. Полонским в статье [23] предвыпуклыми. Получение необходимых условий экстремума в задачах с предвыпуклыми ограничениями восходит к работам Б. Н. Пшеничного [51] и Р. Рокафелла-ра [54], где в качестве допустимого множества рассматривалась теоретико-множественная разность конечномерного евклидова пространства и некоторого выпуклого множества и исследовались задачи минимизации выпуклой функции на данном множестве. Надо отметить, что эти необходимые условия были получены как "побочный продукт" теорий, которые строились указанными авторами.

Было, однако, ясно, что в указанных задачах применим аппарат отделимости выпуклых множеств. Дальнейшее развитие применения аппарата отделимости было получено в работах В. И. Заботина и Ю. А. Полонского. Ими вводится понятие предвыпуклого множества, частными случаями которого являются выпуклое множество, выпуклая поверхность, а также множества, рассматриваемые Б. Н. Пшеничным и Р. Рокафелларом. Предвыпуклым было названо множество в линейном пространстве, дополнение которого до его выпуклой оболочки является выпуклым множеством. В статье В. И. Заботина и Ю. А. Полонского [23] показано, что необходимым и достаточным условием предвыпуклости множества является возможность его представления как теоретико-множественной разности двух выпуклых множеств. Основным результатом работ указанных авторов было обобщение теорем отделимости, которое позволило получать необходимые условия экстремума выпуклых функций на различного рода предвыпуклых множествах, включающие в себя и результаты, полученные в [51, 54].

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

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

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

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

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

1) исследовать некоторые необходимые условия экстремума для задач с предвыпуклыми ограничениями;

2) разработать численные алгоритмы решения поставленных задач;

3) доказать сходимость алгоритма метода условного градиента для случая предвыпуклых ограничений с непустым множеством внутренних точек при различных способах выбора итерационного шага;

4) доказать сходимость различных вариантов метода проекции градиента для случая предвыпуклых ограничений с непустым множеством внутренних точек;

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

6) провести вычислительные эксперименты для иллюстрации сходимости рассматриваемых методов.

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

На защиту выносятся следующие результаты:

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

2) формулировки алгоритмов решения поставленных задач;

3) исследование некоторых необходимых условий экстремума для задач с предвыпуклыми ограничениями;

4) обоснование сходимости указанных алгоритмов при различных способах выбора параметров;

5) результаты вычислительных экспериментов, проведённых с помощью разработанного автором программного обеспечения алгоритмов.

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

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

С точки зрения конкретных приложений, рассматриваемые в диссертации методы могут найти своё практическое применение, например, при решении задач проектирования спутниковых созвездий кратного обзора земной поверхности или обзора атмосферного слоя вблизи поверхности Земли. Здесь возникают задачи отыскания экстремума гладких функций и некоторых функций типа максимина, рассматриваемые в работах Ш. И. Галиева [13], В. И. Заботина [22], и Г. В. Можаева [44], при этом экстремум отыскивается на предвыпуклом множестве, являющемся либо выпуклой гладкой поверхностью, либо теоретико-множественной разностью двух шаров или областей, ограниченных эллипсоидами. Сюда относится, в частности, задача нахождения точки атмосферного слоя (земной поверхности), в каком-либо смысле наиболее удалённой от нескольких фиксированных точек этого атмосферного слоя (земной поверхности). Для негладкой функции максимина возможно предварительное сглаживание, описанное, например, в [13], тогда для решения таких задач могут быть использованы методы, которым посвящена диссертация, как это показано в [61].

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

Реализация результатов работы. Полученные в диссертации результаты реализованы в следующих научных отчётах для Академии наук Республики Татарстан, выполненных в рамках научно-исследовательских работ Отделения математики, механики и машиноведения АН РТ, а также в рамках научно-исследовательских работ, поддерживаемых Фондом НИОКР РТ.

1. Этап 2001 г. "Математическое моделирование и информатика оптимальных решений в технологиях и управлении".

Тема: "Фундаментальные и прикладные вопросы информационных технологий, моделирования и управления".

Договор-подряд № 05-5.2.3 / 2001 (ФП).

2. Этап 2002 г. "Построение и исследование математических моделей сложных динамических и статических систем".

Тема: "Модели, методы и программное обеспечение оптимального проектирования и оценивания сложных детерминированных и стохастических систем".

Договор-подряд № 05-5.2-195 / 2002 (Ф).

3. Этап 2003 г. "Методы и алгоритмы исследования математических моделей сложных динамических и статических систем".

Тема: "Модели, методы и программное обеспечение оптимального проектирования и оценивания сложных детерминированных и стохастических систем".

Договор-подряд № 05-5.2-195 / 2003 (Ф).

Указанные договоры входят в "Программу развития приоритетных направлений науки в Республике Татарстан" на 2001-2005 годы.

Апробация результатов исследований. Основные результаты, полученные в диссертации, докладывались и обсуждались на следующих конференциях: Научно-техническая конференция "IX Всероссийские Ту-полевские чтения студентов" (г. Казань, 25-26 октября 2000 года); 6-я Международная конференция "Системный анализ и управление космическими комплексами" (г. Евпатория, 2-8 июля 2001 года); XIII Международная конференция "Проблемы теоретической кибернетики" (г. Казань, 27-31 мая 2002 года); Международная молодёжная научная конференция "XXX Гагаринские чтения" (г. Москва, 6-10 апреля 2004 года).

Публикации по теме диссертации. Основные положения настоящей диссертации опубликованы в 9 печатных работах [24, 25, 60-66], в ♦ том числе в 5 научных статьях "Журнала вычислительной математики и математической физики" Российской Академии наук.

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Черняев, Юрий Анатольевич

Выводы по главе 4

В четвёртой главе диссертации получены следующие результаты: 1) поставлена задача минимизации выпуклой функции для случая предвыпуклых ограничений с непустым множеством внутренних точек; ^ 2) поставлена задача минимизации выпуклой функции для случая ограничений в виде выпуклой гладкой поверхности;

3) предложены численные алгоритмы решения поставленных задач, обобщающие алгоритм метода проекции субградиента;

4) с помощью разработанного автором программного обеспечения проведены расчёты тестовых примеров, иллюстрирующие сходимость ал

•V горитмов, и рассмотрены вычислительные аспекты метода.

ЗАКЛЮЧЕНИЕ

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

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

2) разработаны численные методы оптимизации, обобщающие методы проекции градиента и субградиента на множества обоих указанных типов и метод условного градиента на множества первого типа;

Ы 3) исследованы некоторые необходимые условия экстремума гладких функций на предвыпуклых множествах указанных типов;

4) доказана сходимость метода условного градиента (на уровне необходимых условий экстремума) при различных способах выбора величины итерационного шага;

5) доказана сходимость метода проекции градиента для первого из н двух указанных типов предвыпуклых ограничений (на уровне необходимых условий экстремума) при различных способах выбора параметров;

6) доказана сходимость метода проекции градиента для второго из двух указанных типов предвыпуклых ограничений (на уровне необходимых условий экстремума) при различных способах выбора величины ите рационного шага;

7) проведены расчёты примеров на основе разработанного автором программного обеспечения, реализующего алгоритмы указанных методов для предвыпуклых множеств в виде сферы «-мерного пространства, а также теоретико-множественной разности двух шаров или выпуклого многогранника и шара двумерного или трёхмерного пространства; v 8) рассмотрены вычислительные аспекты алгоритмов указанных методов, и проведён сравнительный анализ этих алгоритмов при различных способах выбора параметров.

Постановка задачи математического программирования с предвы-пуклыми ограничениями, а также формулировки алгоритмов методов проекции градиента и субградиента, изложенные в разделах 2.1, 3.1, 4.1 и 4.2 р диссертации, принадлежат научному руководителю. Доказательство предложения 2.1 и доказательство леммы 3.1 получены автором диссертации и руководителем совместно. Остальные результаты, полученные в диссертации, принадлежат её автору.

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

Список литературы диссертационного исследования кандидат физико-математических наук Черняев, Юрий Анатольевич, 2004 год

1. Алексеев В. М., Тихомиров В. М., Фомин С. В. Оптимальное управление. М.: Наука, 1979. - 429 с.

2. Андронов В. Г., Белоусов Е. Г. О сводимости общей задачи выпуклого программирования к задаче на безусловный экстремум // Известия вузов. Математика. 1995. № 12. С. 10-18.

3. Андронов В. Г., Белоусов Е. Г. О слабой сходимости по аргументу метода штрафных функций // Ж. вычисл. матем. и матем. физ. 1997.1. V Т. 37. №4. С. 404-414.

4. Антипин А. С. Об оценках скорости сходимости метода проекции градиента // Известия вузов. Математика. 1995. Т. 35. № 6. С. 16-24.

5. Антипин А. С., Васильев Ф. П. О непрерывном методе минимизации в пространствах с переменной метрикой // Известия вузов. Математика. 1995. № 12. С. 3-9.

6. Аоки М. Введение в методы оптимизации. М.: Наука, 1977. - 343 с.

7. Ашманов С. А. Линейное программирование. М.: Наука, 1981. - 304 с.

8. Беллман Р. Динамическое программирование. М.: Иностранная литература, 1960. - 400 с.

9. Болтянский В. Г. Математические методы оптимального управления. М.: Наука, 1969. - 408 с.

10. Буземан Г. Выпуклые поверхности. М.: Наука, 1964. - 238 с.

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

12. Васильев Ф. П., Недич А. Об одном варианте регуляризованного v метода проекции градиента // Ж. вычисл. матем. и матем. физ. 1994.1. Т. 34. №4. С. 511-519.

13. Галиев Ш. И. Многократные упаковки и покрытия сферы // Дискретная математика. 1996. Т. 8. № 3. С. 148-160.

14. Гирсанов И. В. Лекции по математической теории экстремальных (у задач. М.: Издательство МГУ, 1970. - 117 с.

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

16. Демьянов В. Ф. Точные штрафные функции в задачах негладкой оптимизации // Вестник СПбГУ. Серия 1. 1994. № 4. С. 21-27.

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

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

19. Дубовицкий А. Я., Милютин А. А. Задачи на экстремум при наличии ограничений // Ж. вычисл. матем. и матем. физ. 1965. Т. 5. № 3. С. 395-453.щ

20. Дубовицкий А. Я., Милютин А. А. Необходимые условия слабого экстремума в общей задаче оптимального управления. М.: Наука, 1971.- 114с.

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

22. Заботин В. И. Задача кратного обзора Земли спутниковыми системами глобальной связи на эллиптических орбитах // Космические исследования. Т. 35. 1997. № 4. С. 445-448.

23. Заботин В. И., Полонский Ю. А. Предвыпуклые множества, отображения и их приложения к экстремальным задачам // Кибернетика. 1981. № 1.С. 71-74.

24. Заботин В. И., Черняев Ю. А. Обобщение метода проекции градиента на экстремальные задачи с предвыпуклыми ограничениями // Ж. вычисл. матем. и матем. физ. 2001. Т. 41. № 3. С. 367-373.

25. Заботин В. И., Черняев Ю. А. Сходимость итерационного метода решения задачи математического программирования с ограничением в виде выпуклой гладкой поверхности // Ж. вычисл. матем. и матем.физ. 2004. Т. 44. №4. С. 609-612.

26. Заботин Я. И. Контрпримеры к алгоритмам Зойтендейка в методах возможных направлений // Известия вузов. Серия матем. 1976. №11. С. 32-37.

27. Заботин Я. И., Кораблёв А. И., Хабибуллин Р. Ф. Условия экстремума функционала при наличии ограничений // Кибернетика. 1973.1. V № 6. С. 65-70.

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

29. Измаилов А. Ф. Необходимые условия высших порядков в задачах на экстремум // Ж. вычисл. матем. и матем. физ. 1992. Т. 32. № 8.1. С. 1310-1313.

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

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

32. Канторович JI. В. Об одном эффективном методе решения некотоk рых экстремальных задач // Доклады АН СССР. 1940. Т. 28. № 3.1. С. 212-215.

33. Карманов В. Г. Математическое программирование. М.: Наука, 1975.-272 с.

34. Карманов В. Г. Об одном подходе к исследованию сходимости релаксационных процессов минимизации // Ж. вычисл. матем. и матем.4 физ. 1974. Т. 14. № 6. С. 1581-1585.

35. Карманов В. Г. Оценки сходимости итерационных методов минимизации //Ж. вычисл. матем. и матем. физ. 1974. Т. 14. № 1. С. 3-14.

36. Кларк Ф. Оптимизация и негладкий анализ.-М.: Наука, 1988.-279 с.

37. Красовский Н. Н. Теория управления движением. М.: Наука, 1968. -475 с.г 38. Кротов В. Ф., Гурман В. И. Методы и задачи оптимального управления. М.: Наука, 1973. - 446 с.

38. Куликов А. Н., Фазылов В. Р. Выпуклая оптимизация с заданной точностью // Ж. вычисл. матем. и матем. физ. 1990. Т. 30. № 5. С. 663-671.

39. Куликов А. Н., Фазылов В. Р. Конечный метод решения систем выпуклых неравенств // Известия вузов. Математика. 1984. № 11. С. 59-63.

40. Ларичев О. И., Горвиц Г. Г. Методы поиска локального экстремума овражных функций. М.: Наука, 1990. - 95 с.

41. Лоран П. Ж. Аппроксимация и оптимизация. -М.: Мир, 1975. -496 с. q 43. Михалевич В. С., Гупал А. М., Норкин В. И. Методы невыпуклойоптимизации. М.: Наука, 1987. - 280 с.

42. Можаев Г. В. Синтез орбитальных структур спутниковых систем. -М.: Машиностроение, 1989. 303 с.

43. Моисеев Н. Н. Элементы теории оптимальных систем. М.: Наука, 1975.-526 с.

44. V 46. Недич А. Регуляризованный непрерывный метод проекции градиента для задач минимизации с неточными исходными данными // Вестник МГУ. Серия вычисл. матем. и киберн. 1994. № 1. С. 3 10.

45. Недич А. Трёхшаговый метод проекции градиента для задач минимизации // Известия вузов. Математика. 1993. № 10. С. 32-38.

46. Понтрягин Л. С., Болтянский В. Г., Гамкрелидзе Р. В., Мищенчко Е. Ф. Математическая теория оптимальных процессов. М.: Наука, 1976.-392 с.49