ПАРАЛЛЕЛЬНЫЕ МЕТОДЫ РЕШЕНИЯ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ Ю.Г. Евтушенко, А.И. Голиков Вычислительный центр им. А.А. Дородницына РАН М.А. Посыпкин Центр Грид-технологий и распределенных вычислений Института системного анализа РАН Москва, ИВМ-2010

Прямая задача ЛП: (P) Двойственная задача ЛП: (D)

Задача нахождения проекции точки на множество решений X * прямой задачи ЛП имеет вид : (1) Функция Лагранжа: Двойственная к (1): Решение внутренней задачи минимизации

Теорема 1. Пусть множество решений X* прямой задачи (P) непусто. Тогда существует такое β*, что при любом β β* проекция точки на множество X* задается формулой где p(β) является решением задачи безусловной минимизации

Теорема 2. Пусть множество решений X * прямой задачи (P) непусто. Тогда для любых и β > 0 решение задачи (D) дается формулой где p(β) является решением задачи безусловной минимизации

P-IV, 2,6 GHz, 1Gb Вычислительный эксперимент m × n × d T (Sec.)Iterat.||Ax-b||||(A T u-c) + |||cTx-bTu||cTx-bTu| 100 × 10 6 × × × × × 10 6 × × × × × 10 6 × × × × × 10 6 × × × × × 10 4 × × × × × 10 4 × × × × × 10 4 × × × × × 10 4 × × × × ×(3·10 6 ) × × × × ×(5·10 6 ) × × × × ×(5·10 7 ) × × × × 10 -7

Компьютер: Celeron 2.02 GHz, 1.0 GB, Win XP Размер Задачи m × n × d Метод Врем я (сек.) Точности Primal Infeas.Dual Infeas.Duality Gap 1500 × × 1 EGM (MATLAB) × × × BPMPD (Interior point) × × × MOSEK (Interior point) × × × CPLEX (Interior point) × × CPLEX (Simplex) × × × × × 0.01 EGM (MATLAB) × × × BPMPD (Interior point) × × × MOSEK (Interior point) × × × CPLEX (Interior point) × × CPLEX (Simplex) × × × ×(3·10 6 ) × 0.01 EGM (MATLAB) × × × BPMPD (Interior point) -Не решил - MOSEK (Interior point) -Не решил - CPLEX (Interior point) × × CPLEX (Simplex) × × × ×(5·10 6 ) × 0.01 EGM (MATLAB) × × × × 10 5 × 1 EGM (MATLAB) × × ×

S(p) выпуклая один раз дифференцируемая кусочно квадратичная функция Градиент: Обобщенная матрица Гессе: D # (t) есть n×n диагональная матрица с i-м элементом

МЕТОД НЬЮТОНА 1) С регулировкой шага Armijo где d s квазиньютоновское направление: 2) Стоп, если ||p s+1 – p s || < tol, иначе положить s =s+1и перейти к 1)

Клеточная схема разбиения данных

Вычислительный комплекс МВС-6000IM Максимальное ускорение 50 на 144 процессорах, клеточная схема, m=10 000, n= , t=28 сек. Максимальное число переменных n= , m=5000, t=232 сек., столбцовая схема на 120 процессорах Максимальное число ограничений m= , n= , t=40 мин., на 80 процессорах.

12 ГЛОБАЛЬНАЯ МИНИМИЗАЦИЯ ФУНКЦИИ - множество решений - множество - решений

ЛЕБЕГОВСКОЕ МНОЖЕСТВО

Условия глобальной оптимальности Критерий глобальной оптимальности 2. Критерий глобальной -оптимальности 3. Для любого набора множеств справедливо

Применение минорант 15 Если - миноранта для, т.е., то

ОСНОВНАЯ ТЕОРЕМА 16 S1S1 S2S2 S3S3 S4S4 S5S5 S6S6 - совокупность множеств рекордная точка Теорема 1. Если выполнено то Поэтому

17 МИНОРАНТА 1 Условие Липшица: Миноранта: Можно исключить из рассмотрения шар радиуса с центром в точке.

18 МИНОРАНТА 2 Градиент удовлетворяет условию Липшица Миноранта Шар радиуса с центром в точке может быть исключен из дальнейшего рассмотрения.

19 МИНОРАНТА 3 Гессиан удовлетворяет условию Липшица

СРАВНЕНИЕ МИНОРАНТ

НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

ОСНОВНАЯ ТЕОРЕМА ДЛЯ НЛП Теорема 1. Если для, выполнено то P

ПРИМЕР ЗАДАЧИ С ИЗОЛИРОВАННОЙ ТОЧКОЙ Tuy H.: D(C)-optimization and robust global optimization. J. Glob. Optimization (2010), v. 47, pp

ПРИМЕР ЗАДАЧИ С ИЗОЛИРОВАННОЙ ТОЧКОЙ

РЕЗУЛЬТАТЫ РАСЧЕТОВ ПРИ РАЗЛИЧНЫХ

УЧЕТ ЦЕЛОЧИСЛЕННОСТИ МетодЧисло итераций Липшицева функция585 Градиент удовлетворяет условию Липшица121 Градиент + сокращение области поиска55 Без учета целочисленности2671

27 ПРИМЕР: ОПТИМАЛЬНЫЙ ДИЗАЙН ОТОПИТЕЛЬНОГО КОТЛА Требуется минимизировать затраты f(x) на производство при соблюдении технологических ограничений g 1 -g 4.

РЕЗУЛЬТАТЫ РАСЧЕТОВ

ТЕСТИРОВАНИЕ НА СЛУЧАЙНЫХ ПОЛИНОМАХ (БМ) СерияBNB-SolverBARONLINDOGLOBAL n=3 m=4 сред n=3 m=6 сред E n=3 m=8 сред 11.24AE

где ρ скалярный параметр, x i и x j трехмерные векторы координат центров аминокислот i и j, соответственно. Функция энергии молекулярного кластера (потенциал Морзе):

31 РЕАЛИЗАЦИЯ МЕТОДОВ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ Много общего в методах решения для различных задач оптимизации: безусловная минимизация, нелинейное программирование, многокритериальное программирование, частично целочисленное и целочисленное программирование Декомпозиционная структура методов решения Большие возможности для распараллеливания

32 ИНСТРУМЕНТАРИЙ BNB-Solver: библиотека решения непрерывных и дискретных задач на кластерах BNB-Grid: программный комплекс для решения непрерывных и дискретных задач в среде распределенных вычислений (ГРИД) Internet

СПАСИБО ЗА ВНИМАНИЕ! ВОПРОСЫ ? 33