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

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

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

3 3

4 4 Молекулярный кластер 85 атомов, потенциал Морзе, ρ = 6, f * = (А.А. Станевичюс, В.У. Малкова) ПРИМЕР ОПТИМАЛЬНОЙ КОНФИГУРАЦИИ

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

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

7 7 Набор точек рекордная точка набор множеств

8 Лебеговское множество

9 Миноранта

10 Метод неравномерных покрытий Миноранта Целевая функция 10 ] [[]

11 ОСНОВНАЯ ТЕОРЕМА 11 L1L1 L2L2 L3L3 L4L4 L5L5 L6L6 - рекордная точка Теорема 1. Если выполнено поэтому то

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

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

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

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

16 Декомпозиция исходного множестве X X1X1 X2X2 16

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

18 Многокритериальная оптимизация - непрерывная вектор-функция 18

19 Многокритериальная оптимизация Допустимое множество 19 Множество достижимых критериальных векторов - пространство параметров - пространство критериев

20 Полезные обозначения случай минимизации Точка y лучше, чем a, если, т.е. все Точка y хуже, чем b, если, т.е. все Точки a и c несравнимые.

21 - множество (граница) Парето Допустимое множество Множество достижимых критериальных векторов 21

22 - оболочка Эджворта-Парето 22

23 - множество -Парето Ю. Г. Евтушенко, М. А. Потапов. Методы решения многокритериальных задач. Доклады Академии наук СССР, Т. 291, N 1, С ,

24 24

25 Mixing max/min Точка y лучше, чем a, если Точки a и c несравнимые. Точка y хуже, чем b, если

26 Mixing max/min

27 -Pareto Set

28 -оболочка множества Y

29 Практический пример: построение области достижимости многосекционного робота- манипулятора (Предложен А.П. Карпенко) 29

30 Важность задачи Построение области достижимости многосекционного робота-манипулятора является важнейшей задачей Гарантия точности аппроксимации является очень важной 30

31 Трехсекционный плоский робот- манипулятор 31

32 0.2 c 47.1 c

33 Пятисекционный плоский робот- манипулятор секции: 1.86, 1.86, 1.86, 1.86, 1.86 углы: точность аппроксимации 0.1 Расчеты 4-х фрагментов (юго-запад, юго-восток, северо-восток, северо-запад ) занял примерно 15 минут с использованием 64 х процессоров суперкомпьютера МВС-100К. Для каждого вычисления примерно 1 миллиард вычислений критериев. 33

34 Метод неравномерных покрытий 1. Предложен для безусловной оптимизации в 1971 Ю. Г. Евтушенко, Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке), Ж. вычисл. матем. и матем. физ., 11:6 (1971), 1390– Расширен на случай многих критериев в 1986 Евтушенко Ю. Г., Потапов М. А. «Методы численного решения многокритериальных задач.» ДАН СССР, Т. 291, N 1, 1986, С Расширен на задачи математического программирования в 1992 Yu. G. Evtushenko, M. A. Potapov, V. V. Korotkikh. Numerical methods for global optimization. In "Recent advances in global optimization, Princeton University Press, pp Первая параллельная реализация 2007 Ю. Г. Евтушенко, В. У. Малкова, А. А. Станевичюс. Распараллеливание процесса поиска глобального экстремума. Автоматика и телемеханика, 5. С , Новая техника для задач частично-целочисленного программирования 2011 Ю. Г. Евтушенко, М. А. Посыпкин. Варианты метода неравномерных покрытий для глобальной оптимизации частично-целочисленных нелинейных задач. Доклады Академии наук. Т: С. 168– Обобщенный вариант для задач многокритериальной оптимизации 2012 Ю.Г. Евтушенко, М.А. Посыпкин. Метод неравномерных покрытий для решения задач многокритериальной оптимизации с гарантированной точностью // ЖВМиМФ (в печати)

35 35

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

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

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

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

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

41 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

42 Компьютер: 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) × × ×

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

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

45 Столбцовая схема разбиения данных

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

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

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

49 БЛАГОДАРЮ ЗА ВНИМАНИЕ! 49