Разработка и исследование методов ускорения сходимости алгоритмов глобальной условной оптимизации тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Баркалов, Константин Александрович

• Баркалов, Константин Александрович
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Баркалов, Константин Александрович

ВВЕДЕНИЕ.

1. ЗАДАЧИ УСЛОВНОЙ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ.

1.1. постановка задачи условной глобальной оптимизации.

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

1.3. многомерные задачи и методы их сведения к одномерным задачам.

2. МЕТОДЫ УСКОРЕНИЯ СХОДИМОСТИ, ОСНОВАННЫЕ IIA ПОНЯТИИ е-РЕЗЕРВИРОВАННОГО РЕШЕНИЯ.

2.1. ПОНЯТИЕ 8-РЕЗЕРВИРОВАННОГО PELLIEI1ИЯ.

2.2. Индексный алгоритм, учитывающий существование 8-резервированных решений.

2.3. достаточ11ые условия сходимост модифицированного индексного алгоритма.

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

2.5. Адаптивное оценивание резервов.

2.6. Вычислительные эксперименты для оценки ускорения, обеспечиваемого адаптивными оценками s-pe3epbob.

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

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

3.2. Алгоритм с адаптивным порядком проверки ограничений.

3.3. достаточные условия сходимости метода садаптивным порядком проверок.

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

3.5. Адаптивные оценки константы Липшица при переменном порядке проверки ограничений

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

4. УСКОРЕНИЕ СХОДИМОСТИ ЗА СЧЕТ УЧЕТА ЗАВИСИМОСТИ ВРЕМЕНИ ВЫЧИСЛЕНИЯ ФУНКЦИОНАЛОВ ОТ ТОЧКИ ИТЕРАЦИИ.

4.1. Вычислительные затраты в задачах с разным временем вычисления функцио! 1алов.

4.2. Алгоритм, учитывающий различное время вычисления ограничений.

4.3. Достаточные условия сходимости алгоритма.

4.4. Генераторы тестовых задач.

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

5. ВОПРОСЫ УСКОРЕНИЯ РЕШЕНИЯ МНОГОМЕРНЫХ ЗАДАЧ.

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

5.2. Способы построения разверток. Кусочно-линейная развертка.

5.3. Использование множественных отображений.

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

5.5. Применение индексного метода к многомерным задачам.

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

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

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

В общем виде задачу математического программирования можно сформулировать следующим образом. Пусть (р{х), gj(x)<0, 1 <j<m, есть действительные функции, определенные на множестве X N-мерного евклидова пространства RN, и пусть точка х* удовлетворяет условию p(x') = min{<p(x): хеХ, gj(x)£Q, 1 <j<m). (0.1) t

Точка из л:* (0.1) обычно называется глобально-оптимальной точкой или глобально-оптимальным решением. При этом функцию (р{х) называют функцией цели, или целевой функцией, а функции gy(x)<0, 1 <j<m, - ограничениями задачи.

Область X называют областью поиска и обычно описывают как некоторый гиперинтервал из iV-мерного евклидова пространства

X={xeRN: a^x^bi, 1 <i<n) , где a,beRN есть заданные векторы. Точки из области поиска, удовлетворяющие всем ограничениям, называются допустимыми точками или допустимыми решениями. Множество

Q={x: хеХ, gj(x)<0, 1 <j<m} (0.2) всех таких точек называют допустимой областью.

Важный в прикладном отношении подкласс задач вида (0.1) характеризуется тем, что все функционалы, входящие в определение задачи, заданы некоторыми (программно реализуемыми) алгоритмами вычисления значений (р{х), gj{x), 1 <j<m, в точках области поискаХ. При этом решение задачи (0.1) сводится к построению оценки x*eQ, отвечающей некоторому понятию близости к точке х* (например, чтобы х* -х* <£ или <€, где £>0 есть заданная точность) на основе некоторого числа к значений функционалов задачи, вычисленных в точках области X.

Частным случаем задачи (0.1) при отсутствии ограничений, т.е. когда т = 0, является задача безусловной оптимизации. Решению таких задач в настоящее время посвящена обширная литература (см., например, [9], [13], [24], [34], [39], [50], [58]-[60]).

Случай, когда все функционалы задачи обладают свойством линейности, достаточно исследован. Соответствующие результаты в этой области, называемой линейным программированием, опубликованы во многих монографиях и учебниках (см., например, [11], [14], [26]—[28],

32], [36], [37]). Весьма исследован также случай, когда функционалы задачи являются выпуклыми (см., например, [1], [14], [23], [27], [28], [32], [35]).

Если допустить, что функционалы задачи не обладают не обладают свойством выпуклости (именно этот случай и рассматривается в настоящей работе), то допустимая область Q может оказаться не односвяз-ной, а сама задача - многоэкстремальной. Это означает, что в допустимой области Q может оказаться несколько точек х*, 1 <i<n, обладающих свойством локальной оптимальности. Т.е. для каждой из этих точек существует своя et -окрестность £/,- такая, что р{х*)<(р{х), хе Ui(~\Q, 1 <i<n.

Поскольку искомая точка х* совпадает с одной из локально-оптимальных точек xit 1 <i<n, то можно попытаться найти эту точку с помощью релаксационных методов (таких как метод проекции градиента, метод условного градиента, метод возможных направлений и др.), являющихся обобщениями методов безусловной локальной оптимизации на случай наличия ограничений (см. [14], [27], [32], [35]). При этом нужно либо иметь начальную точку из области притяжения точки х * (т.е. из области, где х * есть единственная локально-оптимальная точка), либо найти все локально-оптимальные точки х*, 1 <i<n, для их последующего сравнения. Трудность, связанная с таким подходом, состоит в том, что ни область притяжения точки х *, ни число п локально-оптимальных точек обычно не известны.

Другой известный подход к решению многоэкстремальных задач вида (0.1) состоит в использовании штрафных функций. Идея метода штрафных функций состоит в замене исходной задачи математического программирования x*=argmin{(р{х): xeQ], где Q из (0.2), задачей безусловной оптимизации argmin{ (p{x) +Лу/(х)}, (0-3) где функция у/{х) называется функцией штрафа, а величина Л - коэффициентом штрафа. Примерами функций штрафа могут служить т

У=1 т

К*) = ехр(|>ах{£у(х),0}П-1, Р> 1

У=1

При этом помимо коэффициента Я, могут вводиться также весовые коэффициенты Xj, \<j<n, при слагаемых с целью выравнивания их "вклада" в штраф.

Недостатком метода штрафных функций является то, что при "свертывании" функций ограничений в одну штрафную функцию происходит потеря информации о поведении каждого ограничения в отдельности. Кроме того, существуют трудности, связанные с подбором штрафных коэффициентов. Следует также отметить, что метод штрафов (с учетом указанных трудностей) снимает лишь проблему ограничений, но не снимает проблемы многоэкстремальности и, следовательно, для решения задачи (0.3) приходится использовать уже упоминавшиеся методы глобальной оптимизации для задач без ограничений (см., например, [9], [13], [24], [34], [39], [50], [58]-[60]).

Новый подход к решению задач условной глобальной оптимизации (получивший название индексного метода) был разработан на кафедре математического обеспечения ЭВМ факультета вычислительной математики и кибернетики Нижегородского государственного университета под руководством Р.Г. Стронгина (см. [5], [39]—[41], [44], [46], а также [64]). Характерной чертой этого подхода, не использующего идей метода штрафных функций, является раздельный учет каждого ограничения задачи. В соответствии с правилами индексного метода каждая итерация, называемая испытанием в соответствующей точке области поиска, включает последовательную проверку выполнимости ограничений задачи в этой точке, а обнаружение первого нарушенного ограничения прерывает испытание и инициирует переход к точке следующей итерации. При этом допускается, что некоторые функционалы задачи определены не во всей области поиска X. Это обстоятельство может быть важным в приложениях, поскольку невыполнение некоторых (представленных ограничениями) условий для одних характеристик задачи может вызвать неопределенность других характеристик. Указанная схема подробно воспроизведена в двух первых параграфах первой главы работы.

В обсуждаемом подходе используется еще одно важное нововведение. Решение многомерных задач сводится к решению эквивалентных им одномерных задач. Соответствующая редукция основана на использовании разверток единичного отрезка вещественной оси на гиперкуб. Роль таких разверток играют непрерывные однозначные отображения типа кривой Пеано, называемые также кривыми, заполняющими пространство, и их обобщения, названные "множественными развертками". Численные методы, позволяющие эффективно использовать аппарат таких отображений, детально разработаны в [39] - [41] и [64].

Алгоритмы, развиваемые в рамках указанного подхода, основаны на предположении липшицевости всех функционалов задачи, что типично и для многих других подходов (см., например, [17], [20], [59]). Предположение такого рода является достаточно естественным для многих прикладных задач, поскольку относительные вариации функционалов, характеризующих моделируемую систему, обычно не могут превышать некоторый порог, определяемый ограниченной энергией изменений в системе. Возникающий при этом вопрос об оценке априори неизвестных значений констант Липшица может решаться путем введения адаптивных схем (см. [38], [39], [60], а также [64]).

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

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

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

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

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

Диссертационная работа состоит из пяти глав.

В первой главе излагаются исходные положения индексного метода решения одномерных многоэкстремальных задач условной глобальной оптимизации. С этой целью в § 1.1 описана постановка задачи минимизации многоэкстремальной функции при невыпуклых ограничениях. Дано определение индекса точки и описана схема его определения. В § 1.2 изложена схема индексного алгоритма глобального поиска и приведена формулировка достаточных условий его сходимости. В § 1.3 рассмотрен вопрос сведения многомерной задачи условной оптимизации к эквивалентной ей одномерной задаче.

Во второй главе рассматривается предложенный в работе метод ускорения, основанный на понятии ^-резервированного решения. В § 2.1 введено определение ^-резервированного решения, а также множества допустимых точек, которые не хуже (по значению целевой функции), чем ^-резервированное решение. Введенные понятия проиллюстрированы на примерах. В § 2.2 изложен модифицированный индексный алгоритм, учитывающий существование ^-резервированных решений. Условия сходимости модифицированного алгоритма приведены и доказаны в § 2.3. В § 2.4 исследована скорость сходимости модифицированного алгоритма. Далее в § 2.5, с учетом полученных теоретических результатов, предложены схемы адаптивного оценивания заранее неизвестных параметров резервирования. Сравнение эффективности алгоритмов проведено путем проведения численных экспериментов, результаты которых приведены в § 2.6.

В третьей главе рассматривается метод ускорения сходимости, основанный на введении переменного порядка ограничений. В § 3.1 рассмотрена связь порядка проверки ограничений в задаче условной оптимизации и вычислительных затрат на решение задачи. Отмечено, что введение переменного порядка проверки ограничений может снизить вычислительные затраты на проведение отдельной итерации. При этом используется достаточно естественное предположение, что ограничение (если таковое есть), нарушение которого прервало некоторую итерацию, будет нарушено также во всех точках из некоторой окрестности точки этой итерации. Это предположение позволяет (адаптивно) упорядочивать ограничения по "вероятности" их нарушения в новой точке итерации (путем анализа нарушений в соседних точках). В § 3.2 изложена схема нового алгоритма, в котором используется переменный порядок проверки. Для предложенного алгоритма с адаптивным порядком проверок в §3.3 сформулированы и доказаны достаточные условия сходимости. Генераторы многоэкстремальных тестовых задач с невыпуклыми ограничениями описаны в § 3.4.

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

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

В четвертой главе предложен метод ускорения сходимости за счет учета зависимости времени вычисления функционалов задачи от точки проведения итерации. Сказанное актуально для задач, в которых оценка функционалов требует заметных вычислительных ресурсов, связанных с необходимостью численного моделирования поведения систем, характеризуемых этими функционалами (§ 4.1). В § 4.2 изложен алгоритм с переменным порядком проверки ограничений, при котором ограничения адаптивно упорядочиваются по возрастанию трудоемкости их проверки. Это позволяет начинать проверку с "простых" ограничений, переходя затем к более "сложным". В § 4.3 приведены достаточные условия сходимости алгоритма. Предложенный для тестирования алгоритма класс задач условной глобальной оптимизации, для которого характерно зависящее от точки итерации время вычисления функционалов, описан в § 4.4. Результаты сравнения стандартного индексного алгоритма и алгоритма с упорядочиванием ограничений по трудоемкости приведены в § 4.5. Здесь же рассмотрен вопрос об адаптивных оценках константы Липшица для данного класса задач.

Пятая глава иллюстрирует возможность применения полученных результатов для решения многомерных задач с использованием схемы редукции размерности, основанной на отображениях типа кривой Пеано. Для этого в § 5.1 описан механизм редукции многомерной задачи к эквивалентной ей одномерной задаче с помощью кривых, заполняющих пространство (разверток). Конкретные способы построения разверток - кусочно-линейная и множественная развертки - приведены в § 5.2. Индексный алгоритм многомерной глобальной условной оптимизации, использующий множественную развертку, изложен в § 5.3. Здесь же приведены и доказаны достаточные условия его сходимости. В § 5.4 приведены результаты численных экспериментов, показывающие эффект ускорения при применении индексного алгоритма с ^-резервированием к многомерным задачам условной глобальной оптимизации.

Практическая ценность работы. Исследования по теме диссертации выполнялись при поддержке ФЦНТП "Исследования и разработки по приоритетным направлениям развития науки и техники гражданского назначения", направление "Автоматизация проектирования", проект 297, а также при финансовой поддержке Российского фонда фундаментальных исследований (проект 01-01-00587, проект 04-01-00455). Результаты работы использовались при реализации совместного исследовательского проекта РФФИ и Нидерландской организации по научным исследованиям (the Netherlands Organization for Scientific Research - NWO); номер проекта NWO: 047.016.014. Также результаты работы используются при чтении курса "Численные методы" для студентов четвертого курса факультета ВМК ННГУ.

Апробация работы. Результаты работы докладывались на XII международной конференции "Проблемы теоретической кибернетики" (И. Новгород, 1999), на VI нижегородской сессии молодых ученых (Н.Новгород, 2001), на международной конференции, посвященной памяти проф. А.М.Богомолова (Саратов, 2002), на VI Международном конгрессе по математическому моделированию (Н.Новгород, 2004), на научных конференциях и семинарах Нижегородского государственного университета.

• Основное содержание диссертации отражено в двенадцати работах

2]-[7], [42]—[45], [51], [57].

В заключение выражаю глубокую признательность моему научному руководителю Роману Григорьевичу Стронгину за внимание и поддержку в работе.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Баркалов, Константин Александрович

Результаты работы докладывались на XII международной конфе-® ренции "Проблемы теоретической кибернетики" (Н. Новгород, 1999), на

VI нижегородской сессии молодых ученых (Н. Новгород, 2001), на международной конференции, посвященной памяти проф. А.М.Богомолова (Саратов, 2002), на научных конференциях и семинарах Нижегородского государственного университета им. Н.И. Лобачевского.

Основное содержание диссертации отражено в двенадцати работах

2Н7], [42]-[45], [51], [57].

Заключение

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

Список литературы диссертационного исследования кандидат физико-математических наук Баркалов, Константин Александрович, 2006 год

1. Баркалов КА. Ускорение сходимости в задачах условной глобальной оптимизации. Нижний Новгород: изд-во Нижегородского гос. ун-та, 2005.

2. Баркалов К.А., Стронгин Р.Г. Многомерный алгоритм глобальной оптимизации с использованием развертки с переменным шагом// Шестая нижегородская сессия молодых ученых: тез. докл., Нижний Новгород, Нижегородский гуманитарный центр, 2001. С. 9.

3. Баркалов К.А., Стронгин Р.Г. Метод условной глобальной оптимизации с адаптивным порядком проверки ограничений// Математика и кибернетика 2002: тез. докл., Нижний Новгород, типография Нижегородского госуниверситета, 2002. С. 6.

4. Баркалов К.А., Стронгин Р.Г. Метод глобальной оптимизации с адаптивным порядком проверки ограничений// Ж. вычисл. матем. и матем. физ. 2002. Т.42. №9. С. 1338-1350.

5. Баркалов К.А., Стронгин Р.Г. Учет времени вычисления функционалов в задачах условной глобальной оптимизации// Вестник ННГУ. Математическое моделирование и оптимальное управление, Нижний Новгород: изд-во Нижегородского гос. ун-та, 2003. С. 145-161.

6. БарронД. Рекурсивные методы в программировании. М.: Мир, 1974.

7. Батищев Д.И. Методы оптимального проектирования. М: Радио и связь, 1984.

8. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М. Наука, 1987.

9. Булавский В.А., Звягина Р.А. Яковлева М.А. Численные методы линейного программирования. М.: Наука, 1977.

10. Булатов B.YI. Методы погружения в задачах оптимизации. Новосибирск: Наука, 1977.

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

12. Габасов Н.С., Кириллова Ф.М. Методы оптимизации. Минск: Изд-во Белорусского ун-та, 1975.

13. Гергель В.П. Об одном способе учета значений производных при минимизации многоэкстремальных функции // Ж. вычисл. матем. и матем. физ., 1996. Т. 36 № 6. С. 51-67.

14. Гергель В.П., Стронгин Р.Г. Абсолют. Программная система для исследований и изучения методов глобальной оптимизации. Н.Новгород: Изд. Нижегород. ун-та, 1998.

15. Городецкий С.Ю. Многоэкстремальная оптимизация на основе триангуляции области// Вестник ННГУ. Математическое моделирование и оптимальное управление, Нижний Новгород: изд-во Нижегородского гос. ун-та, 1999, вып. 2, С. 249-269.

16. Гришагин В.А. Операционные характеристики некоторых алгоритмов глобального поиска// Проблемы случайного поиска. Рига: Зи-натне, 1978. №.7. с. 198-206.19