Все выпуски

[ Switch to English ]

Прямые мультипликативные методы для разреженных матриц. Квадратичное программирование

Свириденко А.Б.
 pdf (322K)  / Список литературы

Рассматривается численно устойчивый прямой мультипликативный метод решения систем линейных уравнений, учитывающий разреженность матриц, представленных в упакованном виде. Преимущество метода состоит в расчете факторов Холесского для положительно определенной матрицы системы уравнений и ее решения в рамках одной процедуры, а также в возможности минимизации заполнения главных строк мультипликаторов без потери точности результатов, причем изменения в позиции очередной обрабатываемой строки матрицы не вносятся, что позволяет использовать статические форматы хранения данных. Решение системы линейных уравнений прямым мультипликативным алгоритмом — это, как и решение с помощью LU-разложения, просто другая схема реализации метода исключения Гаусса.

Расчет факторов Холесского для положительно определенной матрицы системы и ее решение лежит в основе построения новой математической формулировки безусловной задачи квадратичного программирования и новой формы задания необходимых и достаточных условий оптимальности, которые достаточно просты и в данной работе используются для построения новой математической формулировки задачи квадратичного программирования на многогранном множестве ограничений, которая представляет собой задачу поиска минимального расстояния между началом координат и точкой границы многогранного множества ограничений средствами линейной алгебры и многомерной геометрии.

Для определения расстояния предлагается применить известный точный метод, основанный на решении систем линейных уравнений, размерность которых не выше числа переменных целевой функции. Расстояния определяются построением перпендикуляров к граням многогранника различной размерности. Для уменьшения числа исследуемых граней предлагаемый метод предусматривает специальный порядок перебора граней. Исследованию подлежат только грани, содержащие вершину, ближайшую к точке безусловного экстремума, и видимые из этой точки. В случае наличия нескольких ближайших равноудаленных вершин исследуется грань, содержащая все эти вершины, и грани меньшей размерности, имеющие с первой гранью не менее двух общих ближайших вершин.

Ключевые слова: математическое программирование, квадратичное программирование, разреженные матрицы, прямой мультипликативный алгоритм, новые математические формулировки, необходимые и достаточные условия оптимальности, квадратичная задача, линейное программирование, многомерная геометрия
Цитата: Свириденко А.Б. Прямые мультипликативные методы для разреженных матриц. Квадратичное программирование // Компьютерные исследования и моделирование, 2018, т. 10, № 4, с. 407-420
Citation in English: Sviridenko A.B. Direct multiplicative methods for sparse matrices. Quadratic programming // Computer Research and Modeling, 2018, vol. 10, no. 4, pp. 407-420
DOI: 10.20537/2076-7633-2018-10-4-407-420
URL: http://crm.ics.org.ru/journal/article/2707/
Creative Commons License Статья доступна по лицензии Creative Commons Attribution-NoDerivs 3.0 Unported License.
Просмотров за год: 32.

Журнал индексируется в Scopus

Полнотекстовая версия журнала доступна также на сайте научной электронной библиотеки eLIBRARY.RU

Журнал входит в систему  Российского индекса научного цитирования.

Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science

Международная Междисциплинарная Конференция "Математика. Компьютер. Образование"

Международная Междисциплинарная Конференция МАТЕМАТИКА. КОМПЬЮТЕР. ОБРАЗОВАНИЕ.

Copyright © 2009–2024 Институт компьютерных исследований