Вид документа : Статья из журнала Шифр издания : Автор(ы) : Крыжановский Б. В., Крыжановский В. М. Заглавие : Об ускорении процедуры решения задач бинарной оптимизации Серия: Методы оптимизации Место публикации : Известия РАН. Теория и системы управления. - 2009. - N 5. - С. 62-68 (Шифр irts/2009/5) Примечания : Библиогр.: c. 68 (20 назв. ) УДК : 517.98 ББК : 22.162 Предметные рубрики: Математика Функциональный анализ Ключевые слова (''Своб.индексиров.''): задачи бинарной оптимизации--бинарная оптимизация--минимизация квадратичного функционала--многоэкстремальные квадратичные функционалы--локальное поле--бинаризация матриц Аннотация: Исследована задача минимизации многоэкстремального квадратичного функционала, построенного в пространстве состояний с бинарными переменными. Для ускорения вычислений локального поля (аналог градиента в непрерывном пространстве) предлагается бинаризировать матрицу, на которой построен функционал, огрубляя ее элементы по знаку до значений 0, +1. Показано, что процедуру бинаризации можно провести настолько оптимально, что расчетное направление локального поля будет с большей вероятностью совпадать с его истинным направлением. Процедура ориентирована на решение задач в конфигурационном пространстве высокой размерности, поскольку бинаризация матрицы существенно уменьшает необходимый объем оперативной памяти и вычислительную сложность алгоритма. Доп.точки доступа: Крыжановский, В. М. |