Разделение переменных
В прикладной математике и информатике , разделение переменных — это метод декомпозиции который ослабляет ряд ограничений . [1]
Подробности
[ редактировать ]Когда переменная x появляется в двух наборах ограничений, можно заменить новые переменные x 1 в первом ограничении и x 2 во втором, а затем соединить две переменные новым « связывающим » ограничением. [2] что требует, чтобы
- х 1 = х 2.
Это новое ограничение связи можно ослабить с помощью множителя Лагранжа ; во многих приложениях множитель Лагранжа можно интерпретировать как цену равенства между x 1 и x 2 в новом ограничении.
Для многих задач, когда равенство разделенных переменных ослаблено, система разлагается, и каждая подсистема может быть решена независимо, при существенном сокращении времени вычислений и объема памяти. Решение релаксированной задачи (с расщеплением переменных) дает приближенное решение исходной задачи: далее приближенное решение релаксированной задачи обеспечивает «теплый старт», хорошую инициализацию итерационного метода решения исходной задачи (имея только переменная x ).
Впервые это было предложено Куртом О. Йорнстеном, Микаэлем Нэсбергом, Пером А. Смедсом в 1985 году. В то же время М. Гиньяр и С. Ким представили ту же идею под названием «Разложение Лагранжа» (их статьи появились в 1987 году). Оригинальные ссылки (1) Расщепление переменных: новый подход лагранжевой релаксации к некоторым моделям математического программированияАвторы Курт О. Йорнстен, Микаэль Нэсберг, Пер А. Смедс, тома 84-85 LiTH MAT R.: Издательство Matematiska Institutionen - Университет Линчепинга, факультет математики, 1985 г. Объем - 52 страницы; и (2) Лагранжево разложение: модель, дающая более сильные границы, авторы Моник Гиньяр и Сивхан Ким, Математическое программирование, 39 (2), 1987, стр. 215–228. [2] [3] [4]
Ссылки
[ редактировать ]- ^ Пипацрисават, Узел; Палян, Акоп; Чавира, Марк; Чой, Артур; Дарвич, Аднан (2008). «Решение взвешенных задач Max-SAT в ограниченном пространстве поиска: анализ производительности» . Журнал по логическому моделированию и вычислениям выполнимости (JSAT) . 4 (2008). Калифорнийский университет в Лос-Анджелесе: 4 . Проверено 18 апреля 2022 г.
- ^ Jump up to: а б Вандербей (1991)
- ^ Альварадо (1997)
- ^ Адлерс и Бьорк (2000) Перепечатано как Приложение A, в Микаэле Адлерсе, 2000, Темы в разреженных задачах наименьших квадратов , Линчёпингские исследования в области науки и технологий», Университет Линчёпинга, Швеция.
Библиография
[ редактировать ]- Адлерс, Микаэль; Бьорк, Оке (2000). «Растяжение матрицы для разреженных задач наименьших квадратов». Численная линейная алгебра с приложениями . 7 (2): 51–65. doi : 10.1002/(sici)1099-1506(200003)7:2<51::aid-nla187>3.0.co;2-o . ISSN 1099-1506 .
- Альварадо, Фернандо (1997). «Методы увеличения матриц и их применение». БИТ Численная математика . 37 (3): 473–505. CiteSeerX 10.1.1.24.5976 . дои : 10.1007/BF02510237 . S2CID 120358431 .
- Грчар, Джозеф (1990). Растяжение матриц для линейных уравнений (Технический отчет). Сандианские национальные лаборатории. arXiv : 1203.2377 . Бибкод : 2012arXiv1203.2377G . ПЕСОК90-8723.
- Вандербей, Роберт Дж. (июль 1991 г.). «Разбиение плотных столбцов в разреженных линейных системах» . Линейная алгебра и ее приложения . 152 : 107–117. дои : 10.1016/0024-3795(91)90269-3 . ISSN 0024-3795 .