Текущий выпуск Номер 4, 2018 Том 10

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

 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
Creative Commons License
Статья доступна по лицензии Creative Commons Attribution-NoDerivs 3.0 Unported License.

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

Журнал входит в Перечень российских рецензируемых научных журналов, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученых степеней доктора и кандидата наук ВАК, группы специальностей: 01.01.00, 01.02.00.
 

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

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

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

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