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

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

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



Компьютерные исследования и моделирование:
Год:
Том:
Выпуск:
Страница:
Найти






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


Компьютерные исследования и моделирование, 2019, том 11, выпуск 4, страницы 563–591 (Mi crm730)  

МАТЕМАТИЧЕСКИЕ ОСНОВЫ И ЧИСЛЕННЫЕ МЕТОДЫ МОДЕЛИРОВАНИЯ

О проектировании нуля на линейное многообразие, многогранник и вершину многогранника. Ньютоновские методы минимизации

А. Б. Свириденко

Кубанский государственный университет, филиал в г. Новороссийске, Россия, 353922, г. Новороссийск, ул. Героев Десантников, д. 87

Аннотация: Рассматривается подход к построению методов решения задачи квадратичного программирования для расчета направления спуска в ньютоновских методах минимизации гладкой функции на множестве, заданном набором линейных равенств. Подход состоит из двух этапов.
На первом этапе задача квадратичного программирования преобразуется численно устойчивым прямым мультипликативным алгоритмом в эквивалентную задачу о проектировании начала координат на линейное многообразие, что определяет новую математическую формулировку двойственной квадратичной задачи. Для этого предложен численно устойчивый прямой мультипликативный метод решения систем линейных уравнений, учитывающий разреженность матриц, представленных в упакованном виде. Преимущество подхода состоит в расчете модифицированных факторов Холесского для построения существенно положительно определенной матрицы системы уравнений и ее решения в рамках одной процедуры, а также в возможности минимизации заполнения главных строк мультипликаторов без потери точности результатов. Причем изменения в позиции очередной обрабатываемой строки матрицы не вносятся, что позволяет использовать статические форматы хранения данных.
На втором этапе необходимые и достаточные условия оптимальности в форме Куна–Таккера определяют расчет направления спуска — решение двойственной квадратичной задачи сводится к решению системы линейных уравнений с симметричной положительно определенной матрицей коэффициентов для расчета множителей Лагранжа и к подстановке решения в формулу для расчета направления спуска.
Доказано, что предложенный подход к расчету направления спуска численно устойчивыми прямыми мультипликативными методами на одной итерации требует по кубическому закону меньше вычислений, чем одна итерация по сравнению с известным двойственным методом Гилла и Мюррея. Кроме того, предложенный метод допускает организацию вычислительного процесса с любой начальной точки, которую пользователь выберет в качестве исходного приближения решения.
Представлены варианты постановки задачи о проектировании начала координат на линейное многообразие, выпуклый многогранник и вершину выпуклого многогранника. Также описаны взаимосвязь и реализация методов решения этих задач.

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

DOI: https://doi.org/10.20537/2076-7633-2019-11-4-563-591

Полный текст: PDF файл (476 kB)
Полный текст: http://crm.ics.org.ru/.../2821
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.85
Поступила в редакцию: 02.04.2019
Исправленный вариант: 02.04.2019
Принята в печать:30.04.2019

Образец цитирования: А. Б. Свириденко, “О проектировании нуля на линейное многообразие, многогранник и вершину многогранника. Ньютоновские методы минимизации”, Компьютерные исследования и моделирование, 11:4 (2019), 563–591

Цитирование в формате AMSBIB
\RBibitem{Svi19}
\by А.~Б.~Свириденко
\paper О проектировании нуля на линейное многообразие, многогранник и вершину многогранника. Ньютоновские методы минимизации
\jour Компьютерные исследования и моделирование
\yr 2019
\vol 11
\issue 4
\pages 563--591
\mathnet{http://mi.mathnet.ru/crm730}
\crossref{https://doi.org/10.20537/2076-7633-2019-11-4-563-591}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/crm730
  • http://mi.mathnet.ru/rus/crm/v11/i4/p563

    ОТПРАВИТЬ: 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
  • Компьютерные исследования и моделирование
    Просмотров:
    Эта страница:12
    Полный текст:3
    Литература:2
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019