Содержание к диссертации
Введение
1. Задачи условной глобальной оптимизации 14
1.1. Постановка задачи условной глобальной оптимизации 14
1.2. Индексный алгоритм решения одномерных задач условной птимизации с невыпуклыми ограничениями 18
1.3. Многомерные задачи и методы их сведения к одномерным задачам 22
2. Методы ускорения сходимости, основанные на понятии резервированного решения 25
2.1. Понятие є-резервированпого решения 25
2.2. Индексный алгоритм, учитывающий существование є-резервированньіх решений 28
2.3. Достаточные условия сходимост модифицированного индексного алгоритма 31
2.4. Оценка скорости сходимости индексного алгоритма 43
2.5. Адаптивное оценивание резервов 44
2.6. Вычислительные эксперименты для оценки ускорения, обеспечиваемого адаптивными оценками e-pe3epbob 45
3. Ускорение сходимости за счет введения переменного порядка проверки ограничений 49
3.1. Порядок проверки ограничений и вычислительныезатраты 49
3.2. Алгоритм с адаптивным порядком проверки ограничений 51
3.3. Достаточные условия сходимости метода с адаптивным порядком проверок 57
3.4. Генераторы тестовых задач условной оптимизации с невыпуклыми ограничениями 65
3.5. Адаптивные оценки константы липшица при переменном порядке проверки ограничений .68
3.6. Оценка ускорения, обеспечиваемого введением переменного порядка проверки ограничений, путем численного эксперимента на больших выборках задач 70
4. Ускорение сходимости за счет учета зависимости времени вычисления функционалов от точки итерации 74
4.1. Вычислительные затраты в задачах с разным временем вычисления функционалов 74
4.2. Алгоритм, учитывающий различное время вычисления ограничений 75
4.3. Достаточные условия сходимости алгоритма 76
4.4. Генераторы тестовых задач 77
4.5. Экспериментальная оценка ускорения, обеспечиваемого учетом различного времени вычисления ограничений 81
5. Вопросы ускорения решения многомерных задач 84
5.1. Редукция многомерных задач условной глобальной оптимизации 84
5.2. Способы построения разверток, кусочно-линейная развертка. 86
5.3. Использование множественных отображений 90
5.4. Индексный метод для решения многомерных задач условной глобальной оптимизации 93
5.5. Применение индексного метода к многомерным задачам 103
Заключение 112
Литература
- Индексный алгоритм решения одномерных задач условной птимизации с невыпуклыми ограничениями
- Достаточные условия сходимост модифицированного индексного алгоритма
- Алгоритм с адаптивным порядком проверки ограничений
- Алгоритм, учитывающий различное время вычисления ограничений
Введение к работе
Во всех областях своей целенаправленной деятельности перед человеком возникает проблема выбора наилучшего решения из множества всех возможных. Примерами могут служить экономика (планирование и управление экономическими объектами), техника (выбор наилучшего проекта или оптимальной конструкции), военное дело (ведение боевых действий и снабжение войск). На ранних этапах развития общества для принятия наилучшего решения достаточно было интуиции и опыта. Но уже в конце 19 - начале 20 веков стало ясно, что одной интуиции недостаточно. Человек просто физически не в состоянии осмыслить тот огромный объем информации, который является необходимым для совершения правильного выбора. Поэтому неизбежным стало применение для выбора решений математических методов.
К числу наиболее распространенных моделей рационального выбора относятся математические задачи оптимизации (максимизации или минимизации) некоторого функционала при ограничениях типа неравенств. При этом выполнение ограничений для некоторого вектора параметров, определяющего решение, интерпретируется как допустимость этого решения, т.е. как возможность его реализации при имеющихся ресурсах. Теорию и методы отыскания минимумов функций многих переменных при наличии дополнительных ограничений на эти переменные обычно рассматривают как отдельную дисциплину - математическое программирование.
Поскольку искомая точка х совпадает с одной из локально-оптимальных точек X;, 1 і п, то можно попытаться найти эту точку с помощью релаксационных методов (таких как метод проекции градиента, метод условного градиента, метод возможных направлений и др.), являющихся обобщениями методов безусловной локальной оптимизации на случай наличия ограничений (см. [14], [27], [32], [35]). При этом нужно либо иметь начальную точку из области притяжения точки х (т.е. из области, где х есть единственная локально-оптимальная точка), либо найти все локально-оптимальные точки х , \ і п, для их последующего сравнения. Трудность, связанная с таким подходом, состоит в том, что ни область притяжения точки х , ни число п локально-оптимальных точек обычно не известны.
При этом помимо коэффициента Я, могут вводиться также весовые коэффициенты 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].
В заключение выражаю глубокую признательность моему научному руководителю Роману Григорьевичу Стронгину за внимание и поддержку в работе.
Индексный алгоритм решения одномерных задач условной птимизации с невыпуклыми ограничениями
Алгоритм. Первое испытание осуществляется в произвольной внутренней точке х1 є(а,Ь). Выбор точки х + , к \, любого последующего испытания определяется следующими правилами.
Правило 1. Перенумеровать точки х1,...,хк предшествующих испытаний нижними индексами в порядке увеличения значений координаты, т.е. а=х0 Х] ... Хі ... Хк Хк+ \ = b, (1.2.1) и сопоставить им значения z,=g ,,( ,), v=v(x(), 1 / , из (1.1.8), вычисленные в этих точках; точки х0 = а и Xk + \ = b введены дополнительно (значения z0 и zk+i не определены) для удобства последующих обозначений,
Правило 2. Провести классификацию номеров і,\ і к, точек из ряда (1.2.1) по числу ограничений задачи, выполняющихся в этих точках, путем построения множеств Iy={i: \ i k, v v(Xi)}, l v m + l. содержащих номера всех точек Xi,l i k, имеющих индексы, равные одному и тому же значению v. Граничные точкиХо-а и х +1 = 6 интерпретируются как имеющие нулевые индексы, и им сопоставляется дополнительное множество 7Q= {0 ,к+ 1}.
Правило 3. Построить объединения SV=IQ J...UIV-I, \ v m + \, содержащие номера всех точек из (1.2.1), имеющих индексы меньшие чем V, и Ty=Iy+lu...vIm + luIin + 2, l v m + l, содержащие номера всех точек из (1.2.1), имеющих индексы большие чем v(Im + 2 = 0). Пр а в ил о 4. Вычислить текущие нижние границы ply = max Z- — z. J i-Xj , i,jelv,i j\ (1.2.2) для неизвестных констант Липшица Lv функций gv,\ v m + \. Если множество I у содержит менее двух элементов или если pv ИЗ (1.2.2) оказывается равным нулю, то принять pv= 1. Из (1.2.2) следует, что оценки pv являются неубывающими, начиная с момента, когда (1.2.2) порождает первое положительное значение р у.
Правило 5. Для всех непустых множеств Iv, 1 v m+1, определить величины jmin{zi:ieIv} Ty=0, Z = lO,7v 0. (1-23) Т.е. zv = 0, если существуют точки ХІ, 1 i k, имеющие индекс, больший V. Правило б. Для каждого интервала (д:(„і ,д:,), \ i k+l, вычислить характеристику R (і), где R(i)=Ai+{\ Z2 2 -2 + 2"-2 :\ /-1,/6/,, (1.2.4) R(i) = 2Ai-4(Zi Zv\ ieIy,i-\eSv, (1.2.5) rvMv Д(0 = 2Д; -4 -1 Zv), z-іє/,,/є.?,, (1.2.6) Л,=д:;-л:/-і. (1.2.7)
Величины r y 1, 1 v m+1, являются параметрами алгоритма. Подходящий выбор значений rv позволяет использовать произведение rvfiv как оценку константы ЛипшицаLVi 1 v m + l. Правило 7. Определить интервал (х,_і,хt), которому соответствует максимальная характеристика R(t) = max{R(i): 1 / +1}. (1.2.8) Правило 8. Провести очередное испытание в серединной точке интервала (xt_i ,х(), если индексы его концевых точек не совпадают, т.е. i + 1 xt +xt , , . (1.2.9) В противном случае провести испытание в точке .t+l_ -/ "г- /_ ( f_] X = , v=v(xt.l)=v(xi). (1.2.10) 2 2rvjiv Описанные правила можно дополнить условием остановки, прекращающим испытания, если xt-xt-\ s (1,2.11) где t из (1.2.8) и 0 есть заданная точность. Теорема 1.1. (достаточные условия сходимости индексного алгоритма)
Пусть для значения Миз (1,1.6) справедливо следующее . 1. каждая область Qj, \ j M, из (1.1.2) представляет собой объединение конечного числа отрезков положительной длины; 2. каждая функция gj, 1 j M, допускает липшш{ево с константой Lj продолжение Gj(x) на весь отрезок [a ,b], т.е. GJ(X) = GJ(X), xeQj,\ j M; 3. точка х есть решение задачи (1.1.5); 4. начиная с некоторого шага, для параметров метода г v величин fivu констант Липшица L v на каждой итерации справедливы неравенства rvpv 2Lv, \ v M.
Тогда: 1. х есть предельная точка последовательности {хк}, порождаемой индексным алгоритмом при точности є=0 в условии остановки; если х Фа их ФЬ, то сходимость к точкех является двусторонней; 2. любая другая предельная точка х последовательности {х } также является решением задачи (1.1.5). 3. индексы всех точек любой сходящейся подпоследовательности xq x, q = q{kp), р-1,2,..., последовательности {х } при достаточно больших значениях р не превышают индекса предельной точки, т.е.
Достаточные условия сходимост модифицированного индексного алгоритма
Теорема 2Л. Пусть задача (2.1.1) имеет решение х и выполняются следующие условия: 1. каждая область Qj,\ j m+l, из (1.1.2) представляет собой объединение конечного числа отрезков полоэюительной длины , 2. каждая функция gj, 1 j m + 1, допускает липшицево с константой Lj продолжение Gj(x) на весь отрезок [а ,6], т.е. Gj(x) = Gj(x), xzQJt\ j m + \; (2.3.1) 3. компоненты sv вектора резервов SR, соответствующие актив ным в точке абсолютного минимума х ограничениям (т.е. ограничени ям, для которых выполняется условие g v(x ) = 0), удовлетворяют нера венствам 0 2ev Lv(/3-a), (2.3.2) где (5-а есть длина интервала [а, /?] cz Qm + \, содержащего точку х ; 4. компоненты ev вектора резервов sR, соответствующие неактив ным в точке абсолютного минимума х х ограничениям (т.е. ограниче ниям, для которых выполняется условие g v(x ) 0), удовлетворяют ли бо неравенствам (2.3.2), либо неравенствам 0 ev \gv(xm)\; (2.3.3) 5. если некоторым точкам из ряда (2,2.1) соответствуют значения индекса, равные v, то при достаточно больших значениях к для соот ветствующей величины fiv из (2.2.2) справедливо неравенство rvpv 2Ly, \ v m + \. (2.3.4) Тогда:
1. точка х является предельной точкой последовательности точек испытаний {х }, порождаемой индексным алгоритмом для задачи (2.1.1), при =0 в условии остановки (2.2.11); 2. любая предельная точка х последовательности {х } является решением задачи (2.1.1);
3. сходимость к предельной точке х является двухсторонней, если х а и х Ь. Если условия (2.3.2) и (2.3.3) не выполняются для заданного вектора резервов 6R, но задача (2.1.1) имеет є-резервированное решение, определяемое отношением (2.1.3), то:
4. для любой предельной точки х последовательности {х } спра ведливы отношения p(x) = inf{ p(xk): gj{xk) 0, \ j m, k=\ ,2,... } р(хє) (2.3.5)
5. любая предельная точка х есть граничная точка множества Хє из (2.1.4), если функция р(х) иліеет не более одной точки локального максимума в каждом из изолированных интервалов, составляющих мноэ/сество Х;
6. приведенное выше утвероісдение о двухстороннем характере сходимости остается в силе.
Прежде чем приступить к доказательству теоремы, сформулируем и докажем несколько вспомогательных утверждений.
Лемма 2.1. (о последовательности стягивающихся интервалов) Пусть выполнены условия теоремы 2.1. Тогда для каждой предельной точки х последовательности испытаний {х } существует бесконечная последовательность интервалов {( ,_,, ,): t=t(qp)} = 1,2,..., (2.3.6) удовлетворяющих условиям СО = Г)[ м ] (2.3.7) р-\ НтД,=0, (Z3.8) R(t(qp)) 0, =1,2,..., (2.3.9) \im R(t(qp)) = 0, (2.3.10) где qi q2 .,.\ R(t), At и t соответственно из (2.2.4)-(2.2.6), (2.2.7) и (2.2.8). Доказательство (леммы 2.1).
Поскольку х является предельной точкой, должна существовать последовательность номеров испытаний ql,q2 ..., удовлетворяющая условиям xq+l, xefrt-uXt], /=/(g), qe{qp}, /7=1,2,.... (2.3.11)
Эти условия отражают то обстоятельство, что точка (q+1)-го испытания попала в интервал [х t-\ ,xt], содержащий точку х на шаге q, т.е. t = t(q). Из (2.2.9), (2.2.10), (2.2.2), (2.3.11) следует, что max {xt xq + l, xq + x-xt-\ } уЛ(, (2.3.12) где y = (r+\)llr \, r vain{r v\ 1 v m+\ } 1. При этом свойство (2.3.8) является следствием неравенства (2.3.12).
На каждом шаге к 1 существует интервал ( ,_і ,х,): i=i(k), на одном из концов которого достигается значение z a (см. комментарий к пятому правилу алгоритма). Если при этом \{ХІ-\) \(ХІ) ТО согласно (2.2.5), (2.2.6) R(i)-2Ai 0. В случае, когда Цд:,-_і)= Цдг,-) = «, из (2.2.2) следует оценка которая в сочетании с (2.2.4) дает неравенство Л(/) = ( 1-г-1)Д, 0. Таким образом, на любом шаге поиска к \ существует интервал, имеющий строго положительную характеристику. Отсюда, с учетом (2.2.8), получаем, что интервалы из системы (2.3.6) также должны иметь положительные характеристики, ибо они подвергаются дроблению попадающими в них точками испытаний; т.е. условия (2.3.9) справедливы.
Алгоритм с адаптивным порядком проверки ограничений
Для удобства изложения материала сначала опишем индексный алгоритм с -резервированием, отличающийся от изложенного в п.2.2 точкой проведения первого испытания.
Алгоритм (с фиксированным порядком проверок). Первые два испытания осуществляются в граничных точкахх = я их1 = Ь интервала [а,Ь], представляющего собой область поиска. Выбор точки х +1, k \, любого последующего испытания определяется следующими правилами.
Правило 1. Перенумеровать точки х,...,хк предшествующих испытаний нижними индексами в порядке увеличения значений координаты, т.е. a=x0 ... Xj ... Xk = b, (3.2.1) и сопоставить им значения zt=g v(Xi), v-v{xi), 0 і к, из (3.1.6) вычисленные в этих точках.
Правило 2, Для каждого целого числа v, \ v m + \, определить соответствующее ему множество І у нижних индексов тех точек из (3.2.1), в которых вычислялись значения функций gv, т.е. /„={ : 0 i k, v v(Xi)}, \ v m+\. (3.2.2)
Правило 3. Вычислить текущие нижние границы //,,=max{ \gv(Xi)-gv(Xj) \/{xj-Xj): ijely, i j] (3.2.3) для неизвестных констант L v из (3.1.2), 1 v m+1. Если множество Iv содержит менее двух элементов или, если значение fly, определенное из (3.2.3), оказывается равным нулю, то принять /JV= 1. Заметим, что оценки }ЛУ, порождаемые выражением (3.2.3), являются неубывающими и определяются уже вычисленными (в ходе проведенных испытаний) значениями функционалов. Правило 4. Для всех непустых множеств /,,, 1 v m, определить значения z ( v) = min{gv(Xi): iely} (3.2.4) и вычислить оценки z"(v), z (v) О, zv4 , (3.2.5) где вектор =( 1,-., ), (3.2.6) имеющий положительные координаты, называется вектором резервов. В случае, когда 1т + \Ф0 (в этом случае все множества /v, 1 v m, также являются непустыми) оценка z m+] определяется выражением z m+l=z {m + \). (3.2.7) Правило 5. Для каждого интервала (xi-i,xt), \ i k, вычислить характеристику R(i), где Д(0=Л,- + {Z\ \-f -2(Zi + Z 4 "2z;), V = V(A:M) = V( ), (3.2.8) /?0 2A,.-4(Z " ), К м) К /)-и, (3.2.9) rvMv R(i) = 2Д, -4(ZM"H И = у( м) ФІ), (3.2,10) Д,= ,-Л,_І, 1 / Аг. (3.2.11) Величины rv \t \ v m + \, (3.2.12) являются параметрами алгоритма. Подходящий выбор их значений позволяет использовать произведения rvjuv как оценки неизвестных значений констант Липшица из (3.1.2). Это обстоятельство будет более подробно обсуждаться при рассмотрении теории сходимости. Правило 6. Определить интервал (xt-i ,xt), которому соответствует максимальная характеристика R(t) = max{R(i): \ i k}. (3.2.13) Правило 7. Провести очередное испытание в серединной точке интервала (я,-!, ,), если индексы его концевых точек не совпадают, т.е. jt+i_ f+ ,-i Wr ч , ч (3.2.14) В противном случае провести испытание в точке ,к+ 1 _ " " - 7-l Z( /-1 v=v(xt-i)=v(xt). (3.2.15) 2 2rv//v
Описанные правила можно дополнить условием остановки, прекращающим испытания, если xt-Xt \ e, (3.2.16) где t из (3.2.13) и 0 есть заданная точность.
Перейдем теперь к обобщению описанной схемы на случай, когда порядок проверки ограничений не является фиксированным. При этом будем ссылаться на рассмотренный исходный алгоритм как на метод с фиксированным порядком проверок (МФ1111).
Алгоритм, предлагаемый ниже, допускает изменение порядка проверки ограничений в процессе решения задачи (3.1.1). Указанные изменения направлены на то, чтобы при очередном испытании сначала анализировалось ограничение, нарушенное на конце интервала, содержащего точку очередной итерации. Как уже отмечалось выше, такой подход может уменьшить число проверок в новой точке, поскольку невыполнение указанного ограничения в некоторой окрестности уже обнаруженного нарушения может быть весьма вероятным. При этом возникает потребность как в новых правилах сопоставления индексов точкам из (3.2.1) (напомним, что эти индексы определяют использование выражений (3.2.8)-(3.2.10) для подсчета характеристик), так и в специальной процедуре, формирующей порядок проверки ограничений в точке очередного испытания. Заметим, что формирование такого порядка несущественно для интервалов, концы которых принадлежат допустимому множеству Q из (3.1.4), ибо в таких интервалах вероятна необходимость проверки всех ограничений.
Алгоритм, учитывающий различное время вычисления ограничений
Теорема 4.1. Пусть задача (3.1.1) имеет решение х и выполняются следующие условия: {.каждая область Qj, \ j m, из (3.1.3) представляет собой объединение конечного числа отрезков, имеющих положительную длину; 2.каждая функция gj(x), \ j m + \, удовлетворяет условию Липшица (3Л.2) с соответствующей константой Lj-; 3. компоненты EV вектора резервов SR из (3.2.6) удовлетворяют неравенствам 0 2ey L,(fi-a), (4.3.1) где J3- а есть длина интервала [a ,j3], принадлежащего допустимой области Q из (3.1.4) и содержащего точку х из (3.1.1); 4. при достаточно больших значениях к величины fiv из (3.2.3), со ответствующие непустым множествам Iv, удовлетворяют неравен ствам rvpiv 2Lv, l v m + l, (4.3.2) где г у из (3.2.12). Тогда . І.точка х является предельной точкой последовательности {xk}, порождаемой описанным методом с адаптивным порядком проверки ограничений для задачи (3.1.1) при є=0 в условии остановки (3.2.16); 2, любая предельная точка х последовательности {х } является решением задачи (3.1.1); 3. сходимость к предельной точке х является двухсторонней, если х а и ХФЬ. Доказательство.
Теорема 4.1 доказывается аналогично теореме 3.1 из 3.3. В самом деле, алгоритмы, изложенные в 3.2 и 4.2, различаются лишь способом определения порядка проверки ограничений. Однако при доказательстве теоремы 3.1 не фиксировался какой-либо конкретный способ проверки ограничений. При доказательстве использовалось лишь то свойство задачи (3.1.1), что допустимое множество Q является пересечением допустимых множеств Qj, 1 j m, каждого ограничения и не зависит от порядка проверки ограничений. В силу этого доказательство теоремы 3.1 распространяется и на теорему 4.1.
Как уже было отмечено в 3.4, генераторы многоэкстремальных задач в литературе не рассматривались. В связи с этим в настоящей работе предлагается схема построения генератор G, порождающего задачи с т ограничениями вида, на основе заданного случайного механизма F, дающего функции/(х), хе[а ,Ь], Полученный генератор G позволяет управлять мерой допустимой области (усложняя или упрощая задачи путем уменьшения или увеличения этой меры). При этом класс функций F сконструирован таким образом, что время вычисления значения функции в точке х є [а , Ъ ] существенным образом зависит от точки х.
В качестве генератора тестовых задач можно использовать следующую схему: 1. С помощью заданного механизма F независимо генерируются т+1 функция/, (Л), xe[a,b], l j m+\. 2. Вычисляется минимакс A = min max f. (х) айхйЬ \ j m J и вводятся левые части ограничений gj(x)=fj(x)-A-S, \ j m, (4.4.1) которым при 5 0 соответствует (по построению) непустая допустимая область Q. При этом увеличение значения параметра S позволяет расширять допустимую область. 3. Функции (4.4.1) и целевая функция p{x)=fm+j{x) задают за дачу вида (4.1.1), заведомо имеющую решение.
В случаях, когда необходимо указать используемые при запуске генератора параметры т и S, будем использовать обозначение G(m,S).
В численных экспериментах, результаты которых описываются ниже, использовался класс функций, задаваемый следующим выражением: Я )= j ff/2 Г 14 YMi sin(2 (« x)t) + Bf cos(2m(a - x)t)) -л/2 Л, х е [ОД], (4.4.2) где значения Aj,Bit 1 / 14, независимо и равномерно распределены в интервале [-1,1]) а параметра а - в интервале [0,1]. Интеграл (4.4.2) составлен таким образом, что в окрестности а подынтегральная функция будет пологой, а вне этой окрестности - резко колебательной. Поэтому если интеграла (4.4.2) вычислять численно с переменным шагом интегрирования, то в окрестности точки х = а значение интеграла будет вы числено гораздо быстрее, чем вне этой окрестности. Метод интегрирования с переменным шагом состоит в следующем (см. [8], [10]).
