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

• Автор: Баркалов, Константин Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Нижний Новгород
• Количество страниц: 120 с. : ил.

1. ЗАДАЧИ УСЛОВНОЙ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ
1.1. Постановка задачи условной глобальной оптимизации
1.2. Индексный алгоритм решения одномерных задач условной оптимизации с
НЕВЫПУКЛЫМИ ОГРАНИЧЕНИЯМИ
1.3. Многомерные задачи и методы их сведения к одномерным задачам
2. МЕТОДЫ УСКОРЕНИЯ СХОДИМОСТИ, ОСНОВАННЫЕ НА ПОНЯТИИ еРЕЗЕРВИРОВАННОГО РЕШЕНИЯ
2.1. Понятие ь-резервиров анного реше! шя
2.2. Индексный алгоритм, учитывающий существование е-резервированных решений
2.3. ДОСТАТОЧ11ЫЕ УСЛОВИЯ СХОДИМОСТ МОДИФИЦИРОВАННОГО ИНДЕКСНОГО АЛГОРИТМА
2.4. Оценка скорости сходимости индексного алгоритма
2.5. Адаптивное оценивание резервов
2.6. Вычислительные эксперименты для оценки ускорения, обеспечиваемого адаптивными
ОЦЕ11КАМИ Е-РЕЗЕРВОВ
3. УСКОРЕНИЕ СХОДИМОСТИ ЗА СЧЕТ ВВЕДЕНИЯ ПЕРЕМЕННОГО ПОРЯДКА
ПРОВЕРКИ ОГРАНИЧЕНИЙ
3.1. ПОРЯДОК ПРОВЕРКИ ограничений и вычислительныезатраты
3.2. АЛГОРИТМ С АДАПТИВНЫМ ПОРЯДКОМ ПРОВЕРКИ ОГРАНИЧЕНИЙ
3.3. ДОСТАТОЧ11ЫЕ УСЛОВИЯ СХОДИМОСТИ МЕТОДА С АДАПТИВНЫМ ПОРЯДКОМ ПРОВЕРОК
3.4. ГЕНЕРАТОРЫ ТЕСТОВЫХ ЗАДАЧ УСЛОВНОЙ ОПТИМИЗАЦИИ С НЕВЫПУКЛЫМИ ОГРАНИЧЕНИЯМИ
3.5. Адаптивные оценки константы Липшица при переменном порядке проверки ограничений
3.6. Оценка ускорения, обеспечиваемого введением переменного порядка проверки
ограничений, путем численного эксперимента па больших выборках задач
4. УСКОРЕНИЕ СХОДИМОСТИ ЗА СЧЕТ УЧЕТА ЗАВИСИМОСТИ ВРЕМЕНИ
ВЫЧИСЛЕНИЯ ФУНКЦИОНАЛОВ ОТ ТОЧКИ ИТЕРАЦИИ
4.1. Вычислительные затраты в задачах с раз! 1ым временем вычисления функцио! !алов
4.2. Алгоритм, учитывающий различное время вычисления ограничений
4.3. Достаточные условия сходимости алгоритма
4.4. Генераторы тестовых задач
4.5. Экспериментальная оценка ускорения, обеспечиваемого учетом различного времени
вычисления ограничений
5. ВОПРОСЫ УСКОРЕНИЯ РЕШЕНИЯ МНОГОМЕРНЫХ ЗАДАЧ
5.1. Редукция многомерных задач условной глобалыюй оптимизации
5.2. Способы построения разверток. Кусочно-линейная развертка
5.3. Использование множественных отображений
5.4. Индексный метод для решения многомерных задач условной глобальной оптимизации
5.5. Применение индексного метода к многомерным задачам
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

Во всех областях своей целенаправленной деятельности перед человеком возникает проблема выбора наилучшего решения из множества всех возможных. Примерами могут служить экономика (планирование и управление экономическими объектами), техника (выбор наилучшего проекта или оптимальной конструкции), военное дело (ведение боевых действий и снабжение войск). На ранних этапах развития общества для принятия наилучшего решения достаточно было интуиции и опыта. Но уже в конце 19 - начале 20 веков стало ясно, что одной интуиции недостаточно. Человек просто физически не в состоянии осмыслить тот огромный объем информации, который является необходимым для совершения правильного выбора. Поэтому неизбежным стало применение для выбора решений математических методов.
К числу наиболее распространенных моделей рационального выбора относятся математические задачи оптимизации (максимизации или минимизации) некоторого функционала при ограничениях типа неравенств. При этом выполнение ограничений для некоторого вектора параметров, определяющего решение, интерпретируется как допустимость этого решения, т.е. как возможность его реализации при имеющихся ресурсах. Теорию и методы отыскания минимумов функций многих переменных при наличии дополнительных ограничений на эти переменные обычно рассматривают как отдельную дисциплину - математическое программирование.
В общем виде задачу математического программирования можно сформулировать следующим образом. Пусть <р(х), g;•(x)<0, <]<т, есть действительные функции, определенные на множестве X Димерного евклидова пространства , и пусть точка х* удовлетворяет условию
(р(х* ) = тп {<р{х) х&Х, gj{x)<0, 1 <у Точка из х* (0.1) обычно называется глобально-оптимальной точкой или глобалыю-оптимальнымрешением. При этом функцию <р(х) называют функцией цели, или целевой функцией, а функции £у(х)<0, 1 <у < т, — ограничениями задачи.
Область X называют областью поиска и обычно описывают как некоторый гиперинтервал из//-мерного евклидова пространства
Х={х £ ^: О,•<*;<£;, 1 ()={х: хеХ, gJ(x)<0, 1 <у всех таких точек называют допустимой областью.
Важный в прикладном отношении подкласс задач вида (0.1) характеризуется тем, что все функционалы, входящие в определение задачи, заданы некоторыми (программно реализуемыми) алгоритмами вычисления значений <р(х), gj{x), 1 <]<т, в точках области поиска X. При этом решение задачи (0.1) сводится к построению оценки xteQ, отвечающей некоторому понятию близости к точке х* (например, чтобы ||х* -х*||<г: или |^(х*)-р(х*)|<£, где £>0 есть заданная точность) на
основе некоторого числа к значений функционалов задачи, вычисленных в точках области X.
Частным случаем задачи (0.1) при отсутствии ограничений, т.е. когда т = 0, является задача безусловной оптимизации. Решению таких задач в настоящее время посвящена обширная литература (см., например, [9], [13], [24], [34], [39], [50], [58]-[60]).
Случай, когда все функционалы задачи обладают свойством линейности, достаточно исследован. Соответствующие результаты в этой области, называемой линейным программированием, опубликованы во многих монографиях и учебниках (см., например, [11], [14], [26]-[28],
При этом выявление первого нарушенного ограничения прерывает испытание в точке х.
В случае, когда точка х допустима, т.е. когда
хе<2, (3.1.5)
испытание включает вычисление значений всех функционалов задачи. При этом значение индекса принимается равным величине у=т +1.
В связи с изложенным, пару
у=у(х), z=gv(x), (3.1.6)
где индекс к заведомо лежит в границах 1 < у<т +1, будем называть результатом испытания в точке х.
Очевидно, что вычислительные затраты на проведение испытания могут существенным образом зависеть от порядка, в котором вычисляются функционалы задачи. Если предположить, что время вычисления любого функционала задачи не зависит от точки проведения итерации, то затраты на проведение испытания в точке х будут тем меньше, чем меньше функционалов будет вычислено в этой точке.
Для многих прикладных задач естественно допустить, что ограничение, нарушенное в некоторой точке области поиска, не будет выполняться и в некоторой окрестности этой точки. В таком случае может оказаться полезным начинать испытания в точках этой окрестности с анализа выполнимости указанного ограничения. В свете сказанного представляется целесообразным построить алгоритм глобальной оптимизации, допускающий изменение порядка проверки ограничений с учетом информации, получаемой в ходе поиска решения. Формирование порядка проверки будет ориентировано на то, чтобы нарушенное в точке итерации ограничение было выявлено возможно раньше.