Статья посвящена анализу двух быстрых алгоритмов ортогонального проектирования точки на стандартный симплекс. Мы называем их "векторным алгоритмом" и "скалярным алгоритмом", соответственно. Идея векторного алгоритма принадлежит Michelot (1986). Скалярный алгоритм впервые появился в работе Held, Wolfe, Crowder (1974) и получил дальнейшее развитие в работах Maculan, de Paula (1989) и В.Н. Малозёмова, А.Б. Певного (1992). В данной статье представлены усовершенствованные варианты описания и обоснования конечной сходимости обоих алгоритмов, указаны точные оценки количества арифметических операций при их реализации, приведены результаты численных экспериментов по сравнению их трудоемкости. На примерах показано, что в некоторых случаях, когда трудоемкость скалярного алгоритма максимальна, трудоемкость векторного алгоритма минимальна, и наоборот. Рассмотрена также задача ортогонального проектирования точки на телесный симплекс.
Язык оригиналарусский
Страницы (с-по)742–755
ЖурналЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ
Том56
Номер выпуска5
DOI
СостояниеОпубликовано - 2016
Опубликовано для внешнего пользованияДа

    Области исследований

  • квадратичное программирование, проектирование на симплекс, условия оптимальности, быстрые алгоритмы

ID: 7547221