Вычислительные методы и программирование
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Выч. мет. программирование:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Выч. мет. программирование, 2013, том 14, выпуск 1, страницы 9–16 (Mi vmp85)  

Вычислительные методы и приложения

Параллельная реализация субградиентного алгоритма для максимизации двойственной функции Лагранжа в задаче о $p$-медиане

И. Л. Васильев, А. В. Ушаков

Институт динамики систем и теории управления СО РАН

Аннотация: Рассматривается алгоритм поиска нижних оценок для оптимального значения в задаче о $p$-медиане, основанный на построении релаксации Лагранжа, а также максимизации двойственной функции с помощью субградиентного метода. Предлагается эффективная схема распараллеливания такого алгоритма, включающая в себя процедуру каскадной сборки данных между процессами. Разработанный алгоритм тестируется на широком наборе модельных примеров большой размерности, в том числе на задачах, размерность которых превосходит известную до настоящего времени из литературы. Полученные результаты подтверждают эффективность предложенной модели распараллеливания. Работа выполнена при частичной финансовой поддержке РФФИ (проекты 12-07-33045-мол_а_вед и 12-01-31198-мол_а), а также СО РАН (интеграционный проект 21).

Ключевые слова: задача о $p$-медиане; параллельное программирование; релаксация Лагранжа; субградиентный метод; MPI.

Полный текст: PDF файл (214 kB)
Тип публикации: Статья
УДК: 519.854.2; 004.272.2
Поступила в редакцию: 19.11.2012

Образец цитирования: И. Л. Васильев, А. В. Ушаков, “Параллельная реализация субградиентного алгоритма для максимизации двойственной функции Лагранжа в задаче о $p$-медиане”, Выч. мет. программирование, 14:1 (2013), 9–16

Цитирование в формате AMSBIB
\RBibitem{VasUsh13}
\by И.~Л.~Васильев, А.~В.~Ушаков
\paper Параллельная реализация субградиентного алгоритма для максимизации двойственной функции Лагранжа в задаче о $p$-медиане
\jour Выч. мет. программирование
\yr 2013
\vol 14
\issue 1
\pages 9--16
\mathnet{http://mi.mathnet.ru/vmp85}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/vmp85
  • http://mi.mathnet.ru/rus/vmp/v14/i1/p9

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Вычислительные методы и программирование
    Просмотров:
    Эта страница:70
    Полный текст:38
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021