Текущий выпуск Номер 1, 2024 Том 16

Все выпуски

Результаты поиска по 'двойственная задача':
Найдено статей: 21
  1. От редакции
    Компьютерные исследования и моделирование, 2018, т. 10, № 3, с. 279-283
    Просмотров за год: 18.
  2. От редакции
    Компьютерные исследования и моделирование, 2019, т. 11, № 4, с. 559-561
    Просмотров за год: 4.
  3. Рассматривается подход к построению методов решения задачи квадратичного программирования для расчета направления спуска в ньютоновских методах минимизации гладкой функции на множестве, заданном набором линейных равенств. Подход состоит из двух этапов.

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

    На втором этапе необходимые и достаточные условия оптимальности в форме Куна–Таккера определяют расчет направления спуска — решение двойственной квадратичной задачи сводится к решению системы линейных уравнений с симметричной положительно определенной матрицей коэффициентов для расчета множителей Лагранжа и к подстановке решения в формулу для расчета направления спуска.

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

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

    Просмотров за год: 6.
  4. От редакции
    Компьютерные исследования и моделирование, 2023, т. 15, № 2, с. 229-233
  5. От редакции
    Компьютерные исследования и моделирование, 2020, т. 12, № 2, с. 259-261
  6. От редакции
    Компьютерные исследования и моделирование, 2023, т. 15, № 3, с. 485-489
  7. Тюрин А.И.
    Прямо-двойственный быстрый градиентный метод с моделью
    Компьютерные исследования и моделирование, 2020, т. 12, № 2, с. 263-274

    В данной работе рассматривается возможность применения концепции $(\delta, L)$-модели функции для оптимизационных задач, в которых посредством решения прямой задачи имеется необходимость восстанавливать решение двойственной задачи. Концепция $(\delta, L)$-модели основана на концепции $(\delta, L)$-оракула, предложенной Деволдером–Глинером–Нестеровым, при этом данные авторы предложили фукнционалы в оптимизационных задачах аппроксимировать сверху выпуклой параболой с некоторым аддитивным шумом $\delta$; таким образом, им удалось получить квадратичные верхние оценки с шумом даже для негладких функционалов. Концепция $(\delta, L)$-модели продолжает эту идею за счет того, что аппроксимация сверху делается не выпуклой параболой, а некоторым более сложным выпуклым функционалом. Возможность восстанавливать решение двойственной задачи хорошо зарекомендовала себя, так как во многих случаях в прямой задаче можно значительно быстрее находить решение, чем в двойственной. Отметим, что прямо-двойственные методы хорошо изучены, но при этом, как правило, каждый метод предлагается под конкретный класс задач. Наша же цель — предложить метод, который бы включал в себя сразу различные методы. Это реализуется за счет использования концепции $(\delta, L)$-модели и адаптивной структуры наших методов. Таким образом, нам удалось получить прямо-двойственный адаптивный градиентный метод и быстрый градиентный метод с $(\delta, L)$-моделью и доказать оценки сходимости для них, причем для некоторых классов задач данные оценки являются оптимальными. Основная идея заключается в том, что нахождение двойственных решений происходит относительно оптимизационной задачи, которая аппроксимируют прямую с помощью концепции $(\delta, L)$-модели и имеет более простую структуру, поэтому находить двойственное решение у нее проще. Стоит отметить, что это происходит на каждом шаге работы оптимизационного метода; таким образом, реализуется принцип «разделяй и властвуй».

  8. Спевак Л.Ф., Нефедова О.А.
    Численное решение двумерного нелинейного уравнения теплопроводности с использованием радиальных базисных функций
    Компьютерные исследования и моделирование, 2022, т. 14, № 1, с. 9-22

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

  9. Лобанов А.И.
    Разностные схемы для уравнения переноса, удовлетворяющие обобщенному условию аппроксимации
    Компьютерные исследования и моделирование, 2018, т. 10, № 2, с. 181-193

    Cтроится семейство явных разностных схем на пятиточечном шаблоне для численного решения линейного уравнения переноса. Анализ свойств разностных схем проводится в пространстве неопределенных коэффициентов. Такие пространства впервые были введены в рассмотрение А. С. Холодовым. Для исследования свойств разностных схем ставилась задача линейного программирования. В качестве целевой функции обычно рассматривался коэффициент при главном члене невязки. Для построения монотонных разностных схем ставилась задача оптимизации с ограничениями типа неравенств. Ограниченность такого подхода становится ясной с учетом того, что аппроксимация разностной схемы определяется лишь на классических (гладких) решениях дифференциальной задачи.

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

    Построение разностной схемы с заданными свойствами тогда опирается на решение задачи поиска минимума функционала.

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

    Приводится пример численной реализации простейшей разностной схемы с обобщенной аппроксимацией.

    Просмотров за год: 27.
  10. Алкуса М.С., Гасников А.В., Двуреченский П.Е., Садиев А.А., Разук Л.Я.
    Подход к решению невыпуклой равномерно вогнутой седловой задачи со структурой
    Компьютерные исследования и моделирование, 2022, т. 14, № 2, с. 225-237

    В последнее время седловым задачам уделяется большое внимание благодаря их мощным возможностям моделирования для множества задач из различных областей. Приложения этих задач встречаются в многочисленных современных прикладных областях, таких как робастная оптимизация, распределенная оптимизация, теория игр и~приложения машинного обучения, такие как, например, минимизация эмпирического риска или обучение генеративно-состязательных сетей. Поэтому многие исследователи активно работают над разработкой численных методов для решения седловых задач в самых разных предположениях. Данная статья посвящена разработке численного метода решения седловых задач в невыпуклой равномерно вогнутой постановке. В этой постановке считается, что по группе прямых переменных целевая функция может быть невыпуклой, а по группе двойственных переменных задача является равномерно вогнутой (это понятие обобщает понятие сильной вогнутости). Был изучен более общий класс седловых задач со сложной композитной структурой и гёльдерово непрерывными производными высшего порядка. Для решения рассматриваемой задачи был предложен подход, при котором мы сводим задачу к комбинации двух вспомогательных оптимизационных задач отдельно для каждой группы переменных: внешней задачи минимизации и~внутренней задачи максимизации. Для решения внешней задачи минимизации мы используем адаптивный градиентный метод, который применим для невыпуклых задач, а также работает с неточным оракулом, который генерируется путем неточного решения внутренней задачи максимизации. Для решения внутренней задачи максимизации мы используем обобщенный ускоренный метод с рестартами, который представляет собой метод, объединяющий методы ускорения высокого порядка для минимизации выпуклой функции, имеющей гёльдерово непрерывные производные высшего порядка. Важной компонентой проведенного анализа сложности предлагаемого алгоритма является разделение оракульных сложностей на число вызовов оракула первого порядка для внешней задачи минимизации и оракула более высокого порядка для внутренней задачи максимизации. Более того, оценивается сложность всего предлагаемого подхода.

Страницы: следующая последняя »

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

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

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

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

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