Диагональные алгоритмы решения задач липшицевой глобальной оптимизации

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

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

ГЛАВА 1. Безусловная липшицева глобальная оптимизация

1.1. Постановка задачи

1.2. Способы оценивания константы Липшица.

1.3. Подходы к решению многомерных задач.

ГЛАВА 2. Диагональный подход к решению задач глобальной

оптимизации

2.1. Общая схема диагональных алгоритмов.

2.2. Диагональные алгоритмы с локальной настройкой

2.2.1. Предварительные замечания

2.2.2. Вычислительная схема алгоритмов .
2.2.3. Условия сходимости.
2.2.4. Численные эксперименты.
2.3. Избыточность традиционных диагональных стратегий
разбиения.
2.4. Безызбыточная стратегия разбиения и ее реализация.
ГЛАВА 3. Методы глобальной оптимизации на основе безызбыточной диагональной стратегии разбиения
3.1. Диагональный информационностатистический алгоритм на
основе безызбыточных разбиений
3.1.1. Предварительные замечания
3.1.2. Вычислительная схема алгоритма.
3.1.3. Условия сходимости.
3.1.4. Численные эксперименты.
3.2. Диагональный алгоритм на основе безызбыточных разбиений
и множественных оценок константы Липшица.
3.2.1. Предварительные замечания.
3.2.2. Оценивание нижних границ значений функции
3.2.3. Нахождение недоминируемых гиперинтервалов
3.2.4. Вычислительная схема алгоритма и анализ сходимости .
3.2.5. Численные эксперименты
ЗАКЛЮЧЕНИЕ
ПРИЛОЖЕНИЕ А. генератор классов тестовых функций
ПРИЛОЖЕНИЕ В. Критерии сравнения методов глобальной
оптимизации на классах тестовых функций
СПИСОК ЛИТЕРАТУРЫ


Разнообразие задач глобальной оптимизации влечет за собой разнообразие подходов к их решению (описанных во многих монографиях и обзорных статьях, см. Необходимо отметить при этом, что, с одной стороны, узко специализированные методы могут быть малоэффективными при решении задач из более широкого класса; с другой стороны, метод, разработанный для решения задач слишком общего класса, может оказаться неприемлемым для решения конкретной прикладной задачи. Например, существуют эффективные методы решения задач линейного программирования (целевая функция и ограничения обладают свойством линейности), являющихся подклассом задач (1. Очевидно, эти методы не подходят для решения более общих задач глобальной оптимизации, за исключением отдельных редких случаев. В то же время задача линейного программирования может быть успешно решена неким общим методом глобального поиска, хотя обычно такой подход к решению задач линейного программирования является непродуктивным в силу неоправданно высоких вычислительных затрат. Этот пример иллюстрирует тот факт, что для успешного и эффективного решения задачи (1. Заметим, что метод глобального поиска может быть дополнен фазой локальной оптимизации, призванной уточнить найденное глобачьное решение (см. Тем не менее, глобальная сходимость должна быть гарантирована именно глобальной частью такого “комбинированного” алгоритма. В противном случае возникает риск потери глобального решения. В то же время необходимо отдавать отчет в том, что исключительно глобальный подход (даже имеющий строго доказываемые теоретические условия сходимости и допускающий непосредственную реализацию на ЭВМ) может потребовать слишком больших вычислительных затрат в ходе решения задачи, особенно на заключительной фазе поиска. В литературе по глобальной оптимизации рассматриваются различные предположения о структуре целевой функции и ограничений (как, например, непрерывность, дифференцируемость, выпуклость, линейность и т. Такие предположения необходимы для построения алгоритмов глобального поиска. Как отмечается, например, в работах [2,3,2,0], при отсутствии предположений о целевой функции и ограничениях любое сколь угодно большое количество вычислений целевой функции не даст гарантии нахождения глобального минимума, так как се поведение может отличаться очень узкими и глубокими пиками и впадинами. Одним из естественных и важных (как в теоретическом, так и в прикладном отношениях) предположений о задаче (1. В таком случае функции называются липшицевыми, а задача (1. I < Ь\х' - *", /хх" е X, (1. Ь = Ь(ф, X) есть некоторая константа (называемая константой Липшица), 0 < Ь < оо, и || • || есть некая норма в пространстве ; в дальнейшем будет использоваться евклидова норма. Условие Липшица допускает простую геометрическую интерпретацию. Допустим, что одномерная липшицева функция ф(х) (с известной константой Липшица Ь) была вычислена в двух точках х' и х" (см. В силу условия (1. Ь(х “ ХИ), X < ХИ. Таким образом, график функции на интервале [хг, хИ] должен располагаться внутри области, ограниченной четырьмя линиями, проходящими через точки (хф(х')) и (хИ,ф(хИ)) с угловыми коэффициентами ±Ь (светлосерый параллелограмм на рис. Следовательно, может быть легко получена оценка наименьшего значения функции ф(х) при ее минимизации на интервале [х х"]. Действительно, ввиду условия Липшица (1. Наименьшее значение функции Ф(ж) на [х*, хп) совпадает таким образом с оценкой наименьшего значения функции ф(х) на данном интервале. Таким образом, условие Липшица (1. Знание степени ограничения скорости изменения целевой функции, выраженной константой Липшица, позволяет конструировать алгоритмы глобального поиска и доказывать их сходимость. В диссертационной работе рассматриваются задачи безусловной лип-шицсвой глобальной оптимизации, которые являются подклассом задач (1. Дх*) =шт/(х), хЕД (1. П = [а,6] = {х Е Е^ : а(Д < х^) < &(. О! < ь||х7 - ж7,||, Ух',х"еД 0 < ? Функция /(х) предполагается заданной в форме “черного ящика”, многоэкстремалыюй, а также недифференцируемой. Следовательно, для решения задачи (1. Кроме того предполагается, что каждое испытание функции (т.