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

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

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

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

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

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

6 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

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) × × ×

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

34