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

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

ЧЕРНЯЕВ Юрий Анатольевич

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

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

Казань 2004

Работа выполнена в Казанском государственном техническом университете им. А. Н. Туполева

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

Заботин Владислав Иванович

Официальные оппоненты: доктор физико-математических наук, с. н. с.

Сидоров Игорь Николаевич

доктор физико-математических наук, доцент Фазылов Валерий Рауфович

Ведущая организация: Новгородский государственный университет

им. Ярослава Мудрого

Защита состоится " 25 " июня 2004 г. в Щ часов на заседании диссертационного совета Д 212.079.01 в Казанском государственном техническом университете им. А. Н. Туполева по адресу: 420111, ул. К. Маркса, 10

С диссертацией можно ознакомиться в библиотеке Казанского государственного технического университета им. А. Н. Туполева

Автореферат разослан мая 2004 г.

Учёный секретарь диссертационного совета,

доктор физико-математических наук, профессор ^(¿№¿/£¿2 П. Г. Данилаев

нчоа э

~ 1 -

ЛГ.^дО 4В

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

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

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

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

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

РОС НДИЙГ.гпЛМПП I .;:..'<..чц..!.;\

•"2 С. Пек^'Сур'

ф

'АЛ/РК

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 печатных работах, в том числе в 5 научных статьях "Журнала вычислительной математики и математической физики" Российской Академии наук.

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

В разделе 1.1 диссертации ставится задача минимизации вида ф(дг)->1шп, xeXczR", где <р(х)еС'(Х), а множество X ограничено и представимо в виде теоретико-множественной разности некоторых множеств F и intG, причём F и G выпуклы и замкнуты, множества внутренних точек X и G непусты, граница G является гладким многообразием. Решение поставленной задачи всегда существует в силу ограниченности Хи непрерывности <р(дг).

Вводятся обозначения, которые используются в первой и второй главах диссертации: - проекция точки х на множество G, п(х) - вектор внешней ортонормали к G в точке $(*)> Г(х) - опорное полупространство к G в точке 5(л), Р(д:>=Г(д:)П^г • Везде считается, что хеХ. Множества Г(*) и Р(х) и проекции s(x), построенные для точек хк и х„ обозначаются соответственно и r.,P,,s..

В силу выпуклости и замкнутости G, проекции s(x) существуют и определяются однозначно. Поскольку граница множества G - гладкое многообразие, векторы н(х), а значит, и множества Г(х) определяются однозначно для любого хеХ. Показано, что хеР(х) для всех хеХ.

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

Шаг 0. Пусть к=0.

Шаг 1. Пусть xt еХ есть к-е приближение.

Шаг 2. Определяется точка sk.

Шаг 3. Строится полупространство r¿.

Шаг4. Строится множество Р1.

Шаг 5. Пусть х'к — решение задачи (ф'(хДх-х*)-»тт,хе/».

Шаг 6. Задается величина а4 е[0; 1].

Шаг 7. Пусть =хк +а*(х'к

Шаг 8. Если хк=хм, то хк считается решением задачи, иначе положить к:=к+1 и перейти к шагу 1.

Множества Рк,к<= 0,1,2,... выпуклы и замкнуты, так как являются пересечением выпуклого замкнутого множества Р с замкнутыми полупространствами Г4. Множества ГЛ, £=0,1,2,... являются опорными полупространствами к выпуклому множеству б, то есть при любом к имеет место ГкГ\т№=0. Отсюда следует, что поскольку \intG.

Это означает, что Рк, к-0,1,2,... ограничены в силу ограниченности множества X. Таким образом, шаг 5 изложенного алгоритма представляет собой решение задачи минимизации линейной функции на выпуклом, замкнутом и ограниченном множестве. Эта задача при любом к имеет решение в силу компактности Рк и непрерывности минимизируемой функции. Числа а1, ¿=0,1,2,..., характеризующие величину итерационного шага движения в направлении, найденном из решения вспомогательной задачи минимизации линейной функции, могут выбираться по-разному.

В разделе 1.2 диссертации рассматриваются необходимые условия экстремума гладкой функции ср(х) на множестве X вида, описанного в разделе 1.1. Доказывается следующее предложение о необходимом условии локального минимума для случая, когда множество ^задаётся в произвольной форме.

Предложение 1.1. Если х. - точка локального минимума функции <р(х) на мноэхестве X, то выполняется условие

УхеД : ( ф'(*0» (1)

Далее рассматривается задание множества X вида, указанного в постановке задачи, с помощью функциональных ограничений типа неравенств, и доказывается, что любая точка, удовлетворяющая условию (1) или условию ЫР.~0, является стационарной в смысле Лагранжа.

Множество X может задаваться в виде

Х={хеЯ"\/,{х)йО,Ы\.....т+1} (2)

при выполнении условий:

2) /,(х),1=\,т выпуклые, /т|(дг) вогнутая в Л";

3) /((х)<0, :=1,7и+1 для некоторой точки хеЯп;

4) /п+1(дг)>0 для некоторой точки хеЛ".

Из этих условий и теорем выпуклого анализа следует, что Х- множество вида, указанного в разделе 1.1, если оно ограничено. В частности, из условия 2 следует, что множества

Я={хбК"|/)(х)£0}, 1=1,2.....т

выпуклы, а множество выпукло как пересечение выпуклых множеств,

(=1

множество 0~{хеЯ" | тоже выпукло. Из условия 3 следует, что

ЫХ*0, а из условия 4 следует, что тЮф(8. Из условия 1 следует, что граница (? есть гладкое многообразие.

Далее доказывается следующая лемма, в формулировке которой через К,,К(Х),К(Р.) обозначены конусы возможных направлений множеств /<), X, Р. соответственно, построенные для точки х..

/я+1

Лемма 1.1. Справедливы равенства К(Х)=К(Р.)= П К,.

м

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

Предложение 1.2. Пусть Х-множество вида (2) и выполняются условия 1-4, а функция ф(л) принадлежит классу С'(Х). Тогда любая точка х.еХ, удовлетворяющая условию (1) или условию и& Р, =0, является стационарной в смысле Лагранжа.

В разделах 1.3 и 1.4 диссертации исследуется сходимость алгоритма при различных способах выбора итерационного шага. Сначала вводится обозначение х~хк) и доказывается следующая лемма.

Лемма 1.2. Если X- множество рассматриваемого вида, ф(х)еС'''(Х), д;0 — произвольная точкаХ, последовательность {дг4} построена по алгоритму раздела 1,1 при некотором способе выбора чисел ак, &=0,1,2,... и 1т1ф<(х*)=0, то любая её предельная точка х., для которой удо-

влетворяет условию (1).

Утверждение этой леммы используется при доказательстве сходимости алгоритма в разделах 1.3 и 1.4 диссертации.

В разделе 1.3 рассматривается выбор чисел ак, ¿=0,1,2,..., характеризующих величину итерационного шага, из условия наискорейшего спуска, то есть на каждой итерации полагается

а, =аг§пипф[д:4 -**)]•

ас10;1]

В разделе 1.4 рассматривается случай, когда величина а* на каждой итерации полагается равной 2";, где у есть первый индекс /=0,1,2,..., для которого выполняется неравенство

Показано, что если <р(д:)еСи(Х), то указанный способ выбора чисел ак, ¿=0,1,2,... возможен.

В разделах 1.3 и 1.4 для соответствующих способов выбора итерационного шага доказываются следующие предложения о сходимости метода.

Предложения 1.3, 1.4. Если X - множество рассматриваемого вида, ф(х)еСи(ЛТ), х0 - произвольная точка X и последовательность построена по алгоритму раздела 1.1 при указанном способе выбора чисел ос*, к=0,1,2,..., то любая её предельная точка х., для которой удо-

влетворяет условию (1).

Из предложения 1.2 следует, что если множество X задаётся в виде (2) при выполнении соответствующих условий 1-4 и выполняются требования только что приведённого предложения, то любая предельная точка х» последовательности стационарна в смысле Лагранжа.

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

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

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

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

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

Шаг0.Пусть к-0.

Шаг 1. Пусть хк еХ есть к-е приближение.

Шаг 2. Определяется точка

Шаг 3. Строится полупространство Г*.

Шаг 4. Строится множество Рк,

Шаг 5. Задаётся величина <хк >0.

Шаг 6. Пусть ук - проекция точки хк-ак<р'(л:к) на Рк.

Шаг 7. Задаётся величина р4 е[0; 1].

Шаг 8. Пусть хм =хк +р,(ук -хк).

Шаг 9. Если хк =х<+], то хк считается решением задачи, иначе полагается к'.=к+1 и осуществляется переход к шагу 1.

Множества Рк, к-0,1,2,... выпуклы и замкнуты, так как являются пересечением выпуклого замкнутого множества Г с замкнутыми полупространствами ГА, и непусты, так как по построению хк<~Рк,к=0,1,2.....поэтому

задача проектирования точки хк -ак(р'(хк) на множество Рк при к=0,1,2,.,. имеет единственное решение. Числа а*, р*, к-0,1,2,... могут выбираться различными способами.

В разделе 2.2 исследуется сходимость изложенного алгоритма при следующих условиях:

1) (р(х)еС',1(Х);

2) М(х0)={хеХ1<р(х)£<р(*0)} - ограниченное множество, где х0еХ есть выбранное начальное приближение;

3) ак,к=0,1,2,... выбираются так, что выполняются неравенства Ф(х* )-ф(хА+1)£е||хк -хд+|||2, где е - некоторое положительное число;

4) а4,А=0,1,2,... ограничены снизу положительным числом;

5) р4=1 при ¿=0,1,2,...

Показано, что выбор чисел а4, ¿=0,1,2,... из условий 3 и 4 при выполнении условия I всегда возможен.

В разделе 2.3 исследуется сходимость того же самого алгоритма при следующих условиях:

1) А/(х0)={хеЛГ|ф(х):аф(х0)} - ограниченное множество, где х0еЛГ есть выбранное начальное приближение;

2) а» =а, ¿=0,1,..., где а - некоторая положительная константа;

3) р, =а^пип ф[х, +р(л ¿=0,1,2,...

ОфЯ

Доказывается следующая лемма, используемая при доказательстве сходимости алгоритма.

Лемма 2.1. Если точки хк и ук не совпадают, то р* >0.

Далее вводится на множестве X вспомогательная функция фс)=ф(х)-штф[х+Р(;Кх)-х)],

где у(л-)=РгР(;<)[х-аф(х)], и доказываются ещё две леммы.

Лемма 2.2. Точка у(х) непрерывно зависит от х при любом хеХ, для которого ]хйР{х)ф0.

Лемма 2.3. Функция %(х) непрерывна в любой точке хеХ, для которой яйР(х)Ф0.

Утверждение леммы 2.2 используется при доказательстве сходимости алгоритма в каждом из разделов 2.3 и 2.4 диссертации, утверждения лемм 2.1 и 2.2 - только в разделе 2.3.

В разделе 2.4 рассмотрен случай, когда величина а4 на каждой итерации полагается равной некоторой произвольной положительной константе а, а величина рл полагается равной 2"у, где] есть первый индекс /=0,1,..., для которого выполняется неравенство

ф(х, +2"' (у* -**))£ф(** )+0,5-2-'Ф, (ук). Показано, что если ф(х)еСм(.ЛГ), то указанный способ выбора чисел Рд ¿=0,1,2,... возможен. Исследована сходимость алгоритма при следующих условиях:

1) ф(*)еС'-'(*);

2) Л/(*0)={;се.ЛГ|ф(х)£ф(х0)} - ограниченное множество, где x0sX есть выбранное начальное приближение;

3)числа at, ßj, к=0,1,2,... выбираются указанными способами.

В разделах 2.2, 2.3 и 2.4 для соответствующих способов выбора параметров доказываются следующие предложения о сходимости метода.

Предложения 2.1, 2.2, 2.3. Если Х-множество рассматриваемого вида, последовательность {jct} построена по алгоритму раздела 2.1 и выполняются вышеперечисленные условия, то любая её предельная точка х., для которой int Р. Ф0, удовлетворяет условию (1).

Из предложения 1.2 следует, что если множество X задаётся в виде (2) при выполнении соответствующих условий 1-4 и выполняются требования только что приведённого предложения, то любая предельная точка х. последовательности {xj} стационарна в смысле Лагранжа.

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

Вычисления показали, что при выборе параметров, рассмотренном в разделе 2.2, сходимость алгоритма, как правило, достаточно быстрая, но число ак на каждой итерации приходится определять дроблением некоторой константы а; при этом каждый раз приходится заново решать задачу проектирования, что ведёт к росту объёма вычислений. Если константу а задать слишком маленькой, то дробить её не придётся, но сходимость алгоритма будет более медленной. Эффективность вычислений зависит также от удачного выбора константы е.

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

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

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

Рассматривается задача минимизации вида ф(х)—>min, xeXcR", где <р(х)еС'(Х), а множество X есть граница некоторого выпуклого замкнутого множества G, причём последняя является гладким многообразием и множество внутренних точек G непусто, то есть X— выпуклая гладкая поверхность. Предполагается, что решение поставленной задачи существует. Множество X пред-выпукло, так как оно является теоретико-множественной разностью G и intG, где intG выпукло в силу выпуклости множества G.

Вводятся обозначения: и(*) _ вектор внешней ортонормали к G в точке х\ А(х) - опорная гиперплоскость к G в точке х. Везде считаем, что хеХ. Гиперплоскости Л(х), построенные для точек хк и х., обозначаются соответственно Ак и Л..

Поскольку граница G — гладкое многообразие, вектор внешней ортонормали п(х) и опорная гиперплоскость

A(x)={eeÄ":(w(x), е-*)=0} определяются однозначно для любого хеХ.

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

Шаг 0. Пусть к = 0.

Шаг 1. Пусть хк еХ есть к-е приближение.

Шаг 2. Строится гиперплоскость Ак.

Шаг 3. Задаётся величина ак >0.

Шаг 4. Пусть zk - проекция точки хк-аку'(хк) на Ак.

Шаг 5. Пусть - проекция точки zk на G.

Шаг 6. Если хк =хм, то хк считается решением задачи, иначе полагается &:=£+1 и осуществляется переход к шагу 1.

Множества G и Л4,А=0,1,2,... выпуклы, замкнуты и непусты, поэтому задачи проектирования на итерациях решаются единственным образом, следовательно, при заданном выборе чисел ак,к=0,1,2,... последовательность }

строится однозначно. Проектирование точки гк при к-0,1,2,... на множество О равносильно её проектированию на X, так как Л" есть граница (7, а точка гк по построению не лежит в ЫО. Числа ак,к=0,1,2,..., характеризующие величину итерационного шага перемещения по антиградиенту на итерациях, могут выбираться по-разному.

В разделе 3.2 рассмотрен случай, когда множество X задаётся с помощью ограничения типа равенства в виде

*={*еЛ"|я(*)=0} (3)

при выполнении условий:

1) вЮеСЧД");

2) g(x) выпукла в Л";

3) я(х)<0 при некотором хеН".

При построении считаются выполненными предположения:

1) фig(x)eC^^^(G);

2) А/(;с0)={хе.ЛГ| ф(х)5ф(л:0)} - ограниченное множество, где х0еХ есть выбранное начальное приближение;

3) а*,£=0,1,2,... выбираются так, что выполняются неравенства

ф(ж;1)-ф(х4+1)>8||д:д — х1+1||2, где е - некоторое положительное число;

4) а*, ¿=0,1,... ограничены снизу положительным числом.

Показано, что выбор чисел ак, к=0,1,2,... из условий 3 и 4 при выполнении условия 1 всегда возможен.

Доказывается следующее предложение о сходимости алгоритма. Предложение 3.1. Если Х-множество, заданное в виде (3) при выполнении условий 1-3, последовательность {хЛ} построена по алгоритму раздела 3.1 и выполняются предположения 1-4, то любая её предельная точка х, стационарна в смысле Лагранжа.

В разделе 3.3 рассмотрен случай, когда числа ак, к-0,1,2,... выбираются из условия

а*=агвпипф[Рг0(г,(а))], /с=0,1,2,...,

асЮ-.Р]

где гк (а) - проекция точки хк -аф'(**) на Ак, а р - заданное фиксированное положительное число. Множество X задаётся в произвольной форме.

Пусть р - фиксированное положительное число, а у, - проекция точки х.~Рф'(х.) на Л(х.)> построенная для произвольного х.еХ. Доказано еле-

дующее предложение о необходимом условии локального минимума на множестве X рассматриваемого вида.

Предложение 3.2. Если х. - точка локального минимума функции <р(х) на множестве X, то точки х. и у. совпадают.

Далее вводится на множестве X вспомогательная функция ^(дг)=Ф(х)-ттф[Ргс(д:+аСу(*)-*))]

и доказывается следующая лемма, используемая при доказательстве сходимости алгоритма.

Лемма 3.1. Функция непрерывна на множестве X.

Доказано следующее предложение о сходимости алгоритма.

Предложение 3.3. Если X — множество вышеописанного вида, последовательность {**} построена по изложенному выше алгоритму и множество М{ха)={х<аХ\ф(х)^ф(х0)} ограничено, то любая предельная точка х, построенной последовательности удовлетворяет необходимому условию экстремума в смысле утверждения предложения 3.2.

Показано, что если множество X задаётся с помощью ограничения типа равенства в виде (3), где g(x) является выпуклой и гладкой, то любая точка х,, стационарная в смысле утверждения предложения 3.2, является стационарной в смысле Лагранжа.

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

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

Рассматриваемые в четвёртой главе задачи аналогичны поставленным в разделах 2.1 и 3.1 диссертации. Отличие в том, что здесь требование гладкости функции ф(х) заменено требованием её выпуклости.

Предлагаемые в разделах 4.1 и 4.2 диссертации алгоритмы аналогичны изложенным соответственно в разделах 2.1 и 3.1 с тем отличием, что здесь на каждой итерации вместо градиента <р(х), который в произвольной точке может не существовать, определяется её субградиент. Что касается значений а^, ¿=0,1,2,..., то их можно выбирать, например, из условий

р4 =1, ¿=0,1,2,...; а4>0, ¿=0,1,2,...; £а,=а>; ±а.\<«>.

Последним условиям удовлетворяют, например, числа

а,^(¿н-!)-',¿=0,1,..., где С>0, 0,5<р^1. (4)

Возможны и другие способы выбора параметров а*, Р* на итерациях. В качестве субградиента функции ф(д-) на каждой итерации для простоты вычислений можно брать произвольный элемент с^еЭфОО, но для ускорения сходимости предпочтительнее брать ск =сгшп ^¡сЦ, так как в этом случае вектор ск

есть направление наискорейшего спуска для функции ф(х) в точке хк.

В разделе 4.3 приведены некоторые результаты вычислений для случая, когда множество X представлено в виде окружности, теоретико-множественной разности выпуклого многоугольника и круга или двух кругов двумерного пространства, а ф(х) является функцией максимума конечного числа выпуклых гладких функций двух переменных. Числа а4, ¿=0,1,2,... выбираются из условий (4). Проведённые расчёты показали эффективность метода для ряда задач. Скорость сходимости во многом зависит от выбора параметров С и р.

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

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

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

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

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

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

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Черняев Ю. А. Метод проекции градиента для задач с предвыпуклыми ограничениями // Тезисы докладов научно-технической конференции "IX Всероссийские Туполевские чтения студентов". Т. 2. С. 17. - Казань: Изд-во КГТУ, 2000.

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

3. Черняев Ю. А. Применение обобщённого метода проекции градиента к задачам проектирования спутниковых созвездий кратного обзора Земли // Тезисы докладов 6-й Международной конференции "Системный анализ и управление космическими комплексами". С. 78-79. - М.: Изд-во МАИ, 2001.

4. Черняев Ю. А. Применение метода проекции градиента к решению задач с предвыпуклыми ограничениями // Тезисы докладов XIII Международной конференции "Проблемы теоретической кибернетики". Ч. 2. С. 192. - М.: Изд-во Центра прикл-х иссл-й при мех.-мат. фак-те МГУ, 2002.

5. Черняев Ю. А. Об одном численном алгоритме решения экстремальных задач с предвыпуклыми ограничениями // Журнал вычислительной математики и математической физики. 2003. Т. 43. № 2. С. 169-175.

6. Черняев Ю. А. Метод условного градиента для экстремальных задач с предвыпуклыми ограничениями // Журнал вычислительной математики и математической физики. 2003. Т. 43. № 12. С. 1910-1913.

7. Черняев Ю. А. Обобщение метода условного градиента на случай предвы-пуклых допустимых множеств // Тезисы докладов Международной молодёжной научной конференции "XXX Гагаринские чтения". Т. 2. С. 104. - М.: МАГИ, 2004.

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

9. Черняев Ю. А. Два алгоритма решения задачи математического программирования с предвыпуклыми ограничениями // Журнал вычислительной математики и математической физики. 2004. Т. 44. № 7. С. 1228-1232.

> _

Формат 60x84. 1/16. Бумага офсетная. Печать офсетная. Печ.л. 1,0 . Усл.печ.л.0,33. Усл.кр.-отг.0,3£. Уч.-изд.л. 1,0 . * Тираж 100. Заказ $>90 .

Типография Издательства Казанского государственного технического университета им. А. Н. Туполева 420111, Казань, К. Маркса, 10.

РНБ Русский фонд

2007-4

13 200^ 1

Введение

Глава 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 ч

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