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

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

Баркалов Константин Александрович

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ УСКОРЕНИЯ СХОДИМОСТИ АЛГОРИТМОВ ГЛОБАЛЬНОЙ УСЛОВНОЙ ОПТИМИЗАЦИИ

Специальность 01.01.09 Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Нижний Новгород - 2006

Работа выполнена на кафедре математического обеспечения ЭВМ факультета вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского.

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

д. ф.-м.н., проф. Стронгин Р.Г.

Официальные оппоненты:

член-корр. РАН, проф. Флеров Ю.А. к.ф.-м.н., доцент Коротченко А.Г.

Ведущая организация:

факультет ВМК МГУ им. М.В. Ломоносова

седан ии диссертационного совета Д 212.166.06 при ННГУ им. Н.И. Лобачевского по адресу: 603950, г. Нижний Новгород, пр. Гагарина, 23, корп. 2, конференц-зал.

С диссертацией можно ознакомиться в фундаментальной библиотеке ННГУ им. Н.И. Лобачевского.

Автореферат разослан "14 " апреля 2006 г.

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

Защита диссертации состоится " " мая 2006 г. в \Ч ^

часов на за-

к.ф.-м.н., доцент

Я ооб А

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

Актуальность темы диссертационной работы. Математическими моделями широкого класса проблем рационального выбора являются задачи минимизации функций при дополнительных ограничениях. В большинстве случаев решить подобные задачи можно только численно. Стремительное развитие вычислительной техники сделало возможным решение экстремальных задач, которые ранее из-за своей сложности представлялись недоступными. Библиография по вопросам численного решения оптимизационных задач насчитывает в настоящее время сотни наименований (см., например, работы Д.И. Батищева, Ф.П. Васильева, В.П. Гергеля, В.А. Гришагина, Ю.Г. Евтушенко, А.Г. Жилинскаса, В.Г. Карманова, А.Г. Коротченко, С.А. Пиявского, Я.Д. Сергеева, Р.Г. Стронгина, Ю.А. Флерова, П. Пардалоса, Я. Пинтера, X. Туя, Д. Уайлда, Д. Химмельблау, Р. Хорста, и др.). Одним из предложений, позволяющим разрабатывать эффективные алгоритмы решения оптимизационных задач, является выпуклость допустимой области и целевой функции. Отказ от требований выпуклости приводит к классу задач многоэкстремальной оптимизации при невыпуклых ограничениях, решение которых сопряжено со значительным объемом вычислений. Распространенные методы решения подобных задач обладают существенными недостатками. Например, релаксационные методы гарантируют, вообще говоря, сходимость лишь к локально-оптимальной точке, а метод штрафных функций является весьма затратным, так как при свертке происходит потеря информации о поведении функций, которая приводит к избыточным вычислениям значений ограничений вне допустимой области. Поэтому актуальной является проблема разработки эффективных алгоритмов решения многоэкстремальных задач при невыпуклых ограничениях, которые обладали бы сходимостью к глобальному оптимуму и не основывались бы на идеях штраф^щ^н^ц^^^ьи«,

БИБЛИОТЕКА }

3 СП.

09 *

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

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

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

Цель работы. В диссертации рассматриваются многоэкстремальные задачи условной оптимизации с невыпуклыми ограничениями. Новый подход к решению таких задач был разработан на кафедре математического обеспечения ЭВМ факультета ВМК ННГУ под руководством Р.Г. Стронгина и получил название индексного метода глобальной оптимизации. Главной целью работы является разработка и исследование подходов к ускорению сходимости методов глобальной условной оптимизации (на примере индексного метода). Ускорение сходимости достигается за счет более полного использования всей доступной информации о свойствах решаемой задачи (например, о времени вычисления функционалов). Основное внимание уделено определению условий сходимости методов, а также численному сравнению эффективности методов путем решения серии тестовых задач.

Научная новизна:

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

• Для индексного метода с ¿-резервированием определены достаточные условия сходимости и оценена скорость сходимости, а также рассмотрена адаптивная схема оценки априори неизвестных параметров резервирования.

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

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

• Для класса задач, в которых время вычисления функционалов зависит от точки проведения итерации, предложена адаптивная схема упорядочивания ограничений по возрастанию трудоемкости.

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

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

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

Личный вклад соискателя. Постановка задач и методы исследования принадлежат руководителю. Соискателю принадлежат разработка

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

Практическая ценность работы. Исследования по теме диссертации выполнялись при поддержке ФЦНТП "Исследования и разработки по приоритетным направлениям развития науки и техники гражданского назначения", направление "Автоматизация проектирования", проект 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), на научных конференциях и семинарах Нижегородского государственного университета.

Публикации. Основное содержание диссертации изложено в работах [1]-[12].

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

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

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

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

Рассматриваются задачи вида

р(х')=Ш1п{^(дс): хе[а,Ь], &/(*)<(), 1 <_/<«} (1)

в предположении, что целевая функция (р (в дальнейшем обозначаемая также £/я+1(*)) и левые части ограничений gJ{x),\<j<m, являются определенными на отрезке [а,Ь] липшицевыми функциями с соответствующими константами 1 <]<т+1. Предполагается также, что каждая функция gJ{x),\<jйm+ \, определена и вычислима лишь в соответствующей подобласти QjCl[a,b], причем

б1=[а,Ь], QJ + l={xeQJ■.gl(x)<0}, 1 <)<т. (2)

Каждая точка х из области поиска [а,Ь] характеризуется числом у= у(х) ограничений, которые выполняются в этой точке, т.е. указанный индекс V определяется условиями

£,(х)£0, 1 V-1, gy(x)>0, и удовлетворяет неравенствам 1 < у= у(х)£гп+ 1.

Введенная классификация точек х из области поиска [а,А] с помощью сопоставления им индексов у=у(х) порождает функцию яx)=gv(x), у=у(х),

1 Стронрин Р Г. Маркин ДЛ Минимизация многоэкстремальных функций при невыпуклых ограничениях// Кибернетика 1986 №4 С 63-69

определенную и вычислимую всюду в [а, 6]. Ее значение в точке х есть либо значение левой части ограничения, нарушенного в этой точке, либо значение минимизируемой функции. Поэтому определение значения f(x), xe[a,b], сводится к последовательному вычислению величин gj(x), 1 <j< v= v(x). Процесс вычислений завершается либо в результате установления неравенства gj(x)>0, либо в результате достижения значения v(x) = m+ 1. Описанная процедура называется испытанием в точке х.

В § 1.2 изложена схема индексного алгоритма глобального поиска. Основная идея алгоритма состоит в редукции условной задачи к безусловной задаче

Дуги функции у/(х) будут липшицевыми с константой £=1 на каждом множестве Qv,\<v<m+ \. Используемые в алгоритме максимальный индекс, значения констант Липшица 1 < у<т+1, и величина являются неизвестными. Однако вместо самих величин можно использовать их адаптивные оценки, получаемые в процессе решения задачи на основании результатов испытаний.

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

Во второй главе исследуются методы ускорения сходимости, основанные на понятии ¿•-резервированного решения. Одним из недостатков

^(*')=min{ у(х): хе [а,Ь])>

где

индексного метода является концентрация точек испытаний не только в окрестности точки х' условного глобального оптимума, но и в окрестностях граничных точек допустимого множества. Этот эффект можно ослабить введением в алгоритм дополнительного вектора параметров еи={£\,■■■,£*,) (вектора "резервов"). В § 2.1 вводится в рассмотрение понятие ¿'-резервированного решения: точка хс называется е-резервированным решением задачи, если выполнено условие

<р(хс)=т\п{<р{х)\ хь[а,Ь]< gJ(x)<,-£J, 1 (3)

где - положительные числа ("резервы" по каждому ограниче-

нию). Вводится в рассмотрение также множество допустимых решений задачи

Хе={х$[а,Ъу. gJ(x)<0, 1 ¿/¿и, <р{х)<,<р(х с)}, (4)

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

В § 2.2 изложен модифицированный индексный алгоритм, учитывающий существование ¿-резервированных решений. Условия сходимости модифицированного алгоритма софрмулированы в виде теоремы2 и доказаны в § 2.3.

Теорема 2.1. Пусть задача (1) имеет решение х' и выполняются следующие условия :

1. каждая область QJ,\<j<m+ \, из (2) представляет собой объединение конечного числа отрезков положительной длины;

2. каждая функция gj,\■¿j<m+ \, допускает литиицево с константой продолжение С/Дх) на весь отрезок [а,Ь], т.е.

С;(х) = £,(*), xeQJ^<j<m+\•

2 Нумерация теорем в автореферате совпадает с нумерацией в тексте диссертации

9

3. компоненты еу вектора резервов Ец, соответствующие активным в точке абсолютного минимума х * ограничениям (т е ограничениям, для которых выполняется условие g ^(х *) = 0), удовлетворяют неравенствам

0<2£„<£ „(/?-£*), (5)

где Р~а есть длина интервала [а, /3] с Qm - 1, содержащего точку х *;

4. компоненты еу вектора резервов Ец, соответствующие неактивным в точке абсолютного минимума х' ограничениям {т.е. ограничениям, для которых выполняется условие gУ(х')<0), удовлетворяют либо неравенствам (5), либо неравенствам

0<£У<1Ы*')|; (6)

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

V, 15 у<т + 1, где г у> 1, 1 < /я + 1, - параметры метода. Тогда:

1. точка х * является предельной точкой последовательности испытаний {**}, порождаемой индексным алгоритмом для задачи (1) при £=0 в условии остановки',

2. любая предельная точка х последовательности {хк} является решением задачи (1);

3. сходимость к предельной точке х является двухсторонней, если х*а и х*Ь.

Если условия (5) и (6) не выполняются для заданного вектора резервов £я, но задача (1) имеет е-резервированное решение, определяемое отношением (3), то:

4. для любой предельной точки х последовательности {хк} справедливы отношения

<р{х)=Ш{<р{хку. gj{xk)<>0, 1 üjüm, *=1,2,...}<«>(*,)

5. любая предельная точка х есть граничная точка множества Хс из (4), если функция <р(х) имеет не более одной точки локального максимума в каждом из изолированных интервалов, составляющих множество Хе;

6. приведенное выше утверждение о двухстороннем характере сходимости остается в силе.

В § 2.4 проведена оценка скорости сходимости модифицированного алгоритма. Для этого введено в рассмотрение понятие плотности последовательности испытаний: отношение числа Naß точек последовательности {**}, лежащих в подынтервале [а,ß]c[a,b], к его длине ß-a

Paß=Napl(ß-a) называется плотностью последовательности {.**} в указанном подынтервале.

Доказано, что при выполнении условий сходимости алгоритма плотность последовательности испытаний в интервале [а,ß]czQv, 1 < v<m, (т.е. в интервале, не содержащем глобального минимума задачи), ограничена. А именно, выполняется неравенство

Paß<r?Lv/(rv-l)(Sv+£v).

Здесь г v> 1 - параметры алгоритма, L v - значение константы Липшица для V—й функции ограничения, gv(x)>8v>0 - оценка значения нарушенного v-ro ограничения на интервале [ а, ß], ev~ координаты вектора резервов.

Далее в § 2.5 для адаптивного оценивания заранее неизвестных параметров резервирования предложены схемы, которые вытекают из

условий сходимости метода. При этом выбор координат вектора резервов = ( г,,..., £т) заключаются в следующем:

где цу - текущая оценка константы Липшица для у-й функции, е -точность, задаваемая в условии остановки метода, <7> 1 - параметр, который можно интерпретировать как априорную оценку того, во сколько раз длина интервала, содержащего решение задачи х', превышает заданную точность е.

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

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

(р(х') = т\п {<р{х)-. хе[а,Ь], 8](х)<Ъ, 1 <./<;«} (7)

в предположении, что целевая функция (р и левые части ограничений %,,\<}<т, являются определенными на отрезке [а,Ь] липшицевыми функциями с соответствующими константами ¿,,1<у'</и+1. Предполагается, что ограничение, имеющее номер<у'</я, выполняется во всех точках области

д^{хе[а,Ь]: е^х)<0}, \<]<т, (8)

при этом допустимая область Q исходной задачи определяется условием е=<2,п...пвт. (9)

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

12

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

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

Для алгоритма с адаптивным порядком проверок в § 3.3 доказана теорема о сходимости.

Теорема 3.1. Пусть задача (7) имеет решение х* и выполняются следующие условия:

1. каждая область 1 <)<т, из (8) представляет собой объединение конечного числа отрезков, имеющих положительную длину,

2. каждая функция g^(x), 1 <у<т + 1, удовлетворяет условию Липшица с соответствующей константой LJ;

3. компоненты sv вектора резервов er удовлетворяют неравенствам

Q<2ev<Ly(P-a),

где Р~а есть длина интервала [а, Д], принадлежащего допустимой области Q из (9) и содержащего точкух' из (7);

4. при достаточно больших значениях к оценки констант Липшица fivудовлетворяют неравенствам

г vHv>2Lv, \£v<,m+\, где г „> 1, 1 < v< m + 1, - параметры метода.

Тогда:

1. точка х* является предельной точкой последовательности {**}, порождаемой описанным методом с адаптивным порядком проверки ограничений для задачи (7) при £= О в условии остановки;

2. любая предельная точка х последовательности {**} является решением задачи (7);

3. сходимость к предельной точке х является двухсторонней, если х*а их*Ъ.

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

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

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

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

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

В § 4.3 приведены достаточные условия сходимости алгоритма. Доказано, что данные условия эквивалентны условиям сходимости из §3.3.

В § 4.4 описан класс тестовых задач условной глобальной оптимизации, для которого характерно значительное время вычисления функционалов. Результаты сравнения стандартного индексного алгоритма и алгоритма с упорядочиванием ограничений по трудоемкости приведены в § 4.5. Здесь же рассмотрен вопрос об адаптивных оценках константы Липшица для данного класса задач.

В пятой главе изложены подходы к ускорению сходимости при решении многомерных задач. Для этого в § 5.1 описан механизм редукции многомерной задачи к эквивалентной ей одномерной задаче с помощью кривых, заполняющих пространство (разверток). Известно, что отрезок [0,1] можно непрерывно и однозначно отобразить на N-мерный гиперкуб О, т.е.

(Я*): 0<х<1 } = {>>€/?": -2''<у,<2-\ 1 </<ЛГ}=Я. Такое отображение у(х), называемое разверткой Пеано, позволяет свести многомерную задачу условной минимизации в области У к одномерной задаче условной минимизации на отрезке [0,1], поскольку

<р(у')=тхп{<р{у): уей, I<у</я} = (10)

=ш!п{?»(Я*)): *е[0,1], 8;(у(х))<0, 1 <]<т).

Здесь же введено (для многомерного случая) понятие е-резервированного решения задачи

<р(у,) = пип{рО>): уеО, 1^<т}, (11)

а также множества

¥е={уеО: £,О>)<0, 1 <]<т, <р{у)<,<р(уе)} (12)

всех допустимых точек задачи, которые не хуже (по значению целевой функции <р), чем ¿-резервированное решение.

Конкретные способы построения разверток - кусочно-линейная и множественная развертки - приведены в § 5.2. Показаны преимущества множественной развертки по сравнению с кусочно-линейной разверткой.

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

Теорема 5.1. Пусть выполнены следующие условия:

1. Задача (10) имеете-резервированное решение у е из (11).

2. каждая функция gJ(y),l¿j<m+l, допускает липшицево с константой Ь, продолжение О ¡{у) на всю допустимую область Д т.е.

0^у{х)) = 0^у{х)), 1<]<т+\,

где Qj область выполнимости ]-го ограничения и у(х) - развертка Пеано.

3. параметры метода е}, 1 <]<т + 1, имеют значения соответствующих координат вектора резервов',

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

¿у, \<у<т + \, где г У>1, 1 < у<т + 1, - параметры метода.

Тогда любая предельная точка у последовательности испытаний {ук} = {у(х1)}, порождаемой индексным алгоритмом для задачи (10), принадлежит множеству Ус из (12) и удовлетворяет условиям <р{у)=Ш{<р{ук)'^]{ук)<а,\<]<т,к=\,2,...}<<р(ус).

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

В заключении сформулированы основные результаты диссертационной работы.

Основные результаты работы

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

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

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

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

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

1. Стронгин Р.Г., Баркалов К.А. О сходимости индексного алгоритма в задачах условной оптимизации с ¿-резервированными решениями// Математические вопросы кибернетики. М.: Наука, 1999. С. 273-288.

2. Стронгин Р.Г., Баркалов К.А. Индексный метод условной глобальной оптимизации с адаптивными резервами// Проблемы теоретической кибернетики: тез. докл. XII международн. конф. М.: изд-во механико-математического факультета МГУ, 1999. С. 220.

3. Стронгин Р.Г, Баркалов К.А О сходимости индексного алгоритма в задачах условной глобальной оптимизации с ¿-резервированными решениями// Вестник ННГУ. Математическое моделирование и оптимальное управление, Нижний Новгород: изд-во Нижегородского гос. ун-та, 1999. вып. 2. С. 233.

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

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

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

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

8. Баркалов К.А. Учет зависимости времени вычисления функционалов от точки итерации в задачах условной глобальной оптимизации// Математика и кибернетика 2003. Сборник научных статей юбилейной научно-технической конференции факультета ВМК ННГУ и НИИ ПМК. Нижний Новгород, издательство Нижегородского госуниверситета, 2003. С. 31-33.

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

10. Barkalov К A. A global optimization technique with an adaptive order of checking for constraints: application to multidimensional problems// VI International congress on mathematical modeling: Nizhny Novgorod, University of Nizhny Novgorod, 2004. P. 68.

11. Markine V.L., Barkalov K.A., Gergel VP. An Optimum Design Procedure Based On Multipoint Approximations And A Global Optimization Method. 6th World Congresses of Structural and Multidisciplinary Optimization, Rio de Janeiro, Brazil, 2005. P. 12.

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

Подписано в печать 05.04.2006. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1. Зак. 611. Тир. 100.

Типография Нижегородского госуниверситета. Лиц. ПД№ 18-0099 от 04.05.2001. 603000, Н. Новгород, ул. Б. Покровская, 37.

í

s

V,

л ï

¿oo6£

гш

»-8489

ВВЕДЕНИЕ.

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

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